Типы данных
НФ (Пятая Нормальная Форма)
жүктеу/скачать 0,64 Mb.
|
Лекции по БД
- Бұл бет үшін навигация:
- Продолжение алгоритма нормализации (приведение к 5НФ)
- Выводы
5НФ (Пятая Нормальная Форма)Функциональные и многозначные зависимости позволяют произвести декомпозицию исходного отношения без потерь на две проекции. Можно, однако, привести примеры отношений, которые нельзя декомпозировать без потерь ни на какие две проекции. Пример 3. Рассмотрим следующее отношение :
Таблица 14 Отношение R Всевозможные проекции отношения , включающие по два атрибута, имеют вид:
Таблица 15 Проекция R1=R[X,Y]
Таблица 16 Проекция R2=R[X,Z]
Таблица 17 Проекция R3=R[Y,Z] Как легко заметить, отношение не восстанавливается ни по одному из попарных соединений , или . Действительно, соединение имеет вид:
Таблица 18 R1 JOIN R2 Серым цветом выделен лишний кортеж, отсутствующий в отношении . Аналогично (в силу соображений симметрии) и другие попарные соединения не восстанавливают отношения . Однако отношение восстанавливается соединением всех трех проекций: . Это говорит о том, что между атрибутами этого отношения также имеется некоторая зависимость, но эта зависимость не является ни функциональной, ни многозначной зависимостью. Определение 5. Пусть является отношением, а , , …, - произвольными (возможно пересекающимися) подмножествами множества атрибутов отношения . Тогда отношение удовлетворяет зависимости соединения тогда и только тогда, когда оно равносильно соединению всех своих проекций с подмножествами атрибутов , , …, , т.е. . Можно предположить, что отношение в примере 3 удовлетворяет следующей зависимости соединения: . Утверждать, что это именно так мы пока не можем, т.к. определение зависимости соединения должно выполняться для любого состояния отношения , а не только для состояния, приведенного в примере. Покажем, что зависимость соединения является обобщением понятия многозначной зависимости. Действительно, согласно теореме Фейджина, отношение может быть декомпозировано без потерь на проекции и тогда и только тогда, когда имеется многозначная зависимость . Согласно определению зависимости соединения, теорема Фейджина может быть переформулирована следующим образом: Теорема Фейджина (другая формулировка). Отношение удовлетворяет зависимости соединения тогда и только тогда, когда имеется многозначная зависимость . Т.к. теорема Фейджина является взаимно обратной, то ее можно взять в качестве определения многозначной зависимости. Таким образом, многозначная зависимость является частным случаем зависимости соединения, т.е., если в отношении имеется многозначная зависимость, то имеется и зависимость соединения. Обратное, конечно, неверно. Определение 6. Зависимость соединения называется нетривиальной зависимостью соединения, если выполняется два условия: Одно из множеств атрибутов не содержит потенциального ключа отношения . Ни одно из множеств атрибутов не совпадает со всем множеством атрибутов отношения . Для удобства работы сформулируем это определение так же и в отрицательной форме: Определение 7. Зависимость соединения называется тривиальной зависимостью соединения, если выполняется одно из условий: Либо все множества атрибутов содержат потенциальный ключ отношения . Либо одно из множеств атрибутов совпадает со всем множеством атрибутов отношения . Определение 8. Отношение находится в пятой нормальной форме (5НФ) тогда и только тогда, когда любая имеющаяся зависимость соединения является тривиальной. Определения 5НФ может стать более понятным, если сформулировать его в отрицательной форме: Определение 9. Отношение не находится в 5НФ, если в отношении найдется нетривиальная зависимость соединения. Возвращаясь к примеру 3, становится понятно, что не зная ничего о том, какие потенциальные ключи имеются в отношении и как взаимосвязаны атрибуты, нельзя делать выводы о том, находится ли данное отношение в 5НФ (как, впрочем, и в других нормальных формах). По данному конкретному примеру можно только предположить, что отношение в примере 3 не находится в 5НФ. Предположим, что анализ предметной области позволил выявить следующие зависимости атрибутов в отношении : (i) Отношение является полностью ключевым (т.е. потенциальным ключом отношения является все множество атрибутов). (ii) Имеется следующая зависимость (довольно странная, с практической точки зрения): если в отношении содержатся кортежи , и , то отсюда следует, что в отношении содержится также и кортеж . Утверждение. Докажем, что при наличии ограничений (i) и (ii), отношение находится в 4НФ, но не в 5НФ. Доказательство. Покажем, что отношение находится в 4НФ. Согласно определению 4НФ, необходимо показать, что отношение находится в НФБК и не содержит нетривиальных многозначных зависимостей. Т.к. отношение является полностью ключевым, то оно автоматически находится в НФБК. Если бы в отношении имелась многозначная зависимость (необязательно нетривиальная), то, согласно теореме Фейджина, отношение можно было бы декомпозировать без потерь на две проекции. Но пример 3 показывает, что таких декомпозиций нет (здесь мы воспользовались тем, что для доказательства возможности декомпозиции необходимо доказать ее для всех возможных состояний отношения, а для доказательства невозможности достаточно привести один контрпример). Поэтому в отношении нет никаких многозначных зависимостей. Покажем, что отношение не находится в 5НФ. Для этого нужно привести пример нетривиальной зависимости соединения. Естественным кандидатом на нее является . Если это действительно зависимость соединения, то она нетривиальна. Действительно, ни одно из множеств атрибутов , и не совпадает с множеством всех атрибутов отношения и не содержит потенциального ключа. Но является ли такая декомпозиция именно зависимостью соединения? Для этого нужно показать, что декомпозиция на три проекции , и является декомпозицией без потерь для любого состояния отношения (именно здесь содержится ключевая тонкость, обычно пропускаемая при анализе конкретного состояния отношения в примере 3, и именно здесь нам понадобятся знания о предметной области, выраженные в утверждении (ii)). Как и в предыдущих доказательствах, нужно доказать, что для любого состояния отношения . Включение доказывается как в теореме Хеза. Такое включение выполняется всегда для любой декомпозиции отношения . Докажем включение . Пусть кортеж . Это означает, что в проекции содержится кортеж , в проекции содержится кортеж , а в проекции содержится кортеж . По определению проекции, найдутся такие значения , , атрибутов , и соответственно, что отношение содержит кортежи , и . Но тогда по условию (ii) в отношении содержится также и кортеж . Этим доказано необходимое включение. Утверждение доказано.
Отношение находится в нормальной форме Бойса-Кодда (НФБК) тогда и только тогда, когда детерминанты всех функциональных зависимостей являются потенциальными ключами. Нормализация отношений вплоть до нормальной формы Бойса-Кодда основывалась на понятии функциональной зависимости и теореме Хеза, гарантировавшей, что декомпозиция будет происходить без потерь информации. Дальнейшая нормализация связана уже с обобщением понятия функциональной зависимости. Атрибуты (множества атрибутов) и многозначно зависят от , (), тогда и только тогда, когда из того, что в отношении содержатся кортежи и следует, что в отношении содержится также и кортеж к. Корректность дальнейшей декомпозиции основывается на теореме Фейджина, которая говорит о том, что декомпозиция отношения на две проекции является декомпозицией без потерь тогда и только тогда, когда в отношении имеется некоторая многозначная зависимость. Если в отношении имеется функциональная зависимость, то автоматически имеется и тривиальная многозначная зависимость, определяемая этой функциональной зависимостью. Многозначная зависимость называется нетривиальной многозначной зависимостью, если не существует функциональных зависимостей и . Отношение находится в четвертой нормальной форме (4НФ) тогда и только тогда, когда отношение находится в НФБК и не содержит нетривиальных многозначных зависимостей. Имеют место зависимости специального вида, когда отношение не может быть подвергнуто декомпозиции без потерь на две проекции, но может быть декомпозировано на большее число проекций. Такие зависимости называются зависимостями соединения и являются обобщением понятия многозначной зависимости. Отношение находится в пятой нормальной форме (5НФ) тогда и только тогда, когда любая имеющаяся зависимость соединения является тривиальной. жүктеу/скачать 0,64 Mb. Достарыңызбен бөлісу:
|