Учебное пособие Для студентов университетов Специальностей «Информатика», «Прикладная математика»

 
Аналогичные свойства имеют и замыкания наборов функций. 
Вычисление  F
+
  –  довольно  трудоемкая  задача,  поскольку  F
+
  может 
быть довольно большим, даже если F мало, и может содержать порядка 
2
n
  элементов,  где  n  –  количество  атрибутов  в  отношении.  Фактически 
вычисление F
+
 сводится к вычислению замыканий подмножеств атрибу-
тов. 
Аксиомы  Армстронга  не  являются  достаточно  удобными  для  непо-
средственного применения при вычислении замыканий подмножеств ат-
рибутов, и обычно используется описанный ниже алгоритм, его правиль-
ность легко обосновывается теми же аксиомами Армстронга. Этот алго-
ритм требует времени пропорционально длине всех выписанных зависи-
мостей из набора F. 
Пусть задана схема R = (U, F) и X 
⊂ U, требуется вычислить Х
+
. 
Шаг 1: положить Х
(0) 
:= Х, i := 0;  
Шаг 2: найти 
∆Х
(i+1)
 – множество всех таких атрибутов у 
∈ U \ X
(i)
, что 
существует некоторая зависимость V 
→ W ∈ F, такая что Х
(i) 
⊇ V и y ∈ W; 
Шаг 3: если 
∆Х
(i+1) 
= 
∅,  то  Х
(i) 
=  Х
+
  и  конец  работы,  иначе  
X
(i+1) 
:= Х
(i)
 
∪ ∆X
(i+1)
, i := i + l и перейти к шагу 2. 
Поскольку  множество  атрибутов  U  конечно,  то  алгоритм  всегда  за-
канчивает работу за конечное число итераций. 
П р и м е р 
Пусть R = (U, F) – схема отношения, где U = {A
1
, A
2
, …, А
7
},  
F = {А
1
, А
4
 
→ А
2
; А
2
 
→ A
3
; А
3
 
→ А
4
; А
4
, А
7
 
→ А
5
; А
5
 
→ А
6
; А
6
 
→ А
7
}, 
множество Х = {А
3
, А
5
}.  
Требуется вычислить Х
+
. 
Выпишем последовательность действий для каждого этапа.  
Х
(0)
 = (А
3
, А
5
); 
∆X
(1) 
= {А
4
, А
6
}, Х
(1)
= {А
3
, А
4
, А
5
, А
6
}; 
∆Х
(2) 
={А
7
}, Х
(2)
={А
3
, А
4
, A
5
, А
6
, А
7
}; 
∆X
(3) 
= 
∅, следовательно, Х
+ 
= Х
(2) 
= {А
3
, А
4
, А
5
, А
6
, А
7
}. 
4.2.2. Ключи схем отношений 
Рассматривая  наборы  объектов,  мы  предполагали,  что  существует 
ключ  –  набор  атрибутов,  однозначно  определяющий  объект.  Аналогич-
ное понятие существует и для отношения с заданным множеством функ-
циональных  зависимостей,  т.  е.  набор  атрибутов,  однозначно  опреде-
ляющий кортеж отношения. 
Пусть задана схема отношения R = (U, F), X 
⊆ U; 
 
30

 
Множество  Х  называют  сверхключом  схемы  отношения  R,  если  
Х
+ 
= U, т. е. зависимость Х 
→ U принадлежит F
+
 . 
Минимальный по включению сверхключ называется ключом, т. е. Х – 
ключ схемы R, если: 
1)  X
+
 = U; 
2)  ни для какого собственного подмножества Y 
⊂ Х, Y
+ 
≠ U. 
В  литературе  часто  такой  ключ  называют  возможным  ключом,  а 
собственно  ключом  называют  некоторый  определенный  возможный  по-
меченный  ключ;  в  свою  очередь  такой  помеченный  ключ  иногда  назы-
вают  первичным,  а  остальные – просто  ключами.  Здесь  эти  термины 
(«возможный  ключ», «первичный  ключ»)  не  используются,  поскольку 
они связаны с семантикой базы. 
В принципе отношение может иметь несколько ключей. Если атрибут 
содержится в некотором ключе, то его называют ключевым или первич-
ным  атрибутом  отношения,  в  противном  случае  атрибут  называют  не-
первичным. 
Задача  нахождения  произвольного  «первого  попавшегося»  ключа  от-
ношения решается довольно просто. Это можно сделать следующим об-
разом: рассматривается все множество атрибутов U, из него вычеркива-
ется любой атрибут, получаем множество V; если V
+ 
= U, то вычеркнутый 
атрибут  так  и  остается  вычеркнутым,  иначе  возвращаем  его  на  место. 
Далее пытаемся вычеркнуть следующий атрибут, так продолжаем до тех 
пор, пока ни один атрибут нельзя будет вычеркнуть. Оставшийся набор 
атрибутов является ключом отношения. 
Вычисление  всех  ключей  отношения – задача  довольно  трудоемкая, 
поскольку ключей может быть экспоненциально много. Задачи нахожде-
ния  минимального  по  количеству  атрибутов  ключа,  а  также  проверки, 
является  ли  конкретный  атрибут  ключевым  (первичным),  относятся  к 
классу NP-трудных, т. е. не имеют алгоритмов решения с полиномиаль-
ной оценкой трудоемкости. 
П р и м е р 
Для схемы отношения R = (U, F), где U = {А
1
, А
2
, …, А
8
}, 
 F = {А
1
 
→ А
2
; А
2
 
→ А
3
; A
3
 
→ А
1
; А
2
, А
3
 
→ А
4
; А
4
, А
7
 
→ 
А6
;  
А
6
, А
5
 
→ А
7
; А
7
 
→ А
8
} требуется найти все ключи, наборы первичных и 
непервичных атрибутов и сверхключ. В результате решения получаем:  
1) Все ключи отношения: 
К
1
 = {А
1
, А
5
, А
6
}, К
2
 = {А
1
, А
5
, А
7
}, К
3
 = {А
2
, А
5
, 
A6
},  
К
4
 = {А
2
, А
5
, А
7
}, К
5
 = {А
3
, А
5
, А
6
}, К
6
 = {А
3
, А
5
, А
7
}.  
2) Множество первичных атрибутов: {А
1
, А
2
, А
3
, А
5
, А
6
, А
7
}.  
 
31

 
3) Множество непервичных атрибутов: {А
4
, А
8
}. 
Ясно, что сверхключом  является любое множество атрибутов, содер-
жащее ключ. В приведенном примере сверхключом является множество 
{А
1
, А
2
, А
5
, А
6
}. 

жүктеу/скачать 2,58 Mb.

Достарыңызбен бөлісу: