Основы проектирования реляционных баз данных

         

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


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

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

Математически эту задачу можно поставить следующим образом. Пусть U {A1, A2, ..., An} - универсальное множество атрибутов, т.е. полный набор атрибутов отношения базы данных. Совокупность пар (X, Y), таких, что

, задает структуру ФЗ отношения R. Такое отношение называют еще универсальным отношением. Задача состоит в построении такого набора ФЗ, из которого могут быть получены все ФЗ базы данных.

Например, транзитивную ФЗ в отношении r можно логически вывести из

и
. Пусть отношение содержит два кортежа - t и s, совпадающие по атрибуту А, но не совпадающие по С. Нужно выяснить, совпадают ли кортежи t и s по атрибуту В. Если это не так, то нарушается зависимость
. Если существует совпадение для В, то, поскольку по условию не совпадают компоненты по С, то будет нарушена зависимость
. Таким образом, отношение удовлетворяет зависимости
.

Такие рассуждения позволяют ввести следующие определения.

Определение 7. Пусть F - множество ФЗ для схемы отношения r,

- некоторая ФЗ. Говорят, что ФЗ
логически следует из F, если для каждого отношения R со схемой r, удовлетворяющего ФЗ из F, удовлетворяется также зависимость
.


В примере выше мы видели, что если F содержит ФЗ из
и
, то зависимость
логически следует из F.

Определение 8. Пусть F - множество ФЗ для схемы отношения r. Тогда замыканием F+ множества ФЗ F называется множество ФЗ, которое логически следует из F. F называется полным семейством ФЗ, если F+ = F.

Пример (без доказательства). Пусть
. Тогда F+ состоит из всех зависимостей
, таких, что выполняется одно из следующих условий:

X содержит A, т.е.
или
;X содержит B, но не A, и Y не содержит A, т.е.
или B;
есть
или
.

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

Определение 9. Пусть F - множество ФЗ для схемы отношения R(A1, A2, ..., An). Подмножество атрибутов X называется ключом отношения R, если ФЗ:
принадлежит F+ и не для какого собственного подмножества
ФЗ:
не принадлежит F+.

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

Пример. Многозначность при выборе ключа



Легко убедиться, что оба множества атрибутов {город, адрес} и {адрес, почтовый_индекс} являются ключами отношения. Какой из них выбрать, решает проектировщик базы данных.

Для того чтобы определить ключи отношений и логические следствия ФЗ для заданной схемы отношения, необходимо вычислить F+ или для заданного F уметь определять, принадлежит ли данная ФЗ его замыканию F+. Для этого необходимо иметь набор правил - операций над ФЗ, позволяющих ими манипулировать.

Набор правил вывода должен быть полным, т.е. давать возможность вывести все зависимости из F+, и надежным, т.е. не позволять вывести зависимость из F, не принадлежащую F+. Таким образом, правила вывода, называемые также аксиомами вывода функциональных зависимостей, должны позволять вывести множество функциональных зависимостей, присущих рассматриваемой схеме отношения R(A1, A2, ..., Am) на заданном универсальном множестве атрибутов U по заданному множеству ФЗ F = {F1, F2, ..., Fk}.

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

Рефлексивность. Если
, то ФЗ
следует из F. Иначе
.Пополнение. Если
и задана ФЗ
из F, то имеет место ФЗ
.Транзитивность. Если
и задана ФЗ
из F , то имеет место ФЗ
.Расширение. Если
и задана ФЗ
, то
имеет место ФЗ
.Продолжение. Если
, и задана ФЗ
, то
имеет место ФЗ
.Псевдотранзитивность. Если
, и заданы ФЗ
и ФЗ
, то имеет место ФЗ
.Аддитивность. Если
, и заданы ФЗ
и ФЗ
, то имеет место ФЗ
.Декомпозиция. Если
, и задана ФЗ
, то имеет мето ФЗ
. Пример. Определение ключа отношения с помощью правил вывода

Используя три первых аксиомы вывода, покажем, что пара атрибутов {адрес, почтовый_индекс} из примера выше являются ключом отношения (город, адрес, почтовый_индекс), иначе имеет место ФЗ адрес, почтовый_индекс
город, адрес, почтовый_индекс. Задана ФЗ: почтовый_индекс
город. Используя аксиому пополнения, пополним эту ФЗ атрибутом адрес, получаем адрес, почтовый_индекс
город, адрес. Задана ФЗ город, адрес
почтовый_индекс. Используя аксиому пополнения, пополнив эту ФЗ атрибутами город, адрес, получим город, адрес
город, адрес, почтовый_индекс.


Тогда по аксиоме транзитивности получаем адрес, почтовый_индекс
город, адрес, почтовый_индекс.

Можно доказать утверждение о том, что настоящие правила вывода позволяют по заданному множеству ФЗ F построить все зависимости, допускаемые на U. Таким образом, система правил вывода ФЗ 1-6 является надежной и полной.

Покажем, как можно доказать утверждение о полноте и надежности аксиом вывода. Аксиомы 1, 2 и 3 составляют независимое подмножество среди всех шести аксиом и называются аксиомами Армстронга. Из них можно вывести все остальные аксиомы. Поэтому надежность и полноту достаточно установить только для первых трех аксиом.

Надежность аксиом заключается в том, что если ФЗ
выведена из F с помощью этих аксиом, то она справедлива на любом отношении, на котором справедливы ФЗ из F. Аксиома рефлексивности является надежной, так как нельзя иметь отношение R с двумя кортежами, которые совпадают по Х, но не совпадают по некоторому его подмножеству. Для доказательства аксиомы пополнения предположим, что имеется отношение R и справедлива ФЗ
на R. Однако есть два кортежа t и s, которые совпадают по атрибутам XZ, но не совпадают по YZ. Поскольку они не могут совпадать по какому-либо атрибуту из Z, то они не должны совпадать по некоторому атрибуту из Y. Тогда они совпадают по X, но не совпадают по Y, что противоречит существованию ФЗ
. Надежность аксиомы транзитивности уже была доказана в настоящем учебном элементе ранее.

Для доказательства полноты аксиом вывода введем понятие замыкания множества атрибутов X относительно множества ФЗ F.

Определение 10. Пусть F - множество ФЗ на множестве атрибутов U и
. Тогда замыканием X+ множества ФЗ F называется множество атрибутов А, таких, что ФЗ
может быть выведена из F по аксиомам 1-3.

Нетрудно показать, что ФЗ
следует из аксиом 1-3 тогда и только тогда, когда
. По определению замыкания для каждого атрибута из Y выводится ФЗ
. По аксиоме объединения имеет место ФЗ
. Обратно, если выполняется ФЗ
, то по аксиоме декомпозиции имеет место ФЗ
каждый атрибут из Y, и, следовательно, имеет место
.



Теперь, для того чтобы показать полноту аксиом 1-3, покажем, что если при заданном F ФЗ
не может быть выведена из данных аксиом, то должно существовать такое отношение, в котором справедливы все ФЗ F, кроме ФЗ
.

Рассмотрим отношение R с двумя кортежами:

X+другие атрибуты
1 1 … 11 1 … 1
1 1 … 10 0 … 0


Все зависимости из F справедливы на R. Следует показать, что
не удовлетворяется на R. Допустим обратное. Из
следует
, иначе два кортежа, совпадая по Х, не совпадают по Y. Тогда ФЗ
следует из аксиом 1-3, что приводит к противоречию. Таким образом, аксиомы 1-3 полны.

На основе аксиом вывода можно уточнить понятие замыкания множества ФЗ
, как наименьшего множества, содержащего F, которое не может быть расширено за F с помощью аксиом 1, 2 и 3. Понятие замыкания является основным при доказательстве приведенного выше утверждения. Оно также важно при определении, имеет ли множество ФЗ F зависимость
. Для этого достаточно проверить, принадлежит ли рассматриваемая зависимость множеству F+.

Вычисление замыкания конечного множества ФЗ является трудоемкой задачей, так как необходимо перебрать множество всех подмножеств, а таких множеств, как известно, 2n, где n - число элементов исходного множества. Однако вычислить замыкание X+ для данного множества атрибутов несложно. Алгоритм вычисления приведен ниже. Можно показать, что этот алгоритм корректно вычисляет замыкание X+.

Алгоритм вычисления X+

Input: U - конечное множество атрибутов, множество ФЗ F на U, множество
.

Output: X+

Х0 есть Х.Xi+1 есть Xi плюс множество атрибутов А, для которых в F существует ФЗ
.

Условие завершения. Так как U - конечно и
, то существует i, такое, что Xi = Xi+1.

Пример. Вычислим Х+

Пусть
.
Находим ФЗ, которые в левой части имеют
. Присоединим E и G к X0. X1 = BDEG. Находим ФЗ с левыми частями из
. Находим ФЗ с левыми частями из
.
.


Минимальные покрытия множеств функциональных зависимостей


Попытаемся теперь выяснить, какова роль F-зависимостей в реляционных базах данных. Как показали исследования, класс F-зависимостей оказывает существенное влияние на построение согласованных схем реляционных баз данных, определяет механизмы согласованности данных и целостности баз данных.

Одной из основных целей создания базы данных является сохранение всех данных и взаимосвязей между ними из предметной области в вычислительной среде. Табличное представление отношений в реляционных базах данных позволяет выдвинуть следующую гипотезу хранения данных - каждой ФЗ по отношению. Другой целью создания базы данных является надежность и целостность сохраняемых данных. Можно предположить, что табличное представление породит ряд проблем, связанных с восстанавливаемостью данных, и вступит в противоречие с требованием производительности базы данных. Поэтому меньшее число F-зависимостей означает меньший объем использования памяти компьютера и меньшее число проверок при операциях модификации.

В начале проектирования реляционных баз данных всегда возникает задача представления множеств F-зависимостей. Чем меньшим числом отношений их можно представить, тем лучше. Формализация решения этой задачи строится на понятии покрытия ФЗ. Построение покрытий множеств ФЗ является четвертой (4) конструктивной идеей в теории проектирования реляционных баз данных. Введем ряд определений.

Определение 11. Два множества F-зависимостей F и G над схемой r отношения R эквивалентны, если их замыкания совпадают, т.е. F+ = G+.

Эквивалентность двух множеств ФЗ F и G устанавливается следующим образом: для каждой ФЗ

из F проверяется ее принадлежность G+; для этого вычисляется Y+; затем проверяется вложение Z в Y+; если каждая зависимость F принадлежит G+, то каждая зависимость в F+ принадлежит G+; далее повторяем процедуру для G по отношению к F.

Следствием введения понятия эквивалентности является следующий важный факт: каждое множество ФЗ покрывается некоторым множеством ФЗ, в которых ни одна из правых частей не имеет более одного атрибута (правила декомпозиции и объединения).
Таким образом, существует набор эквивалентных схем для каждой исходной схемы отношений реляционной базы данных.

Теория проектирования реляционных баз данных дает возможность построения более коротких представлений ФЗ. Для рассмотрения таких процедур введем понятия неизбыточных ФЗ и минимального покрытия множеств ФЗ.

Определение 12. Множество F-зависимостей F неизбыточно, если у него нет собственного подмножества, эквивалентного ему самому.

Определение 13. Множество F-зависимостей F минимально, если оно содержит не больше F-зависимостей, чем любое эквивалентное ему множество.

Минимальное покрытие (МП) не может содержать избыточных зависимостей. Понятие МП F можно детализировать следующим образом:

правая часть каждой ФЗ в F содержит один атрибут;ни для какой ФЗ

