Главная » SQL, Базы данных » ЗАВИСИМОСТИ СОЕДИНЕНИЯ И ПЯТАЯ НОРМАЛЬНАЯ ФОРМА

0

До сих пор в настоящей главе и на протяжении всей предыдущей главы по умолчанию предполагалось, что единственной необходимой или допустимой  операцией в процессе нормализации является замена переменной отношения по  правилам декомпозиции без потерь точно двумя ее проекциями. Такое допущение нас вполне устраивало, пока речь не шла о 4НФ. Однако, хотя это может показаться удивительным, существуют переменные отношения, для которых нельзя выполнить декомпозицию без потерь на две проекции, но которые можно подвергнуть декомпозиции без потерь на три или большее количество проекций.  Подобные переменные отношения обозначим не очень удачным, но достаточно удобным термином "n-декомпонуемая переменная отношения, или отношение". Такое название применяется к переменной отношения, если можно выполнить ее декомпозицию без потерь нап проекций, но не наш проекций, где 1  < m и m < п.

Примечание. Впервые возможность n-декомпонуемости для п > 2 была  упомянута в работе Ахо (Aho), Бери (Beeri) и Ульмана (Ullman) [13.1], а частный случай для п = 3 был описан Николасом (Nicolas) [13.26].

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

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

1.          Три бинарные проекции (SP, PJ и JS), соответствующие значению отношения

SPJ, показанному в верхней части рисунка.

2.          Результат соединения проекций SP и PJ ПО атрибуту р#.

3.          Результат соединения этого результата с проекцией JS по комбинации атрибутов

J#  И  S#.

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

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

Упражнение. Предлагаем читателю проверить это утверждение.

Далее отметим, что представленный на рис. 13.4 пример, безусловно,  выражен в терминах отношений, а не переменных отношения. Однако  3-декомпонуемость переменной отношения SPJ может быть более фундаментальным и не зависящим от  времени свойством (т.е. свойством, которое соблюдается при всех допустимых значениях данной переменной отношения), если данная переменная отношения  удовлетворяет определенному, не зависящему от времени ограничению целостности. Для того чтобы понять,  каким  именно  должно  быть  это  ограничение,  прежде  всего  отметим,  что утверждение "переменная отношения SPJ равна соединению трех своих проекций SP, PJ

и JS", полностью эквивалентно следующему утверждению:

■     если пара ( s 1 ,   p1) присутствует в SP и пара(р1,   j1) присутствует в PJ,    а пара ( j l ,    s1) присутствует в JS,

■     то тройка ( s 1 ,   p1,   j l ) присутствует в SPJ.

Это верно, поскольку очевидно, что тройка (s1, p1, j1) обязательно присутствует в соединении проекций SP, PJ и JS. (Следует отметить, что обратное утверждение, т.е. если тройка (s1, p1, j l )  присутствует в переменной  отношения SPJ, то, например, пара (s1 , p1) присутствует в проекции SP, является истинным для любой переменной отношения SPJ степени три.) Поскольку пара ( s 1 , p1) присутствует в отношении SP тогда и только тогда, когда тройка ( s 1 ,   p1,   j 2 ) присутствует в отношении SPJ для

некоторого значения  j2 (аналогично  для (p1, j l )  и ( j l ,  s1)),  приведенное  выше утверждение можно переписать в виде следующего ограничения,  налагаемого на переменную отношения SPJ:

■     если кортежи (s1,  p1,   j 2 ) , ( s 2 ,   p1,   j l ) , ( s l ,   p2,   jl) присутствуют в SPJ,

■     то кортеж ( s 1 ,   pi,   j 1) также присутствует в SP J.

