Функциональные зависимости и реляционные базы данных

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Например, транзитивную ФЗ в отношении r можно логически вывести из $$A \to B$$ и $$B \to C$$. Пусть отношение содержит два кортежа - t и s, совпадающие по атрибуту А, но не совпадающие по С. Нужно выяснить, совпадают ли кортежи t и s по атрибуту В. Если это не так, то нарушается зависимость $$А \to В$$. Если существует совпадение для В, то, поскольку по условию не совпадают компоненты по С, то будет нарушена зависимость $$В \to С$$. Таким образом, отношение удовлетворяет зависимости $$А \to С$$.

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

В примере выше мы видели, что если F содержит ФЗ из $$A \to B$$ и $$B \to C$$, то зависимость $$А \to С$$ логически следует из F.

Пример (без доказательства). Пусть $$r = ABC, F=\{A \to B, B \to C\}$$. Тогда F+ состоит из всех зависимостей $$X \to Y$$, таких, что выполняется одно из следующих условий:

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

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

Рассмотрим схему отношения R (город, адрес, почтовый_индекс). В этом случае существуют следующие нетривиальные, т.е. имеющие смысл в контексте предметной области, ФЗ город, адрес -> почтовый_индекс (полный адрес определяет почтовый индекс) и почтовый_индекс -> город (почтовый индекс определяет город, но не адрес). Легко убедиться, что оба множества атрибутов {город, адрес} и {адрес, почтовый_индекс} являются ключами отношения. Какой из них выбрать, решает проектировщик базы данных.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Эквивалентность двух множеств ФЗ F и G устанавливается следующим образом: для каждой ФЗ $$Х \to Y$$ из F проверяется ее принадлежность G+ ; для этого вычисляется Y+ ; затем проверяется вложение Z в Y+ ; если каждая зависимость F принадлежит G+, то каждая зависимость в F+ принадлежит G+ ; далее повторяем процедуру для G по отношению к 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)

Алгоритмы построения минимального покрытия

Алгоритм MINIMAZE (G)
input:		Множество ФЗ G
output:	Минимальное покрытие G

	F = NONREDUN ( G )
	Построить непустые множества Еf(X)+, состоящие из ФЗ, с левой частью, 
	эквивалентной Х. Ef(X) - подмножество Ef(X)+, отвечающее атрибуту Х.
	for any Ef(X) из Ef(X)+  do 
                    for any Y -> U из Ef(X) do
                           for any Z -> V <> Y->U из Еf(X) do
                                 if DDERIVERS ( F, Y, -> Z ) then
                                        заменить Y->U и Z->V на  Z->UV в F
	Return(F)

Примеры. Построение минимального покрытия ФЗ

Пусть F = {AB -> C, C -> A, BC -> D, ACD -> B, D -> EG, BE -> C, CG -> BD, CE -> AG}.

Расщепив правые части с помощью правила декомпозиции, получим

AB -> C, C -> A, BC -> D, ACD -> B, D -> E, D -> G, BE -> C, CG -> B, CG -> D, CE -> A, CE -> G}.

CE -> A - избыточна, так как следует из C -> A.

CG -> B - избыточна, так как следует из CG -> D, C -> A, ACD -> B.

Больше избыточных ФЗ нет.

ACD -> B может быть замещена CD -> В, так как C -> A.

Первое МП:

AB -> C, C -> A, BC -> D, CD -> B, D -> E, D -> G, BE -> C, CG -> D, CE -> G.

Построим второе МП, исключив CE -> A, CG -> D, AC -> DB:

AB -> C, C -> A, BC -> D, D -> E, D -> G, BE -> C, CG ->В, CE -> G

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

Правила вывода для MV-зависимостей:

Совместные правила вывода для F - и MV -зависимостей:

Справедливо следующее утверждение: система правил вывода F1-F3, MV1-MV3, FMV1 и FMV2 является надежной и полной.

Правила декомпозиции и объединения MV -зависимостей позволяют сформулировать следующее утверждение. Пусть U - множество атрибутов, тогда можно построить разбиение U-X на множества $$Y_1, Y_2, \dots, Y_k$$, такое, что при $$Z \subseteq U-X$$ имеет место МФЗ $$X \to\to Z$$, если только Z является объединением некоторого числа Yi. Набор множеств Y1, Y2, ..., Yk называется базисом Х F - и MV -зависимостей. Каждое Yi может состоять из одного атрибута.

Пусть D - множество F - и MV -зависимостей, тогда, так же как и для F-зависимостей, замыкание D+ множества D может быть логически выведено по аксиомам F1-F3, MV1-MV3, FMV1 и FMV2. Однако этот процесс может потребовать времени, пропорционального eL, где L - число ФЗ в D.

На практике часто требуется только знать, следует ли из D конкретная ФЗ $$X \to\to Z$$ или $$X\toZ$$. Этого достаточно, чтобы исключить избыточные ФЗ. Для того чтобы определить, имеет ли место MV -зависимость $$X \to \to Z$$, достаточно построить базис Х зависимостей и посмотреть, является ли Z - X объединением каких-либо его множеств. Для вычисления базиса зависимостей Х относительно D достаточно найти базис относительно множества МФЗ М, где М состоит из а) всех МФЗ из D и б) множества МФЗ $$X \to \to А_i, i = 1, 2, \dots, n$$ для каждой ФЗ $$X \to Y$$ в D, где $$Y = A_1, A_2, \dots, A_n$$.

Ниже приведен алгоритм вычисления базиса Х ФЗ относительно M.

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

input:   Множество MV-зависимостей М на множестве атрибутов

output:  Базис Х относительно М.

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

Литература: [3], [11], [14], [15], [20], [31], [43], [44], [45].