Запрещается дублирование кортежей в отношении

3.3. Ограничения целостности

Отношения реляционной модели данных должны удовлетворять следующим правилам:

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

Это правило требует пояснения. Вернемся к отношению Соревнования из раздела 3.1. Согласно правилу целостности по ссылкам, значения атрибута Номер_билета отношения Соревнования должны либо совпадать с каким-нибудь значением атрибута Номер_билета отношения Студент, либо быть неопределенными. Это означает, что участником соревнований может быть только человек, являющийся студентом, т. е. информация о нем должна быть в отношении Студент. Если участник соревнований пока неизвестен или никто из студентов не будет участвовать в этом виде соревнований, тогда это поле остается пустым. Но в этом поле не должно быть значения, которого нет в отношении Студент.

3.4. Нормализация отношений

3.4.1. Аномалии схемы отношения

После того как построена схема отношений, являющаяся моделью данных, при ее использовании могут возникнуть некоторые нежелательные эффекты. Например, мы построили отношение Поставка(Товар, Поставщик, Адрес, Цена, Склад, Объем). Это отношение содержит информацию о наличии различных товаров, поставляемых несколькими поставщиками в некоторый магазин, и размещении их на складах магазина. Для каждого поставщика хранится его адрес, а для каждого склада – его объем. Цена товара зависит от поставщика. Один и тот же товар, поставленный одним поставщиком, целиком хранится на одном складе.

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

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

Такая же ситуация характерна для информации о складе и его объеме: если склад опустошается, то теряются данные о его объеме.

Эти проблемы называются аномалиями обновления.

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

Решением этих проблем было бы разделение отношения Поставка на несколько других отношений: Склад(Номер, Объем), Поставщик(Название, Адрес), Товар(Наименование, Поставщик, Цена, Склад). В отношении Товар атрибут Поставщик будет внешним ключом, ссылающимся на отношение Поставщик, а атрибут Склад будет внешним ключом, ссылающимся на отношение Склад.

Эти действия по разделению одного отношения на несколько отношений называются декомпозицией.

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

По каким правилам проводить декомпозицию?
Как оценить, хорошая получилась схема или плохая?

3.4.2. Функциональные зависимости

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

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

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

адрес функционально зависит от поставщика,
цена функционально зависит от товара и поставщика,
номер склада функционально зависит от товара и поставщика,
объем функционально зависит от номера склада.

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

Пусть отношение r имеет схему R, X и Y – подмножества R. Отношение r удовлетворяет функциональной зависимости X→Y, если π_Y(σ_X=x(r)) имеет не более чем один кортеж для каждого значения xX, т. е. значения атрибутов X однозначно определяют значения атрибутов Y.

Функциональную зависимость будем обозначать следующим образом:

Поставщик → Адрес,
{Товар, Поставщик}→ Цена,
{Товар, Поставщик}→ Склад,
Склад → Объем.

А читаются они так:

Поставщик определяет Адрес,
Товар и Поставщик определяют Цену,
Товар и Поставщик определяют Склад,
Склад определяет Объем.

На языке функциональных зависимостей ключ для схемы R – это подмножество KR, такое, что K→R, и никакое собственное подмножество KK этим свойством не обладает.

3.4.3. Нормальные формы

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

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

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

Например, атрибут ФИО является составным, состоит из трех данных: фамилии, имени и отчества.

Чтобы привести схему в 1НФ, нужно все составные атрибуты заменить простыми.

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

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

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

Например, в отношении Поставка первичными атрибутами являются Товар и Поставщик. Атрибут Цена функционально полно зависит от ключа, а атрибут Адрес зависит от части ключа, т. е. только от атрибута Поставщик, это неполная функциональная зависимость. Значит, схема Поставки не находится во 2НФ.

Чтобы привести схему, находящуюся в 1НФ, ко 2НФ, нужно разбить ее на несколько схем:

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

В примере с отношением Поставки в результате приведения схемы ко 2НФ получатся два отношения:

Поставки_1(Товар, Поставщик, Цена, Склад, Объем),

Поставки_2(Поставщик, Адрес).

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

Схема отношения R находится в третьей нормальной форме (3НФ), если она находится во второй нормальной форме и в ней отсутствуют транзитивные зависимости непервичных атрибутов от ключа.

Что такое транзитивные зависимости? Транзитивная зависимость имеет место, если какой-либо непервичный атрибут функционально зависит от другого непервичного атрибута, а тот в свою очередь функционально зависит от ключа.

Схема отношения Поставки_1(Товар, Поставщик, Цена, Склад, Объем) не находится в 3НФ, так как в ней присутствует транзитивная зависимость:

{Товар, Поставщик} → Склад, Склад → Объем.

Чтобы привести схему, находящуюся во 2НФ, в 3НФ, нужно:

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

В примере с отношением Поставки_1 в результате приведения схемы к 3НФ получатся два отношения:

Поставки_1_1(Товар, Поставщик, Цена, Склад),

Поставки_1_2(Склад, Объем).

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

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

В рассмотренном примере в результате декомпозиции вместо одного отношения Поставки мы получили три новых отношения:

Поставки_1_1(Товар, Поставщик, Цена, Склад),

Поставки_1_2(Склад, Объем),

Поставки_2(Поставщик, Адрес).

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

Как вы заметили, схема в 3НФ избавляет базу данных от дублирования информации и аномалий обновления, но не всегда.

Рассмотрим отношение Лекции(Студент, Предмет, Преподаватель), которое хранит информацию о том, какие предметы изучают студенты и кто ведет эти предметы. Предметная область накладывает следующие ограничения:

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

Из этих ограничений вытекают следующие функциональные зависимости:

{Студент, Предмет} → Преподаватель;
Преподаватель → Предмет.

