Зависимости. Замыкание множества атрибутов. Покрытия и эквивалентность

Лекции №5-6 Пример: Пусть дано отношение , где – номер сотрудника, – номер отдела, – номер руководителя (начальника) данного сотрудника, – номер проекта, возглавляемого данным руководителем (уникальный для каждого отдельно – взятого руководителя), – название отдела, – доля времени, уделяемая данным руководителем заданному проекту и дано множество ФЗ Вопрос: Выполняется ли зависимость для ? Покажем, что зависимость выполняется для отношения и, таким образом, принадлежит замыканию данного множества ФЗ. 1. (дано) 2. (из 1 по правилу декомпозиции) 3. (из 2 по правилу пополнения) 4. (дано) 5. (из 3 и 4 по правилу транзитивности) 6. (из 5 по правилу декомпозиции) Пример 2: Пусть Представленная ниже последовательность последовательностью вывода для AB  GH 1. AB  E (дано) 2. AB  AB (Ф1: рефлексивность) 3. AB  B (Ф8: декомпозиция из 2) 4. AB  BE (Ф7: аддитивность из 1 и 3) 5 BE  I (дано) 6. AB  I (ФЗ транзитивность из 4 и 5) 7. E  G (дано) 8. AB  G (ФЗ транзитивность из 1 и 7) 9. AB  GI (Ф7 аддитивность из 6 и 8) 10. GI  H (дано) является 11. AB  H (ФЗ транзитивность из 9 и 10) 12. GI  GI (рефлексивность Ф1) 13. GI  I (Ф8 декомпозиция из 12) 14. AB  GH (Ф7 аддитивность из 8 и 11) Эта последовательность содержит ненужные (изменения): - Ф-зависимости, такие как 12 и 13 - и является также последовательностью вывода для других Ф-зависимостей, например AB  GI (3) B-аксиомы. RAP-последовательность вывода. Ранее было показано, что подмножество аксиом вывода F1, F2 и F6 является полным. Имеется также другое полное множество аксиом вывода, которые называются В–аксиомами. Для отношения r(R), подмножеств W, X, Y, Z схемы R и её атрибута C имеем: В1 (свойство рефлексивности): XX. B2 (свойство накопления): XYZ и Z W влечет XYZW. B3 (свойство проективности): XYZ влечет XY. Покажем, что аксиомы Армстронга выводятся из В–аксиом следствием этого является полнота системы В–аксиом. F1 (свойство рефлексивности): совпадает с В1. F2 (свойство пополнения): если XY, то в силу В1 имеем XZXZ, в силу В2 имеем XZXYZ, и, наконец, применение В3 дает XZYZ. F6 (свойство псевдотранзитивности): если XY и YZW, то в силу В1 имеем XZXZ. Последовательное применение B2 дает XZXYZ и XZWXYZ. Применяя В3 получаем XZW. Так как система В–аксиом полна, всегда можно найти последовательность вывода, использующую только В–аксиомы. Пример. Пусть F={ABE, AG I, BEI, EG, GI H}. Построим последовательность вывода из F для AB GH (пользуясь B-аксиомами). 1. EIEI (B1) 2. EG (дано) 3. EIEGI (В2 из 1 и 2) 4. EIGI (В3 из 3) 5. GIH (дано) 6. EIGHI (В2 из 4 и 5) 7. EIGH (В3 из 6) 8. ABAB (B1) 9. ABE (дано) 10. ABABE (В2 из 8 и 9) 11. BEI (дано) 12. ABABEI (В2 из 10 и 11) 13. ABABEGI (В2 из 4 и 12) 14. ABABEGHI (В2 из 7 и 13) 15. ABGH (В3 из 14) Рассмотрим такую последовательность вывода для XY из множества Ф-зависимостей F при помощи В–аксиом которые удовлетворяют следующим условиям: 1. первая Ф–зависимость – это XX. 2. последняя Ф–зависимость – это XY. 3. каждая Ф–зависимость, отличающаяся от первой или последней, либо принадлежит F, либо вид XZ и получена при помощи аксиомы В2. Такая последовательность вывода называется RAP– последовательностью вывода (по первым буквам названия В–аксиом: Reflexivity, Accumulation, Projectivity). Пример. Пусть F={ABE, AG I, BEI, EG, GI H}. Построим RAP–последовательность вывода из F для AB GH. 1. ABAB (B1) 2. ABE (дано) 3. ABABE (В2 из 1 и 2) 4. BEI (дано) 5. ABABEI (В2 из 3 и 4) 6. EG (дано) 7. ABABEGI (В2 из 5 и 6) 8. GIH (дано) 9. ABABEGHI (В2 из 8 и 7) 10. ABGH (В3 из 9) Таким образом, зависимость XY может быть выведена только при помощи аксиомы В2 (за исключением первой и последней зависимостей в Р). При этом, единственным результатом использования аксиомы В2 является возможность получить Ф–зависимость с большей правой частью, чем у первоначальной Ф–зависимости и подстановка Ф–зависимостей с большими правыми частями осуществляется по всей последовательности вывода. Замыкание множества атрибутов. Проверка принадлежности к F+. Постановка задачи. Предположим, что известны некоторые ФЗ, выполняющиеся для данного отношения, и требуется определить ключи этого отношения. Решение. 1. По определению потенциальными ключами называются неприведенные суперключи (т.е. суперключ содержит потенциальный ключ). 2. Таким образом, выясняя, является ли данное множество атрибутов К суперключом, можно в значительной степени продвинуться к выяснению вопроса, является ли К потенциальным ключом. 3. Для этого нужно определить, будет ли набор атрибутов отношения R множеством всех атрибутов, функционально зависящих от К. 4. Таким образом, для заданных множества зависимостей S, которые выполняются для отношения R, необходимо найти множество всех атрибутов отношения R, которые функционально зависимы от К, т.е. замыкание К+ множества К для S. Алгоритм вычисления этого замыкания: CLOSURE Алгоритм вычисления замыкания К+ множества К для S. (Алгоритм CLOSURE) Вход: множество атрибутов К и множество Ф– зависимостей S. Выход: К+ для S. FUNCTION CLOSURE PARAMETERS K,S Olddep=0 Newdep=K DO WHILE Newdep#older Olddep=Newdep FOR каждая Ф – зависимость X  Y в S IF X  newdep (если Х – является подмножеством Newdep) Newdep = Newdep  Y ENDIF ENDFOR ENDDO RENURN Newdep. Пример: Предположим, что дано отношение R с атрибутами A, B, C, D, E, F и следующими ФЗ: {A  BC, E  CF, B  E, CD  EF}. Вычислим замыкание {A,B}+ множества атрибутов {A, B} для данного множества ФЗ 1. olddep = newdep = {AB} 2 2.1. A  BC newdep = {ABC} 2.2. E  CF newdep = {ABC} 2.3. B  E newdep = {ABCE} 2.4. CD  EF newdep = {ABCE} 3. olddep = newdep = {ABCE} 4. Теперь выполним внутренний цикл четыре раза 4.1. AB  C newdep = {ABCE} 4.2. E  CF newdep = {ABCEF} 4.3. B  E newdep = {ABCEF} 4.4. CD  EF newdep = {ABCEF} Наконец, после ещё одного прохождения внутреннего цикла работа алгоритма завершается с получением результата {A, B}+ = {A, B, C, E, F }, что равносильно АВABCEF. {A, B} – не является суперключом и, следовательно потенциальным ключом, т.к. атрибут D функционально не зависит от AB. Какое множество атрибутов может являться суперключом: ABD , AD, ACD Из сказанного выше можно сделать очень важное заключение: для заданного множества функциональных зависимостей F, можно легко указать, будет ли заданная Ф – зависимой XY следовать из S, поскольку это возможно тогда и только тогда, когда Y является подмножеством замыкания X+ множества для заданного множества F. Иначе говоря, таким образом представлен простой способ определения, будет ли данная функциональная зависимость X  Y включена в замыкание F+ множества F. Алгоритм проверки выводимости функциональной зависимости X  Y из множества F: MEMBER Алгоритм MEMBER Вход: множество Ф – зависимостей F и ФЗ X  Y Выход: истина, если из F следует X  Y, лож в противном случае. FUNCTION MEMBER PARAMETERS F, X  Y IF Y  CLOSURE (X, F) RETURN T ELSE RETURN F ENDIF Задание: 1) Дано отношение R=(A, B, C, D, E, F, G) и задана ФЗ над этим отношением S={A  B, BC  DE, AEF  G }. Вычислить замыкание {A, C}+ для данного множества. Подразумевается ли зависимость ACF  DG этим множеством S 2) R = (A, B, C, D, E, F, G, H, I) S = {A  D, AB  E, BI  E, CD  I, E  C} Вычислить замыкание {AE}+ для множества. Вычислить замыкание: {BEI}+ Покрытия функциональных зависимостей Рассмотрим методы наиболее короткого представления Ф– зависимостей. Например, любая зависимость, выводимая из множества F={AB, BC, AC, ABC, ABC}, также выводима из множества G={AB, BC}, поскольку все Ф–зависимости из F могут быть выведены из Ф–зависимостей, принадлежащих G. Пример: R = (A, B, C, D, E, T), где A – читаемый курс, B – преподаватель, C – час начала занятий, D – аудитория, E – студент, T – оценка по курсу. F = {CD → B, CD → A, AC → D, CE → A, A → B, CB → D, AE → T, CE → D} A→B – каждый курс ведет один преподаватель; CD→A – в аудитории в один и тот же момент времени может читаться только один курс; CE→A – каждый студент в один и тот же момент времени может слушать только один курс; CB→D – преподаватель в один и тот же момент времени может находиться только в одной аудитории; AC→D – каждый курс в один и тот же момент времени может читаться только в одной аудитории; CE→D – студент в один и тот же момент времени может находиться только в одной аудитории AE→T – по каждому курсу каждый студент имеет только одну оценку; CD→B – в аудитории в один и тот же момент времени может быть один преподаватель; Покрытие множества функциональных зависимостей F S = {A→B, CD→A, CB→D, AE→T, CE→D} Цели минимизации количества Ф–зависимостей: 1. Меньшее множество F–зависимостей гарантирует более быстрое исполнение алгоритмов, число шагов которых зависит от размера входного множества Ф–зависимостей, таких, например, как алгоритм MEMBER. 2. При эксплуатации баз данных меньшее число Ф– зависимостей означает меньший объем используемой памяти и меньшее число проверок при модификации базы данных. Покрытия и эквивалентность Два множества Ф–зависимостей F и G над схемой R эквивалентны (FG), если F+=G+. Если FG и |F|<|G|, то F есть покрытие для G. Если FG, то поскольку F+=G+, для каждой зависимости XY из G+ следует, что и F влечет XY. В частности, F влечет XY также для каждой Ф–зависимости XY из G. Обобщая понятие выводимости на множество Ф–зависимостей, можно сказать, что множество F влечет множество G. Поскольку определение эквивалентности симметрично относительно F и G, из FG следует также, что G влечет F. Так как F+ включает все до одной Ф-зависимости, которые вообще могут быть получены из F, то из того, что F влечет G, следует GF+. Применяя операцию замыкания к обеим частям неравенства, получаем G+(F+)+=F+. Аналогично из того, что G влечет F, следует G+F+. Таким образом, доказано, что для заданных множеств F–зависимостей F и G над схемой R тождество FG имеет место тогда и только тогда, когда и F влечет G, и G влечет F. Это дает возможность простой проверки эквивалентности любых двух множеств Ф–зависимостей с помощью следующих двух алгоритмов: DERIVES и EQUIV Алгоритм DERIVES. Вход: два множества F–зависимостей F и G. Выход: истина, если F влечет G, ложь в противном случае. FUNCTION DERIVES PARAMETERS F,G FOR каждая Ф–зависимость XY из G IF NOT MEMBER(F, XY) EXIT ENDIF ENDFOR RETURN MEMBER(F, XY) Алгоритм EQUIV. Вход: два множества Ф–зависимостей F и G. Выход: истина, если FG, ложь в противном случае. FUNCTION EQUIV PARAMETERS F,G RETURN DERIVES(F,G) AND DERIVES(G,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. По другому определению неизбыточности множество F неизбытно, если в нем не существует такой F–зависимости XY, что F-{XY} влечет XY. Если же такая F–зависимость существует, она называется избыточной в F. Такое определение позволяет построить алгоритм проверки избыточности F. Алгоритм REDUNDANT. Вход: множество F–зависимостей F. Выход: истина, если F избыточно, ложь в противном случае. FUNCTION REDUNDANT PARAMETERS F FOR каждая F–зависимость XY из F IF MEMBER(F-{XY }, XY) EXIT ENDIF ENDFOR RETURN MEMBER(F-{XY }, XY) Для любого множества Ф–зависимостей G существует некоторое подмножество F, такое, что F является неизбыточным покрытием G. Если G неизбыточно, то F=G. Если G избыточно, то в G существует F–зависимость XY, которая является избыточной в G. Обозначим G’=G-{XY}. Если G’ избыточно, то в G’ существует Ф–зависимость WZ, которая является избыточной в G’. Обозначим G’’= G’-{WZ}. При этом (G’’)+=(G’)+=G+. На каком-то шаге процесс удаления избыточных зависимостей должен, безусловно, закончиться. В результате для G образуется неизбыточное покрытие F. Этот процесс является основой алгоритма NONREDUN, который вычисляет неизбыточное покрытие G. Алгоритм NONREDUN. Вход: множество F–зависимостей G. Выход: неизбыточное покрытие G. FUNCTION NONREDUN PARAMETERS G F=G FOR каждая F–зависимость XY из G IF MEMBER(F-{XY}, XY) F=F-{XY} ENDIF ENDFOR RETURN F Пример: Пусть G={AB, BA, BC, AC}. Результатом работы NONREDUN(G) является множество {AB, BA, AC}. Если G представить в другом порядке: G={AB, AC, BA, BC}, то результатом работы NONREDUN(G) является множество {AB, BA, BC}. Из примера видно, что множество F–зависимостей G может иметь более одного неизбыточного покрытия. Могут также существовать неизбыточные покрытия G, не содержащиеся в G. Для примера таким покрытием может служить множество F={AB, BA, ABC}. РАСПИСАНИЕ ЭКЗАМЕНОВ - Код дисциплины, - Название дисциплины, -Табельный номер преподавателя – экзаменатора, -Ф.И.О. реподавателя, - Дата экзамена, - Время экзамена, - Место проведения экзамена, - Номер группы Функциональные зависимости: 1) - Код дисциплины однозначно определяет ее название. 2) - Табельный номер однозначно идентифицирует преподавателя 3) - В указанный день и время в аудитории проводится только по одной дисциплине, одним преподавателем и в одной студенческой группе. 4) - В каждой студенческой группе по каждой отдельной дисциплине принимает экзамен только один преподаватель. 5) - Преподаватель одновременно может принимать экзамен только в одной аудитории. 6) - Для каждой группы по одной дисциплине и соответствующего преподавателя однозначно определяются дата, время и место экзамена. 7) - Преподаватель одновременно может принимать экзамен только по одной дисциплине.