Главная » SQL, Базы данных » НОРМАЛЬНАЯ ФОРМА БОЙСА-КОДДА

0

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

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

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

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

Поэтому впоследствии исходное определение ЗНФ было заменено более строгим определением Бойса—Кодда (Воусе—Codd) [12.2]. А поскольку это  новое определение фактически задает нормальную форму, которая во всех отношениях сильнее по сравнению со старой ЗНФ, для нее было установлено собственное название10 — нормальная форма Бойса—Кодда (или НФБК).

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

Для  объяснения  концепции  НФБК необходимо  снова  воспользоваться  понятием детерминанта, введенным в главе 11 для обозначения левой части некоторой функциональной  зависимости,  а  также  понятием  тривиальной  функциональной  зависимости,

которое обозначает такую ФЗ, левая часть которой является надмножеством правой части. Дадим определение НФБК.

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

■      Нормальная форма Бойса—Кодца. Переменная отношения находится в нормальной форме Бойса-Кодда тогда и только тогда, когда каждая ее нетривиальная и неприводимая слева функциональная зависимость имеет в качестве своего детерминанта некоторый потенциальный ключ.

Можно дать и другой, менее формальный вариант этого определения.

■  Нормальная форма Бойса—Кодда {неформальное определение). Переменная отношения находится в нормальной форме Бойса—Кодда тогда и только тогда, когда детерминанты всех ее ФЗ являются потенциальными ключами.

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

Примечание. Различие между двумя приведенными определениями НФБК состоит в том, что в менее формальном из них неявно подразумевается, что  детерминанты "не слишком велики" и все ФЗ нетривиальны. Для простоты изложения далее в этой главе будут использованы такие же допущения, за исключением особо оговоренных случаев.

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

Прежде чем рассматривать примеры переменных отношения с несколькими потенциальными ключами, покажем, что переменные отношения FIRST и SECOND, которые не находятся в ЗНФ, не находятся также в НФБК. Кроме того,  покажем, что переменные отношения SP, SC и CS, которые находятся в ЗНФ, находятся также в НФБК. Переменная отношения FIRST содержит три детерминанта, а именно — S#, CITY и {S#, Р#}, из которых  только  {S#,  P#}  является  ее  потенциальным  ключом.  Поэтому  переменная

отношения FIRST не находится в НФБК. Аналогичное утверждение верно для переменной отношения SECOND, поскольку детерминант CITY не является ее  потенциальным ключом. С другой стороны, переменные отношения SP, SC и CS находятся в НФБК, поскольку в каждом случае единственный потенциальный  ключ является единственным детерминантом для данной переменной отношения.

Теперь рассмотрим пример, содержащий два отдельных (т.е.  неперекрывающихся)