из F множество
не эквивалентно F;ни для какой ФЗ
из F и собственного подмножества
множества
не эквивалентны.

Доказано, что для каждого множества ФЗ F существует эквивалентное ему минимальное покрытие. Для заданного F может существовать несколько минимальных покрытий. Ниже приведены общие алгоритмы проверки избыточности и построения минимальных покрытий.

Алгоритмы проверки избыточности

Алгоритм REDUNDANT ( F ) input: Множество F output: True, если F избыточно 1. temp = false for any X
Y < F do if MEMBER ( F - { X
Y } , X
Y ) then temp = True Return ( temp )

Алгоритм NONREDUN ( G ) input: Множество ФЗ G output: Неизбыточное покрытие G 1. F = G for any X
Y > G do if MEMBER (F - { X
Y }, X
Y ) then F = F - { X
Y } Return (F)


Основные классы функциональных зависимостей


Анализ связей между сущностями в предметных областях позволяет выделить различные классы функциональных зависимостей.

Для определения ФЗ предметной области часто бывает недостаточно определить все возможные ключи отношения. Значения атрибутов могут зависеть от ключа по-разному. Различают классы полных и частичных ФЗ. ФЗ может быть частичной, когда значение неключевого атрибута зависит от значений некоторых атрибутов составного ключа, и полной, когда значения неключевого атрибута зависят от значений всех атрибутов составного ключа.

Введем определение.

Определение 3. Говорят, что неключевой атрибут функционально полно зависит от составного ключа, если он функционально зависит от ключа, но не находится в функциональной зависимости ни от какой части составного ключа. Если неключевой атрибут зависит от части составного ключа, то говорят о частичной ФЗ.

Пример. Частичные и полные ФЗ

ПРЕПОДАВАТЕЛЬ_ПРЕДМЕТ (Личный номер, Предмет, Фамилия, Должность, Оклад, Часы)

1.Ивановдоцент25000Математика40
2.Исаевдоцент25000Физика50
3.Фроловпрофессор50000Химия30

Первичным ключом отношения ПРЕПОДАВАТЕЛЬ_ПРЕДМЕТ является пара атрибутов Личный_номер-Предмет. Значения атрибута Количество_часов зависят от значения атрибута Предмет, т.е. имеем частичную ФЗ Предмет

Часы. Значения атрибута Фамилия зависят от значений атрибутов Личный_номер-Предмет, т.е. имеем полную функциональную зависимость {Личный_номер, Предмет}
Фамилия.

Рассмотрим проблему избыточности данных с точки зрения существования определенных функциональных зависимостей. Избыточность данных может проявляться в виде дублирования значений некоторых атрибутов. Так, например, если несколько преподавателей находятся на одной и той же должности, то их оклады могут совпадать. Атрибут Оклад частично зависит от ключа отношения, но однозначно определяется атрибутом Должность. Разделение исходного отношения на два новых отношения позволит исключить дублирование данных.

Таким образом, выявление определенных функциональных зависимостей в отношениях базы данных позволяет преобразовать их с целью исключения избыточности и повышения надежности данных.
Разбиение исходных отношений в соответствии с функциональными зависимостями - это вторая (2) конструктивная идея в теории проектирования реляционных баз данных. Формирование схем отношений путем разбиения исходных отношений по их атрибутам с учетом функциональных зависимостей является одним из способов создания хороших схем реляционных баз данных.

Каким образом можно использовать это наблюдение с учетом семантики данных для конструирования отношений? Имеет смысл разбить все возможные зависимости на определенные типы ФЗ, и на основе этой классификации проанализировать, какие типы ФЗ к каким аномалиям в выполнении реляционных операций приводят. Такой анализ может стать основой для построения алгоритмов проектирования реляционной базы данных.

Анализ связей между сущностями в предметных областях позволяет определить, наряду с частичной и полной ФЗ, еще несколько классов ФЗ. Одним из таких классов является класс транзитивных ФЗ.

