Замыкание множества зависимостей

Транзитивные зависимости.

Тривиальные и нетривиальные зависимости

Зависимость является тривиальной, если она не может не выполняться. Пример : { S#, P# }→{ S# }. Функциональная зависимость является тривиальной, тогда и только тогда, когда правая часть её символической записи является подмножеством правой части. Тривиальные зависимости в реальной практике не представляют интереса, они рассматриваются только в формальной теории зависимостей.

Функциональная зависимость X→Y называется транзитивной, если существует атрибут Z такой, что имеются функциональные зависимости X→Z и Z→Y и отсутствует функциональная зависимость Z →X

Одни функциональные зависимости могут подразумевать и другие функциональные зависимости.

Например, рассмотрим зависимость.

{ S#, P# }→{ CITY , QTY }

она подразумевает выполнение следующих зависисмостей

{ S#, P# }→{ QTY }

{ S#, P# }→{ CITY }

Множество всех функциональных зависсимостей, которые подразумеваются заданным множеством зависимостей S, называется замыканием множества S и обозначается S⁺ . Для нахождения замыкания используются Аксиомы АРМСТРОНГА, которые представляют собой набор правил для вывода новых функциональных зависимостей.

Пусть А, В ,С – произвольные подмножества множества атрибутов переменной-отношения, а запись АВ обозначает объединение множеств А и В. тогда правила формулируются следующим образом :

· Правило рефлексивности : если множество В является подмножеством множества А, то А→В. является формулировкой тривиальной зависимости.

· Правило дополнения : если А→В, то АС→ВС

· Правило транзитивности : если А→В и В→С, то С→А .

· Правило самоопределения : А→А

· Правило декомпозиции : если А→ВС, то А→В и А→С

· Правило объединения : если А→В и А→С, то А→ВС,

· Правило композиции : если А→В и С→D, то АС→BD

ПРИМЕР : пусть дана переменная-отношение R c атрибутами

A личный номер сотрудника

B номер отдела

C личный номер руководителя для данного сотрудника

D номер проекта, возглавляемого данным руководителем.. Является уникальным для отдельно взятого руководителя.

E название отдела

F время, уделяемое руководителю для данного проекта,

И следующими фунциональными зависимостями

A→BC
B→E

CD→EF.

Докажем, что для заданной переменной-отношения выполняется также функциональная зависимость AD→F.

A→BC (дано)

A→C (следует из п .1 согласно правилу декомпозиции)

AD→CD (следует из п .2 согласно правилу дополнения)

CD→EF (дано)

AD→EF (следует из п .3 и 4 согласно правилу транзитивности)

AD→F (следует из п .5 согласно правилу декомпозиции)