Сохранение зависимостей, основанное на оригинальных функциональных зависимостях или каноническом покрытии? - PullRequest
Новая
       90

Сохранение зависимостей, основанное на оригинальных функциональных зависимостях или каноническом покрытии?

0 голосов
/ 20 апреля 2019

Учитывая эти функциональные зависимости для 

R: {A,B,C,D,E,F}

AC->EF
E->CD
C->ADEF
BDF->ACD

, я получил это как каноническое покрытие: 

E->C
C->ADEF
BF->C

И затем разбил его на нормальную форму Бойса Кодда: 

Relation 1: {C,A,D,E,F} 
Relation 2: {B,F,C}

Я полагал, что это без потерь и сохранение зависимости?Но верно ли это, поскольку из исходных функциональных зависимостей BDF-> ACD больше нет ни в одном из моих отношений.Но если я уйду от своего вычисленного канонического покрытия, тогда все мои функциональные зависимости будут сохранены.

Так что вопрос в следующем: сохраняет ли это разложение на BCNF-зависимость?

1 Ответ

1 голос
/ 20 апреля 2019

Разложение сохраняет зависимости в том и только в том случае, если объединение проекции зависимостей на разложенные отношения является накрытием зависимостей отношения.

Итак, чтобы узнать, сохраняется ли разложение или нетзависимостей недостаточно, чтобы проверить, сохранились ли зависимости конкретного покрытия или нет (например, путем просмотра, имеет ли какое-то разложенное отношение все атрибуты зависимости).Например, в отношении R(ABC) с покрытием F = {A→B, B→C, C→A} можно подумать, что при разложении R1(AB) и R2(BC) зависимость C→A не сохраняется.Но если вы проецируете F на AB, вы получаете A→B, B→A, проецируете его на BC, вы получаете B→C, C→B, поэтому из их объединения вы можете также получить C→A.

Проверкане просто, даже если существуют полиномиальные алгоритмы, которые выполняют эту задачу (например, один из них описан в J. Ullman, Принципы систем баз данных, Computer Science Press, 1983).

Предполагая зависимости, которые вы далиобразуют покрытие зависимостей отношения, найденная вами каноническая оболочка неверна.На самом деле BF -> C не может быть получено из исходных зависимостей.

По этой причине ваше разложение некорректно, поскольку R2(BCF) не в BCNF (фактически, это не в 2NF).

Одним из возможных канонических покрытий R является следующее: 

BDF → C
C → A
C → E
C → F
E → C
E → D

Следуя алгоритму анализа, в BCNF возможны две декомпозиции (в соответствии с зависимостями, выбранными для исключения).Один из них: 

R1 = (ACDEF)
R2 = (BC)

, а другой: 

R1 = (ACDEF)
R3 = (BE)

(обратите внимание, что BC и BE являются ключами-кандидатами исходного отношения вместе с BDF).

Обложка зависимостей в R1: 

C → A
C → E
C → F 
E → C
E → D

, в то время как в R2 и R3 нет нетривиальных зависимостей.

Отсюда можно сделать вывод, что обе декомпозиции не сохраняют зависимости;например, следующая зависимость (и все производные от нее) не может быть получена: 

BDF → C
...