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

CHECK (DEPT_EMP_NO = (SELECT COUNT(*) FROM EMP WHERE DEPT_NO = EMP.DEPT_NO))

из определения таблицы DEPT. Предположим, например, что в отдел зачисляется новый служащий. Тогда нужно выполнить две операции: (a) вставить новую строку в таблицу EMP и (b) изменить соответствующую строку таблицы DEPT (прибавить единицу к значению столбца DEPT_EMP_NO). Очевидно, что в каком бы порядке ни выполнялись эти операции, сразу после выполнения первой из них ограничение целостности будет нарушено, соответствующее действие будет отвергнуто, и мы никогда не сможем принять на работу нового служащего.

Поскольку ограничения целостности, немедленная проверка которых бессмысленна, являются нужными и полезными, в язык SQL включены средства, позволяющие регулировать время проверки ограничений. Если говорить более точно, в контексте каждой выполняемой транзакции каждое ограничение целостности должно находиться в одном из двух режимов: режиме немедленной проверки (immediate) или режиме отложенной проверки (deferred). Все ограничения целостности, находящиеся в режиме немедленной проверки, проверяются при выполнении в транзакции любой операции, изменяющей состояние базы данных. Если действие операции нарушает какое-либо немедленно проверяемое ограничение целостности, то это действие отвергается. Ограничения целостности, находящиеся в режиме отложенной проверки, проверяются при завершении транзакции (выполнении операции COMMIT). Если действия этой транзакции нарушают какое-либо отложенно проверяемое ограничение целостности, то транзакция откатывается (операция COMMIT трактуется как операция ROLLBACK).

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

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

Независимые проекции отношений. Теорема Риссанена

Обратите внимание, что для переменной отношения СЛУЖ {СЛУ_НОМ, СЛУ_УРОВ, СЛУ_ЗАРП}, кроме декомпозиции на отношения СЛУЖ1 {СЛУ_НОМ, СЛУ_УРОВ} и УРОВ {СЛУ_УРОВ, СЛУ_ЗАРП}, возможна и декомпозиция на отношения СЛУЖ1 {СЛУ_НОМ, СЛУ_УРОВ} и СЛУЖ_ЗАРП {СЛУ_НОМ, СЛУ_ЗАРП}. Оба отношения, полученные путем второй декомпозиции, находятся в 3NF, и эта декомпозиция также является декомпозицией без потерь. Тем не менее вторая декомпозиция, в отличие от первой, не устраняет проблемы, связанные с обновлением отношения СЛУЖ. Например, по-прежнему невозможно сохранить данные о разряде, которым не обладает ни один служащий. Посмотрим, с чем это связано.

Отношения СЛУЖ1 и УРОВ могут обновляться независимо (являются независимыми проекциями), и при этом результат их естественного соединения всегда будет таким, как если бы обновлялось исходное отношение СЛУЖ. Это происходит потому, что FD отношения СЛУЖ трансформировались в индивидуальные ограничения первичного ключа отношений СЛУЖ1 и УРОВ. При второй декомпозиции FD СЛУ_УРОВ

Теорема Риссанена

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

