12

Найдите каноническое покрытие для множества функциональных зависимостей S={A->B, ABCD->E, EF->GH, ACDF->EG}, заданных для переменной-отношения R(A, B, C, D, E, F, G, H).

Похожая задача

(min покрытие == ФЗ (функциональные зависимости) явл. неприводимым)

Множество ФЗ явл. неприводимым (min покрытие) тогда и только тогда, когда обладает след. свойствами:

Детерминант - левая часть. Зависимая часть - правая.

• Для любой ФЗ X->Y, Y - один элемент.
• Ни одну ФЗ нельзя удалить без изменения замыкания. (Пробуем удалить и смотрим на замыкание, поменялось?)
• Ни один атрибут не может быть удален из детирменанта без изменения замыкания

Каноническое покрытие = min покрытие + используем правило объединения, чтобы получить покрытие, которое содержит наименьшее количество ФЗ.

S={A->B, ABCD->E, EF->GH, ACDF->EG}

Этап 1:
S={A->B, ABCD->E, EF->G, EF->H, ACDF->E, ACDF->G}

Этап 2:
* Удаляем A->B
{A}+={A} - Не содержит B, значит нельзя удалить без изменения замыкания.

* Удаляем ABCD->E
{ABCD}+={ABCD} - Не содержит E, значит нельзя удалить без изменения замыкания.

* Удаляем EF->G
{EF}+={EFH} - Не содержит G, значит нельзя удалить без изменения замыкания.

* Удаляем ACDF->E
{ACDF}+={ACDFBEHG} - Содержит E, значит можем удалить без изменения замыкания.

S={A->B, ABCD->E, EF->G, EF->H, ACDF->G}

* Удаляем ACDF->G
{ACDF}+{ACDFEGB} - Содержит G, значит можем удалить без изменения замыкания. 

S={A->B, ABCD->E, EF->G, EF->H}

Этап 3.
Для ABCD->E:
* Заменяем ABCD->E на ABC->E 
{ABC}+={ABCE} - не содержит D => не можем удалить. 
* Заменяем ABCD->E на ACD->E
{ACD}+={ACDBE} - Содержит E, значит можем заменить.

S={A->B, ACD->E, EF->G, EF->H}

Для EF->G:
* Заменяем EF->G на F->G
{F}+={FG} - не содержит E => не можем удалить. 

* Заменяем EF->G на E->G
{E}+={EG} - не содержит F => не можем удалить. 

Для EF->H:
* Заменяем EF->H на E->H
{E}+= {EH} - не содержит F => не можем удалить.

* Заменяем EF->H на F->H
{F}+{FH} - не содержит E => не можем удалить.

Этап 4 (используем правило объединения)
S={A->B(0), ACD->E(1), EF->G(2), EF->H(3)}

Объединяем (2) и (3).

S={A->B, ACD->E, EF->GH}

Ответ: S={A->B, ACD->E, EF->GH}.

<- or ->