Если это утверждение выполняется всегда, т.е. для всех допустимых значений переменной отношения SPJ, то будет получено не зависящее от времени (хотя и несколько странное) ограничение для данной переменной отношения. Обратите внимание на циклический характер этого ограничения ("если значение s1 связано с p1 и p1 связано с j 1,  a  j  1  связано  опять  cs l, то sl,pl   и   jl   должны  находиться  в  одном  кортеже"). Переменная отношения будет п-декомпонуемой для п>2 тогда и только тогда, когда она удовлетворяет   некоторому  подобному  циклическому  ограничению  (многостороннему,  с количеством участников п).

Рис. 13.4. Пример значения переменной отношения SPJ, которая может быть получена только в результате соединения всех трех ее бинарных проекций, но не л юбых двух из них

До конца этого раздела будем руководствоваться предположением, что  переменная отношения SPJ действительно удовлетворяет этому не зависящему от времени ограничению (представленный на рис. 13.4 пример данных соответствует такой гипотезе). Такое ограничение будем кратко называть ограничением 3-Д (сокращение от 3-декомпонуемости). Что означает ограничение 3-Д с практической точки зрения? Для получения ответа на этот вопрос рассмотрим пример, в котором под такими ограничениями подразумевается, что если в реальном мире для переменной отношения SP J верны следующие утверждения:

а)  если Смит поставляет гаечные ключи;

б)  гаечные ключи используются в Манхэттенском проекте; в)  Смит является поставщиком для Манхэттенского проекта; то

г)   Смит поставляет гаечные ключи для Манхэттенского проекта.

Обратите внимание на то, что (как уже упоминалось в главе 1, раздел 1.3) из взятых в совокупности утверждений а, б и в обычно не следует утверждение г. Действительно, точно такой же пример был рассмотрен в главе 1 для  демонстрации "дефекта соединения". Однако в данном частном случае следует отметить, что никакого дефекта здесь не возникает, поскольку существует  дополнительное практическое ограничение 3-Д, имеющее место в реальном мире, благодаря чему вывод утверждения г на основе утверждений а, бив является вполне правомочным.

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

■   Зависимость соединения. Пусть R— переменная отношения, а А, B, …,  Z — произвольные подмножества множества ее атрибутов. Переменная  отношения R удовлетворяет следующей зависимости соединения

*{А,    В,    .. .,     Z}

(читается "звездочка А, в, …, Z") тогда и только тогда, когда любое допустимое значение переменной отношения R эквивалентно соединению ее проекций по подмножествам А,   в,   …,   z множества атрибутов.

Например, если использовать сокращенную символьную запись SP для подмножества

