ВВЕДЕНИЕ В СИСТЕМЫ УПРАВЛЕНИЯ БАЗАМИ ДАННЫХ
1942e8f8

НФ (Четвертая Нормальная Форма)


Рассмотрим следующий пример. Пусть требуется учитывать данные об абитуриентах, поступающих в ВУЗ. При анализе предметной области были выделены следующие требования:

  • Каждый абитуриент имеет право сдавать экзамены на несколько факультетов одновременно.
  • Каждый факультет имеет свой список сдаваемых предметов.
  • Один и тот же предмет может сдаваться на нескольких факультетах.
  • Абитуриент обязан сдавать все предметы, указанные для факультета, на который он поступает, несмотря на то, что он, может быть, уже сдавал такие же предметы на другом факультете.

    Предположим, что нам требуется хранить данные о том, какие предметы должен сдавать каждый абитуриент. Попытаемся хранить данные в одном отношении "Абитуриенты-Факультеты-Предметы":

    Абитуриент

    Факультет

    Предмет



    Иванов Математический Математика
    Иванов Математический Информатика
    Иванов Физический Математика
    Иванов Физический Физика
    Петров Математический Математика
    Петров Математический Информатика

    Таблица 7 Отношение "Абитуриенты-Факультеты-Предметы"

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

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

    Номер

    Абитуриента

    Номер

    Факультета

    Номер

    Предмета

    1 1 1
    1 1 2
    1 2 1
    1 2 3
    2 1 1
    2 1 2

    Таблица 8 Модифицированное отношение "Абитуриенты-Факультеты-Предметы"

    Номер

    Абитуриента

    Абитуриент

    1 Иванов
    2 Петров
    <
    Таблица 9 Отношение "Абитуриенты"


    Номер

    Факультета
    Факультет


    1 Математический
    2 Физический

    Таблица 10 Отношение "Факультеты"


    Номер

    Предмета
    Предмет



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

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


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


    Однако Фейджином Р. [52] доказана следующая теорема:
    Теорема (Фейджина). Пусть
    ,
    ,
    - непересекающиеся множества атрибутов отношения
    .
    Декомпозиция отношения
    на проекции
    и
    будет декомпозицией без потерь тогда и только тогда, когда имеется многозначная зависимость
    .
    Замечание. Если зависимость
    является тривиальной, т.е. существует одна из функциональных зависимостей
    или
    , то получаем теорему Хеза.
    Доказательство теоремы.
    Необходимость. Пусть декомпозиция отношения
    на проекции
    и
    является декомпозицией без потерь. Докажем что
    .
    Предположим, что отношение
    содержит кортежи
    и
    . Необходимо доказать, что кортеж
    также содержится в
    . По определению проекций, кортеж
    содержится в
    , а кортеж
    содержится в
    . Тогда кортеж
    содержится в естественном соединении
    , а в силу того, что декомпозиция является декомпозицией без потерь, этот кортеж содержится и в
    . Необходимость доказана.
    Достаточность. Пусть имеется многозначная зависимость
    . Докажем, что декомпозиция отношения
    на проекции
    и
    является декомпозицией без потерь.
    Как и в доказательстве теоремы Хеза, нужно доказать, что
    для любого состояния отношения
    .
    Включение
    доказывается как в теореме Хеза. Такое включение выполняется всегда для любой декомпозиции отношения
    .
    Докажем включение
    . Пусть кортеж
    . Это означает, что в проекции
    содержится кортеж
    , а в проекции
    содержится кортеж
    . По определению проекции, найдется такое значение
    атрибута
    , что отношение
    содержит кортеж
    . Аналогично, найдется такое значение
    атрибута
    , что отношение
    содержит кортеж
    . Тогда по определению многозначной зависимости кортеж
    . Включение доказано. Достаточность доказана. Теорема доказана.
    Определение 4. Отношение
    находится в четвертой нормальной форме (4НФ) тогда и только тогда, когда отношение находится в НФБК и не содержит нетривиальных многозначных зависимостей.
    Отношение "Абитуриенты-Факультеты-Предметы" находится в НФБК, но не в 4НФ. Согласно теореме Фейджина, это отношение можно без потерь декомпозировать на отношения:




    Факультет
    Абитуриент



    Математический Иванов
    Физический Иванов
    Математический Петров

    Таблица 12 Отношение "Факультеты-Абитуриенты"


    Факультет
    Предмет




    Математический Математика
    Математический Информатика
    Физический Математика
    Физический Физика

    Таблица 13 Отношение "Факультеты-Предметы"
    В полученных отношениях устранены аномалии вставки и удаления, характерные для отношения "Абитуриенты-Факультеты-Предметы".
    Заметим, что полученные отношения остались полностью ключевыми, и в них по-прежнему нет функциональных зависимостей.
    Отношения с нетривиальными многозначными зависимостями возникают, как правило, в результате естественного соединения двух отношений по общему полю, которое не является ключевым ни в одном из отношений. Фактически это приводит к попытке хранить в одном отношении информацию о двух независимых сущностях. В качестве еще одного примера можно привести ситуацию, когда сотрудник может иметь много работ и много детей. Хранение информации о работах и детях в одном отношении приводит к возникновению нетривиальной многозначной зависимости Работник
    Работа|Дети.

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