| Где используется | |
| Болт | Двигатель |
| Болт | Колесо |
| Гайка | Двигатель |
| Гайка | Колесо |
| Двигатель | Автомобиль |
| Колесо | Автомобиль |
| Ось | Колесо |
Таблица 5 Отношение RТранзитивное замыкание 
Таблица 5
| 1 | Иванов | 1000 |
| 2 | Петров | 2000 |
| 3 | Сидоров | 3000 |
| 2 | Петров | 2000 |
| 3 | Сидоров | 3000 |
Таблица 5 Отношение A MINUS B
| Иванов | Болт | 100 |
| Иванов | Гайка | 200 |
| Иванов | Винт | 300 |
| Петров | Болт | 150 |
| Петров | Гайка | 250 |
| Сидоров | Болт | 1000 |
| 1 | Иванов | 1 |
| 2 | Петров | 1 |
| 3 | Сидоров | 2 |
Таблица 5 Отношение СОТРУДНИКИ
Отношение ОТДЕЛЫ (Н_ОТД, ТЕЛ):
Функциональные зависимости:
Зависимость номера телефона от номера отдела:
Н_ОТД 
ТЕЛ
Таблица 5
| 1 | 100 |
| 2 | 200 |
| 3 | 300 |
| 1 | 150 |
| 2 | 250 |
| 1 | 1000 |
Таблица 5 Отношение "Поставки-3"
На первый взгляд, такая декомпозиция хуже, чем первая. Действительно, наименования поставщиков по-прежнему повторяются, и при изменении наименования поставщика, это наименование придется менять одновременно в нескольких местах (тем более сразу в двух отношениях!). Кажется, что ситуация стала еще хуже, чем была до декомпозиции. Однако такое ощущение возникает от того, что мы интуитивно считаем, что наименования поставщиков могут меняться, а номера - нет. Если же предположить, что номера поставщиков тоже могут меняться (почему бы нет - директор приказал перенумеровать поставщиков!), то первая декомпозиция получается такой же "плохой" как и вторая - повторяющиеся номера придется менять одновременно в нескольких местах и также сразу в двух отношениях.
На самом деле никакого противоречия тут нет. В отношении "Поставки-3" атрибут "Наименование поставщика" (PNAME) является внешним ключом, служащим для связи с отношением "Поставщики". Поэтому, при изменении наименования поставщика, это изменение производится в отношении "Поставщики" и каскадно (см. стратегии поддержания ссылочной целостности в гл. 3) распространяется на отношение "Поставки-3" совершенно так, как изменение номера поставщика каскадно распространяется на отношение "Поставки-2". Поэтому, формально обе декомпозиции совершенно равноправны. В реальной работе разработчик выберет, конечно, первую декомпозицию, но тут важно подчеркнуть, что его выбор основан совсем на других соображениях, не имеющих отношения к формальной теории нормальных форм.
Замечание. Отношение "Поставки-2", полученное в результате декомпозиции имеет всего один потенциальный ключ. Поэтому, для анализа отношения "Поставки-2" не требуется привлекать определение НФБК, достаточно определения 3НФ. Хотя отношение "Поставщики" имеет два потенциальных ключа, но, т.к. других атрибутов в нем нет, оно уже так просто устроено, что упростить его дальше нельзя. Возникает вопрос, имеются ли нетривиальные примеры отношений в НФБК, не находящиеся в 3НФ и не такие простые, как отношение "Поставщики"?
Таблица 5
Z
X
Y
1
1
Aa
2
1
Null
3
Null
Cc
4
Null
Null
5
4
Gg
Таблица 5 Таблица B (Дочерняя)
Таблица A имеет первичный ключ (X, Y). Таблица B имеет первичный ключ Z, и внешний ключ (X, Y), ссылающийся на первичный ключ таблицы A. Различные варианты совпадения строк дочерней таблицы B со строками родительской таблицы A приведены ниже:
Таблица 5
Чтение счета   |
 |
--- |
| --- |  |
Снятие денег со счета   |
| --- |  |
Помещение денег на счет   |
| --- |  |
Фиксация транзакции |
Чтение счета   |
 |
--- |
Чтение счета   |
 |
--- |
| Фиксация транзакции |  |
--- |
| Болт | Двигатель |
| Болт | Колесо |
| Гайка | Двигатель |
| Гайка | Колесо |
| Двигатель | Автомобиль |
| Колесо | Автомобиль |
| Ось | Колесо |
| Болт | Автомобиль |
| Гайка | Автомобиль |
| Ось | Автомобиль |
Таблица 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
| 1 | Иванов | 1 | Болт |
| 1 | Иванов | 2 | Гайка |
| 1 | Иванов | 3 | Винт |
| 2 | Петров | 1 | Болт |
| 2 | Петров | 2 | Гайка |
| 2 | Петров | 3 | Винт |
| 3 | Сидоров | 1 | Болт |
| 3 | Сидоров | 2 | Гайка |
| 3 | Сидоров | 3 | Винт |
| 1 | 11-22-33 |
| 2 | 33-22-11 |
Таблица 6 Отношение ОТДЕЛЫОбратим внимание на то, что атрибут Н_ОТД, не являвшийся ключевым в отношении СОТРУДНИКИ_ОТДЕЛЫ, становится потенциальным ключом в отношении ОТДЕЛЫ. Именно за счет этого устраняется избыточность, связанная с многократным хранением одних и тех же номеров телефонов.
Вывод. Таким образом, все обнаруженные аномалии обновления устранены. Реляционная модель, состоящая из четырех отношений СОТРУДНИКИ, ОТДЕЛЫ, ПРОЕКТЫ, ЗАДАНИЯ, находящихся в третьей нормальной форме, является адекватной описанной модели предметной области, и требует наличия только тех триггеров, которые поддерживают ссылочную целостность. Такие триггеры являются стандартными и не требуют больших усилий в разработке.
Таблица 6
| 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
| Колонки 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 строка - не допустима. |
| Транзакция B пытается наложить блокировку: | ||
| Транзакция A наложила блокировку: | S-блокировку | X-блокировку |
| S-блокировку | Да | НЕТ|
| X-блокировку | НЕТ
Таблица 1 Матрица совместимости S- и X-блокировок
Три случая, когда транзакция B не может блокировать объект, соответствуют трем видам конфликтов между транзакциями.
Доступ к объектам базы данных на чтение и запись должен осуществляться в соответствии со следующим протоколом доступа к данным:
Прежде чем прочитать объект, транзакция должна наложить на этот объект S-блокировку.
Прежде чем обновить объект, транзакция должна наложить на этот объект X-блокировку. Если транзакция уже заблокировала объект S-блокировкой (для чтения), то перед обновлением объекта S-блокировка должна быть заменена X-блокировкой.
Если блокировка объекта транзакцией B отвергается оттого, что объект уже заблокирован транзакцией A, то транзакция B переходит в состояние ожидания. Транзакция B будет находиться в состоянии ожидания до тех пор, пока транзакция A не снимет блокировку объекта.
X-блокировки, наложенные транзакцией A, сохраняются до конца транзакции A.
| 1 | Иванов |
| 2 | Петров |
| 3 | Сидоров |
Таблица 6 Отношение "Поставщики"
Таблица 7
| 1 | Болт |
| 2 | Гайка |
| 3 | Винт |
Таблица 7 Отношение B (Детали) Декартово произведение отношений 
будет иметь вид:
Таблица 7
| 1 | Иванов | 4 |
| 2 | Петров | 1 |
| 3 | Сидоров | 2 |
Таблица 1 Отношение P (Поставщики)
Таблица 7
| Адекватность базы данных предметной области | ХУЖЕ (-) | ЛУЧШЕ (+) |
| Легкость разработки и сопровождения базы данных | СЛОЖНЕЕ (-) | ЛЕГЧЕ (+) |
| Скорость выполнения вставки, обновления, удаления | МЕДЛЕННЕЕ (-) | БЫСТРЕЕ (+) |
| Скорость выполнения выборки данных | БЫСТРЕЕ (+) | МЕДЛЕННЕЕ (-) |
| Иванов | Математический | Математика |
| Иванов | Математический | Информатика |
| Иванов | Физический | Математика |
| Иванов | Физический | Физика |
| Петров | Математический | Математика |
| Петров | Математический | Информатика |
Таблица 7 Отношение "Абитуриенты-Факультеты-Предметы"
В данный момент в отношении хранится информация о том, что абитуриент Иванов поступает на два факультета (математически и физический), а абитуриент Петров - только на математический. Кроме того, можно сделать вывод, что на математическом факультете нужно сдавать математику и информатику, а на физическом - математику и физику.
Кажется, что в отношении имеется аномалия обновления, связанная с тем, что дублируются фамилии абитуриентов, наименования факультетов и наименования предметов. Однако эта аномалия легко устраняется стандартным способом - вынесением всех наименований в отдельные отношения, оставляя в исходном отношении только соответствующие номера:
Таблица 7
S-блокировка  |
 |
