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

Question

Рассмотрим отношение R(ABCDE) следующим текстом ФЗ:

• AB -> C
• BC -> D
• CD -> E
• DE -> A
• AE -> B

проекта эти ФЗ на отношения S(ABCD). Какая из следующих FD удерживается в прогнозируемом отношении?

1. А -> В
2. А -> Д
3. БК -> A
4. переменного тока -> В

формулировка в приведенном выше вопрос непосредственно скопированы из назначения

Правильный ответ дается равным 3.

, поскольку последние 3 FD содержат E, они не удерживаются в проекции на R (ABCD). Я верю. Так что это оставляет меня с AB -> C и BC -> D Я не могу понять, как определить правильный ответ из моего текущего процесса.

Answer 1

Ваш вопрос непонятен. Я предполагаю, что вы спрашиваете, какая из последних четырех зависимостей имеет место в отношении R (ABCD): ответ является третьим. Это может быть просто доказывается путем вычисления закрытия BC в исходном наборе зависимостей:

BC+ = BC 
BC+ = BCD (using BC → D) 
BC+ = BCDE (using CD → E) 
BC+ = BCDEA (using DE → A) 

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

Почему ответ может быть получен путем вычисления замыкания определителя?

Назовем FS проекцией исходного набора зависимостей F по отношению S(ABCD). Таким образом, для определения проекции набора зависимостей имеем:

FS = {X → Y ∈ F ⁺ | X, Y ⊆ ABCD}

, и вопрос задает вопрос о том, принадлежат ли определенные зависимости к FS. Но поскольку для вычисления FS требуется вычисление F ⁺, которое является экспоненциальной задачей, вместо вычисления его мы проверяем для каждой из четырех зависимостей X → Y, если она принадлежит F ⁺. Это эквивалентно многочленной задаче вычисления замыкания X и нахождения, если Y принадлежит ему или нет (мы уже знаем, что зависимости имеют все атрибуты в наборе ABCD).

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

Answer 2

«Проектировать эти FD на отношение S (A, B, C, D)» является неаккуратным письмом. (Хотя вы прокомментируете, что вы цитируете свое задание.) Предположительно, это пытается сказать, что если эти FD хранятся в R (ABCDE), то какой из следующих FDs имеет место в своей проекции на ABCD.

Когда некоторые FD держат, другие должны также удерживаться, потому что те делают. Таким образом, в R есть еще больше FD, чем те, которые вам дали. Более того, некоторые из FD, которые хранятся, но не выполняются, потому что некоторые из FD, использующих E hold, даже если они сами не содержат E. Поэтому сначала вам нужно найти больше FD в R, пока не найдете тот, который будут сохраняться после проецирования, поскольку они не связаны с E.

Один из способов - найти F + (замыкание множества FD). Но это может быть очень большим. Вместо этого мы можем использовать понятие закрытия набора атрибутов. Это набор всех атрибутов, определенных набором атрибутов. (Из определенных атрибутов мы знаем все FD, которые держатся с этим определителем.) Существует алгоритм его поиска. Если определитель детерминанта ответа является определителем в F, то мы можем вычислить его замыкание в R, чтобы проверить, сохраняется ли его ответ FD в R.

Если ни один из детерминантов ФД не появился как детерминанты в F, мы имели бы чтобы начать генерировать FD в F +, пока мы не получили один с детерминантом, который также был детерминантом среди ответов. Затем мы могли применить предыдущий шаг.