Свойство сохранения функциональных зависимостей

Свойство декомпозиции сохранять зависимости из исходного множества F состоит в том, что при восстановлении схемы отношения R из декомпозиционных подсхем все зависимости, объявленные в F, должны автоматически выполняться и в восстановленной схеме R. Определим это свойство формально.

Проекцией множества функциональных зависимостей F на множество атрибутов Z Í U, обозначаемое как p_Z (F), называется такое множество зависимостей (X ® Y) Î F⁺, для которых XY Í Z.

Например, для U = ABC и F = {A ® B, B ® C} проекция p_AB (F) = {A ® B}, а p_AС(F) = {A ® С}. Легко видеть, что зависимость (A ® C) Ï F, но следует из F по аксиоме транзитивности из зависимостей A ® B и B ® C. Следовательно, (A ® C) Î F⁺.

Декомпозиция r = {R₁, R₂,..., R_k} схемы отношения R сохраняет множество функциональных зависимостей F, определенное на R, если из объединения всех зависимостей, принадлежащих проекциям F на декомпозиционные подсхемы R_i, i = 1,2,..., k, логически следуют все зависимости из F.

Тогда

_{k k}

(È p_Ri(F))⁺ = F⁺, т.е. имеет место эквивалентность множеств: (È p_Ri(F)) º F.

^{i=1 i=1}

Пример 27 [6]. Пусть R = ABC и F = {A ® B, B ® C}.

Случай 1. Декомпозиция r = {AB, BC} схемы отношения R сохраняет зависимости из F, так как F₁ = p_AB (F) = {A ® B}, F₂ = p_BC (F) = {B ® C} и (F₁ ÈF₂) = {A ® B,

B ® C} = F, а следовательно, и {A ® B, B ® C}⁺ = F⁺.

Случай 2. Декомпозиция r₁ = {AB, AC} не сохраняет зависимостей из F, так как F₁ = p_AB (F) = {A ® B}, F₂ = p_AС (F) = {A ® C}. Зависимость A ® C выводится из исходного множества F по аксиоме транзитивности. Тогда (F₁ ÈF₂)⁺ = {A ® B, A ® C}⁺ ≠ F⁺. Зависимость B ® C не восстанавливается из объединения проекций.

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

Достаточное условие сохранения декомпозицией функциональных зависимостей состоит в том, чтобы все атрибуты каждой зависимости из F целиком входили в какую-нибудь декомпозиционную подсхему (как в случае 1). Тогда каждая зависимость из F наверняка окажется в проекции F на какую-нибудь декомпозиционную подсхему, а раз так, то все зависимости из F обязательно восстановятся из объединения проекций. Однако это условие не является необходимым, т.е. условие достаточности может быть не выполнено, а декомпозиция при этом сохраняет зависимости. Например, для R = ABC и F = {A ® B, B ® A, A ® C} декомпозиция r = {AB, BC} сохраняет зависимости из F, несмотря на то, что условие достаточности не выполнено. Атрибуты AC зависимости A ® C целиком не входят ни в одну декомпозиционную подсхему, но F₁ = p_AB (F) = {A ® B, B ® A}, F₂ = p_BС (F) = {B ® C} и F₁ ÈF₂ = {A ® B, B ® A, B ® C}. Зависимость A ® C транзитивно выводится из зависимостей A ® B и B ® C. Поэтому (F₁ ÈF₂)⁺ = F⁺.

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

Например, зависимость A ® B будет применима к декомпозиционным подсхемам AB, AB C, AB CD, D A HR B и так далее.

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

§ Способ 1 использует алгоритм синтеза множества зависимостей, входящих в проекции p_Ri(F), где i = 1,2,...,k.

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

Рассмотрим эти способы.

Способ 1 подробно изложен в работах[3], [6]. Способ 2, по мнению авторов, проще. Поэтому ограничимся рассмотрением именно этого способа.

Пример 28 [6]. Пусть R = ABCDEM и F = {A ® B, CD ® A, CB ® D, AE ® M, CE ® D}. Рассмотрим декомпозицию r = {R₁, R₂}, где R₁ = AEM и R₂ = ABCDE. На основе простых рассуждений выясним, обладает ли заданная декомпозиция r свойством сохранения функциональных зависимостей на заданном множестве атрибутов

U = ABCDEM. Попробуем получить ответ на этот вопрос, используя только свойство достаточности.

Строим таблицу из двух столбцов. В один столбец будем записывать функциональные зависимости из F, которые точно восстанавливаются из объединения проекций по условию достаточности, а в другой – остальные, которые необходимо дополнительно исследовать. Очевидно, точно восстанавливаются те зависимости, которые по условию достаточности применимы к какой-либо декомпозиционной подсхеме:

Восстанавливаются Остальные

A ® B (применима к __

подсхеме R₂ = ABCDE)

CD ® A (применима к ABCDE)

CB ® D (применима к ABCDE)

