Оставшиеся аномалии удаления (DELETE)

При удалении некоторых данных по-прежнему может произойти потеря другой информации. Например, если удалить сотрудника Сидорова, то будет потеряна информация о том, что в отделе номер 2 находится телефон 33-22-11.

Причина аномалии - хранение в одном отношении разнородной информации (и о сотрудниках, и об отделах).

Вывод - логическая модель данных неадекватна модели предметной области. База данных, основанная на такой модели, будет работать неправильно.

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

Оставшиеся аномалии вставки (INSERT)

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

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

Вывод - увеличивается сложность разработки базы данных. База данных, основанная на такой модели, будет работать правильно только при наличии дополнительного программного кода в виде триггеров.

Отбор данных из нескольких таблиц

Пример 13. Естественное соединение таблиц (способ 1 - явное указание условий соединения): SELECT P.PNUM, P.PNAME, PD.DNUM, PD.VOLUME FROM P, PD WHERE P.PNUM = PD.PNUM;

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

Отбор данных из одной таблицы

Пример 6. Выбрать все данные из таблицы поставщиков (ключевые слова SELECT- FROM-): SELECT * FROM P;

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

Пример 7. Выбрать все строки из таблицы поставщиков, удовлетворяющих некоторому условию (ключевое слово WHERE-): SELECT * FROM P WHERE P.PNUM > 2;

Замечание. В качестве условия в разделе WHERE можно использовать сложные логические выражения, использующие поля таблиц, константы, сравнения (>, <, = и т.д.), скобки, союзы AND и OR, отрицание NOT.

Пример 8. Выбрать некоторые колонки из исходной таблицы (указание списка отбираемых колонок): SELECT P.NAME FROM P;

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

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

Пример 9. Выбрать некоторые колонки из исходной таблицы, удалив из результата повторяющиеся строки (ключевое слово DISTINCT): SELECT DISTINCT P.NAME FROM P;

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

Пример 10. Использование скалярных выражений и переименований колонок в запросах (ключевое слово AS-): SELECT TOVAR.TNAME, TOVAR.KOL, TOVAR.PRICE, "=" AS EQU, TOVAR.KOL*TOVAR.PRICE AS SUMMA FROM TOVAR;

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

Отношение

Определение 6. Подмножество

декартового произведения множеств

называется отношением степени n (n-арным отношением).

Определение 7. Мощность множества кортежей, входящих в отношение

, называют мощностью отношения

Замечание. Понятие отношения является очень важным не только с математической точки зрения. Понятие отношения фактически лежит в основе всей реляционной теории баз данных. Как будет показано ниже, отношения являются математическим аналогом таблиц. Сам термин "реляционное представление данных", впервые введенный Коддом [43], происходит от термина relation, понимаемом именно в смысле этого определения.

Т.к. любое множество можно рассматривать как декартовое произведение степени 1, то любое подмножество, как и любое множество, можно считать отношением степени 1. Это не очень интересный пример, свидетельствующий лишь о том, что термины "отношение степени 1" и "подмножество" являются синонимами. Нетривиальность понятия отношения проявляется, когда степень отношения больше 1. Ключевыми здесь являются два момента:

Во-первых, все элементы отношения есть однотипные кортежи. Однотипность кортежей позволяет считать их аналогами строк в простой таблице, т.е. в такой таблице, в которой все строки состоят из одинакового числа ячеек и в соответствующих ячейках содержатся одинаковые типы данных. Например, отношение, состоящее из трех следующих кортежей {(1, "Иванов", 1000), (2, "Петров", 2000), (3, "Сидоров", 3000)} можно считать таблицей, содержащей данные о сотрудниках и их зарплатах. Такая таблица будет иметь три строки и три колонки, причем в каждой колонке содержатся данные одного типа.

В противоположность этому рассмотрим множество {(1), (1, 2), (1, 2, 3)}, состоящее из разнотипных числовых кортежей. Это множество не является отношением ни в

, ни в

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

, но такая трактовка ничего нового, по сравнению с понятием подмножества, не дает.

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

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

Действительно, каждому отношению можно поставить в соответствие некоторое логическое выражение

, зависящее от n параметров (n-местный предикат) и определяющее, будет ли кортеж

принадлежать отношению

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

. Более точно, кортеж

принадлежит отношению

тогда и только тогда, когда предикат этого отношения

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

Если это не вызывает путаницы, удобно и отношение, и его предикат обозначать одной и той же буквой. Например, отношение

имеет предикат

Отношение эквивалентности

Определение 8. Отношение

на множестве

называется отношением эквивалентности, если оно обладает следующими свойствами:

для всех

(рефлексивность) Если

, то

(симметричность) Если

, то

(транзитивность)

Обычно отношение эквивалентности обозначают знаком

или

и говорят, что оно (отношение) задано на множестве

(а не на

). Условия 1-3 в таких обозначениях выглядят более естественно:

для всех

(рефлексивность) Если

, то

(симметричность) Если

, то

(транзитивность)

Легко доказывается, что если на множестве

задано отношение эквивалентности, то множество

разбивается на взаимно непересекающиеся подмножества, состоящие из эквивалентных друг другу элементов (классы эквивалентности).

Пример 1. Рассмотрим на множестве вещественных чисел

отношение, заданное просто равенством чисел. Предикат такого отношения:

, или просто

Условия 1-3, очевидно, выполняются, поэтому данное отношение является отношением эквивалентности. Каждый класс эквивалентности этого отношения состоит из одного числа.

Пример 2. Рассмотрим более сложное отношение эквивалентности. На множестве целых чисел

зададим отношение "равенство по модулю n" следующим образом: два числа

равны по модулю n, если их остатки при делении на n равны. Например, по модулю 5 равны числа 2, 7, 12 и т.д.

Условия 1-3 легко проверяются, поэтому равенство по модулю является отношением эквивалентности. Предикат этого отношения имеет вид:

Классы эквивалентности этого отношения состоят из чисел, дающих при делении на n одинаковые остатки. Таких классов ровно n: [0] = {0, n, 2n, -} [1] = {1, n+1, 2n+1, -} - [n-1] = {n-1, n+n-1, 2n+n-1, -}

Отношения атрибуты кортежи отношения

Отношения, атрибуты, кортежи отношения

Отношения порядка

Определение 9. Отношение

на множестве

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

для всех

(рефлексивность) Если

, то

(антисимметричность) Если

, то

(транзитивность)

Обычно отношение порядка обозначают знаком

. Если для двух элементов

выполняется

, то говорят, что

"предшествует"

. Как и для отношения эквивалентности, условия 1-3 в таких обозначениях выглядят более естественно:

для всех

(рефлексивность) Если

, то

(антисимметричность) Если

, то

(транзитивность)

Пример 3. Простым примером отношения порядка является отношение, задаваемое обычным неравенством

на множестве вещественных чисел

. Заметим, что для любых чисел

выполняется либо

, либо

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

Предикат данного отношения есть просто утверждение

Пример 4. Рассмотрим на множестве

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

предшествует сотруднику

тогда и только тогда, когда выполняется одно из условий:

является начальником (не обязательно непосредственным)

Назовем такое отношение "быть начальником". Легко проверить, что отношение "быть начальником" является отношением порядка. Заметим, что в отличие от предыдущего примера, существуют такие пары сотрудников

, для которых не выполняется ни

, ни

