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

 
R
22
 = ({A
1
, A
2
, A
3
, A
6
}, {A
1
 
→ A
2
; А
2
 
→ А
1
; А
2
 
→ А
3
;  A
3
 
→ А
6
}).  
Ш а г 3. R
21
 находится в УТНФ. Рассматриваем зависимость A
3 
→ А
6
; 
для  нее  выполняется  {А
3
}
+ 
≠  U
22
.  Следовательно,  она  не  удовлетворяет 
УТНФ. Выделяем зависимость A
3
 
→ А
6
 в отдельную схему. Получаем:  
R
221
 = ({A
3
, A
6
}, {A
3
 
→ A
6
}),  
R
222
 = ({A
1
, A
2
, A
3
), {A
1
 
→ А
2
; А
2
 
→ А
1
; А
2
 
→ А
3
}). R
221
 и R
222
 находятся 
в УТНФ. Следовательно, 
УТНФ 
ρ = (R
1
, R
21
, R
221
, R
222
) для схемы R. 
Дерево декомпозиции имеет вид: 
 
R
R
2
R
21
R
22
R
222
R
221
R
1
 
 
 
 
 
 
 
 
Однако  полученная  декомпозиция  имеет  следующие  существенные 
недостатки. 
1. R
1
 и R
21
 можно объединить в одну схему, получим R
1
 = ({A
3
, A
4
, A
5
}, 
{A
3
→ А
4
; А
3
 
→ А
5
}). Заметим, что так делать можно не всегда. Например, 
если бы была зависимость А
4
 
→ А
5
, то в R
1
 получили бы транзитивную 
зависимость A
3
 
→ А
4
 
→ А
5
. 
2. A
3
 и А
6
 нецелесообразно объединять в одну подсхему, поскольку в 
исходной схеме есть транзитивная зависимость A
3
 
→ А
5
 
→ А
6
, где A
3
 и А
6
 
не смежны, и поэтому такое объединение приведет к избыточности дан-
ных в базе. Лучше вместо {А
3
, А
6
} использовать подсхему {А
5
, А
6
}. Легко 
видеть,  что  такая  замена  не  нарушает  свойства  соединения  без  потерь, 
попросту  функциональные  зависимости  проверяются  в  другом  порядке. 
Таким образом, пришли к декомпозиции: 
ρ = (({А
3
, А
4
, А
5
}, {А
3
 
→ А
4
; А
3
 
→ А
5
}), ({А
5
, А
6
}, {А
5
 
→ А
6
}), 
({А
1
, А
2
, А
3
), {А
1
 
→ А
2
; А
2
 
→ А
1
; А
2
 
→ А
3
})). 
При больших количествах атрибутов такого рода улучшения требуют 
значительных затрат. Целесообразно поступать следующим образом. 
1. Найти произвольный ключ К. 
2.  Построив  К
+
,  выписать  все  К
(i)
  (см.  алгоритм  построения  замыка-
ний). 
 
46

 
3. Просматривать К
(i) 
в обратном порядке и выделять в отдельные под-
схемы зависимости X 
→ Y, нарушающие УТНФ и такие, что Х и Y при-
надлежат К
(i)
 с наибольшими номерами i. 
Во  многих  случаях  такой  подход  исключает  включение  в  подсхемы 
несмежных транзитивных компонент. 
Заметим,  что  не  всегда  можно  преобразовать  схему  отношения  к 
УТНФ с сохранением зависимостей.  
Например, R = ({A
1
, A
2
, A
3
}, {A
1
, A
2
 
→ A
3
; А
3
 
→ A
l
}).  
Схема R находится в ТНФ, но не в УТНФ, поскольку для зависимости 
A
3
 
→ А
1
 выполняется {A
3
}
+ 
≠ {А
1
, А
2
, А
3
}. УТНФ дает декомпозиция: R
1
 = 
({A
1
, A
3
), {A
3
 
→ A
1
}),  R
2
 = ({A
2
, A
3
}),  но при этом теряется зависимость 
А
1
, А
2
 
→ A
3
, и, следовательно, построить УТНФ с сохранением этой зави-
симости невозможно. 
4.3.4. Четвертая нормальная форма схем отношений 
 
