Связи между отношениями. Внешние ключи. Проблема целостности внешних ключей

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

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

Номер поставщика	Наименование поставщика	Номер детали	Наименование детали	Поставляемое количество
1	Иванов	1	Болт
1	Иванов	2	Гайка
1	Иванов	3	Винт
2	Петров	1	Болт
2	Петров	2	Гайка
3	Сидоров	3	Винт

Таблица "Поставщики и поставляемые детали"

Потенциальным ключом этого отношения может выступать пара атрибутов {"Номер поставщика", "Номер детали"} - в таблице они выделены курсивом.

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

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

Далее, как отразить факт, что некоторый поставщик, например Петров, временно прекратил поставки деталей? Если мы удалим все кортежи, в которых хранится информация о поставках этого поставщика, то мы потеряем данные о самом Петрове как потенциальном поставщике. Выйти из этого положения, оставив в отношении кортеж типа (2, Петров, NULL, NULL, NULL) мы не можем, т.к. атрибут "Номер детали" входит в состав потенциального ключа и не может содержать null-значений. То же самое произойдет, если некоторая деталь временно не поставляется никаким поставщиком. Получается, что мы не можем хранить информацию о том, что есть некий поставщик, если он не поставляет хотя бы одну деталь, и не можем хранить информацию о том, что есть некоторая деталь, если она никем не поставляется.

Подобные проблемы возникают потому, что мы смешали в одном отношении различные объекты предметной области - и данные о поставщиках, и данные о деталях, и данные о поставках деталей. Говорят, что это отношение плохо нормализовано (просто нормализованным оно является хотя бы потому, что оно есть отношение и, следовательно, автоматически находится в 1НФ).

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

Эти фразы отражают различные типы взаимосвязей. Чтобы более точно отразить предметную область, можно иначе переформулировать фразы: " Один Поставщик может выполнять несколько Поставок", " Одна Деталь может поставляться несколькими Поставками". Это пример взаимосвязи типа " один-ко-многим ".

Взаимосвязь между "Поставщиками" и "Деталями" можно переформулировать так: " Несколько Деталей может поставляться несколькими Поставщиками". Это пример взаимосвязи типа " много-ко-многим ".

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

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

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

Номер поставщика	Наименование поставщика
1	Иванов
2	Петров
3	Сидоров

Таблица "Поставщики"

Номер детали	Наименование детали
1	Болт
2	Гайка
3	Винт

Таблица "Детали"

Номер поставщика	Номер детали	Поставляемое количество
1	1
1	2
1	3
2	1
2	2
3	3

Таблица "Поставки"

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

Дадим точное определение.

Определение 2. Пусть дано отношение. Подмножество атрибутов K отношения R₂ будем называть внешним ключом, если:

1. Существует отношение R₁ с потенциальным ключом K.

2. Каждое значение К в отношении R₂ совпадает со значением t(K) для некоторого кортежа t из R₁, либо является null-значением.

Отношение R₁ называется родительским отношением, отношение R₂ называется дочерним отношением.

Замечание. Внешний ключ, также как и потенциальный, может быть простым и составным.

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

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

Замечание. Если внешний ключ все-таки обладает свойством уникальности, то связь между отношениями имеет тип " один-к-одному ". Чаще всего такие отношения объединяются в одно отношение, хотя это и не обязательно.

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

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

Замечание. Null-значения для атрибутов внешнего ключа допустимы только в том случае, когда атрибуты внешнего ключа не входят в состав никакого потенциального ключа

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

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

Замечания к правилам целостности сущностей и внешних ключей

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

Действительно, в определении потенциального ключа требуется, чтобы потенциальный ключ обладал свойством уникальности. Это фактически означает, что мы должны уметь различать значения потенциальных ключей, т.е. при сравнении двух значений потенциального ключа мы всегда должны получать значения либо ИСТИНА, либо ЛОЖЬ. Но любое сравнение, в которое входит null-значение, принимает значение U - НЕИЗВЕСТНО, откуда следует, что атрибуты потенциального ключа не могут содержать null-значений.

Для внешних ключей правило целостности фактически входит в определение (п. 2 определения).

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

Тем не менее, явная формулировка правил целостности имеет определенный практический смысл. В большинстве серьезных СУБД за выполнением этих ограничений следит сама СУБД, если, конечно, пользователь явно объявил потенциальные и внешние ключи. Но, во-первых, для некоторых систем можно допустить, чтобы эти ограничения не выполнялись, а во-вторых, некоторые системы просто не поддерживают понятия целостности, например, некоторые "настольные" СУБД типа FoxPro 2.5. В этих случаях за целостностью данных должен следить сам пользователь, или программист, разрабатывающий приложение для пользователя.

