Введение в основы теории функциональных зависимостей.

Пусть R – реляционное (конечное) отношение с атрибутами A = (X1,...Y1,...Z1,...). X,Y Í A.

R удовлетворяет функциональной зависимости X®Y:

проекция [X,Y](R) является функциональным отношением типа X®Y, т.е. не содержит пары строк с одинаковыми значениями атрибутов X («аргумент функции»), но разными значениями атрибутов Y («значение функции»). Будем использовать также терминологию: f-зависимость, Y функционально (однозначно) зависит от X, X функционально (однозначно) определяет Y, X – посылка (детерминант) f-зависимости, Y – заключение.

Пусть F – множество f-зависимостей.

F ÷= X®Y (F влечет f-зависимость X®Y): для любого R, если R удовлетворяет каждой f-зависимости из F, то R удовлетворяет f-зависимости X®Y. F* - (соответствующее) замыкание F, т.е. множество всех f-зависимостей X®Y, таких что F влечет f-зависимость X®Y.

Аксиомы Армстронга (точнее, исчисление выводимости для f-зависимостей).

F1. Рефлексивность (аксиома): X®X

F2. Пополнение (правило вывода): X®Y

XZ®Y

F6. Псевдотранзитивность (правило вывода): X®Y YZ®W

XZ®W

Производные правила вывода (их обоснование можно получить из предыдущих):

F3. Аддитивность: X®Y X®Z

X®YZ

F4. Проективность: X®YZ

X®Y

F5. Транзитивность (~ F6 при пустом Z): X®Y Y®W

X®W

F ÷- X®Y (из F выводима f-зависимость X®Y): имеется вывод X®Y из набора зависимостей F (как аксиом) и аксиом рефлексивности по правилам вывода Армстронга.

Теорема о полноте. F ÷= X®Y Û F ÷- X®Y

Таким образом, F* - транзитивное замыкание F, построенные по отношению «влечет» и по отношению «выводимости», совпадают.

NB. Доказуемость в исчислении выводимости для f-зависимостей равносильна доказуемости в &É - фрагменте интуиционистской (конструктивной) логики высказываний.

Задача проверки (X®YÎF*) имеет вычислительную сложность по времени – O (n), где n – длина кода, представляющего (X®Y;F).

Как уже отмечалось выше, взаимосвязи между данными отражают семантику базы данных, унаследованную от предметной области. Фактически для проектировщика и администратора БД основной интерес представляют не конкретные взаимосвязи между конкретными данными конкретного текущего состояния БД, а именно зависимости между атрибутами, причем те, которые должны сохраняться, по крайней мере в периоде между реструктуризациями БД (изменениями в метаданных).

Поэтому точнее, семантику БД фиксирует именно F, множество зависимостей, которое определяется не по конкретному текущему наполнению конкретной БД, а (априорно) определяется проектировщиком БД, исходя из смысла предметной области («что, будем считать, должно сохранятся в процессе преобразований БД»).

Однако базовые зависимости F влекут свои последствия, из чего проистекает практический интерес к F* и далее к понятиям «выводимость и сложность вывода».

Может возникнуть недоумение – база данных состоит из нескольких взаимосвязанных таблиц, а все вышеприведенные определения даны применительно к одному отношению R. Поэтому напомним, что выше было оговорено, что многотабличная реляционная БД теоретически сводима к однотабличной, а практически... приведенные определения чисто технически обобщаются и на многотабличные БД.

X – возможный ключ отношения R: X является уникальным ключом (но возможно не выделенным в качестве первичного ключа). Неключевой атрибут – атрибут, не входящий в состав ни одного из возможных ключей.

R находится во второй нормальной форме: R находится в первой нормальной форме, и нет неключевых атрибутов, зависящих от части какого-либо (составного) возможного ключа.

Пусть (X,Y) – возможный ключ отношения R, но поля B1,... зависят от X (части возможного ключа), т.е. X®B1,... Тогда R = [X,B1,...](R) * [X,Y,C1,...](R), где C1,... – остальные атрибуты отношения R. Это разложение отношения R на два отношения [X,B1,...](R) и [X,Y,C1,...](R) устраняет (внутритабличную) зависимость X®B1,... от части ключа. Причем естественное соединение этих двух отношений точно совпадает с исходным отношением. Такое разложение называется декомпозицией без потерь.

ПРИМЕР.

B	X	Y	C
N группы	N зачетки	Наименование экзамена	Оценка
...	...	...	...

Для этой таблицы нетрудно привести (аналогичные ранее приведенным) примеры аномалий. Рекомендованная декомпозиция (без потерь) дает две таблицы:

B	X		X	Y	C
N группы	N зачетки		N зачетки	Наименование экзамена	Оценка
...	...		...	...	...

Z транзитивно зависит от X (в отношении R): имеется такой Y, что X®Y и Y®Z, где X¹Y¹Z и не верно: Y®X.

R находится в третьей нормальной форме: R находится во второй нормальной форме, и нет неключевых атрибутов, транзитивно зависящих от какого-либо возможного ключа.

Пусть X – возможный ключ отношения R, X®Y и Y®Z (т.е. Z транзитивно зависит от X), W – остальные атрибуты отношения R. Тогда R = [Y,Z](R) * [X,Y,W](R). Это разложение отношения R на два отношения [Y,Z](R) и [X,Y,W](R) устраняет (внутритабличную) транзитивную зависимость X®Z. Причем декомпозицией без потерь.

ПРИМЕР.

W	X	Y	Z
Сумма оценок по всем экзаменам	N зачетки	Группа	Количество экзаменов в текущей сессии
...	...	...	...

Для этой таблицы нетрудно привести (аналогичные ранее приведенным) примеры аномалий. Рекомендованная декомпозиция (без потерь) дает две таблицы:

W	X	Y		Y	Z
Сумма оценок по всем экзаменам	N зачетки	Группа		Группа	Количество экзаменов в текущей сессии
...	...	...		...	...