Определение 4. Пусть X, Y, Z - атрибуты отношения R. Если при этом имеются ФЗ

и
, но отсутствуют ФЗ
и
, то говорят, что Z транзитивно зависит от Х. Такие ФЗ называются транзитивными (Т-зависимостями).

Пример. Транзитивные ФЗ

Личный номер преподавателя определяет его должность, т.е. имеет место ФЗ Личный_номер
Должность. С другой стороны, согласно тарификации каждой должности назначается определенный оклад, т.е. имеет место ФЗ Должность
Оклад. Каждый преподаватель получает за работу соответствующий должности оклад, т.е. оклад преподавателя определяется через его должность.

Очевидно, что семантическая связь между атрибутами отношения может носить неоднозначный характер, это порождает существование класса многозначных зависимостей (MV-зависимостей). Например, один преподаватель может преподавать несколько предметов, а один предмет может преподаваться несколькими преподавателями. Многозначная зависимость может быть следующих типов: 1:N (один ко многим), M:1 (многие к одному) и M:N (многие ко многим).

Определение 5. Пусть r - некоторая схема отношения, X и Y - подмножества атрибутов r.


Если при заданных значениях атрибутов из {X} существует некоторое множество, состоящее из нуля или более взаимосвязанных значений атрибутов из {Y}, никак не связанных со значениями других атрибутов этого отношения r - X - Y, то говорят о существовании многозначной зависимости между атрибутами X и Y:
(класс MV-зависимостей).

Формально многозначная зависимость означает, что если в отношении
имеются два кортежа t и s, такие, что их значения совпадают по атрибутам из Х, т.е. t[X] = s[X], то данное отношение содержит кортежи w и v, такие, что

w[X] = v[X] = t[X] = s[X],w[Y] = t[Y], w[r - X - Y] = s[r - X - Y],v[Y] = s[Y], v[r - X - Y] = t[r - X - Y].

Фактически многозначная зависимость означает, что значения атрибутов из Y в кортежах t и s можно поменять местами и получить два новых кортежа, также принадлежащих отношению R.

Разделение установленных функциональных зависимостей по различным отношениям может привести к нарушению принципа замкнутости реляционных операций, потере некоторых существующих кортежей или появлению мнимых кортежей. Это обстоятельство приводит к необходимости выделения еще одного класса функциональных зависимостей - класса зависимостей по соединению (J-зависимостей). Этот класс ФЗ требует от ФЗ наличия свойства восстанавливаемости по своим проекциям с помощью естественного соединения.

Пусть U - универсальное отношение, полученное объединением всех атрибутов сущностей предметной области в одно отношение.

Определение 6. Пусть r = {r_1, …, r_p} - множество схем на U. Отношение R \subset U удовлетворяет зависимости по соединению, если R разлагается без потерь на r как


Процесс выделения новых классов функциональных зависимостей может быть продолжен. Он аналогичен классификации чисел в школьном курсе алгебры: натуральные числа
целые числа
рациональные числа
действительные числа. В теории реляционных баз данных уже выделены ветвящиеся и циклические функциональные зависимости, предпринимаются попытки расширить набор реляционных операций. Введение новых классов функциональных зависимостей обусловлено следующим важным обстоятельством: при декомпозиции схем реляционных отношений могут быть потеряны как функциональные зависимости, так и кортежи (или приобретены несуществующие кортежи).Каждый класс функциональных зависимостей позволяет проанализировать механизм потери данных или функциональной зависимости и сформулировать правила, которые позволят этого избежать.

Однако для практических целей проектирования реляционных баз данных достаточно знания рассмотренных классов ФЗ. Даже зависимость по соединению встречается очень редко.


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


Оставим пока в стороне ответ на вопрос, почему проекты реляционных баз данных бывают плохими, т.е. зачем нужно проектировать реляционную базу данных. Попытаемся сначала ответить на вопросы "В чем заключается проектирование реляционных баз данных? и "Что лежит в основе процедур проектирования реляционных баз данных?"

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

На практике построение логической модели базы данных, независимо от используемой модели данных, выполняется с учетом двух основных требований: исключить избыточность и максимально повысить надежность данных. Эти требования вытекают из требования коллективного использования данных группой пользователей. Формальных средств описания данных, необходимых для проверки правильности заполнения конструкций моделей, явно недостаточно. Выбор сущностей, атрибутов и фиксация взаимосвязей между сущностями зависит от семантики предметной области и выполняется системным аналитиком субъективно в соответствии с его личным пониманием специфики прикладной задачи. Разные люди определяют и представляют данные по-разному.

Поэтому любое априорное знание об ограничениях предметной области, накладываемых на взаимосвязи между данными и значения данных, и знания об их свойствах и взаимоотношениях между ними может сыграть определенную роль в соблюдении указанных выше требований. Формализация таких априорных знаний о свойствах данных предметной области базы данных нашла свое отражение в концепции функциональной зависимости данных, т.е.
Такая ФЗ обозначается как

.

Как видно из определения, функциональная зависимость инвариантна к изменению состояний базы данных во времени.

Пример. Понятие функциональной зависимости Продемонстрируем понятие функциональной зависимости на примере графика полетов аэропорта. ГРАФИК_ПОЛЕТОВ (Пилот, Рейс, Дата_вылета, Время_вылета)
Иванов1008.0710:20
Иванов1029.0713:30
Исаев907.076:00
Исаев10011.0710:20
Исаев10310.0719:30
Петров10012.0710:20
Петров10211.0713:30
Фролов908.076:00
Фролов9012.076:00
Фролов10414.0713:30
Известно, что:

каждому рейсу соответствует определенное время вылета;для каждого пилота, даты и времени вылета возможен только один рейс;на определенный день и рейс назначается определенный пилот.

Следовательно:

"Время_вылета" функционально зависим от "Рейс": "Рейс"
"Время_{} вылета";"Рейс" функционально зависим от {"Пилот", "Дата_вылета", "Время_вылета"}: {"Пилот", "Дата_вылета", "Время_вылета"}
"Рейс";"Пилот" функционально зависим от {"Рейс", "Дата_вылета"}: {"Рейс", "Дата_вылета"}
"Пилот".

Важной задачей при выявлении функциональных зависимостей на атрибутах отношения, которое по определению является множеством, является выяснение, какой из атрибутов выступает как аргумент, а какой - как значение ФЗ. Наиболее подходящими кандидатами в аргументы ФЗ являются возможные ключи, так как кортежи представляют экземпляры сущности, которые идентифицируются значениями атрибутов своего ключа. Нестрого говоря, функциональная зависимость имеет место на отношении, когда значения кортежа на одном множестве атрибутов однозначным образом определяют значения кортежа на другом множестве атрибутов. Это рабочее определение ФЗ не содержит в себе тех формальных элементов, которые позволяют ответить на вопрос "А как проверить наличие ФЗ между атрибутами отношения?" Необходимый для этого формализм дает нам использование реляционных операций.


Для получения формального (строгого) определения н аличия ФЗ в отношении обратимся к реляционным операциям.

Определение 2. Пусть имеется отношение R со схемой r, X и Y - два подмножества R. ФЗ
имеет место на R, если множество
имеет не более одного кортежа для каждого значения х. Такая ФЗ называется также F-зависимостью.

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

Алгоритм, который проверяет, удовлетворяет ли отношение R ФЗ
, состоит в сортировке отношения по значениям возможного ключа и установления факта однозначности между его значением и значениями других атрибутов. Этот алгоритм полезен, но он носит вспомогательный характер.

