Функциональные зависимости.

Пусть дана схема R с атрибутами А1, А2, … An и пусть X и Y являются подмножеством R. Тогда говорят, что X функционально определяет Y или Y функционально зависит от X, если для любого отношения r со схемой R невозможно существование двух кортежей, у которых значение атрибутов из Х попарно совпадают, а значения хотя бы одного атрибута из Y отличаются.

Другими словами, для любых двух кортежей t1 и t2 из таблицы r со схемой R и с заданной функциональной зависимостью X->Y, попарное равенство атрибутов из множества Х логически влечет попарное равенство атрибутов из множества Y.

В примере с поставщиками имеются следующие функциональные зависимости:

{Имя }–> {Адрес}

{Имя, товар}->{Цена}

Используя реляционную алгебру, можно дать другое определение функциональной зависимости:

Пусть r – отношение со схемой R. X и Y – подмножества R, тогда отношение r удовлетворяет функциональной зависимости X->Y, если формула 1 всегда имеет не более одного кортежа для любой константы, то есть, если мы имеет зависимость X->Y, то сделав селекцию по атрибутам из Х, а затем сделав проекцию на Y, мы не получим более одного кортежа.

Функциональные зависимости выявляются внимательным изучением смысла атрибутов. Зависимости – утверждение о предметной области, которые должны быть реализованы в базе данных. Когда функциональные зависимости выбраны, применяется аппарат, позволяющий на их основе спроектировать структуру базы данных.

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

Определение логического следования.

Пусть F – множество функциональных зависимостей, заданных на схеме R. Будем говорить, что F логически влечет функциональную зависимость X->Y (F), если каждое отношение r со схемой R, удовлетворяющее F, также удовлетворяет и зависимости X->Y.

Пусть задано множество функциональных зависимостей F. Замыканием множества функциональных зависимостей F называется множество всех функциональных зависимостей, которые логически следуют из F. Обозначается F+.

Используя понятие функциональной зависимости, можно дать определение ключа.

Пусть задана схема R с атрибутами А1, А2,…,An и множество функциональных зависимостей F.

2) не существует множества Y, являющегося подмножеством X, такого, что Y->

Второй пункт требует, чтобы ключ был минимальным.

У схемы отношения с заданным множеством функциональных зависимостей может существовать несколько ключей. Из них выбирается один – первичный, остальные считаются вторичными, или вспомогательными. Множество атрибутов, содержащих ключ, называются суперключом.

Аксиомы функциональных зависимостей.

Для определения ключей отношения и для анализа логических свойств базы данных необходимо знать, как строить замыкание функциональных зависимостей. Для этого необходим набор правил вывода, или аксиом. Такой набор аксиом называется аксиомами Армстронга.

Пусть задана схема отношения со множеством атрибутов U.

1) Рефлексивность.

Доказательство. Сделав селекцию по атрибутам X, получаем либо пустое множество, либо множество кортежей, у которых все атрибуты из X имеют одинаковые значения. Спроецировав их на атрибуты из Y после отбрасывания дубликатов, больше одного кортежа мы не получим. Таким образом, X->Y.

Эта аксиома утверждает тривиальные зависимости, которые не зависят от F (которые не могут не выполняться).

2) Пополнение.

Эта аксиома доказывается методом от противного. Допустим, что существуют два кортежа t1 и t2, которые нарушают функциональную зависимость XZ->YZ, но при этом удовлетворяют первой функциональной зависимости, то есть у них атрибуты на XZ совпадают, а на YZ отличаются. В YZ атрибуты Z отличаться не могут, исходя из вышесказанного. Следовательно, должны отличаться атрибуты Y, то есть получается, мы имеем дело с двумя кортежами, у которых атрибуты X совпадают, а атрибуты Y – разные. Это противоречит посылке X->Y.

3) Транзитивность.

