Неизбыточное покрытие

Эквивалентные множества функциональных зависимостей (покрытия)

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

Определение 21

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

Определение 22

Два множества ФЗ эквивалентны, если их замыкания равны.

Множество, эквивалентное исходному множеству, также называют его покрытием.

На практике получение замыканий функциональных зависимостей для доказательства эквивалентности покрытий применяется достаточно редко из-за проблем временного характера. Для примера построим замыкание для множества функциональных зависимостей F={X®Y, X®Z}. F⁺={X®Y, X®Z X®X, Y®Y, Z®Z, XY®X, XZ®X, ZX®Z, ZY®Z, YX®Y, YZ®Y, X®ZY, XY®XY, XZ®XZ, YZ®YZ, XYZ®XYZ, XYZ®YZ,… }.

Ниже приведено еще одно определение эквивалентности (см. Определение 23), которое имеет большую практическую значимость, поскольку позволяет значительно упростить процесс доказательства эквивалентности множеств функциональных зависимостей.

Определение 23

Множество функциональных зависимостей F’=F-(X®Y) на схеме R эквивалентно множеству F на этой же схеме, если оно получено из F путем применения аксиом вывода и каждая функциональная зависимость F может быть восстановлена из вновь полученного множества F’ путем последовательного применения аксиом вывода.

То есть для того, чтобы доказать, что два множества эквиваленты, следует просто доказать, что они взаимообратимы. Например, два множества F₁={X®Y, X®Z} и F₂ = {X®YZ} эквиваленты, поскольку, как уже было рассмотрено выше, второе множество можно получить из первого на основании аксиомы аддитивности, а первое из второго по аксиоме проективности. Однако этого нельзя сказать о множествах F₁={X®Y, Y®Z} и F₂ = {X®Z}. Действительно второе множество (F₂) следует из первого (F₁) на основании аксиомы транзитивности, однако из второго нельзя получить первое.

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

· неизбыточное покрытие;

· минимальное покрытие;

· редуцированное покрытие (редуцированное, редуцированное слева, справа);

· каноническое покрытие;

· оптимальное покрытие;

· кольцевое покрытие[4].

Определение 24

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

У каждого множества функциональных зависимостей может быть несколько неизбыточных покрытий. Например, у исходного множества функциональных зависимостей F={A®B, A®C, A®BC} два неизбыточных покрытия F₁={A®B, A®C} и F₂={A®BC}. Как уже отмечалось выше, вид неизбыточного покрытия во многом определяется порядком, в котором функциональные зависимости проверяются на избыточность.

Порядок получения неизбыточного покрытия:

· Выбирается произвольная функциональная зависимость X®Y из множества функциональных зависимостей F на схеме R отношения r и проверяется возможность ее получения из оставшегося функциональных зависимостей F-{X®Y} с помощью аксиом вывода.

· Если данная функциональная зависимость не может быть выведена с помощью аксиом вывода из множества F-{X®Y}, то она остается в исходном множестве и рассматривается следующая функциональная зависимость этого множества.

· Если ее вывод возможен, то рассматриваемая функциональная зависимость X®Y удаляется из исходного множества F и рассматривается следующая функциональная зависимость этого множества.

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

Дата добавления: 2014-12-17