Неприводимое множество зависимостей.

Название лекции: Замыкание множества атрибутов.

Лекция №12

План:

1. Определение суперключа.

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

_3. Приложение (следствие) алгоритма построения замыкания K_i⁺ для множества атрибутов K_i.

4. Алгоритм проверки, следует ли Ф.З. X ® Y из множества S, т.о. проверки принадлежности X ® Y множеству S⁺.

5. Неприводимое множество зависимостей.

6. Потенциальные ключи и функциональные зависимости.

1. Определение суперключа.

Суперключом отношения R называется множество атрибутов отношения R, которое содержит как подмножество хотя бы один потенциальный ключ (т.е. ключ, который обладает свойствами: 1 – уникальности, 2 – не избыточности). Суперключ обладает свойством уникальности, но является избыточным.

Пусть дано переменная отношения R с множеством атрибутов A. Допустим, что для некоторого подмножества K множества атрибутов A (KÌA), выполняется ФЗ K→A. По определения ФЗ это означает, что если два кортежа отношения R совпадают по значениям атрибутов из множества K, то эти два кортежа будут совпадать и по значениям атрибутов A, т.е. по множеству всех атрибутов. Но в этом случае (два кортежа совпадают по K) эти два кортежа просто совпадают, что не возможно, т.к. в отношении никакие два кортежа не могут совпадать. Следовательно, никакие два кортежа не могут совпадать по значению атрибутов из множества K. При условии, что K→A в этом случае K обладает свойством уникальности и значит, что K– это ключ.

Суперключи – это такие подмножества К_i (K_iÌA) множества атрибутов отношения R, обладающее свойством уникальности и избыточности. Это значит, что у К_i есть непустое подмножество, не совпадающее с К_i (например, KÌК_i), обладающее свойством уникальности, т.е. K→A.

Пусть известно некоторое множество S функциональных зависимостей отношения R. Требуется найти потенциальные ключи этого отношения. Если построить множество всех ключей (каждый из элементов этого множества содержит потенциальный ключ) и исключить из этого множества суперключи (т.е.ключи, обладающие свойством избыточности), то мы получим множество потенциальных ключей. Чтобы установить является ли множество атрибутов К_i ключом необходимо выяснить являются ли функционально зависимыми все атрибуты отношения R от K_i, т.е. если для отношения R, с множеством атрибутов А, множеством ФЗ S и множеством K_i Ì A удается найти множество К_i⁺ Í А такое, что все элементы К_i⁺ функционально зависят от К_i и при этом К_i⁺ = А, то К_i является ключом. Если при этом ключ не обладает избыточностью, то это потенциальный ключ.

Множество всех элементов из A, функционально зависимых от K_i Ì A, называется замыканием множества K_i для отношения R и множества функциональных зависимостей S и обозначается K_i⁺ Ì A. Если для K_i построили K_i⁺, то выполняется ФЗ K_i→K_i⁺.

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

Дано: отношение R с множеством атрибутов A и множеством ФЗ S={X₁→Y₁,X₂→Y₂,...,X_m→Y_m}. Кроме того, пусть дано подмножество атрибутов K_i Ì A. Построим K_i⁺, замыкание множества ФЗ K_i. Т.е. требуется построить множество всех атрибутов из A, которые функционально зависят от K_i (т.е. K_i→K_i⁺). Алгоритм построения такого множества является рекуррентным. В качестве начального приближения K_i⁺ выберем само множество K_i. Это возможно, т.к. имеет место ФЗ К_i → К_i и, следовательно, K_i Ì K_i⁺. Итак:

K_i⁺ = K_i

Цикл_пока истина

j = 0, f = ложь

Цикл_пока j < m

j + +

Если (X_j Ì K_i⁺ ) Ù ($ y½y Î Y_j Ù y Ï K_i⁺)

K_i⁺ = K_i⁺ È Y_j

f = истинна

Всё_если

Всё_цикл

Если не (f) то

Выход из цикла

Всё_если

Всё_цикл

Пример: Дано: отношение R, А – множество атрибутов, А = {a, b, c, d, e, f},

S = {{a} ® {b, c}, {e} ® {c, f}, {b} ® {e}, {c, d} ® {e, f}}

Найти: {a, b}⁺ для {a, b}

1) {a, b}⁺ = {a, b}

2) Бесконечный цикл