Мы не будем приводить доказательство этой теоремы, но продемонстрируем ее верность на примере двух показанных выше декомпозиций отношения СЛУЖ. В первой декомпозиции (на проекции СЛУЖ1 и УРОВ) общий атрибут СЛУ_УРОВ является возможным (и первичным) ключом отношения УРОВ, а единственная дополнительная FD отношения СЛУЖ (СЛУ_НОМ

Нормальная форма Бойса-Кодда

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

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

Переменная отношения СЛУЖ_ПРО_ЗАДАН1 может быть приведена к BCNF путем одной из двух декомпозиций: СЛУЖ_НОМ_ИМЯ {СЛУ_НОМ, СЛУ_ИМЯ} и СЛУЖ_НОМ_ПРО_ЗАДАН {СЛУ_НОМ, ПРО_НОМ, СЛУ_ЗАДАН} с множеством FD и значениями, показанными на , и СЛУЖ_НОМ_ИМЯ {СЛУ_НОМ, СЛУ_ИМЯ} и СЛУЖ_ИМЯ_ПРО_ЗАДАН {СЛУ_ИМЯ, ПРО_НОМ, СЛУ_ЗАДАН} (FD и значения результирующих переменных отношений выглядят аналогично).

Очевидно, что каждая из декомпозиций устраняет трудности, связанные с обновлением отношения СЛУЖ_ПРО_ЗАДАН1.

Нормальные формы ER-диаграмм

Как и в случае схем реляционных баз данных, для ER-диаграмм вводится понятие нормальных форм, причем их смысл очень близко соответствует смыслу нормальных форм отношений. Заметим, что определения нормальных форм ER-диаграмм делают более понятным смысл нормализации схем отношений. Мы приведем только очень краткие и неформальные определения трех первых нормальных форм. Конечно, можно было бы ввести дальнейшие нормальные формы ER-диаграмм, аналогичные нормальной форме Бойса-Кодда, 4NF и 5NF, но на практике к такой нормализации обычно не прибегают, а общие идеи после ознакомления с лекцией 9 должны быть понятны и так.

Объектная модель SQL

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

Объектная модель SQL:1999 включает два основных отличительных компонента – структурные, определяемые пользователями типы данных (User Defined Type – UDT) и типизированные таблицы (Typed Table). Первый компонент позволяет определять новые типы данных, которые могут быть гораздо более сложными, чем встроенные типы данных языка SQL. При определении структурного UDT требуется специфицировать не только содержащиеся в нем элементы данных, но и семантику типа данных, т. е. его поведение на основе интерфейса вызовов методов. Второй компонент – типизированные таблицы – позволяет определять таблицы, строки которых являются экземплярами (или значениями) UDT, с которым явно ассоциируется таблица. Во многих отношениях строка типизированной таблицы похожа на объект класса в объектно-ориентированной системе.

В стандарте SQL:1999 определены два пакета объектных свойств – минимальный (PKG006) и полный (PKG007), которым должны удовлетворять SQL-ориентированные ОРСУБД, претендующие на соответствие стандарту. Ниже будут перечислены свойства, включенные в каждый из пакетов, но смысл этих свойств будет понятен только после прочтения остальных разделов.

Пакет PKG006 включает всего пять свойств: свойство S023 («Basic structured types») – возможность определять UDT и их методы с ограниченными возможностями;свойство S041 («Basic reference types») – возможность определять и использовать ссылки на экземпляры UDT, входящие в типизированные таблицы;свойство S051 («Create table of type») – возможность создания типизированных таблиц;свойство S151 («Type predicate») – возможность определения точного типа (в иерархии типов) экземпляра UDT;свойство Т041 («Basic LOB data type support») – возможность определения LOB-типов в смысле SQL (с необязательной поддержкой операций, кроме операций сохранения и полной выборки).

Объектно-ориентированная модель данных

Если не обращать внимания на особенности объектно-ориентированной терминологии (предполагается, что читатели в общих чертах знакомы с ней), то объектно-ориентированная модель данных ODMG, специфицированная в , отличается от других двух моделей, описываемых в этом разделе, прежде всего, в одном принципиальном аспекте. В модели данных SQL и истинной реляционной модели данных база данных представляет собой набор именованных контейнеров данных одного родового типа: таблиц или отношений соответственно. В объектно-ориентированной модели данных база данных – это набор объектов (контейнеров данных) произвольного типа.

Области разумного применения файлов

После краткого экскурса в историю и современное состояние файловых систем обсудим возможные области их применения. Прежде всего, конечно, файлы используются для хранения текстовых данных: документов, текстов программ и т. д. Такие файлы обычно создаются и модифицируются с помощью различных текстовых редакторов. Эти редакторы могут быть очень простыми, такими, как ed в мире UNIX или утилиты редактирования Norton Commander, FAR Manager и других интерактивных сред Windows. Они могут быть сложными и многофункциональными, синтаксически ориентированными, как, например, GNU Emacs. Но обычно структура текстовых файлов очень проста (c точки зрения файловой системы): это либо последовательность записей, содержащих строки текста, либо последовательность байтов, среди которых встречаются специальные символы (например, символы конца строки). Конечно же, сложность логической структуры текстового файла определяется текстовым редактором, но в любом случае файловой системе она не видна.

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

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

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

Рис. 1.3.  Связи между программными компонентами по пониманию логической структуры файлов

Обнаружение тупиковых ситуаций

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

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

Пример применения алгоритма редукции к графу ожидания транзакций показан на рис. 13.7 (в целях упрощения примера предполагается, что все блокировки являются монопольными, т.е. для каждой вершины-объекта имеется не более одной входящей дуги). В этом случае редукция состоит в том, что, прежде всего, из графа ожидания (начальное состояние которого показано на рис. 13.7 (a)) удаляются все дуги, исходящие из вершин-транзакций, в которые не входят дуги из вершин-объектов. (Это основывается на том разумном предположении, что транзакции, не ожидающие удовлетворения запроса блокировок, могут успешно завершиться и освободить блокировки). Кроме того, удаляются дуги, входящие в вершины-транзакции, из которых не исходят, ведущие к вершинам-объектам (транзакции, ожидающие удовлетворения блокировок, но не удерживающие заблокированные объекты, не могут быть причиной тупика). Для тех вершин-объектов, для которых не осталось входящих дуг, но существуют исходящие, ориентация одной из исходящих дуг (выбираемой произвольным образом) изменяется на противоположную (это моделирует удовлетворение запроса блокировки). Состояние графа после выполнения первого шага редукции показано на рис. 13.7 (b). После этого снова повторяются описанные действия (cостояние графа после выполнения второго шага редукции показано на рис. 13.7 (c)), и так до тех пор, пока не прекратится удаление дуг. Если в графе остались дуги, то они обязательно образуют цикл (см. рис. 13.7 (c)).

Рис. 13.7. Применение алгоритма редукции к графу ожидания транзакций

Предположим теперь, что нам удалось найти цикл в графе ожидания транзакций. Что делать теперь?

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

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

Решение, принятое в SQL, является предельно простым, хотя и несколько странным. При определении каждого триггера фиксируется временная метка выполнения оператора CREATE TRIGGER, и все триггеры, ассоциированные с одной предметной таблицей, относящиеся к одной и той же категории (BEFORE или AFTER) и срабатывающие по одному и тому же событию, упорядочиваются в соответствии со своими временными метками. Тогда при возникновении условия срабатывания всех триггеров одной группы сначала выполняется первый триггер, затем второй и т.д. В стандарте не специфицируется точность временной метки, связываемой с триггером, и если в одной группе обнаруживаются два или более триггеров с неразличимыми временными метками, то порядок их выполнения должен определяться в реализации.

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

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

Общая характеристика

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

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

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

Общая характеристика языка OCL

Более точный и лаконичный способ формулировки ограничений обеспечивает язык OCL (Object Constraints Language). Вот общая характеристика этого языка.

Из языка UML в OCL заимствованы, в первую очередь, следующие концепции: класс, атрибут, операция;объект (экземпляр класса);ассоциация; тип данных (включая набор предопределенных типов Boolean, Integer, Real и String);значение (экземпляр типа данных).

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

В дополнение к скалярным типам данных, заимствованным из UML, в OCL предопределены структурные типы, которые являются разновидностями типов коллекций (collection): математическое множество (set), неупорядоченная коллекция, не содержащая одинаковых элементов; мультимножество (bag), неупорядоченная коллекция, которая может содержать повторяющиеся элементы-дубликаты;последовательность (sequence), упорядоченная коллекция, которая может содержать элементы-дубликаты.

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

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

Общая интерпретация реляционных операций

Если не вдаваться в некоторые тонкости, которые мы рассмотрим в следующих разделах, то почти для всех операций предложенного выше набора имеется очевидная и простая интерпретация. При выполнении операции объединения (UNION) двух отношений с одинаковыми заголовками производится отношение, включающее все кортежи, которые входят хотя бы в одно из отношений-операндов.Операция пересечения (INTERSECT) двух отношений с одинаковыми заголовками производит отношение, включающее все кортежи, которые входят в оба отношения-операнда.Отношение, являющееся разностью (MINUS) двух отношений с одинаковыми заголовками, включает все кортежи, входящие в отношение-первый операнд, такие, что ни один из них не входит в отношение, которое является вторым операндом.При выполнении декартова произведения (TIMES) двух отношений, пересечение заголовков которых пусто, производится отношение, кортежи которого производятся путем объединения кортежей первого и второго операндов.Результатом ограничения (WHERE) отношения по некоторому условию является отношение, включающее кортежи отношения-операнда, удовлетворяющее этому условию.При выполнении проекции (PROJECT) отношения на заданное подмножество множества его атрибутов производится отношение, кортежи которого являются соответствующими подмножествами кортежей отношения-операнда.При соединении (JOIN) двух отношений по некоторому условию образуется результирующее отношение, кортежи которого производятся путем объединения кортежей первого и второго отношений и удовлетворяют этому условию.У операции реляционного деления (DIVIDE BY) два операнда – бинарное и унарное отношения. Результирующее отношение состоит из унарных кортежей, включающих значения первого атрибута кортежей первого операнда таких, что множество значений второго атрибута (при фиксированном значении первого атрибута) включает множество значений второго операнда.Операция переименования (RENAME) производит отношение, тело которого совпадает с телом операнда, но имена атрибутов изменены.Операция присваивания (:=) позволяет сохранить результат вычисления реляционного выражения в существующем отношении БД.

Общая структура оператора выборки в языке SQL

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

SELECT [ ALL | DISTINCT ] select_item_commalist FROM table_reference_commalist [ WHERE conditional_expression ] [ GROUP BY column_name_commalist ] [ HAVING conditional_expression ] [ ORDER BY order_item_commalist ]

Общее понятие транзакции и основные характеристики транзакций

Более точно, в современных СУБД поддерживается понятие транзакции, характеризуемое аббревиатурой ACID (Atomicy, Consistency, Isolation и Durability). В соответствии с этим понятием под транзакцией разумеется последовательность операций над базой данных, обладающая следующими свойствами.

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

Согласованность (Consistency).

В классическом смысле это свойство означает, что транзакция может быть успешно завершена с фиксацией

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

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

и целостность

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

Изоляция (Isolation).

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

не должны быть видны никакой другой транзакции T2

до тех пор, пока транзакция T1

не завершится успешным образом.

Долговечность (Durability).

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

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

Общие определения

Пусть задана переменная отношения R, и X и Y являются произвольными подмножествами заголовка R («составными» атрибутами).

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

Для примера будем использовать отношение СЛУЖАЩИЕ_ПРОЕКТЫ {СЛУ_НОМ, СЛУ_ИМЯ, СЛУ_ЗАРП, ПРО_НОМ, ПРОЕКТ_РУК} (). Очевидно, что если СЛУ_НОМ является первичным ключом отношения СЛУЖАЩИЕ, то для этого отношения справедлива функциональная зависимость (Functional Dependency – FD) СЛУ_НОМ

На самом деле, для тела отношения СЛУЖАЩИЕ_ПРОЕКТЫ в том виде, в котором оно показано на , выполняются еще и следующие FD (1):

Рис. 7.1.  Пример возможного тела отношения СЛУЖАЩИЕ_ПРОЕКТЫ

СЛУ_НОМ

Поскольку имена всех служащих различны, то выполняются и такие FD (2):

СЛУ_ИМЯ

Более того, для примера на выполняется и FD (3):

СЛУ_ЗАРП

Однако заметим, что природа FD группы (1) отличается от природы FD групп (2) и (3). Логично предположить, что идентификационные номера служащих должны быть всегда различны, а у каждого проекта имеется только один руководитель. Поэтому FD группы (1) должны быть верны для любого допустимого значения переменной отношения СЛУЖАЩИЕ_ПРОЕКТЫ и могут рассматриваться как инварианты, или ограничения целостности этой переменной отношения.

FD группы (2) базируются на менее естественном предположении о том, что имена всех служащих различны. Это соответствует действительности для примера из , но возможно, что с течением времени FD группы (2) не будут выполняться для какого-либо значения переменной отношения СЛУЖАЩИЕ_ПРОЕКТЫ.

Общие принципы организации данных во внешней памяти в SQL-ориентированных СУБД

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

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

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

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

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

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

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

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

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

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

журнальная информация, поддерживаемая для удовлетворения потребности в надежном хранении данных;

служебная информация, поддерживаемая для удовлетворения внутренних потребностей нижнего уровня системы (например, информация о свободной памяти).

Общие синтаксические правила построения скалярных выражений

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

value_expression ::= numeric_value_expression | string_value_expression | datetime_value_expression | interval_value_expression | boolean_value_expression | array_value_expression | multiset_value_expression | row_value_expression | user_defined_value_expression | reference_value_expression

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

value_expression_primary ::= unsigned_value_specification | column_reference | set_function_specification | scalar_subquery | case_expression | (value_expression) | cast_specification

В пределах этого курса можно считать, что спецификация беззнакового значения (unsigned_value_specification) – это всегда литерал соответствующего типа или вызов ниладической функции (например, CURRENT_USER). При вычислении выражения V для строки таблицы каждая ссылка на столбец (column_reference) этой таблицы, непосредственно содержащаяся в V, рассматривается как ссылка на значение данного столбца в данной строке. Агрегатные функции (функции над множествами – set_function_specification) обсуждаются в лекции 19. Если первичное выражение является скалярным подзапросом (scalar_subquery, или подзапросом, результатом которого является таблица, состоящая из одной строки и одного столбца) и результат подзапроса пуст, то результат первичного выражения – неопределенное значение. (Подзапросы обсуждаются в следующей лекции, выражения с переключателем (case_expression) рассматриваются ниже в этом разделе.)

Обзор реляционной алгебры Кодда

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

Существует много подходов к определению реляционной алгебры, которые различаются наборами операций и способами их интерпретации, но, в принципе, являются более или менее равносильными. В данном разделе мы опишем немного расширенный начальный вариант алгебры, который был предложен Коддом (будем называть ее «алгеброй Кодда»). В этом варианте набор основных алгебраических операций состоит из восьми операций, которые делятся на два класса – теоретико-множественные операции и специальные реляционные операции. В состав теоретико-множественных операций входят операции: объединения отношений;пересечения отношений;взятия разности отношений;взятия декартова произведения отношений.

Специальные реляционные операции включают: ограничение отношения;проекцию отношения;соединение отношений;деление отношений.

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

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

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

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

Заметим, что аналогичная поддержка целостности по ссылкам между записями без связи «предок-потомок», не обеспечивается. Примером такой «внешней» ссылки является содержимое поля Рук_Отдел

в экземпляре типа записи Руководитель.

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

Заметим, что перечисляемые ниже характеристики в полной мере относятся и к другим не реляционным подходам к организации баз данных, которые возникли до появления реляционного подхода или почти одновременно с ним. В частности, подобными свойствами обладают системы, основанные на подходах MUMPS (наиболее известной в России является реализация этого подхода в СУБД Cache компании Intersystems) и Pick (этот подход реализован во многих СУБД, в частности, в СУБД UniVerse и UniData семейства U2 компании IBM).

Ограничения целостности и язык OCL

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

Рис. 11.13.  Ограничение, выраженное на естественном языке

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

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

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

column_constraint_definition ::= [ CONSTRAINT constraint_name ] NOT NULL | { PRIMARY KEY | UNIQUE } | references_definition | CHECK ( conditional_expression )

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

Ограничение NOT NULL означает, что в определяемом столбце никогда не должны содержаться неопределенные значения. Если определяемый столбец имеет имя C, то это ограничение эквивалентно следующему табличному ограничению: CHECK (C IS NOT NULL).

В определение столбца может входить одно из ограничений уникальности: ограничение первичного ключа (PRIMARY KEY) или ограничение возможного ключа (UNIQUE). Включение в определение столбца любого из этих ограничений означает требование уникальности значений определяемого столбца (т. е. во все время существования определяемой таблицы во всех ее строках значения данного столбца должны быть различны). Ограничение PRIMARY KEY, в дополнение к этому, влечет за собой ограничение NOT NULL для определяемого столбца. Эти ограничения столбца эквивалентны следующим табличным ограничениям: PRIMARY KEY (C) и UNIQUE (С).

Ограничение references_definition означает объявление определяемого столбца внешним ключом таблицы и обладает следующим синтаксисом:

references_definition ::= REFERENCES base_table_name [ (column_commalist) ] [ MATCH { SIMPLE | FULL | PARTIAL } ] [ ON DELETE referential_action ] [ ON UPDATE referential_action ]

На самом деле, данная синтаксическая конструкция работает и в случае определения внешнего ключа на уровне таблицы (в одном из определений табличных ограничений целостности).
Поэтому мы отложим обсуждение до рассмотрения этого общего случая. Пока отметим только, что при использовании конструкции на уровне определения столбца  column_commalist может содержать имя только одного столбца (потому что внешний ключ состоит из одного определяемого столбца). Ограничение эквивалентно следующему табличному ограничению: FOREIGN KEY (C) references_definition.

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

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

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

  В этом случае SQL опирается на семантику неопределенных значений, отличную от используемой в большинстве других случаев. Считается, что (NULL = NULL) = true и что (a = NULL) = (NULL = a) = false для любого значения a, отличного от NULL.

Ограничения целостности в истинной реляционной модели

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

Средства поддержки декларативной ссылочной целостности фигурируют только в разделе рекомендуемых возможностей: «В D

[конкретную реализацию истинной реляционной модели] следует включить некоторую декларативную сокращенную форму для выражения ссылочных ограничений (называемых также ограничениями внешнего ключа)».

Ограничения целостности в модели SQL

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

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

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

Ограничения целостности в объектной модели

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

Что же касается ссылочной целостности, то она поддерживается, если между двумя атомарными объектными типами определяется связь вида «один-ко-многим». В этом случае объекты на стороне связи «один» рассматриваются как предки, а объекты на стороне связи «многие» – как потомки, и ООСУБД обязана следить за тем, чтобы не образовывались потомки без предков.

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

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

Операции exists, forAll, size

В OCL определены три одноименных операции exists над множеством, мультимножеством и последовательностью, дополнительным параметром которых является логическое выражение. В результате каждой из этих операций выдается true в том и только в том случае, когда хотя бы для одного элемента входной коллекции значением логического выражения является true. В противном случае результатом операции является false. Операции forAll отличаются от операций exists тем, что в результате каждой из них выдается true в том и только в том случае, когда для всех элементов входной коллекции результатом вычисления логического выражения является true. В противном случае результатом операции будет false. Операция size применяется к коллекции и выдает число содержащихся в ней элементов.

Операции модификации таблиц и списков

Группа операций модификации таблиц и списков включает операции вставки кортежа в таблицу или список (INSERT), удаления кортежа из таблицы (DELETE) и обновления кортежа в таблице (UPDATE).

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

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

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

Операции над множествами, мультимножествами и последовательностями

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

<коллекция>

Операции над объектами

В OCL определены три операции над объектами: получение значения атрибута; переход по соединению, вызов операции класса (последняя операция для целей проектирования реляционных БД несущественна).

Для записи этих трех операций используется «точечная нотация». Например, результатом выражения вида

<объект>.<имя атрибута>

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

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

<объект>.<имя роли, противоположенной по отношению к объекту>

Операции над значениями предопределенных типов данных

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

Операции объединения, пересечения, взятия разности. Совместимость по объединению

Начнем с операции объединения отношений (все, что будет сказано по поводу объединения, верно и для операций пересечения и взятия разности отношений). Смысл операции объединения в реляционной алгебре в целом остается теоретико-множественным. Еще раз напомним (см. ), что в теории множеств: результатом объединения двух множеств A{a} и B{b} является такое множество C{c}, что для каждого с либо существует такой элемент a, принадлежащий множеству A, что c=a, либо существует такой элемент b, принадлежащий множеству B, что c=b;пересечением множеств A и B является такое множество C{c}, что для любого c существуют такие элементы a, принадлежащий множеству A, и b, принадлежащий множеству B, что c=a=b;разностью множеств A и B является такое множество C{c}, что для любого c существует такой элемент a, принадлежащий множеству A, что c=a, и не существует такой элемент b, принадлежащий B, что c=b.

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

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

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

Для иллюстрации операций объединения, пересечения и взятия разности предположим, что в базе данных имеются два отношения СЛУЖАЩИЕ_В_ПРОЕКТЕ_1 и СЛУЖАЩИЕ_В_ПРОЕКТЕ_2 с одинаковыми схемами {СЛУ_НОМЕР, СЛУ_ИМЯ, СЛУ_ЗАРП, СЛУ_ОТД_НОМЕР} (имена доменов опущены по причине очевидности). Каждое из отношений содержит данные о служащих, участвующих в соответствующем проекте. На показано примерное наполнение каждого из двух отношений (некоторые служащие участвуют в обоих проектах).

Операции обновления баз данных и механизм триггеров

Термин триггер в контексте реляционных баз данных был введен в обиход участниками проекта System R (лекции 12, 15). В терминологии этого проекта триггером называлась хранимая в базе данных процедура, автоматически вызываемая СУБД при возникновении соответствующих условий.При определении триггера указывались два условия его применимости – общее условие (имя отношения и тип операции манипулирования данными) и конкретное условие (логическое выражение, построенное по правилам, близким к правилам ограничений целостности), а также действие, которое должно быть выполнено над БД при наличии условий применимости.

Конечно, термин триггер в данном контексте является жаргонным. Но, с другой стороны, он достаточно точно соответствует ситуации: для применения процедуры должны быть произведены «возбуждающие» ее действия. Как отмечалось в лекции 15, после завершения проекта System R на протяжении более десяти лет триггеры не поддерживались ни в одной коммерческой SQL-ориентированной СУБД. Но затем практически во всех ведущих СУБД механизм триггеров в том или ином виде был реализован.

В стандарте же языка SQL спецификации триггеров отсутствовали до принятия стандарта SQL:1999. По словам главного редактора стандартов SQL/92 и SQL:1999 Джима Мелтона, эта спецификация была уже полностью готова к моменту принятия SQL/92 и не вошла в текст стандарта только по причине ограниченности его объема. Однако, как мне кажется, этому препятствовали и расхождения в подходах, существовавшие между основными компаниями-производителями СУБД.

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

Операции сканирования таблиц и списков

Операции группы сканирования позволяют последовательно, в порядке, определяемом типом сканирования, прочитать кортежи таблицы или списка, удовлетворяющие требуемым условиям. Группа включает операции OPEN, NEXT

и CLOSE, означающие, соответственно, начало сканирования, требование чтения следующего кортежа, удовлетворяющего условиям, и конец сканирования.

Для таблицы возможны два режима сканирования: прямое сканирование и сканирование через индекс. При прямом сканировании единственным параметром операции OPEN

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

При начале сканирования таблицы через индекс в число параметров операции OPEN

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

Операции создания и уничтожения постоянных и временных объектов базы данных

Группа операций создания и уничтожения постоянных и временных объектов базы данных включает операции создания таблиц (CREATE TABLE), списков (CREATE LIST), индексов (CREATE IMAGE) и уничтожения любого из подобных объектов (DROP TABLE, DROP LIST и DROP IMAGE). Входным параметром операций создания таблиц и списков является спецификатор структуры объекта, т.е. число полей объекта и спецификаторы их типов. Кроме того, при спецификации полей таблицы указывается разрешение или запрещение наличия неопределенных значений полей в кортежах этой таблицы или списка. Неопределенные значения кодируются специальным образом. Любая операция сравнения константы данного типа с неопределенным значением по определению вырабатывает значение false, кроме операции сравнения на совпадение со специальной литеральной константой NULL.

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

при открытии сканирования объекта).