--- |
Чтение  |
 |
--- |
| --- |  |
S-блокировка  |
| --- |  |
Чтение  |
X-блокировка  |
 |
--- |
| Ожидание… |  |
X-блокировка  |
| Ожидание… |  |
Ожидание… |
| Ожидание… |
. Блокировка отвергается, т.к. объект 
. Блокировка отвергается, т.к. объект 
Результат. Обе транзакции ожидают друг друга и не могут продолжаться. Возникла ситуация тупика.
| 1 | Болт |
| 2 | Гайка |
| 3 | Винт |
Таблица 7 Отношение "Детали"
Таблица 8
| 1 | Иванов | 1 | Болт |
| 1 | Иванов | 2 | Гайка |
| 1 | Иванов | 3 | Винт |
| 2 | Петров | 1 | Болт |
| 2 | Петров | 2 | Гайка |
| 2 | Петров | 3 | Винт |
| 3 | Сидоров | 1 | Болт |
| 3 | Сидоров | 2 | Гайка |
| 3 | Сидоров | 3 | Винт |
Таблица 8 Отношение A TIMES BЗамечание. Сама по себе операция декартового произведения не очень важна, т.к. она не дает никакой новой информации, по сравнению с исходными отношениями. Для реальных запросов эта операция почти никогда не используется. Однако операция декартового произведения важна для выполнения специальных реляционных операций, о которых речь пойдет ниже.
Таблица 8
| 1 | Болт | 3 |
| 2 | Гайка | 2 |
| 3 | Винт | 1 |
Таблица 2 Отношение D (Детали)
Ответ на вопрос " какие поставщики имеют право поставлять какие детали?" дает следующий запрос:
SELECT
P.PNUM,
P.PNAME,
P.PSTATUS,
D.DNUM,
D.DNAME,
D.DSTATUS
FROM P, D
WHERE P.PSTATUS >= D.DSTATUS;
В результате получим следующую таблицу:
Таблица 8
| 1 | Иванов | 1000 |
| 2 | Петров | 1000 |
Таблица 7 Отношение 
Рассмотрим первый вариант декомпозиции отношения 
Таблица 8
| 1 | 1 | 1 |
| 1 | 1 | 2 |
| 1 | 2 | 1 |
| 1 | 2 | 3 |
| 2 | 1 | 1 |
| 2 | 1 | 2 |
Таблица 8 Модифицированное отношение "Абитуриенты-Факультеты-Предметы"
Таблица 8
| --- |  |
S-блокировка  |
| --- |  |
Чтение  |
| --- |  |
X-блокировка  |
| --- |  |
Запись  |
S-блокировка  |
 |
--- |
| Ожидание… |  |
Откат транзакции  (Блокировка снимается) |
S-блокировка  |
 |
--- |
Чтение  |
 |
--- |
Работа с прочитанными данными  |
 |
--- |
| --- |  |
--- |
| Фиксация транзакции |  |
--- |
| 1 | 1 | 100 |
| 1 | 2 | 200 |
| 1 | 3 | 300 |
| 2 | 1 | 150 |
| 2 | 2 | 250 |
| 3 | 3 | 1000 |
Таблица 8 Отношение "Поставки"В отношении "Поставки" атрибуты "Номер поставщика" и " Номер детали" являются ссылками на ключевые атрибуты отношений "Поставщики" и "Детали", и, следовательно, являются внешними ключами. Заметим, что данные отношения свободны от недостатков, описанных выше, когда все данные предлагалось хранить в одном отношении. Действительно, при изменении наименования поставщика или детали, это изменение происходит только в одном месте. Если поставщик прекратил поставки всех деталей, то удаляются соответствующие кортежи в отношении "Поставки", данные же о самом поставщике остаются без изменений.
Дадим точное определение.
Таблица 9
| 1 | Иванов | 1000 |
| 2 | Петров | 2000 |
| 3 | Сидоров | 3000 |
Таблица 9 Отношение A
Результат выборки 
Таблица 9
| 1 | Иванов | 4 | 1 | Болт | 3 |
| 1 | Иванов | 4 | 2 | Гайка | 2 |
| 1 | Иванов | 4 | 3 | Винт | 1 |
| 2 | Петров | 1 | 3 | Винт | 1 |
| 3 | Сидоров | 2 | 2 | Гайка | 2 |
| 3 | Сидоров | 2 | 3 | Винт | 1 |
| 1 | 1000 |
| 2 | 1000 |
Таблица 8 Отношение 
Таблица 9
| 1 | Иванов |
| 2 | Петров |
Таблица 9 Отношение "Абитуриенты"
Таблица 9
S-блокировка  |
 |
--- |
Чтение  |
 |
--- |
| --- |  |
X-блокировка  |
| --- |  |
Ожидание… |
Повторное чтение  |
 |
Ожидание… |
| Фиксация транзакции (Блокировка снимается) |
 |
Ожидание… |
| --- |  |
X-блокировка  |
| --- |  |
Запись  |
| --- |  |
Фиксация транзакции (Блокировка снимается) |
| 1 | Иванов | 1000 |
| 2 | Петров | 2000 |
Таблица 10 Отношение A WHERE Зарплата<3000Смысл операции выборки очевиден - выбрать кортежи отношения, удовлетворяющие некоторому условию. Таким образом, операция выборки дает "горизонтальный срез" отношения по некоторому условию.
Таблица 10
| Иванов | 1000 |
| Петров | 1000 |
Таблица 9 Отношение 
Естественное соединение этих проекций, имеющих общий атрибут "ЗАРПЛАТА", очевидно, будет следующим (каждая строка одной проекции соединится с каждой строкой другой проекции):
Таблица 10
| 1 | Математический |
| 2 | Физический |
Таблица 10 Отношение "Факультеты"
Таблица 10
S-блокировка строк, удовлетворяющих условию  (Заблокировано n строк) |
 |
--- |
Выборка строк, удовлетворяющих условию  (Отобрано n строк) |
 |
--- |
| --- |  |
Вставка новой строки, удовлетворяющей условию  |
| --- |  |
Фиксация транзакции |
S-блокировка строк, удовлетворяющих условию  (Заблокировано n+1 строка) |
 |
--- |
Выборка строк, удовлетворяющих условию  (Отобрано n+1 строк) |
 |
