122

так как их неключевые атрибуты ИМЯ_СТУДЕНТА, ФАКУЛЬТЕТ и ОЦЕНКА зависят от первичных ключей этих отношений, соответственно, {КОД_СТУДЕНТА} и {КОД_СТУДЕНТА, ДИСЦИПЛИНА} неприводимо.

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

Еще раз обращаем внимание на то, что декомпозиция эта осуществляется без потерь информации. Исходное отношение ЭКЗАМЕН (рис.10.8) всегда может быть восстановлено путем соединения двух выходных отношений СТУДЕНТЫ и УСПЕВАЕМОСТЬ (рис.10.9) по их общему атрибуту

КОД_СТУДЕНТА.

10.5. Третья нормальная форма.

Рассмотрим следующий пример. Представим себе, что требуется хранить в базе данных информацию о том, в каком общежитии живет студент с указанием адреса общежития. Для этих целей можно ввести следующие атрибуты: КОД_СТУДЕНТА, ОБЩЕЖИТИЕ и АДРЕС. Между указанными атрибутами имеют место функциональные зависимости, представленные на рис.10.11.

КОД_СТУДЕНТА ОБЩЕЖИТИЕ АДРЕС

Рис. 10.11. Диаграмма функциональных зависимостей между атрибутами

КОД_СТУДЕНТА, ОБЩЕЖИТИЕ и АДРЕС

Эти функциональные зависимости означают тот факт, что студент может жить только в одном общежитии и у общежития может быть только один адрес.

Для хранения рассматриваемой информации может быть использовано отношение СТУДЕНТ_ОБЩЕЖИТИЕ_АДРЕС, приведенное на рис.10.12.

123

СТУДЕНТ_ОБЩЕЖИТИЕ_АДРЕС

Рис. 10.12. Отношение СТУДЕНТ_ОБЩЕЖИТИЕ_АДРЕС

Это отношение находятся во второй нормальной форме. Действительно, как это видно из диаграммы на рис.10.11, между его неключевыми атрибутами ОБЩЕЖИТИЕ и АДРЕС и ключом отношения, которым является атрибут

КОД_СТУДЕНТА имеет место неприводимая функциональная зависимость.

Поэтому, в данном отношении не может быть аномалий, связанных с наличием

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

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

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

Операция DELETE. При удалении информации о проживающих в общежитии студентах можно потерять информацию об адресе общежития. Например, при удалении кортежа для студента с кодом С9 мы теряем информацию об адресе общежития №2.

Операция UPDATE. Дублирование информации об адресах общежитий приводит к тому, что в случае переименования названия улицы, на которой расположено общежитие, необходимо внести изменения в адрес общежития для всех проживающих в нем студентов. При некорректном завершении такой операции в отношении могут оказаться кортежи с противоречивой информацией – для одного общежития два значения адреса, что противоречит имеющей место функциональной зависимости атрибута АДРЕС от атрибута

ОБЩЕЖИТИЕ (см. рис. 10.11).

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

126

ОБЩЕЖИТИЕ→АДРЕС, имеющая место в исходном преобразуемом отношении

СТУДЕНТ_ОБЩЕЖИТИЕ_АДРЕС.

В предыдущем варианте декомпозиция устраняла транзитивную функциональную зависимость, при этом информация не терялась, так как эта зависимость может быть выведена из оставшихся по правилам Армстронга (см. раздел 10.1). В рассматриваемом же варианте вместо транзитивной зависимости была потеряна зависимость ОБЩЕЖИТИЕ→АДРЕС, которая не выводится из остальных. Необходимость поддержания в базе данных такой зависимости делает в этом случае возможные изменения значений атрибутов ОБЩЕЖИТИЕ и АДРЕС, теперь находящихся в разных отношениях зависимыми друг от друга.

Действительно, при изменении значения атрибута ОБЩЕЖИТИЕ в какомлибо кортеже отношения СТУДЕНТ_ОБЩЕЖИТИЕ, мы должны произвести соответствующие изменения атрибута АДРЕС в отношении СТУДЕНТ_АДРЕС. Следовательно, необходимость поддержания функциональной зависимости ОБЩЕЖИТИЕ→АДРЕС из зависимости между атрибутами одного отношения, превратилась в ограничение целостности, накладываемое на два отношения и реализуемое гораздо более сложно.

При первом же варианте декомпозиции, представленном на рис.10.14, функциональная зависимость ОБЩЕЖИТИЕ→АДРЕС, порождающая в отношении СТУДЕНТ_ОБЩЕЖИТИЕ_АДРЕС нежелательную транзитивную зависимость СТУДЕНТ→АДРЕС преобразуется в отношении ОБЩЕЖИТИЕ_АДРЕС в функциональную зависимость атрибута от первичного ключа. Ограничение целостности, задаваемое такой зависимостью в этом случае привести в действие гораздо проще. Оно автоматически обеспечивается путем наложение ограничений на уникальность первичного ключа.

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

Риссанен (Rissanen) показал следующее

Проекции R1 и R2 отношения R независимы в рассмотренном выше смысле тогда и только тогда, когда:

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

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

Второй вариант декомпозиции отношения СТУДЕНТ_ОБЩЕЖИТИЕ_АДРЕС, представленный на рис.10.15 не удовлетворяет правилу Риссанена, поэтому функциональная зависимость ОБЩЕЖИТИЕ→АДРЕС, имеющая место в отношении СТУДЕНТ_ОБЩЕЖИТИЕ_АДРЕС не может быть выведена из

127

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

СТУДЕНТ_ОБЩЕЖИТИЕ и СТУДЕНТ_ АДРЕС.

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

10.6.Нормальная форма Бойса-Кодда

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

•отношение может иметь два или более потенциальных ключа;