CE ® D (применима к ABCDE)

AE ® M (применима к AEM)

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

Если в столбце “Остальные” останутся зависимости, то они требуют дополнительного исследования. Какого? Рассмотрим примеры.

Пример 29. Пусть R = ABCDEKX и

F = {A ® BC, A ® D, C ® B, D ® EK, AD ® X, X ® AK, E ® K, A ® K}.

Рассмотрим декомпозицию r = {ADEX, EKC, ACEK, DEBC} схемы R.

Пытаемся ограничиться только свойством достаточности. Строим таблицу:

Восстанавливаются Остальные

A ® C (применима к ACEK) A ® B

A ® D (применима к ADEX) D ® K

C ® B (применима к DEBC) X ® K

D ® E (применима к DEBC)

AD ® X (применима к ADEX)

X ® A (применима к ADEX)

E ® K (применима к EKC)

A ® K (применима к ACEK)

Теперь попытаемся вывести остальные зависимости из тех зависимостей, которые восстанавливаются. Так, зависимость A ® B выводится транзитивно из зависимостей

A ® C и C ® B, зависимость D ® K аналогично выводится из зависимостей D ® E и E ® K, зависимость X ® K – из зависимостей X ® A и A ® K. Таким образом, все зависимости из F восстанавливаются и свойство сохранения функциональных зависимостей для заданной декомпозиции выполняется. Однако так просто бывает не всегда. Иногда свойство достаточности дает отрицательный результат, а на самом деле свойство сохранения зависимостей выполняется. В этом случае предлагается получить дополнительные, выводимые из F зависимости, которые дадут возможность опять воспользоваться свойством достаточности. Эти дополнительные зависимости можно получить из расширенного множества F- зависимостей.

Пример 30. Пусть R = ABC и F = {A ® B, B ® A, A ® C}.

Рассмотрим декомпозицию r = {AB, BC} схемы R. Воспользуемся только что предложенной процедурой. Для этого строим таблицу:

Восстанавливаются Остальные

A ® B (применима к AB) A ® C

B ® A (применима к AB)

Из таблицы видно, что зависимость A ® C неприменима ни к подсхеме AB, ни к подсхеме BC. Поэтому она требует дополнительного исследования, которое может заключаться в следующем. Из левого столбца таблицы видно, что A функционально определяет B. Попробуем найти дополнительную зависимость, в которой B может функционально определять C (поскольку C является правой частью исследуемой зависимости)? Для этого строим расширенное множество F- зависимостей:

ℱ = {A ® BC, B ® AC, A ® CB}.

Поскольку расширенное множество содержат все F-зависимости и выводимые из F зависимости, то в качестве дополнительной зависимости можно использовать B ® C, которая получается из зависимости B ® AC по правилу декомпозиции ее правой части и которая применима к декомпозиционной подсхеме BC.

Добавляем полученную дополнительную зависимость в таблицу:

Восстанавливаются Остальные

A ® B (применима к AB) A ® C

B ® A (применима к AB)

B ® C (применима к BC)

Теперь зависимость A ® C транзитивно выводится из зависимостей A ® B и B ® C, поэтому свойство сохранения зависимостей для рассматриваемой декомпозиции выполняется.

Пример 31. Пусть R = ABCDEKMNLX и F = {A ® CD, C ® KML, A ® BD, D ® XNC, X ® D, K ® L, LB ® E}. Рассмотрим декомпозицию r = {ABCDE, DX, XE, CKMNL, KM}. Выясним, обладает ли заданная декомпозиция r свойством сохранения функциональных зависимостей на заданном множестве атрибутов U = ABCDEKMNLX.

Строим таблицу:

Восстанавливаются Остальные

A ® CD (применима к ABCDE) D ® N

A ® BD (применима к ABCDE) LB ® E

D ® C (применима к ABCDE)

C ® KML (применима к CKMNL)

K ® L (применима CKMNL)

D ® X (применима к DX)

X ® D (применима к DX)

Две зависимости в столбце “Остальные” требуют дополнительного исследования. Используя аксиомы и правила вывода функциональных зависимостей (раздел 1.3), а также факт выводимости зависимости (теорема 1 из раздела 1.4), нетрудно выяснить, что зависимости D ® N и LB ® E не выводятся из восстанавливаемых зависимостей.

Попробуем воспользоваться расширенным множеством зависимостей.

ℱ = {A ® CDKMLBXNE, C ® KML, A ® CDKMLBXNE, D ® XNCKML, X ® DNCKML, K ® L, LB ® E}.

Исследуя множество ℱ, приходим к выводу об отсутствии нужной дополнительной зависимости, которая позволила бы вывести зависимость LB ® E. А, если такая зависимость и нашлась бы, то она была бы неприменима ни к одной декомпозиционной подсхеме. Таким образом, делаем вывод о невыполнимости свойства сохранения функциональных зависимостей для заданной декомпозиции.

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