На  практике  проектирование  реляционной  базы  данных  завершается 
после  нахождения  третьей  или  усиленной  третьей  нормальной  формы 
исходной схемы отношения. Однако даже УТНФ не всегда избавляет от 
избыточности  данных.  Связано  это  с  существованием  так  называемых 
многозначных  зависимостей.  В  простейшем  случае  многозначные  зави-
симости возникают при приведении исходного отношения к первой нор-
мальной форме. 
П р и м е р 
ФИО_преподавателя Группа Вид_нагрузки 
Иванов И.И. 1 
Лекции 
Иванов И.И. 1 
Практика 
Иванов И.И. 1 
Лабораторные 
Иванов И.И. 2 
Лекции 
Иванов И.И. 2 
Практика 
Иванов И.И. 2 
Лабораторные 
Сидоров С.С. 1 
Практика 
Сидоров С.С. 1 
Лабораторные 
Сидоров С.С. 2 
Практика 
Сидоров С.С. 2 
Лабораторные 
Предположим,  что  преподаватели  некоторой  кафедры  должны  вести 
занятия в каждой группе студентов, специализирующихся по данной ка-
федре.  Кроме  этого  существует  требование  обязательного  включения  в 
общую  нагрузку  преподавателя  определенных  видов  нагрузки  (лекции, 
 
47

 
практические, лабораторные занятия). Поскольку между номерами групп 
и видами нагрузки нет никакой прямой связи, то в отношении, содержа-
щем атрибуты ФИО_преподавателя, Группа, Вид_нагрузки, каждый кор-
теж должен содержать комбинации групп и видов нагрузки. Данное от-
ношение находится в усиленной третьей нормальной форме, так как име-
ется  только  один  ключ,  включающий  все  три  атрибута.  Тем  не  менее 
имеется явная избыточность данных из-за повторения для каждого пре-
подавателя комбинации группы и вида нагрузки. Связано это с тем, что в 
отношении  между  атрибутами  существуют  две  независимые  связи  типа 
«один ко многим»: ФИО_преподавателя : Группа, ФИО_преподавателя : 
Вид_нагрузки.  При  этом  верно  следующее  ограничение:  если  кортежи 
(A, B, C) и (A, D, E) присутствуют одновременно, то кортежи (A, B, E) и 
(A, D, C) также присутствуют в отношении. 
Ситуацию  можно  улучшить,  если  выполнить  декомпозицию  на  две 
подсхемы  (ФИО_преподавателя,  Группа)  и  (ФИО_преподавателя, 
Вид_нагрузки). 
ФИО_преподава-
теля 
Группа 
 
ФИО_преподава-
теля 
Вид_нагрузки 
Иванов И.И. 1  
Иванов И.И. 
Лекции 
Иванов И.И. 2  
Иванов И.И. 
Практика 
Сидоров С.С. 1   
Иванов И.И. 
Лабораторные
Сидоров С.С. 2   
Сидоров С.С. 
Практика  
 
 
 
Сидоров С.С. 
Лабораторные
Введем понятие многозначной зависимости. 
Пусть R – схема отношений с атрибутами U = {A
1
, …, A
n
} и подмно-
жествами X, Y, Z 
⊂ U. Подмножество Y многозначно зависит от X, обо-
значаем X 
⎯>> Y / Z тогда и только тогда, когда  в каждом отношении со 
схемой R множество значений Y, соответствующее заданной паре значе-
ний (X, Z), зависит от X, но не зависит от Z. 
Нетрудно показать, что для данной схемы R(A, B, C) многозначная за-
висимость A 
⎯>> B/C выполняется тогда и только тогда, когда выполня-
ется многозначная зависимость A 
⎯>> C/B. То есть многозначные зави-
симости всегда образуют связные пары. 
Многозначные зависимости являются обобщениями функциональных 
зависимостей  в  том  смысле,  что  всякая      функциональная  зависимость 
является  многозначной.  Точнее  говоря,  функциональная  зависимость  
A 
→ B – это многозначная зависимость A ⎯>> B/(U \ (A ∪ B)), в которой 
множество зависимых значений B, соответствующее значению A, являет-
ся одноэлементным множеством. 
 
48

 
Теорема Фейгина
. Пусть R – схема отношений с множеством атрибу-
тов U = A 
∪ B ∪ C. Декомпозиция ρ = (R
1
, R
2
), где R
1
 = (A, B), R
2 
= (A, C) 
обладает  свойством  соединения  без  потерь  тогда  и  только  тогда,  когда 
выполняется многозначная зависимость A 
⎯>> B/C. 
Теорема Фейгана является более строгой версией теоремы Хита. 
Теперь дадим определение четвертой нормальной формы (4НФ). 

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

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