МД и СУБД(Л6)

1.

МД и СУБД
Pассмотрим схему отношения:
Изготовители = (назв_изгот, адрес_изгот, изделие, колич_за_год, цена)
Эта схема имеет ряд недостатков, указанных ниже.
• Избыточность. Адрес изготовителя повторяется для каждого изготовляемого изделия.
• Потенциальная противоречивость (аномалии обновления). Вследствие избыточности
возможно обновление адреса изготовителя в одном кортеже, оставляя его неизменным
в другом, то есть, возможна ситуация, когда база данных содержит различные адреса
для одного изготовителя.
• Аномалии включения. В базу данных не может быть записан адрес изготовителя, если
не известно, какие изделия и в каком количестве он изготовляет.
• Аномалии удаления. Обратная проблема появляется при необходимости удаления всех
изделий, изготавливаемых определенным изготовителем, вследствие чего мы теряем его
адрес, что не всегда желательно.
В этом примере все перечисленные недостатки исчезают, если заменить исходное
отношение двумя отношениями:
Изг_адр = (назв_изгот, адрес_изгот)
Изг__изд = (назв_изгот, изделие, колич_за_год, цена)
Однако приведенная декомпозиция имеет существенный недостаток, чтобы получить
адреса изготовителей требуется выполнить операцию естественного соединения, которая
работает сравнительно медленно, тем не менее, приведенная декомпозиция явно
предпочтительнее исходной схемы отношения.

2.

МД и СУБД
Метод нормализации отношений.
Нормализация отношений – пошаговый процесс разложения (декомпозиции) исходных
отношений базы данных на более простые. Каждая ступень этого процесса приводит схему
отношений базы данных в последовательные нормальные формы. Каждая следующая
нормальная форма обладает «лучшими» свойствами, чем предыдущая. Каждой
нормальной форме соответствует некоторый набор ограничений. Отношение находится в
определенной нормальной форме, если оно удовлетворяет набору ограничений этой
формы.
Функциональные зависимости и их свойства.
Пусть R=(U) – схема отношения, U={Al, A2, ..., Аn} – множество атрибутов, X, Y U. Говорят,
что Х функционально определяет Y или, что Y функционально зависит от X, и обозначают это
Х—>Y, если в любом отношении R, являющемся текущим значением схемы R, не могут
содержаться два кортежа, компоненты которых совпадают по всем атрибутам,
принадлежащим множеству X, но не совпадают хотя по одному атрибуту, принадлежащему
множеству Y.
Функциональные зависимости являются утверждениями обо всех отношениях, которые
могут быть значениями схемы R, то есть функциональная зависимость это свойство схемы, а
не конкретного экземпляра отношения.

3.

МД и СУБД
Пусть задано множество атрибутов U={А1, А2, ..., Аn} и некоторое множество
функциональных зависимостей F, записанных в виде пар подмножеств (X, Y), X, Y U, таких,
что X—>Y; соответствующую схему отношения будем записывать в виде R=(U, F). Говорят,
что зависимость A—>B логически следует из F, если для каждого экземпляра отношения R
со схемой R, удовлетворяющего зависимостям F, удовлетворяется также зависимость A—>B.
Например, легко показать, что если X—>Y и Y—>Z, то X >Z.
Пусть F+ обозначает замыкание F, то есть множество всех функциональных зависимостей,
которые логически следуют из F (включая, естественно, само F); F при этом называют
системой образующих структуры функциональных зависимостей. Если F+=F, то F называют
замкнутым множеством зависимостей. Теперь рассмотрим задачу поиска зависимостей
логически следующих из заданного набора F.
Аксиомамы Армстронга.:
а1) если X Y, то X—>Y (рефлексивность);
а2) если X >Y и W Z, то X W >Y Z (продолжение);
аЗ) если X—>Y и Y—>Z, то X—> Z (транзитивность).
Легко видеть, что аксиомы а2) и аЗ) могут быть объединены в одну аксиому:
а4) если X—>Y и Y W—> Z, то X W—>Z (псевдотранзитивность).
Полезны также следующие свойства, вытекающие из а1)-а3):
а5) если X—>Y и X >Z, то X—>Y Z (аддитивность);
а6) если X >Y и Z Y, то X—>Z (декомпозиция).

