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

SC { SI, CITY } SS { SI, STATUS }

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

Рассмотрим этот пример подробнее. Прежде всего заметим, что зависимости, использованные для создания проекций в декомпозиции А, соответствуют сплошными стрелкам (см. рис. 11.11), тогда как одна из зависимостей, использованная для создания проекций в декомпозиции В, отмечена пунктирной стрелкой. В декомпозиции А обе проекции независимы одна от другой в том смысле, что обновления в каждой из них могут выполняться совершенно независимо. Если гарантируется, что выполняемые обновления будут допустимы в контексте данной проекции (т.е. уникальность ее первичного ключа не нарушается), то соединение этих двух проекций после обновления всегда будет иметь результатом допустимое значение переменной-отношения SECOND. Это следует понимать так, что при соединении не будут нарушаться ограничения, наложенные на функциональные зависимости в переменной-отношении SECOND. Однако в случае декомпозиции В вносимые в любую из двух проекций обновления должны тщательно контролироваться, чтобы исключить возможные нарушения функциональной зависимости CITY -> STATUS. (Нарушения могут иметь место, если два и более поставщиков находятся в одном и том же городе; в этом случае они должны иметь один статус. В качестве примера разберите случай, когда в декомпозиции В поставщик с номером S1 перемещается из Лондона в Париж.) Иначе говоря, две проекции декомпозиции В не являются независимыми одна от другой.

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

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

Конечно, за исключением соблюдения ограничения целостности, установленного для переменных-отношений SC и CS

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

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

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

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

Замечание. Третий вариант декомпозиции с заменой переменной-отношения SECOND проекциями {St, STATUS} и {CITY, STATUS} не является допустимой декомпозицией, поскольку сопровождается потерей информации. {Упражнение. Докажите это утверждение.)

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

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

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

2. Пусть также задано множество функциональных зависимостей S, имеющих место в исходной переменной-отношении R, и множество функциональных зависимостей Sl, S2, Sn, выполняющихся в переменных-отношениях Rl, R2, Rn.

3. Каждая функциональная зависимость в множестве Si будет иметь отношение только к атрибутам проекции Ri (где i=l, 2, 3, п). В результате реализация офаничений (устанавливаемых существующими ФЗ) для любого данного множества Si представляется достаточно простой задачей. Однако в действительности необходимо реализовать все ограничения, определяемые исходным множеством функциональных зависимостей S. Следовательно, целесообразно выбрать такой вариант

декомпозиции исходной переменной-отношения на проекции R1, R2, ..., Rn, при котором совместный эффект от реализации офаничений для отдельных множеств S1, S2, Sn будет эквивалентен реализации всех офаничений для исходного множества функциональных зависимостей S. Иначе говоря, декомпозиция должна выполняться с сохранением зависимостей.

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

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

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

11.5. Нор]У1альная фор1У1а Бойса-Кодда

В этом разделе отбрасывается применявшееся выше допущение о том, что каждая переменная-отношение имеет только один потенциальный ключ (а именно - первичный ключ), и рассматривается более общий случай. Дело в том, что первоначальное определение, данное Коддом для ЗНФ [10.4], не во всех случаях оказывается удовлетворительным. В частности, оно неадекватно при выполнении следующих условий.

1. Переменная-отношение имеет два (или более) потенциальных ключа.

2. Эти потенциальные ключи являются составными.

3. Два или более потенциальных ключей перекрываются (т.е. имеют по крайней мере один общий атрибут).

Поэтому впоследствии исходное определение ЗНФ было заменено более строгим определением Бойса-Кодда (Boyce/Codd) [11.2], для которого было установлено собственное название - норма1ьная форма Бойса-Кодда (или НФБК).

Замечание. Комбинация условий 1-3 на практике встречается нечасто, а ЗНФ и НФБК полностью эквивалентны для любой переменной-отношения, в которой эти три условия не выполняются.

На самом деле строгое определение третьей нормальной формы, эквивалентное определению нормальной формы Бойса-Кодда, впервые было дано Хитом (Heath) в 1971 году [11.4] и эту форму следовало бы назвать нормальная фор.ма Хита .