Функциональные зависимости и ключи

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

Например, дана схема отношения

r = R(a₁ а₂,..., а_n).

Функциональная зависимость (F-зависимость) между двумя атрибутами определяется следующим образом:

Атрибут а₂ функционально зависит от атрибута a₁, если каждому значению a₁ соответствует единственное значение a₂ (то есть каждый кортеж, имеющий одно и то же значение а₁ должен иметь одно и то же значение a₂).

Обозначается a₁→a₂ (т.е. а₁ функционально определяет а₂).

Отсутствие функциональной зависимости обозначается а / а₂.

Важнейшими задачами при разработке баз данных являются понижение избыточности данных и повышение их надежности. Они решаются наложением различных ограничений на данные. Установление Fзависимостей является одим из способов наложения ограничений на данные.

Допустим, есть отношение:

РАСПИСАНИЕ (Бригада, Рейс, Дата, Время)

На атрибуты отношения наложены ограничения:

- для каждого рейса назначается только одно время отправления;

- для каждой бригады, даты и времени отправления возможен только один рейс;

- для данного рейса и даты назначается только одна бригада.

РАСПИСАНИЕ

Бригада	Рейс	Дата	Время
		5.09	19: 20
		5.09	11:25
		6.09	10:10
		7.09	11:25
		9.09	19:20
		9.09	11:25
		11.09	19:20

Наложенные ограничения являются примерами F-зависимостей. Их можно формально записать следующим образом:

• атрибут Время функционально зависит от атрибута Рейс;

• атрибут Рейс функционально зависит от атрибутов Бригада, Дата, Время;

• атрибут Бригада функционально зависит от атрибутов Рейс, Дата.

Можно сказать иначе:

• (Рейс) функционально определяет (Время);

• (Бригада, Дата, Время) функционально определяют (Рейс);

• (Рейс, Дата) функционально определяют (Бригада),

или - система ограничений отношения РАСПИСАНИЕ имеет вид:

Рейс→Время (1)

Бригада, Дата, Время → Рейс (2)

Рейс, Дата → Бригада. (3)

Рассмотрим формальное определение F зависимостей с использованием реляционных операторов.

Пусть r - отношение со схемой R, а X, Y - подмножества R (атрибуты, столбцы таблицы r). Отношение г удовлетворяет функциональной зависимости X→Y, если проекция отношения r, т.е подмножество Y из отношения r имеет не более чем один кортеж для каждого значения х из подмножества Х [записывается, как Рy(δх=х(г)), читается, как «проекция атрибута Y на атрибут Х в отношении r» ].

Другими словами, проекция отношения r со схемой R, в которой есть

атрибуты (столбцы) Х и Y – это часть отношения r, состоящая только из атри

бутов Х и Y (т.е. схема R = (X,Y)), в которой каждому значению х из атрибута

Х соответствует только одно значение y из атрибута Y.

Если такая проекция Рy(δх=х(г)) имеется, то для отношения r существует F- зависимость X→Y. Для двух кортежей t₁ и t₂ в отношении r это означает, что если

t₁ (X) = t₂ (X), то t₁ (Y) = t₂ (Y)

или - для одного и того же отношения r, если кортежи t₁ и t₂ равны по подмножеству Х, то они равны и по подмножеству Y.

Это приводит к следующему алгоритму выявления наличия F-зависимо­сти X→Y:

1. Пересортировать отношение r по X -столбцам так, чтобы собрать кортежи с равными X-значениями вместе.

2. Если каждая совокупность кортежей с равными X-значениями имеет также равные Y-значения, то на выходе получаем истину, в противном случае - ложь.

Применим этот алгоритм к отношению РАСПИСАНИЕ.

Отсортируем кортежи по атрибуту Рейс для проверки существования F- зависимости Рейс→Время:

РАСПИСАНИЕ

Бригада	Рейс	Дата	Время
		5.09	19: 20
		5.09	11:25
		9.09	11:25
		7.09	11:25
		6.09	10:10
		9.09	19:20
		11.09	19:20

Для каждого значения атрибута Рейс с равными значениями величины значений атрибута Время также одинаковы, следовательно для отношения РАСПИСАНИЕ выполняется F- зависимость(1) Рейс→Время.

 

Если отсортировать таблицу по атрибутам (Бригада, Дата, Время) и (Рейс, Дата), то можно увидеть, что для них F-зависимости не существуют, т.е. отношение РАСПИСАНИЕ имеет некоторую избыточность. Это заметно даже из оформления таблицы: для записей 2,3 и 4 можно объединить поля с рейсом №101 и поля со временем 11:25 и записать рейс №101 и время 11:25 по одному разу вместо трёх. Это же справедливо и для кортежей 6 и 7, где также эти данные дублируются.

Для пустых множеств: если определяется X → Ои Y → О, то F- зависи­мость X → Овыполняется любым отношением, а F- зависимостьО → Y удовлетворяется теми отношениями, в которых Y-значения всех кортежей одинаковы.

Аксиомы вывода