(например, если

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

Отношения совместимые по типу

Отношения, совместимые по типу

Некоторые реляционные операторы (например, объединение) требуют, чтобы отношения имели одинаковые заголовки. Действительно, отношения состоят из заголовка и тела. Операция объединения двух отношений есть просто объединение двух множеств кортежей, взятых из тел соответствующих отношений. Но будет ли результат отношением? Во-первых, если исходные отношения имеют разное количество атрибутов, то, очевидно, что множество, являющееся объединением таких разнотипных кортежей нельзя представить в виде отношения. Во-вторых, пусть даже отношения имеют одинаковое количество атрибутов, но атрибуты имеют различные наименования. Как тогда определить заголовок отношения, полученного в результате объединения множеств кортежей? В-третьих, пусть отношения имеют одинаковое количество атрибутов, атрибуты имеют одинаковые наименования, но определенны на различных доменах. Тогда снова объединение кортежей не будет образовывать отношение.

Определение 1. Будем называть отношения совместимыми по типу, если они имеют идентичные заголовки, а именно, Отношения имеют одно и то же множество имен атрибутов, т.е. для любого атрибута в одном отношении найдется атрибут с таким же наименованием в другом отношении, Атрибуты с одинаковыми именами определены на одних и тех же доменах.

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

Пересечение

Определение 3. Пересечением двух совместимых по типу отношений

называется отношение с тем же заголовком, что и у отношений

, и телом, состоящим из кортежей, принадлежащих одновременно обоим отношениям

Синтаксис операции пересечения:

Пример 3. Для тех же отношений

, что и в предыдущем примере пересечение имеет вид:

Первая нормальная форма

Труднее всего дать определение вещей, которые всем понятны. Если давать не строгое, описательное определение, то всегда остается возможность неправильной его трактовки. Если дать строгое формальное определение, то оно, как правило, или тривиально, или слишком громоздко. Именно такая ситуация с определением отношения в Первой Нормальной Форме (1НФ). Совсем не говорить об этом нельзя, т.к. на основе 1НФ строятся более высокие нормальные формы, которые рассматриваются далее в гл. 6 и 7. Дать определение 1НФ сложно ввиду его тривиальности. Поэтому, дадим просто несколько объяснений.

Объяснение 1. Говорят, что отношение

находится в 1НФ, если оно удовлетворяет определению 2.

Это, собственно, тавтология, ведь из определения 2 следует, что других отношений не бывает. Действительно, определение 2 описывает, что является отношением, а что - нет, следовательно, отношений в непервой нормальной форме просто нет.

Объяснение 2. Говорят, что отношение

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

Опять же, определение 2 опирается на понятие домена, а домены определены на простых типах данных.

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

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

Таким образом появляется третье объяснение Первой Нормальной Формы:

Объяснение 3. Отношение

находится в 1НФ, если оно является плоской таблицей.

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

Плохая нормализация отношений

Данный пример взят из книги Гилуа М.М. [6, стр.43].

Пример 16. Пусть имеется отношение ХИМИЧЕСКИЙ_СОСТАВ_ВЕЩЕСТВ с набором атрибутов (Наименование вещества, Водород, Гелий, -, 105_элемент). Значением атрибута "Вещество" являются наименования химических веществ, значениями остальных атрибутов - процентный состав соответствующих элементов в этом веществе. Такое отношение могло бы иметь, к примеру, следующий вид:

Понятие транзакции

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

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

Транзакция обычно начинается автоматически с момента присоединения пользователя к СУБД и продолжается до тех пор, пока не произойдет одно из следующих событий: Подана команда COMMIT WORK (зафиксировать транзакцию). Подана команда ROLLBACK WORK (откатить транзакцию). Произошло отсоединение пользователя от СУБД. Произошел сбой системы.

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

Замечание. Некоторые системы (например, Visual FoxPro), требуют подать явную команду BEGIN TRANSACTION для того, чтобы начать новую транзакцию.

Команда ROLLBACK WORK приводит к тому, что все изменения, сделанные текущей транзакцией откатываются, т.е. отменяются так, как будто их вообще не было. При этом автоматически начинается новая транзакция.

При отсоединении пользователя от СУБД происходит автоматическая фиксация транзакций.

При сбое системы происходят более сложные процессы. Кратко суть их сводится к тому, что при последующем запуске системы происходит анализ выполнявшихся до момента сбоя транзакций. Те транзакции, для которых была подана команда COMMIT WORK, но результаты работы которых не были занесены в базу данных выполняются снова (накатываются). Те транзакции, для которых не была подана команда COMMIT WORK, откатываются. Более подробно восстановление после сбоев рассматривается далее.

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

Свойство Д (долговечность) также не является абсолютными свойством, т.к. некоторые системы допускают вложенные транзакции. Если транзакция Б запущена внутри транзакции А, и для транзакции Б подана команда COMMIT WORK, то фиксация данных транзакции Б является условной, т.к. внешняя транзакция А может откатиться. Результаты работы внутренней транзакции Б будут окончательно зафиксированы только если будет зафиксирована внешняя транзакция А.

Порядок выполнения оператора SELECT

Для того чтобы понять, как получается результат выполнения оператора SELECT, рассмотрим концептуальную схему его выполнения. Эта схема является именно концептуальной, т.к. гарантируется, что результат будет таким, как если бы он выполнялся шаг за шагом в соответствии с этой схемой. На самом деле, реально результат получается более изощренными алгоритмами, которыми "владеет" конкретная СУБД.

Потенциальные ключи

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

Определение 1. Пусть дано отношение

. Подмножество атрибутов

отношения

будем называть потенциальным ключом, если

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

. Свойством неизбыточности - никакое подмножество в

не обладает свойством уникальности.

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

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

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

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

Предикатные блокировки

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

Поскольку любая операция над реляционной базой данных задается некоторым условием (т.е. в ней указывается не конкретный набор объектов базы данных, над которыми нужно выполнить операцию, а условие, которому должны удовлетворять объекты этого набора), то удобным способом было бы S или X-блокирование именно этого условия. Однако при попытке использовать этот метод в реальной СУБД возникает трудность определения совместимости различных условий. Действительно, в языке SQL допускаются условия с подзапросами и другими сложными предикатами. Проблема совместимости сравнительно легко решается для случая простых условий, имеющих вид:

{Имя атрибута {= | <> | > | >= | < | <=} Значение}

[{OR | AND} {Имя атрибута {= | <> | > | >= | < | <=} Значение}.,..]

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

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

Преднамеренные блокировки

Как видно из анализа поведения транзакций, при использовании протокола доступа к данным не решается проблема фантомов. Это происходит оттого, что были рассмотрены только блокировки на уровне строк. Можно рассматривать блокировки и других объектов базы данных: Блокировка самой базы данных. Блокировка файлов базы данных. Блокировка таблиц базы данных. Блокировка страниц (Единиц обмена с диском, обычно 2-16 Кб. На одной странице содержится несколько строк одной или нескольких таблиц). Блокировка отдельных строк таблиц. Блокировка отдельных полей.

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

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

Современные СУБД, как правило, поддерживают минимальный уровень блокировки на уровне строк или страниц. (В старых версиях настольной СУБД Paradox поддерживалась блокировка на уровне отдельных полей.).

При использовании блокировок объектов разной величины возникает проблема обнаружения уже наложенных блокировок. Если транзакция A пытается заблокировать таблицу, то необходимо иметь информацию, не наложены ли уже блокировки на уровне строк этой таблицы, несовместимые с блокировкой таблицы. Для решения этой проблемы используется протокол преднамеренных блокировок, являющийся расширением протокола доступа к данным. Суть этого протокола в том, что перед тем, как наложить блокировку на объект (например, на строку таблицы), необходимо наложить специальную преднамеренную блокировку (блокировку намерения) на объекты, в состав которых входит блокируемый объект - на таблицу, содержащую строку, на файл, содержащий таблицу, на базу данных, содержащую файл. Тогда наличие преднамеренной блокировки таблицы будет свидетельствовать о наличии блокировки строк таблицы и для другой транзакции, пытающейся блокировать целую таблицу не нужно проверять наличие блокировок отдельных строк. Более точно, вводятся следующие новые типы блокировок: Преднамеренная блокировка с возможностью взаимного доступа (IS-блокировка - Intent Shared lock). Накладывается на некоторый составной объект T и означает намерение блокировать некоторый входящий в T объект в режиме S-блокировки. Например, при намерении читать строки из таблицы T, эта таблица должна быть заблокирована в режиме IS (до этого в таком же режиме должен быть заблокирован файл). Преднамеренная блокировка без взаимного доступа (IX-блокировка - Intent eXclusive lock). Накладывается на некоторый составной объект T и означает намерение блокировать некоторый входящий в T объект в режиме X-блокировки. Например, при намерении удалять или модифицировать строки из таблицы T эта таблица должна быть заблокирована в режиме IX (до этого в таком же режиме должен быть заблокирован файл). Преднамеренная блокировка как с возможностью взаимного доступа, так и без него (SIX-блокировка - Shared Intent eXclusive lock). Накладывается на некоторый составной объект T и означает разделяемую блокировку всего этого объекта с намерением впоследствии блокировать какие-либо входящие в него объекты в режиме X-блокировок. Например, если выполняется длинная операция просмотра таблицы с возможностью удаления некоторых просматриваемых строк, то можно заблокировать эту таблицу в режиме SIX (до этого захватить файл в режиме IS).

IS, IX и SIX-блокировки должны накладываться на сложные объекты базы данных (таблицы, файлы). Кроме того, на сложные объекты могут накладываться и блокировки типов S и X. Для сложных объектов (например, для таблицы базы данных) таблица совместимости блокировок имеет следующий вид:

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

Допустимые стратегии:

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

SET NULL (УСТАНОВИТЬ В NULL) - обновить кортеж, но в качестве значения внешнего ключа занести не предлагаемое пользователем некорректное значение, а null-значение.

SET DEFAULT (УСТАНОВИТЬ ПО УМОЛЧАНИЮ) - обновить кортеж, но в качестве значения внешнего ключа занести не предлагаемое пользователем некорректное значение, а некоторое значение, принятое по умолчанию.

IGNORE (ИГНОРИРОВАТЬ) - обновить кортеж, не обращая внимания на нарушения ссылочной целостности.

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

Допустимые стратегии:

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

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

SET NULL (УСТАНОВИТЬ В NULL) - выполнить обновление и во всех кортежах дочернего отношения, ссылающихся на обновляемый кортеж, изменить значения внешних ключей на null-значение.

SET DEFAULT (УСТАНОВИТЬ ПО УМОЛЧАНИЮ) - выполнить обновление и во всех кортежах дочернего отношения, ссылающихся на обновляемый кортеж, изменить значения внешних ключей на некоторое значение, принятое по умолчанию.

IGNORE (ИГНОРИРОВАТЬ) - выполнить обновление, не обращая внимания на нарушения ссылочной целостности.

При удалении кортежа в родительском отношении

Допустимые стратегии:

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

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

SET NULL (УСТАНОВИТЬ В NULL) - выполнить удаление и во всех кортежах дочернего отношения, ссылающихся на удаляемый кортеж, изменить значения внешних ключей на null-значение.

SET DEFAULT (УСТАНОВИТЬ ПО УМОЛЧАНИЮ) - выполнить удаление и во всех кортежах дочернего отношения, ссылающихся на удаляемый кортеж, изменить значения внешних ключей на некоторое значение, принятое по умолчанию.

IGNORE (ИГНОРИРОВАТЬ) - выполнить удаление, не обращая внимания на нарушения ссылочной целостности.

При вставке кортежа в дочернее отношение

Допустимые стратегии:

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

SET NULL (УСТАНОВИТЬ В NULL) - вставить кортеж, но в качестве значения внешнего ключа занести не предлагаемое пользователем некорректное значение, а null-значение.

SET DEFAULT (УСТАНОВИТЬ ПО УМОЛЧАНИЮ) - вставить кортеж, но в качестве значения внешнего ключа занести не предлагаемое пользователем некорректное значение, а некоторое значение, принятое по умолчанию.

IGNORE (ИГНОРИРОВАТЬ) - вставить кортеж, не обращая внимания на нарушения ссылочной целостности.

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

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

и текстовые редакторы позволяют хранить

Пример 1

ОтделСотрудникиДети сотрудников (интересы)

Цех	Иванов И.И.	Маша	ЛЕГО
Петя	Книги	Видео
Саша	Компьютеры
Дима	Спорт
Петров П.П.	Артур	Ничем не интересуется
Сидоров С.С.	Сергей	Компьютеры Книги
Валерий	Книги
Станислав	Видео
Бухгалтерия	-	-

Таблица 1 Таблица произвольной формы

Конечно, и электронные таблицы, и текстовые редакторы позволяют хранить и обрабатывать данные очень гибко, но как быть, если требуется хранить информацию обо всех сотрудниках большого предприятия и периодически выдавать ответы на запросы типа "представить список всех сотрудников, принятых на работу не позднее трех лет назад, имеющих по крайней мере одного ребенка, не имеющих взысканий и с зарплатой не выше 1000 р.". Для получения ответов на подобные запросы и предназначены Системы Управления Базами Данных (СУБД).

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

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

В свою очередь, на основе реляционной модели были разработаны различные языки для доступа к реляционным данным, такие как SEQUEL, SQL, QUEL и другие. Фактическим промышленным стандартом в настоящее время стал язык SQL (Structured Query Language - язык структурированных запросов).

Различные фирмы, производители СУБД, предлагают свои реализации языка SQL. Эти реализации отличаются как друг от друга, так и от стандартизованного языка SQL. Это и хорошо и плохо. Хорошо это тем, что конкретная реализация языка, может включать в себя более широкие возможности по сравнению со стандартизованными SQL, например, больше типов данных, большее количество команд, больше дополнительных опций имеющихся команд. Такие возможности делают работу с конкретной СУБД более эффективной. Кроме того, такие нестандартные возможности языка проходят практическую апробацию и со временем могут быть включены в стандарт. Плохо же это тем, что различия в синтаксисе реализаций SQL затрудняют перенос приложений из одной системы в другую. Например, если приложение было написано для базы данных MS SQL Server с использованием своего диалекта SQL - языка Transact-SQL, то при переносе системы в базу данных ORACLE, не все конструкции языка будут понятны соответствующему диалекту SQL - языку PL/SQL.

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

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

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

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

Пятая глава содержит краткое описание и примеры применения стандартного языка доступа к реляционным данным - языка SQL.

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

В восьмой главе описывается альтернативный способ разработки таблиц в нормальной форме - модель "сущность-связь".

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

Оглавление

Вперед

Каталог

Индекс раздела

Способ 4. При помощи таблицы

Пример 1

Вовочка Петя Маша Лена Вовочка Петя Маша Лена

Кого Кто
Любит
		Любит
	Любит	Любит
	Любит

Таблица 1. Матрица взаимоотношений

Способ 4. При помощи таблицы фактов:

Пример 2

Кто любит Кого любят

Вовочка	Вовочка
Петя	Маша
Маша	Петя
Маша	Маша
Лена	Петя

Таблица 2 Таблица фактов

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

Что касается предиката данного отношения, то он имеет следующий вид (дизъюнктивная нормальная форма):

R(x,y) = {(x = "Вовочка" AND y = "Вовочка") OR (x = "Петя" AND y = "Маша") OR (x = "Маша" AND y = "Петя") OR (x = "Маша" AND y = "Маша") OR (x = "Лена" AND y = "Петя")}

Замечание. Приведенное отношение не является ни транзитивным, ни симметричным или антисимметричным, ни рефлексивным, поэтому оно не является ни отношением эквивалентности, ни отношением порядка, ни каким-либо другим разумным отношением.

Замечание. Большая часть мировой литературы существует и имеет смысл лишь постольку, поскольку бинарное отношение "любить" не является отношением эквивалентности. В частности, по этой причине человечество не разбивается на классы эквивалентности взаимно любящих особей. Изучением характеристик данного отношения и соответствующего ему предиката занималось (и продолжает заниматься) большое количество экспертов, таких как Толстой Л.Н., Шекспир В. и др.

Определение 3. Реляционной базой данных

Пример 1

Номер_сотрудника Фамилия Зарплата Номер_отдела

1	Иванов	1000	1
2	Петров	2000	2
3	Сидоров	3000	1

Таблица 1 Отношение "Сотрудники"

Определение 3. Реляционной базой данных называется набор отношений.

Определение 4. Схемой реляционной базы данных называется набор заголовков отношений, входящих в базу данных.

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

Термины, которыми оперирует реляционная модель данных, имеют соответствующие "табличные" синонимы:

Таблица истинности

Пример 1

AND F T U F T U

F	F	F
F	T	U
F	U	U

Таблица 1 Таблица истинности AND

Отношение

Пример 1

Табельный номер Фамилия Зарплата

1	Иванов	1000
2	Петров	2000
3	Сидоров	3000

Таблица 1 Отношение A

VOLUME FROM PD ORDER BY

Пример 1

TNAME KOL PRICE EQU SUMMA

Болт	10	100	=	1000
Гайка	20	200	=	4000
Винт	30	300	=	9000

Пример 11.Упорядочение результатов запроса (ключевое слово ORDER BY-): SELECT PD.PNUM, PD.DNUM, PD. VOLUME FROM PD ORDER BY DNUM;

В результате получим следующую таблицу, упорядоченную по полю DNUM:

Отношение

Пример 1

Н_СОТР ФАМ Н_ОТД ТЕЛ Н_ПРО ПРОЕКТ Н_ЗАДАН

1	Иванов	1	11-22-33	1	Космос	1
1	Иванов	1	11-22-33	2	Климат	1
2	Петров	1	11-22-33	1	Космос	2
3	Сидоров	2	33-22-11	1	Космос	3
3	Сидоров	2	33-22-11	2	Климат	2

Таблица 1 Отношение СОТРУДНИКИ_ОТДЕЛЫ_ПРОЕКТЫ

Данное отношение содержит два потенциальных

Пример 1

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

1	Фирма 1	1	100
1	Фирма 1	2	200
1	Фирма 1	3	300
2	Фирма 2	1	150
2	Фирма 2	2	250
3	Фирма 3	1	1000

Таблица 1 Отношение "Поставки"

Данное отношение содержит два потенциальных ключа - {PNUM, DNUM} и {PNAME, DNUM}. Видно, что данные хранятся в отношении с избыточностью - при изменении наименования поставщика, это наименование нужно изменить во всех кортежах, где оно встречается. Можно ли эту аномалию устранить при помощи алгоритма нормализации, описанного в предыдущей главе? Для этого нужно выявить имеющиеся функциональные зависимости (как обычно, курсивом выделены ключевые атрибуты):

PNUM

PNAME - наименование поставщика зависит от номера поставщика.

PNAME

PNUM - номер поставщика зависит от наименования поставщика.

{PNUM, DNUM}

VOLUME - поставляемое количество зависит от первого ключа отношения.

{PNUM, DNUM}

PNAME - наименование поставщика зависит от первого ключа отношения.

{PNAME, DNUM}

VOLUME - поставляемое количество зависит от второго ключа отношения.

{PNAME, DNUM}

PNUM - номер поставщика зависит от второго ключа отношения.

Данное отношение не содержит неключевых атрибутов, зависящих от части сложного ключа (см. определение 2НФ). Действительно, от части сложного ключа зависят атрибуты PNAME и PNUM, но они сами являются ключевыми. Таким образом, отношение находится в 2НФ.

Кроме того, отношение не содержит зависимых друг от друга неключевых атрибутов, т.к. неключевой атрибут всего один - VOLUME (см. определение 3НФ). Таким образом, показано, что отношение "Поставки" находится в 3НФ.

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

Пример DEPART

Пример 1

Dept_Id Dept_Name Dept_Kol

1	Кафедра алгебры	3
2	Кафедра программирования	2

Таблица 1 DEPART

После окончания обеих транзакций, строка

Пример 1

Транзакция A Время Транзакция B Потеря результата обновления

Чтение		---
---		Чтение
Запись		---
---		Запись
Фиксация транзакции		---
---		Фиксация транзакции

Результат. После окончания обеих транзакций, строка

содержит значение

, занесенное более поздней транзакцией B. Транзакция A ничего не знает о существовании транзакции B, и естественно ожидает, что в строке

содержится значение

. Таким образом, транзакция A потеряла результаты своей работы.

С точки зрения реляционных баз

Пример 2

Кто любит Кого любят

Вовочка	Вовочка
Петя	Маша
Маша	Петя
Маша	Маша
Лена	Петя

Таблица 2 Таблица фактов

Что касается предиката данного отношения, то он имеет следующий вид (дизъюнктивная нормальная форма):

Схема базы

Пример 2

Реляционный термин Соответствующий "табличный" термин

База данных	Набор таблиц
Схема базы данных	Набор заголовков таблиц
Отношение	Таблица
Заголовок отношения	Заголовок таблицы
Тело отношения	Тело таблицы
Атрибут отношения	Наименование столбца таблицы
Кортеж отношения	Строка таблицы
Степень (-арность) отношения	Количество столбцов таблицы
Мощность отношения	Количество строк таблицы
Домены и типы данных	Типы данные в ячейках таблицы

Таблица истинности

Пример 2

OR F T U F T U

F	T	U
T	T	T
U	T	U

Таблица 2 Таблица истинности OR

Отношение

Пример 2

Табельный номер Фамилия Зарплата

1	Иванов	1000
2	Пушников	2500
4	Сидоров	3000

Таблица 2 Отношение B

Объединение отношений

будет иметь вид:

Упорядочение результатов запроса по нескольким

Пример 2

PNUM DNUM VOLUME

1	1	100
2	1	150
3	1	1000
1	2	200
2	2	250
1	3	300

Пример 12. Упорядочение результатов запроса по нескольким полям с возрастанием или убыванием (ключевые слова ASC, DESC): SELECT PD.PNUM, PD.DNUM, PD.VOLUME FROM PD ORDER BY DNUM ASC, VOLUME DESC;

В результате получим таблицу, в которой строки идут в порядке возрастания значения поля DNUM, а строки, с одинаковым значением DNUM идут в порядке убывания значения поля VOLUME:

Отношение

Пример 2

Н_СОТР ФАМ Н_ОТД ТЕЛ

1	Иванов	1	11-22-33
2	Петров	1	11-22-33
3	Сидоров	2	33-22-11

Таблица 2 Отношение СОТРУДНИКИ_ОТДЕЛЫ

Отношение ПРОЕКТЫ (Н_ПРО, ПРОЕКТ):

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

Н_ПРО

ПРОЕКТ

Отношение

Пример 2

Номер поставщика
PNUM Наименование поставщика
PNAME 1 Фирма 1 2 Фирма 2 3 Фирма 3

Таблица 2 Отношение "Поставщики"

Ограничение целостности этой базы данных

Пример 2

Pers_Id Pers_Name Dept_Id

1	Иванов	1
2	Петров	2
3	Сидоров	1
4	Пушников	2
5	Шарипов	1

Таблица 2 PERSON

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

С учетом этого ограничения можно заключить, что вставка нового сотрудника в таблицу не может быть выполнена одной операцией. При вставке нового сотрудника необходимо одновременно увеличить значение поля Dept_Kol: Шаг 1. Вставить сотрудника в таблицу PERSON: INSERT INTO PERSON (6, Муфтахов, 1) Шаг 2. Увеличить значение поля Dept_Kol: UPDATE DEPART SET Dept=Dept+1 WHERE Dept_Id=1

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

С чем же работала транзакция

Пример 2

Транзакция A Время Транзакция B Работа с "грязными" данными

---		Чтение
---		Запись
Чтение		---
Работа с прочитанными данными		---
---		Откат транзакции
Фиксация транзакции		---

С чем же работала транзакция A?

Результат. Транзакция A в своей работе использовала данные, которых нет в базе данных. Более того, транзакция A использовала данные, которых нет, и не было в базе данных! Действительно, после отката транзакции B, должна восстановиться ситуация, как если бы транзакция B вообще никогда не выполнялась. Таким образом, результаты работы транзакции A некорректны, т.к. она работала с данными, отсутствовавшими в базе данных.

Для того чтобы отразить факты

Пример 3

A (Преподаватель) B (Предмет) Q (Количество часов)

Пушников	Алгебра	40
Пушников	Базы данных	80
Цыганов	Геометрия	50
Шарипов	Алгебра	40
Шарипов	Геометрия	50

Таблица 3 Отношение "Читает лекции по-"

Для того чтобы отразить факты 4-6 (характеризующие посещение студентами лекций), введем отношение

на декартовом произведении

. Упорядоченная тройка

тогда и только тогда, когда студент

посещает лекции по предмету

у преподавателя

. Назовем это отношение "Посещать лекции". Его также представим в виде таблицы:

Имеется несколько парадоксальных следствий применения

Пример 3

NOT F T U

Таблица 3 Таблица истинности NOT

Имеется несколько парадоксальных следствий применения трехзначной логики.

Парадокс 1. Null-значение не равно самому себе. Действительно, выражение null = null дает значение не ИСТИНА, а НЕИЗВЕСТНО. Значит выражение

не обязательно ИСТИНА!

Парадокс 2. Неверно также, что null-значение не равно самому себе! Действительно, выражение null

null также принимает значение не ИСТИНА, а НЕИЗВЕСТНО! Значит также, что и выражение

тоже не обязательно ЛОЖЬ!

Парадокс 3.

не обязательно ИСТИНА. Значит, в трехзначной логике не работает принцип исключенного третьего (любое высказывание либо истинно, либо ложно).

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

Как видно из приведенного примера,

Пример 3

Табельный номер Фамилия Зарплата

1	Иванов	1000
2	Петров	2000
3	Сидоров	3000
2	Пушников	2500
4	Сидоров	3000

Таблица 3 Отношение A UNION B

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

не наследуются объединением этих отношений. Поэтому, в объединении отношений

атрибут "Табельный номер" может содержать дубликаты значений. Если бы это было не так, и ключи наследовались бы, то это противоречило бы понятию объединения как "объединение множеств". Конечно, объединение отношений

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

Если явно не указаны ключевые

Пример 3

PNUM DNUM VOLUME

3	1	1000
2	1	150
1	1	100
2	2	250
1	2	200
1	3	300

Замечание. Если явно не указаны ключевые слова ASC или DESC, то по умолчанию принимается упорядочение по возрастанию (ASC).

Отношение

Пример 3

Н_ПРО ПРОЕКТ

1	Космос
2	Климат

Таблица 3 Отношение ПРОЕКТЫ

Отношение ЗАДАНИЯ (Н_СОТР, Н_ПРО, Н_ЗАДАН):

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

{Н_СОТР, Н_ПРО}

Н_ЗАДАН

и только тогда, когда детерминанты

Пример 3

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

1	1	100
1	2	200
1	3	300
2	1	150
2	2	250
3	1	1000

Таблица 3 Отношение "Поставки-2"

Определение 1. Отношение

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

Замечание. Если отношение находится в НФБК, то оно автоматически находится и в 3НФ. Действительно, это сразу следует из определения 3НФ.

Отношение "Поставки" не находится в НФБК, т.к. имеются зависимости (PNUM

PNAME и PNAME

PNUM), детерминанты которых не являются потенциальными ключами.

Для того чтобы устранить зависимость от детерминантов, не являющихся потенциальными ключами, необходимо провести декомпозицию, вынося эти детерминанты и зависимые от них части в отдельное отношение. Отношения "Поставщики" и "Поставки-2", полученные в результате декомпозиции находятся в НФБК.

Замечание. Приведенная декомпозиция отношения "Поставки" на отношения "Поставщики" и "Поставки-2" не является единственно возможной. Альтернативной декомпозицией является декомпозиция на следующие отношения:

требующими ввода данных являются всего

Пример 3

Базовый ли атрибут

Наиме-нование атрибута	Описание атрибута	Формула для вычислимого атрибута
Name	Наименование товара	Да
N	Количество	Да
P1	Учетная цена товара	Да
S1	Учетная сумма на все количество		S1 = N*P1
PerSent	Процент наценки на единицу товара	Да
P2	Наценка на единицу товара		P2 = P1*PerSent/100
S2	Сумму наценки на все количество		S2 = N*P2
P3	Цену товара с учетом наценки		P3 = P1+P2
S3	Сумму на все количество с учетом наценки		S3 = N*P3
NDS	Процент НДС	Да
P4	Сумма НДС на единицу товара		P4 = P2*NDS/100
S4	Сумма НДС на все количество		S4 = N*P4
P5	Цена товара с НДС		P5 = P3+P4
S5	Сумма на все количество с НДС		S5 = N*P5

Таблица 3 Атрибуты товара

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

Решение 1. Пусть в отношении решено хранить только базовые атрибуты.

Достоинства решения: Структура отношения полностью неизбыточна. Не требуется дополнительного программного кода для поддержания целостности кортежа. Экономится дисковое пространство. Уменьшается трафик сети.

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

Решение 2. Предположим, что в отношении решено хранить все атрибуты, в том числе и вычислимые.

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

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

Как видим, оба решения имеют свои достоинства и недостатки. Важно то, что программный код, содержащий эти формулы, не исчезает ни в каком из этих решений (да и куда он денется, раз такова предметная область!). Только в одном случае код хранится в одном месте, а в другом может быть "размазан" по всему приложению.

На самом деле данный пример сильно упрощен, т.к. еще одной неприятной особенностью наших бухгалтерий является то, что все расчеты должны вестись с определенной точностью, а именно - до копеек. Возникает проблема округления, а это еще более усложняет формулы для расчетов цен. Простой пример - вычисление НДС содержит операцию деления, следовательно может приводить к бесконечным дробям типа 15,519999- Такую дробь необходимо округлить до 15.52. Если продается одна единица товара, то это не страшно, но если продается несколько единиц товара, то сумму НДС на все количество можно считать по разным формулам: S4 = N* ROUND(P2*NDS/100) - СНАЧАЛА округлить при вычислении НДС на единицу товара, а ПОТОМ умножить на все количество, или S4 = ROUND(N*P2*NDS/100) - СНАЧАЛА умножить на все количество, а ПОТОМ округлить до требуемого знака.

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

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

Проверка ограничения. К моменту проверки ограничения кортежа должны быть проверены ограничения целостности атрибутов, входящих в этот кортеж.

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

о существовании транзакции B, и,

Пример 3

Транзакция A Время Транзакция B Неповторяемое считывание

Чтение		---
---		Чтение
---		Запись
---		Фиксация транзакции
Повторное чтение		---
Фиксация транзакции		---

Транзакция A ничего не знает о существовании транзакции B, и, т.к. сама она не меняет значение в строке, то ожидает, что после повторного чтения значение будет тем же самым.

Результат. Транзакция A работает с данными, которые, с точки зрения транзакции A, самопроизвольно изменяются.

Оно задано на декартовом произведении

Пример 4

C (студент) B (предмет) A (Преподаватель)

Иванов	Алгебра	Шарипов
Иванов	Базы данных	Пушников
Петров	Алгебра	Пушников
Петров	Геометрия	Цыганов
Сидоров	Геометрия	Цыганов
Сидоров	Базы данных	Пушников

Таблица 4 Отношение "Посещать лекции"

Рассмотрим отношение

подробнее. Оно задано на декартовом произведении

. Это произведение, содержащее 3*3*3=27 кортежей, можно назвать "Студенты-Лекции-Преподаватели". Множество

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

показывает текущее состояние учебного процесса. Очевидно, что отношение

является изменяемым во времени отношением.

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

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

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

Замечание. В таблицу "Посещать лекции" нельзя добавить две одинаковые строки, т.к. таблица изображает отношение

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

Замечание. В таблицу "Посещать лекции" нельзя добавить кортеж (Иванов, Геометрия, Пушников). Действительно, из таблицы "Читает лекции по-", представляющей отношение

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

При первом взгляде на таблицу,

Пример 4

Табельный номер Фамилия Зарплата

1	Иванов	1000
2	Петров	2000
3	Сидоров	3000

Таблица 4 Отношение "Сотрудники"

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

Попробуем представить это отношение в другом виде, изменив наименования атрибутов:

в отличие от операции объединения,

Пример 4

Табельный номер Фамилия Зарплата

Иванов

1000

Таблица 4 Отношение A INTERSECT B

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

в разделе FROM оператора, условие

Пример 4

PNUM PNAME DNUM VOLUME

1	Иванов	1	100
1	Иванов	2	200
1	Иванов	3	300
2	Петров	1	150
2	Петров	2	250
3	Сидоров	1	1000

Замечание. Соединяемые таблицы перечислены в разделе FROM оператора, условие соединения приведено в разделе WHERE. Раздел WHERE, помимо условия соединения таблиц, может также содержать и условия отбора строк.

Пример 14. Естественное соединение таблиц (способ 2 - ключевые слова JOIN- USING-): SELECT P.PNUM, P.PNAME, PD.DNUM, PD.VOLUME FROM P JOIN PD USING PNUM;

Замечание. Ключевое слово USING позволяет явно указать, по каким из общих колонок таблиц будет производиться соединение.

Пример 15. Естественное соединение таблиц (способ 3 - ключевое слово NATURAL JOIN): SELECT P.PNUM, P.PNAME, PD.DNUM, PD.VOLUME FROM P NATURAL JOIN PD;

Замечание. В разделе FROM не указано, по каким полям производится соединение. NATURAL JOIN автоматически соединяет по всем одинаковым полям в таблицах.

Пример 16. Естественное соединение трех таблиц: SELECT P.PNAME, D.DNAME, PD.VOLUME FROM P NATURAL JOIN PD NATURAL JOIN D;

В результате получим следующую таблицу:

Отношения

Пример 4

Н_СОТР Н_ПРО Н_ЗАДАН

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

Таблица 4 Отношения ЗАДАНИЯ

Отношение

Пример 4

Номер поставщика
PNUM Наименование поставщика
PNAME 1 Фирма 1 2 Фирма 2 3 Фирма 3

Таблица 4 Отношение "Поставщики"

таблица

Пример 4

X Y

1	Aa
1	Bb
2	Cc
2	Dd
3	Ee
3	Ff

Таблица 4 таблица A (Родительская)

Вставка новой строки, удовлетворяющей условию

Пример 4

Транзакция A Время Транзакция B Появились строки, которых раньше не было

Выборка строк, удовлетворяющих условию . (Отобрано n строк)		---
---		Вставка новой строки, удовлетворяющей условию .
---		Фиксация транзакции
Выборка строк, удовлетворяющих условию . (Отобрано n+1 строк)		---
Фиксация транзакции		---

Транзакция A ничего не знает о существовании транзакции B, и, т.к. сама она не меняет ничего в базе данных, то ожидает, что после повторного отбора будут отобраны те же самые строки.

Результат. Транзакция A в двух одинаковых выборках строк получила разные результаты.

добавленные кортежи помечены серым

Пример 5

Конструкция

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

Таблица 5 Отношение R

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

состоит из кортежей ( добавленные кортежи помечены серым цветом):

и не сообщим смысл наименований

Пример 5

A B C

1	Иванов	1000
2	Петров	2000
3	Сидоров	3000

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

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

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

Отношение

Пример 5

Табельный номер Фамилия Зарплата

2	Петров	2000
3	Сидоров	3000

Таблица 5 Отношение A MINUS B

В результате получим следующую

Пример 5

PNAME DNAME VOLUME

Иванов	Болт	100
Иванов	Гайка	200
Иванов	Винт	300
Петров	Болт	150
Петров	Гайка	250
Сидоров	Болт	1000

Пример 17. Прямое произведение таблиц: SELECT P.PNUM, P.PNAME, D.DNUM, D.DNAME FROM P, D;

В результате получим следующую таблицу:

Зависимость номера телефона от номера

Пример 5

Н_СОТР ФАМ Н_ОТД

1	Иванов	1
2	Петров	1
3	Сидоров	2

Таблица 5 Отношение СОТРУДНИКИ

Отношение ОТДЕЛЫ (Н_ОТД, ТЕЛ):

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

Зависимость номера телефона от номера отдела:

Н_ОТД

ТЕЛ

На первый взгляд, такая декомпозиция

Пример 5

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

1	100
2	200
3	300
1	150
2	250
1	1000

Таблица 5 Отношение "Поставки-3"

На первый взгляд, такая декомпозиция хуже, чем первая. Действительно, наименования поставщиков по-прежнему повторяются, и при изменении наименования поставщика, это наименование придется менять одновременно в нескольких местах (тем более сразу в двух отношениях!). Кажется, что ситуация стала еще хуже, чем была до декомпозиции. Однако такое ощущение возникает от того, что мы интуитивно считаем, что наименования поставщиков могут меняться, а номера - нет. Если же предположить, что номера поставщиков тоже могут меняться (почему бы нет - директор приказал перенумеровать поставщиков!), то первая декомпозиция получается такой же "плохой" как и вторая - повторяющиеся номера придется менять одновременно в нескольких местах и также сразу в двух отношениях.

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

Замечание. Отношение "Поставки-2", полученное в результате декомпозиции имеет всего один потенциальный ключ. Поэтому, для анализа отношения "Поставки-2" не требуется привлекать определение НФБК, достаточно определения 3НФ. Хотя отношение "Поставщики" имеет два потенциальных ключа, но, т.к. других атрибутов в нем нет, оно уже так просто устроено, что упростить его дальше нельзя. Возникает вопрос, имеются ли нетривиальные примеры отношений в НФБК, не находящиеся в 3НФ и не такие простые, как отношение "Поставщики"?

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

B имеет первичный ключ Z,

Пример 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

Транзакция A Время Транзакция B Сумма $ 250 по всем счетам неправильная - должно быть $300

Чтение счета и суммирование.		---
---		Снятие денег со счета .
---		Помещение денег на счет .
---		Фиксация транзакции
Чтение счета и суммирование.		---
Чтение счета и суммирование.		---
Фиксация транзакции		---

Результат. Хотя транзакция B все сделала правильно - деньги переведены без потери, но в результате транзакция A подсчитала неверную общую сумму.

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

в описании включения деталей друг

Пример 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	Винт

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

Пример 18. Соединение таблиц по произвольному условию. Рассмотрим таблицы поставщиков и деталей, которыми присвоен некоторый статую (см. пример 8 из предыдущей главы):

Обратим внимание на то, что

Пример 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,

Зависимость атрибутов от второго ключа отношения:

PNUM,

DNUM,

VOLUME,

Зависимости, являющиеся следствием зависимостей от ключей отношения:

{PNUM, DNUM}

{VOLUME, NN},

{PNUM, DNUM},

{PNUM, VOLUME},

{DNUM, VOLUME},

{PNUM, DNUM, VOLUME}.

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

Предложение MATCH игнорируется, если все

Пример 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 (начально немедленно проверяемое).

B не может блокировать объект,

Пример 6

НЕТ
(Конфликт
R-W) НЕТ
(Конфликт
W-R) НЕТ
(Конфликт
W-W)

	Транзакция B пытается наложить блокировку:
Транзакция A наложила блокировку:	S-блокировку	X-блокировку
S-блокировку	Да
X-блокировку

Таблица 1 Матрица совместимости S- и X-блокировок

Три случая, когда транзакция B не может блокировать объект, соответствуют трем видам конфликтов между транзакциями.

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

Отношение

Пример 7

Номер поставщика Наименование поставщика

1	Иванов
2	Петров
3	Сидоров

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

Декартово произведение отношений

Пример 7

Номер детали Наименование детали

1	Болт
2	Гайка
3	Винт

Таблица 7 Отношение B (Детали)

Декартово произведение отношений

будет иметь вид:

Отношение

Пример 7

PNUM PNAME PSTATUS

1	Иванов	4
2	Петров	1
3	Сидоров	2

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

Как видно из таблицы, более

Пример 7

Критерий Отношения слабо нормализованы
(1НФ, 2НФ) Отношения сильно нормализованы
(3НФ)

Адекватность базы данных предметной области	ХУЖЕ (-)	ЛУЧШЕ (+)
Легкость разработки и сопровождения базы данных	СЛОЖНЕЕ (-)	ЛЕГЧЕ (+)
Скорость выполнения вставки, обновления, удаления	МЕДЛЕННЕЕ (-)	БЫСТРЕЕ (+)
Скорость выполнения выборки данных	БЫСТРЕЕ (+)	МЕДЛЕННЕЕ (-)

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

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

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

о том, что абитуриент Иванов

Пример 7

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

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

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

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

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

в состояние ожидания до тех

Пример 7

Транзакция A Время Транзакция B Ожидание- Ожидание-

S-блокировка - успешна		---
Чтение		---
---		S-блокировка - успешна
---		Чтение
X-блокировка - отвергается		---
Ожидание-		X-блокировка - отвергается
Ожидание-		Ожидание-

Обе транзакции успешно накладывают S-блокировки и читают объект

. Транзакция A пытается наложить X-блокирокировку для обновления объекта

. Блокировка отвергается, т.к. объект

уже S-заблокирован транзакцией B. Транзакция A переходит в состояние ожидания до тех пор, пока транзакция B не освободит объект. Транзакция B, в свою очередь, пытается наложить X-блокирокировку для обновления объекта

. Блокировка отвергается, т.к. объект

уже S-заблокирован транзакцией A. Транзакция B переходит в состояние ожидания до тех пор, пока транзакция A не освободит объект.

Результат. Обе транзакции ожидают друг друга и не могут продолжаться. Возникла ситуация тупика.

Отношение

Пример 8

Номер детали Наименование детали

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

DNUM DNAME DSTATUS

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 Модифицированное отношение "Абитуриенты-Факультеты-Предметы"

транзакции B. После этого транзакция

Пример 8

Транзакция A Время Транзакция B Все правильно

---		S-блокировка - успешна
---		Чтение
---		X-блокировка - успешна
---		Запись
S-блокировка - отвергается		---
Ожидание-		Откат транзакции (Блокировка снимается)
S-блокировка - успешна		---
Чтение		---
Работа с прочитанными данными		---
---		---
Фиксация транзакции		---

Результат. Транзакция A притормозилась до окончания (отката) транзакции B. После этого транзакция A продолжила работу в обычном режиме и работала с правильными данными. Конфликт разрешен за счет некоторого увеличения времени работы транзакции A (потрачено время на ожидание снятия блокировки транзакцией B).

Номер детали" являются ссылками на

Пример 9

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

1	1	100
1	2	200
1	3	300
2	1	150
2	2	250
3	3	1000

Таблица 8 Отношение "Поставки"

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

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

Определение 2. Пусть дано отношение

. Подмножество атрибутов

отношения

будем называть внешним ключом, если: Существует отношение

(

не обязательно различны) с потенциальным ключом

. Каждое значение

в отношении

всегда совпадает со значением

для некоторого кортежа из

, либо является null-значением.

Отношение

называется родительским отношением, отношение

называется дочерним отношением.

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

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

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

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

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

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

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

Отношение

Пример 9

Табельный номер Фамилия Зарплата

1	Иванов	1000
2	Петров	2000
3	Сидоров	3000

Таблица 9 Отношение A

Результат выборки

будет иметь вид:

Пример PNUM PNAME

Пример 9

PNUM PNAME PSTATUS DNUM DNAME DSTATUS

1	Иванов	4	1	Болт	3
1	Иванов	4	2	Гайка	2
1	Иванов	4	3	Винт	1
2	Петров	1	3	Винт	1
3	Сидоров	2	2	Гайка	2
3	Сидоров	2	3	Винт	1

Отношение

Пример 9

НОМЕР ЗАРПЛАТА

1	1000
2	1000

Таблица 8 Отношение

Отношение

Пример 9

Номер
Абитуриента Абитуриент

1	Иванов
2	Петров

Таблица 9 Отношение "Абитуриенты"

B притормозилась до окончания транзакции

Пример 9

Транзакция A Время Транзакция B Все правильно

S-блокировка - успешна		---
Чтение		---
---		X-блокировка - отвергается
---		Ожидание-
Повторное чтение		Ожидание-
Фиксация транзакции (Блокировка снимается)		Ожидание-
---		X-блокировка - успешна
---		Запись
---		Фиксация транзакции (Блокировка снимается)

Результат. Транзакция B притормозилась до окончания транзакции A. В результате транзакция A дважды читает одни и те же данные правильно. После окончания транзакции A, транзакция B продолжила работу в обычном режиме.

выбрать кортежи отношения, удовлетворяющие некоторому

Пример 10

Табельный номер Фамилия Зарплата

1	Иванов	1000
2	Петров	2000

Таблица 10 Отношение A WHERE Зарплата<3000

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

Рассмотрим ситуацию, когда некоторые поставщики

Пример 10

PNAME1 PSTATUS1 PNAME2 PSTATUS2

Иванов	4	Петров	1
Иванов	4	Сидоров	2
Сидоров	2	Петров	1

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

Естественное соединение этих проекций, имеющих

Пример 10

ФАМИЛИЯ ЗАРПЛАТА

Иванов	1000
Петров	1000

Таблица 9 Отношение

Естественное соединение этих проекций, имеющих общий атрибут "ЗАРПЛАТА", очевидно, будет следующим (каждая строка одной проекции соединится с каждой строкой другой проекции):

Таблица 10 Отношение

Пример 10

Номер
Факультета Факультет

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

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

Вставка новой строки, удовлетворяющей условию

Пример 10

Транзакция A Время Транзакция B Появились строки, которых раньше не было

S-блокировка строк, удовлетворяющих условию . (Заблокировано n строк)		---
Выборка строк, удовлетворяющих условию . (Отобрано n строк)		---
---		Вставка новой строки, удовлетворяющей условию .
---		Фиксация транзакции
S-блокировка строк, удовлетворяющих условию . (Заблокировано n+1 строка)		---
Выборка строк, удовлетворяющих условию . (Отобрано n+1 строк)		---
Фиксация транзакции		---

Результат. Блокировка на уровне строк не решила проблему появления фиктивных элементов.

Таблица 11 Отношение

Пример 11

Номер поставщика Наименование поставщика Город поставщика

1	Иванов	Уфа
2	Петров	Москва
3	Сидоров	Москва
4	Сидоров	Челябинск

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

Проекция

будет иметь вид:

Пример 12

Город поставщика

Уфа

Москва

Челябинск

Таблица 12 Отношение A[Город поставщика]

Отношение

Пример 11

Номер контрагента
NUM Наименование контрагента
NAME

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).