Это можно доказать прямым выводом из функциональных зависимостей. Возьмем два кортежа t1 и t2 из отношения r. Если мы предположим, что t1(x)=t2(x), то мы получим, что t1(y)=t2(y). Следовательно, t1(z)=t2(z), а это является определением функциональной зависимости.

Эти три аксиомы являются полными и непротиворечивыми, то есть из них можно вывести все зависимости, которые логически следуют из заданных зависимостей и невозможно вывести зависимость, которая логически не следует из заданной зависимости.

Дополнительные правила вывода.

На основе аксиом Армстронга можно доказать ряд теорем, которые могут быть полезными.

1. Аддитивность.

2. Псевдотранзитивность.

3. Проективность.

Замыкание множества атрибутов.

Важное следствие правил аддитивности и проективности: если A1, A2,…,An – атрибуты отношения, то X→A1, A2, …, An истинно тогда и только тогда, когда X→Ai, i=1…n

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

Пример:

A1→A2 A3 A4

Используя правило проективности, можно вывести следующие зависимости:

A1→A2

A1→A3

A1→A4

A1→A2 A3

A1→A2 A4

A1→A3 A4

Таким образом, для каждого множества функциональных зависимостей с одинаковыми левыми частями, достаточно иметь множество атрибутов, которые могут встретиться в левой части.

Определение. Пусть F – множество функциональных зависимостей на множестве атрибутов U и пусть X с U. Замыканием множеством атрибутов X по отношению к функциональным зависимостям F называется множество атрибутов, для которых функциональная зависимость от X выводится на основе аксиом Армстронга.

Формула х+

Для того, чтобы проверить, что зависимость X→Y следует из F, достаточно проверить принадлежность множества Y к множеству X+. Это следует из определение замыкания множества атрибутов и правила аддитивности.

Алгоритм вычисления замыкания множества атрибутов.

Входные данные:

- множество атрибутов U, определяющих схему отношения,

- F – множество функциональных зависимостей, заданных на U,

- X – множество атрибутов, для которых необходимо построить замыкание X+.

Выходные данные:

Х+ - замыкание множества атрибутов Х+ относительно множества функциональных зависимостей F.

Метод: начнем строить Х+ с множества Х (то есть внесем сначала тривиальные зависимости). Затем будем в цикле добавлять в него новые атрибуты, используя аксиомы транзитивности и рефлексивности.

Нам потребуются две переменные, Xpred и Xsucc.

Пример:

Пусть F состоит из следующих 8 зависимостей

1. AB→C

2. C→A

3. BC→D

4. ACD→B

5. D→BG

6. BE→C

7. CG→BD

8. CE→AG

X=BD

Применив 6, получаем

2,8 →

В итоге Х+

Используя алгоритм вычисления замыкания множества атрибутов, можно построить алгоритм проверки принадлежности функциональной зависимости к множеству F+.

Алгоритм:

Вход:

- F

- X→Y.

Выход: истина, если X→Y принадлежит F+

Имея F и X, строим Х+. Если Y принадлежит X+, то истина, иначе ложь. Используя этот алгоритм, можно проверить принадлежность замыканию F+, имея F и не строя F+.

Минимальное покрытие.

Функциональные зависимости для каждого отношения в общем случае могут быть представлены несколькими случаями.

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

Определение. Два множества функциональных зависимостей F и G, заданные на схеме R, эквивалентны, если F+=G+, то есть если совпадают их замыкания.

Проверим эквивалентность двух множеств функциональной зависимости F и G. Проверим по очереди все зависимости вида X→Y из F на принадлежность к G+ (используя предыдущий алгоритм). Если для всех элементов это справедливо, то есть F является подмножеством G+, то можно заключить, что и F+ является подмножеством G+ (1).

Это следует из определения замыкания множеств функциональных зависимостей: если функциональные зависимости входят в замыкание, то в него входят и все их следствия, полученные на основе аксиом Армстронга.

Далее проверяем функциональные зависимости из G на принадлежность к F+. Если это так, то G+ является подмножеством F+ (2).

