Проективность: X -> YZ влечет за собой X -> Z.

Транзитивность: X -> Y и Y -> Z влечет за собой X -> Z.

Псевдотранзитивность: X -> Y и YZ -> W влечет за собой XZ -> W.

Пример.

Пусть дано отношение R , а X , Y и Z подмножества R . Предположим, что отношению удовлетворяет XY -> Z и X -> Y . Согласно аксиоме псевдотранзитивности получим XX -> Z или X -> Z.

Если даны аксиомы рефлексивности, пополнения и псевдотранзитивности, то из них можно вывести все остальные. Иногда их называют аксиомами Армстронга.

Пусть F-множество F-зависимостей для отношения R . Замыкание F , обозначаемое F­­­­⁺ , - это наименьшее содержащее F множество, такое что при применении к нему аксиом Армстронга нельзя получить ни одной F - зависимости, не принадлежащей F.

Пример.

Пусть F = {AB -> C, C -> B } - множество F-зависимостей на R(ABC). F⁺ = {A -> A, AB -> A, AC -> A, ABC -> A, B -> B, AB -> B, BC -> B, ABC -> B, C -> C, AC -> C, BC -> C, ABC -> C, AB -> AB, ABC -> AB, AC -> AC, ABC -> AC, BC -> BC, ABC -> BC, ABC -> ABC, AB -> C, AB -> AC, AB -> BC, AB -> ABC, C -> B, C -> BC, AC -> B, AC -> AB}

Т аким образом, если известно множество F-зависимостей удовлетворяющих отношению R, можно найти все F- зависимости, удовлетворяющие этому отношению. Говорят, что F = X -> Y ,если X -> Y F⁺ .

Лекция 3

П олучение замыкания F⁺ не обязательно для установления F = X -> Y.

Для этого достаточно воспользоваться алгоритмом MEMBER .

Алгоритм MEMBER.

Вход: Множество F-зависимостей F и F-зависимость X -> Y.

В ыход: истина, если F = F = X -> Y, ложь в противном случае.

MEMBER(F, X -> Y)

begin

if Y CLOSURE(X,F) then return (истина)

else return(ложь)

end

Здесь CLOSURE алгоритм, позволяющий выявить список атрибутов входящих в множество F, который имеет вид.

Алгоритм CLOSURE.

Вход: Множество атрибутов Х и множество F-зависимостей F.

Выход: Замыкание Х над F.

CLOSURE(X,F)

begin

OLDDEP = 0; NEWDEP = X

while NEWDEP OLDDEP do begin

OLDDEP = NEWDEP

for каждая F- зависимость W -> Z в F do

if NEWDEP W then

NEWDEP = NEWDEP Z

end

return(NEWDEP)

end

Пример работы алгоритма MEMBER

Пусть F = {НОМЕР_РЕЙСА ДАТА_ВЫЛЕТА -> КОЛИЧЕСТВО_МЕСТ,

НОМЕР_РЕЙСА -> ПУНКТ_ОТПРАВЛЕНИЯ, НОМЕР_РЕЙСА ДАТА_ВЫЛЕТА -> ПИЛОТ} и необходимо установить F |= НОМЕР_РЕЙСА -> ПИЛОТ

Используем для этого алгоритм MEMBER

Покрытия функциональных зависимостей

Для формирования БД, как системы взаимосвязанных отношений на основании известных (из семантических соображений) F-зависимостей необходимо иметь способ минимизации первоначального множества F-зависимостей. Это необходимо для минимизации дублирования данных, обеспечения их согласованности и целостности. Теоретической основой для построения такого способа является теория покрытий функциональных зависимостей.

Определение.

Два множества F-зависимостей F и G над отношением R эквивалентны, , если F⁺ = G⁺ . Если , то F есть покрытие для G. Предполагается, что имеет смысл рассматривать в качестве покрытий такие множества F, которые не превосходят множество G по числу F-зависимостей.

