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

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

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

Математически эту задачу можно поставить следующим образом. Пусть U {A₁, A₂,..., A_n} - универсальное множество атрибутов, т.е. полный набор атрибутов отношения базы данных. Совокупность пар (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(A₁, A₂,..., A_n). Подмножество атрибутов X называется ключом отношения R, если ФЗ: принадлежит F⁺ и не для какого собственного подмножества ФЗ: не принадлежит F⁺.

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

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

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

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

Набор правил вывода должен быть полным, т.е. давать возможность вывести все зависимости из F⁺, и надежным, т.е. не позволять вывести зависимость из F, не принадлежащую F⁺. Таким образом, правила вывода, называемые также аксиомами вывода функциональных зависимостей, должны позволять вывести множество функциональных зависимостей, присущих рассматриваемой схеме отношения R(A₁, A₂,..., A_m) на заданном универсальном множестве атрибутов U по заданному множеству ФЗ F = {F₁, F₂,..., F_k}.

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

1. Рефлексивность. Если , то ФЗ следует из F. Иначе .
2. Пополнение. Если и задана ФЗ из F, то имеет место ФЗ .
3. Транзитивность. Если и задана ФЗ из F, то имеет место ФЗ .
4. Расширение. Если и задана ФЗ , то имеет место ФЗ .
5. Продолжение. Если , и задана ФЗ , то имеет место ФЗ .
6. Псевдотранзитивность. Если , и заданы ФЗ и ФЗ , то имеет место ФЗ .
7. Аддитивность. Если , и заданы ФЗ и ФЗ , то имеет место ФЗ .
8. Декомпозиция. Если , и задана ФЗ , то имеет мето ФЗ .

Пример. Определение ключа отношения с помощью правил вывода

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

Можно доказать утверждение о том, что настоящие правила вывода позволяют по заданному множеству ФЗ 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 … 1	1 1 … 1
1 1 … 1	0 0 … 0

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

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

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

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

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

1. Х⁰ есть Х.
2. Xⁱ⁺¹ есть Xⁱ плюс множество атрибутов А, для которых в F существует ФЗ .

Условие завершения. Так как U - конечно и , то существует i, такое, что Xⁱ = Xⁱ⁺¹.

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

Пусть .

1. 
2. Находим ФЗ, которые в левой части имеют . Присоединим E и G к X⁰. X¹ = BDEG. Находим ФЗ с левыми частями из . Находим ФЗ с левыми частями из .
3. .

Дата добавления: 2014-01-07