Реляционное исчисление с переменными на доменах

Строится так же, как и исчисление на кортежах (с использованием тех же самых операторов).

Атомами формул могут быть:

1. R(x₁ … x_n), где x_i –const или переменная на некотором домене. Этот атом указывает, что значение тех xi, которые являются переменными д.б. выбраны так, чтобы (x1..xk) было кортежем отношения R.

2. xθ y, где x, y-const, или переменные на некотором домене. θ – арифметический оператор сравнения, смысл атома заключается в том, что x и y представляют собой значения, при которых истинно xθ y. Формулы в РИ с переменными на доменах также используют A, E, И, ИЛИ, НЕ. Аналогично используются понятия свободной и связанной переменной.

Формула РИ с переменными на домене имеет вид: {x1..xk|Ψ (x1..xk)}, где Ψ – формула, обладающая тем свойством, что только ее свободные переменные на доменах являются различн. перемен. х1..хk.

Выражение РИ c переменными на доменах является безопасным, если

1. Из истинности Ψ (x1..xk) следует, что xi принадлежит D(Ψ ).

2. Если существует и (Eu)(Ψ 1(u)) является подформулой Ψ, то из истинности Ψ 1(u) следует, что u принадлежит D(Ψ 1)

3. Если для любого u (Au)(Ψ 1(u)) является подформулой Ψ 1(u) следует, что u не принадлежит D(Ψ 1).

Для каждого безопасного реляционного выражения с переменными на доменах существует эквивалентное ему выражение реляционной алгебры и эквивалентное ему выражение реляционного исчисления с переменными на кортежах.

Выражение исчисления на доменах эквивалентное заданному выражению с переменными на кортежах строится следующим образом:

1. Если t является кортежем арности k, то вводится k новых переменных на доменах t1..tk

2. Атомы R(t) заменяются атомами R(t1..tk)

3. Каждое свободное вхождение t[i] заменяется на ti

4. Для каждого кванта (Eu) и (Au) вводится m новых переменных на доменах u1..um, где u-арность кортежа. В области действия выполняются следующие замены:

Rmà R(U1..Um) U[i]à Ui EUà EU1..EUm AUà AU1..AUm

5. Выполняется построение выражения {t1..tk|Ψ `(t1..tk)}, где Ψ ’, это Ψ, в которой выполнены соответствующие замены.

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

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

Пусть А и В атрибуты отношения 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.

Избыточные функциональные зависимости, минимальное покрытие декомпозиции

Полное множество правил вывода состоит из 3 аксиом Амстронга, а также трёх следующих из этих аксиом правил.

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

1. Аксиомы 1.2.3

1. Рефлексивность: XÍ U, YÍ U, YÍ X, то Xà Y

2. пополнение: XÍ U, YÍ U, ZÍ U, Xà Y, то XÈ Zà YÈ Z

3. транзитивность: XÍ U, YÍ U, ZÍ U, Xà Y, Yà Z, то Xà Z

2. Из них следуют правила:

1. Объединения Aà B, Aà C то Aà B, C

2. Декомпозиции Aà B, C, то Aà B, Aà C

3. Псевдотранзит: Xà Y; Y, Wà Z; то X, Wà Z

По этим правилам определяем избыточные зависимости

Обобщённый алгоритм декомпозиции:

1. Построение универсального отношения для БД.

2. Определение всех ФЗ, существующих между атрибутами универсального отношения.

3. Удаление всех избыточных ФЗ из исходного набора ФЗ с целью получения минимального покрытия. Эта процедура проводится путём поочерёдного удаления избыточных ФЗ с последующей проверкой получаемого на каждом шаге набора ФЗ на наличие хотя бы одной избыточной ФЗ.

4. Использование ФЗ из минимального покрытия для декомпозиции универсального отношения в набор НФБК- отношений.

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

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

а). выбор оставшихся ФЗ и создание одного отношения для каждых детерминанта и набора зависящих от него атрибутов;

б). изменение порядка ранее проведенных декомпозиций, т. к. алгоритм проектирования не ведёт к единственному решению.

ИФЗ

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

Поскольку избыточная функциональная зависимость не содержит уникальной информации она может быть удалена без урона для БД.

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

Отношение является избыточным, если

1. Все его атрибуты могут быть найдены в другом отношении проектного набора.

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

Если установлена избыточность отношения, то его следует исключить из проектного набора.

⇐ Предыдущая 123 4 5 6 Следующая ⇒