Лекции по теории проектирования баз данных (БД)
Пусть дано отношение R , а X , Y и Z подмножества R . Предположим,
что отношению удовлетворяет XY -> Z и X -> Y . Согласно аксиоме
псевдотранзитивности получим XX -> Z или X -> Z.
Если даны аксиомы рефлексивности, пополнения и псевдотранзитивности,
то из них можно вывести все остальные. Иногда их называют аксиомами
Армстронга.
Пусть F-множество F-зависимостей для отношения R . Замыкание F ,
обозначаемое F+ , - это наименьшее содержащее F множество, такое что при
применении к нему аксиом Армстронга нельзя получить ни одной F -
зависимости, не принадлежащей F.
Пример.
Пусть F = {AB -> C, C -> B } - множество F-зависимостей на R(ABC). F+
= {A -> A, AB -> A, AC -> A, ABC -> A, B -> B, AB -> B, BC -> B, ABC ->
B, C -> C, AC -> C, BC -> C, ABC -> C, AB -> AB, ABC -> AB, AC -> AC, ABC
-> AC, BC -> BC, ABC -> BC, ABC -> ABC, AB -> C, AB -> AC, AB -> BC, AB
-> ABC, C -> B, C -> BC, AC -> B, AC -> AB}
Таким образом, если известно множество F-зависимостей удовлетворяющих
отношению R, можно найти все F- зависимости, удовлетворяющие этому
отношению. Говорят, что F = X -> Y ,если X -> Y [pic] F+ .
Лекция 3
Получение замыкания F+ не обязательно для установления F = X ->
Y.
Для этого достаточно воспользоваться алгоритмом MEMBER .
Алгоритм MEMBER.
Вход: Множество F-зависимостей F и F-зависимость X -> Y.
Выход: истина, если F = F = X -> Y, ложь в противном случае.
MEMBER(F, X -> Y)
begin
if Y [pic] CLOSURE(X,F) then return (истина)
else return(ложь)
end
Здесь CLOSURE алгоритм, позволяющий выявить список атрибутов входящих
в множество F, который имеет вид.
Алгоритм CLOSURE.
Вход: Множество атрибутов Х и множество F-зависимостей F.
Выход: Замыкание Х над F.
CLOSURE(X,F)
begin
OLDDEP = 0; NEWDEP = X
while NEWDEP [pic] OLDDEP do begin
OLDDEP = NEWDEP
for каждая F- зависимость W -> Z в F do
if NEWDEP [pic] W then
NEWDEP = NEWDEP [pic] Z
end
return(NEWDEP)
end
Пример работы алгоритма MEMBER
Пусть F = {НОМЕР_РЕЙСА ДАТА_ВЫЛЕТА -> КОЛИЧЕСТВО_МЕСТ,
НОМЕР_РЕЙСА -> ПУНКТ_ОТПРАВЛЕНИЯ, НОМЕР_РЕЙСА ДАТА_ВЫЛЕТА -> ПИЛОТ} и
необходимо установить F |= НОМЕР_РЕЙСА -> ПИЛОТ
Используем для этого алгоритм MEMBER
Покрытия функциональных зависимостей
Для формирования БД, как системы взаимосвязанных отношений на
основании известных (из семантических соображений) F-зависимостей
необходимо иметь способ минимизации первоначального множества F-
зависимостей. Это необходимо для минимизации дублирования данных,
обеспечения их согласованности и целостности. Теоретической основой для
построения такого способа является теория покрытий функциональных
зависимостей.
Определение.
Два множества F-зависимостей F и G над отношением R эквивалентны,
[pic] , если F+ = G+ . Если [pic], то F есть покрытие для G.
Предполагается, что имеет смысл рассматривать в качестве покрытий такие
множества F, которые не превосходят множество G по числу F-зависимостей.
Из этого определения следует, что для установления факта, что
множество функциональных зависимостей F является покрытием G , необходимо
определить эквивалентность F и G. Практически это достигается путем
использования следующего алгоритма:
Алгоритм EQUIV
Вход: два множества F- зависимостей F и G.
Выход: истина, если [pic]; ложь в противном случае.
EQUIV(F,G)
begin
v=DERIVES(F,G) and DERIVES(G,F);
return(v)
end
Здесь DERIVES алгоритм проверяет условие F |= G и имеет вид:
Алгоритм DERIVES
Вход: два множества F- зависимостей F и G.
Выход: истина, если F |= G; ложь в противном случае.
DERIVES(F,G)
begin
v= истина
for каждая F-зависимость X -> Y из G do
v = v and MEMBER(F, X -> Y)
end
return(v)
end
Множество F-зависимостей F не избыточно, если у него нет такого
собственного подмножества F’ , что F’[pic]F . Если такое множество F’
существует, то F избыточно. F является не избыточным покрытием G, если F
есть покрытие G и F не избыточно.
Пример. Пусть G = { AB -> C, A -> B, B -> C, A -> C}. Множество F=
{AB -> C, A -> B, B -> C} эквивалентно G, но избыточно, потому что F’ =
{A -> B, B -> C} также является покрытием G. Множество F’ представляет
собой не избыточное покрытие G.
Действительно, согласно алгоритму EQUIV [pic] , так как DERIVES(F,G)
дает истину и DERIVES(G,F) так же истина. То же самое можно сказать
относительно F’ и G.
(Подробнее)
Множество F не избыточно, если в нем не существует F-зависимости X ->
Y, такой, что F - { X -> Y} |= X -> Y . Назовем F-зависимость из F
избыточной в F , если F - { X -> Y} |= X -> Y.
Для любого множества F-зависимостей G существует некоторое
подмножество F, такое, что F является не избыточным покрытием G. Если G
не избыточно, то F=G. Для определения не избыточного покрытия множества F-
зависимостей G существует алгоритм NONREDUN, который имеет вид:
Вход: множество F-зависимостей G.
Выход: не избыточное покрытие G.
NONREDUN(G)
begin
F=G
for каждая зависимость X -> Y из G do
if MEMBER(F-{X->Y],X->Y) then F=F-{X->Y}
end
return(F)
end
Пример: Пусть G= {A -> B, B -> A, B -> C, A -> C}.
Результатом работы алгоритма является множество:
{A -> B, B -> A, A -> C}.
Если бы G было представлено в порядке {A -> B, A -> C, B -> A , B ->
C} , то результатом работы алгоритма было бы
{A -> B, B -> A, B -> C}.
Из примера видно, что множество F-зависимостей G может иметь более
одного неизбыточного покрытия. Могут так же существовать неизбыточные
покрытия G, не содержащиеся в G. В приведенном примере таким неизбыточным
покрытием будет множество
F = {A -> B, B -> A, AB -> C}.
Если F-неизбыточное множество F-зависимостей, то в нем нет “лишних”
зависимостей в том смысле, что нельзя уменьшить F , удалив некоторые из
них. Удаление любой F-зависимости из F приведет к множеству, не
эквивалентному F. Однако размер можно уменьшить, удалив некоторые
атрибуты F-зависимостей F.
Определение. Пусть F-множество F-зависимостей над R и X -> Y есть F-
зависимость из F. Атрибут А из R называется посторонним в X -> Y
относительно F, если
1. [pic] и (F - {X -> Y}) [pic] {Z -> Y}[pic]F или
1. Y = AW, Y[pic]W и (F - {X -> Y}) [pic] {X -> W}[pic]F.
Иными словами, А - посторонний атрибут, если он может быть удален из
правой или левой части X -> Y без изменения замыкания F.
Пример. Пусть G = {A -> BC,B -> C,AB -> D}. Атрибут С является
посторонним в правой части A -> BC, а атрибут B - в левой части AB -> D.
Определение. Пусть F - множество F-зависимостей над R и X -> Y
принадлежит F. F-зависимость X -> Y называется редуцированной слева, если
Х не содержит постороннего атрибута А и редуцированной справа, если Y не
содержит атрибута А , постороннего для X -> y. Зависимость X -> Y
называется редуцированной, если она редуцирована слева и справа и Y
[pic]. Редуцированная слева F-зависимость называется также полной F-
зависимостью.
Определение. Множество F-зависимостей F называется редуцированным
(слева, справа), если каждая F-зависимость из F редуцирована
(соответственно слева, справа).
Пример. Множество G = {A -> BC, B -> C, AB -> D} не является
редуцированным ни справа, ни слева. Множество G1 = {A -> BC, B -> C, A ->
D} редуцировано слева, но не справа, а G2 = {A -> B, B -> C, AB -> D}
редуцировано справа, но не слева. Множество G3 = {A -> B, B -> C, A -> D}
редуцировано слева и справа, следовательно, поскольку правые части не
пусты, редуцировано.
Для нахождения редуцированных покрытий используется алгоритм:
REDUCE
Вход: множество F-зависимостей G.
Выход: редуцированное покрытие G.
REDUCE(G)
begin
F = RIGHTRED(LEFTRED(G))
удалить из F все F-зависимости вида X -> [pic]
return(F)
end
здесь RIGHTRED и LEFTRED алгоритмы редуцирования соответственно
справа и слева, которые имеют вид:
RIGHTRED
Вход: множество F-зависимостей G.
Выход: редуцированное справа покрытие G.
RIGHTRED(G)
begin
F = G
for каждая зависимость X -> Y из G do
for каждый атрибут А из Y do
if MEMBER(F - {X -> Y} [pic] {X ->(Y - A)}, X -> A) then
удалить А из Y в X -> Y из F[pic]
end
end
return(F)
end
Алгоритм LEFTRED
Вход: множество F-зависимостей G.
Выход: редуцированное слева покрытие G.
Begin
F = G
for каждая зависимость X -> Y из G do
for каждый атрибут А из Х
| |  скачать работу |
Лекции по теории проектирования баз данных (БД) |
