3.3. Нормальные формы более высокого порядка

3.3.1. Многозначные зависимости

Для введения 4 НФ необходимо ввести понятие многозначной зависимости (МЗ).

Пусть А, В, С – произвольные подмножества множества атрибутов отношения R.

Тогда В многозначно зависит от А тогда и только тогда, когда множество значений В, соответствующее заданной паре значений (значение А, значение С) отношения R, зависит только от А, но не зависит от С.

Обозначается: А 8 В

Говорится: «А многозначно определяет В» или «В многозначно зависит от А» или «А двойная стрелка В».

Упрощенно можно сказать так: А многозначно определяет В, если для каждого значения А не существует единственного соответствующего ей значения В (не верна ФЗ А ® В), но каждое значение А определяет множество соответствующих ей значений В.

По сути ФЗ – это частный случай МЗ:

Пример, который пояснит суть МЗ:

Пусть имеется отношение ДПК (Дисциплина, Преподаватель, Кабинет).

Дисциплина

Преподаватель

Кабинет

ИС

Огородников Е.В.

140

ИС

Огородников Е.В.

218

ИС

Шиляева М.С.

140

ИС

Шиляева М.С.

218

СУБД

Шиляева М.С.

315

СУБД

Шиляева М.С.

411

СУБД

Петухова М.В.

315

СУБД

Петухова М.В.

411

   

Введем следующие ограничения:

a) каждой дисциплине может соответствовать любое количество преподавателей и любое количество кабинетов;

b) преподаватели и кабинеты не зависят друг от друга (т.е. независимо от того, кто преподает данную дисциплину, для этой дисциплины используется один и тот же набор кабинетов);

c) конкретный преподаватель и конкретный кабинет могут быть связаны с любым количеством дисциплин.

В этом случае первичный ключ – множество всех атрибутов.

Проверим, в каких НФ находится это отношение.

1) 1 НФ – т.к. атрибуты неделимы (будем считать, что вместо ФИО преподавателя используется некий код преподавателя, но для удобства в примере будем использовать ФИО).

2) 2 НФ – т.к. неключевых атрибутов вообще нет.

3) 3 НФ – по той же причине.

4) НФБК – не подходит для этого отношения, т.к. в нем нет нескольких перекрывающихся потенциальных ключей.

Попутно можно сделать вывод, что полностью ключевое отношение (если оно в 1 НФ) находится в 3 НФ и в НФБК.

По ограничению b) можно утверждать, что если существуют два кортежа

{Дисциплина1, Преподаватель1, Кабинет1} и

{Дисциплина1, Преподаватель2, Кабинет2},

то существуют и кортежи

{Дисциплина1, Преподаватель1, Кабинет2} и

{Дисциплина1, Преподаватель2, Кабинет1}.

Например, если существуют кортежи

{СУБД, Шиляева М.С., 315} и

{СУБД, Петухова М.В., 411},

то существуют и кортежи

{СУБД, Шиляева М.С., 411} и

{СУБД, Петухова М.В., 315}.

В этом случае отношение явно избыточно и может привести к аномалиям обновления. Например, для добавления информации о том, что дисциплина СУБД будет вестись новым преподавателем Ивановым И.И. необходимо создать столько новых кортежей, сколько кабинетов подходят для этой дисциплины. А при этом ошибочно можно ввести кортежи не для всех кабинетов или, наоборот, с лишними кабинетами.

Существование подобных проблем вызвано, как правило, независимостью атрибутов. В нашем примере – атрибутов Преподаватель и Кабинет.

Как исправить ситуацию, чтобы избежать избыточности и аномалий обновления?

Можно заменить отношение ДПК двумя его проекциями:

ДП (Дисциплина, Преподаватель) и ДК (Дисциплина, Кабинет)

Обе проекции полностью ключевые, следовательно, находятся в НФБК.

Кроме того, это декомпозиция без потерь, т.к. при соединении обратно по атрибуту Дисциплина получим первоначальное отношение ДПК.

Можно сказать, что все эти рассуждения были на интуитивном уровне, из соображений здравого смысла – мы не пользовались какими-либо строгими правилами.

