Главная » SQL, Базы данных » Дальнейшая нормализация: нормальные формы более высокого порядка

0

МНОГОЗНАЧНЫЕ ЗАВИСИМОСТИ И ЧЕТВЕРТАЯ НОРМАЛЬНАЯ ФОРМА

Пусть дана переменная отношения нстх (где н сокращенно обозначает "иерархический" — hierarchic), содержащая информацию о курсах обучения, преподавателях и учебниках. В этой переменной отношения атрибуты, описывающие преподавателей и учебники, принимают в качестве значений отношения (пример значения НСТХ приведен на рис. 13.1). Каждый кортеж переменной отношения НСТХ состоит из атрибута с названиями курсов (COURSE), a также атрибута-отношения с именами преподавателей (TEACHERS) и атрибута-отношения с названиями учебников (TEXTS) (на рис. 13.1 показаны два таких кортежа). Смысл каждого кортежа состоит в том, что соответствующий курс может читать любой из указанных преподавателей с использованием всех указанных учебников. Предположим, что для заданного курса с  может быть определено произвольное количество соответствующих преподавателей  m  и учебников п (m > 0n п  > 0). Более того, допустим, хотя этой не совсем реально, что преподаватели и рекомендуемые учебники совершенно не связаны друг с другом. Это означает, что независимо от того, кто преподает данный курс, всегда используется один и тот же набор учебников. Наконец, допустим, что определенный преподаватель или определенный учебник может быть связан с любым количеством курсов.

Пусть необходимо (как в разделе 12.6 главы 12) исключить атрибуты, принимающие отношения в качестве значений. Один из способов выполнения этого (но, возможно, не самый лучший; к этой теме мы вернемся в конце данного раздела) заключается в простой замене переменной отношения НСТХ переменной отношения  СТХ с тремя скалярными атрибутами, COURSE, TEACHER и TEXT, как показано на рис. 13.2. Как видно из этого рисунка, каждый кортеж исходной переменной отношения нстх порождает т * п кортежей в переменной отношения СТХ, где т и п являются значениями кардинальности для отношений TEACHERS и TEXTS в данном кортеже переменной отношения НСТХ. Обратите внимание на то, что все атрибуты результирующей переменной отношения СТХ входят в состав ее ключа (в отличие от переменной отношения нстх, потенциальный ключ которой {COURSE} состоял из единственного атрибута).

Упражнение. Составьте реляционное выражение, с помощью которого можно получить переменную отношения стх из НСТХ.

Рис. 13.2. Набор значений данных в переменной отношения СТХ, эквивалентный

Рис. 13.1. Пример значений данных в переменной отношения НСТХ

приведенному на рис. 13.1 примеру значений данных в переменной отношения НСТХ

Данные, введенные в переменную отношения стх, имеют следующий смысл: кортеж ( с , t, х) (в упрощенной системе обозначений) появляется в переменной отношения СТХ тогда и только тогда, когда курс с читается преподавателем t с использованием учебника х. Затем, принимая во внимание то, что для каждого курса указаны все возможные комбинации имен преподавателей и названий учебников, можно утверждать, что для переменной отношения стх верно следующее ограничение.

ЕСЛИ                                          кортежи (c,t l, xl ) и (c,t 2, x 2 ) присутствуют одновременно,

ТО                                                                                  кортежи (с, t1, х2) и (с, t2 , xl) также присутствуют одновременно.

Очевидно, что переменная отношения СТХ характеризуется значительной избыточностью, а это, как обычно, приводит к некоторым аномалиям обновления. Например, для добавления информации о том, что курс физики может читаться новым преподавателем, необходимо вставить два отдельных кортежа,  по  одному для каждого используемого учебника. Как можно избежать появления таких проблем? Вполне очевидно, что указанные проблемы вызваны тем фактом, что данные о преподавателях и учебниках полностью независимы друг от друга. Кроме того, легко обнаружить, что положение дел может быть улучшено путем  декомпозиции переменной отношения стх на две ее проекции (например, с именами ст и сх), соответственно, по атрибутам {COURSE,   TEACHER} и

{COURSE, TEXT} (рис. 13.3).

Рис. 13.3. Значения данных переменных отношения СТ и СХ, которые соответствуют содержанию переменной отношения СТХ, показанному на рис. 13.2

