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

Итак, для вывода одних зависимостей из других используют аксиомы Армстронга и правила вывода функциональных зависимостей, базирующиеся на этих аксиомах [1], [6]. Рассмотрим их подробнее.

Аксиома рефлексивности. Если Y Í X Í U, где U - множество всех атрибутов, то зависимость X ® Y логически следует из F.

Например, пусть U = ABC и X = {A,B}, а Y = {A}. Тогда по аксиоме рефлексивности будет справедливой зависимость AB ® A.

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

Аксиома пополнения. Если справедлива зависимость X ® Y и Z Í U, то также будет справедливой и зависимость X Z ® Y Z, т.е. левая и правая части зависимости могут быть пополнены одинаковым набором атрибутов (в данном случае Z).

Например, если для заданного множества атрибутов U = ABCD справедлива зависимость A ® B, то будут справедливы также и зависимости A C ® B C, A D ® B D, A CD ® B CD, A A ® B A и так далее.

Аксиома транзитивности. Если справедливы зависимости X ® Y и Y ® Z, то также справедлива и зависимость X ® Z.

Аксиома коммутативности. Из справедливости зависимости XY® Z следует справедливость зависимости YX ® Z.

Аксиома-свертка. Зависимость XX ® Y может быть заменена зависимостью
X ® Y.

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

Правило объединения. Пусть заданы U, F и X,Y,Z Ì U. Если справедливы зависимости X ® Y и X ® Z, то также будет справедливой и зависимость X ® YZ (объединение по правым частям).

Правило псевдотранзитивности. Если справедливы зависимости X ® Y и WY ® Z, то будет справедливой и зависимость XW ® Z, где X, Y, W Ì U.

Правило декомпозиции (разложения). Если справедлива зависимость X ® Y и Z Í Y, то будет также справедливой и зависимость X ® Z (декомпозиция правой части). Например, если для некоторого набора атрибутов U = ABCD справедлива зависимость A ® BCD, то будут справедливы и зависимости A ® B, A ® C, A ® D, A ® BC, A ® BD, A ® CD.

Пример 13. Для приведенного ниже экземпляра отношения R справедливо следующее множество функциональных зависимостей: F = {A ® B, A ® C}.

r(R) = A B C D Попробуем из полученного множества F

a b c d логически вывести зависимости:

m b k b

a b c s AB ® B (¨), AC ® B, AD ® B, ABC ® B(¨),

e f k l ABD ® B(¨),ACD ® B, ABCD ® B(¨),

m b k d AB ® C,...

z b k l Зависимости, отмеченные символом (¨), являют-

ся тривиальными и могут быть получены по аксиоме рефлексивности.

Зависимость AC ® B выводится следующим образом. Из зависимости (A ® B) Î F по аксиоме пополнения следует зависимость AC® BC (левую и правую части зависимости A ® B пополнили атрибутом С), из которой по правилу декомпозиции получаем зависимость AC ® B. Аналогично можно вывести зависимости AD ® B, ACD ® B и другие зависимости.

Легко заметить, что если зависимость (A ® B) Î F и U = ABCDE..., то из этой зависимости выводимы все нетривиальные зависимости вида AC ® B, ACD ® B, ACDE ® B,..., т.е. левую часть любой зависимости из F можно пополнять любым количеством любых атрибутов из множества U.

Построение множества функциональных зависимостей F - один из самых ответственных процессов, который выполняется проектировщиком базы данных на основе анализа семантики данных. Этот процесс не поддается полной формализации, а потому является “слабым” звеном проектирования. С другой стороны, его результаты используются как исходные данные на последующих, полностью формализованных этапах проектирования. Поэтому построение F следует выполнять особенно тщательно, многократно перепроверяя результат.

При построении множества F нужно стремиться к уменьшению количества зависимостей в нем. Одна из причин этого состоит в том, что функциональные зависимости являются ограничением целостности для отношений [5] базы данных. Это означает, что каждая зависимость должна выполняться всегда при любых экземплярах отношений, что накладывает определенные ограничения на все допустимые значения атрибутов, и при каждом обновлении данных все зависимости должны быть проверены. Очевидным способом сокращения размера множества F является исключение тривиальных зависимостей, то есть таких зависимостей, которые не могут не выполняться, например {PN, DN} ® PN, а также зависимостей, выводимых из некоторого “базисного” набора зависимостей.

Заметим, что при построении множества функциональных зависимостей подчас и не нужно стремиться к нахождению только “базисных” зависимостей. Множество F может содержать и больше зависимостей, поскольку существуют формальные процедуры для уменьшения количества зависимостей в F путем удаления “лишних”, т.е. выводимых из оставшихся, зависимостей. Некоторые из таких процедур будут описаны в разделах 1.7 и 2.2.

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

Пример 14 [6]. Пусть схемой базы данных является график вылета самолетов из аэропорта, задаваемый в виде отношения со схемой ГРАФИК (ПИЛОТ, РЕЙС, ДАТА_ВЫЛЕТА, ВРЕМЯ_ВЫЛЕТА).