Аномалия удаления. При попытке удалить кортеж (Иванов, Математический, Математика), мы обязаны удалить также и кортеж (Иванов, Математический, Информатика) по той же самой причине.

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

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

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

Определение 2. Пусть

- отношение, и

- некоторые из его атрибутов (или непересекающиеся множества атрибутов).

Тогда атрибуты (множества атрибутов)

многозначно зависят от

(обозначается

), тогда и только тогда, когда из того, что в отношении

содержатся кортежи

следует, что в отношении

содержится также и кортеж к

Замечание. Меняя местами кортежи

в определении многозначной зависимости, получим, что в отношении

должен содержаться также и кортеж

. Таким образом, атрибуты

, многозначно зависящие от

, ведут себя "симметрично" по отношению к атрибуту

В отношении "Абитуриенты-Факультеты-Предметы" имеется многозначная зависимость Факультет

Абитуриент|Предмет.

Словами это можно выразить так - для каждого факультета (для каждого значения из

) каждый поступающий на него абитуриент (значение из

) сдает один и тот же список предметов (набор значений из

), и для каждого факультета (для каждого значения из

) каждый сдаваемый на факультете экзамен (значение из

) сдается одним и тем же списком абитуриентов (набор значений из

). Именно наличие этой зависимости не позволяет независимо вставлять и удалять кортежи. Кортежи обязаны вставляться и удаляться одновременно целыми наборами.

