Построение минимального покрытия

Для построения минимального покрытия необходимо применить алгоритм его построения.

Первым шагом является преобразование множества зависимостей ко множеству зависимостей с определяемой частью из одного атрибута. На основании правила декомпозиции, зависимость вида X → A₁A₂…A_k разбивается на множество зависимостей X → A₁, X → A_s, … X → A_k. В нашем случае подлежащей такому преобразованию является зависимость

«Идентификатор выдачи» → «ФИО Клиента», «Адрес электронной почты клиента», «Контактный телефон клиента».

По правилу декомпозиции получаем:

«Идентификатор выдачи» → «ФИО Клиента»;

«Идентификатор выдачи» → «Адрес электронной почты клиента»;

«Идентификатор выдачи» → «Контактный телефон клиента».

Второй шаг алгоритма заключается в удалении избыточных зависимостей. Зависимость X→Y удаляется из множества зависимостей F, если множество F \ {X→Y} эквивалентно исходному множеству F.

Для проверки эквивалентности множеств функциональных зависимостей используется понятие замыкания множества атрибутов. Замыканием X⁺ множества атрибутов X зовется множество атрибутов {A_i} таких, что X→A_i Î F⁺, где F⁺ – замыкание множества функциональных зависимостей.

Существует алгоритм проверки эквивалентности двух множеств функциональных зависимостей F и G. Если для каждой зависимости X→Y Î F выполнено Y Í X⁺_G (X⁺_G – замыкание X, построенное для множества зависимостей G), то имеет место F Í G. Для проверки G Í F используется симметричное утверждение. Если одновременно выполнены F Í G и G Í F, то множества эквивалентны.

Возвращаясь ко второму шагу алгоритма, существует утверждение, что для проверки эквивалентности указанных множеств (F \ {X→Y} и F) достаточно построить X⁺_G, где G = F \ {X→Y}, и проверить выполнение Y Î X⁺_G. Если утверждение истинно, то множества F и G эквивалентны, и зависимость может быть удалена.

Второй шаг алгоритма заключается в описанной проверке всех имеющихся зависимостей на избыточность. Здесь же в качестве иллюстрации будут рассмотрены только две зависимости.

Рассмотрим зависимость: «Идентификатор выдачи» → «Идентификатор клиента».

Для построения замыкания X⁺ множества атрибутов X применяется свой алгоритм (X⁽ⁱ⁾ – замыкание, построенное на очередном шаге):

Шаг 0. X⁽⁰⁾:= X;

Шаг i. Пусть в результате последовательного просмотра множества функциональных зависимостей для зависимости Y→Z выполнено Y Í X^(i-1). Тогда X⁽ⁱ⁾:= X^(i-1) È {Z}.

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

Построим замыкание атрибута «Идентификатор выдачи» для множества зависимостей G:

«Идентификатор выдачи»⁺ = {

1. «Идентификатор выдачи»,

2. «Идентификатор носителя», «Дата выдачи носителя клиенту», «Дата возврата носителя», «ФИО клиента», «Адрес электронной почты клиента», «Контактный телефон клиента»,

3. «Метка носителя», «Время добавления информации о носителе», «Идентификатор типа носителя», «Дата порчи-потери носителя», «Рента за сутки»,

4. «Тип носителя» }

Атрибуты в замыкании разбиты на группы согласно причине их добавления. Первая группа появляется в силу шага 0 алгоритма построения замыкания. Каждая следующая группа содержит определяемые части функциональных зависимостей, имеющих определяющие, состоящие из атрибутов предыдущих частей. Атрибуты второй группы функционально зависят от «Идентификатора выдачи». Атрибуты третьей части зависят от «Идентификатора носителя», четвертой — от «Идентификатора типа носителя».

Как можно заметить, атрибут «Идентификатор клиента» в построенное замыкание не входит. Зависимость остается.

Рассмотрим зависимость

«Идентификатор выдачи» → «ФИО Клиента»

Построим замыкание атрибута «Идентификатор выдачи» для множества зависимостей без данной:

«Идентификатор выдачи»⁺ = {

1. «Идентификатор выдачи»,

2. «Идентификатор носителя», «Идентификатор клиента», «Дата выдачи носителя клиенту», «Дата возврата носителя»,

3. «Метка носителя», «Время добавления информации о носителе», «Идентификатор типа носителя», «Дата порчи-потери носителя», «ФИО клиента», «Адрес электронной почты клиента», «Рента за сутки», «Контактный телефон клиента»,

4. «Тип носителя» }

Здесь, несмотря на отсутствие в G зависимости «Идентификатор выдачи» → «ФИО Клиента», атрибут «ФИО Клиента» появляется в построенном замыкании. Данная зависимость избыточная и должна быть удалена.

Аналогичная проверка приводит к удалению следующих зависимостей:

«Идентификатор выдачи» → «Адрес электронной почты клиента»;

«Идентификатор выдачи» → «Контактный телефон клиента».

На третьем шаге алгоритма происходит удаление избыточных атрибутов из определяющих частей. На этом шаге выполняется последовательный просмотр множества зависимостей. Для каждой зависимости X→Y, где X = X₁X₂…X_k, выполняется следующая проверка. Из X удаляется очередной атрибут X_i, после чего проверяется эквивалентность F \ {X→Y} È {X₁X₂…X_i-1X_i+1…X_n→Y} и F. Если эквивалентность имеется, то атрибут не возвращается.

Как и на втором шаге, проверка эквивалентности сводится к построению одного замыкания: (X₁X₂…X_i-1X_i+1…X_n)⁺_F — и проверки Y на принадлежность ему (в силу первого шага это один атрибут). Принадлежность означает эквивалентность множеств, и в этом случае атрибут не возвращается.

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