Покрытия

Если множества F и G эквивалентны, то говорят, что F покрывает множество G, и наоборот, G покрывает F.

В теории реляционных структур рассматривается несколько видов покрытий:

- каноническое;

- неизбыточное, или безызбыточное;

- минимальное;

- минимальное каноническое.

Определим каждое из них.

Множество функциональных зависимостей F называется каноническим покрытием [4], [6], если:

1) правая часть каждой зависимости из F содержит единственный атрибут; этого всегда можно добиться, используя правило декомпозиции правой части зависимости (см. раздел 1.3.2);

2) ни одна функциональная зависимость в F не является “лишней”, т.е. ни для какой зависимости (X ® Y) Î F множества F и F \ {X ®Y} не являются эквивалентными (здесь, как и прежде, знак “\” означает вычитание, в данном случае вычитание зависимостей); очевидно, “лишней” будет зависимость, которую можно вывести из остальных зависимостей.

3) ни один атрибут в левой части любой зависимости из F не является “лишним”. Зависимости без “лишних” атрибутов слева называют элементарными. Так, например, если X = AZ, X ≠Z и (F \ {X ® Y}) È {Z ® Y} º F, то атрибут A в зависимости X ® Y является “лишним” и его можно удалить.

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

Множество функциональных зависимостей без “лишних” зависимостей, называется неизбыточным покрытием исходного множества зависимостей F, которое будем обозначать F₀.

Например, пусть F = {AB ® C, A ® B, B ® C} Нетрудно показать, что множество G = {AB ® C, A ® B, B ® C, A ® C} эквивалентно F, но избыточно (зависимость A ® C – “лишняя”, так как транзитивно выводится из зависимостей A ® B и B ® C). Кроме того, “лишней” оказывается и зависимость AB ® C, так как она выводится из зависимостей A ® B и B ® C. Тогда множество F₀ = {A ® B, B ® C} является неизбыточным покрытием как F, так и G.

Множество функциональных зависимостей F называется минимальным, если оно содержит не больше F - зависимостей, чем любое эквивалентное ему множество зависимостей [4].

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

При проектировании базы данных методом синтеза, который будет подробно рассмотрен в разделе 2.2, каждая зависимость определяет отношение (таблицу). Поэтому стремление получить минимум зависимостей вполне оправдано.

Однако в литературе по базам данных не содержится указаний не только на способы построения минимальных покрытий, но даже на проверку минимальности. В работе [4] предлагается способ вычисления минимальных покрытий при одном частном виде функциональной определенности. Очевидно, в общем случае для построения минимальных покрытий, как и для получения оптимальных решений, требуются алгоритмы высокой вычислительной сложности. На практике часто оптимальные решения заменяются подоптимальными, которые получить гораздо проще, а по своим характеристикам они часто незначительно уступают оптимальным решениям. При проектировании реляционных баз данных таким подоптимальным решением можно считать неизбыточное покрытие. Однако использование неизбыточных покрытий – не единственный способ уменьшения таблиц в проектируемой базе данных.

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

· построением неизбыточных покрытий;

· удалением “лишних” атрибутов в левых частях зависимостей;

· выявлением эквивалентных зависимостей.

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

Рассмотрим каждый из этих способов подробнее.