- •Технологии бд
- •1. Теоретические основы организации бд. Реляционная модель данных. 2
- •2. Технологии проектирования реляционных бд 24
- •Теоретические основы организации бд. Реляционная модель данных.
- •Подходы к организации баз данных
- •Иерархические базы данных
- •Сетевые базы данных
- •Реляционные базы данных
- •12 Правил Кодда:
- •Введение в реляционную модель данных
- •Основные понятия реляционной модели данных
- •Тип данных
- •Заголовок отношения, кортеж, тело отношения, значение отношения, переменная отношения
- •Первичный ключ и интуитивная интерпретация реляционных понятий
- •Фундаментальные свойства отношений
- •Отсутствие кортежей-дубликатов, первичный и возможные ключи отношений
- •Отсутствие упорядоченности кортежей
- •Отсутствие упорядоченности атрибутов
- •Атомарность значений атрибутов, первая нормальная форма отношения
- •Реляционная модель данных
- •Общая характеристика
- •Целостность реляционных данных
- •Null-значения
- •Трехзначная логика (3vl)
- •Потенциальные ключи
- •Целостность сущностей
- •Внешние ключи
- •Целостность внешних ключей
- •Замечания к правилам целостности сущностей и внешних ключей
- •Операции, могущие нарушить ссылочную целостность
- •Стратегии поддержания ссылочной целостности
- •Технологии проектирования реляционных бд
- •Этапы разработки базы данных
- •Критерии оценки качества логической модели данных
- •Адекватность базы данных предметной области
- •Легкость разработки и сопровождения базы данных
- •Скорость операций обновления данных (вставка, обновление, удаление)
- •Скорость операций выборки данных
- •Проектирование реляционных баз данных на основе принципов нормализации
- •Понятие метода нормализации отношений
- •Декомпозиция без потерь и функциональные зависимости
- •Корректные и некорректные декомпозиции отношений. Теорема Хеза
- •Теорема Хеза.
- •Диаграммы функциональных зависимостей
- •Первая нормальная форма
- •Минимальные функциональные зависимости и вторая нормальная форма
- •Аномалии обновления, возникающие из-за наличия неминимальных функциональных зависимостей
- •Возможная декомпозиция
- •Вторая нормальная форма
- •Нетранзитивные функциональные зависимости и третья нормальная форма
- •Аномалии обновлений, возникающие из-за наличия транзитивных функциональных зависимостей
- •Возможная декомпозиция
- •Третья нормальная форма
- •Независимые проекции отношений. Теорема Риссанена
- •Перекрывающиеся возможные ключи и нормальная форма Бойса-Кодда
- •Аномалии обновлений, связанные с наличием перекрывающихся возможных ключей
- •Нормальная форма Бойса-Кодда
- •Всегда ли следует стремиться к bcnf?
- •Необходимость дальнейшей нормализации
- •Многозначные зависимости и четвертая нормальная форма
- •Аномалии обновлений при наличии многозначных зависимостей и возможная декомпозиция
- •Многозначные зависимости. Теорема Фейджина. Четвертая нормальная форма
- •Лемма Фейджина
- •Теорема Фейджина
- •Зависимости проекции/соединения и пятая нормальная форма
- •N-декомпозируемые отношения
- •Зависимость проекции/соединения
- •Аномалии, вызываемые наличием зависимости проекции/соединения
- •Устранение аномалий обновления в 3-декомпозиции
- •Пятая нормальная форма
- •Заключение
- •Проектирование реляционных баз данных с использованием семантических моделей: er-диаграммы
- •Ограниченность реляционной модели при проектировании баз данных
- •Семантические модели данных
- •Семантическая модель Entity-Relationship (Сущность-Связь)
- •Основные понятия er-модели
- •Уникальные идентификаторы типов сущности
- •Нормальные формы er-диаграмм
- •Первая нормальная форма er-диаграммы
- •Вторая нормальная форма er-диаграммы
- •Третья нормальная форма er-диаграммы
- •Более сложные элементы er-модели
- •Наследование типов сущности и типов связи
- •Взаимно исключающие связи
- •Получение реляционной схемы из er-диаграммы
- •Базовые приемы
- •Представление в реляционной схеме супертипов и подтипов сущности
- •Представление в реляционной схеме взаимно исключающих связей
- •Виды нотаций er-диаграмм
- •Метод Баркера
- •Методология idef1x
- •Заключение
Многозначные зависимости. Теорема Фейджина. Четвертая нормальная форма
Заметим, что последний вариант переменной отношения СЛУЖ_ПРО_ЗАДАНнаходится в BCNF, поскольку все атрибуты заголовка отношения входят в состав единственно возможного ключа. В этом отношении вообще отсутствуют нетривиальные FD. Поэтому ранее обсуждавшиеся принципы нормализации здесь неприменимы, но, тем не менее, мы получили полезную декомпозицию. Все дело в том, что в случае четвертого варианта отношенияСЛУЖ_ПРО_ЗАДАНмы имеем дело с новым видом зависимости, впервые обнаруженным Роном Фейджином в 1971 г. Фейджин назвал зависимости этого вида многозначными (multi-valued dependency – MVD). Как мы увидим немного позже, MVD является обобщением понятия FD.
В отношении СЛУЖ_ПРО_ЗАДАНвыполняются две MVD:СЛУ_НОМПРО_НОМиСЛУ_НОМСЛУ_ЗАДАН. Первая MVD означает, что каждому значению атрибутаСЛУ_НОМсоответствует определяемое только этим значением множество значений атрибутаПРО_НОМ. Другими словами, в результате вычисления алгебраического выражения
(СЛУЖ_ПРО_ЗАДАН WHERE (СЛУ_НОМ = сн AND СЛУ_ЗАДАН = сз)) PROJECT {ПРО_НОМ}
для фиксированного допустимого значения сни любого допустимого значениясзмы всегда получим одно и то же множество значений атрибутаПРО_НОМ. Аналогично трактуется вторая MVD.
В переменной отношенияrс атрибутамиA,B,C(в общем случае, составными) имеетсямногозначная зависимость BотA (AB)в том и только в том случае, когда множество значений атрибутаB, соответствующее паре значений атрибутовAиC, зависит от значенияAи не зависит от значенияC.
Многозначные зависимости обладают интересным свойством "двойственности", которое демонстрирует следующая лемма.
Лемма Фейджина
В отношении r {A, B, C}выполняется MVDABв том и только в том случае, когда выполняется MVDAC.
Таким образом, MVD ABиACвсегда составляют пару. Поэтому обычно их представляют вместе в формеA B | C.
FD является частным случаем MVD, когда множество значений зависимого атрибута обязательно состоит из одного элемента. Таким образом, если выполняется FD AB, то выполняется и MVDAB.
Мы видим, что отношения СЛУЖ_ПРО_НОМиСЛУЖ_ЗАДАНИЕне содержат MVD, отличных от FD, и именно в этом выигрывает декомпозиция из Рис. 23. Правомочность этой декомпозиции доказывается приведенной ниже теоремой Фейджина, которая является уточнением и обобщением теоремы Хеза.
Теорема Фейджина
Пусть имеется переменная отношения rс атрибутамиA,B,C(в общем случае, составными). Отношениеrдекомпозируется без потерь на проекции{A, B}и{A, C}тогда и только тогда, когда для него выполняется MVDA B | C.
Теорема Фейджина обеспечивает основу для декомпозиции отношений, удаляющей "аномальные" многозначные зависимости, с приведением отношений в четвертую нормальную форму.
Определение: Четвертая нормальная форма
Переменная отношенияrнаходится вчетвертой нормальной форме (4NF)в том и только в том случае, когда она находится в BCNF, и все MVDrявляются FD с детерминантами – возможными ключами отношенияr.
В сущности, 4NF является BCNF, в которой многозначные зависимости вырождаются в функциональные. Понятно, что отношение СЛУЖ_ПРО_ЗАДАНне находится в 4NF, поскольку детерминант MVDСЛУ_НОМПРО_НОМиСЛУ_НОМСЛУ_ЗАДАНне является возможным ключом, и эти MVD не являются функциональными. С другой стороны, отношенияСЛУЖ_ПРО_НОМиСЛУЖ_ЗАДАНИЕнаходятся в BCNF и не содержат MVD, отличных от FD с детерминантом – возможным ключом. Поэтому они находятся в 4NF.