1) X(0) = X
2) X(i+1) = X(i)
Z,
где Z - множество атрибутов, таких, что в
F существует некоторая
зависимость Y
Z и Y
X(i). Поскольку X = X(0)
...
X(i)
...
U, мы
должны в конце
концов достигнуть такого X(k), что никакая зависимость из F не расширяет X(k).
3) Имеем X
+
=X(k).
Определение 3. Множества ФЗ
F и G
, определенные на
одном и том же множестве
атрибутов U, называются
эквивалентными (принадлежат одному классу эквивалентности)
,
если F
+
=G
+
. Обозначение:
F=G
ALG2.
Проверка F и G на эквивалентность:
1) Если
((Y
Z)
F) (Y
+
(F)=Y
+
(G)), то F
+
G
+
(см.ALG1)
2) Если
((A
B)
G) (A
+
(G)=A
+
(F)), то G
+
F
+
(см.ALG1)
3)
Если F
+
G
+
и G
+
F
+
, то F=G
Определение 4. Множество ФЗ F называется
минимальным
, если
1) правая часть каждой ФЗ из F содержит единственный атрибут
2)
((X
a)
F)((F-{X
a})=F) – не избыточность ФЗ
3)
((X
a)
F)(
(Z
X))((F-{X
a})
{Z
a}=F)- не избыточность атрибутов в
левой
части ФЗ
ALG3.
Построение минимального покрытия ФЗ F: (исп. ALG2)
1) Для каждой X
a: если (F-{X
a})=F, то X
a удаляется из F
2) Пусть X=(x1,x2,…,xn); (X
a)
F, G=F-{X
a}
{(X-{xi})
a}.
3) Для каждого атрибута xi в левой части оставшихся ФЗ проверяем: если (X-{xi})
+
(F)=
(X-{xi})
+
(G), то xi избыточен (удаляется)
Определение 5. Пусть U-множествово атрибутов отношения R, F-множествово ФЗ на
R.
Ключом (первичным, альтернативным)
называется X
U если:
1) (X
U)
F – условие уникальности ключа
2)
(Y
X)((Y
U)
F) – условие не избыточности ключа
ALG4.
Определение первичного ключа:
1) дополним F: F*=F
{U
q},
q-фиктивный атрибут
2) вычислим минимальное покрытие F* (по ALG3)
3) оставшиеся атрибуты образуют ключ (первичный)
Замечание. Различный порядок удаления избыточных атрибутов может приводить к
различным ключам (альтернативным). В качестве первичного ключа выбирается любой из
альтернативных ключей (желательно с меньшим числом атрибутов)
Определение 6.
Каждый
класс эквивалентности
в
F можно представить составной
обобщенной зависимостью (
CF-зависимостью
) вида:
X
1
X
2
…
X
K
X
1
Y
или
(X
1
,X
2
,…,X
Достарыңызбен бөлісу: 