Входными параметрами операции CREATE IMAGE

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

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

Операции DROP TABLE, DROP LIST

и DROP IMAGE

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

Следует отметить, что массовые операции над постоянными объектами (CREATE IMAGE и DROP TABLE) требуют дополнительных накладных расходов в связи с необходимостью обеспечения возможности откатов транзакции, для чего требуется выполнение массовых обратных действий. Особенно сильно это затрагивает операцию уничтожения непустых таблиц, поскольку требует журнализации всех кортежей, содержащихся в них к моменту уничтожения. Поэтому, хотя уничтожение непустых таблиц и не запрещено, нужно иметь в виду, что это очень дорогостоящая операция.

Операции union, intersect, symmetricDifference

Параметрами двуместных операций union, intersect, symmetricDifference являются две коллекции, причем в OCL операции определены почти для всех возможных комбинаций типов коллекции. Не будем рассматривать все определения этих операций и кратко упомянем только две из них. Результатом операции union, определенной над множеством и мультимножеством, является мультимножество, т. е. из результата объединения таких двух коллекций дубликаты не исключаются. Результатом же операции union, определенной над двумя множествами, является множество, т. е. в этом случае возможные дубликаты должны быть исключены.

Операции управления прохождением транзакций

Каждая операция RSS выполняется в пределах некоторой транзакции. Интерфейс RSS включает набор операций управления прохождением транзакции: начать транзакцию (BEGIN TRANSACTION), закончить транзакцию (END TRANSACTION), установить точку сохранения (SAVE) и выполнить откат до указанной точки сохранения или до начала транзакции (RESTORE).

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

