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

 
R
1
 = ({A
1
, A
2
, A
4
, A
5
, A
6
, A
7
}, 
{A
l
 
→ A
5
; А
2
 
→ А
4
; А
4
 
→ А
6
; А
5
, А
6
 
→ А
7
}). 
Зависимость А
1
 
→ A
5
 получена в результате проецирования F нa под-
схему R
1
; ключом отношения R
1
 является {А
1
, А
2
}. 
R
2
 = ({A
1
, A
3
}, {A
1
 
→ A
3
}), единственный ключ R
2
 – {А
1
}.  
R
2
 находится во второй нормальной форме, в R1 нежелательной явля-
ется зависимость А
1
 
→ А
5
. Получаем декомпозицию R
1
: 
R
11
 = ({A
1
, A
2
, A
4
, A
6
, A
7
}, {A
2
 
→ А
4
; А
4
 
→ А
6
; А
1
, А
6
 
→ А
7
}), ключ R
11
 – 
{А
1
, А
2
},  
R
12
 = ({A
1
, A
5
}, {A
1
 
→ A
5
}), ключ R
12
 – {А
1
}. 
R
12
  находится  во  второй  нормальной  форме,  в  R
11
  нежелательной  яв-
ляется зависимость А
2
 
→ А
4
, получаем декомпозицию R
11
: 
R
111
 = ({А
1
, А
2
, А
6
, А
7
}, {А
2
 
→ A
6
; А
1
, А
6
 
→ А
7
}), ключ – {А
1
, А
2
},  
R
112
 = ({A
2
, A
4
}, {A
2
 
→ А
4
}), ключ R
112
 – {А
2
}. 
R
112
 находится во второй нормальной форме, в R
111
 нежелательной яв-
ляется зависимость А
2
 
→ А
6
, получаем декомпозицию R
111
: 
 R
1111
 = ({A
1
, A
2
, A
7
}, {А
1
, А
2
 
→ А
7
}), ключ R
1111
 – {А
1
, А
2
}, 
 R
1112
 = ({A
2
, A
6
}, {A
2 
→ A
6
}) , ключ R
1112
 – {А
2
}. 
R
1111
  и  R
1112
  находятся  во  второй  нормальной  форме,  искомая  деком-
позиция (вторая нормальная форма отношения R) имеет вид  
ρ = (R
2
, R
12
, R
112
, R
1111
, R
1112
). 
Дерево декомпозиции имеет вид: 
 
 
A
1
, 
A
3
A
1
, 
A
2
, 
A
4
, 
A
5
, 
A
6
, 
A
7
A
1
, 
A
5
A
1
, 
A
2
, 
A
4
, 
A
6
, 
A
7
A
2
, 
A
4
A
1
, 
A
2
, A
6
, 
A
7
A
2
, 
A
6
A
1
, 
A
2
, 
A
7
A
1
, 
A
2
, 
A
3
, 
A
4
, 
A
5
, 
A
6
, 
A
7
Схема отношения может иметь более одной второй нормальной фор-
мы.  Так,  в  приведенном  примере  второй  нормальной  формой  исходной 
схемы является также декомпозиция 
ρ
1 
= ({A
1
, A
3
}, {А
3
, А
5
}, {А
2
, А
4
}, {А
4
, А
6
}, {А
5
, А
6
, А
7
}), 
причем 
ρ удачнее, чем ρ
1
, в смысле минимизации аномалий базы данных. 
 
40

 
В  приведенном  примере  ситуация  упрощалась  тем,  что  отношение 
имеет  единственный  ключ  (рассматривать  надо  неполные  зависимости 
непервичных атрибутов от всех ключей). 
4.3.2. Третья нормальная форма схем отношений. 
Понятие третьей нормальной формы схемы отношения тесно связано 
с понятием транзитивной зависимости, которая имеет вид цепочки функ-
циональных зависимостей с определенными ограничениями. 
Пусть задана схема отношения R = (U, F), A, C 
⊆ U. Функциональная 
зависимость А 
→ С называется транзитивной, если существует подмно-
жество атрибутов В 
⊂ U такое, что  
А 
⊉ В, В ⊉ С, А → В, В
↛
А и В 
→ С. 
Отметим, что наличие или отсутствие зависимости С 
→ В значения не 
имеет.  Если  такой  зависимости  нет,  то  транзитивная  зависимость  назы-
вается строгой транзитивной зависимостью. Например, R = ({А
1
, А
2
, А
3
, 
А
4
, А
5
}, {А
1
 
→ А
2
; А
2
 
→ А
3
; А
1
 
→ А
4
; А
4
 
→ А
5
; А
5
 
→ А
1
}). Здесь зависи-
мость А
1
 
→ А
3
 является транзитивной, так как имеем цепочку  
А
1
 
→ А
2
 
→ А
3
 и А