Только в 1971 году эти соображения были формализованы Фейгином с помощью понятия многозначных зависимостей.

Формализуем процесс декомпозиции отношения ДПК. Этого нельзя сделать, основываясь на ФЗ, т.к. диаграмма ФЗ выглядит так:

 


И все ФЗ здесь тривиальны.

Но произведенную декомпозицию можно сделать на основе МЗ, т.к. в отношении их две:

Дисциплина 8 Преподаватель

Дисциплина 8 Кабинет

Первая означает, что хотя для каждой дисциплины не существует единственного соответствующего ей преподавателя (не верна ФЗ Дисциплина ® Преподаватель), но каждая дисциплина определяет множество соответствующих ей преподавателей.

Вторая означает, что хотя для каждой дисциплины не существует единственного соответствующего ей кабинета (не верна ФЗ Дисциплина ® Кабинет), но каждая дисциплина определяет множество соответствующих ей кабинетов.

По этим МЗ и можно произвести декомпозицию.

Можно заметить, что для отношения ДПК многозначная зависимость Дисциплина 8 Преподаватель выполняется тогда и только тогда, когда выполняется МЗ Дисциплина 8 Кабинет.

Для подобных отношений это выполняется всегда, т.е. в обобщенном виде можно сформулировать правило многозначных зависимостей:

Для R (А, В, С) А 8 В тогда и только тогда, когда А 8 С.

Таким образом, МЗ образуют пары и их обычно представляют так: А 8В½С.

Для ДПК можно записать Дисциплины 8 Преподаватели½Кабинеты.

Теорема Фейгина:

Пусть А, В, С – подмножества множества атрибутов отношения R. Отношение R будет равно соединению его проекций {А, В} и {А, С} тогда и только тогда, когда для отношения R выполняется МЗ А 8В½С.

3.3.2. Четвертая нормальная форма

Отношение R находится в 4 НФ тогда и только тогда, когда

если существуют такие подмножества А и В множества атрибутов R, что выполняется нетривиальная МЗ А 8 В,

то все атрибуты отношения R функционально зависят от атрибута А.

Другая формулировка:

Отношение R находится в 4 НФ если оно находится в НФБК и все МЗ отношения R фактически являются ФЗ от потенциальных ключей.

Отношение ДПК из предыдущего примера не находится в 4 НФ, т.к. (по первой формулировке):

1) Существует МЗ Дисциплина 8 Преподаватель, но при этом атрибут Кабинет не зависит функционально от атрибута Дисциплина.

2) Существует МЗ Дисциплина 8 Кабинет, но при этом атрибут Преподаватель не зависит функционально от атрибута Дисциплина.

Но обе проекции ДП и ДК находятся в 4 НФ, т.к. в каждой из них существует по одной МЗ, и других атрибутов (не входящих в эти МЗ) нет.

Фейгин доказал также, что 4 НФ всегда может быть получена, т.е. любое отношение, содержащее МЗ может быть подвергнуто декомпозиции без потерь на набор отношений в 4 НФ.

3.3.3. Зависимость соединения

Не всегда можно произвести декомпозицию без потерь одного отношения на две проекции. Если это невозможно, но возможно разбить отношение на три или более проекций, такое отношение называют n-декомпозируемым, где n – число проекций, на которое можно разбить отношение без потерь.

Например, рассмотрим отношение ЛДС (Литература, Дисциплина, Специальность), полностью ключевое. Это отношение выражает информацию о том, что некая имеющаяся в библиотеке книга подходит для некоторой дисциплины, изучаемой определенной специальностью.

Отношение ЛДС:

Литература

Дисциплина

Специальность

Хомоненко А. и др. Базы данных

СУБД

Информатика с доп. спец. ин. язык

Хомоненко А. и др. Базы данных

ИС

Математика с доп. спец. информатика

Хомоненко А. и др. Базы данных

ИС

Информатика с доп. спец. ин. язык

Дейт К. Введение в системы баз данных

СУБД

Информатика с доп. спец. ин. язык