Из этого определения следует, что для установления факта, что множество функциональных зависимостей F является покрытием G , необходимо определить эквивалентность F и G. Практически это достигается путем использования следующего алгоритма:

Алгоритм EQUIV

Вход: два множества F- зависимостей F и G.

Выход: истина, если ; ложь в противном случае.

EQUIV(F,G)

begin

v=DERIVES(F,G) and DERIVES(G,F);

return(v)

end

Здесь DERIVES алгоритм проверяет условие F |= G и имеет вид:

Алгоритм DERIVES

Вход: два множества F- зависимостей F и G.

Выход: истина, если F |= G; ложь в противном случае.

DERIVES(F,G)

begin

v= истина

for каждая F-зависимость X -> Y из G do

v = v and MEMBER(F, X -> Y)

end

return(v)

end

Множество F-зависимостей F не избыточно, если у него нет такого собственного подмножества F’ , что F’ F . Если такое множество F’ существует, то F избыточно. F является не избыточным покрытием G, если F есть покрытие G и F не избыточно.

Пример. Пусть G = { AB -> C, A -> B, B -> C, A -> C}. Множество F= {AB -> C, A -> B, B -> C} эквивалентно G, но избыточно, потому что F’ = {A -> B, B -> C} также является покрытием G. Множество F’ представляет собой не избыточное покрытие G.

Действительно, согласно алгоритму EQUIV , так как DERIVES(F,G) дает истину и DERIVES(G,F) так же истина. То же самое можно сказать относительно F’ и G.

(Подробнее)

Множество F не избыточно, если в нем не существует F-зависимости X -> Y, такой, что F - { X -> Y} |= X -> Y . Назовем F-зависимость из F избыточной в F , если F - { X -> Y} |= X -> Y.

Для любого множества F-зависимостей G существует некоторое подмножество F, такое, что F является не избыточным покрытием G. Если G не избыточно, то F=G. Для определения не избыточного покрытия множества F- зависимостей G существует алгоритм NONREDUN, который имеет вид:

Вход: множество F-зависимостей G.

Выход: не избыточное покрытие G.

NONREDUN(G)

begin

F=G

for каждая зависимость X -> Y из G do

if MEMBER(F-{X->Y],X->Y) then F=F-{X->Y}

end

return(F)

end

Пример: Пусть G= {A -> B, B -> A, B -> C, A -> C}.

Результатом работы алгоритма является множество:

{A -> B, B -> A, A -> C}.

Если бы G было представлено в порядке {A -> B, A -> C, B -> A , B -> C} , то результатом работы алгоритма было бы

{A -> B, B -> A, B -> C}.

Из примера видно, что множество F-зависимостей G может иметь более одного неизбыточного покрытия. Могут так же существовать неизбыточные покрытия G, не содержащиеся в G. В приведенном примере таким неизбыточным покрытием будет множество

F = {A -> B, B -> A, AB -> C}.

Если F-неизбыточное множество F-зависимостей, то в нем нет “лишних” зависимостей в том смысле, что нельзя уменьшить F , удалив некоторые из них. Удаление любой F-зависимости из F приведет к множеству, не эквивалентному F. Однако размер можно уменьшить, удалив некоторые атрибуты F-зависимостей F.

Определение. Пусть F-множество F-зависимостей над R и X -> Y есть F-зависимость из F. Атрибут А из R называется посторонним в X -> Y относительно F, если

1. и (F - {X -> Y}) {Z -> Y} F или

2. Y = AW, Y W и (F - {X -> Y}) {X -> W} F.

Иными словами, А - посторонний атрибут, если он может быть удален из правой или левой части X -> Y без изменения замыкания F.

Пример. Пусть G = {A -> BC,B -> C,AB -> D}. Атрибут С является посторонним в правой части A -> BC, а атрибут B - в левой части AB -> D.