В любой точке транзакции до выполнения операции END TRANSACTION

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

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

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

Операция collect

Аналогично набору операций select, в OCL определены три операции collect, параметрами которых являются множество, мультимножество или последовательность и некоторое выражение над элементами соответствующей коллекции. Результатом является мультимножество для операций collect, определенных над множествами и мультимножествами, и последовательность для операции collect, определенной над последовательностью. При этом результирующая коллекция соответствующего типа (коллекция значений или объектов) состоит из результатов применения выражения к каждому элементу входной коллекции. Операция collect используется, главным образом, в тех случаях, когда от заданной коллекции объектов требуется перейти к некоторой другой коллекции объектов, которые ассоциированы с объектами исходной коллекции через некоторое соединение. В этом случае выражение над элементом исходной коллекции основывается на операции перехода по соединению.

Операция деления отношений

Эта операция наименее очевидна из всех операций реляционной алгебры Кодда и поэтому нуждается в более подробном объяснении. Пусть заданы два отношения – A с заголовком {a1, a2, ..., an, b1, b2, ..., bm} и B с заголовком {b1, b2, ..., bm}. Будем считать, что атрибут bi отношения A и атрибут bi отношения B (i = 1, 2, …, m) не только обладают одним и тем же именем, но и определены на одном и том же домене. Назовем множество атрибутов {aj} составным атрибутом a, а множество атрибутов {bj} – составным атрибутом b. После этого будем говорить о реляционном делении «бинарного» отношения A{a, b} на унарное отношение B{b}.