Из функциональных зависимостей вытекает, что ключом отношения Лекции будет набор атрибутов {Студент, Предмет}.

	Лекции
Студент	Предмет	Преподаватель
Иванов	Алгебра	проф. Белый
Иванов	Физика	проф. Яров
Петров	Алгебра	проф. Белый
Петров	Физика	проф. Серов

Отношение Лекции находится в 3НФ. Но оно страдает аномалиями обновления. Если требуется удалить информацию о том, что Петров изучает Физику, то утратится информация о том, что профессор Серов преподает Физику. В то же время информация о том, что профессор Белый ведет Алгебру, дублируется.

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

Отношение находится в нормальной форме Бойса–Кодда (НФБК), если оно находится в 3НФ и в нем отсутствуют зависимости первичных атрибутов от непервичных. Эквивалентное определение требует, чтобы все левые части функциональных зависимостей были потенциальными ключами.

Приведя отношение к НФБК, мы получим два отношения: Лекции_1(Студент, Преподаватель) и Лекции_2(Преподаватель, Предмет).

Лекции_1		Лекции_2
Студент	Преподаватель	Преподаватель	Предмет
Иванов	проф. Белый	проф. Белый	Алгебра
Иванов	проф. Яров	проф. Яров	Физика
Петров	проф. Белый	проф. Серов	Физика
Петров	проф. Серов

3.4.4. Многозначные зависимости

Атрибут X многозначно определяет атрибут Y в R (или Y многозначно зависит от X), если каждому значению атрибута X соответствует множество (возможно, пустое) значений атрибута Y, никак не связанных с другими атрибутами R. То есть для наличия в отношении многозначной зависимости необходимо иметь как минимум три атрибута.

Многозначная зависимость обозначается двойной стрелкой: X→→Y.

Рассмотрим отношение Преподаватель(Номер, Имя_ребенка, Предмет, Должность). Предметная область накладывает следующие ограничения:

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

Тогда отношение Преподаватель имеет две многозначные зависимости и одну функциональную:

Номер→→Имя_ребенка,
Номер→→Предмет,
Номер→Должность.

Преподаватель
Номер	Имя_ребенка	Предмет	Должность
111	Ольга	Алгебра	Доцент
111	Иван	Геометрия	Доцент
111	Ольга	Геометрия	Доцент
111	Иван	Алгебра	Доцент
115	Сергей	Алгебра	Профессор

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

Для избавления от этих аномалий необходимо привести отношение к четвертой нормальной форме.

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

После приведения отношения Преподаватель к 4НФ мы получим три отношения:

Преподаватель_1(Номер, Должность),

Преподаватель_2(Номер, Имя_ребенка),

Преподаватель_3(Номер, Предмет).

Преподаватель_1		Преподаватель_2		Преподаватель_3
Номер	Должность	Номер	Имя_ре-бенка	Номер	Предмет
111	Доцент	111	Ольга	111	Алгебра
115	Профессор	111	Иван	111	Геометрия
		115	Сергей	115	Алгебра

3.4.5. Свойства декомпозиции

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

Пусть исходная схема R с множеством функциональных зависимостей F была приведена в результате декомпозиции к схеме отношений R_1, R_2, … , R_k с множеством функциональных зависимостей F₁, F₂, … , F_k.

Декомпозиция обладает свойством соединения без потерь, если любое отношение r со схемой R удовлетворяет соотношению:

r(R) = π_R_{_1}(r)  π_R_{_2}(r)  π_R_{_3}(r)  …  π_{R_k}(r).

Декомпозиция обладает свойством сохранения зависимостей, если из объединения всех зависимостей F₁, F₂, … , F_k можно вывести все зависимости F.

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

Теорема Всякая схема отношения R с множеством функциональных зависимостей F может быть приведена к декомпозиции в 3НФ с сохранением зависимостей и соединением без потерь.

Теорема Всякая схема отношения R с множеством функциональных зависимостей F и множеством многозначных зависимостей M может быть приведена к декомпозиции в 4НФ с соединением без потерь.

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

3.5. Построение реляционной модели данных

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

Построить схемы отношения для классов объектов.

Для каждого класса объектов сформировать отдельное отношение, атрибутами которого будут свойства этого класса. Например, для объекта Студент можно составить следующую схему отношения:

Студент(ФИО, Курс, Год_рождения, Номер).

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

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

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

Например, связь между классами Студент и Группа выльется в следующее отношение:

Группы(Студент, Номер_группы),

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

Во втором примере для связи между классами Товар и Поставщик схема отношения будет иметь следующий вид:

Поставки(Товар, Поставщик, Дата, Количество).

Это связь вида «многие-ко-многим», следовательно, в ключ должны входить и атрибут Товар и атрибут Поставщик. Но один и тот же поставщик может поставлять один и тот же товар несколько раз, следовательно, двух атрибутов для ключа недостаточно. Если в предметной области определено такое ограничение, что в один и тот же день поставщик не может поставить один и тот же товар, то тогда ключом будут три атрибута {Товар, Поставщик, Дата}. Если же этого ограничения нет, то в этом случае даже всех атрибутов будет недостаточно для определения ключа и необходимо ввести искусственный ключ (например, Номер_поставки или т. п.).

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

При таком построении модели данных – из модели предметной области – отношения чаще всего будут сразу находиться в 3НФ. Исключением могут быть только составные атрибуты, нарушающие условия 1НФ, но, исправив их, вы получите 3НФ.
Конечно, схема может получиться неоптимальной; например, связь, относящуюся к типу «один-ко-многим», в некоторых случаях бывает удобным не оставлять как отдельное отношение, а включить в схему отношения для класса объекта, который входил в связь со стороны «многие». Однако при перестроении схемы будьте внимательны, могут быть нарушены условия одной из нормальных форм.