потенциальных  ключа.  Допустим,  что  в  переменной  отношения поставщиков  S{S#, SNAME, STATUS, CITY} множества атрибутов {S#} и {SNAME} являются  ее потенциальными ключами (т.е. в этом случае каждый поставщик имеет уникальный номер и уникальное имя). Также предположим (как, впрочем, и  всюду в этой книге), что атрибуты STATUS и CITY являются взаимно  независимыми, т.е. введенная выше просто для раскрытия  темы  раздела  12.3  функциональная  зависимость  CITY→  STATUS  больше  не соблюдается.  Тогда диаграмма функциональных зависимостей будет иметь вид, представленный на рис. 12.12.

Рис. 12.12. Диаграмма функциональных зависимостей в переменной отношения S для случая, ко  : гда   множество   атрибутов    {SNAME}   является   ее потенциальным   ключом   (и   зависимость CITY—> STATUS не выполняется)

Можно видеть, что переменная отношения S находится в НФБК. Хотя ее диаграмма ФЗ существенно "сложнее" диаграммы ФЗ для переменной отношения  в ЗНФ, в этом случае все детерминанты являются потенциальными ключами,  поскольку все стрелки начинаются с потенциальных ключей. Таким образом, из данного примера можно сделать вывод, что наличие нескольких потенциальных ключей не обязательно должно рассматриваться как признак плохого проекта.

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

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

В первом примере снова примем предположение, что имена поставщиков уникальны,

и рассмотрим переменную отношения.

SSP   {   S#,    SNAME,    P#,   QTY   }

Потенциальными  ключами  в  ней  являются  множества  атрибутов  {S#,  P#}  и

{SNAME, P#}. Однако эта переменная отношения не находится в НФБК, так  как  она содержит два детерминанта, s# и SNAME, которые не являются ее потенциальными ключами (и {S#}, и {SNAME} —детерминанты, поскольку они определяют друг друга). Пример значения переменной отношения SSP показан на рис. 12.13.

Рис. 12.13. Пример значения переменной отношения SSP (показан не полностью)

Согласно этому рисунку, переменной отношения SSP свойственна некоторая  доля избыточности, как и переменным отношения FIRST И SECOND (CM. раздел 12.3), а также переменной отношения SCP (см. раздел 12.1), поэтому при ее использовании возникают такие же проблемы, которые были характерными для последних. Например, для изменения имени поставщика, имеющего номер S1, со Smith на Robinson необходимо найти

все относящиеся к нему кортежи, поскольку в противном случае база данных перейдет в противоречивое состояние. Тем не менее, переменная отношения SSP находится в ЗНФ, поскольку согласно старому определению не требуется, чтобы атрибут был неприводимо зависим от каждого потенциального ключа, если он сам является компонентом некоторого потенциального ключа данной переменной отношения. В результате тот факт, что атрибут SNAME приводимо зависим от атрибутов {S#, Р#}, данным определением игнорируется.

Примечание. Под термином ЗНФ здесь подразумевается определение, данное Коддом в [ 11.6], а не упрощенное определение, данное нами в разделе 12.3.

Для решения указанной проблемы переменную отношения SSP следует разбить на две проекции, как показано ниже.

SS  {  S#,   SNAME

} SP   {   S#,    P#, QTY   }

Однако можно выбрать и альтернативный вариант разбиения.

SS  {  S#,   SNAME  }

SP  {  SNAME,   P#,   QTY  }

Обратите внимание, что в этом примере показаны два варианта декомпозиции, и оба они в равной степени являются допустимыми, поскольку все входящие в них проекции находятся в НФБК.

Здесь следует сделать небольшое отступление и пояснить, что же происходит "в действительности". Ясно, что исходный вариант, состоящий из одной переменной отношения SSP, неудачен и возникающие в связи с этим проблемы вполне очевидны. Маловероятно, чтобы подобный проект предложил более или менее  опытный разработчик баз данных, даже если он совершенно незнаком с концепцией НФБК (и т.д.). Простой здравый смысл подскажет нам, что вариант с двумя переменными отношения SS и SP, несомненно, лучше. Но что в данном случае  подразумевается под "здравым смыслом" и какими

принципами должен руководствоваться разработчик, отдавая предпочтение  варианту с

переменными отношения SS и SP, а не варианту с переменной отношения SSP?

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

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

Рассмотрим переменную отношения SJT с атрибутами s, J и т, которые  обозначают, соответственно, студента, изучаемый предмет и преподавателя. Смысл каждого кортежа (s, j , t) переменной отношения SJT (в сокращенной системе обозначений) состоит в том, что некоторый студент s изучает некоторый предмет j на лекциях некоторого преподавателя t. При этом на информацию налагаются следующие два ограничения.

■     Каждый студент изучает определенный предмет только у одного преподавателя.

■     Каждый преподаватель ведет только один предмет, но каждый предмет ведут не сколько преподавателей.

На рис. 12.14 показан пример значения переменной отношения SJT.

Рис. 12.14. Пример значения переменной отношения SJT

Какие функциональные зависимости существуют в этой переменной отношения? Из первого ограничения следует функциональная зависимость {S, J} → т, а из второго — функциональная зависимость Т → J. Наконец,  сам  факт, что каждый предмет ведут несколько преподавателей, говорит о том,  что функциональная зависимость J → т не соблюдается.  Следовательно,  диаграмма  функциональных  зависимостей  переменной отношения SJT будет иметь вид, представленный на рис. 12.15.

Рис. 12.15. Диаграмма функциональных зависимостей в переменной отношения SJT

И вновь в рассматриваемом примере присутствуют два перекрывающихся  потенциальных ключа, а именно множество атрибутов {S, J} и множество атрибутов {S, Т}. Как и в первом примере, исходная переменная отношения SJT находится в ЗНФ, но не в НФБК, в связи с чем для нее будут характерны  некоторые аномалии обновления. Например, если потребуется удалить сведения о том, что студент Джонс (Jones) изучает физику, этого нельзя будет сделать, не утратив одновременно информацию о том, что профессор Браун (Prof . Brown) преподает этот предмет. Подобные трудности вызваны тем, что атрибут т является детерминантом, но не является потенциальным ключом. И вновь для решения указанной проблемы исходную переменную отношения SJT следует разбить на две проекции, каждая из которых будет находиться в НФБК.

ST  {  S,   Т  }

TJ   {   Т,    J   }

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

Однако следует отметить, что все еще существует иная проблема. Суть ее в том, что декомпозиция исходного отношения на проекции ST и TJ позволяет  исключить одни аномалии, но приводит к появлению других. Причиной является тот факт, что проекции ST и TJ не являются независимыми в том смысле, который был указан Риссаненом (см. раздел 12.4). Точнее говоря, функциональная зависимость

{S,    J}   →   Т

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

Т  →  J

В результате две полученные проекции не могут обновляться независимо. Например, попытка вставить в переменную отношения ST кортеж для студента  Смита (Smith) и профессора Брауна (Prof . Brown) должна быть отвергнута  системой, поскольку профессор Браун преподает физику, а Смит уже  обучается физике у профессора Грина (Prof. Green). Однако система не может обнаружить этот факт, не проверив содержимое переменной отношения TJ. Таким образом, мы пришли к неприятному выводу о том, что попытка достижения двух целей (а именно декомпозиции исходной переменной отношения на переменные  отношения, находящиеся в НФБК, и декомпозиции исходной переменной отношения на независимые компоненты) в некоторых случаях может привести к конфликтной ситуации. Поэтому достичь обеих целей одновременно не всегда возможно.

Изучив этот пример более внимательно, можно обнаружить, что в действительности переменная отношения s JT с точки зрения трактовки, предложенной Риссаненом, является атомарной (см. раздел 12.4) даже несмотря на то, что она не находится в НФБК. Поэтому тот факт, что атомарная  переменная  отношения не может быть подвергнута декомпозиции на независимые компоненты, отнюдь не означает, что она вообще не может быть подвергнута декомпозиции (здесь под "декомпозицией" понимается декомпозиция без потерь). Таким образом, интуитивные соображения подсказывают, что  концепцию атомарности нельзя назвать очень продуктивной, поскольку  атомарность переменных отношения не может служить необходимым или достаточным условием создания хорошего проекта базы данных.

В качестве третьего и последнего примера переменной отношения с перекрывающимися потенциальными ключами рассмотрим переменную отношения EXAM с атрибутами S (студент), J (предмет) и Р (позиция). Каждый кортеж (s, j , р) переменной отношения EXAM отражает сведения о том, что некоторый студент s экзаменуется по определенному предмету j и занимает определенную позицию р в экзаменационной ведомости. Дополнительно условимся, что в нашем примере имеет место следующее ограничение.

■     Никакие два студента не могут занимать одну и ту же позицию в экзаменационной ведомости, которая относится к одному и тому же предмету.

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

Рис. 12.16. Диаграмма функциональных зависимостей в переменной отношения

EXAM

В этом примере вновь присутствуют два перекрывающихся потенциальных ключа,

{S, J } H {J,  P},  поскольку для каждого студента и предмета существует точно  одна занимаемая позиция в соответствующем списке, а в каждом списке экзаменующихся по некоторому предмету каждую позицию занимает только один соответствующий студент.

Однако такая переменная отношения находится в НФБК, поскольку указанные  потенциальные ключи являются ее единственными детерминантами. Поэтому для  данной переменной  отношения  не  характерны  какие-либо  аномалии  обновления,  подобные упоминавшимся ранее в настоящей главе. {Упражнение.  Проверьте правильность этого утверждения.) Таким образом, наличие  перекрывающихся потенциальных ключей не всегда приводит к появлению проблем подобного рода.

В заключение следует подчеркнуть, что концепция НФБК позволяет  избавиться  от

проблем, которые присущи формам, соответствующим старому определению  ЗНФ. Более того, новое определение концептуально проще старого, так как в нем не используются понятия 1НФ, 2НФ, первичного ключа или транзитивной зависимости. Дополнительно понятие потенциального ключа может быть  заменено ссылкой на более фундаментальное понятие функциональной зависимости (в определении, данном в [12.2], имеет

место именно такая замена). С другой стороны, концепции первичного ключа, транзитивной зависимости и т.д. весьма полезны на практике, поскольку позволяют наметить схему некоторого пошагового процесса, выполняемого разработчиком  для приведения произвольной переменной отношения к эквивалентному набору переменных отношения в НФБК.

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

быть подвергнута декомпозиции без потерь на множество D проекций НФБК (но при этом не обязательно сохраняются все зависимости).

1.  Инициализировать множество D так, чтобы в нем содержалась только переменная отношения R.

2.  Для каждой переменной отношения т из множества D, не находящейся в НФБК,

выполнить шаги 3 и 4.

3.  Пусть X —> Y является функциональной зависимостью для т, которая нарушает требования НФБК.

4.  Заменить переменную отношения т из множества D двумя ее проекциями: по ат рибутам X и Y и по всем атрибутам, кроме тех, что находятся BY.

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

По теме:

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