Минимальное покрытие и функциональные зависимости

Учитывая следующие функциональные зависимости, как бы я вычислил минимальное покрытие:

A -> B, ABCD -> E, EF -> GH, ACDF -> EG

В лекциях он дает вывод для минимальной обложки, но я этого не понимаю.

Например, для избавления от ACDF → E:

A -> B => AACD -> BACD -> E => ACD -> E => ACDF -> E

И тогда они говорят, что мы не сохраняем ACDF → G

И тогда я понимаю, что ABCD → E выводится ACD → E, потому что A → B, но я не понять формальный процесс, как добраться до этого.

Итак, мой вопрос: может ли кто-нибудь объяснить, как создать минимальное покрытие для заданных функциональных зависимостей?

Ответ 1

Чтобы получить минимальное покрытие, вам нужно сделать два шага. Чтобы продемонстрировать, я сначала разделил зависимости на несколько (только один атрибут с правой стороны), чтобы сделать его более чистым:

A -> B
ABCD -> E
EF -> G
EF -> H
ACDF -> E
ACDF -> G

В этом порядке должны быть выполнены следующие шаги (# 1, а затем № 2), в противном случае вы можете получить неверный результат.

1) избавиться от избыточных атрибутов (уменьшить левые стороны):

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

Вы узнаете, что вы можете удалить B из зависимостей ABCD -> E, потому что ACD -> ABCD (используйте первый отклик) и от ABCD -> E. Вы можете использовать полный отпечаток. вы в настоящее время сокращаете, иногда это путает, но если вы подумаете об этом, станет ясно, что вы можете это сделать.

Аналогично, вы можете удалить F из ACDF -> E, потому что ACD -> ABCD -> ABCDE -> E (вы можете, очевидно, вывести одну букву из самой буквы). После этого шага вы получите:

A -> B
ACD -> E
EF -> G
EF -> H
ACD -> E
ACDF -> G

Эти правила по-прежнему представляют те же зависимости, что и оригинал. Обратите внимание, что теперь у нас есть повторяющееся правило ACD -> E. Если вы посмотрите на все это как на набор (в математическом смысле), то, конечно, вы не можете иметь один и тот же элемент дважды в одном наборе. На данный момент я просто оставляю это дважды здесь, потому что следующий шаг все равно избавится от него.

2) избавиться от избыточных зависимостей

Теперь для каждого правила попытайтесь удалить его и посмотрите, выведите то же правило, используя только другие. На этом этапе вы, конечно, не можете использовать dep. вы в настоящее время пытаетесь удалить (вы могли бы на предыдущем шаге).

Если вы берете левую часть первого правила A -> B, скройте его сейчас, вы увидите, что вы не можете вывести ничего из A в одиночку. Поэтому это правило не является избыточным. Сделайте то же самое для всех остальных. Вы узнаете, что вы можете (очевидно) удалить одно из повторяющихся правил ACD -> E, но, строго говоря, вы также можете использовать алгоритм. Скройте только одно из двух правил, затем возьмите левую сторону (ACD) и используйте другую, чтобы вывести правую сторону. Поэтому вы можете удалить ACD -> E (только один раз, конечно).

Вы также увидите, что вы можете удалить ACDF -> G, потому что ACDF -> ACDFE -> G. Теперь результат:

A -> B
EF -> G
EF -> H
ACD -> E

Какова минимальная обложка исходного набора.

Ответ 2

По моим словам, в приведенных выше функциональных минимальных зависимостях ACDF → G также следует включать, потому что когда вы закрываете каждую букву с левой стороны и их комбинацию, ни одна из них не производит G без включения F

Итак, это будет следующим образом:

(A → B, EF → G, EF → H, ACD → E, ACDF → G)