Определение. Пусть F - множество F-зависимостей над R и X -> Y принадлежит F. F-зависимость X -> Y называется редуцированной слева, если Х не содержит постороннего атрибута А и редуцированной справа, если Y не содержит атрибута А , постороннего для X -> y. Зависимость X -> Y называется редуцированной, если она редуцирована слева и справа и Y . Редуцированная слева F-зависимость называется также полной F-зависимостью.

Определение. Множество F-зависимостей F называется редуцированным (слева, справа), если каждая F-зависимость из F редуцирована (соответственно слева, справа).

Пример. Множество G = {A -> BC, B -> C, AB -> D} не является редуцированным ни справа, ни слева. Множество G₁ = {A -> BC, B -> C, A -> D} редуцировано слева, но не справа, а G₂ = {A -> B, B -> C, AB -> D} редуцировано справа, но не слева. Множество G₃ = {A -> B, B -> C, A -> D} редуцировано слева и справа, следовательно, поскольку правые части не пусты, редуцировано.

Для нахождения редуцированных покрытий используется алгоритм:

REDUCE

Вход: множество F-зависимостей G.

Выход: редуцированное покрытие G.

REDUCE(G)

begin

F = RIGHTRED(LEFTRED(G))

удалить из F все F-зависимости вида X ->

return(F)

end

здесь RIGHTRED и LEFTRED алгоритмы редуцирования соответственно справа и слева, которые имеют вид:

RIGHTRED

Вход: множество F-зависимостей G.

Выход: редуцированное справа покрытие G.

RIGHTRED(G)

begin

F = G

for каждая зависимость X -> Y из G do

for каждый атрибут А из Y do

if MEMBER(F - {X -> Y} {X ->(Y - A)}, X -> A) then

удалить А из Y в X -> Y из F

end

end

return(F)

end

Алгоритм LEFTRED

Вход: множество F-зависимостей G.

Выход: редуцированное слева покрытие G.

Begin

F = G

for каждая зависимость X -> Y из G do

for каждый атрибут А из Х do

if MEMBER(F,{X - A) -> Y) then

удалить А из X в X -> Y из F

end

end

return(F)

end

Пример. Пусть G’= {A -> C, AB -> DE, AB ->CDI, AC -> J}.Из LEFTRED(G’) получаем G” = {A -> C, AB -> DE, AB -> CDI, A -> J} и из RIGHTRED(G”) получаем F= {A -> C, AB -> E, AB -> DI, A -> J}, уже редуцированное.

Далее потребуется находить разбиение множества F- зависимостей, заданных на отношении R на подмножества, которые представляют собой классы F- зависимостей с эквивалентной левой частью.

Определение: два множества атрибутов X и Y называются эквивалентными на множестве F- зависимостей F, если F |= X->Y и F |= Y ->X.

Например пусть дано F={A -> BC, B -> A, AD -> E}, найдем все F- зависимости эквивалентные левой части первой, т.е. А. Левая часть второй F- зависимости (В) эквивалентна А ? Проверим F |= A -> B и F |= B -> A . Это действительно так. Следовательно А эквивалентно В и первые две F- зависимости можно объединить в один класс эквивалентности, который обозначается в общем случае Е_А(Х). Множество классов эквивалентности для заданного множества F- зависимостей обозначается _F . Сокращенным способом записи F- зависимостей с эквивалентными левыми частями является составная функциональная зависимость (CF-зависимость), которая имеет вид:

(X₁, X₂, ..., X_k) -> Y

где X₁, X₂, ..., X_k , множество эквивалентных левых частей F- зависимостей, а Y объединение правых частей F- зависимостей.

Синтез реляционных баз данных

База данных состоит из множества атрибутов и ключей. С точки зрения теоретико-множественного описания реляционной базой данных d называется такая совокупность отношений {R₁, R₂, ...,R_p}, в которой каждое отношение имеет вид R_i= (S_i,K_i), где S_i- множество атрибутов, а K_i - множество атрибутов образующих ключ.