10.8 Зависимости соединения и пятая нормальная форма
В предыдущих разделах, посвященных вопросам нормализации отношений, рассматриваются случаи, когда единственно необходимой и допустимой операцией для устранения имеющих место в отношениях проблем является декомпозиция без потерь отношения на две его проекции. Такая декомпозиция решала проблемы, связанные с наличием в отношении многозначной зависимости и ее частного случая – функциональной зависимости, и на такой декомпозиции основывается последовательная нормализация отношений от первой нормальной формы до четвертой.
Однако, возможны случаи, когда устранение в отношении аномалий не может быть достигнуто путем декомпозиции отношения на две его проекции без потерь, в то время как декомпозиция его на три и более проекций обеспечивает отсутствие потерь информации и устранение аномалий. Другими словами, для некоторых отношений возможна декомпозиция без потерь на n проекций, а на меньшее число проекций декомпозиция без потерь невозможна.
Рассмотрим в качестве примера отношение, имеющее следующий набор атрибутов {Студент, Дисциплина, Преподаватель}. В этом отношении представлена информация о студентах, изучающих конкретные дисциплины у конкретных преподавателей. При этом каждый студент изучает несколько дисциплин, каждый преподаватель может преподавать несколько дисциплин и студент может обучаться у нескольких преподавателей. Ключом такого отношения является составной атрибут {Студент, Дисциплина, Преподаватель}, то есть весь кортеж отношения. Это отношение не содержит нетривиальных функциональных и многозначных зависимостей и поэтому полностью удовлетворяет требованиям четвертой нормальной формы.
Теперь допустим, что в отношении имеются следующие кортежи: кортеж, в котором представлена информация о том, что студент Иванов изучает Физику, другой кортеж, в котором указано, что преподаватель Степанов преподает Физику, и третий кортеж, в котором указано, что преподаватель Степанов обучает студента Иванова. Пример фрагмента такого отношения представлен на рис. 10.25.
|
|
|
|
Рис.10.25. Отношение СТУД_ДИСЦ_ПРЕП
В общем случае из трех описываемых этими кортежами фактов совсем не обязательно должно следовать, что студент Иванов изучает Физику именно у преподавателя Степанова. Тем не менее, предположим, что в нашей предметной области имеет место такое правило, определяющее, что из наличия указанных трех фактов обязательно следует, что студент Иванов должен изучать Физику у преподавателя Степанова. При этом, вообще говоря, преподавателю Степанову не запрещено преподавать другие дисциплины, а студенту Иванову изучать Физику и у другого преподавателя.
Это ограничение целостности формально можно сформулировать следующим образом.
Если в каких-либо кортежах отношения R имеются пары значений атрибутов (С1, Д1), (Д1, П1) и (П1, С1), или, что эквивалентно, если в отношении присутствуют кортежи {С1, Д1, П2}, {С2, Д1, П1} и {С1, Д2, П1}, то в этом отношении обязательно также должен быть кортеж вида {С1, Д1, П1}.
Такого вида ограничение называют циклическим, или 3Д-ограничением.
Пример отношения, удовлетворяющего такому ограничению целостности, приведен на рис. 10.26.
|
|
|
|
Рис.10.26. Отношение Студ_Дисц_Преп
Можно заметить, что следствием рассматриваемого циклического или 3Д-ограничения является то, что каждая пара значений атрибутов обязательно должна встречаться в двух экземплярах в разных кортежах. Из-за этого в данном отношении появляются проблемы при выполнении в нем операций обновления данных в кортеже – INSERT, DELETE и UPDATE, так как каждая из этих операций, может затрагивать не один, а большее число кортежей.
Например, если в отношение
|
|
|
|
вставить кортеж {Петров, Физика, Степанов}, то для выполнения 3Д-ограничения также должен быть вставлен и кортеж {Иванов, Физика, Степанов}, так как к уже имеющимся в отношении парам (Иванов, Физика) и (Иванов, Степанов) добавляется третья пара (Физика, Степанов).
Еще пример.
Пусть из отношения
|
|
|
|
требуется удалить кортеж {Петров, Физика, Степанов}. Этот кортеж содержит пары значений (Петров, Физика), (Физика, Степанов) и (Петров, Степанов). В оставшихся после удаления кортежах отсутствует дубликат пары (Петров, Физика), следовательно, удаляемый кортеж не выводится из остающихся, и следовательно, его удаление не нарушит требования 3Д-ограничения.
Если же требуется удалить кортеж {Иванов, Физика, Степанов}, то для каждой его пары (Иванов, Физика), (Физика, Степанов) и (Иванов, Степанов) имеются двойники в других кортежах. Следовательно, для того чтобы требования 3Д-ограничения не нарушились, вместе с кортежем {Иванов, Физика, Степанов} должен быть удален и какой-либо из кортежей с парой-двойником. Возникает только вопрос, какой из трех кортежей должен быть также удален.
Указанные проблемы операций обновления, обусловленные наличием 3Д-ограничения, могут быть решены путем замены рассматриваемого отношения Студ_Дисц_Преп (рис.10.25, 10.26) тремя его бинарными проекциями Студ_Дисц, Дисц_Преп и Студ_Преп, как это показано на рис. 10.27
|
|
|
Рис.10.27. Декомпозиция отношения СТУД_ДИСЦ_ПРЕП
Возникает вопрос, почему необходима декомпозиция на три, а не на два отношения. Можно, однако, увидеть, что соединение любых двух из этих отношений не обеспечивает восстановления исходного отношения. Например, результатом соединения отношений Студ_Дисц и Дисц_Преп по атрибуту Дисциплина будет отношение, представленное на рис. 10.28.
|
|
|
|
Рис.10.28. Соединение отношений СТУД_ДИСЦ и ДИСЦ_ПРЕП
Видно, что это отношение не совпадает с исходным отношением Студ_Дисц_Преп (рис. 10.26). В нем имеется лишний кортеж {Петров, Физика, Кузнецов}, которого не было в отношении СТУД_ДИСЦ_ПРЕП. Если же еще выполнить соединение этого отношения (рис.10.28) с третьим отношением Студ_Преп (рис.10.27) по атрибутам Студент и Преподаватель, то нетрудно увидеть, что лишний кортеж будет исключен и исходное отношение СТУД_ДИСЦ_ПРЕП будет полностью восстановлено.
Поскольку рассматриваемое 3Д-ограничение удовлетворяется тогда и только тогда, когда отношение равносильно соединению трех его проекций, такое ограничение еще называют зависимостью соединения (или зависимостью проекции-соединения).
Зависимость соединения (join dependency) является таким же семантическим ограничением данного отношения, как многозначная и функциональная зависимости. Определение зависимости соединения имеет следующий вид.
Пусть R является отношением, а А, В, …, Z – произвольным подмножеством множества атрибутов отношения R. Отношение R удовлетворяет зависимости соединения *(А, В, …, Z) тогда и только тогда, когда оно равносильно соединению своих проекций с подмножествами атрибутов А, В, …, Z.
Таким образом, для рассматриваемого в этом разделе отношения Студ_Дисц_Преп (рис. 10.26) можно записать, что оно удовлетворяет зависимости соединения *(Студ_Дисц, Дисц_Преп, Студ_Преп) и для устранения аномалий операций обновления может быть представлено своими тремя проекциями {СТУДЕНТ, ДИСЦИПЛИНА}, {ДИСЦИПЛИНА, ПРЕПОДАВАТЕЛЬ} и {СТУДЕНТ, ПРЕПОДАВАТЕЛЬ}.
Сравним приведенные определения зависимости соединения с рассмотренной выше теоремой Фейгина.
Отношение R{А, В, С} может быть декомпозировано без потерь на проекции с атрибутами {А, В} и {А, С} тогда и только тогда, когда для отношения R выполняются многозначные зависимости А →→ В (и А →→ С).
Можно видеть, что фактически многозначная зависимость А →→ В эквивалентна (является частным случаем) зависимости соединения *(АВ, АС).
Другими словами, зависимость соединения является обобщением многозначной зависимости, так же, как ранее многозначная зависимость оказалась обобщением функциональной зависимости. И наоборот, многозначная зависимость является частным случаем зависимости соединения, а функциональная зависимость – частным случаем многозначной зависимости.
Таким образом, мы выяснили, что отношение может находиться в четвертой нормальной форме, но, тем не менее, у него могут быть проблемы операций обновления, связанные с наличием в нем зависимости соединения, не являющейся многозначной зависимостью (в четвертой нормальной форме многозначные зависимости отсутствуют). Эти проблемы могут быть решены путем декомпозиции отношения на три или большее число его проекций. Тем самым отношение приводится к, так называемой, пятой нормальной форме. Дадим ее определение.
Определение пятой нормальной формы.
Отношение R находится в пятой нормальной форме (5НФ), которая также называется проекционно-соединительной нормальной формой, тогда и только тогда, когда каждая зависимость соединения в отношении R подразумевается потенциальными ключами отношения R.
Другими словами, в отношении присутствуют только функциональные зависимости атрибутов от потенциальных ключей.
Пятая нормальная форма является окончательной нормальной формой по отношению к операциям проекции и соединения.
NEXT THEME