Для отношения г (R) в любой момент существует семейство F - зависимостей (множество F), которым это отношение удовлетворяет.

Это множество F, применимых к отношению г (R), - конечно, так как существует только конечное число подмножеств (атрибутов) множества R. Можно перебрать все варианты с помощью описанного выше алгоритма, чтобы найти весь список F- зависимостей., но это потребует большого количества времени. Задача упрощается, если известны некоторые F-зависимости из F, тогда остальные можно получить, использую аксиомы вывода.

Аксиома вывода —если отношение удовлетворяет определенным F - зависимостям, то оно должно удовлетворять и ряду других F-зависимостей.

Существует шесть аксиом вывода для F- зависимостей. В их формулировках используется обозначение г - для отношения на R, и W, X, Y, Z - для подмножеств R.

F1. Рефлексивность. Проекция (отношение) Р_x (σ_X=x (r)) всегда имеет не более одного кортежа, следовательно, Х→Х всегда имеет место в r. Другими словами, проекция атрибута Х на самого себя всегда имеется в отношении r.

F2. Пополнение. Если отношение r удовлетворяет F-зависимости Х→Y, то оно удовлетворяет и F-зависимости ХZ→Y, где Z - любое подмножество схемы отношения R.

Пример 2.6. Дано отношение:

 

А	В	С	D
al	b1	cl	dl
а2	b2	cl	dl
al	b1	с2	d2
аЗ	ЬЗ	с2	d3

Это отношение удовлетворяет F-зависимо­сти А→В, и, следовательно, F-зависимостям:

АВ → В, АС → В, AD → В,

ABC → В, ABD → В, ACD → B,

AВCD → B всилу аксиомы F2.

F3. Аддитивность (объединение). Если отношение r удовлетворяет F-за­висимостям Х→Y и X→Z, то оно удовлетворяет F-зависимости X →YZ.

Пример 2..7 Отношение r из примера 2.6 удовлетворяет F-за­висимо­стям А→В и А→С. По аксиоме F3оно также удовлетворяет F-зависимости А→ВС.

F4. Проективность (декомпозиция). Если отношение r удовлетворяет F-зависимости X →YZ, то оно удовлетворяет также F-зависимостям Х→Y и X→Z.

Пример 2.8. Отношение r из примера 2.6 удовлетворяет F-за­висимо­сти

А→ВС. Согласно аксиоме F3оно также удовлетворяет F-зависимостям А→В и А→С.

F5. Транзитивность. Если отношение r удовлетворяет F-за­висимо­стям Х→Y и Y→Z, то оно удовлетворяет F-зависимости X→Z.

Пример 2.9 Дано отношение:

r

A	В	С	D
al	bl	c2	dl
a2	b2	cl	d2
а1	bl	c2	dl
а1	bl	c2	d3

Здесь А→В и B→С. Согласно аксиоме F5,

отношение r удовлетворяет А→С.

F6. Псевдотранзитивность. Если отношение r удовлетворяет F-зависимостям X→Y и YZ→W, то оно удовлетворяет F-зависимости XZ→W.

Запишем кратко все аксиомы.

F1. Рефлексивность: X→X.

F2. Пополнение: X→Y влечет за собой XZ→Y.,

F3. Аддитивность: X→Y и X→Z влечет за собой X→YZ.

F4. Проективность: X→YZ влечет за собой X→Y.

F5. Транзитивность: X→Y и Y→Z влечет за собой X→Z.

F6. Псевдотранзитивность: X→Y и YZ→W влечет за собой XZ→W.

Аксиомы Армстронга

Аксиомы F1, F2, F6 составляют полное подмножество для F1- F6. Они являются независимыми, т.е.ни одна из этих аксиом не может быть получена из двух других. Эти три аксиомы называются аксиомами Армстронга.

Пример 2.10. Аксиома F5 является частным случаем аксиомы F6

при Z = O.

Для отношения r(R) помимо множества F всех F-зависимостей существует также замыкание F⁺ - это наименьшее, содержащее Fмножество такое, что при применении к нему аксиом Армстронга нельзя получить ни одной F- зависимости, не принадлежащей F.

Замыкание F⁺ есть также замыкание замыкания F⁺, т.е.

F⁺ = (F⁺)⁺

Пример 2.11. Дано F={AB→С }- множество F- зависимостей на r (ABC).

F⁺ = {А→А, АВ→А, АС→A, ABC→А, -аксиомы Fl, F2

В→В, АВ→В, ВС→В, ABC →В, -аксиомы Fl, F2

С→С, АС→С, ВС→С, ABC→C, -аксиомы Fl, F2

АВ→АВ, ABC→AB, -аксиомы Fl, F2

АС→AC, ABC→АС, -аксиомы Fl, F2

BC→BC, ABC→BC, ABC→ABC, -аксиомы Fl, F2

АВ→С, АВ→АС, АВ→ВС, АВ→ABC} -аксиомы Fl, F2

Система аксиом вывода F1- F6 является полной. Это означает, что каждая F-зависимость из множества F, может быть выведена путем одно- или многократного применения этих аксиом к множеству F.