--- |
| Фиксация транзакции |  |
--- |
| 1 | Иванов | Уфа |
| 2 | Петров | Москва |
| 3 | Сидоров | Москва |
| 4 | Сидоров | Челябинск |
Таблица 11 Отношение A (Поставщики)
Проекция 
Таблица 11
| 1 | Иванов |
| 2 | Петров |
| 3 | Сидоров |
Таблица 3 Отношение CONTRAGENTS
Таблица 11
| 1 | Иванов | 1000 |
| 1 | Петров | 1000 |
| 2 | Иванов | 1000 |
| 2 | Петров | 1000 |
Таблица 10 Отношение 
Итак, данная декомпозиция не является декомпозицией без потерь, т.к. исходное отношение не восстанавливается в точном виде по проекциям (серым цветом выделены лишние кортежи).
Рассмотрим другой вариант декомпозиции:
Таблица 11
| 1 | Математика |
| 2 | Информатика |
| 3 | Физика |
Таблица 11 Отношение "Предметы"
Теперь каждое наименование встречается только в одном месте.
И все-таки как в исходном, так и в модифицированном отношении имеются аномалии обновления, возникающие при попытке вставить или удалить кортежи.
Аномалия вставки. При попытке добавить в отношение "Абитуриенты-Факультеты-Предметы" новый кортеж, например (Сидоров, Математический, Математика), мы обязаны добавить также и кортеж (Сидоров, Математический, Информатика), т.к. все абитуриенты математического факультета обязаны иметь один и тот же список сдаваемых предметов. Соответственно, при попытке вставить в модифицированное отношении кортеж (3, 1, 1), мы обязаны вставить в него также и кортеж (3, 1, 2).
Аномалия удаления. При попытке удалить кортеж (Иванов, Математический, Математика), мы обязаны удалить также и кортеж (Иванов, Математический, Информатика) по той же самой причине.
Таким образом, вставка и удаление кортежей не может быть выполнена независимо от других кортежей отношения.
Кроме того, если мы удалим кортеж (Иванов, Физический, Математика), а вместе с ним и кортеж (Иванов, Физический, Физика), то будет потеряна информация о предметах, которые должны сдаваться на физическом факультете.
Декомпозиция отношения "Абитуриенты-Факультеты-Предметы" для устранения указанных аномалий не может быть выполнена на основе функциональных зависимостей, т.к. это отношение не содержит никаких функциональных зависимостей. Это отношение является полностью ключевым, т.е. ключом отношения является все множество атрибутов. Но ясно, что какая-то взаимосвязь между атрибутами имеется. Эта взаимосвязь описывается понятием многозначной зависимости.
Таблица 11
S-блокировка счета  |
 |
--- |
Чтение счета   |
 |
--- |
| --- |  |
X-блокировка счета  |
| --- |  |
Снятие денег со счета   |
| --- |  |
X-блокировка счета  |
| --- |  |
Ожидание… |
S-блокировка счета  |
 |
Ожидание… |
Чтение счета 
|
 |
Ожидание… |
S-блокировка счета  |
 |
Ожидание… |
| Ожидание… |  |
Ожидание… |
| Ожидание… |
| Уфа |
| Москва |
| Челябинск |
Таблица 12 Отношение A[Город поставщика]
Таблица 12
| 1 | Болт |
| 2 | Гайка |
| 3 | Винт |
Таблица 4 Отношение DETAILS (Детали)
Таблица 12
| 1 | Иванов |
| 2 | Петров |
Таблица 11 Отношение 
Таблица 12
| Математический | Иванов |
| Физический | Иванов |
| Математический | Петров |
Таблица 12 Отношение "Факультеты-Абитуриенты"
Таблица 12
Блокировка объекта  |
 |
--- |
| --- |  |
Блокировка объекта  |
Блокировка объекта  |
 |
--- |
| Ожидание… |  |
Блокировка объекта  |
| Ожидание… |  |
Ожидание… |
| Ожидание… |
| Номер поставщика | Наименование поставщика
X
(Статус поставщика) | |
| 1 | Иванов | 4 |
| 2 | Петров | 1 |
| 3 | Сидоров | 2 |
Таблица 13 Отношение A (Поставщики)
Таблица 13
| 1 | 2 | 1 | 100 |
| 1 | 3 | 2 | 200 |
| 1 | 3 | 3 | 300 |
| 2 | 3 | 1 | 150 |
| 2 | 3 | 2 | 250 |
| 3 | 1 | 1 | 1000 |
Таблица 5 Отношение CD (Поставки)
В таблице CD (поставки) поля PNUM и CNUM являются внешними ключами, ссылающимися на потенциальный ключ NUM в таблице CONTRAGENTS.
Ответ на вопрос "кто кому что в каком количестве поставляет" дается следующим запросом:
SELECT
P.NAME AS PNAME,
C.NAME AS CNAME,
DETAILS.DNAME,
CD.VOLUME
FROM
CONTRAGENTS P,
CONTRAGENTS C,
DETAILS,
CD
WHERE
P.NUM = CD.PNUM AND
C.NUM = CD.CNUM AND
D.DNUM = CD.DNUM;
В результате получим следующую таблицу:
Таблица 13
| 1 | 1000 |
| 2 | 1000 |
Таблица 12 Отношение 
По данным проекциям, имеющие общий атрибут "НОМЕР", исходное отношение восстанавливается в точном виде. Тем не менее, нельзя сказать, что данная декомпозиция является декомпозицией без потерь, т.к. мы рассмотрели только одно конкретное состояние отношения 
восстанавливаться точно. Например, предположим, что отношение 
Таблица 13
| Математический | Математика |
| Математический | Информатика |
| Физический | Математика |
| Физический | Физика |
Таблица 13 Отношение "Факультеты-Предметы"
В полученных отношениях устранены аномалии вставки и удаления, характерные для отношения "Абитуриенты-Факультеты-Предметы".
Заметим, что полученные отношения остались полностью ключевыми, и в них по-прежнему нет функциональных зависимостей.
Отношения с нетривиальными многозначными зависимостями возникают, как правило, в результате естественного соединения двух отношений по общему полю, которое не является ключевым ни в одном из отношений. Фактически это приводит к попытке хранить в одном отношении информацию о двух независимых сущностях. В качестве еще одного примера можно привести ситуацию, когда сотрудник может иметь много работ и много детей. Хранение информации о работах и детях в одном отношении приводит к возникновению нетривиальной многозначной зависимости Работник
Таблица 13
| Транзакция B пытается наложить на таблицу блокировку: | |||||
| Транзакция A наложила на таблицу блокировку: | IS | S | IX | SIX | X |
| IS | Да Да Да Да Нет|||||
| S | Да Да Нет Нет Нет|||||
| IX | Да Нет Да Нет Нет|||||
| SIX | Да Нет Нет Нет Нет|||||
| X | Нет Нет Нет Нет Нет
Таблица 2 Расширенная таблица совместимости блокировок Более точная формулировка протокола преднамеренных блокировок для доступа к данным выглядит следующим образом: При задании X-блокировки для сложного объекта неявным образом задается X-блокировка для всех дочерних объектов этого объекта. При задании S- или SIX-блокировки для сложного объекта неявным образом задается S-блокировка для всех дочерних объектов этого объекта. Прежде чем транзакция наложит S- или IS-блокировку на заданный объект, она должна задать IS-блокировку (или более сильную) по крайней мере для одного родительского объекта этого объекта. Прежде чем транзакция наложит X-, IX- или SIX-блокировку на заданный объект, она должна задать IX-блокировку (или более сильную) для всех родительских объектов этого объекта. Прежде чем для данной транзакции будет отменена блокировка для данного объекта, должны быть отменены все блокировки для дочерних объектов этого объекта. Понятие относительной силы блокировок можно описать при помощи следующей диаграммы приоритета (сверху - более сильные блокировки, снизу - более слабые):
Таблица 3 Диаграмма приоритета блокировокЗамечание. Протокол преднамеренных блокировок не определяет однозначно, какие блокировки должны быть наложены на родительский объект при блокировании дочернего объекта. Например, при намерении задать S-блокировку строки таблицы, на таблицу, включающую эту строку, можно наложить любую из блокировок типа IS, S, IX, SIX, X. При намерении задать X-блокировку строки, на таблицу можно наложить любую из блокировок типа IX, SIX, X.
Посмотрим, как разрешается проблема фиктивных элементов (фантомов) с использованием протокола преднамеренных блокировок для доступа к данным.
Транзакция A дважды выполняет выборку строк с одним и тем же условием. Между выборками вклинивается транзакция B, которая добавляет новую строку, удовлетворяющую условию отбора.
Транзакция B перед попыткой вставить новую строку должна наложить на таблицу IX-блокировку, или более сильную (SIX или X). Тогда транзакция A, для предотвращения возможного конфликта, должна наложить такую блокировку на таблицу, которая не позволила бы транзакции B наложить IX-блокировку. По таблице совместимости блокировок определяем, что транзакция A должна наложить на таблицу S, или SIX, или X-блокировку. (Блокировки IS недостаточно, т.к. эта блокировка позволяет транзакции B наложить IX-блокировку для последующей вставки строк).
| 1 | Болт | 3 |
| 2 | Гайка | 2 |
| 3 | Винт | 1 |
Таблица 14 Отношение B (Детали)
Ответ на вопрос " какие поставщики имеют право поставлять какие детали?" дает 
:
Таблица 14
| Иванов | Петров | Болт | 100 |
| Иванов | Сидоров | Гайка | 200 |
| Иванов | Сидоров | Винт | 300 |
| Петров | Сидоров | Болт | 150 |
| Петров | Сидоров | Гайка | 250 |
| Сидоров | Иванов | Болт | 1000 |
| 1 | Иванов | 1000 |
| 2 | Петров | 1000 |
| 2 | Сидоров | 2000 |
Таблица 13 Отношение 
Кажется, что этого не может быть, т.к. значения в атрибуте "НОМЕР" повторяются. Но мы же ничего не говорили о ключе этого отношения! Сейчас проекции будут иметь вид:
Таблица 14
| 1 | 1 | 2 |
| 1 | 2 | 1 |
| 2 | 1 | 1 |
| 1 | 1 | 1 |
Таблица 14 Отношение R
Всевозможные проекции отношения 
Таблица 14
| S-блокировка таблицы ( с целью потом блокировать строки) - успешна |  |
--- |
S-блокировка строк, удовлетворяющих условию  (Заблокировано n строк) |
 |
