Кольцевое покрытие

Комплексные функциональные зависимости

Каноническое покрытие

Определение 31

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

Очевидно, что любое каноническое покрытие редуцировано по определению.

Для получения канонического покрытия следует выполнить следующие преобразования:

· Применяя аксиомы проективности, все функциональные зависимости приводятся к виду X®A, где Х – множество атрибутов, А – атрибут отношения.

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

· В оставшихся функциональных зависимостях удаляются лишние атрибуты.

· Удаляются функциональные зависимости типа X®ø.

Например, каноническим покрытием множества функциональных зависимостей F={A®BC, B®CD} будет множество функциональных зависимостей F={A®B, B®C B®D}. После реализации первого шага была выявлена избыточная функциональная зависимость A®B. Следует обратить внимание, что в исходном множестве избыточные функциональные зависимости не наблюдались, однако в первой функциональной зависимости присутствовал “ лишний” атрибут B.

Множество функциональных зависимостей может быть разделено на классы с эквивалентными левыми частями. Функциональные зависимости, у которых левые части эквивалентны, относятся к одному классу и могут быть сведены в одну функциональную зависимость, которая называется составной функциональной зависимостью (CF- зависимость) и имеет вид (X₁,X₂,...,X_K) ® Y, где X₁,X₂,...,X_K и Y - различные подмножества схемы R над отношением r.

Если Y есть пустое множество, то СF- зависимость запишется так: (X₁,X₂,...,X_K). Этой записи соответствует следующее множество функциональных зависимостей: X₁® X₂, X₂ ® X₃ , …, X_n ® X₁. Таким образом, CF – зависимость есть сокращенная форма записи традиционного множества функциональных зависимостей.

Определение 32

Множество функциональных зависимостей вида X®Y называется характеристическим множеством составной функциональной зависимости, если оно эквивалентно ей.

Определение 33

Если в характеристическом множестве каждое левое множество из CF –зависимости используется в качестве левой части функциональной зависимости только один раз, то характеристическое множество называется естественным характеристическим множеством.

Например, если CF=(X₁,X₂,...,X_K) ® Y, то множество X₁ ® X₂, X₂ ® X₃, X₃ ® X₁Y является естественно-характеристическим, в то время как множество X₁® X₂, X₂ ® X₃, X₁ ® X₃, X₃ ® X₁, X₃ ® Y – только характеристическим.

Кольцевое покрытие используется в качестве основания для декомпозиции на множестве функциональных зависимостей с несколькими эквивалентными левыми частями. Действительно, рассмотрим отношение со схемой R={ABCD} и множеством функциональных зависимостей на этой схеме F={A ® B, B ® C, C ® D, D® B}. Анализ функциональных зависимостей не позволит здесь выявить избыточные функциональные зависимости. Очевидно, что это покрытие является минимальным, однако число функциональных зависимостей может быть несколько сокращено, поскольку в отношении присутствуют три эквивалентных атрибута (B, C,D), замыкания которых равны. Запишем исходное множество функциональных зависимостей, используя комплексные функциональные зависимости G={ (A)® B, (B,C,D)}, и назовем его кольцевым.

Определение 34

Множество функциональных зависимостей G называется кольцевым покрытием F, если оно эквивалентно F и представлено в виде СF – зависимостей.

Любое множество функциональных зависимостей можно представить как кольцевое. Например, множество F₁={X®Y, X®Z}может быть записано какG₁={(X) ® YZ}, а множество F₂={X® Y} как G₂={(X)® Y}.

Кольцевые покрытия следует рассматривать как более удобную форму записи множества функциональных зависимостей, среди которых есть функциональные зависимости с эквивалентными левыми частями. В связи с вышесказанным кольцевые покрытия могут быть неизбыточными, минимальными, редуцированными и т.п. Ниже приведены примеры кольцевых покрытийF₁={A®BDC, B®ACE} (см. Таблица 9).

Таблица 9

№	Кольцевое покрытие	Характеристика
	G={ (B)®ACE, (A) ® BCD)}	Множество неизбыточное, но не редуцировано, в первой CF зависимости лишний атрибут С
	G={ (B)® AE, (A) ® BCD)}	Множество неизбыточно, редуцировано, но не минимально
	G={ (B,A)® EC,D)}	Множество редуцировано и минимально

Дата добавления: 2014-12-17