По определению, результатом деления A на B (A DIVIDE BY B) является «унарное» отношение C{a}, тело которого состоит из кортежей v таких, что в теле отношения A содержатся кортежи v UNION w такие, что множество {w} включает тело отношения B. Операция реляционного деления не является примитивной и выражается через операции декартова произведения, взятия разности и проекции. Мы покажем это в следующей лекции.

Для иллюстрации этой операции предположим, что в базе данных служащих поддерживаются следующие отношения: СЛУЖАЩИЕ, как оно было определено ранее, и унарное отношение НОМЕРА_ПРОЕКТОВ {ПРО_НОМ} (). Тогда запрос СЛУЖАЩИЕ DIVIDE BY НОМЕРА_ПРОЕКТОВ выдаст данные обо всех служащих, участвующих во всех проектах (результат операции приведен также на ).

Рис. 4.10.  Пример реляционного деления

Операция добавления поля к существующей таблице

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

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

Операция явной синхронизации

Последняя операция интерфейса RSS – операция явной синхронизации LOCK. Эта операция позволяет установить явную синхронизационную блокировку указанной таблицы (параметром операции является идентификатор таблицы). Выполнение операции LOCK

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

Из всего, что говорилось раньше по поводу подхода к синхронизации в System R и соответствующего разбиения системы на уровни, следует нелогичность наличия этой операции в интерфейсе RSS. На самом деле, логически эта операция избыточна, т.е. если бы ее не было, можно было бы реализовать SQL с использованием оставшейся части операций. Предварительно (до подробного обсуждения средств управления транзакциями в лекции 13) заметим, что операция LOCK