--- |
Выборка строк, удовлетворяющих условию  (Отобрано n строк) |
 |
--- |
| --- |  |
IX-блокировка таблицы (с целью потом вставлять строки) - отвергается из-за конфликта с S-блокировкой, наложенной транзакцией A |
| --- |  |
Ожидание… |
| --- |  |
Ожидание… |
S-блокировка строк, удовлетворяющих условию  (Заблокировано n строк) |
 |
Ожидание… |
Выборка строк, удовлетворяющих условию  (Отобрано n строк) |
 |
Ожидание… |
| Фиксация транзакции - блокировки снимаются |  |
Ожидание… |
| --- |  |
IX-блокировка таблицы (с целью потом вставлять строки) - успешна |
| --- |  |
Вставка новой строки, удовлетворяющей условию  |
| --- |  |
Фиксация транзакции |
| 1 | Иванов | 4 | 1 | Болт | 3 |
| 1 | Иванов | 4 | 2 | Гайка | 2 |
| 1 | Иванов | 4 | 3 | Винт | 1 |
| 2 | Петров | 1 | 3 | Винт | 1 |
| 3 | Сидоров | 2 | 2 | Гайка | 2 |
| 3 | Сидоров | 2 | 3 | Винт | 1 |
Таблица 15 Отношение " Какие поставщики поставляют какие детали"
N
| 3 |
| 1 | Иванов |
| 2 | Петров |
| 2 | Сидоров |
Таблица 14 Отношение 
Таблица 15
| 1 | 1 |
| 1 | 2 |
| 2 | 1 |
Таблица 15 Проекция R1=R[X,Y]
Таблица 15
Проверка SCN счета  Чтение счета   |
 |
--- |
| --- |  |
X-блокировка счета  |
| --- |  |
Снятие денег со счета   |
| --- |  |
X-блокировка счета  |
| --- |  |
Помещение денег на счет   |
| --- |  |
Фиксация транзакции
(Снятие блокировок) |
Проверка SCN счета  Чтение счета   |
 |
--- |
Проверка SCN счета  МЕНЬШЕ SCN счета.
Чтение старого варианта счета   |
 |