Замечание. Если в отношении

имеется не менее трех атрибутов

и есть функциональная зависимость

, то есть и многозначная зависимость

Действительно, действуя формально в соответствии с определением многозначной зависимости, предположим, что в отношении

содержатся кортежи

. В силу функциональной зависимости

отсюда следует, что

. Но тогда кортеж

в точности совпадает с кортежем

и, следовательно, содержится в отношении

. Таким образом, имеется многозначная зависимость

Таким образом, понятие многозначной зависимости является обобщением понятия функциональной зависимости.

Определение 3. Многозначная зависимость

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

В отношении "Абитуриенты-Факультеты-Предметы" имеется именно нетривиальная многозначная зависимость Факультет

Абитуриент|Предмет. В силу нетривиальности этой зависимости мы не можем воспользоваться теоремой Хеза для декомпозиции отношения. Однако Фейджином Р. [52] доказана следующая теорема:

Теорема (Фейджина). Пусть

- непересекающиеся множества атрибутов отношения

Декомпозиция отношения

на проекции

будет декомпозицией без потерь тогда и только тогда, когда имеется многозначная зависимость

Замечание. Если зависимость

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

или

, то получаем теорему Хеза.

Доказательство теоремы.

Необходимость. Пусть декомпозиция отношения

на проекции

