Тривиальные и нетривиальные зависимости
Очевидным способом сокращения размера множества ФЗ было бы исключение тривиальных зависимостей, т.е. таких, которые не могут не выполняться. В качестве примера приведем тривиальную ФЗ для отношения SR:
{StNo, GrNo} ® {StNo}
Фактически ФЗ тривиальна тогда и только тогда, когда правая часть символической записи данной зависимости является подмножеством (не обязательно собственным подмножеством) левой части.
Замыкание множества зависимостей и правила вывода Армстронга
Некоторые функциональные зависимости обозначают другие функциональные зависимости. Например, функциональная зависимость:
{StNo}®{GrNo, StName}
подразумевает следующие функциональные зависимости:
{StNo}®{GrNo}
{StNo}®{StName}
Множество всех ФЗ, которые задаются данным множеством функциональных зависимостей S, называется замыканием S и обозначается символом S+.
Поскольку функциональные зависимости являются ограничениями целостности, которые должны быть проверены СУБД, желательно для заданного множества ФЗ S найти такое множество ФЗ которое было бы гораздо меньшего размера, чем множество S, причем каждая ФЗ множества S могла бы быть заменена функциональной зависимостью множества T. Для решения этой задачи следует найти способ вычисления S+ на основе S.
Первой попыткой решить эту проблему была статья Армстронга (Armstrong), в которой представлен набор правил вывода функциональных зависимостей на основе заданных (эти правила также называются аксиомами Армстронга).
|
|
|
Правила вывода Армстронга. Пусть в перечисленных ниже правилах А, В, С и D – произвольные подмножества множества атрибутов заданного отношения R, а символическая запись АВ означает объединение А и В.
1. Рефлексивность: если В является подмножеством А, то А®В.
2. Дополнение: если А®В, то АС®ВС.
3. Транзитивность: если А®В и В®С, то А®С.
Каждое из этих правил может быть непосредственно доказано на основе определения функциональной зависимости (первое из них — это всего лишь определение тривиальной зависимости). Более того, эти правила являются полными в том смысле, что для заданного множества функциональных зависимостей S минимальный набор ФЗ, которые подразумевают все зависимости S, может быть выведен из S на основе этих правил. Они также являются исчерпывающими, поскольку никакие дополнительные ФЗ не могут быть выведены (т.е. ФЗ, которые не подразумеваются зависимостями множества S). Иначе говоря, эти правила могут быть использованы для получения замыкания S+.
Из трех описанных выше правил для упрощения задачи практического вычисления замыкания S можно вывести несколько других правил. (Пусть D – это другое произвольное подмножество множества атрибутов R.).
|
|
|
1. Самоопределение: А®А.
2. Декомпозиция: если А®ВС, то А®В и А®C.
3. Объединение: если A®В и А®С, то А®ВС.
4. Композиция: если А®В и С®D, то AC®BD.
5. Если А®В и С®D, то А È (С – В) ®BD (где символ "È" обозначает объединение множеств, а символ "–" – их разность).Это правило называют также теоремой всеобщего объединения.
Например. Пусть дано некоторое отношение R с атрибутами А, В, С, D, Е, F и следующими ФЗ:
А®{ВС}
В®Е
{CD}®{EF}
Далее символами, записанными подряд, например ВС, будем обозначать множество, состоящее из атрибутов В и С, а не объединение В и С.
Этому примеру можно придать более конкретный смысл, а именно: А – номер сотрудника, В – номер отдела, С – номер руководителя (начальника) данного сотрудника, D – номер проекта, возглавляемого данным руководителем (уникальный для каждого отдельно взятого руководителя), Е – название отдела, F – доля времени, уделяемая данным руководителем заданному проекту.
Показать, что зависимость AD ® F выполняется для отношения R и таким образом принадлежит замыканию данного множества ФЗ.
1. А®ВС (дано);
2. А®С (из 1 согласно декомпозиции);
3. AD®CD (из 2 согласно дополнению);
|
|
|
4. CD®EF (дано);
5. AD®EF (из 3 и 4 согласно транзитивности);
6. AD®F (из 5 согласно декомпозиции).
Неприводимое множество зависимостей
Пусть S1 и S2 являются двумя множествами ФЗ. Если любая ФЗ, которая является зависимостью множества S1, также является зависимостью множества S2, т.е. если S1+ является подмножеством S2+ то S2 называется покрытием для S1. Это значит, что если накладываемые в СУБД ограничения представлены зависимостями множества S2, то в этой СУБД также наложены ограничения на основе зависимостей множества S1.
Далее, если S2 является покрытием для S1, а S1 – покрытием для S2, т.е. если S1+=S2+ , то S1 и S2 эквивалентны. Ясно, что если S1 и S2 эквивалентны и наложенные в СУБД ограничения представлены зависимостями множества S2, то эти ограничения также могут быть представлены зависимостями множества S1, верно также и обратное утверждение.
Множество ФЗ называется неприводимым тогда и только тогда, когда выполняются перечисленные ниже свойства.
1. Правая часть (зависимая часть) каждой ФЗ множества S содержит только один атрибут (т.е. является одноэлементным множеством).
2. Левая часть (детерминант) каждой ФЗ множества S является неприводимой, т.е. ни один атрибут не может быть опущен из детерминанта без изменения замыкания S+ (без конвертирования множества S в некоторое множество, не эквивалентное множеству S). В таком случае ФЗ является неприводимой слева
|
|
|
3. Ни одна функциональная зависимость в S не может быть опущена из S без изменения замыкания S+ (т.е. без конвертирования множества S в некоторое множество, не эквивалентное множеству S).
Множество зависимостей t, которое неприводимо и эквивалентно некоторому другому множеству зависимостей S, называется неприводимым покрытием множества S. Таким образом, с тем же успехом в системе вместо исходного множества зависимостей S может быть использовано его неприводимое покрытие t. Однако следует отметить, что для заданного множества ФЗ не всегда существует уникальное неприводимое покрытие.
Дата добавления: 2018-09-22; просмотров: 495; Мы поможем в написании вашей работы! |
Мы поможем в написании ваших работ!