Пусть 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-зависимостей).
Производные правила вывода (их обоснование можно получить из предыдущих):
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 зачетки
Группа
Количество экзаменов в текущей сессии
...
...
...
...
Для этой таблицы нетрудно привести (аналогичные ранее приведенным) примеры аномалий. Рекомендованная декомпозиция (без потерь) дает две таблицы:
Задача проверки (X®YÎF*) имеет вычислительную сложность по времени – O(n), где n – длина кода, представляющего (X®Y;F).
ПРИМЕР.
ПРИМЕР.