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



Pdf көрінісі
бет25/177
Дата15.02.2022
өлшемі2,58 Mb.
#25567
түріУчебное пособие
1   ...   21   22   23   24   25   26   27   28   ...   177
XY 
⊆ U и Y, образует структуру функциональных зависимостей от-
ношения R, которая характеризуется следующим набором аксиом, назы-
ваемых аксиомами Армстронга
1)  если  
⊇ Y, то → Y  (рефлексивность); 
2)  если 
→ Y и W ⊇ Z, то X ∪ → Y ∪ Z
 
(продолжение); 
3)  если 
→ Y и → Z, то → Z   (транзитивность). 
Легко видеть, что аксиомы 2) и 3) могут быть объединены в одну ак-
сиому: 
4) если 
→ Y и Y ∪  Z, то X ∪ → Z (псевдотранзитивность). 
Полезны также следующие свойства, вытекающие из 1)–3): 
5) если 
→ Y и → Z, то → Y ∪ Z (аддитивность); 
6) если 
→ Y и Z ⊆ Y, то → Z (декомпозиция). 
Аксиомы  Армстронга  можно  рассматривать  как  правила  вывода,  по-
зволяющие  выводить  функциональные  зависимости,  логически  следую-
щие из заданного набора зависимостей. 
Аксиомы  Армстронга  являются  надежными  и  полными,  иными  сло-
вами, если зависимость 
→ Y выведена из F по этим аксиомам, то она 
выполняется в любом отношении, в котором выполняются все зависимо-
сти из F, и наоборот, если некоторая зависимость 
→ Y не выводится из 
F  по  аксиомам  Армстронга,  то  можно  построить  экземпляр  отношения, 
для которого выполняются все зависимости из F и не выполняется зави-
симость X 
→ Y
Пусть задана схема отношения R = (UF), X 
⊆ Uзамыканием множе-
ства  атрибутов  Х  относительно  набора  зависимостей  F  называется  мно-
жество всех таких атрибутов A
i 
∈ U, что зависимость X → A
i
 выводится 
из по аксиомам Армстронга; замыкание Х обозначают Х
+

Таким  образом,  Х

– 
максимальное  по  включению  подмножество 
множества  U,  функционально  зависимое  от  Х  при  заданном  наборе 
функций F. Ясно, что зависимость (
→ Y) ∈ F тогда и только тогда, ко-
гда Х

⊇ Y
Отметим следующие свойства замыканий: 
1)  X

⊇ X
2)  X 
⊇ Y ⇒ X

⊇ Y
+

3)  (X
+
)

X
+

 
29


 
Аналогичные свойства имеют и замыкания наборов функций. 
Вычисление  F
+
  –  довольно  трудоемкая  задача,  поскольку  F
+
  может 
быть довольно большим, даже если F мало, и может содержать порядка 
2
n
  элементов,  где  n  –  количество  атрибутов  в  отношении.  Фактически 
вычисление F
+
 сводится к вычислению замыканий подмножеств атрибу-
тов. 
Аксиомы  Армстронга  не  являются  достаточно  удобными  для  непо-
средственного применения при вычислении замыканий подмножеств ат-
рибутов, и обычно используется описанный ниже алгоритм, его правиль-
ность легко обосновывается теми же аксиомами Армстронга. Этот алго-
ритм требует времени пропорционально длине всех выписанных зависи-
мостей из набора F
Пусть задана схема R = (UF) и X 
⊂ U, требуется вычислить Х
+

Шаг 1: положить Х
(0) 
:= Х, i := 0;  
Шаг 2: найти 
Х
(i+1)
 – множество всех таких атрибутов у 
∈ U \ X
(i)
, что 
существует некоторая зависимость V 
→ W ∈ F, такая что Х
(i
⊇ V и ∈ W
Шаг 3: если 
Х
(i+1) 

∅,  то  Х
(i
=  Х
+
  и  конец  работы,  иначе  
X
(i+1) 
:= Х
(i)
 
∪ ∆X
(i+1)
i := + l и перейти к шагу 2. 
Поскольку  множество  атрибутов  U  конечно,  то  алгоритм  всегда  за-
канчивает работу за конечное число итераций. 
П р и м е р 
Пусть R = (UF) – схема отношения, где 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 = (UF), X 
⊆ U
 
30


 
Множество  Х  называют  сверхключом  схемы  отношения  R,  если  
Х

U, т. е. зависимость Х 
→ U принадлежит F
+
 . 
Минимальный по включению сверхключ называется ключом, т. е. Х – 
ключ схемы R, если: 
1)  X
+
 = U
2)  ни для какого собственного подмножества Y 
⊂ ХY

≠ U
В  литературе  часто  такой  ключ  называют  возможным  ключом,  а 
собственно  ключом  называют  некоторый  определенный  возможный  по-
меченный  ключ;  в  свою  очередь  такой  помеченный  ключ  иногда  назы-
вают  первичным,  а  остальные – просто  ключами.  Здесь  эти  термины 
(«возможный  ключ», «первичный  ключ»)  не  используются,  поскольку 
они связаны с семантикой базы. 
В принципе отношение может иметь несколько ключей. Если атрибут 
содержится в некотором ключе, то его называют ключевым или первич-
ным  атрибутом  отношения,  в  противном  случае  атрибут  называют  не-
первичным
Задача  нахождения  произвольного  «первого  попавшегося»  ключа  от-
ношения решается довольно просто. Это можно сделать следующим об-
разом: рассматривается все множество атрибутов U, из него вычеркива-
ется любой атрибут, получаем множество V; если V

U, то вычеркнутый 
атрибут  так  и  остается  вычеркнутым,  иначе  возвращаем  его  на  место. 
Далее пытаемся вычеркнуть следующий атрибут, так продолжаем до тех 
пор, пока ни один атрибут нельзя будет вычеркнуть. Оставшийся набор 
атрибутов является ключом отношения. 
Вычисление  всех  ключей  отношения – задача  довольно  трудоемкая, 
поскольку ключей может быть экспоненциально много. Задачи нахожде-
ния  минимального  по  количеству  атрибутов  ключа,  а  также  проверки, 
является  ли  конкретный  атрибут  ключевым  (первичным),  относятся  к 
классу NP-трудных, т. е. не имеют алгоритмов решения с полиномиаль-
ной оценкой трудоемкости. 
П р и м е р 
Для схемы отношения R = (UF), где 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
}. 


Достарыңызбен бөлісу:
1   ...   21   22   23   24   25   26   27   28   ...   177




©emirsaba.org 2024
әкімшілігінің қараңыз

    Басты бет