Количество различных минимальных покрытий возможно? - PullRequest
Новая
       74

Количество различных минимальных покрытий возможно?

0 голосов
/ 06 января 2020

Рассмотрим R (A, B, C, D, E, F, G) как реляционную схему со следующими функциональными зависимостями: A C -> G, D-> EG, B C -> D, CG-> BD, ACD-> B, CE-> AG. Количество возможных минимальных покрытий: ___________?

На самом деле в этом вопросе мы должны были найти все возможные минимальные покрытия. Я использовал это видео. Таким образом, используя эту теорию, я попытался ответить на этот вопрос, но в итоге получил только 2 минимальных обложки, а затем в моем учебнике был дан ответ 4. Минимальные обложки, которые я получил:

1) D-> E, D-> G, B C -> D, CG-> D, A C -> B (# ), CE-> A

2) A C -> G, D-> E, D-> G, B C -> D, CG-> D, CD-> B ( #), CE-> A

На самом деле видео дает только стандартную процедуру, чтобы НАЙТИ минимальное покрытие. но проблема немного сложна, поскольку она спрашивает о том, как МНОГО минимальных покрытий мы можем найти. Я правильно применяю алгоритм ... единственная проблема в том, что я не могу найти, сколько еще минимальных покрытий может быть возможно для данного набора FD

1 Ответ

1 голос
/ 07 января 2020

Общий алгоритм создания минимального покрытия состоит из трех этапов:

  1. Разделение правой части с получением FD только с одним атрибутом в правой части.

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

  3. Для каждой оставшейся зависимости попытайтесь выяснить, можно ли ее устранить.

В вашем случае первый шаг выдает: 

F = { A C → G
      A C D → B
      B C → D
      C G → B
      C G → D
      C E → A
      C E → G
      D → E
      D → G }

На втором шаге мы должны проверить первые семь зависимостей. Для каждой зависимости A1A2...An -> B мы пытаемся по очереди исключить каждую Ai и посмотреть, включено ли B в замыкание оставшихся атрибутов (замыкание, принятое по отношению к F). В этом случае у нас есть две возможности: из ACD -> B мы можем исключить либо A, либо D. Итак, теперь у нас есть два различных набора зависимостей: 

F1 = { A C → G
       C D → B
       B C → D
       C G → B
       C G → D
       C E → A
       C E → G
       D → E
       D → G }

и 

F2 = { A C → G
       A C → B
       B C → D
       C G → B
       C G → D
       C E → A
       C E → G
       D → E
       D → G }

Теперь мы можем применить последний шаг: для каждой зависимости X -> A мы можем видеть, если A включено в закрытие X, X+ относительно всех других зависимостей. В этом случае мы можем устранить эту зависимость.

В общем случае результат будет зависеть от порядка, в котором мы применяем эти проверки.

Здесь есть четыре различных канонических обложки: 

G1 = { A C → G
       B C → D
       C G → B
       C E → A
       D → E
       D → G }

G2 = { A C → G
       B C → D
       C G → D
       C E → A
       C D → B
       D → E
       D → G }

G3 = { A C → B
       B C → D
       C G → B
       C E → A
       D → E
       D → G }

G4 = { A C → B
       B C → D
       C G → D
       C E → A
       D → E
       D → G }

Примечание: мне не ясно, есть ли другие канонические обложки.

...