{S#, Р#} множества атрибутов переменной отношения SPJ и аналогично  использовать сокращения PJ и JS для двух других подмножеств, то переменная отношения SPJ будет удовлетворять зависимости соединения * {SP,  Р J,  JS}, если соблюдается ограничение 3-Д.

В качестве еще одного примера рассмотрим обычную переменную  отношения  S.

Если принято соглашение об использовании сокращения SN для обозначения  подмножества {S#,SNAME} множества атрибутов S и аналогичное соглашение для ST и SC, то можно сказать, что переменная отношения S удовлетворяет зависимости соединения *{SN, ST, SC}.

Отсюда  ясно,  что  переменная  отношения  SPJ  с  зависимостью  соединения

*{SP,  PJ,  JS}  может  быть  3-декомпонуемой. Однако  возникает  вопрос,  следует  ли выполнять такую декомпозицию? По всей видимости, следует, так как в связи с наличием зависимости соединения переменная отношения SPJ  характеризуется многочисленными аномалиями обновления, которые можно  устранить лишь с помощью ее 3декомпозиции. Некоторые примеры подобных  аномалий показаны на рис. 13.5. Предлагаем читателям в качестве упражнения  самостоятельно ответить на вопрос, что произойдет после выполнения 3-декомпозиции.

Рис. 13.5. Примеры аномалий обновления в переменной отношения SPJ

Теорема Фейгина (которая рассматривалась в разделе 13.2) гласит, что  переменная отношения R{A, в, С} может быть декомпонована без потерь на проекции по атрибутам {А, В} и {А, с} тогда и только тогда, когда для переменной отношения R выполняются многозначные зависимости А →→ В и А →→ С.

Теперь теорема Фейгина может быть сформулирована иначе, как показано ниже.

■   Переменная  отношения  R{A, в,  С} удовлетворяет  зависимости  соединения

*{АВ, АС} тогда и только тогда, когда она удовлетворяет многозначной  зависимости А →→ B | C.

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

Формально получим следующий результат.

А  →→   В    |    С   ≡   *{   АВ,    АС   }

Примечание. Более того, из определения зависимости соединения  непосредственно следует, что это наиболее общая форма зависимости из всех возможных (безусловно, имеется в виду, что термин "зависимость" употребляется в узко специальном смысле). Это означает, что если речь идет о зависимостях, касающихся переменных отношения, которые подвергаются декомпозиции с  помощью операции проекции и обратной композиции с помощью операции соединения проекций, то не существует более высокой степени зависимости, по  отношению к которой зависимость соединения  является всего лишь частным случаем. (Но если ввести другие операции декомпозиции и композиции, то возможно появление других типов зависимостей, которые будут кратко описаны в разделе 13.7.)

Возвращаясь к рассматриваемому примеру, можно отметить, что проблема, связанная с использованием переменной отношения SPJ, состоит в том, что она подчиняется зависимости соединения, которая не является многозначной зависимостью, и поэтому также не является функциональной. {Упражнение. Объясните, почему такая ситуация рассматривается как проблема?) Можно также заметить, что возможно (и даже желательно) декомпоновать такую переменную отношения на меньшие  компоненты, а именно — на проекции, определяемые зависимостью соединения. Данный процесс декомпозиции

может повторяться до тех пор, пока все результирующие переменные отношения не буду!

находиться в пятой нормальной форме. Дадим определение этой нормальной формы.

■  Пятая нормальная форма. Переменная отношения R находится в пятой нормально» форме (5НФ), которую иногда иначе называют проекционно-соединительной нормальной формой (ПСНФ), тогда и только тогда, когда каждая нетривиальная зависимость  соединения  в  переменной  отношения  R определяется  потенциальным ключом (ключами) R, если соблюдаются приведенные ниже условия.

а)  Зависимость соединения *{   А,   в,   …,   z   } в переменной отношения R яв ляется тривиальной тогда и только тогда, когда по крайней мере одно из под множеств А,  в,   …,   z множества атрибутов является множеством всех атри бутов R.

б)  Зависимость соединения *{   А,   в,   …,   Z   } в переменной отношения R оп ределяется потенциальным ключом (ключами) R тогда и только тогда, когда каж

дое из подмножеств А,   B,  …,  Z множества атрибутов является суперключом

для R.