Для предварительного анализа семантики атрибутов можно указать экземпляр этого отношения, например:

r (ГРАФИК) = ПИЛОТ, РЕЙС, ДАТА, ВРЕМЯ Поскольку анализ семантики

Иванов 83 10.08 10:15 данных следует проводить на

Петров 281 10.08 15:30 всех возможных экземплярах

Иванов 301 10.08 18:10 отношения, то следует попы-

Петров 83 11.08 10:15 таться экстраполировать наши

представления о семантике

данных, полученных из одного экземпляра, на другие экземпляры схемы. Иногда для этого полезно построить абстрактный экземпляр схемы, из которого была бы понятна семантика данных, например для рассматриваемого примера такой:

ПИЛОТ, РЕЙС, ДАТА, ВРЕМЯ Первый кортеж абстpактного экземпляра

p1 r1 d1 v1 пишем произвольно, например, (p1, r1, d1, v1).

p1 r2 d1 v2 Второй и далее - со смыслом, рассуждая при-

p1 r1 d2 v1 мрно следующим образом. Если возможен

p1 r2 d2 v2 кортеж для того же пилота, то во втором кор-

p2 r1 d3 v1 теже пишем также p1. Пилот p1 не может в

p2 r2 d3 v2 один день выполнить еще раз тот же рейс при

условии, что каждый рейс отправляется в любой день в одно и то же время. Поэтому во втором кортеже пишем другой номер рейса, например, r2. Пилот p1 может выполнить другой рейс в тот же день. Поэтому пишем дату также d1. Время этого рейса должно быть отличным от v1 приусловии, что в одно и то же время может отправляться не более одного рейса. Поэтому напишем другое время отправления рейса, например, v2. Продолжаем этот процесс дальше, пока не будет полностью ясна семантика данных. Теперь будем строить множество F из полученного абстрактного экземпляра формально, используя определение функциональной зависимости атрибутов, которое было дано в разделе 1.3.1. Будем строить только нетривиальные функциональные зависимости с одиночным атрибутом в правых частях, поскольку этого легко добиться, используя правило декомпозиции правых частей зависимостей. В левых частях зависимостей может быть несколько атрибутов (один, два,..., n - 1, где n -количество атрибутов схемы базы данных). Общее количество различных левых частей - m, где

_{n -1}

m = å Cⁱ_n. Для рассматриваемого примера n = 4 и m = 14.

^{i = 1}

Шаг 1. Перечислим все возможные зависимости с одиночным атрибутом в левой части:

ПИЛОТ ® РЕЙС РЕЙС ® ПИЛОТ ДАТА ® ПИЛОТ ВРЕМЯ ® ПИЛОТ

ПИЛОТ ® ДАТА РЕЙС ® ДАТА ДАТА ® РЕЙС ВРЕМЯ ® РЕЙС Å

ПИЛОТ ® ВРЕМЯ РЕЙС ® ВРЕМЯ Å ДАТА ® ВРЕМЯ ВРЕМЯ ® ДАТА

Воспользовавшись определением функциональных зависимостей атрибутов, найдем зависимости, справедливые на абстрактном экземпляре. Отметим их символом Å и будем считать эти зависимости первым “базисным” набором, который должен быть включен в конструируемое множество F. Не отмеченные зависимости на абстрактном экземпляре не выполняются.

Таким образом получен первый “базисный” набор из двух зависимостей:

{РЕЙС ® ВРЕМЯ, ВРЕМЯ ® РЕЙС}

Шаг 2. Перечислим все возможные зависимости с двумя атрибутами в левых частях:

ПИЛОТ, РЕЙС ® ДАТА РЕЙС, ДАТА ® ПИЛОТ Å

ПИЛОТ, РЕЙС ® ВРЕМЯ ¨ РЕЙС, ДАТА ® ВРЕМЯ ¨

ПИЛОТ, ДАТА ® РЕЙС РЕЙС, ВРЕМЯ ® ПИЛОТ

ПИЛОТ, ДАТА ® ВРЕМЯ РЕЙС, ВРЕМЯ ® ДАТА

ПИЛОТ, ВРЕМЯ ® РЕЙС ¨ ДАТА, ВРЕМЯ ® ПИЛОТ Å

ПИЛОТ, ВРЕМЯ ® ДАТА ДАТА, ВРЕМЯ ® РЕЙС ¨

Отмеченные зависимости выполняются на абстрактном экземпляре. Однако, зависимости, отмеченные символом “¨”, логически выводимы из зависимостей, полученных на шаге 1. Поэтому их можно не включать в конструируемое множество F. Например, зависимость (ПИЛОТ, РЕЙС) ® ВРЕМЯ выводится из зависимости РЕЙС ® ВРЕМЯ следующим образом:

– следуя аксиоме пополнения, пополним обе части зависимости РЕЙС® ВРЕМЯ атрибутом ПИЛОТ. Получим зависимость (ПИЛОТ, РЕЙС) ® (ПИЛОТ, ВРЕМЯ);

– по правилу декомпозиции правой части эта зависимость может быть заменена двумя зависимостями:

тривиальной зависимостью (ПИЛОТ, РЕЙС) ® ПИЛОТ и зависимостью (ПИЛОТ, РЕЙС) ® ВРЕМЯ.

Аналогично выводится из той же зависимости РЕЙС ® ВРЕМЯ и зависимость (РЕЙС, ДАТА) ® ВРЕМЯ.

Зависимости (ПИЛОТ, ВРЕМЯ) ® РЕЙС и (ДАТА, ВРЕМЯ) ® РЕЙС выводятся из зависимости ВРЕМЯ ® РЕЙС также по аксиоме пополнения и правилу декомпозиции.

Зависимости, отмеченные символом Å, не выводятся из зависимостей, полученных на шаге 1, а потому они должны быть добавлены к первому “базисному” набору. В результате получим “базисный” набор уже из четырех зависимостей:

{РЕЙС ® ВРЕМЯ, ВРЕМЯ ® РЕЙС, (РЕЙС, ДАТА) ® ПИЛОТ, (ДАТА, ВРЕМЯ) ® ПИЛОТ}

Шаг 3. Перечислим все возможные зависимости с тремя атрибутами в левых частях:

ПИЛОТ, РЕЙС, ДАТА ® ВРЕМЯ ¨ ПИЛОТ, ДАТА, ВРЕМЯ ® РЕЙС ¨

ПИЛОТ, РЕЙС, ВРЕМЯ ® ДАТА РЕЙС, ДАТА, ВРЕМЯ ® ПИЛОТ ¨

Отмеченные зависимости выполняются на абстрактном экземпляре. Легко видеть, что зависимость (ПИЛОТ, РЕЙС, ДАТА) ® ВРЕМЯ выводима из зависимости РЕЙС ® ВРЕМЯ, зависимость (ПИЛОТ, ДАТА ВРЕМЯ) ® РЕЙС – из зависимости ВРЕМЯ ® РЕЙС, а зависимость (РЕЙС, ДАТА, ВРЕМЯ) ® ПИЛОТ – из зависимости (ДАТА, ВРЕМЯ) ® ПИЛОТ.

Итак, на шаге 3 не удается пополнить “базисный” набор зависимостей, а потому результирующее множество зависимостей можно записать в виде:

F = {РЕЙС® ВРЕМЯ, ВРЕМЯ ® РЕЙС, (РЕЙС, ДАТА) ® ПИЛОТ, (ДАТА, ВРЕМЯ) ® ПИЛОТ }

Еще раз проанализируем полученное множество зависимостей. Оказывается, что зависимость (ДАТА, ВРЕМЯ) ® ПИЛОТ также выводима из остальных зависимостей множества F следующим образом.

Пополним зависимость ВРЕМЯ ® РЕЙС атрибутом ДАТА. Получим зависимость (ДАТА, ВРЕМЯ) ® (РЕЙС, ДАТА). Тогда зависимость (ДАТА, ВРЕМЯ) ® ПИЛОТ транзитивно выводима из зависимостей

(ДАТА, ВРЕМЯ) ® (РЕЙС, ДАТА)

(РЕЙС, ДАТА) ® ПИЛОТ

Только что полученная зависимость также просто выводится из остальных зависимостей, как и предыдущие зависимости. Но так бывает не всегда. Иногда не удается сразу найти простой вывод для какой-нибудь зависимости. В этом случае хотелось бы не мучить себя поиском процедуры вывода, а решить вопрос принципиально о возможности вывода одной зависимости из других зависимостей. Другими словами полезно уметь устанавливать факт выводимости одной зависимости из других. Если факт выводимости какой-либо зависимости будет установлен (теорема 1 из раздела 1.4), тогда можно ее не выводить, а просто удалить, как “лишнюю”, из множества F.

Итак, для рассматриваемого примера окончательно имеем:

F = {РЕЙС ® ВРЕМЯ, ВРЕМЯ ® РЕЙС, (РЕЙС, ДАТА) ® ПИЛОТ}

Заметим, что при построении множества функциональных зависимостей подчас и не нужно стремиться к нахождению только “базисных” зависимостей. Множество F может содержать и больше зависимостей, поскольку существуют формальные процедуры для уменьшения количества зависимостей в F путем удаления “лишних”, т.е. выводимых из оставшихся, зависимостей. Некоторые из таких процедур будут описаны ниже.

В только что рассмотренном примере для построения множества F используется полный перебор возможных вариантов. Однако перебора можно избежать, если использовать комбинированный метод проектирования, который подробно будет рассмотрен в разделе 2.5.

Для выявления “лишних” зависимостей потребуется научиться вычислять замыкание атрибутов.