Из условий 1 и 2 имеем, что F+=G+, то есть F эквивалентно G.

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

Определение: Множество функциональных зависимостей F называется минимальным, если

- правая часть каждой зависимости из F имеет единственный атрибут,

- ни для какой зависимости X→A из F не выполняется, что F эквивалентно F-{X→A}, то есть нет такой зависимости в F, выбросив которую F+ не изменится.

- ни у одной функциональной зависимости нет ни одного постороннего атрибута в левой части, то есть такого атрибута, при удалении которого F­­­­­­⁺, то есть нет функциональной зависимости X→A, у которой для собственного подмножества справедливо F-{X→A}U{Z→A}= F.

Алгоритм построения минимального покрытия.

Имеет те же самые три шага.

1. Каждую функциональную зависимость X→Y, где Y={A1, A2, …, An} заменяем на {X→A1, X→A2, …, X→An}

2. Проверяем каждую функциональную зависимость X→A на избыточность в F. Если X⁺, вычисленное относительно F-{X→A}, содержит атрибут A, то зависимость X→A избыточна.

3. Определяем, является ли атрибут Bϵ принадлежащий множеству X, посторонним в функциональной зависимости X→A. Можно показать, что его можно удалить, если Aϵ(X-{B})⁺

Доказательство: Если Aϵ(X-{B})⁺, то (X-{B})→AϵF⁺

X→A (X-{B})→A

X→AB

X→A

Каждое множество функциональных зависимостей имеет минимальное покрытие, которых может быть несколько.

Декомпозиция схем отношений.

Декомпозицией реляционной схемы R с атрибутами A1, A2, …, An называется ее замена на множество подмножеств ρ={R1,R2,…,Rk} таких, что Ri с R для каждого i=1…k и R=R1 U R2 U… U Rk.

Схемы членов декомпозиций могут пересекаться. Не любая декомпозиция позволяет восстанавливать исходное отношение, а только та, которая обладает свойством соединения без потерь.

Для заданной схемы отношения R и множества функциональных зависимостей F декомпозиция ρ обладает свойством соединения без потерь и называется декомпозицией без потерь, если для каждого отношения r со схемой R, не нарушающего F, справедливо следующее: r=π_R1(r)|><| π_R2(r)|><|…|><| π_R1(r)

Пример. Возьмем отношение со схемой Поставщик (имя, адрес, товар, цена), которое представлено следующей таблицей:

Имя → адрес

{Имя, товар} → цена

ρ={{имя, адрес},{имя, товар, цена}}

Данные, соответствующие декомпозиции, распределены следующим образом:

Соединим таблицы, соответствующие декомпозиции отношений, получим исходное отношение.

Так получится, потому что мы использовали декомпозицию, обладающую свойством соединения без потерь.

Рассмотрим теперь декомпозицию, в которой будут потери.

ρ={{имя, адрес, товар} {товар, цена}}

Данные теперь распределятся следующим образом:

Соединим таблицы, соответствующие декомпозиции отношений, получим следующее отношение.

Отметим, что функциональная зависимость {Имя, товар} → цена перестала работать и появились лишние кортежи (2 и 5). Эта декомпозиция была бы без потерь, если бы для каждого товара была определена фиксированная цена, то есть если бы существовала зависимость товар → цена, либо каждый товар поставлял определенный поставщик, то есть выполнялась бы зависимость товар → {имя, адрес}.

Формально справедливо следующее: декомпозиция ρ={R1,R2} имеет свойство соединения без потерь по отношению к множеству функциональных зависимостей F тогда и только тогда, когда выполняются следующие условия:

(R1∩R2)→(R1-R2)

(R1∩R2)→(R2-R1)

То есть общие атрибуты должны определять остальные атрибуты в каком-либо члене декомпозиции.

В нашем примере первая декомпозиция удовлетворяла этому требованию. Если декомпозиция содержит большее количество членов, то применяют специальный алгоритм проверки декомпозиции на соединение без потерь.

