Правила вывода Армстронга

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

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

Действительно, рассмотрим два кортежа u Î r и v Î r, где r – некоторая реализация отношения, удовлетворяющая схеме R. Пусть u[A] = v[A]. Что можно сказать о u[B] и v[B]? u[C] и v[C]? Если эти кортежи не совпадают по атрибуту B, т.е. для этих кортежей u[B] ¹ v[B], значит, нарушена функциональная зависимость A à B. Если же кортежи не совпадают по атрибуту C – u[C] ¹ v[C], тогда будет нарушена функциональная зависимость B à C.

Рассмотрим некоторые определения.

Определение

Пусть F – множество функциональных зависимостей для схемы отношения R, и имеется еще одна функциональная зависимость f: X à Y. Говорят, что функциональная зависимость X à Y логически следует из F, если для любой реализации отношения r(R), удовлетворяющей всем зависимостям из F, удовлетворяется также и зависимость X à Y.

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

Определение

Логическим замыканием F (обозначается как F⁺) называется полное множество функциональных зависимостей, которые логически следуют из F.

Важно иметь возможность из F получить F⁺. F⁺ получается из F с помощью специальных правил вывода.

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

Правила вывода позволяют по заданному множеству F функциональных зависимостей получить F⁺. Причем эти правила являются:

- полными, в том смысле, что для заданного множества F функциональных зависимостей эти правила позволяют вывести все функциональные зависимости, принадлежащие F⁺;

- надежными (исчерпывающими), в том смысле, что, используя их, нельзя вывести из F некоторую функциональную зависимость, не принадлежащую F⁺.

Рассмотрим правила вывода. Введем следующие обозначения:

R(A1A2…An) –схема отношения;

U = {A1, A2, …An} – универсальное множество атрибутов;

X Í U, Y Í U, Z Í U, W Í U – некоторые подмножества атрибутов из U;

XY – объединение атрибутов: X È Y º XY