RAP последовательности вывода

Выводы с использованием аксиом Армстронга

Выводы

B - аксиомы

Независимость аксиом вывода

Аксиомы рефлексивности, пополнения и псевдотранзитивности являются независимыми. Ни одна из перечисленных аксиом не может быть получена на основании других. В то время как остальные аксиомы могут быть выведены на основании трех независимых аксиом. Так, например, аксиома аддитивности может быть выведена на основании аксиом рефлексивности и псевдотранзитивности (см. Таблица 5).

Таблица 5

№	Функциональные зависимости	Основание
1.	X®Y	Дано
2.	YZ®YZ	Рефлексивность
3.	XZ®YZ	Псевдотранзитивность из (1) и (2)
4.	X®Z	Дано
5.	X®YZ	Псевдотранзитивность из (3) и (4)

Кроме перечисленных шести аксиом вывода, которые часто называют аксиомами Армстронга, существуют так называемые b – аксиомы, которые не являются подмножеством аксиом Армстронга.

Пусть дано отношение r со схемой R, подмножества атрибутов W, X, Y и Z схемы R и атрибут C, тогда мы имеем:

Рефлексивность (b₁) X®X,

Накопление (b₂).

Определение 17

Если отношение удовлетворяет функциональным зависимостям X®YZ и Z®CW, то оно удовлетворяет и функциональной зависимости X® YZC.

Проективность (b₃).

Определение 18

Если отношение удовлетворяет функциональным зависимостям X®YZ, то оно удовлетворяет и функциональной зависимости X® Y.

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

Ниже приведен пример построения последовательности вывода (см. Таблица 6), позволяющей доказать, что если имеют место функциональные зависимостиX® Y, Y® Z, то будет иметь место и функциональная зависимостьXY® Z.

Таблица 6

№	Функциональная зависимость	Основание
1.	X®Y	Дано
2.	Y®Z	Дано
3.	X®Z	Транзитивность из 1 и 2
4.	XY®Z	Пополнение из 3

На основании b - аксиом так же, как и на основании аксиом Армстронга, осуществляется вывод одних функциональных зависимостей из других. Поскольку названия b - аксиом имеют на английском языке следующее написание:

R eflexiviti,

A ccumulation,

P rojectivity,

то по первым буквам этих названий получили название последовательности вывода, выполняемые с помощью b - аксиом RAP последовательности.

Порядок построения RAP последовательности вывода.

· Первая функциональная зависимость получается путем применения аксиомы b₁.

· Каждая последующая функциональная зависимость вычисляется из предыдущих функциональных зависимостей путем применения аксиомы b₂, или вводится из исходного множества функциональных зависимостей, или генерируется на основании аксиомы b₁.

· На последнем шаге вывода может быть применена аксиома проективности b₃.

Ниже приведен пример построения RAP последовательности вывода (см. Таблица 7), позволяющей доказать, что если имеют место функциональные зависимостиX® Y, Y® Z, то будет иметь место и функциональная зависимостьX® Z.

Таблица 7

№	Функциональная зависимость	Основание
1.	X®X	b1
2.	X®Y	Дано
3.	X®XY	Накопление (b2)
4.	Y®Z	Дано
5.	X®XYZ	Накопление (b2)
6.	X®Z	Проективность (b3), это и требовалось доказать

Дата добавления: 2014-12-17