Сохранение зависимости

В процессе приведения отношений часто возникают ситуации, когда данное отношение может быть подвергнуто операции декомпозиции разными способами. Рассмотрим снова приведенное выше отношение SECOND с функциональными зависимостями S#®CITY, CITY®STATUS и, следовательно, транзитивной зависимостью S#®STATUS (на рис. 10.11 транзитивная зависимость показана пунктирной стрелкой).

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

Назовем эту декомпозицию просто "декомпозицией А", имея в виду, что для нее существует альтернативная "декомпозиция В":

При этом обе проекции SC одинаковы как для А, так и для В. Декомпозиция В происходит также без потери информации, а обе ее проекции находятся в ЗНФ. Однако по некоторым причинам декомпозиция В менее желательна, чем декомпозиция А. Например, после выполнения декомпозиции В все еще невозможно вставить информацию о том, что некоторый город имеет некоторый статус, без указания поставщика из этого города.

Рассмотрим этот пример подробнее. Прежде всего заметим, что зависимости проекций в декомпозиции А отмечены сплошными стрелками (см. рис. 10.11), тогда как одна из зависимостей проекций декомпозиции В отмечена пунктирной стрелкой. В декомпозиции А две проекции независимы друг от друга в следующем смысле: обновления в каждой из проекций могут быть выполнены совершенно независимо друг от друга. (Конечно, за исключением ограничения целостности для SC и CS.) Если такое обновление допустимо только в контексте данной проекции, т.е. не нарушается уникальность первичного ключа для этой проекции, то соединение этих двух проекций после обновления всегда будет равносильно отношению SECOND (т.е. при соединении не будут нарушены ограничения, наложенные на Ф3 в отношении SECOND). В декомпозиции В, наоборот, обновление любой из двух проекций должно тщательно фиксироваться, чтобы гарантировать отсутствие нарушения зависимости CITY ® STATUS (если два поставщика находятся в одном и том же городе, они должны иметь одинаковый статус; в качестве примера разберите случай, когда в декомпозиции В поставщик S1 переместится из Лондона в Париж). Иначе говоря, обе проекции декомпозиции В не являются независимыми одна от другой.

Основная проблема заключается в том, что в декомпозиции В функциональная зависимость CITY®STATUS становится ограничением между отношениями. (Следует отметить, что во многих современных программных продуктах это ограничение должно поддерживаться с помощью процедурной обработки.) В декомпозиции А, наоборот, транзитивная зависимость S#®STATUS является ограничением между отношениями, которое автоматически выполняется при задействовании двух ограничений внутри отношений: S#®STATUS и CITY®STATUS. Привести в действие эти ограничения достаточно просто за счет соответствующих ограничений, наложенных на уникальность первичных ключей.

Концепция независимых проекций, таким образом, обеспечивает критерий выбора одной из нескольких возможных декомпозиций. Декомпозиция с независимыми проекциями в приведенном выше общем смысле предпочтительнее той, в которой проекции зависимы. Риссанен (Rissanen) [10.6] показал, что проекции R1 и R2 отношения R независимы в упомянутом выше смысле тогда и только тогда, когда

■ ■ каждая ФЗ в отношении R является логическим следствием функциональных зависимостей в проекциях R1 и R2;

■ ■ общие атрибуты проекций R1 и R2 образуют потенциальный ключ, по крайней мере, для одной из них.

Рассмотрим заданные выше декомпозиции А и В. В декомпозиции А две проекции независимы, поскольку их общий атрибут CITY является первичным ключом для отношения CS и каждая ФЗ отношения SECOND либо находится в одной из проекций, либо является логическим следствием имеющихся. В декомпозиции В, наоборот, две проекции не являются независимыми, поскольку зависимость CITY —»STATUS не может быть выведена из ФЗ этих проекций, хотя их общий атрибут S# является потенциальным ключом для обеих проекций.

(Следует отметить, что третий вариант декомпозиции с заменой отношения SECOND проекциями {S#, STATUS} и {CITY, STATUS} не является допустимой декомпозицией, поскольку выполняется с потерей информации. Упражнение. Докажите это утверждение.)

Терминология. Отношение, которое не может быть подвергнуто декомпозиции с получением независимых проекций, называется атомарным [10.6]. Однако это не значит, что любое неатомарное отношение может быть разбито на атомарные компоненты. Например, отношения S и Р из рассматриваемой ранее базы данных поставщиков и товаров (поставщиков и деталей) не являются атомарными, но дальнейшая их декомпозиция была бы бессмысленной. Отношение SP, наоборот, является атомарным.

Идея нормализации с декомпозицией на независимые проекции (в смысле Риссанена) называется декомпозицией с сохранением зависимости. В заключение следует привести несколько более строгих замечаний по поводу этой идеи.

1. 1. Пусть дано некоторое отношение R, которое после выполнения всех этапов процедуры нормализации заменяется множеством отношений R1, R2,... Rn (конечно, все они являются проекциями отношения R).

2. 2. Пусть также задано множество зависимостей S для исходного отношения R, и множества зависимостей S1, S2,... Sn для отношений R1, R2,... Rn.

3. 3. Каждая ФЗ множества Si будет относиться только к атрибутам множества Ri (i =1, 2, 3,...,). Таким образом, приведение в действие ограничений (ФЗ) в любом заданном множестве Si представляется достаточно простой задачей. Однако в данном случае необходимо задействовать ограничения из исходного множества S. При этом следовало бы выбрать такую декомпозицию на отношения R1, R2,... Rn, для которой совместное приведение в действие отдельных множеств ограничений S1, S2,... Sn эквивалентно приведению в действие ограничений в исходном множестве S. Иначе говоря, декомпозиция должна выполняться с сохранением зависимостей.

4. 4. Пусть S' является объединением множеств зависимостей S1, S2,... Sn. Обратите внимание, что в общем случае равенство S'=S не выполняется, однако для выполнения декомпозиции с сохранением зависимостей достаточно, чтобы замыкания S и S' были равны друг другу (понятие замыкания множества ФЗ рассматривалось в главе 9).

5. 5. В общем случае не существует эффективного способа вычисления замыкания S⁺ множества Ф3, поэтому вычисление и сравнение двух замыканий трудноосуществимо. Тем не менее, существует эффективный метод проверки, будет ли данная декомпозиция выполняться с сохранением зависимости. Описание подробностей этого алгоритма выходит за рамки данной книги, однако они описываются в книге Ульмана (Ullman) [7.16].

Замечание. В ответах на упражнения в конце этой главы описан алгоритм выполнения декомпозиции без потерь и с сохранением зависимости для произвольного отношения с разбиением на множество проекций в ЗНФ.