3) Цикл по элементам множества S

а) {a} ® {b, c} {a} Ì {a,b}⁺ => {a, b}⁺ = {a, b} È {b, c} = {a, b, c}

б) {e} ® {c, f} {e} Ë {a, b}⁺ => {a, b}⁺ = {a, b, c}

в) {b} ® {e} {b} Ì {a,b}⁺ {a, b}⁺ = {a, b, c} È {e} = {a, b, c, e}

г) {c, d} ® {e, f} {c, d} Ë {a, b}⁺ => {a, b}⁺ = {a, b, c, e}

4)

а) {a, b}⁺ = {a, b, c, e}

б) {e} ® {c, f} {e} Ì {a, b}⁺ => {a, b}⁺ ={a, b, c, e} È {c, f}={a, b, c, e, f}

Далее {a, b}⁺ не изменится и т. о. {a, b}⁺ = {a, b, c, e, f}. Мы построили такое множество {a, b}⁺, которое зависит от {a, b}, т.е. {a, b} ® {a, b, c, e, f}.

Множество {a, b}⁺ ¹ A и {a, b} не является ключом и, т.о. не является ни потенциальным ключом, ни суперключом.

_3. Приложение (следствие из) алгоритма построения замыкания K_i⁺ для множества атрибутов K_i.

Пусть дано:

1) Отношение R с множеством атрибутов A

2) Множество ФЗ S для R и S={X₁→Y₁,X₂→Y₂,...,X_m→Y_m}.

3) Некоторая ФЗ X ® Y такая, что X ® Y Ï S.

Проверить: {X ® Y} Ì S⁺. Т.е. необходимо проверить: следует ли X ® Y из S или нет.

Решение:

1) Построим для {R, S, X} замыкание X⁺ для множества атрибутов X.

2) Каждый элемент (атрибут) множества X⁺ функционально зависим от X, т.е. X®X⁺. Следовательно, любое подмножество X⁺ функционально зависимо от X. И, если Y Ì X⁺, то X ® Y следует из S и, тогда, {X ® Y} Ì S⁺ º истина.

Если Y Ë X⁺, то функциональная зависимость X ® Y не следует из S и {X ® Y} Ë S⁺.

4. Алгоритм проверки, следует ли Ф.З. X®Y из множества S, т.е. проверки принадлежности X ® Y множеству S⁺.

¹⁾ Для R, S построить X⁺

2) Если Y Ì X⁺ то

{X ® Y} Ì S⁺

иначе

{X ® Y} Ë S⁺

все - если.

Пример: Дано: A = { a, b, c, d, e, f }

S = {{ a } ® { b, c }, { b } ® { e }, { c, d } ® { e, f }

Найти: истинность высказывания ({ a, d } ® { f } Î S⁺ )

Решение: обозначим x = { a, d } и найдем X⁺

0) X⁺ = { a, d }

1) X⁺ = { a, b, c, d }

2) X⁺ = { a, b, c, d, e }

3) X⁺ = { a, b, c, d, e, f }

Следовательно, в ФЗ {a,d}®{f} зависима часть {f}Ì{a, d}⁺, т.о. {{a, d}®{f}}ÌS⁺

5. Неприводимое множество зависимостей.

Пусть S₁ и S₂ два множества зависимостей отношения R. Если S₁⁺ Ì S₂⁺, то говорят, что S₂ является покрытием S₁. Это означает, что, если выполняются накладываемые на отношение ограничения S₂, то будут выполняться и ограничения S₁.

Если S₁ покрытие S₂, а S₂ является покрытием S₁, т.е. S₁⁺ = S₂⁺, то S₁ и S₂ называют эквивалентными множествами ФЗ.

Это означает, что, если выполняются ограничения S₁, то выполняются ограничения S₂, и наоборот.

Пусть дано отношение R с множеством ФЗ S. Практически важной является задача построения множества ФЗ S₁, эквивалентного S и при этом имеющего принципиально более простую структуру. Для эквивалентных множеств ФЗ S и S₁ отношения R будем говорить, что S₁ проще, чем S, если при модификации R СУБД может проверить ФЗ S₁ быстрее, чем проверить S. В теории реляционных баз данных принято выбирать так называемые неприводимые множества ФЗ.

Множество ФЗ называется неприводимым тогда и только тогда, когда:

