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

Question

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

. Как мне решить вышеуказанный вопрос? Что я пробовал:--------------------------------------------------------------Мой подход к определению количества возможных минимальных покрытий состоял в том, чтобы сначала использовать алгоритм (приведенный ниже) и найти различные способы, с помощью которых я мог бы найти минимальное покрытие, выполняя алгоритм (следовательно, давая количество возможных минимальных покрытий). Проблема в том, что я не уверен, как мне следует рассмотреть «другой способ найти минимальное прикрытие». Например:Алгоритм нахождения минимального покрытия (Учебник: «Основы систем баз данных» - Элмасри, Нават):

Ввод: набор функциональных зависимостей E.

1. Установить F: = E.

2. Заменить каждую функциональную зависимость X → {A1, A2, ..., An} в F наn функциональных зависимостей X → A1, X → A2, ..., X → An.

3. Для каждой функциональной зависимости X → A в Fдля каждого атрибута B, который является элементом X, если {{F - {X → A}} ∪ {(X - {B}) → A}} эквивалентен F, то заменить X → A на (X - {B}) → A в F.

4. Для каждой оставшейся функциональной зависимости X → A в F, если {F - {X → A}} эквивалентно F, то удалить X → A из F.

При применении алгоритма при ACD → B я обнаружил, что A и D являются посторонними (замена ACD → B на C → B дает набор функциональных зависимостей, эквивалентных F)на шаге 3, но я не уверен, должен ли я заменить ACD → B на C → B или ACD → B на AC → B или ACD → B на CD → B. Скажите, если я заменю ACD → B на AC → B илиCD → B, я не уверен, что замена ACD → B на AC → B может привести к одной возможной минимальной обложке, а замена ACD → B на CD → B может привести к другой возможной минимальной обложке. ------------------------------------------------------------- Примечание :

• «Число возможных минимальных покрытий» обозначает минимально возможные покрытия, учитывая вышеуказанное соотношение и функциональные зависимости.
• Предположим, что все функциональные зависимости, упомянутые в вопросе,все что держится.

Answer 1

Я не уверен, должен ли я заменить ACD → B на C → B или ACD → B на AC → B или ACD → B на CD → B.

Собственно алгоритмдолжны применяться последовательно. Таким образом, вы можете удалить либо A, либо D из этой зависимости, но затем вам придется снова проверить соответствие правила алгоритма результирующему набору функциональных зависимостей.

Фактически, если вы удалите, например, A, результирующееЗависимость CD → B, и если вы повторите этот шаг, вы обнаружите, что теперь в этой зависимости больше нет посторонних атрибутов. Точно так же, если вы удалите D, также получающаяся зависимость AC → B не будет содержать посторонних атрибутов.

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

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