Транзитивное замыкание отношения



Таблица 6
Конструкция Где используется

Болт Двигатель
Болт Колесо
Гайка Двигатель
Гайка Колесо
Двигатель Автомобиль
Колесо Автомобиль
Ось Колесо
Болт Автомобиль
Гайка Автомобиль
Ось Автомобиль

Таблица 6 Транзитивное замыкание отношения R Очевидный смысл замыкания



Таблица 6
Номер поставщика Наименование поставщика Номер детали Наименование детали Поставляемое количество
1 Иванов 1 Болт 100
1 Иванов 2 Гайка 200
1 Иванов 3 Винт 300
2 Петров 1 Болт 150
2 Петров 2 Гайка 250
3 Сидоров 3 Винт 1000

Таблица 5 Отношение "Поставщики и поставляемые детали" Потенциальным ключом этого отношения может выступать пара атрибутов {"Номер поставщика", "Номер детали"} - в таблице они выделены курсивом. Приведенный способ хранения данных обладает рядом недостатков. Что произойдет, если изменилось наименование поставщика? Т.к. наименование поставщика повторяется во многих кортежах отношения, то это наименование нужно одновременно изменить во всех кортежах, где оно встречается, иначе данные станут противоречивыми. То же самое с наименованиями деталей. Значит, данные хранятся в нашем отношении с большой избыточностью. Далее, как отразить факт, что некоторый поставщик, например Петров, временно прекратил поставки деталей? Если мы удалим все кортежи, в которых хранится информация о поставках этого поставщика, то мы потеряем данные о самом Петрове как потенциальном поставщике. Выйти из этого положения, оставив в отношении кортеж типа (2, Петров, NULL, NULL, NULL) мы не можем, т.к. атрибут "Номер детали" входит в состав потенциального ключа и не может содержать null-значений. То же самое произойдет, если некоторая деталь временно не поставляется никаким поставщиком. Получается, что мы не можем хранить информацию о том, что есть некий поставщик, если он не поставляет хотя бы одну деталь, и не можем хранить информацию о том, что есть некоторая деталь, если она никем не поставляется. Подобные проблемы возникают потому, что мы смешали в одном отношении различные объекты предметной области - и данные о поставщиках, и данные о деталях, и данные о поставках деталей. Говорят, что это отношение плохо нормализовано (просто нормализованным оно является хотя бы потому, что оно есть отношение и, следовательно, автоматически находится в 1НФ). О том, как правильно нормализовать отношения, будет сказано в следующих главах, сейчас же предложим разнести данные по трем отношениям - "Поставщики", "Детали", "Поставки". Для нас важно выяснить, каким образом данные, хранящиеся в этих отношениях взаимосвязаны друг с другом. Эта связь определяется семантикой предметной области и описывается фразами: "Поставщики выполняют Поставки", "Детали поставляются через Поставки". Эти две взаимосвязи косвенно определяют новую взаимосвязь между "Поставщиками" и "Деталями": "Детали поставляются Поставщиками". Эти фразы отражают различные типы взаимосвязей. Чтобы более точно отразить предметную область, можно иначе переформулировать фразы: "Один Поставщик может выполнять несколько Поставок", "Одна Деталь может поставляться несколькими Поставками". Это пример взаимосвязи типа "один-ко-многим". Взаимосвязь между "Поставщиками" и "Деталями" можно переформулировать так: "Несколько Деталей может поставляться несколькими Поставщиками". Это пример взаимосвязи типа "много-ко-многим". В реляционных базах данных основными являются взаимосвязи типа "один-ко-многим". Взаимосвязи типа "много-ко-многим" реализуются использованием нескольких взаимосвязей типа "один-ко-многим". Отношение, входящее в связь со стороны "один" (например, "Поставщики"), называют родительским отношением. Отношение, входящее в связь со стороны "много" (например, "Поставки"), называется дочернем отношением. Механизм реализации взаимосвязи "один-ко-многим" состоит в том, что в дочернее отношение добавляются атрибуты, являющиеся ссылками на ключевые атрибуты родительского отношения. Эти атрибуты и являются внешними ключами, определяющими, с какими кортежами родительского отношения связаны кортежи дочернего отношения. Такие атрибуты еще называют мигрирующими из родительского отношения. Таким образом, наш пример с поставщиками и поставляемыми деталями должен выглядеть следующим образом:





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

Таблица 6 Отношение A (Поставщики)



Таблица 6

PNUM PNAME DNUM DNAME
1 Иванов 1 Болт
1 Иванов 2 Гайка
1 Иванов 3 Винт
2 Петров 1 Болт
2 Петров 2 Гайка
2 Петров 3 Винт
3 Сидоров 1 Болт
3 Сидоров 2 Гайка
3 Сидоров 3 Винт
Замечание. Т.к. не указано условие соединения таблиц, то каждая строка первой таблицы соединится с каждой строкой второй таблицы.



Таблица 6
Н_ОТД ТЕЛ
1 11-22-33
2 33-22-11

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



Таблица 6

Номер поставщика
PNUMНомер детали
DNUMПоставляемое количество
VOLUMEСквозной номер поставки

