Теперь каждое наименование встречается только

Пример 11

Номер
Предмета Предмет

1	Математика
2	Информатика
3	Физика

Таблица 11 Отношение "Предметы"

Теперь каждое наименование встречается только в одном месте.

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

Аномалия вставки. При попытке добавить в отношение "Абитуриенты-Факультеты-Предметы" новый кортеж, например (Сидоров, Математический, Математика), мы обязаны добавить также и кортеж (Сидоров, Математический, Информатика), т.к. все абитуриенты математического факультета обязаны иметь один и тот же список сдаваемых предметов. Соответственно, при попытке вставить в модифицированное отношении кортеж (3, 1, 1), мы обязаны вставить в него также и кортеж (3, 1, 2).

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

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

Кроме того, если мы удалим кортеж (Иванов, Физический, Математика), а вместе с ним и кортеж (Иванов, Физический, Физика), то будет потеряна информация о предметах, которые должны сдаваться на физическом факультете.

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

Определение 2. Пусть

- отношение, и , , - некоторые из его атрибутов (или непересекающиеся множества атрибутов).

Тогда атрибуты (множества атрибутов)

и многозначно зависят от (обозначается ), тогда и только тогда, когда из того, что в отношении содержатся кортежи и следует, что в отношении содержится также и кортеж к.

Замечание. Меняя местами кортежи

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

В отношении "Абитуриенты-Факультеты-Предметы" имеется многозначная зависимость Факультет

Абитуриент|Предмет.

Словами это можно выразить так - для каждого факультета (для каждого значения из

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

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

имеется не менее трех атрибутов , , и есть функциональная зависимость , то есть и многозначная зависимость .

Действительно, действуя формально в соответствии с определением многозначной зависимости, предположим, что в отношении

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

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

Определение 3. Многозначная зависимость

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

В отношении "Абитуриенты-Факультеты-Предметы" имеется именно нетривиальная многозначная зависимость Факультет

Абитуриент|Предмет. В силу нетривиальности этой зависимости мы не можем воспользоваться теоремой Хеза для декомпозиции отношения. Однако Фейджином Р. [52] доказана следующая теорема:

Теорема (Фейджина). Пусть

, , - непересекающиеся множества атрибутов отношения.

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

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

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

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

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

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

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

Предположим, что отношение

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

Достаточность. Пусть имеется многозначная зависимость

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

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

для любого состояния отношения .

Включение

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

Докажем включение

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

Определение 4. Отношение

находится в четвертой нормальной форме (4НФ) тогда и только тогда, когда отношение находится в НФБК и не содержит нетривиальных многозначных зависимостей.

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

Содержание раздела

---

---

Главная сайта

---