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

Question

У меня возникают проблемы с этим учебником вопрос

Рассмотрим множество функциональных зависимостей F = {A → B, B → C, CD → A, AC → D}

Compute минимальная крышка F.

Я пытаюсь выполнить простые шаги для этого. Сначала я вижу, что нет правого синглтона. Можно ли выделить CD и AC с левой стороны? Должен ли я?

Это моя попытка, не следуя шагам. Правильно ли это?

F = { A→ B, B→C, CD→A, AC → D} 
=> F = { A → C, CD → A, AC → D} 
=> F = { CD → C, AC → D} 
=> F = { D→ C, AC → D} 
=> F = {AC → C} 
=> F = {A->C} 

Answer 1

Если я правильно понимаю вашу запись, минимальная обложка содержит только A→C, но это, конечно, не покрытие исходного F, поскольку многие зависимости в F не могут быть получены из одной зависимости A→C. Например, как вы могли бы получить A→B от A→C? В минимальной оболочке вы «упрощаете» набор функциональных зависимостей без потери информации.

Итак, давайте начнем с самого начала и посмотрим, как нужно приступить к получению минимального покрытия.

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

Затем для каждой зависимости, которая содержит более одного атрибута слева, мы должны увидеть, могут ли некоторые из них быть устранены. Есть только два случая: CD→A и AC→D. Проверка выполняется таким образом. Атрибут можно устранить, если закрытие другого атрибута относительно F включает правую руку. Поэтому мы должны вычислить как C +, так и D + для первой зависимости, а A + и C + для второго.

C⁺ = {C} 
D⁺ = {D} 

Оба закрытия не содержат A, поэтому зависимость CD→A должна быть сохранена.

A⁺ = {A, B, C, D} 
C⁺ = {C} 

Поскольку закрытие атрибута A содержит D, C могут быть устранены с левой стороны, и новый набор зависимостей:

F' = {A→B, B→C, CD→A, A→D} 

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

A⁺ = AD 
B⁺ = B 
CD⁺ = CD 
A⁺ = ABC 

Ни в коем случае замыкание содержит правую руку, так что минимальная крышка F является F'.