NN
1 1 100 1
1 2 200 2
1 3 300 3
2 1 150 4
2 2 250 5
3 1 1000 6

Таблица 6 Отношение "Поставки-с-номером" Одним потенциальным ключом данного отношения является, как и раньше, пара атрибутов {PNUM, DNUM}. Другим ключом, в силу уникальности сквозного номера, является атрибут NN. В данном отношении имеются следующие функциональные зависимости: Зависимость атрибутов от первого ключа отношения: {PNUM, DNUM} VOLUME, {PNUM, DNUM} NN, Зависимость атрибутов от второго ключа отношения: NN PNUM, NN DNUM, NN VOLUME, Зависимости, являющиеся следствием зависимостей от ключей отношения: {PNUM, DNUM} VOLUME, NN}, NN {PNUM, DNUM}, NN {PNUM, VOLUME}, NN {DNUM, VOLUME}, NN {PNUM, DNUM, VOLUME}. Как можно заметить, детерминанты всех зависимостей являются потенциальными ключами, поэтому данное отношение находится в НФБК. Особенностью данного отношения является то, что оно имеет два совершенно независимых потенциальных ключа.



Таблица 6

MATCH отсутствует MATCH FULL MATCH PARTIAL
Колонки X и Y таблицы B допускают null-значения Колонки X и Y таблицы B не допускают null-значений
1 строка - допустима, совпадает с 1 строкой таблицы A.
2 строка - допустима, не совпадает ни с чем.
3 строка - допустима, не совпадает ни с чем.
4 строка - допустима, не совпадает ни с чем.
5 строка - не допустима.
1 строка - допустима, совпадает с 1 строкой таблицы A.
2 строка - не допустима.
3 строка - не допустима.
4 строка - не допустима.
5 строка - не допустима.
1 строка - допустима, совпадает с 1 строкой таблицы A.
2 строка - не допустима.
3 строка - не допустима.
4 строка - допустима, не совпадает ни с чем.
5 строка - не допустима.
1 строка - допустима, совпадает с 1 строкой таблицы A.
2 строка - не допустима.
3 строка - не допустима.
4 строка - не допустима.
5 строка - не допустима.
1 строка - допустима, совпадает с 1 строкой таблицы A.
2 строка - допустима, неуникально совпадает с 1 и 2 строками таблицы A.
3 строка - допустима, уникально совпадает с 3 строкой таблицы A.
4 строка - допустима, не совпадает ни с чем.
5 строка - не допустима.
1 строка - допустима, совпадает с 1 строкой таблицы A.
2 строка - не допустима.
3 строка - не допустима.
4 строка - не допустима.
5 строка - не допустима.
Предложение MATCH игнорируется, если все столбцы внешнего ключа имеют ограничения NOT NULL. Предложения ON UPDATE и ON DELETE. Предложения ON UPDATE и ON DELETE определяют действия, исполняемые по ссылке. Действия, исполняемые по ссылке, в основном описаны выше в этой главе. Сложности в понимании того, как выполняются эти действия, возникают если установлено MATCH PARTIAL и колонки, входящие в состав внешнего ключа, допускают NULL-значения. Подробно эти действия с учетом возможных сложностей описаны в [9]. Атрибуты ограничения. Атрибуты ограничения определяют, в какой момент проверяются ограничения. Ограничение может быть определено как NOT DEFERRABLE (неоткладываемое) или DEFERRABLE (откладываемое). Если атрибуты ограничения не указаны, то по умолчанию принимается NOT DEFERRABLE. Если ограничение определено как NOT DEFERRABLE (неоткладываемое), то ограничение всегда проверяется сразу после выполнения каждого оператора INSERT, UPDATE или DELETE, которые могут привести к нарушению ограничения. Если ограничение определено как DEFERRABLE (откладываемое), то ограничение может иметь два режима проверки - немедленно после выполнения операции или в конце транзакции. Режим проверки может быть изменен в любой момент внутри транзакции командой SET CONSTRAINTS. При определении ограничения можно указать начальный режим проверки INITIALLY DEFERRED (начально отложенное) или INITIALLY IMMEDIATE (начально немедленно проверяемое).



Таблица 6
НЕТ
(Конфликт
R-W) НЕТ
(Конфликт
W-R)НЕТ
(Конфликт
W-W)
Транзакция B пытается наложить блокировку:
Транзакция A наложила блокировку: S-блокировку X-блокировку
S-блокировку Да
X-блокировку

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

  1. Прежде чем прочитать объект, транзакция должна наложить на этот объект S-блокировку.
  2. Прежде чем обновить объект, транзакция должна наложить на этот объект X-блокировку. Если транзакция уже заблокировала объект S-блокировкой (для чтения), то перед обновлением объекта S-блокировка должна быть заменена X-блокировкой.
  3. Если блокировка объекта транзакцией B отвергается оттого, что объект уже заблокирован транзакцией A, то транзакция B переходит в состояние ожидания. Транзакция B будет находиться в состоянии ожидания до тех пор, пока транзакция A не снимет блокировку объекта.
  4. X-блокировки, наложенные транзакцией A, сохраняются до конца транзакции A.



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