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

НФБК (Нормальная Форма Бойса-Кодда)

При приведении отношений при помощи алгоритма нормализации к отношениям в 3НФ неявно предполагалось, что все отношения содержат один потенциальный ключ. Это не всегда верно. Рассмотрим следующий пример отношения, содержащего два ключа.

и только тогда, когда детерминанты

Определение 1

. Отношение нормальной форме Бойса-Кодда (НФБК) тогда и только тогда, когда детерминанты всех функциональных зависимостей являются потенциальными ключами. Замечание. Если отношение находится в НФБК, то оно автоматически находится и в 3НФ. Действительно, это сразу следует из определения 3НФ. Отношение "Поставки" не находится в НФБК, т.к. имеются зависимости (PNUM PNAME и PNAME PNUM), детерминанты которых не являются потенциальными ключами. Для того чтобы устранить зависимость от детерминантов, не являющихся потенциальными ключами, необходимо провести декомпозицию, вынося эти детерминанты и зависимые от них части в отдельное отношение. Отношения "Поставщики" и "Поставки-2", полученные в результате декомпозиции находятся в НФБК. Замечание. Приведенная декомпозиция отношения "Поставки" на отношения "Поставщики" и "Поставки-2" не является единственно возможной. Альтернативной декомпозицией является декомпозиция на следующие отношения:

и только тогда, когда из

Определение 2

. Пусть , - некоторые из его атрибутов (или непересекающиеся множества атрибутов). Тогда атрибуты (множества атрибутов) многозначно зависят от ), тогда и только тогда, когда из того, что в отношении и содержится также и кортеж кЗамечание. Меняя местами кортежи в определении многозначной зависимости, получим, что в отношении . Таким образом, атрибуты , многозначно зависящие от . В отношении "Абитуриенты-Факультеты-Предметы" имеется многозначная зависимость ФакультетСловами это можно выразить так - для каждого факультета (для каждого значения из ) сдает один и тот же список предметов (набор значений из ) каждый сдаваемый на факультете экзамен (значение из ). Именно наличие этой зависимости не позволяет независимо вставлять и удалять кортежи. Кортежи обязаны вставляться и удаляться одновременно целыми наборами. Замечание. Если в отношении , и есть функциональная зависимость . Действительно, действуя формально в соответствии с определением многозначной зависимости, предположим, что в отношении и отсюда следует, что в точности совпадает с кортежем . Таким образом, имеется многозначная зависимость Таким образом, понятие многозначной зависимости является обобщением понятия функциональной зависимости.

если не существует функциональных зависимостей

Определение 3

. Многозначная зависимость нетривиальной многозначной зависимостью, если не существует функциональных зависимостей . В отношении "Абитуриенты-Факультеты-Предметы" имеется именно нетривиальная многозначная зависимость Факультет

и только тогда, когда отношение

Определение 4

. Отношение четвертой нормальной форме (4НФ) тогда и только тогда, когда отношение находится в НФБК и не содержит нетривиальных многозначных зависимостей. Отношение "Абитуриенты-Факультеты-Предметы" находится в НФБК, но не в 4НФ. Согласно теореме Фейджина, это отношение можно без потерь декомпозировать на отношения:

возможно пересекающимися) подмножествами множества атрибутов

Определение 5

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

Ни одно из множеств атрибутов

Определение 6

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

Либо одно из множеств атрибутов

Определение 7

. Зависимость соединения тривиальной зависимостью соединения, если выполняется одно из условий: Либо все множества атрибутов . Либо одно из множеств атрибутов совпадает со всем множеством атрибутов отношения

и только тогда, когда любая

Определение 8

. Отношение пятой нормальной форме (5НФ) тогда и только тогда, когда любая имеющаяся зависимость соединения является тривиальной. Определения 5НФ может стать более понятным, если сформулировать его в отрицательной форме:

в отношении найдется нетривиальная зависимость

Определение 9

. Отношение 5НФ, если в отношении найдется нетривиальная зависимость соединения. Возвращаясь к примеру 3, становится понятно, что не зная ничего о том, какие потенциальные ключи имеются в отношении и как взаимосвязаны атрибуты, нельзя делать выводы о том, находится ли данное отношение в 5НФ (как, впрочем, и в других нормальных формах). По данному конкретному примеру можно только предположить, что отношение в примере 3 не находится в 5НФ. Предположим, что анализ предметной области позволил выявить следующие зависимости атрибутов в отношении (i) Отношение (ii) Имеется следующая зависимость (довольно странная, с практической точки зрения): если в отношении , , то отсюда следует, что в отношении . Утверждение. Докажем, что при наличии ограничений (i) и (ii), отношение находится в 4НФ, но не в 5НФ. Доказательство. Покажем, что отношение Покажем, что отношение не находится в 5НФ. Для этого нужно привести пример нетривиальной зависимости соединения. Естественным кандидатом на нее является , не совпадает с множеством всех атрибутов отношения Но является ли такая декомпозиция именно зависимостью соединения? Для этого нужно показать, что декомпозиция на три проекции и (именно здесь содержится ключевая тонкость, обычно пропускаемая при анализе конкретного состояния отношения Как и в предыдущих доказательствах, нужно доказать, что . Включение . Докажем включение Пусть кортеж содержится кортеж содержится кортеж содержится кортеж , атрибутов и содержит кортежи и содержится также и кортеж Утверждение доказано.

о поставках деталей некоторыми поставщиками.

Пример 1

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

прежнему необходимо учитывать поставки, но

Пример 2

. Предположим, что нам по- прежнему необходимо учитывать поставки, но каждый акт поставки должен иметь некоторый уникальный номер (назовем его "сквозной номер поставки"). Отношение может иметь следующий вид:

Рассмотрим следующее отношение

Пример 3

Продолжение алгоритма нормализации (приведение к 5НФ)

В предыдущей главе был описан алгоритм нормализации как алгоритм приведения отношений к 3НФ. Теперь мы можем продолжить этот алгоритм, доведя его до алгоритма приведения к 5НФ.

Приведение к НФБК)