является декомпозицией без потерь. Докажем что

Предположим, что отношение

содержит кортежи

. Необходимо доказать, что кортеж

также содержится в

. По определению проекций, кортеж

содержится в

, а кортеж

содержится в

. Тогда кортеж

содержится в естественном соединении

, а в силу того, что декомпозиция является декомпозицией без потерь, этот кортеж содержится и в

. Необходимость доказана.

Достаточность. Пусть имеется многозначная зависимость

. Докажем, что декомпозиция отношения

на проекции

является декомпозицией без потерь.

Как и в доказательстве теоремы Хеза, нужно доказать, что

для любого состояния отношения

Включение

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

Докажем включение

. Пусть кортеж

. Это означает, что в проекции

содержится кортеж

, а в проекции

содержится кортеж

. По определению проекции, найдется такое значение

атрибута

, что отношение

содержит кортеж

. Аналогично, найдется такое значение

атрибута

, что отношение

содержит кортеж

. Тогда по определению многозначной зависимости кортеж

. Включение доказано. Достаточность доказана. Теорема доказана.

Определение 4. Отношение

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

Отношение "Абитуриенты-Факультеты-Предметы" находится в НФБК, но не в 4НФ. Согласно теореме Фейджина, это отношение можно без потерь декомпозировать на отношения:

Обе транзакции ожидают друг друга

Пример 11

Транзакция A Время Транзакция B Ожидание- Ожидание-

S-блокировка счета - успешна		---
Чтение счета и суммирование.		---
---		X-блокировка счета - успешна
---		Снятие денег со счета .
---		X-блокировка счета - отвергается
---		Ожидание-
S-блокировка счета - успешна		Ожидание-
Чтение счета и суммирование.		Ожидание-
S-блокировка счета - отвергается		Ожидание-
Ожидание-		Ожидание-

Результат. Обе транзакции ожидают друг друга и не могут продолжаться. Возникла ситуация тупика.

Таблица 12 Отношение

Пример 12

Город поставщика

Уфа

Москва

Челябинск

Таблица 12 Отношение A[Город поставщика]

Отношение DETAILS

Пример 12

Номер детали
DNUM Наименование детали
DNAME

1	Болт
2	Гайка
3	Винт

Таблица 4 Отношение DETAILS (Детали)

Таблица 11 Отношение

Пример 12

НОМЕР ФАМИЛИЯ

1	Иванов
2	Петров

Таблица 11 Отношение

Таблица 12 Отношение

Пример 12

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

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

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

Как видно, ситуация тупика может

Пример 12

Транзакция A Время Транзакция B Ожидание- Ожидание-