1) Правая (зависимая) часть каждой ФЗ множества S содержит только один атрибут.

2) В левой части каждой ФЗ множества S не может быть опущен ни один атрибут без изменения замыкания S⁺.

3) Ни одна ФЗ в S не может быть опущена из S без изменения S⁺.

Пояснение:

по п.2, т.е. нельзя преобразовать (конвертировать) S путем удаления некоторых атрибутов из детерминантов S во множество, эквивалентное S.

по п.2, говорят, что множество S в этом случае неприводимое слева.

по п.3, нельзя конвертировать S путем удаления каких-либо Ф.З. из S во множество эквивалентное S.

Пример: Дано: отношение R с атрибутами A={a, b, c, d}; множество ФЗ: S={ { a } ® { b, c }; { b } ® { c }; { a } ® { b }; { a, b } ® { c }; { a, c } ® { d }}

Найти неприводимое множество, эквивалентное S.

1) Определим во всех ФЗ справа только одноэлементное множество атрибутов

S₁={{ a } ® { b }, { a } ® { c }, { b } ® { c }, { a,b } ® { c }, { a,c } ® { d }}.

Напомним, что любое множество содержит только различимые объекты. Множество ФЗ должно содержать только различные функциональные зависимости. Следовательно { a } ® { b } должна встретится только один раз. Мы преобразовали S в S₁ , используя правила Амстронга. Следовательно, S и S₁ эквивалентные множества (S⁺=S₁⁺ и замыкание S не изменилось от преобразования его в S₁).

2) Ни один атрибут слева не может быть опущен без изменения замыкания множества зависимостей.

Рассмотрим последние две зависимости:

· в { a,c } ® { d } – в детерминанте атрибут с можно опустить, т.к.

(a®c) Ù(ac→d)~(a→ac) Ù(ac→d)~(a→ac) Ù(a→d)~(a→c) Ù(a→d).

S₁ преобразовали с помощью правил Амстронга в

S₂={{ a } ® { b }, { a } ® { c }, { b } ® { c }, { a,b } ® { c }, { a } ® { d }}.

При этом S₁⁺=S₂⁺.

· Зависимость { a,b } ® { c } из S₂ может быть исключена, т.к.

(a®b)Ù(a→c)~(a→b) Ù(ab→bc)~(ab→b)Ù(ab→c)~ (a→b)Ù(ab→c), следовательно

(a→b)Ù(a→c)~(a→b)Ù(ab→c), но ФЗ (a→b) и (a→c) уже входят в S₂ и Зависимость {a,b} ® { c } из S₂ может быть исключена. Получим

S₃={{ a } ® { b }, { a } ® { c }, { b } ® { c }, { a } ® { d }}.

3) Ни одна ФЗ не может быть опущена без изменения S⁺. По третьему правилу Амстронга (транзитивность) ({a} ® {b} Ù {b} ® {c})=>{a} ® {c}, следовательно, из S₃ можно опустить {a} ® {c} без изменения замыкания. Окончательно получаем S₄={ a→b, b→c, a→d} – неприводимое множество ФЗ для S.

Пример: Дано отношение – расписание занятий с атрибутами:

D – день недели (1…5), P – номер урока (1…8), C – номер класса, T – имя учителя, L – название урока.

Кортеж (d,p,c,t,l) является элементом этого отношения тогда и только тогда, когда урок l проводится учителем t в классе с в момент времени d,p. Предположим, что каждый урок имеет название, уникальное по отношению ко всем урокам этой недели.

Ответить на вопросы:

Какие ФЗ выполняются для этого отношения? Какие потенциальные ключи отношения?

Решение: L→D,P,C,T

D,P,C→T

D,P,T→C

D,P,C→L

6 Потенциальные ключи и функциональные зависимости.

Если Х является потенциальным ключом отношения R (например, первичным ключом), то все атрибуты этого отношения функционально зависят от Х.

Если отношение R удовлетворяет функциональной зависимости А®B и А не является потенциальным ключом, то R обладает некоторой избыточностью.

Пример: A={<Поставщик>,<Город>,<Товар>,<Количество>} множество атрибутов с потенциальным ключом ={<Поставщик>,<Товар>}

Есть ФЗ <Поставщик>®<Город>, то отношение обладает избыточностью, т.к. факт: поставщик из данного города повторяется в нескольких кортежах.

Дата добавления: 2014-01-05