Алгоритм проверки декомпозиции на соединение без потерь.

Входные данные:

- схема R={A1, A2, …, An}

- множество функциональных зависимостей F

- декомпозиция ρ={R1,R2,…,Rk}

Выходные данные:

- логическое значение, утверждающее, обладает декомпозиция свойством объединения без потерь или нет.

Метод:

1. Создаем массив размером n*k

2. В массив построчно записываем все члены декомпозиции: для каждой декомпозиции в клетку заносим либо а_j, если A_j принадлежит Ri, в противном случае заносим b_ij.

3. Последовательно просматриваем все функциональные зависимости из F: X→Y ищем в массиве две строчки, у которых все атрибуты из X совпадают. Если они находятся, то приравниваем в них символы, соответствующие атрибутам Y. (Если атрибут помечен a_j, то и все остальные помечаем a_j, если же они равны b_ij, то делаем их одинаковыми, причем все равно какими, главное что они равны и обрабатываться будут одновременно) Если были просмотрены все функциональные зависимости без изменения массива, то цикл заканчивается

4. Если после выполнения цикла обнаруживается строка, имеющая все символы a, то выдаем истину.

Пример: пусть задана декомпозиция, исходные данные представим в таблице:

Берем функциональную зависимость имя → адрес.

Получаем строчку, состоящую только из символов а.

Пример: задано отношение R{A,B,C,D,E}

{A→C, B→C, C→D, DE→C, CE→A}

ρ={R1, R2, R3, R4, R5}

R1=AD, R2=AB, R3=BE, R4=CDE, R5=AE

Требуется выяснить, будет ли данная декомпозиция обладать свойством соединения без потерь.

A→C

B→C

C→D

DE→C

CE→A

Средняя строчка содержит все символы а, следовательно, декомпозиция обладает свойством соединения без потерь.

Декомпозиция, сохраняющая зависимости.

ρ={R1,R2,…,Rk}

Важным свойством декомпозиции ρ схемы R является сохранение зависимостей, то есть возможность вывода всех зависимостей F схемы R из проекций F⁺ на Ri.

Проекцией множеств функциональных зависимостей F на множество атрибутов Z называется множество функциональных зависимостей X→Y на F+, для которых справедливо, что объединение X и Y является подмножеством Z.

π_z(F)={X→Y|X→Y Є F⁺ X˄ XUY c Z}

Отметим, что в проекцию могут попасть зависимости, которые не принадлежат исходному множеству F, но встречаются в F+.

Декомпозиция ρ={R1,R2,…,Rk} сохраняет множество зависимостей F, если объединение всех зависимостей π_Ri(F) логически влечет все зависимости из F.

Пример: Пусть задано отношение R (город, улица, индекс) с зависимостями:

Город, улица → индекс

Индекс → город

Возьмем декомпозицию ρ={{улица, индекс}, {город, индекс}}. Эта декомпозиция обладает свойством соединения без потерь, так как пересечение {улица, индекс} и {город, индекс} => {улица, индекс}-{город, индекс}, следовательно, индекс → город

Однако проекция F на {улица, индекс} дает только тривиальные зависимости, а проекция F на {город, индекс}, помимо тривиальных, дает зависимость индекс → город. Исходную зависимость город, улица → индекс нельзя вывести из проекций. Таким образом, наша декомпозиция не сохраняет зависимости.

Следовательно, в базе данных может возникнуть противоречие. Работая с декомпозицией, мы можем заполнить базу данных следующим образом:

Если соединим эти таблицы, то получим следующую таблицу, которая нарушает функциональную зависимость город, улица → индекс. Таким образом, наша декомпозиция является декомпозицией без потерь, но не сохраняет зависимости.

Бывают другие ситуации, когда декомпозиция сохраняет зависимости, но не обладает свойством соединения без потерь.

Пример: R={A,B,C,D}