Блокировка объекта - успешна		---
---		Блокировка объекта -успешна
Блокировка объекта - конфликтует с блокировкой, наложенной транзакцией B		---
Ожидание-		Блокировка объекта - конфликтует с блокировкой, наложенной транзакцией A
Ожидание-		Ожидание-

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

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

Можно представить два принципиальных подхода к обнаружению тупиковой ситуации и выбору транзакции-жертвы: СУБД не следит за возникновением тупиков. Транзакции сами принимают решение, быть ли им жертвой. За возникновением тупиковой ситуации следит сама СУБД, она же принимает решение, какой транзакцией пожертвовать.

Первый подход характерен для так называемых настольных СУБД (FoxPro и т.п.). Этот метод является более простым и не требует дополнительных ресурсов системы. Для транзакций задается время ожидания (или число попыток), в течение которого транзакция пытается установить нужную блокировку. Если за указанное время (или после указанного числа попыток) блокировка не завершается успешно, то транзакция откатывается (или генерируется ошибочная ситуация). За простоту этого метода приходится платить тем, что транзакции-жертвы выбираются, вообще говоря, случайным образом. В результате из-за одной простой транзакции может откатиться очень дорогая транзакция, на выполнение которой уже потрачено много времени и ресурсов системы.

Второй способ характерен для промышленных СУБД (ORACLE, MS SQL Server и т.п.). В этом случае система сама следит за возникновением ситуации тупика, путем построения (или постоянного поддержания) графа ожидания транзакций. Граф ожидания транзакций - это ориентированный двудольный граф, в котором существует два типа вершин - вершины, соответствующие транзакциям, и вершины, соответствующие объектам захвата. Ситуация тупика возникает, если в графе ожидания транзакций имеется хотя бы один цикл. Одну из транзакций, попавших в цикл, необходимо откатить, причем, система сама может выбрать эту транзакцию в соответствии с некоторыми стоимостными соображениями (например, самую короткую, или с минимальным приоритетом и т.п.).

Таблица 13 Отношение

Пример 13

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

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

Пример 14

Номер детали Наименование детали Y

(Статус детали)

1	Болт	3
2	Гайка	2
3	Винт	1

Таблица 14 Отношение B (Детали)

Ответ на вопрос " какие поставщики имеют право поставлять какие детали?" дает

-соединение

и CNUM являются внешними ключами,

Пример 13

Номер поставщика
PNUM Номер получателя
CNUM Номер детали
DNUM Поставляемое количество
VOLUME

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 Отношение "Факультеты-Предметы"

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

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

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

Работа|Дети.

B пытается наложить на таблицу

Пример 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-блокировку для последующей вставки строк).

какие поставщики имеют право поставлять

Пример 14

Номер детали Наименование детали Y

(Статус детали)

1	Болт	3
2	Гайка	2
3	Винт	1

Таблица 14 Отношение B (Детали)

Ответ на вопрос " какие поставщики имеют право поставлять какие детали?" дает

-соединение