Файл: Тема 19. Теория проектирования реляционных баз данных.pdf
Добавлен: 20.10.2018
Просмотров: 574
Скачиваний: 5
Тема 19. Теория проектирования реляционных баз данных
Аномалии схем баз данных
При проектировании реляционных баз данных часто возникает проблема
выбора схемы отношения из нескольких вариантов. При этом некоторые схемы
оказываются предпочтительнее других, оцениваемых как худшие. Почему так
происходит?
Рассмотрим схему Поставщики (Название, Адрес, Товар, Цена). При
работе с соответствующим отношением возможны следующие проблемы:
Избыточность. Адрес поставщика повторяется для каждого товара.
Потенциальная
противоречивость
(аномалии
обновления).
Вследствие избыточности можно обновить адрес в одном кортеже и
забыть сделать это в другом. В результате некоторые поставщики
будут иметь два адреса.
Аномалии включения. В базу данных не может быть записан адрес
поставщика, если он не поставляет хотя бы один товар.
Аномалии удаления. При удалении всех товаров, поставляемых
данным поставщиком, утрачивается его адрес.
Названные проблемы исчезнут, если заменить отношение Поставщики
двумя отношениями:
Поставщик_адрес (Название, Адрес),
Поставщик_Товар_Цена (Название, Адрес, Цена).
Однако при этом возникают другие проблемы. Всем этим и занимается
теория проектирования реляционных баз данных. Центральное место в этой
теории отводится идее зависимостей данных (функциональных и
многозначных).
Функциональные зависимости
Существуют два основных вида ограничений на отношения:
семантические ограничения на значения атрибутов,
функциональные и многозначные зависимости.
Примеры семантических ограничений: рост человека не должен
превышать 3-х метров, рабочий стаж не может быть больше возраста и т.д. Эти
ограничения не вызывают больших проблем при работе с БД. Наоборот,
функциональные зависимости, требующие равенства или неравенства
компонентов разных кортежей, оказывают большое влияние на проектирование
БД.
Определение. Пусть R(A
1
, A
2
,…A
n
) – схема отношения, а X и Y –
подмножества множества атрибутов схемы. Говорят, что X функционально
определяет Y (Y функционально зависит от X) (обозначается X Y), если все
кортежи отношения R с одинаковыми значениями атрибутов из X имеют
одинаковые значения атрибутов из Y.
Примером функциональной зависимости является зависимость X Y, где
X - ключевые атрибуты отношения, а Y – любое подмножество атрибутов
отношения.
Следует отметить, что функциональные зависимости являются
утверждениями обо всех отношениях с данной схемой. Из исследования
конкретного отношения нельзя сделать вывод, что в схеме имеются те или иные
зависимости. Исследование конкретного отношения, однако, позволяет сделать
вывод, что некоторые зависимости не имеют места.
Решение о наличии той или иной зависимости в БД принимается
проектировщиком и в дальнейшем поддерживается СУБД.
Примеры функциональных зависимостей.
В отношении Покупатели имеется зависимость Фамилия Адрес, Баланс;
в отношении Заказы – зависимость Фамилия, Товар Количество; в отношении
Поставщики – зависимости Название Адрес и Название, Товар Цена.
Логические следствия зависимостей
Пусть R – схема, а A, B, C – некоторые еѐ атрибуты. Пусть в R
существуют зависимости A B, B C. Тогда можно утверждать, что
зависимость A C также имеет место в R.
В общем случае, пусть F – множество функциональных зависимостей для
R и X
Y – некоторая функциональная зависимость. Говорят, что зависимость
X
Y логически следует из F, если для каждого отношения r со схемой R,
удовлетворяющего зависимостям из F, удовлетворяется также зависимость
X
Y.
Обозначим F
+
логическое замыкание F - множество функциональных
зависимостей, логически следующих из F. Если F=F
+
, то F – полное семейство
зависимостей.
Ключи
Пусть R=A
1
, A
2
,…A
n
; F - функциональные зависимости R; X A
1
, A
2
,…A
n
.
Тогда X – ключ R, если выполняются условия:
1. функциональная зависимость X
A
1
, A
2
,…A
n
принадлежит F
+
(однозначная идентификация);
2. Y X
Y
A
1
, A
2
,…A
n
F
+
(минимальность ключа).
Условие 1 означает, что ключ однозначно идентифицирует каждый
кортеж отношения; условие 2 утверждает, что никакая часть ключа сама
ключом не является.
Отношение может иметь несколько ключей, один из них принимается за
первичный ключ, другие считаются возможными ключами.
Пример.
В отношении Покупатели (Фамилия, Адрес, Баланс) ключом является
атрибут Фамилия, т.к. зависимость Фамилия Фамилия, Адрес, Баланс F
+
и
выполняется условие 2. Других ключей в отношении нет.
Аксиомы функциональных зависимостей
Аксиомы функциональных зависимостей позволяют выводить из
известных зависимостей новые зависимости.
Пусть U - множество атрибутов, F - множество функциональных
зависимостей. Имеют место следующие правила вывода:
А1. Рефлекcивность. Если Y X U, то X Y логически следует из F. Это
тривиальная зависимость: правая часть зависимости целиком содержится в ее
левой части.
А2. Пополнение. Если X Y и Z U, то XZ YZ.
А3. Транзитивность. Если X Y и Y Z, то X Z.
Указанные аксиомы полны и надежны, т.е. позволяют вывести все
зависимости из F+ и не позволяют вывести зависимости, не принадлежащие F+.
Производные правила вывода
Из аксиом А1, А2, А3 следуют производные правила вывода, которые как
и основные позволяют выводить новые зависимости.
А4. Объединение. Если X Y и X Z, то X YZ.
А5. Псевдотранзитивность. Если X Y и WY Z, то XW Z.
А6. Декомпозиция. Если X Y и Z Y, то X Z.
Правила объединения и декомпозиции дают важное следствие:
зависимость X A
1
,A
2
,…A
n
справедлива, если и только если зависимость X
A
i
справедлива для всех i = [1..n].
В качестве примера использования аксиом приведем доказательство
производных правил вывода.
А4. X Y X XY; (пополнение по X) (1)
X
Z
XY
YZ. (пополнение по Y) (2)
Следовательно, X
YZ. (транзитивность 1, 2)
А5. X Y WX WY; (пополнение по W) (3)
WY
Z. (дано) (4)
Следовательно, WX
Z. (транзитивность 3, 4)
А6. Z Y Y Z; (рефлексивность) (5)
X
Y. (дано) (6)
Следовательно, X
Z. (транзитивность 6, 5)
Введем важное понятие замыкания множества атрибутов относительно
множества функциональных зависимостей.
Пусть F – множество функциональных зависимостей на U, и пусть X U.
Тогда X
+
, замыкание X относительно F, есть множество атрибутов A таких, что
зависимость X A может быть выведена из F.
Можно показать, что зависимость X Y выводится из F, если и только
если Y X
+
. Это обстоятельство позволяет заменить проверку X Y проверкой
утверждения Y X
+
, которая выполняется намного быстрее.
Декомпозиция схем отношений
Декомпозицией схемы отношения R={A
1
,A
2
,…A
n
} называется замена ее
совокупностью ={R
1
,R
2
,…R
k
}, где каждое R
i
R и
R
i
=R.Схемы могут
пересекаться.
Декомпозиция может снять часть проблем, связанных с избыточностью.
С другой стороны, желательно, чтобы декомпозиция не приводила к потере
информации, чтобы всегда можно было бы восстановить исходное отношение
из его разложения. При этом естественно ожидать, что отношения из
разложения будут проекциями исходного отношения на схемы R
i
. В этом
случае восстановление отношения потребует соединения отношений
разложения.
Определение. Пусть R – схема отношения; {R
1
,R
2
,…R
k
} - декомпозиция
R, F - множество зависимостей. Говорят, что декомпозиция обладает
свойством соединения без потерь (сохраняет данные) относительно F, если
каждое отношение r для схемы R, удовлетворяющее F, может быть
представлено в виде:
).
(
)
(
2
)
(
1
r
k
R
r
R
r
R
r
Т.е. r является естественным соединением его проекций на все R
i
. Свойство
соединения без потерь желательно для декомпозиции.
Рассмотрим часто встречающуюся на практике декомпозицию вида
={R
1
,R
2
}. Такая декомпозиция обладает свойством соединения без потерь
относительно множества функциональных зависимостей F, если и только если
зависимости R
1
R
2
R
1
-R
2
или R
1
R
2
R
2
-R
1
принадлежат F
+
.