Переменная отношения SPJ не находится в 5НФ. Она удовлетворяет некоторой зависимости соединения, а именно — ограничению 3-Д, которое, безусловно, не определяется ее единственным потенциальным ключом (этот ключ является  комбинацией всех ее атрибутов). Иначе говоря, переменная отношения SPJ не находится в 5НФ, поскольку она может быть 3-декомпонована и возможность такой декомпозиции не обусловлена тем  фактом,  что  комбинация  атрибутов  {s#,  P#,  J#}  является  ее потенциальным ключом. Напротив, после 3-декомпозиции три проекции SP, PJ и JS находятся в 5НФ, поскольку в них вообще нет нетривиальных зависимостей соединения.

Обратите внимание на тот факт, что любая переменная отношения в 5НФ безусловно находится также в 4НФ, поскольку многозначная зависимость является частным случаем

зависимости соединения. Действительно, Фейгин в [13.15] показал, что любая  многозначная зависимость, определяемая потенциальным ключом, на самом деле должна быть функциональной зависимостью, в которой потенциальный ключ  является детерминантом. В той же работе Фейгин показал, что любая  переменная отношения может быть подвергнута декомпозиции без потерь на эквивалентный набор переменных отношения в 5НФ, т.е. 5НФ всегда достижима.

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

*{    {   S#,    SNAME,    STATUS   },    {   S#,    CITY   }    }

Это означает, что переменная отношения S эквивалентна соединению ее проекций по атрибутам {S#, SNAME, STATUS} и {S#, CITY}. Поэтому она может быть подвергнута декомпозиции без потерь на указанные проекции. (Этот факт  означает не то, что она должна подвергаться подобной декомпозиции, а только то, что может быть ей подвергнута.) Существование данной зависимости  соединения предполагается на основании того факта, что атрибут {S#} является потенциальным ключом данной переменной отношения (в действительности, это следует из теоремы Хита [12.4]).

Теперь предположим (как было сделано в разделе 12.5 главы 12), что переменная отношения S имеет второй потенциальный ключ, {SNAME}. В таком случае существует еще одна зависимость соединения, которая удовлетворяется  этой переменной отношения, как показано ниже.

*{ { S#, SNAME }, { S#, STATUS }, { SNAME, CITY } }

Существование этой зависимости соединения обусловлено тем фактом, что оба атрибута, {S#} и {SNAME}, являются потенциальными ключами.

Как следует из приведенных выше примеров, заданная зависимость соединения *{А, В, …, Z} определяется потенциальными ключами тогда и только тогда,  когда каждое подмножество А, B, …, Z множества атрибутов фактически является суперключом для данной  переменной  отношения.  Таким  образом,   относительно  заданной  переменной отношения R можно утверждать, что она находится в 5НФ, только при условии, что известны все ее потенциальные ключи и все зависимости соединения, существующие в ней. Но сама по себе задача определения всех подобных зависимостей соединения может оказаться очень сложной. Это означает, что можно относительно легко определить функциональные и многозначные зависимости (поскольку они имеют довольно  простую интерпретацию в реальном мире), но этого нельзя утверждать по отношению к зависимостям соединения (т.е. к таким зависимостям соединения,  которые не являются многозначными и поэтому функциональными зависимостями), поскольку интуитивный смысл зависимостей соединения не всегда бывает очевидным. Следовательно, процедура определения того, что некоторая переменная отношения все еще находится в 4НФ, а не в 5НФ, и, таким образом, существует возможность ее дальнейшей выгодной декомпозиции, все еще остается не вполне ясной. Однако, как следует из опыта, подобные переменные отношения довольно редко встречаются на практике.

В заключение заметим, что, как следует из определения, 5НФ является окончательной нормальной формой по отношению к операциям проекции и соединения (что отражено в ее альтернативном названии — проекционно-соединительная нормальная форма). Таким образом, если переменная отношения находится в 5НФ, то гарантируется, что она не содержит аномалий, которые могут быть исключены посредством ее разбиения на проекции. (Безусловно, это замечание не означает, что такая переменная отношения свободна от аномалий; еще раз подчеркнем, что это означает отсутствие в ней аномалий, которые могут быть устранены с использованием операции проекции.) Если переменная отношения находится в 5НФ, то единственными в ней являются те  зависимости соединения, которые определяются ее потенциальными ключами, и  тогда единственными допустимыми декомпозициями будут декомпозиции, которые основаны на этих потенциальных ключах. (Каждая проекция в подобной декомпозиции будет состоять из одного или нескольких потенциальных ключей в сочетании с дополнительными атрибутами в количестве от нуля или больше.) Например, переменная отношения поставщиков s находится в 5НФ.  Как  упоминалось  выше,  эта  переменная  отношения  может  быть  подвергнута дальнейшей декомпозиции без потерь, причем в нескольких вариантах, но каждая проекция в любом из этих вариантов по-прежнему будет содержать один из исходных потенциальных ключей. Следовательно, подобная декомпозиция не  даст никаких дополнительных преимуществ.

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

По теме:

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