4.

МД и СУБД
Пусть F- множество функциональных зависимостей над схемой R. Обозначим через FА
множество всех зависимостей, выводимых из зависимостей F с использованием только
аксиом Армстронга а1)-а3).
Система аксиом называется полной, если для любого множества зависимостей F
выполняется FА F+. Система аксиом называется надёжной, если F+ FА.
Теорема полноты. Аксиомы Армстронга являются надежными и полными.
Иными словами, если зависимость X—>Y выведена из F по этим аксиомам, то она
выполняется в любом отношении, в котором выполняются все зависимости из F, и
наоборот, если некоторая зависимость X >Y не выводится из F по аксиомам Армстронга,
то можно построить экземпляр отношения, для которого выполняются все зависимости из F
и не выполняется зависимость X—>Y.
Доказательство. Надёжность аксиом Армстронга очевидна. Докажем полноту от противного.
Предположим, что существует зависимость X >Y, являющаяся логическим следствием F, но
не выводимая из F. Заметим, что если из F выводимы зависимости X —> Y, X —> Z, то по
правилу аддитивности выводима зависимость X —> YZ. Поэтому, найдется некоторое
максимальное множество V такое, что X —> V выводимо из F, и для любого Z, такого что
выполняется зависимость X —> Z, получим Z V. В силу предположения, Y не содержится в V.
Определим некоторое отношение R, содержащее два кортежа

5.

МД СУБД
A1 . . . An
R= | a1 . . . an |
| b 1 . . . bn |
где
bi=ai при Ai принадлежащем V и bi≠ai при Ai не принадлежащем V.
Тогда зависимость X >Y не выполняется на отношении R.
Однако все зависимости из F выполняются для R.

6.

МД и СУБД
Аксиомы Армстронга можно рассматривать как правила вывода, позволяющие выводить
функциональные зависимости, логически следующие из заданного набора зависимостей.
Аксиомы Армстронга являются надежными и полными, иными словами, если зависимость
X—>Y выведена из F по этим аксиомам, то она выполняется в любом отношении, в котором
выполняются все зависимости из F, и наоборот, если некоторая зависимость X >Y не
выводится из F по аксиомам Армстронга, то можно построить экземпляр отношения, для
которого выполняются все зависимости из F и не выполняется зависимость X—>Y.
Пусть задана схема отношения R=(U, F), X U, замыканием множества атрибутов Х
относительно набора зависимостей F называется множество всех таких атрибутов Ai U, что
зависимость X—>Ai выводится из F по аксиомам Армстронга; замыкание Х обозначают Х+.
Таким образом, Х+ – максимальное по включению подмножество множества U,
функционально зависимое от Х при заданном наборе функциональных зависимостей F.
Ясно, что зависимость (X—>Y) F, тогда и только тогда, когда Х+ Y.
Отметим следующие свойства замыканий:
1) X+ X;
2) X Y X+ Y+;
3) (X+)+=X+.
Аналогичные свойства имеют и замыкания наборов функциональных зависимостей.
Вычисление F+ довольно трудоемкая задача, поскольку F+ может быть довольно большим,
даже если F мало, и может содержать порядка 2n элементов, где n – количество атрибутов в
отношении.

7.

МД и СУБД
Пусть задана схема 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={A1, A2, …, А7},
F={А1,А4—>А2; А2—>A3; АЗ—>А4; А4,А7 >А5; А5 >А6; А6—>А7}, множество Х={АЗ, А5}.
Требуется вычислить Х+.
Выпишем последовательность действий для каждого этапа.
Х(0) = (АЗ, А5);
X(1)= {А4, А6}, Х(1)= {АЗ, А4, А5, А6};
Х(2)={А7}, Х(2)={АЗ, А4, A5, А6, А7};
X(3)= , следовательно, Х+= Х(2)={АЗ, А4, А5, А6, А7}.