Если база данных имеет проект, показанный на рис. 13.3, то для добавления  новой информации о том, что курс физики будет читаться новым преподавателем, достаточно вставить единственный кортеж в переменную отношения ст. (Отметим также, что переменная отношения СТХ может быть восстановлена за счет обратного соединения проекций ст и сх, и потому данная декомпозиция  выполнена без потерь.) Таким образом, вполне разумно было бы  предположить,  что для переменных отношения, подобных CTX, существует некий способ "дальнейшей нормализации".

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

В связи с этим с неформальной точки зрения очевидно, что переменная отношения СТХ спроектирована плохо и ее декомпозиция на проекции ст и сх является более удачным решением. Но проблема в данном случае заключается в том, что с формальной точки зрения это совсем не очевидно. Заметим, в частности, что переменная отношения стх вообще не имеет функциональных зависимостей (за исключением таких тривиальных, как COURSE →  COURSE). Фактически переменная отношения СТХ находится1  в НФБК, поскольку, как отмечалось ранее, все ее атрибуты входят в состав ее ключа, а любая подобная переменная отношения обязательно находится в НФБК. (Обратите внимание на то, что и проекции ст и сх являются полностью ключевыми, а потому также находятся в НФБК.) Следовательно, изложенные в предыдущей главе идеи никак не могут помочь в разрешении этой проблемы.

"Проблемы", которые связаны с переменными отношения в НФБК, подобными переменной отношения стх, были замечены достаточно давно, и способы их разрешения

1 Переменная отношения НСТХ также находится в НФБК, а фактически она дополнительно находится и в 4НФ, и в 5НФ

(определенияэтихнормальныхформприведенынижевданнойглаве).

также были вскоре после этого определены, по крайней мере, на интуитивном  уровне. Однако эти идеи были сформулированы Фейгином (Fagin) в строгом теоретическом виде с использованием понятия многозначной зависимости, или  МЗЗ, только в 1977 году [13.14]. Многозначную зависимость можно считать обобщением понятия функциональной зависимости в том смысле, что каждая функциональная зависимость является также многозначной зависимостью, но обратное утверждение неверно (поскольку существуют многозначные  зависимости,  которые не являются функциональными). В случае переменной отношения СТХ имеют место две следующие многозначные зависимости.

COURSE →→  TEACHER COURSE  →→  TEXT

Обратите внимание на двойную стрелку, которая в многозначной зависимости А →→ B означает, что в многозначно зависит от А или А многозначно определяет в. Вначале рассмотрим первую из этих зависимостей, COURSE  →→ TEACHER. На интуитивном уровне она означает, что, хотя для каждого курса не существует одного соответствующего только ему преподавателя, т.е. не выполняется функциональная зависимость COURSE → TEACHER, каждый курс имеет вполне определенное множество соответствующих преподавателей. Если говорить точнее, под понятием "вполне определенное множество" в нашем случае подразумевается, что для данного курса с и данного учебника х множество преподавателей t, соответствующее паре ( с , х) переменной отношения СТХ, зависит только от значения с, поскольку не имеет значения, какой именно  учебник х будет выбран. Вторая многозначная зависимость, COURSE   →→ TEXT, имеет аналогичную интерпретацию.

Ниже приведено формальное определение понятия многозначной зависимости.

■  Многозначная зависимость. Пусть R переменная отношения, а А, в и с являются произвольными подмножествами множества атрибутов переменной  отношения R. Тогда подмножество в многозначно зависит от подмножества А, что символически выражается следующей записью

А   →→                                        В

(читается как "А многозначно определяет в" или "А двойная стрелка в"), тогда и только тогда, когда в каждом допустимом значении R множество значений в, соответствующее заданной паре значений А, с, зависит только от значения А и не зависит от значения с.

Нетрудно показать (это описано в работе Фейгина [13.14]), что для данной переменной отношения R{A, в, С} многозначная зависимость А→→ B  выполняется тогда и только тогда, когда выполняется также многозначная зависимость А →→ С. Таким образом, многозначные зависимости  всегда  образуют связанные пары, поэтому обычно их представляют вместе в символическом виде, как показано ниже.

А     →→ В    |    С

Для рассматриваемого примера подобная запись будет иметь следующий вид.

COURSE   →→ TEACHER   |   TEXT

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

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