Ясно, что если семантика предметной области базы данных сложна, то проверить кортежи на принадлежность к ФЗ достаточно сложно. Сложно вообще установить наличие самой функциональной зависимости, отвечающей природе рассматриваемых данных. С помощью такого формального метода можно выявить ФЗ, которые не являются реальными и носят случайный характер. Проектировщику реляционных баз данных следует знать о таком методе проверки наличия ФЗ, но при проектировании новой базы данных его применение малоэффективно. Он может быть полезен при реинжиниринге существующей базы данных.

Функциональные зависимости фактически представляют собой утверждения обо всех отношениях предметной области. Эти отношения могут являться значениями схемы r и, в сущности, не могут быть получены формальными методами. Единственный способ установления функциональных зависимостей для схемы отношения r - это исследование семантики атрибутов сущностей предметной области. Являясь высказываниями о сущностях предметной области, они не могут быть доказаны. Это обстоятельство по существу порождает неединственность представления предметной области отношениями реляционной БД.

Здесь уместно высказать гипотезу о том, почему бывают хорошие и плохие проекты баз данных.Во-первых, в силу субъективности подходов к анализу предметной области аналитики могут упустить важные ФЗ. Это может привести к тому, что, работая на множестве заведомо неэквивалентных схем, проектировщик создаст неудовлетворительный проект базы данных. Во-вторых, неединственность представления предметной области отношениями приводит к проблеме выбора из множества альтернатив. При этом схема базы данных, выбранная из набора эквивалентных схем, является правильной, но может организовывать данные для пользователя непривычным образом. В-третьих, можно определить ("накроить") схемы баз данных таким образом, что в результате операций с ФЗ будут потеряны и ФЗ, и сами данные.



ограничений на возможные взаимосвязи между данными, которые могут быть текущими значениями схемы отношений.

Кортежи отношений могут представлять экземпляры сущности предметной области или фиксировать их взаимосвязь. Но даже если эти кортежи определены правильно, т.е. отвечают схеме отношения и выбраны из допустимых доменов, не всякий из них может быть текущим значением некоторого отношения. Например, возраст человека редко бывает более 120 лет, или один и тот же пилот не может одновременно выполнять два различных рейса. Такие ограничения семантики домена практически не влияют на выбор той или иной схемы отношений. Они представляют собой ограничения на типы данных.

Априорные ограничения предметной области на взаимосвязь значений отдельных атрибутов оказывают наибольшее влияние на процесс проектирования схем реляционных баз данных. Соответствие по значению определенных атрибутов различных отношений базы данных, т.е. зависимость их значений друг от друга, определяет показатели надежности и корректности сохраняемых данных при их коллективном и согласованном использовании.

Вспомним определение функции как соответствия множества аргументов определенным значениям из множества определения функции и способы задания функций: формула, график и перечисление (таблица). Нетрудно понять, что функциональную зависимость (ФЗ) можно определить на довольно широком классе объектов. Определение функции не накладывает никаких ограничений на множество аргументов и множество значений функции, кроме их существования и наличия соответствия между их элементами. Поскольку ФЗ можно задать таблично, а таблица есть форма представления отношения, то становится очевидной связь между ФЗ и отношением. Отношение может задавать ФЗ. Это утверждение является первой (1) конструктивной идеей, которая положена в основу теории проектирования реляционных баз данных.

Определение 1. Пусть r (A1, A2, ..., An) - схема отношения R, a X и Y - подмножества r. Говорят, что Х функционально определяет Y, если каждому значению атрибутов кортежа отношения из Х соответствует не более одного значения атрибутов того же кортежа отношения из Y.


Такая ФЗ обозначается как
.

Как видно из определения, функциональная зависимость инвариантна к изменению состояний базы данных во времени.

Пример. Понятие функциональной зависимости Продемонстрируем понятие функциональной зависимости на примере графика полетов аэропорта. ГРАФИК_ПОЛЕТОВ (Пилот, Рейс, Дата_вылета, Время_вылета)
Иванов1008.0710:20
Иванов1029.0713:30
Исаев907.076:00
Исаев10011.0710:20
Исаев10310.0719:30
Петров10012.0710:20
Петров10211.0713:30
Фролов908.076:00
Фролов9012.076:00
Фролов10414.0713:30
Известно, что:

