Сохраняет ли эта зависимость разложения?

Question

Я пытаюсь выяснить, как посмотреть, сохраняет ли декомпозиция зависимость или нет. Отношение: R (ABCDEF) и имеют следующие FD. AB -> CE, C -> EB, E -> D, C -> D. Затем мы разбиваем отношение на: R1 (BF), R2 (ACB) и R3 (CDE). Сохраняет ли эта зависимость?

У меня сложилось впечатление, что для вычисления этого вы делаете замыкание на всех левых сторонах FD. Это дает:

AB + = ABCEBD, который включает AB -> CE

C + = CEBD, который включает в себя FD's

E + = ED, включая E-> D

Так что в моем мире это сохранение зависимости. Однако, согласно маркировке, ответ таков: это не так. Что я делаю неправильно и / или неправильно понимаю концепцию?

Чтобы уточнить, я понимаю, что некоторые зависимости не выполняются в каждом разложенном отношении. Например, AB -> E, так как мы не можем найти отношение, которое включает эти три вместе. Тем не менее, я считаю, что поскольку закрытие AB все еще включает E, это все равно будет считаться сохранением зависимости. Это где я ошибаюсь? Объяснение концепции (мой учебник ОЧЕНЬ кратко) будет с благодарностью.

Answer 1

Вкратце : вы правы, зависимости сохранены.

Длинное объяснение.

Для определения концепции сохранения зависимостей сначала нам необходимо определить концепцию проекции набора функциональных зависимостей :

С учетом схемы R (T) с набором зависимостей F и с заданным подмножеством T _i от T, проекция из F на T _i определяется как:

π _{T i} = {X → Y ∈ F ⁺ | X, Y ⊆ T _i }

Обратите внимание, что нам нужно учитывать зависимости F ⁺ (закрытие зависимости F), а не только от F.

Теперь мы можем определить свойство сохранения зависимостей для декомпозиции:

Разложение ρ = {R ₁ (T ₁ ), ..., R _n (T _n )} R (T) с зависимостями F сохраняет зависимости тогда и только тогда, когда ∪ π _{T i} (F) ≡ F.

Это может быть формально подтверждено путем применения алгоритма, описанного в книгах, по крайней мере, с 1983 года (см., Например, Уллман Дж. (1983). Принципы систем баз данных. Пресса компьютерных наук, Роквилл, Мэриленд), который вычисляет в за полиномиальное время замыкание набора атрибутов относительно проекции зависимостей.

На практике, чтобы проверить, что зависимости сохраняются в вашем примере, нет необходимости применять этот алгоритм, но достаточно вычислить каноническое покрытие зависимостей:

A B → C
C → B
C → E
E → D

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

Обратите внимание, что при рассуждении о множестве зависимостей всегда удобно рассуждать о их каноническом покрытии.