введена в интерфейс RSS для возможности оптимизации выполнения запросов.

Дело в том, что, как видно из описания интерфейса RSS, этот интерфейс является покортежным. Следовательно, и информация для синхронизации носит достаточно узкий характер. В то же время, на уровне SQL имеется более полная информация. Например, если обрабатывается предложение SQL DELETE FROM table_name, то известно, что будут удалены все кортежи указанной таблицы. Понятно, что как бы не реализовывался механизм синхронизации в RSS, в данном случае выгоднее сообщить сразу, что изменения касаются всей таблицы.

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

Операция ограничения

Операция ограничения WHERE требует наличия двух операндов: ограничиваемого отношения и простого условия ограничения. Простое условие ограничения может иметь: вид (a comp-op b), где i>a и i>b – имена атрибутов ограничиваемого отношения; атрибуты i>a и i>b должны быть определены на одном и том же домене, для значений базового типа данных которого поддерживается операция сравнения i>comp-op, или на базовых типах данных, над значениями которых можно выполнять эту операцию сравнения;или вид (a comp-op const), где a – имя атрибута ограничиваемого отношения, а const – литерально заданная константа; атрибут a должен быть определен на домене или базовом типе, для значений которого поддерживается операция сравнения comp-op.

Операцией сравнения comp-op могут быть «=», «