каждому рейсу соответствует определенное время вылета;для каждого пилота, даты и времени вылета возможен только один рейс;на определенный день и рейс назначается определенный пилот.

Следовательно:

"Время_вылета" функционально зависим от "Рейс": "Рейс"
"Время_{} вылета";"Рейс" функционально зависим от {"Пилот", "Дата_вылета", "Время_вылета"}: {"Пилот", "Дата_вылета", "Время_вылета"}
"Рейс";"Пилот" функционально зависим от {"Рейс", "Дата_вылета"}: {"Рейс", "Дата_вылета"}
"Пилот".

Важной задачей при выявлении функциональных зависимостей на атрибутах отношения, которое по определению является множеством, является выяснение, какой из атрибутов выступает как аргумент, а какой - как значение ФЗ. Наиболее подходящими кандидатами в аргументы ФЗ являются возможные ключи, так как кортежи представляют экземпляры сущности, которые идентифицируются значениями атрибутов своего ключа. Нестрого говоря, функциональная зависимость имеет место на отношении, когда значения кортежа на одном множестве атрибутов однозначным образом определяют значения кортежа на другом множестве атрибутов. Это рабочее определение ФЗ не содержит в себе тех формальных элементов, которые позволяют ответить на вопрос "А как проверить наличие ФЗ между атрибутами отношения?" Необходимый для этого формализм дает нам использование реляционных операций.


Для получения формального (строгого) определения н аличия ФЗ в отношении обратимся к реляционным операциям.

Определение 2. Пусть имеется отношение R со схемой r, X и Y - два подмножества R. ФЗ
имеет место на R, если множество
имеет не более одного кортежа для каждого значения х. Такая ФЗ называется также F-зависимостью.

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

Алгоритм, который проверяет, удовлетворяет ли отношение R ФЗ
, состоит в сортировке отношения по значениям возможного ключа и установления факта однозначности между его значением и значениями других атрибутов. Этот алгоритм полезен, но он носит вспомогательный характер.

Ясно, что если семантика предметной области базы данных сложна, то проверить кортежи на принадлежность к ФЗ достаточно сложно. Сложно вообще установить наличие самой функциональной зависимости, отвечающей природе рассматриваемых данных. С помощью такого формального метода можно выявить ФЗ, которые не являются реальными и носят случайный характер. Проектировщику реляционных баз данных следует знать о таком методе проверки наличия ФЗ, но при проектировании новой базы данных его применение малоэффективно. Он может быть полезен при реинжиниринге существующей базы данных.

Функциональные зависимости фактически представляют собой утверждения обо всех отношениях предметной области. Эти отношения могут являться значениями схемы r и, в сущности, не могут быть получены формальными методами. Единственный способ установления функциональных зависимостей для схемы отношения r - это исследование семантики атрибутов сущностей предметной области. Являясь высказываниями о сущностях предметной области, они не могут быть доказаны. Это обстоятельство по существу порождает неединственность представления предметной области отношениями реляционной БД.

Здесь уместно высказать гипотезу о том, почему бывают хорошие и плохие проекты баз данных.Во-первых, в силу субъективности подходов к анализу предметной области аналитики могут упустить важные ФЗ. Это может привести к тому, что, работая на множестве заведомо неэквивалентных схем, проектировщик создаст неудовлетворительный проект базы данных. Во-вторых, неединственность представления предметной области отношениями приводит к проблеме выбора из множества альтернатив. При этом схема базы данных, выбранная из набора эквивалентных схем, является правильной, но может организовывать данные для пользователя непривычным образом. В-третьих, можно определить ("накроить") схемы баз данных таким образом, что в результате операций с ФЗ будут потеряны и ФЗ, и сами данные.