F={A→B, C→D}

ρ={AB, CD}

Необходимо проверить, сохраняет ли зависимости данная декомпозиция, а также, обладает ли данная декомпозиция свойством соединения без потерь.

{A,B}∩{С,D}→{A,B}\{C,D} – не соединяется без потерь

π_AB(F)U π_CD (F)={A→B}U{C→D}=F

Алгоритм проверки декомпозиции на сохранение зависимостей.

Есть очевидный способ проверки декомпозиции ρ на сохранение зависимостей F. Нужно вычислить замыкание F+, сделать проекции F+ на каждый член декомпозиции Ri и потом, объединив эти проекции, надо убедиться, что получилось то же самое множество F+.

Однако вычисление замыкания F+ очень громоздко, имеет экспоненциальную сложность, поэтому имеется алгоритм, не требующий вычисления замыкания и потому имеющий полиномиальную сложность.

Алгоритм:

Входные данные: схема R, F – множество функциональных зависимостей, декомпозиция ρ={R1,R2,…,Rk},

Результат: истина или ложь, в зависимости от того, сохраняет ли ρ зависимости или нет.

Метод: обозначим символов G объединение всех проекций функциональной зависимости F на члены ρ.

G=π_R1(F)U π_R(F)U…U π_Rk(F)

Для того, чтобы доказать, что декомпозиция ρ сохраняет зависимости, необходимо доказать, что G=F или равны их замыкания. Будем брать по очереди зависимости X→Y из F, и проверять, содержится ли Y в F+.

Но можно не строить множество G, а вычислить X+ относительно F и потом спроецировать на элементы декомпозиции. Таким образом, для каждой зависимости X→Y выполняется алгоритм:

Пусть X⁺_old и X⁺_new – переменные для хранения старого и нового значений замыкания.

X⁺_new:=X

Repeat

X⁺_old :=X⁺_new

For i:=1 to k do

X⁺_new:=X⁺ _newU((X⁺ _new ∩Ri)⁺ ∩Ri)

Until X⁺_old = X⁺_new

X⁺:=X⁺_new

То есть X⁺_new нужно пересечь с каждой проекцией, построить замыкание относительно F и опять отсечь то, что не входит в проекцию.

Если Y является подмножеством X⁺_new, X→Y принадлежит G⁺. Если все функциональные зависимости из F встречаются в F⁺, то выдаем истину, иначе – выдаем ложь.

Пример: пусть задана схема R={A, B, C, D} и F={A→B, B→C, C→D, D→A}. Возьмем декомпозицию ρ={AB, BC, CD}.

Требуется выяснить, сохраняет ли декомпозиция зависимости.

На первый взгляд кажется, что D→A теряется, но это не так. На самом деле мы проецируем F⁺, а не только F и таким образом, в проекции F на AB остается не только A→B, но и B→A. Также в проекции на BC остается B→C и C→B. Соответственно, в СD аналогично, а эти зависимости определяют D→A. Наши зависимости сохранились.

При помощи алгоритма:

То же самое должен показать рассмотренный выше алгоритм. Возьмем D→A, начнем вычислять {D}⁺ относительно G. Сначала X⁺_new={D}

Для проекции АВ ничего нового не получим, так как

{D}U(({D}∩ {AB})⁺∩{AB}={D}U{(0…)}

То же самое получится и для проекции ВС. Если же взять проекцию CD, то мы получим:

X⁺_new={D}U(({D}∩ {CD})⁺∩{CD})

={D}U(({D}⁺∩{CD}))={D}U({ABCD}∩CD)={CD}

На следующем витке цикла, взяв проекцию ВС и имея X⁺new=CD, получим X⁺new=BCD, на третьем витке цикла, взяв проекцию АВ, так как A принадлежит X⁺new, заключаем, что из G можно вывести D→A. Остальные члены F проверяются элементарно, следовательно, мы имеем декомпозицию, сохраняющую зависимости.