Теперь, возвращаясь к исходной задаче с переменной отношения стх, можно  отметить следующее: описанная ранее проблема с переменными отношения  этого  типа возникает из-за того, что они содержат многозначные зависимости,  которые не являются функциональными. (Следует отметить совсем неочевидный  факт, что именно наличие таких МЗЗ требует вставки двух кортежей, когда необходимо добавить сведения о новом преподавателе физики. Данные два кортежа необходимы для поддержания ограничения целостности, представленного этой МЗЗ.) Проекции ст и сх не содержат многозначных зависимостей, а потому  они действительно представляют собой определенное усовершенствование  исходной структуры. Поэтому было бы желательно заменить исходную переменную отношения стх двумя рассматриваемыми проекциями. Такое действие  будет правомочным в соответствии с теоремой Фейгина [13.14], которая приведена ниже.

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

(Обратите внимание, что эта теорема является более строгой версией теоремы  Хита [12.4], которая описана в главе 12.) Теперь, следуя работе Фейгина [13.14],  можно дать определение четвертой нормальной формы. (Эта нормальная форма  получила такое название потому, что в момент ее появления НФБК все еще считалась третьей нормальной формой, как отмечено в главе 12.)

■     Четвертая нормальная форма. Переменная отношения R находится в четвертой нормальной форме (4НФ) тогда и только тогда, когда в случае существования таких подмножеств А И В  атрибутов этой переменной отношения R, для которых выпол няется нетривиальная многозначная зависимость А →→ в, все атрибуты пере менной отношения R также функционально зависят от атрибута А.

Примечание. Многозначная зависимость А →→ в является тривиальной, если А является надмножеством в или объединение АВ атрибутов А И В  составляет весь заголовок.

Иначе  говоря,  единственные  нетривиальные  зависимости  (функциональные   или многозначные) в переменной отношения R находятся в форме K —> X (т.е. имеет место функциональная зависимость некоторого другого атрибута х от  определенного суперключа к). Это можно также сформулировать в следующей эквивалентной форме: переменная отношения R находится в 4НФ тогда и только тогда, когда она находится в НФБК и все многозначные зависимости в переменной  отношения R фактически представляют собой функциональные зависимости от ее ключей. Обратите внимание на то, что, исходя из этого определения, нахождение  в 4НФ предполагает обязательное нахождение в НФБК.

Переменная отношения CTX не находится в 4НФ, поскольку содержит многозначную зависимость, которая вообще не является функциональной, не говоря уже о том, что последняя должна быть еще и функциональной зависимостью от ключа. Однако обе ее проекции, СТ и CX, находятся в 4НФ. Следовательно, 4НФ обеспечивает лучшую структуру

данных по сравнению с НФБК, поскольку позволяет исключить некоторые нежелательные зависимости. Кроме того, в [13.14] Фейгин показал, что 4НФ всегда является достижимой, т.е. любая переменная отношения может быть  подвергнута декомпозиции без потерь в эквивалентный набор переменных отношения в 4НФ. Однако, как показано в разделе 12.5 главы 12 на примере переменной отношения SJT, такая декомпозиция (или даже декомпозиция до НФБК) не всегда оказывается полезной и нужной.

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

R{A, B, C}, удовлетворяющую функциональным зависимостям А —> B и B —> C, желательно разбивать на проекции по атрибутам {А, B} и {В, С}, а не на  проекции по атрибутам {А, B} и {А, С}. Это утверждение также будет верно,  если вместо функциональных зависимостей А →B и B → с использовать многозначные зависимости А   →→ В    и    В    →→ С.

В заключение, как было обещано, вернемся к вопросу об устранении  атрибутов  со

значениями в виде отношений, или сокращенно АО (атрибутов-отношений). Суть в том,

что если приходится иметь дело с переменной отношения наподобие НСТХ,  которая включает один или несколько независимых АО, то вместо простой  замены этих АО

скалярными атрибутами (как было сделано в начале данного раздела), а затем выполнения декомпозиции без потерь полученного результата, лучше вначале разделить эти АО. Например, в случае переменной отношения НСТХ прежде всего следует  заменить исходную переменную отношения двумя ее проекциями нет {COURSE, TEACHERS} и

нсх{COURSE, TEXTS}, где атрибуты TEACHERS и TEXTS все еще относятся к типу  АО. Далее эти АО можно будет исключить из двух полученных проекций (с приведением их к НФБК, а фактически к 4НФ) обычным способом, и тогда "проблема", свойственная находящейся в НФБК переменной отношения CTX, просто никогда не возникнет. Как видите, понятия многозначных зависимостей и 4НФ предоставляют формальное обоснование тех способов усовершенствования  проекта, которые в противном случае были бы

основаны исключительно на эмпирических правилах.

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

По теме:

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