2
↛
A
l
. 
В то же время зависимость A
l
 
→ А
5
 не является транзитивной, хотя и есть 
цепочка А
1
 
→ А
4
 
→ А
5
, но здесь (А
4
 
→ A
l
) 
∈ F
+
, что противоречит опреде-
лению транзитивной зависимости. 
Присутствие в схеме транзитивной зависимости А 
→ В → С приводит 
к избыточности данных о связи атрибутов В и С и, следовательно, избы-
точности значений атрибутов С, что может привести к нарушению цело-
стности базы данных при изменении значений атрибутов из множеств С 
и  В.  Избыточность  значений  С  возрастает,  если  дополнительно  В 
↚ С. 
Замена схемы отношения, в которой есть транзитивная зависимость, де-
композицией, которая не содержит зависимостей такого типа, избавляет 
базу данных от указанных недостатков. Такая декомпозиция при выпол-
нении  определенных  условий  называется  третьей  нормальной  формой 
отношения. 
Третья нормальная форма
 (ТНФ) схемы отношения – это либо дан-
ная схема, если она находится во второй нормальной форме и не содер-
жит транзитивной зависимости непервичных атрибутов от ключей, либо 
декомпозиция исходной схемы, каждая подсхема которой удовлетворяет 
этим же требованиям, а сама декомпозиция обладает свойством соедине-
ния без потерь. 
 
41

 
Третья  нормальная  форма  существует  для  любой  схемы  отношения, 
причем часто не единственная. 
Возможность  неоднозначного  преобразования  к  ТНФ,  а  также  жела-
ние сохранить в подсхемах более «близкие» взаимосвязи между атрибу-
тами  приводит  к  понятию  оптимальной  ТНФ,  содержащей  наименьшее 
число подсхем, и кроме того, в случае зависимости А 
→ В → С подсхемы 
не должны включать одновременно «несмежные» компоненты А и С. 
Получить ТНФ (не всегда оптимальную) можно с помощью модифи-
кации алгоритма Хита, применявшегося для получения второй нормаль-
ной формы. 
Суть алгоритма заключается в следующем. Пусть задана схема отно-
шения R = (U, F), А, В, C 
⊂ U, А → В → С – транзитивная зависимость (С 
состоит  из  непервичных  атрибутов),  тогда  переходим  к  декомпозиции  
ρ  = (R
1
 = (U
1
, F
1
), R
2
 = (U
2
, F
2
)), где U
1
 = U \ С, U
2
 = B 
∪ C, F
1
 и F
2
 – про-
екции F соответственно на U
1
 и U
2
. Затем, если необходимо, производит-
ся  декомпозиция  R
1
  и  R
2
  и  так  далее  до  тех  пор,  пока  все  подсхемы  не 
окажутся в ТНФ. 
Заметим, что задача проверки, находится ли схема отношения в ТНФ, 
относится  к  NP-трудным,  что  связано  с  задачей  выделения  всех  непер-
вичных  атрибутов  отношения.  В  принципе  можно  выполнять  декомпо-
зицию зависимости А 
→ В → С не проверяя, находятся первичные атри-
буты в С или нет, но это может привести к избытку подсхем, что снижает 
«качество» декомпозиции. 
П р и м е р 
Для  схемы  R = ({A
1
,  A
2
, ..., А
6
}, {А
1
,  А
2
 
→  А
3
;  А
3
 
→  А
4
;  А
4
 
→  А
5
;  
А
4
 
→  А
6
})  требуется  получить  ТНФ.  Первичные  атрибуты  {А
1
,  А
2
},  не-
первичные – {A
3
, А
4
, А
5
, А
6
}. Транзитивная зависимость: А
1
, А
2
 
→ А
3
 
→ 
А
4
. 
На первом этапе получаем: R
1
 = ({A
1
, A
2
, A
3
, А
5
, А
6
}, 
{А
1
, А
2
 
→ A
3
; А
3
 
→ А
5
; А
3
 
→ А
6
});  
R
2
 = ({A
3
, A
4
}, {A
3
 
→ A
4
}). R
2
 находится в ТНФ. 
В  R1  нежелательная  транзитивная  зависимость:  А
1
,  А
2
 
→  A
3
 
→  А
5
. 
Строим декомпозицию, получаем: 
R
11
 = ({A
l
, А
2
, А
3
, А
6
}, {А
1
, А
2
 
→ A
3
; А
3
 
→ А
6
}), 
R
12
 = ({A
3
, A
5
}, {A
3
 
→ A
5
}). R
12
 находится в ТНФ. 
В
 
R
11
 нежелательная транзитивная зависимость: A
l
, А
2
 
→ A
3
 
→ А
6
. 
Строим декомпозицию, получаем: 
R
111
 = ({А
1
, А
2
, A
3
}, {А
1
, А
2
 
→ A
3
}), R
112
=({A
3
, A
6
}, {A
3
 
→ A
6
}).  
R
111
 и R
