Глава 7. Нормальные формы более высоких порядков
Глава 7. Нормальные формы более высоких порядков В предыдущей главе были рассмотрены нормальные формы вплоть до третьей нормальной формы (3НФ). В большинстве случаев этого вполне достаточно, чтобы... НФБК (Нормальная Форма Бойса-Кодда)
НФБК (Нормальная Форма Бойса-Кодда) При приведении отношений при помощи алгоритма нормализации к отношениям в 3НФ неявно предполагалось, что все отношения содержат один потенциальный ключ. Это не... Пример 1
Пример 1 . Пусть требуется хранить данные о поставках деталей некоторыми поставщиками. Предположим, что наименования поставщиков являются уникальными. Кроме того, каждый поставщик имеет свой уника... Таблица 1
Таблица 1 Номер поставщика PNUMНаименование поставщика PNAMEНомер детали DNUMПоставляемое количество VOLUME 1 Фирма 1 1 100 1 Фирма 1 2 200 1 Фирма 1 3 300 2 Фирма 2 1 150 2 Фирма 2 2 250 3 Фирма... Таблица 2
Таблица 2 Номер поставщика PNUM Наименование поставщика PNAME 1 Фирма 1 2 Фирма 2 3 Фирма 3 Таблица 2 Отношение "Поставщики"... Таблица 3
Таблица 3 Номер поставщика PNUMНомер детали DNUMПоставляемое количество VOLUME 1 1 100 1 2 200 1 3 300 2 1 150 2 2 250 3 1 1000 Таблица 3 Отношение "Поставки-2"... Определение 1
Определение 1 . Отношение находится в нормальной форме Бойса-Кодда ( НФБК ) тогда и только тогда, когда детерминанты всех функциональных зависимостей являются потенциальными ключами . Замечание .... Таблица 4
Таблица 4 Номер поставщика PNUMНаименование поставщика PNAME 1 Фирма 1 2 Фирма 2 3 Фирма 3 Таблица 4 Отношение "Поставщики"... Таблица 5
Таблица 5 Наименование поставщика PNAMEНомер детали DNUMПоставляемое количество VOLUME Фирма 1 1 100 Фирма 1 2 200 Фирма 1 3 300 Фирма 2 1 150 Фирма 2 2 250 Фирма 3 1 1000 Таблица 5 Отношение "Пос... Пример 2
Пример 2 . Предположим, что нам по-прежнему необходимо учитывать поставки, но каждый акт поставки должен иметь некоторый уникальный номер (назовем его "сквозной номер поставки"). Отношение может и... Таблица 6
Таблица 6 Номер поставщика PNUMНомер детали DNUMПоставляемое количество VOLUMEСквозной номер поставки NN 1 1 100 1 1 2 200 2 1 3 300 3 2 1 150 4 2 2 250 5 3 1 1000 6 4НФ (Четвертая Нормальная Форма)
4НФ (Четвертая Нормальная Форма) Рассмотрим следующий пример. Пусть требуется учитывать данные об абитуриентах, поступающих в ВУЗ. При анализе предметной области были выделены следующие требования... Таблица 7
Таблица 7 Абитуриент Факультет Предмет Иванов Математический Математика Иванов Математический Информатика Иванов Физический Математика Иванов Физический Физика Петров Математический Математика Пет... Таблица 8
Таблица 8 Номер АбитуриентаНомер ФакультетаНомер Предмета 1 1 1 1 1 2 1 2 1 1 2 3 2 1 1 2 1 2 Таблица 8 Модифицированное отношение "Абитуриенты-Факультеты-Предметы"... Таблица 9
Таблица 9 Номер Абитуриента Абитуриент 1 Иванов 2 Петров Таблица 9 Отношение "Абитуриенты"... Таблица 10
Таблица 10 Номер Факультета Факультет 1 Математический 2 Физический Таблица 10 Отношение "Факультеты"... Таблица 11
Таблица 11 Номер ПредметаПредмет 1 Математика 2 Информатика 3 Физика Таблица 11 Отношение "Предметы" Теперь каждое наименование встречается только в одном месте. И все-таки как в исходном, так и в... Определение 2
Определение 2 . Пусть - отношение, и , , - некоторые из его атрибутов (или непересекающиеся множества атрибутов). Тогда атрибуты (множества атрибутов) и многозначно зависят от (обозначается ), тог... Определение 3
Определение 3 . Многозначная зависимость называется нетривиальной многозначной зависимостью , если не существует функциональных зависимостей и . В отношении "Абитуриенты-Факультеты-Предметы" имеет... Теорема (Фейджина)
Теорема (Фейджина) . Пусть , , - непересекающиеся множества атрибутов отношения . Декомпозиция отношения на проекции и будет декомпозицией без потерь тогда и только тогда, когда имеется многозначн... Определение 4
Определение 4 . Отношение находится в четвертой нормальной форме ( 4НФ ) тогда и только тогда, когда отношение находится в НФБК и не содержит нетривиальных многозначных зависимостей . Отношение "А... Таблица 12
Таблица 12 Факультет Абитуриент Математический Иванов Физический Иванов Математический Петров Таблица 12 Отношение "Факультеты-Абитуриенты"... Таблица 13
Таблица 13 Факультет Предмет Математический Математика Математический Информатика Физический Математика Физический Физика Таблица 13 Отношение "Факультеты-Предметы" В полученных отношениях устране... 5НФ (Пятая Нормальная Форма)
5НФ (Пятая Нормальная Форма) Функциональные и многозначные зависимости позволяют произвести декомпозицию исходного отношения без потерь на две проекции. Можно, однако, привести примеры отношений,... Пример 3
Пример 3 . Рассмотрим следующее отношение :... Таблица 14
Таблица 14 X Y Z 1 1 2 1 2 1 2 1 1 1 1 1 Таблица 14 Отношение R Всевозможные проекции отношения , включающие по два атрибута, имеют вид:... Таблица 15
Таблица 15 X Y 1 1 1 2 2 1 Таблица 15 Проекция R1=R[X,Y]... Таблица 16
Таблица 16 X Z 1 2 1 1 2 1 Таблица 16 Проекция R2=R[X,Z]... Таблица 17
Таблица 17 Y Z 1 2 2 1 1 1 Таблица 17 Проекция R3=R[Y,Z] Как легко заметить, отношение не восстанавливается ни по одному из попарных соединений , или . Действительно, соединение имеет вид:... Таблица 18
Таблица 18 X Y Z 1 1 2 1 1 1 1 2 2 1 2 1 2 1 1 Таблица 18 R1 JOIN R2 Серым цветом выделен лишний кортеж, отсутствующий в отношении . Аналогично (в силу соображений симметрии) и другие попарные сое... Определение 5
Определение 5 . Пусть является отношением, а , , …, - произвольными (возможно пересекающимися) подмножествами множества атрибутов отношения . Тогда отношение удовлетворяет зависимости соединения т... Теорема Фейджина (другая формулировка)
Теорема Фейджина (другая формулировка) . Отношение удовлетворяет зависимости соединения тогда и только тогда, когда имеется многозначная зависимость . Т.к. теорема Фейджина является взаимно обратн... Определение 6
Определение 6 . Зависимость соединения называется нетривиальной зависимостью соединения , если выполняется два условия: Одно из множеств атрибутов не содержит потенциального ключа отношения . Ни о... Определение 7
Определение 7 . Зависимость соединения называется тривиальной зависимостью соединения , если выполняется одно из условий: Либо все множества атрибутов содержат потенциальный ключ отношения . Либо... Определение 8
Определение 8 . Отношение находится в пятой нормальной форме ( 5НФ ) тогда и только тогда, когда любая имеющаяся зависимость соединения является тривиальной . Определения 5НФ может стать более пон... Определение 9
Определение 9 . Отношение не находится в 5НФ , если в отношении найдется нетривиальная зависимость соединения . Возвращаясь к примеру 3, становится понятно, что не зная ничего о том, какие потенци... Продолжение алгоритма нормализации (приведение к 5НФ)
Продолжение алгоритма нормализации (приведение к 5НФ) В предыдущей главе был описан алгоритм нормализации как алгоритм приведения отношений к 3НФ. Теперь мы можем продолжить этот алгоритм, доведя... Шаг 4 (Приведение к НФБК)
Шаг 4 (Приведение к НФБК) . Если имеются отношения, содержащие несколько потенциальных ключей, то необходимо проверить, имеются ли функциональные зависимости, детерминанты которых не являются поте... Шаг 5 (Приведение к 4НФ)
Шаг 5 (Приведение к 4НФ) . Если в отношениях обнаружены нетривиальные многозначные зависимости, то необходимо провести декомпозицию для исключения таких зависимостей.... Шаг 5 (Приведение к 5НФ)
Шаг 5 (Приведение к 5НФ) . Если в отношениях обнаружены нетривиальные зависимости соединения, то необходимо провести декомпозицию для исключения и таких зависимостей.... Выводы
Выводы Обобщением 3НФ на случай, когда отношение имеет более одного потенциального ключа, является нормальная форма Бойса-Кодда. Отношение находится в нормальной форме Бойса-Кодда ( НФБК ) тогда и...