Лекции по теории проектирования баз данных (БД) — страница 3

атрибутов. Так в отношении: ГРАФИК[ПИЛОТ,РЕЙС,ДАТА,ВРЕМЯ] ПИЛОТ функционально зависит от {РЕЙС,ДАТА} F-зависимости принято обозначать {РЕЙС,ДАТА}-> ПИЛОТ и говорят, что РЕЙС и ДАТА функционально определяют ПИЛОТ. В терминах теории множеств и реляционной алгебры F-зависимость определяется так. Пусть R отношение и X, Y подмножества атрибутов в R. Отношение R удовлетворяет функциональной зависимости X -> Y, если pY(sX-x®) имеет не более чем

один кортеж для каждого Х - значения х. В F-зависимости X->Y подмножество X называется левой частью, а Y - правой частью. Лекция 2 Такая интерпретация функциональной зависимости является основой алгоритма SATISFIES, приводимого ниже. SATISFIES Вход: Отншение R и F-зависимость X->Y. Выход: истина, если R удовлетворяет X->Y, ложь - в противном случае. SATISFIES(R,X->Y)       Этот алгоритм проверяет, удовлетворяет ли отношение R F-зависимости X -> Y.

Пример. В результате выполнения алгоритма SATISFIES выясним удовлетворяет ли F-зависимость РЕЙС -> ВРЕМЯ_ВЫЛЕТА следующему отношению ГРАФИК ПИЛОТ РЕЙС ДАТА ВРЕМЯ_ВЫЛЕТА А... 83 9 авг 10:15 П... 83 11 авг 10:15 А... 116 10 авг 13:25 Р... 116 12 авг 13:25 П... 281 8 авг 5:50 С... 281 9 авг 5:50 П... 301 12 авг 18:35 С... 412 15 авг 13:25 Однако F-зависимость ВРЕМЯ_ВЫЛЕТА -> РЕЙС согласно этому алгоритму не выполняется для этого отношения ГРАФИК ПИЛОТ РЕЙС ДАТА ВРЕМЯ_ВЫЛЕТА П... 281 8 авг 5:50 С...

281 9 авг 5:50 А... 83 9 авг 10:15 П... 83 11 авг 10:15 А... 116 10 авг 13:25 Р... 116 12 авг 13:25 С... 412 15 авг 13:25 П... 301 12 авг 18:35 Рефлексивность: X -> X. Пополнение: X -> Y влечет за собой XZ -> y. Аддитивность: X -> Y и X -> Z влечет за собой X -> YZ. Проективность: 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} X -> Y F+ . Лекция 3 + не обязательно для установления F = X -> Y. Для этого достаточно воспользоваться алгоритмом MEMBER .