Для обозначения вызова операции ограничения будем использовать конструкцию A WHERE comp, где A – ограничиваемое отношение, а comp – простое условие сравнения. Пусть comp1 и comp2 – два простых условия ограничения. Тогда по определению: A WHERE (comp1 AND comp2) обозначает то же самое, что и (A WHERE comp1) INTERSECT (A WHERE comp2);A WHERE (comp1 OR comp2) обозначает то же самое, что и (A WHERE comp1) UNION (A WHERE comp2);A WHERE NOT comp1 обозначает то же самое, что и A MINUS (A WHERE comp1).

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

Результат выполнения операции СЛУЖАЩИЕ_В_ПРОЕКТЕ_1 WHERE (СЛУ_ЗАРП > 20000.00 AND (СЛУ_ОТД_НОМ = 310 OR СЛУ_ОТД_НОМ = 315)) (получить данные из отношения СЛУЖАЩИЕ_В_ПРОЕКТЕ_1 о служащих, работающих в отделах 310 и 315 и получающих зарплату, превышающую 20 000.00 руб.) показан на .

Рис. 4.5.  Результат операции СЛУЖАЩИЕ_В_ПРОЕКТЕ_1 WHERE (СЛУ_ЗАРП 200 > 20000.00 AND (СЛУ_ОТД_НОМ = 310 OR СЛУ_ОТД_НОМ = 315))