Дейт К. Введение в системы баз данных

ИС

Информатика с доп. спец. ин. язык

Произведем декомпозицию на три проекции: ЛД, ДС, ЛС.

ЛД ДС ЛС

Литература

Дисциплина

 

Дисциплина

Специальность

 

Литература

Специальность

Хомоненко

СУБД

 

СУБД

Информатика

 

Хомоненко

Информатика

Хомоненко

ИС

 

ИС

Математика

 

Хомоненко

Математика

Дейт

СУБД

 

ИС

Информатика

 

Дейт

Информатика

Дейт

ИС

           

Соединим обратно только две проекции, ЛД и ДС по атрибуту Дисциплина, и сравним кортежи полученного отношения с кортежами первоначального отношения ЛДС:

Литература

Дисциплина

Специальность

 

Хомоненко

СУБД

Информатика

- есть

Хомоненко

ИС

Математика

- есть

Хомоненко

ИС

Информатика

- есть

Дейт

СУБД

Информатика

- есть

Дейт

ИС

Математика

- нет!

Дейт

ИС

Информатика

- есть

В результате получили лишний кортеж.

Аналогичная ситуация будет и при соединении ЛД и ЛС, а также ДС и ЛС.

А если соединить все три проекции, то получим именно первоначальное отношение ЛДС.

Таким образом, можно сделать вывод, что отношение ЛДС 3-декомпозируемо.

В связи с такими n-декомпозициями вводится понятие зависимости соединения (ЗС), на основе которого затем определяется 5 НФ.

Пусть R – отношение, А, В, …, Z – произвольные подмножества множества атрибутов R.

Отношение R удовлетворяет зависимости соединения *(А, В, …, Z) тогда и только тогда, когда оно равносильно соединению своих проекций с подмножествами атрибутов А, В, …, Z.

Для нашего примера отношение ЛДС удовлетворяет зависимости соединения

*(ЛД, ДС, ЛС) или

*({Литература,Дисциплина},{Дисциплина,Специальность},{Литература,Специальность}).

Как ФЗ является частным случаем МЗ, так и МЗ является частным случаем ЗС.

3.3.4. Пятая нормальная форма

Отношение R находится в 5 НФ, которая также называется проекционно-соединительной НФ, тогда и только тогда, когда каждая ЗС в отношении R подразумевается потенциальными ключами отношения R.

Например, рассмотрим отношение Группы (КодГруппы, НазваниеГруппы, Курс, Староста). Имеется два потенциальных ключа: КодГруппы и НазваниеГруппы. Эти ключи подразумевают (т.е. обеспечивают) такие, например, ЗС:

*({КодГруппы, Староста}, {КодГруппы, НазваниеГруппы, Курс})

*({КодГруппы, НазваниеГруппы}, {КодГруппы, Курс}, {НазваниеГруппы, Староста})

и т.п.

А если убрать альтернативный ключ (НазваниеГруппы), оставив единственный потенциальный ключ (КодГруппы), то еще проще:

*({КодГруппы, Курс}{КодГруппы, Староста})

и всё.

Рассмотренное в предыдущем примере отношение ЛДС не в 5 НФ, т.к. ЗС *(ЛД, ДС, ЛС) не подразумевается единственным в этом отношении потенциальным ключом {Литература, Дисциплина, Специальность}.

Найти все ЗС гораздо сложнее, чем ФЗ и МЗ, - нет точного алгоритма такого поиска. То есть процесс проверки отношения на 5 НФ не определен достаточно четко. Утешает то, что на практике подобные отношения встречаются редко.

Из определения 5 НФ можно сделать вывод, что эта НФ является окончательной по отношению к проекции и соединению (это и отражено в ее втором названии).

Таким образом, гарантируется, что отношение в 5 НФ не содержит избыточности данных, которые могут привести к аномалиям обновления.

Проектирование реляционных баз данных


*****
Новосибирск © 2009-2017 Банк лекций siblec.ru
Лекции для преподавателей и студентов. Формальные, технические, естественные, общественные, гуманитарные, и другие науки.