Главная » SQL, Базы данных » СОХРАНЕНИЕ ЗАВИСИМОСТЕЙ

0

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

8  Из этого следует, что комбинация переменных отношения "SECOND—SP" немного лучше представляет реальный мир по сравнению с переменной отношения FIRST, находящейся в 1НФ, а комбинация переменных отношения "SC-CS" — немного лучше по сравнению с переменной отношения SECOND, находящейся в2НФ.

476     Часть III. Проектирование базы данных

зависимостями S# CITY и CITY STATUS и, следовательно, с еще одной транзитивной зависимостью S#  →STATUS   (на  рис.  12.11  эта  транзитивная   зависимость показана пунктирной стрелкой). В разделе 12.3 отмечалось, что  аномалии обновления, характерные для переменной отношения SECOND, можно предотвратить посредством ее декомпозиции с последующей заменой двумя проекциями в ЗНФ.

Рис. 12.11. Функциональные зависимости в переменной отношения SECOND SC   {   S#,   CITY   }

CS { CITY, STATUS }

Назовем эту декомпозицию "декомпозицией А". Ниже приведен еще один  вариант декомпозиции (декомпозиция в).

SC { S#, CITY } SS { S#, STATUS }

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

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

9Еслинеучитыватьограничениессылочнойцелостности,котороесвязываетмеждусобойпеременныеотношения SC и CS.

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

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

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

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

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

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

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

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

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

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

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

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

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

Тем не менее, существует эффективный метод проверки того, будет ли декомпозиция выполняться с сохранением зависимостей. Описание всех нюансов этого алгоритма выходит за рамки данной главы, но заинтересованный читатель сможет найти его в [8.13].

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

1.  Инициализировать D значением пустого множества.

2.  Пусть I является неприводимым покрытием для S.

3.  Пусть х — множество атрибутов, присутствующих в левой части некоторой функ циональной зависимости X → У из I.

4.  Пусть полным множеством функциональных зависимостей из I с левой частью X

является X → Y1,X Y2,…,X Yn.

5.  Пусть объединением Yl,   Y2,   …,   Yn является z.

6.  Заменить множество D объединением множества D и проекции R по X и z.

7.  Повторить шаги 4—6 для каждого отдельного X.

8.  Пусть Al,   A2,    …,   An являются теми атрибутами R (если только они вообще имеются), которые все еще не охвачены этим алгоритмом (т.е. не включены ни в одну переменную отношения из D); заменить множество D объединением множе ства D и проекции R по А1,  А2,  …,  An.

9.  Если ни одна переменная отношения из D не включает некоторый потенциальный ключ переменной отношения R, заменить D объединением D и проекции R по рас сматриваемому потенциальному ключу переменной  отношения R.

Источник: Дейт К. Дж., Введение в системы баз данных, 8-е издание.: Пер. с англ. — М.: Издательский дом «Вильямс», 2005. — 1328 с.: ил. — Парал. тит. англ.

По теме:

  • Комментарии