Введение в системы БД (542480), страница 117
Текст из файла (страница 117)
Поэтому было бы желательно заменить исходную переменную-отношение СТХ двумя рассматриваемыми проекциями. Это действие будет правомочным в соответствии с теоремой Фейгина (12.13), которая приведена ниже. ° Теорема Фейгина. Пусть А, В и С являются множествами атрибутов переменной- отношения Н(А, В, С). Переменная-отношение Н будет равна соединению ее проекций (А, В) и (А, С) тогда и только тогда, когда для переменной-отношения Н выполняется многозначная зависимостьА -+э В ~ С. (Обратите внимание, что эта теорема является более строгой версией теоремы Хита, описанной в главе 1!.) Теперь, следуя работе Фейгина (12.13), можно дать определение четвертой нормаэьной формы.
(Эта нормальная форма получила такое название потому, что в момент ее появления НФБК все еше считалась третьей нормальной формой.) Глава 12. Дальнейшая нормализаг(ияг более высокие нормальные формы 473 ° Переменная-отношение Н находится в четвертой нормальной форме (4НФ) тогда и только тогда, когда в случае существования таких подмножеств А и В атрибутов этой переменной-отношения Н, для которых выполняется нетривиальная' многозначная зависимость й -+ь В, все атрибуты переменной-отношения Н также функционально зависят от атрибута А. Иначе говоря, в переменной-отношении В могут находиться только нетривиальные зависимости (функциональные нли многозначные) вида К вЂ” ь Х (т.е. некоторый атрибут Х функционально зависит от суперключа К).
Это можно также сформулировать в следующей эквивалентной форме: переменная-отношение Н находится в 4НФ, если она находится в НФБК и все многозначные зависимости в переменной-отношении Н фактически представляют собой функциональные зависимости от ее ключей. Обратите внимание, что, исходя из этого определения, нахождение в 4НФ предполагает обязательное нахождение в НФБК. Переменная-отношение СТХ не находится в 4НФ, поскольку содержит многозначную зависимость, которая не является функциональной, не говоря уже о том, что последняя должна быть еше и функциональной зависимостью от ключа. Однако обе ее проекции, СТ и СХ, находятся в 4НФ.
Следовательно, 4НФ обеспечивает лучшую структуру данных по сравнению с НФБК, поскольку позволяет исключить некоторые нежелательные зависимости. Кроме того, в 112.13) Фейгин показал, что 4НФ всегда является достижимой, т.е. любая переменная-отношение может быть подвергнута декомпозиции без потерь в эквивалентный набор переменных-отношений в 4НФ, Однако, как показано в разделе 11.5 на примере переменной-отношения БЮТ, такая декомпозиция (или даже декомпозиция до НФБК) не всегда оказывается полезной и нужной. Замечание. Следует отметить, что хотя идеи Риссанена, изложенные в посвященной независимым проекциям работе (11.6), сформулированы с использованием функциональных зависимостей, они также справелливы в отношении многозначных зависимостей. Напомним, что в соответствии с этими идеями переменную-отношение Н(й, В, С», удовлетворяющую функциональным зависимостям й ~ В и В ~ С, необходимо разбивать на проекции (А, В) и (В, С), а не на проекции (А, В) и (А, С).
Это утверждение также будет верно, если вместо функциональных зависимостей использовать многознач- ныезависимостиА -ь+ В и В ~-> С. В заключение вернемся, как было обещано, к вопросу об исключении атрибутов, принимающих в качестве значений отношения, или АО (атрибутов-отношений) для краткости. В частности, рассмотрим процедуру такого исключения, описанную в ответе к упр. 11.3 из предыдущей главы. Суть в том, что на практике для достижения 4НФ достаточно учитывать следующее: если мы имеем дело с переменной- отношением с двумя или более независимыми АО, то прел|еде всего следует разделить эти АО. Данное правило имеет не только интуитивно понятный смысл.
Это именно то, что было сделано в ответе к упр. 11.3! Например, в случае переменной- отношения НСТХ прежде всего следует заменить исходную переменную-отношение двумя ее проекциями НОТ(СООНБЕ, ТЕАСНЕНБ) и НСХ(СООВБЕ, ТЕХТБ), где перемен- | МЗЗ А -ьь В называется тривиальной, если либо А является супермноигествал| В, либо объединение А и В образует весь заголовок отношения, 474 Часть 111. Проектирование базы данных ные-отношения ТЕйСНЕНВ и ТЕХТБ все еше сохраняют АО. Далее эти АО можно будет исключить из двух полученных проекций (с приведением их к НФБК) обычным способом, и тогда "проблема", свойственная находящейся в НФБК переменной- отношению СТХ, просто никогда не возникнет.
Как видите, понятия многозначных зависимостей и 4НФ предоставляют формальное обоснование тех правил, которые в противном случае остались бы чисто эмпирическими. 12.3. Зависимости соединения и пятая нормальная форма До сих пор в настоящей главе и на протяжении всей предыдущей главы предполагалось, что единственной необходимой или допустимой операцией в процессе нормализации является замена переменной-отношения по правилам декомпозиции без потерь только двумя ее проекциями. Такое допущение нас вполне устраивало вплоть до достижения 4НФ.
Однако, хотя это может показаться удивительным, существуют переменные- отношения, для которых нельзя выполнить декомпозицию без потерь на две проекции, но которые можно подвергнуть декомпозиции без потерь на три или более проекций. Подобные переменные-отношения обозначим не очень удачным, но достаточно удобным термином "и-декомпозируемая переменная-отношение" (для некоторого и > 2). Это значит, что для данной переменной-отношения возможна декомпозиция без потерь на и проекций, но не на в проекций для любого в <п.
Таким образом, переменную- отношение, для которой можно выполнить декомпозицию на две проекции, следовало бы называть 2-декомпозируемой. Зачечание. Впервые возможность и-декомпозируемости для в > 2 была упомянута в работе Ахо (А!зо), Бери (Веет!) и Ульмана (()!!шап) [12.1), а частный случай для и = 3 был описан Николасом (%со!аз) (12.251. В качестве примера рассмотрим переменную-отношение БРЮ из базы данных поставщиков, деталей и проектов, представленную на рис. 12.4 (в целях упрощения изложения атрибут 0ТТ исключен). Обратите внимание, что эта переменная-отношение состоит только из ключевых атрибутов, не содержит нетривиальных функциональных и многозначных зависимостей н потому находится в 4НФ, Заметим также, что на этом рисунке показаны следующие компоненты.
1, Три бинарные проекции, ВР, РЛ и ЮБ, переменной-отношения БРЮ. 2, Результат соединения проекций ВР и РЮ по атрибуту Р((. 3. Соединение этого результата с проекцией ЮВ по комбинации атрибутов (3Е, БЕ). Обратите внимание, что в результате первого соединения получается копия исходной переменной-отношения БРЮ с одним дополнительным (излишним) кортежем, а в результате второго соединения этот лишний кортеж исключается. Иначе говоря, исходная переменная-отношение ВРЮ является З-декомпозируемой.
Замечание. Независимо от того, какая пара проекций будет выбрана для первого соединения, в итоге будет получен один результат, хотя промежуточные результаты будут в каждом случае разными. Упражнение. Читателю предлагается проверить это утверждение. Глава 12.
Дальнейшая нормализация: более высокие нормальные формы 475 (я1, р1) (р1, 31) (31г в1) (в1, р1, 31) ЕСЛИ И И ТО присутствует в БР присутствует в РЮ, присутствует в 3Б, присутствует в БРЮ. пара пара пара тройка Это верно, поскольку очевилио, что тройка (в1, р1, 31) обязательно присутствует в соединении проекций БР, Рй и ЮБ.(Обратное утверждение, т,е.
если тройка (в1, р1, 31) присутствует в переменной-отношении ЯР3, то, например, пара (в1, р1) присутствует в проекции ЯР, является истинным для любой переменной-отношения БРЮ третьего порядка.) Так как пара (в1, р1) присутствует в отношении БР тогда и только тогда, когда тройка (в1, р1, 32) присутствует в отношении БРЮ для некоторого значения 32 (аналогично для (р1, 31) и (31, в1)), приведенное выше утверждение можно переписать в виде ограничения, накладываемого иа переменную-отношение ЯРЮ.
ЕСЛИ кортежи(в1, р1, 32),(в2, р1, 31),(в1, р2, 31) присутствуютвБРв ТО кортеж (в1, р1, 31) также присутствует в БРЮ. 476 Часть 111. Проектирование базы данных Рис. 12.4. Переменная-отношение ЯРб может быть получена только в результате соединения всех трех ее бинарных проекций, но не любых двух из них Далее, представленный иа рис. 12.4 пример, безусловно, выполнен в терминах отношений, а ие переменных-отношений. Однако 3-декомпозируемость переменной-отношения БРЮ может быть более фундаментальным и ие зависящим от времени свойством (т.е. свойством, которое удовлетворяется для всех допустимых значений данной переменной-отношения), если данная переменная-отношение удовлетворяет определенному ие зависящему от времени ограничению целостности.
Для того чтобы понять, каким именно должно быть это ограничение, прежле всего заметим, что утверждение "переменная-отношение БР3 равна соединению трех своих проекций ЯР, РЮ и ЮЯ" в точности эквивалентно следующему утверждению. Если это утвержление выполняется всегда, т.е. для всех допустимых значений переменной-отношения ЯРЮ, то будет получено не зависящее от времени (хотя и несколько странное) ограничение для данной переменной-отношения. Обратите внимание на циклическую структуру этого ограничения Г'если значение я1 связано с р1 и р1 связано с 31, а 31 связано опять с в1, то а1, р1 и 31 должны находиться в одном кортеже").
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