Явная формулировка правил целостности помогает четко понять, какие опасности несет в себе пренебрежение этими правилами.

Операции, могущие нарушить ссылочную целостность

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

Для родительского отношения

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

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

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

Для дочернего отношения

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

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

· Удаление кортежа в дочернем отношении. При удалении кортежа в дочернем отношении ссылочная целостность не нарушается.

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

· Обновление кортежа в родительском отношении.

· Удаление кортежа в родительском отношении.

· Вставка кортежа в дочернее отношение.

· Обновление кортежа в дочернем отношении.

Стратегии поддержания ссылочной целостности

Существуют две основные стратегии поддержания ссылочной целостности:

· RESTRICT (ОГРАНИЧИТЬ) - не разрешать выполнение операции, приводящей к нарушению ссылочной целостности. Это самая простая стратегия, требующая только проверки, имеются ли кортежи в дочернем отношении, связанные с некоторым кортежем в родительском отношении.

· CASCADE (КАСКАДИРОВАТЬ) - разрешить выполнение требуемой операции, но внести при этом необходимые поправки в других отношениях так, чтобы не допустить нарушения ссылочной целостности и сохранить все имеющиеся связи. Изменение начинается в родительском отношении и каскадно выполняется в дочернем отношении. В реализации этой стратегии имеется одна тонкость, заключающаяся в том, что дочернее отношение само может быть родительским для некоторого третьего отношения. При этом может дополнительно потребоваться выполнение какой-либо стратегии и для этой связи и т.д. Если при этом какая-либо из каскадных операций (любого уровня) не может быть выполнена, то необходимо отказаться от первоначальной операции и вернуть базу данных в исходное состояние. Это самая сложная стратегия, но она хороша тем, что при этом не нарушается связь между кортежами родительского и дочернего отношений.

Эти стратегии являются стандартными и присутствуют во всех СУБД, в которых имеется поддержка ссылочной целостности.

3. Функциональные зависимости. Аксиоматическая система функциональных зависимостей. Теорема полноты.

Определения. Пусть A₁,A₂,..., A_n – набор атрибутов с приписанными им доменами D₁, D₂,... D_n. Выражение R= < A₁,A₂,..., A_n > называется схемой атрибутов. Любое отношение r с атрибутами из множества R называется отношением над схемой R (обозначается r = r(R)).

Пусть Q- непустое подмножество R, кортеж t принадлежит отношению r(R), t=<t₁, t₂,..., t_n>. Ограничением кортежа t на множестве Q называется кортеж t(Q), состоящий из тех значений t_i, что iÎQ.

Определение. Пусть множества А, ВÍ R, r – отношение над схемой R. Функциональной зависимостью называется формальное выражение вида A®B. Функциональная зависимость A®B выполняется в отношении r, если

("t, qÎr) t(A)=q(A) ® t(B)=q(B) (2)

Из определения следует, что если К является ключом r, то в r выполнятся функциональная зависимость К®R. Поэтому понятие ключевой зависимости является частным случаем функциональной зависимости.

Рассмотрим в качестве примера отношение Авиарейсы (ПИЛОТ, РЕЙС, ДАТА, ВРЕМЯ ВЫЛЕТА). В этом отношении выполняются следующие ограничения:

1. Для каждого рейса назначается только одно время вылета.

2. Для каждого пилота, времени вылета и даты назначается один рейс.

3. Для каждого рейса и даты назначается один пилот.

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

1. {РЕЙС}®{ВРЕМЯ}

2. {ПИЛОТ, ДАТА, ВРЕМЯ}® {РЕЙС}

3. {РЕЙС, ДАТА}®{ПИЛОТ}

Реляционное исчисление. Задача этой части – построить аксиоматическое исчисление функциональных зависимостей, т.е. описать систему аксиом и правил вывода, позволяющих выводить одни ф.з. из других, причем если в отношении r выполняются исходные, то выполняются и производные зависимости. Наша аксиоматика называется системой Армстронга и состоит из одной аксиомы и 3 правил вывода. Для краткости будем называть функциональные зависимости просто формулами.

Определение. Правило

называется допустимым, если для любого отношения r из того что все формулы из F выполняются в r, следует что формула Aà B также выполняется в r.

В дальнейшем, будем для краткости опускать символ объединения È, записывая объединение просто XZ. Это не даст двусмысленности, поскольку операция пересечения множеств у нас использоваться не будет.

Дата добавления: 2014-01-11