--- |
| Фиксация транзакции |  |
--- |
| 1 | Иванов |
| 2 | Петров |
| 3 | Сидоров |
Таблица 16 Отношение P (Поставщики)
Таблица 16
| 2000 | 1000 | 100 | 333.33333333 |
| 1 | 1000 |
| 2 | 1000 |
| 2 | 2000 |
Таблица 15 Отношение 
Естественное соединение этих проекций будет содержать лишние кортежи:
Таблица 16
| 1 | 2 |
| 1 | 1 |
| 2 | 1 |
Таблица 16 Проекция R2=R[X,Z]
Таблица 16
| Да | Да | Да |
| Да | Да | |
| Да | ||
Таблица 4 Уровни изоляции стандарта SQL
| 1 | Болт |
| 2 | Гайка |
| 3 | Винт |
Таблица 17 Отношение D (Детали)
Таблица 17
| 1 | 1250 |
| 2 | 450 |
| 3 | 300 |
| 1 | Иванов | 1000 |
| 2 | Петров | 1000 |
| 2 | Петров | 2000 |
| 2 | Сидоров | 1000 |
| 2 | Сидоров | 2000 |
Таблица 16 Отношение 
Вывод. Таким образом, без дополнительных ограничений на отношение 
Такими дополнительными ограничениями и являются функциональные зависимости. Имеет место следующая теорема Хеза [54]:
Таблица 17
Y
Z
1
2
2
1
1
1
Таблица 17 Проекция R3=R[Y,Z]
Как легко заметить, отношение 
, 
. Действительно, соединение 
| 1 | 1 | 100 |
| 1 | 2 | 200 |
| 1 | 3 | 300 |
| 2 | 1 | 150 |
| 2 | 2 | 250 |
| 3 | 1 | 1000 |
Таблица 18 Отношение PD (Поставки)
Ответ на вопрос, какие детали поставляются поставщиками, дает экви-соединение 
Обычно, такой сложной формой записи не пользуются. Но как бы то ни было, в результате имеем отношение:
Таблица 18
| 1 | 1250 |
| 2 | 450 |
| 1 | 1 | 2 |
| 1 | 1 | 1 |
| 1 | 2 | 2 |
| 1 | 2 | 1 |
| 2 | 1 | 1 |
Таблица 18 R1 JOIN R2
Серым цветом выделен лишний кортеж, отсутствующий в отношении 
.
Однако отношение 
Это говорит о том, что между атрибутами этого отношения также имеется некоторая зависимость, но эта зависимость не является ни функциональной, ни многозначной зависимостью.
| 1 | Иванов | 1 | 1 | 100 |
| 1 | Иванов | 1 | 2 | 200 |
| 1 | Иванов | 1 | 3 | 300 |
| 2 | Петров | 2 | 1 | 150 |
| 2 | Петров | 2 | 2 | 250 |
| 3 | Сидоров | 3 | 1 | 1000 |
Таблица 19 Отношение "Какие детали поставляются какими поставщиками"
Недостатком экви- соединения является то, что если соединение происходит по атрибутам с одинаковыми наименованиями (а так чаще всего и происходит!), то в результатирующем отношении появляется два атрибута с одинаковыми значениями. В нашем примере атрибуты PNUM1 и PNUM2 содержат дублирующие данные. Избавиться от этого недостатка можно, взяв проекцию по всем атрибутам, кроме одного из дублирующих. Именно так действует естественное соединение.
| 1 | Иванов | 1 | Болт | 100 |
| 1 | Иванов | 2 | Гайка | 200 |
| 1 | Иванов | 3 | Винт | 300 |
| 2 | Петров | 1 | Болт | 150 |
| 2 | Петров | 2 | Гайка | 250 |
| 3 | Сидоров | 1 | Болт | 1000 |
Таблица 20 Отношение P JOIN PD JOIN D
| 1 | 1 |
| 1 | 2 |
| 1 | 3 |
| 2 | 1 |
| 2 | 2 |
| 3 | 1 |
Таблица 21 Проекция X=PD[PNUM,DNUM]
В качестве делителя возьмем проекцию 
| 1 |
| 2 |
| 3 |
Таблица 22 Проекция Y=D[DNUM]
Деление 
| 1 |
Таблица 23 Отношение X DEVIDEBY Y
Оказалось, что только поставщик с номером 1 поставляет все детали.
| Дезоксирибону-клеиновая кислота | 5 | 3 | … | 0.01 |
| Бензин | 50 | 0 | … | 0 |
| … | … | … | … | … |
Таблица 24 Отношение ХИМИЧЕСКИЙ_СОСТАВ_ВЕЩЕСТВРассмотрим запрос "Найти все химические элементы, содержание которых в каком-либо из веществ превышает заданный процент (скажем, 90)".
С алгоритмической точки зрения этот запрос выполняется элементарно - просматриваются все столбцы таблицы, если в столбце присутствует хотя бы одно значение, большее 90, то запоминается заголовок этого столбца. Набор наименований запомненных столбцов и является ответом на запрос.
Формально невозможно выразить этот запрос в рамках реляционной алгебры, т.к. ответом на этот запрос должен быть список атрибутов отношений, удовлетворяющих определенному условию. В реляционной алгебре нет операторов, манипулирующих с наименованиями атрибутов.
На самом деле, этот пример показывает, что таблица плохо нормализована (нормализация отношений рассматривается в гл.6 и 7). В таблице есть набор однотипных атрибутов ("Водород", "Гелий" и т.д. в количестве 105 столбцов).
Правильнее разбить это отношение на три различных отношения:
ВЕЩЕСТВО(НОМ_ВЕЩЕСТВА, ВЕЩЕСТВО),
ЭЛЕМЕНТЫ(НОМ_ЭЛЕМЕНТА, ЭЛЕМЕНТ),
ХИМИЧЕСКИЙ_СОСТАВ_ВЕЩЕСТВ(НОМ_ВЕЩЕСТВА, НОМ_ЭЛЕМЕНТА, ПРОЦЕНТ).
| 1 | Дезоксирибонуклеиновая кислота |
| 2 | Бензин |
Таблица 25 Отношение ВЕЩЕСТВО
| 1 | Водород |
| 2 | Гелий |
| … | … |
| 105 | … |
Таблица 26 Отношение ЭЛЕМЕНТЫ
| 1 | 1 | 5 |
| 1 | 2 | 3 |
| 1 | 105 | 0.01 |
| 2 | 1 | 50 |
Таблица 27 Отношение ХИМИЧЕСКИЙ_СОСТАВ_ВЕЩЕСТВДля отношений, нормализованных таким образом, исходный запрос реализуется следующей последовательностью операторов:
R1(НОМЕР_ВЕЩЕСТВА,НОМ_ЭЛЕМЕНТА,ПРОЦЕНТ)= ХИМИЧЕСКИЙ_СОСТАВ_ВЕЩЕСТВ[ПРОЦЕНТ>90]. (Выборка из отношения).
R2(НОМ_ЭЛЕМЕНТА) = R1[НОМ_ЭЛЕМЕНТА]. (Проекция отношения).
R3(НОМ_ЭЛЕМЕНТА,ЭЛЕМЕНТ)= R2[НОМ_ЭЛЕМЕНТА=НОМ_ЭЛЕМЕНТА]ЭЛЕМЕНТЫ. (Естественное соединение)
ОТВЕТ(ЭЛЕМЕНТ) = R3[ЭЛЕМЕНТ]. (Проекция таблицы).
На языке SQL такой запрос реализуется одной командой:
SELECT ЭЛЕМЕНТЫ.ЭЛЕМЕНТ
FROM ЭЛЕМЕНТЫ, ХИМИЧЕСКИЙ_СОСТАВ_ВЕЩЕСТВ
WHERE
ЭЛЕМЕНТЫ.НОМ_ЭЛЕМЕНТА=ХИМИЧЕСКИЙ_СОСТАВ_ВЕЩЕСТВ.НОМ_ЭЛЕМЕНТА
AND ХИМИЧЕСКИЙ_СОСТАВ_ВЕЩЕСТВ.ПРОЦЕНТ>90;
| 1 | Иванов | Директор | 1 |
| 2 | Петров | Глав.бухгалтер | 1 |
| 3 | Сидоров | Бухгалтер | 2 |
| 4 | Васильев | Начальник цеха | 1 |
| 5 | Сухов | Мастер | 4 |
| 6 | Шарипов | Рабочий | 5 |
| … | … | … | … |
Таблица 28 Отношение СОТРУДНИКИ
Рассмотрим запрос "Перечислить всех руководителей (прямых и непрямых) данного сотрудника".
Ответом на запрос может быть получен при помощи понятия транзитивного замыкания. Однако транзитивное замыкание не может быть выражено операторами реляционной алгебры.
Требуется представить эти данные в виде таблицы, по строкам которой идут наименования товаров, по столбцам - месяцы, а в ячейках содержатся объемы продаж. Это и будет кросс-таблицей:
| Компьютеры | 100 | 150 | … |
| Принтеры | 200 | 250 | … |
| Сканеры | 300 | 350 | … |
Таблица 30 Кросс-таблица
Построение кросс- таблицы средствами реляционной алгебры невозможно, т.к. для этого требуется превратить данные в ячейках таблицы в наименования новых столбцов таблицы.
Замечание. В доказательстве теоремы Хеза наличие функциональной зависимости не использовалось при доказательстве включения 
Т.к. алгоритм нормализации (приведения отношений к 3НФ) основан на имеющихся в отношениях функциональных зависимостях, то теорема Хеза показывает, что алгоритм нормализации является корректным, т.е. в ходе нормализации не происходит потери информации.
Протокол называется двухфазным, потому что он характеризуется двумя фазами: 1 фаза - нарастание блокировок. Во время этой фазы накладываются блокировки, и производится работа с заблокированными объектами. 2 фаза - снятие блокировок. Во время этой фазы блокировки только снимаются. Работа с ранее заблокированными данными может продолжаться.
Работа транзакции может выглядеть приблизительно, как на рисунке:
Рисунок 1 Работа транзакции по протоколу двухфазной блокировки
На следующем рисунке показан пример транзакции, не подчиняющийся протоколу двухфазной блокировки:
Рисунок 2 Транзакция, не подчиняющаяся протоколу двухфазной блокировки
На практике, как правило, вторая фаза сводится к одной операции завершения транзакции (или отката транзакции) с одновременным снятием всех блокировок.
Если некоторая транзакция A не подчиняется протоколу двухфазной блокировки (и, следовательно, состоит не менее чем из двух операция блокирования и разблокирования), то всегда можно построить другую транзакцию B, которая при чередующемся выполнении вместе с A приводит к графику, не подлежащему упорядочению и неверному.
Транзакции, используемые в этом протоколе, не различаются по типам и считаются монопольными. Описанные выше протоколы доступа к данным с использованием S- и X-блокировок и протокол преднамеренных блокировок являются модификациями протокола двухфазной блокировки для случая, когда блокировки имеют различные типы.
Есвараном сформулирована следующая теорема:
Теорема (фейджина)
Теорема (Фейджина)
. Пусть 
, 
.
Декомпозиция отношения 
и 
.
Замечание. Если зависимость 
или 
Доказательство теоремы.
Необходимость. Пусть декомпозиция отношения 
и 
.
Предположим, что отношение 
и 
также содержится в 
содержится в 
содержится в 
содержится в естественном соединении 
. Необходимость доказана.
Достаточность. Пусть имеется многозначная зависимость 
на проекции 
является декомпозицией без потерь.
Как и в доказательстве теоремы Хеза, нужно доказать, что 
.
Включение 
.
Докажем включение 
. Это означает, что в проекции 
, а в проекции 
. По определению проекции, найдется такое значение 
, что отношение 
. Аналогично, найдется такое значение 
, что отношение 
. Тогда по определению многозначной зависимости кортеж 
Достаточность доказана.
Теорема фейджина (другая формулировка)
Теорема Фейджина (другая формулировка)
. Отношение 
тогда и только тогда, когда имеется многозначная зависимость 
Т.к. теорема Фейджина является взаимно обратной, то ее можно взять в качестве определения многозначной зависимости. Таким образом, многозначная зависимость является частным случаем зависимости соединения, т.е., если в отношении имеется многозначная зависимость, то имеется и зависимость соединения. Обратное, конечно, неверно.
- атрибуты или множества атрибутов этого отношения. Если имеется функциональная зависимость 
и 
Доказательство. Необходимо доказать, что 
. В левой и правой части равенства стоят множества кортежей, поэтому для доказательства достаточно доказать два включения для двух множеств кортежей: 
.
Докажем первое включение. Возьмем произвольный кортеж 
. По определению проекции, кортежи 
. По определению естественного соединения кортежи 
, имеющие одинаковое значение 
, будут соединены в процессе естественного соединения в кортеж 
Докажем обратное включение. Возьмем произвольный кортеж 
. По определению естественного соединения получим, что в имеются кортежи 
. Т.к. 
, такое что кортеж 
, такое что кортеж 
и 
, равное 
, следует, что 
. Обратное включение доказано.
Теорема хеза как было показано...
атрибуты исходного отношения. Т.е., при декомпозиции не должны теряться атрибуты отношений. Но при декомпозиции также не должны потеряться и сами данные. Данные можно считать не потерянными в том случае, если возможна обратная операция - по декомпозированным отношениям можно восстановить исходное отношение в точности в прежнем виде. Операцией, обратной операции проекции, является операция соединения отношений. Имеется большое количество видов операции соединения (см. гл. 4). Т.к. при восстановлении исходного отношения путем соединения проекций не должны появиться новые атрибуты, то необходимо использовать естественное соединение.
Типы данных
Типы данных
Любые данные, используемые в программировании, имеют свои типы данных.
Важно! Реляционная модель требует, чтобы типы используемых данных были простыми.
Для уточнения этого утверждения рассмотрим, какие вообще типы данных обычно рассматриваются в программировании. Как правило, типы данных делятся на три группы:
Простые типы данных.
Структурированные типы данных.
Ссылочные типы данных.
Собственно, для реляционной модели данных тип используемых данных не важен. Требование, чтобы тип данных был простым, нужно понимать так, что в реляционных операциях не должна учитываться внутренняя структура данных. Конечно, должны быть описаны действия, которые можно производить с данными как с единым целым, например, данные числового типа можно складывать, для строк возможна операция конкатенации и т.д.
С этой точки зрения, если рассматривать массив, например, как единое целое и не использовать поэлементных операций, то массив можно считать простым типом данных. Более того, можно создать свой, сколь угодно сложных тип данных, описать возможные действия с этим типом данных, и, если в операциях не требуется знание внутренней структуры данных, то такой тип данных также будет простым с точки зрения реляционной теории. Например, можно создать новый тип - комплексные числа как запись вида 
. Можно описать функции сложения, умножения, вычитания и деления, и все действия с компонентами 
выполнять только внутри этих операций. Тогда, если в действиях с этим типом использовать только описанные операции, то внутренняя структура не играет роли, и тип данных извне выглядит как атомарный.
Именно так в некоторых пост-реляционных СУБД реализована работа со сколь угодно сложными типами данных, создаваемых пользователями.
Введем понятие транзитивного замыкания, связанное с бинарными отношениями, которое понадобится в дальнейшем.
Т.к. null-значение обозначает на самом деле тот факт, что значение неизвестно, то любые алгебраические операции (сложение, умножение, конкатенация строк и т.д.) должны давать также неизвестное значение, т.е. null. Действительно, если, например, вес детали неизвестен, то неизвестно также, сколько весят 10 таких деталей.
При сравнении выражений, содержащих null-значения, результат также может быть неизвестен, например, значение истинности для выражения 
трехзначной логике (three-valued logic, 3VL), в которой кроме значений T - ИСТИНА и F - ЛОЖЬ, введено значение U - НЕИЗВЕСТНО. Логическое значение U - это то же самое, что и null-значение. Трехзначная логика базируется на следующих таблицах истинности:
Уровни изоляции
Уровни изоляции
Стандарт SQL не предусматривает понятие блокировок для реализации сериализуемости смеси транзакций. Вместо этого вводится понятие уровней изоляции. Этот подход обеспечивает необходимые требования к изолированности транзакций, оставляя возможность производителям различных СУБД реализовывать эти требования своими способами (в частности, с использованием блокировок или выделением версий данных).
Стандарт SQL предусматривает 4 уровня изоляции: READ UNCOMMITTED - уровень незавершенного считывания. READ COMMITTED - уровень завершенного считывания. REPEATABLE READ - уровень повторяемого считывания. SERIALIZABLE - уровень способности к упорядочению.
Если все транзакции выполняются на уровне способности к упорядочению (принятом по умолчанию), то чередующееся выполнение любого множества параллельных транзакций может быть упорядочено. Если некоторые транзакции выполняются на более низких уровнях, то имеется множество способов нарушить способность к упорядочению. В стандарте SQL выделены три особых случая нарушения способности к упорядочению, фактически именно те, которые были описаны выше как проблемы параллелизма: Неаккуратное считывание ("Грязное" чтение, незафиксированная зависимость). Неповторяемое считывание (Частный случай несовместного анализа). Фантомы (Фиктивные элементы - частный случай несовместного анализа).
Потеря результатов обновления стандартом SQL не допускается, т.е. на самом низком уровне изолированности транзакции должны работать так, чтобы не допустить потери результатов обновления.
Различные уровни изоляции определяются по возможности или исключению этих особых случаев нарушения способности к упорядочению. Эти определения описываются следующей таблицей:
Восстановление базы данных может производиться в следующих случаях: Индивидуальный откат транзакции. Откат индивидуальной транзакции может быть инициирован либо самой транзакцией путем подачи команды ROLLBACK, либо системой. СУБД может инициировать откат транзакции в случае возникновения какой-либо ошибки в работе транзакции (например, деление на нуль) или если эта транзакция выбрана в качестве жертвы при разрешении тупика. Мягкий сбой системы (аварийный отказ программного обеспечения). Мягкий сбой характеризуется утратой оперативной памяти системы. При этом поражаются все выполняющиеся в момент сбоя транзакции, теряется содержимое всех буферов базы данных. Данные, хранящиеся на диске, остаются неповрежденными. Мягкий сбой может произойти, например, в результате аварийного отключения электрического питания или в результате неустранимого сбоя процессора. Жесткий сбой системы (аварийный отказ аппаратуры). Жесткий сбой характеризуется повреждением внешних носителей памяти. Жесткий сбой может произойти, например, в результате поломки головок дисковых накопителей.
Во всех трех случаях основой восстановления является избыточность данных, обеспечиваемая журналом транзакций.
Как и страницы базы данных, данные из журнала транзакций не записываются сразу на диск, а предварительно буферизируются в оперативной памяти. Таким образом, система поддерживает два вида буферов - буферы страниц базы данных и буферы журнала транзакций.
Страницы базы данных, содержимое которых в буфере (в оперативной памяти) отличается от содержимого на диске, называются "грязными" (dirty) страницами. Система постоянно поддерживает список "грязных" страниц - dirty-список. Запись "грязных" страниц из буфера на диск называется выталкиванием страниц во внешнюю память. Очевидно, необходимо предусмотреть такие правила выталкивания буферов базы данных и буферов журнала транзакций, которые обеспечивали бы два требования: Максимальную скорость выполнения транзакций. Для этого необходимо выталкивать страницы как можно реже. В идеале, если оперативная память была бы бесконечной, и сбои никогда бы не происходили, наилучшим выходом была бы загрузка всей базы данных в оперативную память, работа с данными только в оперативной памяти, и запись измененных страниц на диск только в момент завершения работы всей системы. Гарантию, что при возникновении сбоя (любого типа), данные завершенных транзакций можно было бы восстановить, а данные незавершенных транзакций бесследно удалить, т.е. обеспечение восстановления последнего согласованного состояния базы данных. Для этого что-то выталкивать на диск все-таки необходимо, даже если мы обладали бы бесконечной оперативной памятью.
Таким образом, имеется две причины для периодического выталкивания страниц во внешнюю память - недостаток оперативной памяти и возможность сбоев.
Основным принципом согласованной политики выталкивания буфера журнала и буферов страниц базы данных является то, что запись об изменении объекта базы данных должна попадать во внешнюю память журнала раньше, чем измененный объект оказывается во внешней памяти базы данных. Соответствующий протокол журнализации (и управления буферизацией) называется Write Ahead Log (WAL) - "пиши сначала в журнал", и состоит в том, что если требуется вытолкнуть во внешнюю память измененный объект базы данных, то перед этим нужно гарантировать выталкивание во внешнюю память журнала записи о его изменении. Это означает, что если во внешней памяти базы данных содержится объект, к которому применена некоторая команда модификации, то во внешней памяти журнала транзакций содержится запись об этой операции. Обратное неверно - если во внешней памяти журнала содержится запись о некотором изменении объекта, то во внешней памяти базы данных может и не быть самого измененного объекта.
Дополнительное условие на выталкивание буферов накладывается тем требованием, что каждая успешно завершившаяся транзакция должна быть реально зафиксирована во внешней памяти. Какой бы сбой не произошел, система должна быть в состоянии восстановить состояние базы данных, содержащее результаты всех зафиксированных к моменту сбоя транзакций.
Третьим условием выталкивания буферов является ограниченность объемов буферов базы данных и журнала транзакций. Периодически или при наступлении определенного события (например, количество страниц в dirty-списке превысило определенный порог, или количество свободных страниц в буфере уменьшилось и достигло критического значения) система принимает так называемую контрольную точку. Принятие контрольной точки включает выталкивание во внешнюю память содержимого буферов базы данных и специальную физическую запись контрольной точки, которая представляет собой список всех осуществляемых в данный момент транзакций.
Оказывается, что минимальным требованием, гарантирующим возможность восстановления последнего согласованного состояния базы данных, является выталкивание при фиксации транзакции во внешнюю память журнала всех записей об изменении базы данных этой транзакцией. При этом последней записью в журнал, производимой от имени данной транзакции, является специальная запись о конце этой транзакции.
Различные объекты предметной области, информация о которых хранится в базе данных, всегда взаимосвязаны друг с другом. Например, накладная на поставку товара содержит список товаров с количествами и ценами, сотрудник предприятия имеет детей, числится в подразделении и т.д. Термины "содержит", "имеет", "числится" отражают взаимосвязи между понятиями "накладная" и "список товаров", "сотрудник" и "дети", "сотрудник" и "подразделение". Такие взаимосвязи отражаются в реляционных базах данных при помощи внешних ключей, связывающих несколько отношений.
Рассмотрим пример с поставщиками и поставками деталей. Предположим, что нам требуется хранить информацию о наименовании поставщиков, наименовании и количестве поставляемых ими деталей, причем каждый поставщик может поставлять несколько деталей и каждая деталь может поставляться несколькими поставщиками. Можно предложить хранить данные в следующем отношении:
Стандарт языка SQL не содержит требований к восстановимости данных, оставляя эти вопросы на усмотрение разработчиков СУБД.
При жестком сбое база данных на диске нарушается физически. Основой восстановления в этом случае является журнал транзакций и архивная копия базы данных. Архивная копия базы данных должна создаваться периодически, а именно с учетом скорости наполнения журнала транзакций.
Восстановление начинается с обратного копирования базы данных из архивной копии. Затем выполняется просмотр журнала транзакций для выявления всех транзакций, которые закончились успешно до наступления сбоя. (Транзакции, закончившиеся откатом до наступления сбоя, можно не рассматривать). После этого по журналу транзакций в прямом направлении повторяются все успешно законченные транзакции. При этом нет необходимости отката транзакций, прерванных в результате сбоя, т.к. изменения, внесенными этими транзакциями, отсутствуют после восстановления базы данных из резервной копии.
Наиболее плохим случаем является ситуация, когда разрушены физически и база данных, и журнал транзакций. В этом случае единственное, что можно сделать - это восстановить состояние базы данных на момент последнего резервного копирования. Для того чтобы не допустить возникновение такой ситуации, базу данных и журнал транзакций обычно располагают на физически разных дисках, управляемых физически разными контроллерами.
Несмотря на протокол WAL, после мягкого сбоя не все физические страницы базы данных содержат измененные данные, т.к. не все "грязные" страницы базы данных были вытолкнуты во внешнюю память.
Последний момент, когда гарантированно были вытолкнуты "грязные" страницы - это момент принятия последней контрольной точки. Имеется 5 вариантов состояния транзакций по отношению к моменту последней контрольной точки и к моменту сбоя:
Рисунок 1 Пять вариантов транзакций
Последняя контрольная точка принималась в момент tc. Мягкий сбой системы произошел в момент tf. Транзакции T1-T5 характеризуются следующими свойствами: T1 - транзакция успешно завершена до принятия контрольной точки. Все данные этой транзакции сохранены в долговременной памяти - как записи журнала, так и страницы данных, измененные этой транзакцией. Для транзакции T1 никаких операций по восстановлению не требуется. T2 - транзакция начата до принятия контрольной точки и успешно завершена после контрольной точки, но до наступления сбоя. Записи журнала транзакций, относящиеся к этой транзакции вытолкнуты во внешнюю память. Страницы данных, измененные этой транзакцией, только частично вытолкнуты во внешнюю память. Для данной транзакции необходимо повторить заново те операции, которые были выполнены после принятия контрольной точки. T3 - транзакция начата до принятия контрольной точки и не завершена в результате сбоя. Такую транзакцию необходимо откатить. Проблема, однако, в том, что часть страниц данных, измененных этой транзакцией, уже содержится во внешней памяти - это те страницы, которые были обновлены до принятия контрольной точки. Следов изменений, внесенных после контрольной точки в базе данных нет. Записи журнала транзакций, сделанные до принятия контрольной точки, вытолкнуты во внешнюю память, те записи журнала, которые были сделаны после контрольной точки, отсутствуют во внешней памяти журнала. T4 - транзакция начата после принятия контрольной точки и успешно завершена до сбоя системы. Записи журнала транзакций, относящиеся к этой транзакции вытолкнуты во внешнюю память журнала. Изменения в базе данных, внесенные этой транзакцией, полностью отсутствуют во внешней памяти базы данных. Такую транзакцию необходимо повторить целиком. T5 - транзакция начата после принятия контрольной точки и не завершена в результате сбоя. Никаких следов этой транзакции нет ни во внешней памяти журнала транзакций, ни во внешней памяти базы данных. Для такой транзакции никаких действий предпринимать не нужно, ее как бы и не было вовсе.
Восстановление системы после мягкого сбоя осуществляется как часть процедуры перезагрузки системы. При перезагрузке системы транзакции T2 и T4 необходимо частично или полностью повторить, транзакцию T3 - частично откатить, для транзакций T1 и T5 никаких действий предпринимать не нужно. При перезагрузке система выполняет следующие действия:
Создается два списка транзакций UNDO (отменить) и REDO (повторить). В список UNDO заносятся все транзакции из последней записи контрольной точки (т.е. все транзакции, выполнявшиеся в момент принятия контрольной точки). Список REDO остается пустым. В нашем случае будет: UNDO = {T2, T3}, REDO = { }.
Начиная с записи контрольной точки просматривается вперед журнал транзакций.
Если в журнале транзакций обнаруживается запись о начале транзакции, то эта транзакция добавляется в список UNDO. В нашем случае будет: UNDO = {T2, T3, T4}, REDO = { }. Заметим, что следов транзакции T5 в журнале транзакций нет.
Если в файле регистрации обнаруживается запись COMMIT об окончании транзакции, то эта транзакция добавляется в список REDO. В нашем случае будет: UNDO = {T2, T3, T4}, REDO = {T2, T4}. Заметим, что записи о конце этих транзакций имеются во внешней памяти журнала транзакций в соответствии с минимальным требованием выталкивания записей журнала при фиксации транзакции.
Когда достигается конец журнала транзакций, оба списка анализируются. При этом из списка UNDO удаляются те транзакции, которые попали в список REDO. В нашем случае будет: UNDO = {T3}, REDO = {T2, T4}.
После этого система просматривает журнал транзакций назад, начиная с момента контрольной точки и откатывая все транзакции из списка UNDO. В нашем случае будут откатываться те операции транзакции T3, которые были выполнены до принятия контрольной точки.
Окончательно, система просматривает журнал транзакций вперед, начиная с момента контрольной точки, и повторно выполняет все операции транзакций из списка REDO. В нашем случае, система выполнит повторно все операции транзакции T4 и те операции транзакции T2, которые были выполнены после принятия контрольной точки.
второй нормальной форме (2НФ) тогда и только тогда, когда отношение находится в 1НФ и нет неключевых атрибутов, зависящих от части сложного ключа.
Отношения в 2НФ "лучше", чем в 1НФ, но еще недостаточно "хороши" - остается часть аномалий обновления, по-прежнему требуются триггеры, поддерживающие целостность базы данных.
Отношение 
третьей нормальной форме (3НФ) тогда и только тогда, когда отношение находится в 2НФ и все неключевые атрибуты взаимно независимы.
Отношения в 3НФ являются самыми "хорошими" с точки зрения выбранных нами критериев - устранены аномалии обновления, требуются только стандартные триггеры для поддержания ссылочной целостности.
Переход от ненормализованных отношений к отношениям в 3НФ может быть выполнен при помощи алгоритма нормализации. Алгоритм нормализации заключается в последовательной декомпозиции отношений для устранения функциональных зависимостей атрибутов от части сложного ключа (приведение к 2НФ) и устранения функциональных зависимостей неключевых атрибутов друг от друга (приведение к 3НФ).
Корректность процедуры нормализации (декомпозиция без потери информации) доказывается теоремой Хеза.
нормальной форме Бойса-Кодда (НФБК) тогда и только тогда, когда детерминанты всех функциональных зависимостей являются потенциальными ключами.
Нормализация отношений вплоть до нормальной формы Бойса-Кодда основывалась на понятии функциональной зависимости и теореме Хеза, гарантировавшей, что декомпозиция будет происходить без потерь информации.
Дальнейшая нормализация связана уже с обобщением понятия функциональной зависимости.
Атрибуты (множества атрибутов) 
многозначно зависят от 
), тогда и только тогда, когда из того, что в отношении 
и 
содержится также и кортеж к
Корректность дальнейшей декомпозиции основывается на теореме Фейджина, которая говорит о том, что декомпозиция отношения на две проекции является декомпозицией без потерь тогда и только тогда, когда в отношении имеется некоторая многозначная зависимость.
Если в отношении имеется функциональная зависимость, то автоматически имеется и тривиальная многозначная зависимость, определяемая этой функциональной зависимостью.
Многозначная зависимость 
нетривиальной многозначной зависимостью, если не существует функциональных зависимостей 
.
Отношение 
четвертой нормальной форме (4НФ) тогда и только тогда, когда отношение находится в НФБК и не содержит нетривиальных многозначных зависимостей.
Имеют место зависимости специального вида, когда отношение не может быть подвергнуто декомпозиции без потерь на две проекции, но может быть декомпозировано на большее число проекций. Такие зависимости называются зависимостями соединения и являются обобщением понятия многозначной зависимости.
Отношение 
пятой нормальной форме (5НФ) тогда и только тогда, когда любая имеющаяся зависимость соединения является тривиальной.
На самом деле приведенные правила целостности сущностей и внешних ключей прямо следуют из определений понятий "потенциальный ключ" и "внешний ключ".
Действительно, в определении потенциального ключа требуется, чтобы потенциальный ключ обладал свойством уникальности. Это фактически означает, что мы должны уметь различать значения потенциальных ключей, т.е. при сравнении двух значений потенциального ключа мы всегда должны получать значения либо ИСТИНА, либо ЛОЖЬ. Но любое сравнение, в которое входит null-значение, принимает значение U - НЕИЗВЕСТНО, откуда следует, что атрибуты потенциального ключа не могут содержать null-значений.
Для внешних ключей правило целостности фактически входит в определение (п. 2 определения 2).
Таким образом, с точки зрения реляционной теории, явная формулировка правил целостности является излишней - они автоматически вытекают из определений понятий ключа и внешнего ключа.
Тем не менее, явная формулировка правил целостности имеет определенный практический смысл. В большинстве серьезных СУБД за выполнением этих ограничений следит сама СУБД, если, конечно, пользователь явно объявил потенциальные и внешние ключи. Но, во-первых, для некоторых систем можно допустить, чтобы эти ограничения не выполнялись, а во-вторых, некоторые системы просто не поддерживают понятия целостности, например, некоторые "настольные" СУБД типа FoxPro 2.5. В этих случаях за целостностью данных должен следить сам пользователь, или программист, разрабатывающий приложение для пользователя.
Явная формулировка правил целостности помогает четко понять, какие опасности несет в себе пренебрежение этими правилами.
Реляционная алгебра представляет собой набор операторов, использующих отношения в качестве аргументов, и возвращающие отношения в качестве результата. Таким образом, реляционный оператор 
Реляционная алгебра является замкнутой, т.к. в качестве аргументов в реляционные операторы можно подставлять другие реляционные операторы, подходящие по типу:
Таким образом, в реляционных выражениях можно использовать вложенные выражения сколь угодно сложной структуры.
Каждое отношение обязано иметь уникальное имя в пределах базы данных. Имя отношения, полученного в результате выполнения реляционной операции, определяется в левой части равенства. Однако можно не требовать наличия имен от отношений, полученных в результате реляционных выражений, если эти отношения подставляются в качестве аргументов в другие реляционные выражения. Такие отношения будем называть неименованными отношениями. Неименованные отношения реально не существуют в базе данных, а только вычисляются в момент вычисления значения реляционного оператора.
Традиционно, вслед за Коддом [43], определяют восемь реляционных операторов, объединенных в две группы.
Теоретико-множественные операторы: Объединение Пересечение Вычитание Декартово произведение
Специальные реляционные операторы: Выборка Проекция Соединение Деление
Не все они являются независимыми, т.е. некоторые из этих операторов могут быть выражены через другие реляционные операторы.
Несмотря на мощь языка реляционной алгебры, имеется ряд типов запросов, которые принципиально нельзя выразить только при помощи операторов реляционной алгебры. Это вовсе не означает, что ответы на эти запросы нельзя получить вообще. Просто, для получения ответов на подобные запросы приходится применять процедурные расширения реляционных языков.
Как было сказано в начале главы, не все операторы реляционной алгебры являются независимыми - некоторые из них выражаются через другие реляционные операторы.
