Разложения BCNF и соединения без потерь для баз данных

Ваш вопрос

Что из следующего является разложением R без потерь в нормальную форму Бойса-Кодда (BCNF)?

предполагает, что у вас есть набор параметров, и вы должны выбрать, какой из них является декомпозицией без потерь, но, поскольку вы не упомянули параметры, я бы сначала (ЧАСТЬ A) разложил отношение на НФБК (сначала в 3NF, затем в BCNF ), а затем (ЧАСТЬ B) иллюстрируют, как проверить, является ли данная декомпозиция декомпозицией соединения без потерь или нет. Если вам просто интересно узнать, как проверить, является ли данное разложение BCNF без потерь или нет, сразу переходите к ЧАСТИ B моего ответа.

ЧАСТЬ А

Чтобы преобразовать отношение R и набор функциональных зависимостей (FD's) в 3NF, вы можете использовать синтез Бернштейна. Чтобы применить синтез Бернштейна -

• Сначала мы убеждаемся, что заданный набор FD's является минимальным покрытием.
• Во-вторых мы берем каждый FD и делаем его собственной подсхемой.
• В-третьих, мы пытаемся объединить эти подсхемы

Например в вашем случае:

R = {A,B,C,D}
FD's = {A->B,C->D,AD->C,BC->A}

Сначала мы проверяем, является ли FD's минимальным покрытием (одноэлементная правая часть, нет постороннего атрибута левой стороны, нет избыточного FD)

• Singleton RHS: Все указанные FD уже имеют singleton RHS.
• Нет посторонних атрибутов LHS. Ни один из FD не имеет посторонних атрибутов LHS, которые необходимо удалить.
• Нет избыточных FD. Нет избыточных FD.

Следовательно, данное множество ФД уже является минимальным покрытием.

Во-вторых, мы создаем для каждой FD собственную подсхему. Итак, теперь у нас есть - (ключи для каждого отношения выделены жирным шрифтом)

R₁={A,D,C}
R₂={B,C,A }
R₃={C,D}
R₄={A,B

В-третьих мы смотрим, можно ли комбинировать какую-либо из подсхем. Мы видим, что R₁ и R₂ уже имеют все атрибуты R и, следовательно, R_3. и R₄ можно опустить. Итак, теперь у нас есть -

S₁ = {A,D,C}
S₂ = {B,C,A}

Это в 3NF. Теперь, чтобы проверить BCNF, мы проверяем, не нарушает ли какое-либо из этих отношений (S₁,S₂) условия BCNF. strong> (т. е. для каждой функциональной зависимости X->Y левая часть (X) должна быть суперключом) . В этом случае ни один из них не нарушает BCNF, и, следовательно, он также разлагается на BCNF.

ЧАСТЬ Б

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

Создайте таблицу, как показано на рисунке 1, с количеством строк, равным количеству разложенных отношений, и количеством столбцов, равным количеству атрибутов в нашем исходном заданном R.

Мы помещаем a во все атрибуты, которые присутствуют в соответствующем декомпозированном отношении, как на рисунке 1. Теперь мы проходим через все FD {C->D,A-> B,AD->C,BC->A} один за другим и добавляйте a, когда это возможно. Например, первый FD — это C->D. Поскольку в обеих строках столбца C есть a, а во второй строке столбца D есть пустое место, мы помещаем a< /strong> там, как показано в правой части изображения. Мы останавливаемся, как только одна из строк полностью заполняется a, что указывает на то, что это декомпозиция без потерь. Если мы пройдемся по всем FD и ни одна из строк нашей таблицы не будет полностью заполнена a, то это декомпозиция с потерями.