•потенциальные ключи могут быть не простыми, а составными, то есть включать в себя несколько атрибутов;

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

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

нормальной формы Бойса-Кодда или сокращенно НФБК. (Хотя Дейт [1]

отмечает, что определение этой нормальной формы впервые в 1971 году было дано Хезом (Heath)).

Определение нормальной формы Бойса-Кодда (НФБК)

128

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

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

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

Можно обратить внимание на то, что приведенное определение нормальной формы Бойса-Кодда не использует явных ссылок на первую,

вторую и третью нормальные формы, а также на транзитивную

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

нормальную форму Бойса-Кодда.

Рассмотрим теперь вопросы, связанные с нормальной формы Бойса-Кодда на примерах.

Пример 1.

Возвращаясь к отношению ЭКЗАМЕН на рис. 10.8, которое находится в первой и не находится во второй нормальной форме, можно убедиться, что отношение не находится в НФБК. Действительно, его детерминантами являются простой атрибут КОД_СТУДЕНТА и составной атрибут {КОД_СТУДЕНТА, ДИСЦИПЛИНА}. Из этих двух детерминантов только {КОД_СТУДЕНТА, ДИСЦИПЛИНА} является потенциальным ключом отношения.

Пример 2.

Отношение СТУДЕНТ_ОБЩЕЖИТИЕ_АДРЕС на рис.10.12, которое находится во второй, но не находится в третьей нормальной форме, также не находится в НФБК, так как его детерминантами являются атрибут КОД_СТУДЕНТА и атрибут ОБЩЕЖИТИЕ, из которых только атрибут КОД_СТУДЕНТА является ключом отношения.

Пример 3.

Отношения СТУДЕНТ и УСПЕВАЕМОСТЬ, представленные на рис.10.9, и

отношения СТУДЕНТ_ОБЩЕЖИТИЕ и ОБЩЕЖИТИЕ_АДРЕС на рис.10.14,

которые, как мы знаем, находятся в третьей нормальной форме, также находятся и в НФБК. Действительно, их детерминанты, а именно составной атрибут {КОД_СТУДЕНТА, ДИСЦИПЛИНА} в отношении УСПЕВАЕМОСТЬ,

129

атрибут КОД_СТУДЕНТА в отношениях СТУДЕНТ и СТУДЕНТ_ОБЩЕЖИТИЕ,

атрибут ОБЩЕЖИТИЕ в ОБЩЕЖИТИЕ_АДРЕС одновременно являются и ключами этих отношений.

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

третьей нормальной форме эквивалентно его нахождению в нормальной форме Бойса-Кодда.

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

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

Пример 4.

Рассмотрим отношение, диаграмма функциональных зависимостей которого имеет следующий вид.

КОД_СТУДЕНТА ФИО

ПАСПОРТ АДРЕС

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

Как видно из этой диаграммы, это отношение, в отличие от рассматриваемых ранее, имеет два потенциальных ключа. Это – атрибуты КОД_СТУДЕНТ и ПАСПОРТ, от которых все остальные атрибуты, включая и их самих, зависят функционально. Это отношение находится во второй и третьей нормальных формах, так как в нем отсутствуют неприводимые слева функциональные зависимости неключевых атрибутов от потенциальных ключей и отсутствуют транзитивные зависимости.

Это отношение находится также и в нормальной форме Бойса-Кодда. Действительно, детерминантами в этом отношении являются атрибуты КОД_СТУДЕНТ и ПАСПОРТ, которые одновременно являются и потенциальными ключами данного отношения.

Приведенный пример иллюстрирует тот факт, что само по себе наличие в отношении нескольких потенциальных ключей не приводит к неэквивалентности третьей нормальной формы и нормальной формы Бойса-

Кодда.

И, наконец, обратим внимание на следующий пример.

130

Пример 5.

УСПЕВАЕМОСТЬ_ПАСПОРТ

Рис.10.17. Отношение с двумя перекрывающимися потенциальными ключами

Пусть в этом отношении имеют место следующие функциональные зависимости.

КОД_СТУДЕНТА ДИСЦИПЛИНА

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

Как видно из этих зависимостей, отношение имеет два потенциальных ключа. Ими являются составные атрибуты {КОД_СТУДЕНТА, ДИСЦИПЛИНА} и {ПАСПОРТ, ДИСЦИПЛИНА}. Обращаем внимание на то, что ключи эти являются перекрывающимися, так как атрибут ДИСЦИПЛИНА входит в состав обоих ключей.

Представленное отношение находится в третьей нормальной форме, так как его единственный неключевой атрибут ОЦЕНКА зависит от обоих ключей неприводимо, и в отношении отсутствуют транзитивные функциональные зависимости.

132

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

В рассматриваемом случае возможен и другой вариант декомпозиции, представленный на рис.10.21.

Рис.10.21. Другой вариант декомпозиции отношения на рис.10.17.

Можно убедиться, что каждое из отношений, представленных на рис.10.19 – 10.21, уже находится в нормальной форме Бойса-Кодда, и в них отсутствуют аномалии операций обновления данных.

Пример 6.

Пусть дано отношение со следующим набором атрибутов

{КОД_СТУДЕНТА, ДИСЦИПЛИНА, ОЦЕНКА, НОМЕР_БИЛЕТА}.

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

{КОД_СТУДЕНТА, ДИСЦИПЛИНА} → {НОМЕР_БИЛЕТА}, {ДИСЦИПЛИНА, НОМЕР_БИЛЕТА} → {КОД_СТУДЕНТА}, {КОД_СТУДЕНТА, ДИСЦИПЛИНА} → {ОЦЕНКА}, {ДИСЦИПЛИНА, НОМЕР_БИЛЕТА} → {ОЦЕНКА}.