Правила вывода функциональной зависимости

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

Пусть А и В атрибуты отношения R . Говорят, что атрибут В отношения R функционально зависит от атрибута А, если в каждый момент времени каждому значению а соответствует не более одного значения b. Функциональную зависимость f атрибута В от атрибута А обозначают : f : А ® В. Эту зависимость f можно также представить множеством упорядоченных пар {< а, b>/ а Î А, b Î В }, в которых каждому значению а соответствует только одно значение b. При этом говорят, что В функционально зависит ( или просто зависти ) от А, а А функционально определяет ( или просто определяет) В.

Если существует единственная функциональная зависимость В от А, то её обозначают просто А ® В. В случае отсутствия между ними функциональной зависимости вводят обозначение А ¹ В. Если А ® В и одновременно В ® А , то между А и В существует взаимно однозначное соответствие, что записывается как А « В.

Пусть имеется множество атрибутов А₁, А₂,...,А_n отношения R, а также множество F Ф.З. Х ® Y, где Х и Y - подмножества атрибутов множества А₁, А₂,...,А_n. Тогда из Ф.З. (функциональные зависимости), входящих в F, могут быть выведены другие Ф.З., присущие отношению R.

Обозначим через F⁺ замыкание множества ФЗ F, т.е. полное множество зависимостей, которое можно получить из F.

Правило вывода ФЗ :

1. Правило ФЗ 1 (свойство рефлексивности). Если Х £ U, Y £ U и Y £ Х, то имеет место Ф.З. Х ® Y.

Правило ФЗ 2 (свойство пополнения). Если Х £ U, Y £ U и Z £ U и имеет место Ф.З. Х ® U, X È Z ® Y È Z.

В отличии от правила ФЗ 1 данное говорит о том, что для его применения несу щественно выполнение условий Y £ Х. Т.е. любые атрибуты из множества U можно одновременно подставлять в левую и правую части выражения Ф.З. F.

Например, имеется универсальное отношение U(A₁, A₂, A₃, A₄, A₅) и заданы наборы атрибутов X={A₁, A₃}, Y={A₂, A₄}, Z={A₅}, тогда из условия, что существует Ф.З. Х ® Y : {A₁, A₃}® {A₂, A₄}, следует, что имеет место зависимость:

{A₁, A₃, А₅}® {A₂, A₄, А₅},

3. Правило ФЗ 3 (свойство транзитивности) . Если Х £ U, Y £ U и Z £ U и имеют место зависимости Х ® Y и Y ® Z, то Х ® Z . Например, имеются подмножества атрибутов X={A₁, A₃}, Y={A₂, A₄}, Z={A₅}. Тогда из условия существования зависимостей {A₁, A₃}® {A₂, A₄}, {A₂, A₄}® {A₅} следует, что имеет место зависимость {A₁, A₃}® {A₅}.

Кроме этих правил часто используют дополнительные правила следствия ФЗ 1, ФЗ 2, и ФЗ 3.

4. Правило ФЗ 4 (свойство расширения). Если Х £ U, Y £ U и задана ФЗ,

Х ® Y , тогда для любого Z £ U имеет место Ф.З. X ÈZ ® Y.

5. Правило ФЗ 5 (свойство продолжения). Если Х £ U, Y £ U, W £ U, Z £ U и задана Ф.З. Х ® Y, то для любых W £ Z имеет место зависимость X ÈZ ® Y È W.

6. Правило ФЗ 6 ( свойство псевдотранзитивности). Если Х £ U, Y £ U,

W £ U, Z £ U и заданы Ф.З. Х ® Y, Y ÈW ® Z , то имеет место Ф.З. X ÈW ® Z.

7. Правило ФЗ 7 (свойство аддитивности). Если Х £ U, Y £ U, Z £ U, и заданы Ф.З. Х ® Y, Х ® Z, то имеет место Ф.З. X ®Y È Z.

8. Правило ФЗ 8 (свойство декомпозиции). Если Х £ U, Y £ U, Z £ U, и при этом Z £ Y и заданы Ф.З. Х ® Y, то имеет место Ф.З. Х ® Z.

Реляционная алгебра

В ней определяются основные операции над данными реляционного типа. Все операции можно разделить на традиционные над множествами и специализированные, вводимые для удобства поиска в БД.

К операциям 1-й группы относятся: объединения, пересечения, разность, декартово произведение. К операциям 2 -й группы относятся: проекция, ограничение, соединение, деление.

Объединение. В результате применения этой операции получается отношение. объединяющее кортежи, содержащиеся в исходных отношениях. Пусть имеем два исходных отношения R₁ и R₂ . Операция объединения этих отношений обозначается R₁ È R₂:

R₁ È R₂ = { r / r Î R₁ или r Î R₂ }.

Объединяемые отношения должны иметь одинаковые атрибуты ( должны быть объединимы ):

Пересечение. В данной операции ( обозначенной Ç ) получают отношение, включающее кортежи, общие для R₁ и R₂:

R₁ Ç R₂ = { r / r Î R₁ и r Î R₂ }.

Разность: В результате применения этой операции (R₁ \ R₂ ) получается отношение, содержащее кортежи, являющиеся кортежами отношения R₁ и не являющиеся кортежами отношения R₂:

R₁ \ R₂ = { r / r Î R₁ и r Ï R₂ }.

Декартово ( прямое ) произведение. В этой операции ( R₁ х R₂ ) из m - местного отношения R₁ и n - местного отношения R₂ получают ( m + n ) - местное отношение. Причём первые m элементов представляют кортежи из отношения R₁ , последние n элементов - кортежи из отношения R₂:

R₁ х R₂ = {< r₁, r₂ > / r Ï R₁ и r Ï R₂ }.

Проекция: Операция проекции предназначена для изменения числа столбцов в отношении, то есть в том случае, когда из строк - кортежей требуется исключить какие-либо атрибуты. Обозначим через j₁, j₂,..., j_n - номера столбцов n - местного отношения R. Операцию определения проекции отношения R обозначим через p _j1, _j2,..., _jn ( R ), а сама операция заключается в том, что из отношения R выбираются столбцы и компонуются в указанном порядке j₁, j₂,..., j_n.

Ограничение. Ограничением называют такую операцию, в которой отношение исследуют по строкам и выделяют множество строк, удовлетворяющим заданным условиям.

Соединение. Операция соединения обратна операции проекции. Рассмотрим два отношения R₁ (А, В) и R₂ (В, С). Соединением отношений R₁ и R₂ (R₁ ¥ R₂ ) называют операцию, при которой соединяют два отношения, используя в качестве признака общий атрибут В:

R₁ ¥ R₂ = { <A,B,C> / <A,B> Î R₁ и <B,C> Î R₂ }.

Отношение R₁ ¥ R₂ является отношением с атрибутами <A,B,C>.

Деление. Рассмотрим деление m - местного отношения R₁ на n - местное отношение R₂.

Пусть из общего количества m атрибутов отношения R₁ выделим несколько атрибутов: A,B,...,F и из них составляем список, обозначив его через M. Набор значений атрибутов из М столбцов можно рассмотреть как проекцию отношения R на список атрибутов М, то есть p_М (R₁). Тогда через М будут обозначаться атрибуты дополнительные к М, то есть атрибуты отношения R₁, не вошедшие в список М, и соответственно значения атрибутов из списка М определяются p_М (R₁).

Операцию деления можно определить так:

R₁ [M ¸N] R₂ = p_М (R₁) \ p_М ((p_М (R₁) ´ p_N (R₂)) \ R₁ },

где p_М - это проекция отношения на атрибуты списка М.

НФСО, НФ1, НФ2