112
 находятся в ТНФ.  
 
42

 
Имеем ТНФ исходной схемы 
ρ = (R
2
, R
12
, R
111
, R
112
). 
Следует отметить, что простота описанного метода только кажущаяся, 
основная  сложность  заключается  в  выявлении  транзитивных  зависимо-
стей, которые не обязательно «видны» по системе образующих структу-
ры функциональных зависимостей, например, в случае  
R = ({А
1
, А
2
, ..., А
5
}, {А
1
, А
2
 
→ А
3
; А
1
, А
2
 
→ А
4
; А
3
, А
4
 
→ А
5
}) 
транзитивной зависимостью является цепочка А
1
, А
2 
→ А
3
, А
4
 
→ А
5
, кото-
рая  кажется  очевидной  только  из-за  малого  количества  атрибутов.  Во 
многом процесс выявления транзитивных зависимостей облегчается гра-
фовым  представлением  схем  отношений.  Ниже  приводятся  алгоритмы 
приведения схемы отношения к ТНФ, не требующие выделения транзи-
тивных зависимостей в явном виде, но часто дающие декомпозиции, да-
лекие от оптимальных. 
Алгоритм Делобеля – Кейси.  
Пусть задана схема отношений R = (U, F). 
1. Перейти от F к элементарному функциональному базису F
*
, т. е.  к 
минимальному  покрытию,  состоящему  только  из  полных  зависимостей, 
причем  в  правой  части  каждой  зависимости  должен  находиться  только 
один атрибут. 
2.  По  каждой  зависимости  (X
i
 
→  Y
i
) 
∈  F
*
  образовать  подсхему  R
i
  =   
= (U
i 
=  X
i
 
∪ Y
i
);  если  при  этом  для  некоторых  i  и  j,  i 
≠ j, окажется, что  
U
j
 
⊆ U
i
, то R
j
 удаляется. 
3. Если хотя бы одна из полученных подсхем содержит ключ исходно-
го отношения (для этого достаточно проверить, выполняется ли хотя бы 
для одного U
i
 соотношение 
 то совокупность полученных R
),
U
F
i
=
+
i
 яв-
ляется  ТНФ  отношения  R,  иначе  добавить  к  полученной  декомпозиции 
еще одну схему, состоящую из произвольного ключа отношения R. 
Заметим, что полученная декомпозиция сохраняет также зависимости 
исходной схемы, алгоритм имеет полиномиальную оценку трудоемкости, 
поскольку здесь не выделяется множество первичных атрибутов и даже 
не проверяется, находится ли исходное отношение в ТНФ, но такие уп-
рощения естественно приводят к избытку подсхем в декомпозиции. 
П р и м е р 
Для  схемы  R = ({A
1
,  A
2
,  А
3
,  А
4
,  А
5
}, {А
1
,  А
2
 
→  A
3
;  А
3
 
→  А
4
;  
А
3
, А
4
 
→ А
5
}) получить ТНФ.  
Переходим к элементарному функциональному базису. В зависимости 
А
3
,  А
4
 
→  А
5
  атрибут  А4  избыточный,  получим  F
* 
= {А
1
,  А
2
 
→  А
3
;  
А
3
 
→ А
4
; А
З
 
→ А
5
). Строим декомпозицию 
 
43

 
ρ = ({А
1
, А
2
, А
3
}, {А
3
, А
4
}, {А
3
, А
5
}). 
Поскольку  {А
1
,  А
2
,  А
3
}
+ 
= {А
1
,  А
2
,  А
3
,  А
4
,  A
5
} = U,  значит,  U
1
  содержит 
ключ исходного отношения и 
ρ
 
является ТНФ отношения R. 
Здесь подсхемы {А
3
, А
4
} и {А
3
, А
5
} можно объединить в одну {А
3
, А
4
, 
А
5
}, но в общем случае такие объединения требуют дополнительной про-
верки, так как подсхема, полученная в результате объединения, может не 
быть в ТНФ. 
Можно модифицировать приведенный алгоритм следующим образом. 
1. Шаг 1 предыдущего алгоритма. 
2. Найти множество всех первичных атрибутов исходного отношения 
U
p
 и непервичных U \ U
p
. 
3. Просмотреть все зависимости Х 
→ Y из F
*
, если Х не является клю-
чом и Y – непервичный атрибут (если таких зависимостей в F нет, то R в 
ТНФ), строим декомпозицию U
l
 = X 
∪ Y, U
2
 = U \ Y, т. e. такие зависимо-
сти выделяются в отдельные отношения. 
В отличие от предыдущего алгоритма, здесь получается, вообще гово-
ря, меньше подсхем, но увеличивается трудоемкость за счет нахождения 
всех первичных атрибутов и декомпозиция не обязательно сохраняет за-
висимости. 

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

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