На интуитивном уровне операцию ограничения лучше всего представлять как взятие некоторой «горизонтальной» вырезки из отношения-операнда (выборки некоторых строк из таблицы).

Операция переименования

Пусть s обозначает результат операции r <RENAME> (A, B). Для обеспечения возможности выполнения операции требуется, чтобы существовал некоторый тип T, такой, что <A, T>

Операция <RENAME> производит отношение s, которое отличается от заданного отношения r только именем одного его атрибута, которое изменяется с A на B. Заголовок s такой же, как заголовок r, за исключением того, что пара <B, T> заменяет пару <A, T>. Тело s включает все кортежи тела r, но в каждом из этих кортежей триплет <B, T, v> заменяет триплет <A, T, v>.

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

Операция расширенного декартова произведения и совместимость отношений относительно этой операции

Другие проблемы связаны с операцией взятия декартова произведения двух отношений. В теории множеств декартово произведение может быть получено для любых двух множеств, и элементами результирующего множества являются пары, составленные из элементов первого и второго множеств. Если говорить более точно, декартовым произведением множеств A{a} и B{b} является такое множество пар C{<c1, 2>}, что для каждого элемента <c1, c2> множества C существуют такой элемент a множества A, что c1=a, и такой элемент b множества B, что c2=b.

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

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

Приведем более точное определение операции расширенного декартова произведения. Пусть имеются два отношения R1{a1, a2, …, an} и R2{b1, b2, …, bm}. Тогда результатом операции R1 TIMES R2 является отношение R{a1, a2, …, an, b1, b2, …, bm}, тело которого является множеством кортежей вида {ra1, ra2, …, ran, rb1, rb2, …, rbm} таких, что {ra1, ra2, …, ran} входит в тело R1, а {rb1, rb2, …, rbm} входит в тело R2.

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

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

Для наглядности предположим, что в придачу к введенным ранее отношениям СЛУЖАЩИЕ_В_ПРОЕКТЕ_1 и СЛУЖАЩИЕ_В_ПРОЕКТЕ_2 в базе данных содержится еще и отношение ПРОЕКТЫ со схемой {ПРОЕКТ_НАЗВ, ПРОЕКТ_РУК} (имена доменов снова опущены) и телом, показанным на . На этом же рисунке показан результат операции СЛУЖАЩИЕ_В_ПРОЕКТЕ_1 TIMES ПРОЕКТЫ.