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

Используя понятие эквивалентности зависимостей, можно также уменьшить количество зависимостей в исходном множестве. Рассмотрим, почему это происходит.

Зависимости X_i ® Y_i и X_j ® Y_j будем называть эквивалентными, если

(X_i È Y_i) = (X_j È Y_j). Например, эквивалентными будут зависимости A ® BCD и AB ® CD. Набор эквивалентных между собой зависимостей называют классом эквивалентности. Очевидно, зависимости из одного класса эквивалентности дадут схемы отношений с одинаковым набором атрибутов. Если каждой зависимости будет соответствовать таблица в базе данных, то эквивалентные зависимости дадут таблицы с одинаковым набором полей. Иметь в базе данных несколько таблиц с одинаковым набором полей бессмысленно. В этом случае целесообразно в каждом классе эквивалентности оставлять одного (почти всегда любого) представителя.

Пример 24. Пусть множество функциональных зависимостей

F = { A ® BCD, CDА ® B, C ® EMK, KMС ® E, E ® B} справедливо на множестве атрибутов U = ABCDEKM.

Легко заметить, что множество F содержит два класса эквивалентности (один класс выделен жирным шрифтом, другой – подчеркиванием).

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

F₁ = {A ® BCD,C ® EMK, E ® B}, которое содержит меньше зависимостей, чем исходное множество F.

Нетрудно показать, что множества F и F₁ эквивалентны.

Декомпозиция схем отношений

Понятие декомпозиции

Декомпозицией схемы отношения R = A₁,..., A_k называется замена ее совокупностью r = {R₁, R₂,..., R_S} возможно пересекающихся подмножеств R_j Ì R, j = 1, 2,..., S, таких что R₁ È R₂ È... È R_S = R. Каждое множество R_j Î r называется декомпозиционной подсхемой.

Декомпозиция - важная операция разбиения схемы отношения на множество декомпозиционных подсхем, которая может использоваться для исключения некоторых недостатков, присущих исходной одной схеме отношения. Отметим основные недостатки [2],[6] отношения PPD из примера 1 раздела 1.1. Итак, имеем отношение:

PPD (PN, PIM, ST, GOR, DN, DIM, CENA, KOL) кортежи

p1 Иванов 80 Москва d1 болт 80 100 к1

p1 Иванов 80 Москва d2 гайка 100 150 к2

p2 Петров 40 Самара d1 болт 80 50 к3

p2 Петров 40 Самара d2 гайка 100 100 к4

p3 Кротов 100 СПб d2 гайка 100 200 к5