Ответ 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
Какова минимальная обложка исходного набора.