Добавил:
Upload Опубликованный материал нарушает ваши авторские права? Сообщите нам.
Вуз: Предмет: Файл:
BD_PM_Final.doc
Скачиваний:
1
Добавлен:
01.05.2025
Размер:
963 Кб
Скачать
☆

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

Проблема размеров множества ФЗ усугубляется тем, что некоторые ФЗ могут означать другие ФЗ. Т е возникает вопрос: а как построить замыкание? Задача построения замыкания представляется достаточно сложной и громоздкой поэтому существует правило вывода Армстронга, которое позволяет по крайней мере ограничить множество ФЗ. Аксиомы:

А,В,С,D

, тогда справедливы следующие правила:

рефлексивность. Если

дополнение. Если

транзитивность. Если и то

Для упрощения вычислений замыкания ФЗ используется и следующие правила.

Самоопределение

декомпозиция. Если и

объединение. Если и то

композиция. Если и то

правило Дарвена. Если и то

Вывод: 8 правил или аксиом Армстронга позволяют существенно упростить замыкание множества ФЗ.

Например: дано K(A,B,С,D,E,F).

S=

Где А – табельный номер,

B – номер отдела

С – руководитель

D – название проекта

Е – название отдела

F – время, уделенное на проект

Тогда очевидно, что приведение ФЗ отражают реальные ограничения данного отношения:

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

Действительно, воспользуемся правилами Армстронга тогда 1) – дано, тогда согласно декомпозиции 2) согласно дополнению 3) 4) – дано тогда из 3),4)следует 5) ,6)

59. Замыкания множества зависимостей. Примеры.

Проблема размеров множества ФЗ усугубляется тем, что некоторые ФЗ могут означать другие ФЗ. Т е возникает вопрос: а как построить замыкание? Задача построения замыкания представляется достаточно сложной и громоздкой поэтому существует правило вывода Армстронга, которое позволяет по крайней мере ограничить множество ФЗ. Аксиомы:

А,В,С,D

, тогда справедливы следующие правила:

рефлексивность. Если

дополнение. Если

транзитивность. Если и то

Для упрощения вычислений замыкания ФЗ используется и следующие правила.

Самоопределение

декомпозиция. Если и

объединение. Если и то

композиция. Если и то

правило Дарвена. Если и то

Вывод: 8 правил или аксиом Армстронга позволяют существенно упростить замыкание множества ФЗ.

Например: дано K(A,B,С,D,E,F).

S=

Где А – табельный номер,

B – номер отдела

С – руководитель

D – название проекта

Е – название отдела

F – время, уделенное на проект

Тогда очевидно, что приведение ФЗ отражают реальные ограничения данного отношения:

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

Действительно, воспользуемся правилами Армстронга тогда 1) – дано, тогда согласно декомпозиции 2) согласно дополнению 3) 4) – дано тогда из 3),4)следует 5) ,6)

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

Опр. Пусть дано ,

Тогда К – суперключ отношения R если содержит по крайней мере один потенциальный ключ этого отношения. Другими словами суперключом можно назвать такое подмножество атрибутов что : выполняется для любого атрибута отношения R. тогда предположим, что известны некоторые ФЗ образующие множество S и требуется найти потенциальный ключи этого отношения. По определению потенциальным ключом называется неприводимые суперключи, т е суперключ состоит из одного потенциального ключа, тогда путем выяснения является ли данное подмножество атрибутов суперключом можно в конечном итоге найти и потенциальный ключ.. действительно, существует алгоритм, который позволяет вычислить замыкание произвольного суперключа определенного на множестве ФЗ S. Алгоритм построения замыкания множества атрибутов основан на понятии суперключа, те пусть нам дано произвольное отношение R(A,B,С,D,E,F). В этом отношении есть некоторое множество значений S и есть некоторое начальное значение , которое назовем начальным значением суперключа. Тогда алгоритм вычисления замыкания на множестве ФЗ S выглядит следующим образом:

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

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

Если да , то новое значение итерационное замыкание = объединение зависимая часть данной ФЗ.

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

Пример. Пусть отношение R(A,B,С,D,E,F), и множество ФЗ S=

А в качестве начального значения суперключа =

Найти замыкание

Алгоритм:

предположим, что

выполним цикл 4 раза, проверив для каждой фз принадлежит ли детерминант . , поэтому

, ничего не делаем

, ,

,

внутренний цикл завершен, но после выхода из цикла поэтому снова проверяем 4 раза все фз.

,

, т к , то

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

легко проверить, что очередная проверка 4 Фз не изменяет значения . Поэтому на этом и завершаем алгоритм. Замыканием множества атрибутов будет подмножество

Вывод: из рассмотренного алгоритма можно сделать важное заключение о том , что для заданного множества ФЗ S можно указать будет ли произвольная зависимость следовать из S поскольку это возможно т и т т к правая часть этой зависимости является подмножеством замыкания . Т о найден относительно простой способ определения будет ли произвольная ФЗ принадлежать замыканию .

Соседние файлы в предмете [НЕСОРТИРОВАННОЕ]