Приведение к 4НФ)

Приведение к 5НФ)

Данное отношение содержит два потенциальных

Таблица 1 Отношение "Поставки" Данное отношение содержит два потенциальных ключа - {PNUM, DNUM} и {PNAME, DNUM}. Видно, что данные хранятся в отношении с избыточностью - при изменении наименования поставщика, это наименование нужно изменить во всех кортежах, где оно встречается. Можно ли эту аномалию устранить при помощи алгоритма нормализации, описанного в предыдущей главе? Для этого нужно выявить имеющиеся функциональные зависимости (как обычно, курсивом выделены ключевые атрибуты): PNUM PNAME - наименование поставщика зависит от номера поставщика. PNAME PNUM - номер поставщика зависит от наименования поставщика. {PNUM, DNUM} VOLUME - поставляемое количество зависит от первого ключа отношения. {PNUM, DNUM} PNAME - наименование поставщика зависит от первого ключа отношения. {PNAME, DNUM} VOLUME - поставляемое количество зависит от второго ключа отношения. {PNAME, DNUM} PNUM - номер поставщика зависит от второго ключа отношения. Данное отношение не содержит неключевых атрибутов, зависящих от части сложного ключа (см. определение 2НФ). Действительно, от части сложного ключа зависят атрибуты PNAME и PNUM, но они сами являются ключевыми. Таким образом, отношение находится в 2НФ. Кроме того, отношение не содержит зависимых друг от друга неключевых атрибутов, т.к. неключевой атрибут всего один - VOLUME (см. определение 3НФ). Таким образом, показано, что отношение "Поставки" находится в 3НФ. Таким образом, описанный ранее алгоритм нормализации неприменим к данному отношению. Очевидно, однако, что аномалия данного отношения устраняется путем декомпозиции его на два следующих отношения:

Отношение "Поставщики"

Таблица 2 Отношение "Поставщики"

Отношение "Поставки-2"

Таблица 3 Отношение "Поставки-2"

Отношение "Поставщики"

Таблица 4 Отношение "Поставщики"

На первый взгляд, такая декомпозиция

Таблица 5 Отношение "Поставки-3" На первый взгляд, такая декомпозиция хуже, чем первая. Действительно, наименования поставщиков по-прежнему повторяются, и при изменении наименования поставщика, это наименование придется менять одновременно в нескольких местах (тем более сразу в двух отношениях!). Кажется, что ситуация стала еще хуже, чем была до декомпозиции. Однако такое ощущение возникает от того, что мы интуитивно считаем, что наименования поставщиков могут меняться, а номера - нет. Если же предположить, что номера поставщиков тоже могут меняться (почему бы нет - директор приказал перенумеровать поставщиков!), то первая декомпозиция получается такой же "плохой" как и вторая - повторяющиеся номера придется менять одновременно в нескольких местах и также сразу в двух отношениях. На самом деле никакого противоречия тут нет. В отношении "Поставки-3" атрибут "Наименование поставщика" (PNAME) является внешним ключом, служащим для связи с отношением "Поставщики". Поэтому, при изменении наименования поставщика, это изменение производится в отношении "Поставщики" и каскадно (см. стратегии поддержания ссылочной целостности в гл. 3) распространяется на отношение "Поставки-3" совершенно так, как изменение номера поставщика каскадно распространяется на отношение "Поставки-2". Поэтому, формально обе декомпозиции совершенно равноправны. В реальной работе разработчик выберет, конечно, первую декомпозицию, но тут важно подчеркнуть, что его выбор основан совсем на других соображениях, не имеющих отношения к формальной теории нормальных форм. Замечание. Отношение "Поставки-2", полученное в результате декомпозиции имеет всего один потенциальный ключ. Поэтому, для анализа отношения "Поставки-2" не требуется привлекать определение НФБК, достаточно определения 3НФ. Хотя отношение "Поставщики" имеет два потенциальных ключа, но, т.к. других атрибутов в нем нет, оно уже так просто устроено, что упростить его дальше нельзя. Возникает вопрос, имеются ли нетривиальные примеры отношений в НФБК, не находящиеся в 3НФ и не такие простые, как отношение "Поставщики"?

Одним потенциальным ключом данного отношения

Декомпозиция отношения и .

Замечание. Если зависимость или

Доказательство теоремы.

Необходимость. Пусть декомпозиция отношения и .

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

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

Как и в доказательстве теоремы Хеза, нужно доказать, что .

Включение .

Докажем включение . Это означает, что в проекции , а в проекции . По определению проекции, найдется такое значение , что отношение . Аналогично, найдется такое значение , что отношение . Тогда по определению многозначной зависимости кортеж Достаточность доказана.

Теорема Фейджина (другая формулировка)

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

Обобщением 3НФ на случай, когда

---

---