- •Методическая разработка для проведения лекционного занятия по военно-технической подготовке (курс 220)
- •Основные определения
- •Тривиальные и нетривиальные зависимости
- •Замыкание множества зависимостей
- •Замыкание множества атрибутов
- •Неприводимые множества зависимостей
- •Нормализация: формы 1нф, 2нф, 3нф и нфбк
- •Введение
- •Декомпозиция без потерь и функциональные зависимости
- •Первая, вторая и третья нормальные формы
- •Нормальная форма Бойса-Кодда
- •Нормализация: более высокие нормальные формы
- •Многозначные зависимости и четвертая нормальная форма
- •Зависимости соединения и пятая нормальная форма
- •Общая схема процедуры нормализации
- •Заключительная часть
Нормализация: более высокие нормальные формы
В этом разделе будет рассмотрены четвертая и пятая нормальные формы. Для определения 4НФ будет введено многозначной зависимости (МЗЗ), которое является обобщением понятия функциональной зависимости. Аналогично для определения понятия 5НФ будет введено понятие зависимости соединения (ЗС), которая, с вою очередь является обобщением понятия многозначной зависимости.
Многозначные зависимости и четвертая нормальная форма
Прежде чем излагать непосредственно содержание приведения переменных-отношений к четвертой нормальной форме покажем, что переменные-отношения, находящиеся в НФБК могут обладать некоторой избыточностью и, как следствие, иметь некоторые аномалии обновления.
Пример 4.5. В качестве примера рассмотрим переменную-отношение HCTX, каждый кортеж которой состоит из атрибута названия курса (COURSE), а также атрибута-отношения с именами преподавателей (TEACHERS) и атрибута-отношения с названиями учебников (TEXTS). Каждый курс может преподаваться любым из указанных преподавателей с использованием всех указанных учебников. При этом преподаватели и рекомендуемые учебники независимы друг от друга, т.е. независимо от того, кто преподает данный курс, всегда используется один и тот же набор учебников. Вид переменной-отношения HCTX представлен на рис. 4.11.
HCTX |
|
Рис. 4.11. Пример значений данных в переменной-отношении HCTX
Исключив из переменной-отношения значения атрибутов, принимающих в качестве значений отношения, получим переменную-отношение, представленную на рис. 4.12. Данные, помещаемые в переменную-отношение CTX, имеют следующий смыл: кортеж {COURSE:c, TEACHER:t, TEXT:x} появляется в переменной-отношении CTX тогда и только тогда, когда курс c читается преподавателем t с использованием учебника x. Тогда верно ограничение:
ЕСЛИ кортежи (c,t1,x1) и (c,t2,x2) присутствуют одновременно,
ТО кортежи (c,t1,x2) и (c, t2, x1) также присутствуют одновременно.
Очевидно, что переменная-отношение CTX характеризуется избыточностью, вследствие чего возникнут аномалии обновления. Например, при добавлении информации о том, что курс физики может читаться новым преподавателем, необходимо создать два кортежа, по одному на каждый используемый учебник.
CTX |
|
Рис. 4.12. Переменная-отношение CTX, эквивалентная по набору данных переменной-отношению HCTX
Рассматриваемые проблемы возникают в результате того, что преподаватели и учебники совершенно не зависят друг от друга. Ситуация может быть улучшена путем выполнения декомпозиции переменной-отношения CTX на две проекции с атрибутами {COURSE, TEACHER} и {COURSE, TEXT}, как это показано на рис. 4.13.
CT |
|
CX |
|
Рис. 4.13. Значения данных в проекциях CT и CX, соответствующих содержанию переменной-отношения CTX
В этом случае для добавления новой информации о том, что курс физики будет читаться новым преподавателем, достаточно вставить единственный кортеж в переменную-отношение CT. Таким образом, вполне разумно было бы предположить, что для переменных-отношений, подобных CTX, существует некий способ «дальнейшей нормализации».
Фактически очевидно, что переменная-отношение CTX спроектирована плохо и ее декомпозиция на проекции CT и CX является более удачным решением, но с формальной точки зрения это совсем не очевидно. Переменная-отношение CTX вообще не имеет функциональных зависимостей (за исключением тривиальных). Фактически переменная-отношение CTX находится в НФБК.
Существование «проблем», которые связаны с переменными-отношениями в НФБК, подобными переменной-отношению CTX, было замечено достаточно давно, и способы их разрешения также вскоре были сформулированы Фейгином (Fagin) в строгом теоретическом виде с использованием понятия многозначной зависимости (МЗЗ), которое является обобщением понятия функциональной зависимости в том смысле, что каждая функциональная зависимость является многозначной.
Пусть A, B и C являются произвольными подмножествами множества атрибутов переменной-отношения R. Тогда подмножество B многозначно зависит от подмножества A, что символически выражается записью:
A B
(читается как «A многозначно определяет B» или «A двойная стрелка B»), тогда и только тогда, когда множество значений B, соответствующее заданной паре (значение A, значение C) переменной-отношения R, зависит от A, но не зависит от C.
Для данной переменной-отношения R {A,B,C} многозначная зависимость A B выполняется тогда и только тогда, когда также выполняется многозначная зависимость AC. Таким образом, многозначные зависимости всегда образуют связанные пары.
Для рассматриваемого примера это значит следующее:
COURSE TEACHER | TEXT
Описанная ранее проблема с переменной-отношения CTX возникает из-за того, что она содержит многозначные зависимости, которые не являются функциональными. Проекции CT и CX не содержат многозначных зависимостей, а поэтому представляют некоторое усовершенствование исходной структуры. Подобная декомпозиция основывается на применении теоремы Фейгина.
Теорема Фейгина. Пусть A, B и C являются множествами атрибутов переменной-отношения R{A,B,C}. Переменная-отношение R будет равна соединению ее проекций {A,B} и {A,C} тогда и только тогда, когда для переменной-отношения R выполняется многозначная зависимость A B | C.
Теперь стало возможным дать определение четвертой нормальной формы.
Переменная-отношение R находится в четвертой нормальной форме (4НФ) тогда и только тогда, когда в случае существования таких подмножеств A и B атрибутов этой переменной-отношения R, для которых выполняется нетривиальная многозначная зависимость A B, все атрибуты переменной-отношения R также функционально зависят от атрибута A.
МЗЗ A B называется тривиальной, если либо A является супермножеством B, либо объединение A и B образует весь заголовок отношения.
Иначе говоря, переменная-отношение R находится в 4НФ, если она находится в НФБК и все многозначные зависимости в переменной-отношении R фактически представляют собой функциональные зависимости от ее ключей.
Переменная-отношение CTX не находится в 4НФ, поскольку содержит многозначную зависимость, которая не является функциональной, не говоря уже о том, что последняя должна быть еще и функциональной зависимостью от ключа. Однако обе проекции CT и CX находятся в 4НФ. Следовательно, 4НФ обеспечивает лучшую структуру данных по сравнению с НФБК, поскольку позволяет исключить некоторые нежелательные зависимости. Фейгин показал, что 4НФ всегда является достижимой.