Именование объектов и организация распределенного каталога

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

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

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

Для определения синонимов SQL расширен оператором вида

DEFINE SYNONYM <relation-name> AS <system-wide-name>.

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

Таким образом, при компиляции запроса всегда можно определить системные имена всех употребляемых в нем отношений: либо они явно указаны, либо могут быть получены на основе информации из локальных отношений-каталогов.
Концепция распределенного каталога System R* основана на наличии у каждого объекта распределенной базы данных уникального системного имени. Принято следующее соглашение: информация о размещении любого объекта базы данных (идентификатор текущего узла, в котором размещен объект) сохраняется в локальном каталоге того узла, в котором объект располагался непосредственно после создания (родового узла). Следовательно, для получения полной информации об отношении в общем случае необходимо сначала воспользоваться локальным каталогом узла, в котором происходит компиляция, затем обратиться к удаленному каталогу родового узла данного отношения и в заключение воспользоваться каталогом текущего узла. Таким образом, для получения точной системной информации о любом отношении распределенной базы данных может потребоваться самое большее два удаленных доступа к отношениям-каталогам. Применяется некоторая оптимизация этой процедуры. В локальном каталоге узла могут храниться копии элементов каталога других узлов (своего рода кэш-каталог). Согласованность копий элементов каталога не поддерживается. Эта информация используется на первой стадии компиляции запроса (мы рассматриваем распределенную компиляцию в следующем подразделе), а затем, на второй стадии, если информация, касающаяся некоторого объекта, оказалась неточной, она уточняется на основе локального каталога того узла, в котором объект хранится в настоящее время. Обнаружение некорректности копии элемента каталога производится за счет наличия при каждом элементе каталога номера версии. Если учесть достаточную инерционность системной информации, эта оптимизация может оказаться существенной. | |

Интерфейс RSS

Мы опишем свое представление об интерфейсе RSS, которое не соответствует в точности ни одной из публикаций из приведенного списка литературы, а является скорее некоторой компиляцией, согласующейся с завершающими публикациями [25-27]. При этом основная информация почерпнута из [16] (с некоторой коррекцией).

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

- 22 памяти для временных объектов.

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

- операции сканирования отношений и списков;

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

- операции модификации отношений и списков;

- операция добавления поля к отношению;

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

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

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

Для отношений возможны два режима сканирования: по отношению и по индексу. При сканировании по отношению единственным параметром операции OPEN является идентификатор отношения (включающий, кстати, и идентификатор сегмента, в котором это отношение хранится). По причине того, что в System R допускается размещение в одной странице данных кортежей нескольких отношений, сканирование по отношению предполагает последовательный просмотр всех страниц сегмента с выделением в них кортежей, входящих в данное отношение; это очень дорогой способ сканирования отношения. При этом порядок выборки кортежей определяется их физическим размещением в страницах сегмента, т.е.
предопределен системой. При открытии сканирования отношения по одному из его индексов в число параметров операции OPEN входит идентификатор индекса, определенного ранее на полях этого отношения. Кроме того, можно указать диапазон сканирования в терминах значений полей, составляющих ключ индекса. При открытии сканирования по индексу производится начальная установка в позицию листа B-дерева индекса, соответсвующую левой границе заданного диапазона. Процесс сканирования состоит в последовательном продвижении по листовым вершинам индекса до достижения правой границы диапазона сканирования с выборкой tid'ов и чтением соответствующих кортежей. Легко видеть, что если сканирование производится не по кластеризованному индексу, то в худшем случае может потребоваться столько чтений страниц данных из внешней памяти, сколько tid'ов было встречено, т.е. эффективность сканирования по индексу определяется "широтой" заданного диапазона сканирования. При этом, конечно, имеется то преимущество, что порядок сканирования соответствует порядку возрастания или убывания значений ключа индекса. Наконец, при сканировании списка, как и при сканировании по отношению, единственным параметром операции OPEN является идентификатор списка, но, в отличии от сканирования по отношению это сканирование максимально эффективно: читаются только страницы, содержащие кортежи из данного списка, и порядок сканирования совпадает с порядком занесения кортежей в список или порядком списка, если он упорядочен. В результате успешного выполнения операции открытия скана (если нет ошибок в параметрах) вырабатывается и возвращается идентификатор скана, который используется в качестве входного параметра других операций группы сканирования. Операция NEXT выполняет чтение следующего кортежа указанного скана, удовлетворяющего условиям данной операции. Условие представляет собой дизъюнктивную нормальную форму простых условий, относящихся к значениям указанных полей отношение. Простое условие - это условие вида <идентификатор-поля op константа>, где op - операция сравнения <, <=, >, >=, = или !=.


Общее условие является параметром операции NEXT. Семантика операции NEXT следующая: Начиная с текущей позиции сканирования выбираются кортежи отношения в порядке, определяемом типом сканирования, до тех пор, пока не встретится кортеж, значения полей которого удовлетворяют указанному условию. Этот кортеж и является результатом операции. Если при выборке следующего кортежа достигается правая граница диапазона сканирования (правая граница значения ключа при сканировании по индексу или последний кортеж отношения или списка при сканировании без индекса), вырабатывается особый признак результата. После этого единственным разумным действием является закрытие сканирования - операция CLOSE. Операция CLOSE может быть выполнена в данной транзакции по отношению к любому ранее открытому скану независимо от его состояния (т.е. независимо от того, достигнута ли при сканировании правая граница диапазона сканирования). Параметром операции является идентификатор скана, и ее выполнение приводит к тому, что этот идентификатор становится недействительным (и, соотвественно, уничтожаются служебные структуры памяти RSS, относящиеся к данному скану). \_Группа операций создания и уничтожения постоянных и временных объектов базы данных\. включает операции создания таблиц (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 и DROP IMAGE) требуют дополнительных накладных расходов в связи с необходимостью обеспечения возможности откатов транзакции, в результате чего требуется выполнение массовых обратных действий.


Особенно сильно это затрагивает операцию уничтожения непустых таблиц, поскольку требует журнализации всех содержащихся в нем к моменту уничтожения кортежей. Поэтому, хотя уничтожение непустых таблиц и не запрещено, нужно иметь в виду, что это очень дорогостоящая операция. Группа операций модификации отношений и списков включает операции вставки кортежа в отношение или список (INSERT), удаления кортежа из отношения (DELETE) и модификации кортежа в отношении (UPDATE). Параметрами операции занесения кортежа являются идентификатор отношения или списка и набор значений полей кортежа. Среди значений полей могут быть литеральные неопределенные значения NULL. Естественно, при выполнении операции контролируется допуcтимость неопределенных значений в соответствующих полях. При занесении кортежа в кластеризованное отношение поиск места в сегменте под кортеж производится с использованием кластеризованного индекса: система пытается вставить кортеж в страницу данных, уже содержащую кортежи с теми же или близкими значениями полей кластеризации. При занесении кортежа в некластеризованное отношение место под кортеж выделяется в первой подходящей странице данных. Наконец, при вставке кортежа в список он помещается в конец списка. При занесении кортежа в постоянное отношение производится коррекция всех индексов, определенных на этом отношении. Реально это выражается во вставке новой записи во все B-деревья индексов. При этом, естественно, могут произойти переполнения одной или нескольких страниц индекса, что вызовет переливание части записей в соседнии страницы или расщепление страниц. Если индекс определен с атрибутом уникальности, то проверяется соблюдение этого условия, и если оно нарушено, операция вставки считается невыполненной. Из этого видно, что операция занесения кортежа тем более накладна, чем больше индексов определено для данной таблицы (это относится и к операциям удаления и модификации кортежей). В результате успешного выполнения операции занесения кортежа в отношение вырабатывается tid нового кортежа, который сообщается в качестве ответного параметра и может быть в дальнейшем использован как прямой параметр операций удаления и модификации кортежей отношения.


При занесении кортежа в список значение tid'а не вырабатывается ( списки допускают только последовательное сканирование и добавление новых кортежей в конец, над ними нельзя определить индексов, поэтому косвенная адресация кортежей списков через tid'ы не требуется). Операции удаления и модификации кортежей допускаются только по отношению к кортежам постоянных таблиц. Естественно, что для выполнения этих операций необходимо идентифицировать соответсвующий кортеж. Интерфейс RSS допускает два способа такой идентификации: с помощью tid'а кортежа (явная адресация) и с использованием идентификатора открытого к этому времени скана. Первый вариант возможен, поскольку tid кортежа сообщается как ответный параметр операции занесения кортежа в постоянную таблицу. При идентификации кортежа с помощью скана имеется в виду кортеж, прочитанный с помощью последней операции NEXT. Если при такой идентификации выполнена операция DELETE или UPDATE, задевающая порядок сканирования (т.е. сканирование ведется по индексу и операция модификации меняет поле кортежа, входящее в состав ключа этого индекса), то текущий кортеж скана теряется, и его идентификатор нельзя использовать для идентификации кортежа до выполнения следующей операции NEXT. Единственным параметром операции DELETE является идентификатор кортежа (tid или идентификатор скана). Параметры операции UPDATE включают кроме этого идентификатора спецификацию изменяемых полей кортежа (список номеров полей и их новых значений). Среди значений могут находиться литеральные изображения неопределенных значений, если соответствующие поля отношения допускают хранение неопределенных значений. При выполнении операции DELETE производится коррекция всех индексов, определенных на данном отношении. Операция UPDATE также может повлечь коррекцию индексов, если затрагивает поля, входящие в состав их ключей. Кроме описанных "атомарных" операций сканирования и модификации таблиц и списков, интерфейс RSS включает одну "макрооперацию", позволяющую за одно обращение к RSS построить отсортированный по значением заданных полей список.


Эта операция BUILDLIST включает сканирование заданного отношения или списка, создание нового списка, в который включаются указанные поля выбираемых кортежей, и сортировку построенного списка в соответствии со значениями указанных полей. Идентификатор заново построенного отсортированного списка является ответным параметром операции. Соответственно, параметрами операции BUILDLIST является набор параметров для открытия сканирования (допускается любой способ сканирования), список номеров полей, составляющих кортежи нового списка, и список номеров полей, по которым нужно производить сортировку (как и в случае создания нового индекса, можно отдельно для каждого из этих полей указать требование к сортировке по возрастанию или убыванию значений данного поля). Отдельным параметром операции BUILDLIST является признак, в соответствии со значением которого допускаются или не допускаются кортежи-дубликаты в новом списке. Забегая вперед, заметим, что допущение или недопущение дубликатов в отсортированном списке зависит от того, для каких целей он строится. Например, если список строится для выполнения операции соединения, то дубликатов в нем быть не должно. Если же список строится для вычисления агрегатных функций (COUNT, AVG и т.д.), то дубликаты из него убирать нельзя. Более подробно мы рассмотрим этот и близкие вопросы в подразделе 1.8 в связи с проблемами оптимизации запросов в System R. Операция RSS добавления поля к существующей таблице позволяет в динамике изменять схему таблицы. Параметрами операции CHANGE являются идентификатор существующей таблицы и спецификация нового поля (его тип). При выполнении операции изменяется только описатель данного отношения в служебном отношении описателей отношений. Как мы уже отмечали в предыдущем подразделе, до выполнения первой операции UPDATE, затрагивающей новое поле таблицы, реально ни в одном кортеже таблицы память под новое поле выделяться не будет. По умолчанию значения нового поля во всех кортежах таблицы, в которые еще не производилось явное занесение значения, считаются неопределенными.


Тем самым, ни для одного поля, динамически добавленного к существующей таблице, не может быть запрещено хранение неопределенных значений. Каждая операция RSS выполняются в пределах некоторой транзакции. Интерфейс RSS включает набор операций управления прохождением транзакции: начать транзакцию (BEGIN TRANSACTION), закончить транзакцию (END TRANSACTION), установить точку сохранения (SAVE) и выполнить откат до указанной точки сохранения или до начала транзакции (RESTORE). Мы не отмечали этого раньше, но на самом деле при обращении к любой функции RSS, кроме BEGIN TRANSACTION, должен указываться еще один параметр - идентификатор транзакции. Этот идентификатор и вырабатывается при выполнении операции BEGIN TRANSACTION, которая сама входных параметров не требует. В любой точке транзакции до выполнения операции END TRANSACTION может быть выполнен откат данной транзакции, т.е. обратное выполнение всех изменений, произведенных в данной транзакции, и восстановление состояния сканов. Откат может быть произведен до начала транзакции (в этом случае о восстановлении состояния сканов говорить не приходится) или до установленной ранее в транзакции точке сохранения. Точка сохранения устанавливается с помощью операции SAVE. При выполнении этой операции запоминается состояние сканов данной транзакции, открытых к моменту выполнения SAVE, и координаты последней записи об изменениях в базе данных в журнале, произведенной от имени данной транзакции. Ответным параметром операции SAVE (а прямых параметров, кроме идентификатора транзакции, она не требует) является идентификатор точки сохранения. Этот идентификатор в дальнейшем может быть использован как прямой параметр операции RESTORE, при выполнении которой производится восстановление по журналу базы данных с использованием записей о ее изменениях от данной транзакции до того состояния, в котором находилась база данных к моменту установления указанной точки сохранения. Кроме того, по локальной информации в оперативной памяти, привязанной к транзакции, восстанавливается состояние ее сканов.


Откат к началу транзакции инициируется также обращением к операции RESTORE, но с указанием некоторого предопределенного идентификатора точки сохранения. При выполнении своих транзакций пользователи System R изолированы один от другого, т.е. не ощущают того, что система функционирует в многопользовательском режиме. Это достигается за счет наличия в RSS механизма неявной синхронизации (более полно это мы обсудим в следующем подразделе). Пока заметим лишь, что до конца транзакции никакие изменения базы данных, произведенные в пределах этой транзакции, не могут быть использованы в других транзакциях (попытка использования таких данных приводит в временным синхронизационным блокировкам этих транзакций). При выполнении операции END TRANSACTION происходит "фиксация" изменений, произведенных в данной транзакции, т.е. они становятся видимыми в других транзакциях. Реально это означает снятие синхронизационных захватов с объектов базы данных, изменявшихся в транзакции. Из этого следует, что после выполнения END TRANSACTIN невозможны индивидуальные откаты данной транзакции. RSS просто делает недействительным идентификатор данной транзакции, и после выполнения операции окончания транзакции отвергает все операции с таким идентификатором. Последняя операция интерфейса RSS - операция явной синхронизации LOCK. Эта операция позволяет установить явный синхронизационный захват на указанное отношение (параметром операции является идентификатор таблицы). Выполнение операции LOCK гарантирует, что никакая другая транзакция до конца данной не сможет изменить данное отношение (вставить в него новый кортеж, удалить или модифицировать существующий), если устанавливается захват на чтение отношения, или даже прочитать любой кортеж этого отношения, если захват устанвливается на изменение. Из всего, что говорилось раньше по поводу подхода к синхронизации в System R и соответствующего разбиения системы на уровни, следует нелогичность наличия этой операции в интерфейсе RSS. На самом деле, логически эта операция избыточна, т.е.


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

Исходные цели проекта System R*

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

- легкость использования системы;

- возможности автономного функционирования при нарушениях связности сети или при административных потребностях;

- высокая степень эффективности.

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

Следуя [49], рассмотрим, каким образом в System R* решаются указанные выше проблемы.

Легкость использования системы достигается за счет того, что пользователи System R* (разработчики прикладных программ и конечные пользователи) остаются в среде языка SQL, т.е. могут продолжать работать в тех же внешних условиях, что и в System R (и SQL/DS и DB2). Возможность использования SQL основывается на обеспечении System R* прозрачности местоположения данных. Система автоматически обнаруживает текущее местоположение упоминаемых в запросе пользователя объектов данных; одна и та же прикладная программа, включающая предложения SQL, может быть выполнена в разных узлах сети. При этом в каждом узле сети на этапе компиляции запроса выбирается наиболее оптимальный план выполнения запроса в соответствии с расположением данных в распределенной системе.

Обеспечению автономности узлов сети в System R* уделяется очень большое внимание. Каждая локальная база данных администрируется независимо от других. Возможны автономное подключение новых пользователей, смена версии автономной части системы и т.д. Система спроектирована таким образом, что в ней не требуются централизованные службы именования объектов или обнаружения тупиков.
В индивидуальных узлах не требуется наличие глобального знания об операциях, выполняющихся в других узлах сети; работа с доступными базами данных может продолжаться при выходе из строя отдельных узлов сети или линий связи. Высокая степень эффективности системы является одним из наиболее ключевых требований к распределенным системам управления базами данных вообще и к System R* в частности. Как мы отмечали в Разделе 2, этому вопросу уделялось большое внимание и в System R. Именно то, что в System R удалось обеспечить достаточно эффективное выполнение запросов, позволило фирме IBM перейти на выпуск коммерческих систем SQL/DS и DB2. Добиться эффективного выполнения запросов в распределенной системе, естестственно, существенно более трудно, чем в централизованной. В System R* для достижения этой цели используются два основных приема. Во-первых, как и в System R, в System R* выполнению запроса предшествует его компиляция. В ходе этого процесса производится поиск употребляемых в запросе имен объектов баз данных в распределенном каталоге и замена имен на внутренние идентификаторы; проверка прав доступа пользователя, от имени которого производится компиляция, на выполнение соответствующих операций над базами данных и выбор наиболее оптимального глобального плана выполнения запроса, который затем подвергается декомпозиции и по частям рассылается в соответствующие узлы сети, где производится выбор оптимальных локальных планов выполнения компонентов запроса и происходит генерация модулей доступа в машинных кодах. В результате множество действий производится на стадии компиляции до реального выполнения запроса. Обработанная посредством прекомпилятора System R* прикладная программа, включающая предложения SQL, может в дальнейшем выполняться много раз без дополнительных накладных расходов. Использование распределенного каталога, распределенная компиляция и оптимизация запросов, как отмечается в [34], являются наиболее интересными и оригинальными аспектами проекта System R*. В следующих подразделах этого раздела мы рассмотрим эти аспекты более подробно.


Вторым средством повышения эффективности системы является возможность перемещения удаленных отношений в локальную базу данных. Диалект SQL, используемый в System R*, включает предложение MIGRATE TABLE, при выполнении которого указанное отношение переносится в локальную базу данных. Это средство, находящееся в распоряжении пользователей, конечно, в ряде случаев может помочь добиться более эффективного прохождения транзакций. Естественно, как и для всех операций, операция MIGRATE по отношению к указанному отношению доступна не любому пользователю, а лишь тем, которые обладают соответствующим правом. Прежде, чем перейти к более детальному изложению наиболее интересных аспектов реализации System R*, упомянем некоторые средства, которые разработчики этой системы предполагали реализовать на начальной стадии проекта [41], но которые реализованы не были (причем некоторые из них, видимо, и не будут никогда реализованы). Предполагалось иметь в системе средства горизонтального и вертикального разделения отношений распределенной базы данных, средства дублирования отношений в нескольких узлах с поддержкой согласованности копий и средства поддержания мгновенных снимков состояния баз данных в соответствии с заданным запросом. Для задания горизонтального разделения отношений в SQL была введена конструкция вида DISTRIBUTE TABLE <table-name> HORIZONTALLY INTO <name> WHERE <predicate> IN SEGMENT <segment-name site> . . <name> WHERE <predicate> IN SEGMENT <segment-name site> При выполнении предложения такого типа указанное отношение разбивалось на ряд подотношений, содержащих кортежи, удовлетворяющие соответствующему предикату из раздела WHERE, и каждое полученное таким образом подотношение посылалось в казанный узел для хранения в сегменте с указанным именем. Гарантируется согласованное состояние разделов при изменении отношения. Вертикальное разделение производилось с помощью предложения DISTRIBUTE TABLE <table-name> VERTICALLY INTO


<name> WHERE <column-name-list> IN SEGMENT <segment-name site> . . <name> WHERE <column-name-list> IN SEGMENT <segment-name site> При выполнении такого предложения также образовывался набор подотношений с помощью проекции заданного отношения на атрибуты из заданного списка. Каждое полученное подотношение затем посылалось для хранения в сегменте с указанным именем в соответствующий узел. После этого система ответственна за поддержание согласованного состояния образованных разделов. Горизонтальное и вертикальное разделение отношений реально не используются в System R*, хотя очевидно, что выполнение собственно оператора DISTRIBUTE никаких технических трудностей не вызывает. Трудности возникают при обеспечении согласованности разделов (смотри ниже). Кроме того, разделенные отношения очень трудно использовать. В соответствии с идеологией системы учет наличия разделов отношения в разных узлах сети должен производить оптимизатор, т.е. количество потенциально возможных планов выполнения запросов, которые должны оцениваться оптимизатором, еще более возрастает. При том, что в распределенной системе число возможных планов и так очень велико, и оптимизатор работает на пределе сложности, разумным образом использовать разделенные отношения невозможно. Как следует из оценок, приводимых в [51], разработчики оптимизатора System R* пока не в состоянии учитывать разделенность отношений. Поэтому и вводить в систему разделенные отношения пока бессмысленно. Для задания требования поддержки копий отношения в нескольких узлах сети предлагалось использовать новую конструкцию SQL DISTRIBUTE TABLE <table-name> REPLICATED INTO <name> IN SEGMENT <segment-name site> . . <name> IN SEGMENT <segment-name site> При выполнении такого предложения должна была производиться рассылка копий указанного отношения для хранения в именованных сегментах указанных узлов сети. Система должна автоматически поддерживать согласованность копий.


Как и в случае разделенных отношений, кроме существенных проблем поддержания согласованности копий, проблемой является и разумное использование копий, наличие которых должно было бы учитываться оптимизатором. Создание мгновенного снимка состояния баз данных в соответствии с заданным запросом на выборку должно было производиться с использованием новой конструкции SQL DEFINE SNAPSHOT <snapshot-name> (<attribute-list>) AS <quary> REFRESHED EVERY <period> При выполнении предложения фактически производится выполнение указанного в нем запроса на выборку, а результирующее отношение сохраняется под указанным в предложении именем в локальной базе данных в том узле, в котором выполняется предложение. После этого мгновенный снимок периодически обновляется в соответствии с запомненным запросом. Можно обновить мгновенный снимок, не дожидаясь истечения временного интервала, указанного в определении, путем выполнения предложения REFRESH SNAPSHOT <snapshot-name>. Разумное использование мгновенных снимков более реально, чем использование разделенных отношений и копированных отношений, поскольку их можно в некотором смысле рассматривать как материализованные представления базы данных. Имя мгновенного снимка можно было бы использовать прямо в запросе на выборку там, где можно использовать имена базовых отношений или представлений. Большие проблемы связаны с обновлением отношений через их мгновенные снимки, поскольку в момент обновления содержимое мгновенного снимка может расходиться с текущим содержимым базового отношения. По отношению к мгновенным снимкам проблем поддержания согласованного состояния мгновенного снимка и базовых отношений не существует, поскольку автоматическое согласование не требуется. Что же касается разделенных отношений и раскопированных отношений, то для них эта проблема общая и достаточно трудная. Во-первых, согласование разделов и копий вызывает существенные накладные расходы при выполнении операций модификации хранимых отношений.


Для этого требуется выработка и соблюдение специальных протоколов модификации. Во-вторых, введение копированных отношений обычно производится не столько для увеличения эффективности системы, сколько для увеличения доступности данных при нарушении связности сети. В системах, в которых применяется этот подход, при нарушении связности сети работа с распределенной базой данных обычно продолжается только в одной из образовавшихся подсетей. При этом для выбора подсети используются алгоритмы голосования; решение принимается на основе учета количества связных узлов сети. Применяются и другие подходы, но все они очень дорогостоящие, а самое главное, они плохо согласуются с базовым подходом System R* по поводу выбора способа выполнения запроса на стадии его компиляции. Поэтому, как нам кажется, в System R* никогда не будут реализованы средства, позволяющие тем или иным способом поддерживать копии отношений в нескольких узлах сети. Далее в этом разделе мы рассмотрим аспекты проекта System R*, которые нашли отражение в ее реализации и являются на наш взгляд наиболее интересными: средства именования объектов и организацию распределенного каталога баз данных; подход к распределенным компиляции и выполнению запросов; особенности использования представлений; средства оптимизации запросов; особенности управления транзакциями; средства синхронизации и распределенный алгоритм обнаружения синхронизационных тупиков. | |

Используемая терминология

Что касается общей терминологии реляционного подхода, то она является достаточно установившейся, и мы будем активно ей пользоваться. К таким терминам относятся названия реляционных операций - селекция, проекция, соединение; названия теоретико-множественных операций - объединение, пересечение, разность и т.д.

В тех случаях, когда традиционная терминология System R расходится с общепринятой, мы будем отдавать предпочтение терминологии System R. В частности, это касается использования термина "поле отношения" вместо "атрибут отношения".

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

Базовым понятием System R является понятие таблицы (приб- лиженный к реализации эквивалент основного понятия реляционного подхода отношения; иногда, в зависимости от контекста, мы будем использовать и этот термин). Таблица - это некоторая регулярная структура, состоящая из конечного набора однотипных записей - кортежей. Каждый кортеж одного отношения состоит из конечного (и одинакового) числа полей кортежа, причем i-тое поле каждого кортежа одного отношения может содержать данные только одного типа, и число допустимых типов данных в System R предопределено и фиксировано. В силу регулярности структуры отношения понятие поля кортежа расширяется до понятия поля таблицы. I-тое поле таблицы можно трактовать как набор одноместных кортежей, полученных выборкой i-тых полей из каждого кортежа этой таблицы, т.е. в общепринятой терминологии как проекцию отношения на i-тый атрибут. В терминологию System R не входит понятие домена, оно заменяется здесь понятием типа поля, т.е.
типом допустимых данных, которые могут храниться в данном поле (это не вполне эквивалентная замена, но такова реальность System R). Таблицы, составляющие базу данных System R, могут физически храниться в одном или нескольких сегментах, которые проще всего понимать как файлы внешней памяти (и это вполне соответствует действительности). Сегменты разбиваются на страницы, в которых располагаются кортежы отношений и вспомогательные служебные структуры данных индексы. Соответственно, каждый сегмент содержит две группы страниц - страницы данных и страницы индексной информации. Страницы каждой группы имеют фиксированный размер, но страницы с индексной информацией меньше по размеру, чем страницы данных. В страницах данных могут располагаться кортежи более, чем одного отношения (это очень важное свойство физической организации баз данных System R; полностью разъяснить следующие из этой организации преимущества мы сможем только в Разделе 3). Этим, конечно, не исчерпывается набор понятий System R, но остальные термины мы будем вводить по ходу изложения, поскольку для этого требуется соответствующий понятийный контекст. | |

Литерутура

1. Chamberlin D.D., Boyce R.F. SEQUEL: A Structured English Query Language // ACM SIGMOD Workshop Data Descr., Acc. Contr., Proc., Ann Arbol, Mich., May 1974. New-York, 1974.- C. 249-264

2. Chamberlin D.D., Boyce R.F., Traiger I.L. A Deadlock-Free Scheme for Resource Locking in a Data Base Environment // Inf. Process., 74. IFIP World Comput. Congr., Geneva, 1974. Amsterdam e.a., 1974.- C. 340-343

3. Chamberlin D.D., Gray J.N., Traiger I.L. View, autorization, and locking in a relational database system // AFIPS Conf. Proc.: Nat. Comput. Conf., Chicago, Ill., May 4-7, 1975. Reston, Virg., 1975.- C. 425-430

4. Reisner P., Boyce R.F., Chamberlin D.D. Human Factors Evaluation of Two Data Base Query Languages: SQUARE and SEQUEL // AFIPS Conf. Proc.: Nat. Comput. Conf., Chicago, Ill., May 4-7, 1975. Reston, Virg., 1975.- C. 431-435

5. Gray J.N., Lorie R.A., Putzolu G.R., Traiger I.L. Granularity of Locks in a Large Shared Data Base // 1st Int. Conf. Very Large Data Bases, Framingham, Mass., Sept. 1975. New-York, 1976.- C.428-451

6. Eswaran K.P., Chamberlin D.D. Functional Specifications of a Subsystem for Data Base Integrity. // 1st Int. Conf. Very Large Data Bases, Framingham, Mass., Sept. 1975. New-York, 1976.- C. 48-68

7. Astrahan M.M., Chamberlin D.D. Implementation of a Structured English Query Language // Commun. ACM.- 1975.- 18, N 10.- C. 580-588

8. Chamberlin D.D., Astrahan M.M., Eswaran K.P., Griffits P.P., Lorie R.A., Mehl J.W., Reisner P., Wade B.W. SEQUEL 2: A Unified Approach to Data Definition, Manipulation, and Control // IBM J. Res. and Dev.- 1976.- 20, N 6.- C. 560-575

9. Astrahan M.M., Blasgen M.W., Chamberlin D.D., Eswaran K.P., Griffits P.P., King W., Lorie R.A., McJones P., Mehl J.W., Putzolu G.R., Traiger I.L., Wade B.W., Watson V. System R: A Relational Approach to Data Base Management // ACM Trans. Database Syst.- 1976.- 1, N 2.- C. 97-137

10. Gray J.N., Lorie R.A., Putzolu G.R., Traiger I.L. Granularity of Locks and Degrees of Consistency in a Shared Database // Proc.
IFIP Work. Conf. Model. Data Base Manag. Syst., Freudenstadt, Germany, Jan. 1976. New-York, 1976.- C. 695-723 11. Eswaran K.P., Gray J.N., Lorie R.A., Traiger I.L. The Notions of Consistency and Predicate Locks in a Database System // Commun. ACM.- 1976.- 19, N 11.- C. 624-633 12. Griffiths P.P., Wade B.W. An Authorization Mechanism for a Relational Database System // ACM Trans. Database Syst.1976.- 1, N 3.- C. 242-255 13. Blasgen M.W., Eswaran K.P. Storage and Access in Relational Data Bases // IBM Syst. J.- 1977.- 16, N 4, C.363-377 14. Lorie R.A. Physical Integrity in a Large Segmented Database // ACM Trans. Database Syst.- 1977.- 2, N 1, C.91-104 15. Blasgen M.W., Gray J.N., Mitoma M., Price T.G. The Convoy Phenomenon // ACM Oper. Syst. Rev.- 1979.- 13, N 2.C.20-25 16. Lorie R.A., Nilsson J.F. An Access Specification Language for a Relatiomal Data Base System // IBM J. Res. and Dev.- 1979.- 23, N 3.- C. 1-13 17. Kim W. Relational Database Systems // ACM Comput. Surv.- 1979.- 11, N 3.- C. 185-211 18. Gray J.N. Notes on Database Operating Systems // Lect. Notes Comput. Sci.- 1979.- 60.- C. 396-481 19. Selinger P.G., Astrahan M.M., Chamberlin D.D., Lorie R.A., Price T.G. Acess Path Selection in a Relational Database Management System // Proc. ACM SIGMOD Int. Conf. Manag. Data, Boston, Mass., May 30 - June 1, 1979. New York, 1979.- C. 23-34 20. King W.F. Relational Database Systems: Where We Stand Today // IFIP Process., 80. Proc. IFIP World Comput. Conf., Melbourne, Sept.1980. Amsterdam, 1980.- C. 369-387 21. Astrahan M.M., Schkolnick M., Kim W. Performance of the System R Acess Selection Mechanism. // IFIP Process., 80. Proc. IFIP World Comput. Conf., Melbourne, Sept.1980. Amsterdam, 1980.- C. 487-492 22. Chamberlin D.D. A Summary of User Experience with the SQL Data Sublanguage // Proc. Int. Conf. Databases, Aberdeen, Scotland, June 1980. Amsterdam, 1980.- C. 181-203 23. Gray J.N., McJones, P., Blasgen M.W., Lindsay B.G., Lorie R.A., Price T.G., Putzolu G.R., Traiger I.L. The Recovery Manager of the System R Database Manager // ACM Comput.


Surv.- 1981.- 13, N 2.- C. 223-242 24. Chamberlin D.D., Gilbert A.M., Yost R.A. A History of System R and SQL/Data System // 7th Int. Conf. Very Large Data Bases, Proc., Cannes, France, 3-11 Sept., 1981. New York, 1981.- C. 456-464 25. Chamberlin D.D., Astrahan M.M., Blasgen M.W., Gray J.N., King W.F., Lindsay B.G., Lorie L.A., Mehl J.W., Price T.G., Putzolu G.R., Selinger P.G., Schkolnick M., Slutz D.R., Traiger I.L., Wade B.W., Yost R.A. A History and Evaluation of System R // Commun. ACM.- 1981.- 24, N 10.- C. 632-646 26. D.D.Chamberlin, Astrahan M.M., King W.F., Lorie L.A., Mehl J.W., Price T.G., Schkolnick M., Griffiths P.P., Selinger P.G., Slutz D.R., Wade B.W., Yost R.A. Support for Repetitive Transactions and Ad Hoc Queries in System R // ACM Trans. Database Syst.- 1981.- 6, N 1.- C. 70-94 27. Blasgen M.W., Astrahan M.M., Chamberlin D.D., Gray J.N., King W.F., Lindsay B.G., Lorie L.A., Mehl J.W., Putzolu G.R., Schkolnick M., Selinger P.G., Slutz D.R., Strong H.R., Traiger I.L., Wade B.W., Yost R.A. System R: An Architectural Overview // IBM Syst. J.- 1981.- 20, N 1.- C. 41-62 28. Date C.J. A Critique of the SQL Database Language // ACM SIGMOD Rec..- 1984.- 14, N 3 .- C. 24-31 29. Haderle D.J., Jackson R.D. IBM Database 2 Overview // IBM Syst. J.- 1984.- 23, N 2.- C. 112-125 30. Дейт К. Руководство по реляционной системе DB2.- М.: Финансы и статистика.- 1988.- 320 c. 31. Дейт К. Введение в системы баз данных.- М.: Наука.1980.- 463 c. 32. Ульман Д. Основы систем баз данных.- М.: Финансы и статистика.- 1983.- 335 c. 33. Date C.J. An Introduction to Database Systems. V.1. 4th ed.- Reading MA: Addison-Wesley.- 1984.- 639 c. 34. Date C.J. An Introduction to Database Systems. V.2. 2nd ed.- Reading MA: Addison-Wesley.- 1985.- 383 c. 35. Blazdell R.K. The IBM SQL/DS System // Relational Databases. Oxford e.a., 1986.- C. 39-46 36. Working Draft Database Language SQL2 // ISO TC97/SC21 N.1479.- 1986.- 117 c. 37. Ferrante L. A Comparison of the ISO Working Draft Standard for SQL and a Commercial Implementation of SQL // ACM SIGSmall/PC Notes.- 1987.- 13, N 3.- C. 28-55


38. Lindsay B.G. Object Naming and Catalog Management for a Distributed Database Manager // 2nd Int. Conf. Distrib. Comput. Syst., Paris, April 1981. Washington, D.C., 1982.- C. 31-40 39. Daniels D., Selinger P., Haas L., Lindsay B., Mohan C., Walker A., Wilms P. An Introduction to Distributed Query Compilation in R* // 2nd Int. Symp. Distrib. Databases, West Berlin, Sept. 1-3, 1982. Amsterdam e.a., 1982.- C. 224-231 40. Traiger I.L., Gray J., Galtieri C.P., Lindsay B.G. Transactions and Consistency in Distributed Database Systems // ACM Trans. Database Syst.- 1982.- 7, N 3.- C. 323-342 41. Williams R., Daniels D., Haas L., Lapis G., Lindsay B., Ng P., Obermarck R., Selinger P., Walker A., Wilms P., Yost R. R*: An Overview of the Architecture // Improv. Usab. Respons.: Proc. 2nd Int. Conf. Databases, Jerusalem, June 1982. New York, 1982.- C. 1-27 42. Mohan C., Lindsay B.G. Efficient Commit Protocols for the Tree of Processes Model of Distributed Transactions // 2nd ACM SIGACT-SIGOPS Symp. Princ. Distrib. Comput., Montreal, Aug. 1983. New York, 1983.- C. 76-88 43. Bertino E., Haas L.M., Lindsay B.G. View Management in Distributed Data Base System // Proc. 9th Int. Conf. Very Large Data Bases, Florence, Oct. 1983. New York, 1983.- C. 376-378 44. Selinger P.G., Bertino E., Daniels D., Haas L., Lindsay B.G., Lohman G., Masunaga Y., Mohan C., Ng P., Wilms P., Yost R. The Impact of Site Autonomy on R*: A Distributed Relational DBMS // Role and Structure. London: Cambridge Univ. Press.- 1983.- C. 151-176 45. Wilms P.F., Lindsay B.G., Selinger P.G. I Wish I Were Over There: Distributed Execution Protocols for Data Definition // ACM SIGMOD Rec.- 1983.- 13, N 4.- C. 238-245 46. Lindsay B.G., Haas L., Mohan C., Wilms P., Yost R. Computation and Communication in R*: A Distributed Database Manager // ACM Trans. Comput. Syst.- 1984.- 2, N 1.- C. 24-38 47. Lohman G., Daniels D., Haas L., Kistler R., Selinger P. Optimization of Nested Queries in a Distributed Relational Database // Proc. 10th Int.


Conf. Very Large Data Bases, Singapore, Aug. 1984. New York, 1984.- C. 403-415 48. Lohman G., Mohan C., Haas L., Lindsay B.G., Selinger P.G., Wilms P., Daniels D. Query Processing in R* // Query Processing in Database Systems. New York e.a.: Springer.1985.- C. 31-47 49. Yost R.A., Haas L.M. R*: A Distributed Data Sharing System // Distributed Systems. Vol.II: Distributed Data Base Systems. Dedham, Mass.: Artech House.- 1986.- C. 462-476 50. Mackert L., Lohman G. R* Optimizer Validation and Performance Evaluation for Local Queries // Proc. ACM SIGMOD Conf. Manag. Data, Washington, D.C., May 28-30, 1986. New York, 1986.- C. 84-95 51. Mackert L., Lohman G. R* Optimizer Validation and Performance Evaluation for Distributed Queries // Proc. 12th Int. Conf. Very Large Data Bases, Kyoto, Japan, Aug. 1986. Palo Alto, Calif., 1986.- C. 149-159 52. Mohan C., Lindsay B., Obermarck R. Transaction Management in the R* Distributed Database Management System // ACM Trans. Database Syst.- 1986.- 11, N 6.- C. 378-396 53. Линдсей Б.Дж. Опыт создания системы управления распределенными базами данных R* // ТИИЭР.- 1987.- 75, N 5.- C. 165-172 54. Gray J.N. The Transaction Concept: Virtues and Limitations // Proc. 7th Int. Conf. Very Large Databases, Cannes, France, Sept. 3-11, 1981. New York, 1981.- C. 144-154 55. Haskins R., Lorie R.A. On Extending the Functions of a Relational Database System // Proc. ACM SIGMOD Int. Conf. Manag. Data, Orlando, Fl., June 2-4, 1982. New York, N.Y.: ACM Press.- 1982.- C. 207-212 56. Lorie R.A., Plouffe W. Complex Oblects and Their Use in Design Transactions // Eng. Des. Appl.: Proc. ACM - IEEE Data Base Week, New York, May 1983. New York, 1983.- C. 115-121 57. Meier A., Lorie R.A. A Surrogate Concept for Engineering Databases // Proc. 9th Int. Conf. Very Large Data Bases, Florence, Italy, Oct. 1983. New York, 1983.- C. 30-32 58. Lorie R.A., Plouffe W. Relational Databases for Engineering Data // Proc. 2nd Int. Conf. Found. Comput. Aided Process Des., New York, Aug. 1983.


New York, 1983.- C. 132-139 59. Kim W., Lorie R., McNabb D., Plouffe W. A Transaction Mechanism for Engineering Design Databases // Proc. 10th Int. Conf. Very Large Data Bases, Singapore, Aug. 27-31, 1984. New York, 1984.- C. 355-362 60. Hallmark G., Lorie R.A. Towards VLSI Design Systems Using Relational Databases // Proc. IEEE Spring Comput. Conf., San Francisco, Calif., Febr. 1984. New York, 1984.- C. 326-329 61. Lorie R.A., Kim W., McNabb D., Plouffe W., Meier A. Supporting Complex Objects in a Relational System for Engineering Databases // Query Processing in Database Systems. New York e.a.: Springer.- 1985.- C. 145-155 62. Katz R.H. Information Management for Engineering Design.- New York e.a.: Springer.- 1985.- 423 c. 63. Bancilhon F., Kim W., Korth H. A Model of CAD Transactions // Proc. 11th Int. Conf. Very Large Data Bases, Stockholm, Sweden, Aug. 1985. Palo Alto, Calif., 1985.- C. 25-33 64. Batory D., Kim W. Modelling Concepts for VLSI CAD Objects // ACM Trans. Database Syst.- 1985.- 10, N 3.- 1985.C. 322-346 65. Lorie A., Daudenarde J.-J.P. On Extending the Realm of Application of Relational Systems // Inf. Process., 86. Proc. IFIP 10th World Comput. Congr., Dublin, Sept. 1-5, 1986. Amsterdam e.a., 1986.- C. 889-899. 66. Dittrich K.R., Lorie R.A. Version Support for Engineering Database Systems // IEEE Trans. Software Eng.1988.- 14, N 4.- C. 429-437 67. Chou H.-T., Kim W. A Unifying Framework for Version Control in a CAD Environment // Proc. 12th Int. Conf. Very Large Data Bases, Kyoto, Japan, Aug. 1986. Palo Alto, Calif., 1986.- C. 336-344 68. W.Kim, Chou H.-T., Banerjee J. Operations and Implementation of Complex Objects // IEEE Trans. Software Eng.- 1988.- 14, N 7.- C. 985-996 69. Bayer R., McGreight E. Organization and Maintenance of Large Ordered Indeces // Acta Inf.- 1972.- 1.- C. 173-189 70. Кнут Д. Искусство программирования. Т.3. Сортировка и поиск.- М.: Наука.- 1978.- 844 c. 71. Bayer R. Integrity, Concurrency, and Recovery in Databases // Lect.Not. Comput. Sci.- 1976.- 44.- C. 284-291 72. Stonebraker M.R., Wong E., Kreps P., Held G. The Design and Implementation of INGRES // ACM Trans. Database Syst.- 1976.- 1, N 3.- C. 189-222 73. Zloof M.M. Query By Example: A Data Base Language // IBM Syst. J.- 1977.- 16, N 4.- C. 324-343 74. Stonebraker M., Neuhold E. A Distributed Data Base Version of INGRES // Proc. 2nd Berkley Workshop Distrib. Data Manag. and Comput. Networks, Berkley, Calif., May 1977. Berkeley, Calif., 1977.- C. 19-36 75. Кузнецов С.Д. Методы оптимизации выполнения запросов в реляционных СУБД. В этом сборнике. | |

Оптимизация в System R

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

Вообще с оптимизацией в реляционных системах связан очень широкий спектр проблем, которые мы более последовательно и полно рассмотриваем в отдельной статье [75]. Здесь же мы коротко рассмотрим особенности оптимизации в System R.

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

При выполнении запроса на выборку из одного отношения концептуально необходимо просмотреть все кортежи указанного в запросе отношения и выбрать из них те, содержимое полей которых удовлетворяет условиям выборки. Возможны два способа выполнения такого просмотра: последовательное сканирование всего отношения или его сканирование через один из определенных на этом отношении индексов. Соответственно, среди кандидатов на оптимальный способ выполнения такого запроса потенциально находятся способ последовательного сканирования и набор способов сканирования на основе всех существующих индексов.
Упоминается еще один способ выполнения запроса на выборку, в котором условие выборки представляет собой логическое выражение, состоящее из простых предикатов сравнения (типа "имя-поля операция-сравнения константа") и включающее только те поля, для которых существуют индексы. Способ состоит в том, что в соответствии с заданными простыми предикатами из индексов выбираются списки tid'ов кортежей, удовлетворяющих предикатам, а затем над этими списками выполняются теоретико-множественные операции объединения и пересечения (объединение соответствует логической операции "или" в логическом условии выборки, пересечение - "и"). Реальная выборка результирующих кортежей производится по произведенному таким образом окончательному списку tid'ов. Здесь следует заметить, что в System R принято довольно простое решение по поводу выполнения запросов со вложенными подзапросами: они выполняются именно так, как указано в исходном запросе, т.е. до того, как выполняется внешний запрос, формируются результаты всех его вложенных подзапросов и т.д. В принципе это является упрощением; имеются работы, показывающие, что можно преобразовать запрос, содержащий вложенные подзапросы, к одноуровневому запросу, содержащему соединения отношений. При этом запрос в преобразованной форме допускает более эффективное выполнение. В System R оптимизационные преобразования этого типа не употребляются, и это, конечно, является ограничением этой системы. Справедливости ради заметим, что публикации, связанные с преобразованием запросов со вложенностями, появились позже основной части публикаций по System R. Тем не менее, с использованием SQL можно явно формулировать запросы на выборку, содержащие предикаты соединения. Тривиальный способ выполнения таких запросов на основе формирования прямого произведения отношений с последующим выделением кортежей, удовлетворяющих условию выборки не рассматривается в числе кандидатов. Для выполнения (экви)соединения двух отношений R и S употребляются четыре следующих способа:


1) Если для отношений R и S определены индексы на полях, по которым происходит соединение, эти индексы последовательно сканируются, пока не будет обнаружена пара tid'ов с общим значением ключа. После этого выбирается соответствующий кортеж, например, из отношения R, и производится его проверка на удовлетворение предикату ограничения на кортежи отношения R из условия выборки. (Если этот кортеж не удовлетворяет предикату ограничения, продолжается параллельное сканирование индексов, начиная с индекса на R.) Затем продолжается сканирование индекса на отношении S, выбираются все кортежи с тем же значением ключа, и те из них, которые удовлетворяют предикату ограничения на S из условия выборки, помещаются во временную память. Путем сканирования индекса на отношении R поочередно выбираются кортежи этого отношения с тем же значением ключа. Каждый такой кортеж, удовлетворяющий предикату ограничения на R, соединяется со всеми кортежами из S, находящимися во временной памяти , образуя очередную часть результирующего отношения. Далее продолжается параллельное сканирование индексов на R и S с целью подбора очередной пары. Временная память должна иметь размер, достаточный для хранения максимального числа кортежей отношения S, которые могут соединиться с одним кортежем отношения R. 2) Любым способом сканируются отношения R и S, и образуются два файла W1 и W2. При этом файл W1 (W2) содержит все кортежи R (S), удовлетворяющие предикату ограничения на кортежи отношения R (S) из условия выборки. Далее файлы W1 и W2 сортируются в соответствии со значениями полей соединения, после чего в процессе их параллельного сканирования производится соединение (это напоминает сортировку со слияниями). Напомним, что в интерфейсе RSS предусмотрены соответствующие операции. 3) Любым способом сканируется отношение S, и поочередно выбираются кортежи. Если очередной кортеж s удовлетворяет предикату ограничения на кортежи S из условия выборки, то этот кортеж заносится в область основной памяти V2, если в ней еще есть место.


Если в V2 места уже нет, и значение поля соединения кортежа s меньше значения поля кортежа, находящегося в V2, с наибольшим значением поля соединения, то все кортежи с таким значением поля соединения удаляются из V2, а s - заносится. В противном случае s не заносится в V2. После окончания формирования V2 (завершения сканирования S) сканируется отношение R, и поочередно выбираются кортежи. Если очередной кортеж r удовлетворяет предикату ограничения из условия выборки, V2 просматиривается на предмет наличия кортежей с таким же, как у r, значением полей соединения. Если такие кортежи находятся, производится соединение кортежа r с каждым из них, и формируется очередная порция результирующего отношения. Если при формировании V2 не все кортежи отношения S, удовлетворяющие предикату ограничения, поместились в эту область, производится повторное сканирование отношения S, и формируется новое множество V2, в которое включатся только кортежи со значением полей соединения большим максимального значения поля соединения кортежей в предыдущем варианте V2. Снова сканируется R, и процесс повторяется. Для организации структуры V2 можно использовать двоичные деревья, хэш-таблицы и т.д. 4) Если существуют индексы для отношений R и S на полях соединения и для всех предикатов ограничения, то с использованием индексов ограничения формируются два списка tid'ов кортежей отношений R и S, удовлетворяющих предикатам ограничения. Эти два списка сортируются и заносятся в файлы R1 и S1. Путем параллельного просмотра индексов на полях соединения R и S находятся пары tid'ов кортежей, являющихся участниками соединения (без учета ограничений). Для каждой такой пары (tid1, tid2) проверяется, присутствуют ли tid1 в R1, а tid2 - в S1 (т.е. удовлетворяют ли кортежи предикатам ограничения). Если эти условия выполнены, соответствующие кортежи читаются и соединяются, образуя очередной кортеж результирующего отношения. Заметим, что в целях упрощения изложения мы не упомянули о том, что в методах 1-3 при выборке кортежа во временную память для сокращения ее объема производится проекция кортежей на те поля, которые упомянуты в списке выборки запроса, плюс поля соединения.


Случаи выполнения соединения двух отношений более сложного вида (не эквисоединений) не рассматриваются в литературе по System R. Упоминается лишь, что для их выполнения применяются методы более сложные, но похожие на те, которые используются для выполнения эквисоединения. Если в запросе участвуют несколько соединений, то рассматриваются только стратегии выполнения запроса на основе поочередного выполнения попарных соединений. При этом в плане выполнения запроса в качестве альтернатив рассматриваются все возможные порядки выполнения соединений. Из-за этого количество планов существенно возрастает, и тем самым увеличивается и время компиляции таких запросов. Итак, на основе заложенных в текущий вариант системы методов выполнения запросов формируется множество возможных планов выполнения данного запроса. Затем для каждого из этих планов оценочный компонент оптимизатора вычисляет стоимость его выполнения в контексте текущего состояния базы данных (вернее сказать, текущей статистической информации), и для выполнения запроса выбирается план с наименьшей стоимостью. Для оценки стоимости плана выполнения запроса в различных генерациях System R могут использоваться разные меры (в [19] рассматриваются оценки стоимости в денежной и временной мерах). В оценочных формулах фигурируют число обменов с внешней памятью, которые по оценкам оптимизатора потребуются при выполнении запроса по данному плану, и оценка процессорного времени, требующегося для выполнения запроса (при этом время оценивается предполагаемым числом обращений к RSS при выполнении запроса по данному плану). Число обменов и число обращений к RSS, встречающиеся в оценочных формулах, подгоняются под единую меру за счет использования соответствующих коэффициентов. Числовые значения коэффициентов зависят от выбранной меры стоимости. Например, если мерой выступает время выполнения запроса, то определяющей составляющей стоимости должно быть число обменов; при выборе денежной меры больший вес должно иметь время процессора.


При оценках числа требуемых обменов наличие буфера страниц в оперативной памяти почти не учитывается. Например,считается, что при последовательном сканировании отношения будет произведено число обменов, равное максимуму числа страниц в сегменте и числа кортежей в отношении (эта оценка может быть, конечно, завышенной). Возможности буферизации учитываются только при использовании кластеризованных индексов. При сканировании отношении через кластеризованный индекс число требуемых при этом обменов оценивается числом страниц, занимаемых кортежами отношения. Вообще говоря, эта оценка может быть заниженной, т.к. в ней не учитываются возможности замещения текущей страницы сканирования в буфере по причине параллельного выполнения нескольких транзакций. С другой стороны, при правильной балансировке загрузки системы и размера буферного пула оценка будет правильной. Набор оценочных формул, применяемых в оптимизаторе System R, описан в [19]. Наиболее слабым местом оптимизатора System R являются эвристики, позволяющие оценить число кортежей отношения при известном диапазоне значений его поля. При таких оценках оптимизатор исходит из двух базовых предположений, которые далеко не всегда удовлетворяются на практике: 1) предполагается, что значения всех полей любого отношения распределены независимо; 2) предполагается, что значения любого поля любого отношения распределены равномерно. Если эти предположения оправданы, то упомянутые оценки можно достаточно точно производить по простой статистической информации: достаточно знать статистические оценки числа кортежей в отношении и числа различных значений ключа в каждом индексе. Так и поступает оптимизатор System R. Для того, чтобы избежать накладных расходов на обновление статистики при выполнении каждой операции занесения, удаления или модификации кортежей, статистика собирается и обновляется только в ходе выполнения специальной утилиты сбора статистики. В заключение заметим, что в настоящее время существует ряд работ, авторы которых пытаются решить проблему более точных оценок, используя достаточно простую статистику.Мы остановимся на этом в отдельной статье [75]. | |

Организация сложных объектов в XSQL

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

В начале работ по развитию System R в направлении инженерных приложений в них активно участвовал известный специалист в области реляционных систем баз данных В.Ким (который в дальнейшем перешел в MCC и в настоящее время, видимо, отошел от этих работ). Мы подчеркиваем этот факт по той причине, что, пожалуй, лучшей публикацией о сложных объектах в System R является [61], список авторов которой он возглавляет.

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

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

В принципе, такая организация уже дает возможность эффективно управлять сложными объектами, поскольку необходимые соединения нескольких отношений становятся ненакладными. Но при этом семантика сложного объекта остается неизвестной системе. В частности, необходимо отдельно от описания структуры объекта указывать необходимые условия целостности, и невозможно автоматически проверить их достаточность.
Второй деффект такого подхода мы уже отмечали - избыточность и неудобство работы на прикладном уровне с плоскими представлениями выбранных в оперативную память объектов. Напрашивается решение ввести структуру сложного объекта на уровне хранения. Физические возможности для организации ссылок между кортежами обеспечиваются уровнем управления памятью System R - каждый кортеж получает на время своего существования уникальный идентификатор (tid), по которому возможен прямой доступ к кортежу. Но такое решение повлекло бы два следствия. Во-первых, нужно было бы переделывать подсистему управления памятью, перегружая ее информацией, по сути дела, логического уровня. Во-вторых, наличие между кортежами физических ссылок вызвало бы усложнение операции копирования сложного объекта как единого целого. Подход, выбранный в XSQL, решает проблемы управления сложными объектами на логическом уровне СУБД с использованием средств кластеризации отношений, предоставляемых физическим уровнем (сам физический уровень, т.е. RSS, при этом не меняется по сравнению с System R). Все отношения, кортежи которых входят в сложный объект, расширяются одним полем - суррогатом или логическим идентификатором кортежа. Ссылки между кортежами сложного объекта - это тоже явно указанные поля отношений на физическом уровне, и значения ссылок есть суррогаты кортежей. Структура сложного объекта (а тем самым и правила кластеризации составляющих его отношений и условия целостности сложного объекта) описывается на расширенном SQL. Конструкции расширенного SQL, предназначенные для определения структуры сложного объекта, довольно громоздки, и формальное описание синтаксиса языка в публикациях не приводится. Отношение, кортежи которого являются корнями иерархий сложных объектов, расширяется еще одним большим по объему полем, которое содержит таблицу приписки суррогатов кортежей, составляющих данный сложный объект, к их физическим идентификаторам. Таким образом, для того, чтобы полностью выбрать сложный объект (или его указанный подобъект) достаточно найти каким-либо образом его корневой кортеж и пройти по ссылкам.


Кластеризация кортежей сложного объекта делает эту операцию эффективной. Заметим по этому поводу, что хотя при реализации прототипа XSQL использовался тот же вариант RSS, что и в System R (точнее, в SQL/DS), в этой реализации используются возможности RSS по части совместной кластеризации кортежей нескольких отношений (в описанном в Разделе 2 интерфейсе RSS мы не упоминали эту возможность, поскольку она не использовалась в System R). Возможны два пути указания подобъектов сложного объекта. Если наиболее важным фактором является эффективность выборки, то общие подобъекты нескольких сложных объектов физически копируются. Это не создает проблем с их физической согласованностью, потому что на уровне SQL модификация отношений происходит в соответствии с условием модификации и потому просто невозможно выполнить модификацию только одной копии кортежа (различающие их суррогаты не видны на уровне SQL). Но, конечно, при такой организации операция модификации может стать дорогостоящей. Второй допустимый способ - физическое разделение общего подобъекта несколькими объектами. В этом случае ссылка становится несколько более сложной, но сохраняется логической. При таком способе организации, вообще говоря, теряется эффективность выборки, но модификации дешевы. Наличие логических ссылок и таблицы приписки позволяет после выборки сложного объекта в основную память образовать обычную списковую структуру, заменив логические ссылки в кортежах на указатели по оперативной памяти. Такая структура сложного объекта в оперативной памяти очень удобна для последующей обработки на прикладном уровне. Наличие таблицы приписки, устанавливающей соответствие логических идентификаторов кортежей с их tid'ами, позволяет легко реализовать операцию копирования сложного объекта. При этом нужно модифицировать только одно поле (содержащее таблицу приписки) корневого кортежа объекта. Появление новой управляющей структуры - таблицы приписки сложного объекта добавляет возможности при выборе способа пути доступа в оптимизаторе СУБД.Как подчеркивается в [61], бывает полезно использовать таблицу приписки (своего рода индекс) не только при выборке сложных объектов. Диалект SQL, используемый в XSQL, содержит несколько расширений, относящихся в средствам выборки. Все они, естественно, отражают специфику работы со сложными объектами и составляющими их кортежами. Вообще говоря, язык в результате в некоторой степени утратил свою простоту, но зато достаточно сложные запросы можно формулировать лаконично. Соответствующим образом расширены и операторы занесения, удаления и модификации кортежей, входящих в сложные объекты. | |

Организация System R

Как отмечалось во введении, по поводу организации СУБД System R существует обширная библиография [1-27]. Хотя официально разработка этой системы началась в 1975 г., первые публикации, связанные с этой системой, появились еще в 1974 г. В частности, именно в [1] была предложена основа базового языка System R SQL (тогда этот язык назывался SEQUEL, и до сих пор многие называют его именно так; кстати, разработчики System R рекомендуют произносить название SQL именно как SEQUEL). Поскольку публикации появлялись по ходу практической реализации системы, каждая из них отражает состояние дел (идейное и практическое) именно на том этапе работы, когда была написана соответствующая статья. Некоторые идеи и представления, естественно, изменялись по ходу работы. Сравнительно законченное представление о системе в целом дают только заключительные публикации [25-27]. С другой стороны, многие интересные моменты совершенно не отражены в этих последних статьях, и мы постараемся привести более полный обзор идей и методов, примененных в System R. При этом мы будем останавливаться и на некоторых возможных альтернативных решениях, которые были найдены разработчиками System R, но практически не были использованы.

| |

Организация внешней памяти в базах данных System R

В подразделе 1.1 мы отмечали, что база данных System R располагается в одном или более сегментов внешней памяти. Каждый сегмент состоит из страниц данных и страниц индексной информации. Размер страницы данных в сегменте может быть выбран равным либо 4, либо 32 килобайт; размер страницы индексной информации равен 512 байт. Кроме того, при работе RSS поддерживается дополнительный набор данных для ведения журнала. Для повышения надежности журнала (а это наиболее критичная информация; при ее потере восстановление базы данных после сбоев невозможно) этот набор данных дублируется на двух внешних носителях.

В каждой странице данных хранятся кортежи одного или нескольких отношений. Фундаментальным понятием RSS является идентификатор кортежа (tuple identifier - tid). Гарантируется неизменяемость tid'а во все время существования кортежа в базе данных независимо от перемещений кортежа внутри страницы и даже при перемещении кортежа в другую страницу. Реально tid представляет собой пару <номер страницы, индекс описателя кортежа в странице>. При этом кортеж может реально располагаться в данной странице (Рис. 1) или в другой странице (Рис. 2). Во втором случае описатель кортежа содержит не координаты кортежа в данной странице, а tid, указывающий на реальное положение кортежа в другой странице. Легко видеть, что применение такого подхода позволяет ограничиться максимум одним уровнем косвенности.

Поскольку допускается нахождение в одной странице данных кортежей разных отношений, каждый кортеж должен кроме содержательной части включать служебную информацию, идентифицирующую отношение, которому принадлежит данный кортеж. Кроме того, в System R (точнее, в языке SQL) допускается динамическое добавление полей к существующим отношениям. При этом реально происходит лишь модификация описателя отношения в отношении-каталоге отношений. В существующем кортеже отношения новое поле возникает только при модификации этого кортежа, затрагивающей новое поле. Это позволяет избежать массовой перестройки хранимого отношения при добавлении к нему новых полей, но, естественно, требует хранения при кортеже дополнительной служебной информации, определяющей реальное число полей в данном кортеже. (Заметим, что удалять существующие поля существующего отношения в SQL и тем самым в System R не разрешается).
На основе наличия неизменяемых во время существования кортежей tid'ов в System R поддерживаются дополнительные управляющие структуры - индексы. Каждый индекс определен на одном или нескольких полях отношения, значения которых составляют его ключ, и позволяет производить прямой поиск по ключу кортежей (их tid'ов) и последовательное сканирование отношения по индексу, начиная с указанного ключа, в порядке возрастания или убывания значений ключа. Некоторые индексы при их создании могут обладать атрибутом уникальности. В таком индексе не допускаются дубликаты ключа. Это единственное средство SQL (и тем самым System R) указания системе первичного ключа отношения (фактически, набора первичного и всех альтернативных ключей отношения). Для организации индексов в System R применяется техника B-деревьев [69-70]. Каждый индекс занимает отдельный набор страниц, номер корневой страницы запоминается в описателе индекса. Использование B-деревьев позволяет достичь эффективности при прямом поиске, поскольку они в силу своей сильной ветвистости обладают небольшой глубиной. Кроме того, B-деревья сохраняют порядок ключей в листовых блоках иерархии, что позволяет производить последовательное сканирование отношения в порядке возрастания или убывания значений полей, на которых определен индекс. Фундаментальное свойство B-деревьев - автоматическая балансировка дерева допускает произведение лишь локальных модификаций индекса при переполнениях и опустошениях страниц индекса. (Мы достаточно вольно используем здесь термин B-дерево. На самом деле в System R используется модифицированный по сравнению с исходным вариант B-деревьев, который называют B*-, а иногда B+-деревьями). В самих B-деревьях System R ничего особенного нет; более подробно мы на этом останавливаться не будем. Отметим только, что System R, насколько нам известно, была первой системой, в которой для организации индексов использовались B-деревья. Эту традицию соблюдает большинство реляционных систем, возникших после System R. Видимо, наиболее важной особенностью физической организации баз данных в System R является возможность обеспечения кластеризации связанных кортежей одного или нескольких отношений.


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


В ранних версиях System R существовал еще один способ физического доступа к кортежам отношения и соответственно еще один способ указания условия кластеризации с использованием так называемых связей (links). На уровне физического представления связь представлялась в виде физической ссылки (tid'a) из одного кортежа на другой (не обязательно одного отношения). В языке SEQUEL (до того момента, когда его стали называть SQL) существовали средства определения связей в иерархической манере: можно было объявить некоторое отношение родительским по отношению к тому же или другому отношению-потомку. При этом указывались поля родительского отношения и отношения-потомка, в соотвествии со значениями которых образовывалась иерархия. Правила построения были очень простыми - проводились связи между кортежем родительского отношения ко всем кортежам отношения-потомка с теми же значениями полей связывания. На самом деле, все кортежи отношения-потомка с общим значением полей связывания связывались в кольцевой список, на который проводилась одна связь из соответствущего кортежа родительского отношения. Естественно, у отношения-родителя требовалась уникальность по отношению к значениям полей связывания. Для строгости следует заметить, что мы описали способ использования механизма связей, который поддерживался в ранних версиях SEQUEL [9]. В интерфейсе RSS System R этого периода допускалась возможность произвольного проведения связей без учета совпадения значений полей связывания. Тем самым, в системе в целом не использовались все возможности RSS, которые с избытком превосходили потребности организации иерархических бинарных связей по совпадению полей связывания. Для одного отношения допускалось создание многих связей: кортеж отношения мог быть родителем нескольких иерархий и входить в несколько других иерархий в качестве потомка. При этом одна связь могла быть объявленной кластеризованной. Тогда система стремилась поместить в одну страницу данных все кортежи одной иерархии. При этом, естественно, использовалась возможность размещения в одной странице данных кортежей нескольких отношений.


Основной смысл такой кластеризации заключался в возможности оптимизации выполнения некоторых запросов, включающих (экви)соединение двух связанных отношений в соответствии со значениями полей связывания. В более поздних публикациях по System R упоминания о механизме связей исчезли, из чего можно заключить, что разработчики отказались от его использования. Думается, что основными причинами отказа от использования связей были следующие: Во первых, средства построения связей, обеспечиваемые RSS, были очень низкого уровня, гораздо более низкого, чем средства поддержания индексов. Если при занесении кортежа RSS обеспечивала автоматическую коррекцию всех индексов, то для коррекции связей требовалось выполнить ряд дополнительных обращений к RSS, из-за чего время выполнения операции занесения кортежа, конечно, увеличивалось (то же касается операций удаления и модификации кортежа). Во-вторых, при реализации этого механизма, возникают дополнительные синхронизационные проблемы нижнего уровня (уровня совместного доступа к страницам данных). В частности, наличие прямых ссылок между страницами данных увеличивает верочтность возникновения синхронизационных тупиков. Наконец, в-третьих, все эти дополнительные накладные расходы не окупались предоставляемыми механизмом связей преимуществами. Действительно, максимального эффекта от использования связей можно достичь только при выполнении операции соединения двух кластеризованных по этой связи отношений, если поле соединения совпадает с полем связывания, и условия, накладываемые на родительское отношение, выделяют в нем ровно один кортеж. Очевидно, что такие запросы на практике редки. (Для точности отметим, что приведенные соображения принадлежат автору и не излагались в публикациях по System R, так что на самом деле причины могли быть и другими.) В Разделе 3 мы обсудим, как преломились идеи использования связей при организации иерархий в расширении System R для работы со сложными объектами. Заранее заметим, что в этом новом подходе активно используется идея совместной кластеризации кортежей нескольких отношений.


Кроме отношений и индексов при работе System R на внешней памяти могут располагаться еще и временные объекты - списки (lists). Список - это мгновенный снимок некоторой выборки с проекцией кортежей одного отношения, возможно, упорядоченный в соответствии со значениями некоторых полей. Средства работы со списками имеются в интерфейсе RSS, но их, естественно, нет в SQL. Cоотвественно, эти средства используются только внутри системы при выполнении запросов (в частности, один из наиболее эффективных алгоритмов выполнения соединений основан на использовании отсортированных списков кортежей). Публикации по System R не дают точного представления о структурах данных, используемых при организации списков, но исходя из здравого смысла можно предположить, что они устроены не так, как отношения (например, для кортежа, входящего в список, не требуется адресация через tid), и что располагаются они во временных файлах (в случае сбоя системы все временные объекты пропадают). | |

Основные цели System R и их связь с архитектурой системы

Как отмечается в [24], основными целями разработчиков Sysyem R являлись следующие:

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

2) обеспечить многообразие допустимых типов использования СУБД, включая программируемые транзакции, диалоговые транзакции и генерацию отчетов;

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

4) обеспечить возможность параллельной работы с одной базой данных многих пользователей с допущением параллельной модификации объектов базы данных при наличии необходимых средств защиты целостности базы данных;

5) обеспечить средства восстановления согласованного состояния баз данных после разного рода сбоев аппаратуры или программного обеспечения;

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

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

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

Основой System R является реляционный язык SQL. Иногда его называют языком запросов или языком манипулирования данными, но на самом деле его возможности гораздо шире. Средствами SQL (с соответствующей системной поддержкой) решаются многие из поставленных целей. Язык SQL включает средства динамической компиляции запросов, на основе чего возможно построение диалоговых систем обработки запросов. Допускается динамическая параметризация статически откомпилированных запросов, в результате чего возможно построение эффективных (не требующих динамической компиляции) диалоговых систем со стандартными наборами (параметризуемых) запросов.
Средствами SQL определяются все доступные пользователю объекты баз данных: таблицы, индексы, представления. Имеются средства уничтожения любого такого объекта. Соответствующие операторы языка могут выполняться в любой момент, и возможность выполнения операции данным пользователем зависит от ранее предоставленных ему прав. Что касается целостности баз данных, то в System R под целостным состоянием базы данных понимается состояние, удовлетворяющее набору ранее сформулированных предикатов целостности. Эти предикаты, называемые в System R условиями целостности (assertions), задаются также средствами языка SQL. Любое предложение языка выполняется в пределах некоторой транзакции неделимой с точки зрения состояния базы данных последовательности предложений языка. Неделимость понимается в том смысле, что все изменения, произведенные в пределах одной транзакции либо целиком отображаются в состоянии базы данных, либо полностью в нем отсутствуют. Последняя возможность возникает при откате транзакции, который может произойти по инициативе пользователя (при выполнении соответствующего оператора SQL) или по инициативе системы. Одной из причин отката транзакции по инициативе системы является как раз нарушение целостности базы данных в результате работы данной транзакции (другие возможные условия отката транзакции по инициативе системы мы рассмотрим позже). Язык SQL содержит средство установки так называемых точек сохранения (savepoint). При инициируемом пользователем откате транзакции можно указать номер точки сохранения, выше которого откат не распространяется. Инициируемый системой откат транзакции поизводится до ближайшей точки сохранения, в которой условие, вызвавшее откат, уже отсутствует. В частности, откат инициированный по причине нарушения условия целостности, производится до ближайшей точки сохранения, в которой условия целостности соблюдены. (Заметим, что средства установки точек сохранения отсутствуют в коммерческих расширениях System R). Естественно, что для реального выполнения отката транзакции необходима некоторая запомненная информация о прямом выполнении транзакции.


В System R для этих и других ( смотри ниже) целей используется специальный набор данных - журнал, в который помещаются записи обо всех меняющих состояние базы данных операциях всех транзакций. При откате транзакции происходит процесс обратного выполнения транзакции (undo), в ходе которого в обратном порядке выполняются все изменения, запомненные в журнале. В языке SQL имеется средство определения так называемых условных воздействий (triggers), позволяющих автоматически поддерживать целостность базы данных при модификациях ее объектов. Условное воздействие - это каталогизированная операция модификации, связанная с условием ее автоматического выполнения. Особенно существенно наличие такого аппарата в связи с наличием рассматриваемых ниже представлений базы данных, которыми может быть ограничен доступ к базе данных для ряда пользователей. Возможна ситуация, когда такие пользователи просто не могут соблюдать целостность базы данных без автоматического выполнения условных воздействий, поскольку они просто "не видят" всей базы данных и, в частности, не могут представить всех ограничений ее целостности. Для строгости заметим, что за исключением ранних публикаций по System R [8, 9] реализация механизма условных воздействий нигде не описывалась, хотя в принципе подходы к реализации достаточно понятны. Совершенно точно этот механизм не реализован в коммерческих системах, возникших на базе System R. Видимо, это связано с возникающими дополнительными непредсказуемыми для пользователей накладными расходами при выполнении транзакций. Язык SQL содержит средства определения представлений. В языке представление - это запомненный именованный запрос на выборку данных (из одной или нескольких таблиц). Поскольку SQL - это реляционный язык, то результатом выполнения любого запроса на выборку является таблица, и поэтому концептуально можно относиться к любому представлению как к таблице (при определении представления можно, в частности, присвоить имена полям этой таблицы). В языке допускается использование ранее определенных представлений практически везде, где допускается использование таблиц (с некоторыми ограничениями по поводу возможностей модификации через представления).


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


система ответственна за обеспечение изолированности пользователей с гарантией отсутствия их взаимного влияния в пределах транзакций. Из этого следует, во-первых, что в интерфейсе пользователя с системой (т.е. в языке SQL) не должно быть средств регулирования взаимодействий с другими пользователями и, во-вторых, что система должна обеспечить автоматическую сериализацию набора транзакций, т.е. обеспечить режим выполнения этого набора транзакций, эквивалентный по конечному результату некоторому последовательному выполнению этих транзакций. Эта проблема решается в System R за счет автоматического выполнения синхронизационных захватов по отношению ко всем измененяемым объектам базы данных. Имеется ряд тонкостей, связанных с такой синхронизацией, на которых мы остановимся в подразделе 1.5. Одним из основных требований к СУБД вообще и System R в частности является обеспечение надежности баз данных по отношению к различного рода сбоям. К таким сбоям могут относиться программные ошибки прикладного и системного уровня, сбои процессора, поломки внешних носителей и т.д. В частности, к одному из видов сбоев можно отнести упоминавшиеся выше нарушения целостности базы данных, и автоматический инициируемый системой откат транзакции - это системное средство восстановления базы данных после сбоев такого рода. Как мы отмечали, такое восстановление происходит путем обратного выполнения транзакции на основе информации о проведенных ею изменениях, запомненной в журнале. На информации журнала основано восстановление базы данных и после сбоев другого рода. Управление журнализацией и восстановлением в System R весьма интересно, применяемые методы в ряде случаев отличаются от методов, используемых в других СУБД, и мы более подробно рассмотрим этот вопрос в подразделе 1.6. Что касается естественных требований к эффективности системы, то здесь основные решения связаны со спецификой физической организации баз данных на внешней памяти, буферизацией используемых страниц базы данных в оперативной памяти и развитой техникой оптимизации запросов, сформулированных на SQL, производимой на стадии их компиляции.


Конечно, аспект эффективности системы относится к числу наиболее важных, и мы более основательно рассмотрим соответствующие вопросы в следующих подразделах. Структурная организация System R вполне согласуется с поставленными при ее разработке целями и выбранными решениями. Основными структурными компонентами System R являются система управления реляционной памятью (Relational Storage System RSS) и компилятор запросов языка SQL. RSS обеспечивает интерфейс достаточно низкого, но достаточного для реализации SQL, уровня для доступа к хранимым в базе данным. Синхронизация транзакций, журнализация изменений и восстановление баз данных после сбоев также относятся к числу функций RSS. Компилятор запросов использует интерфейс RSS для доступа к разнообразной справочной информации (каталоги отношений, индексов, прав доступа, условий целостности, условных воздействий и т.д.) и производит рабочие программы, выполняемые в дальнейшем также с использованием интерфейса RSS. Таким образом, система естественно разделяется на два уровня - уровень управления памятью и синхронизацией, фактически, не зависящий от базового языка запросов системы, и языковой уровень (уровень SQL), на котором решается большинство проблем System R. Для точности заметим, что эта независимость скорее условная, чем абсолютная: язык SQL можно заменить на другой язык, но он должен обладать примерно такой же семантикой. Далее мы последовательно рассмотрим особенности организации RSS, процесс компиляции и оптимизации запросов и технику выполнения откомпилированных транзакций (включая отмеченную выше возможность динамической компиляции запросов). | |

Особенности оптимизации запросов в System R*

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

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

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

Основной функцией оптимизации запроса первого уровня стадии выработки глобального плана выполнения запроса является выбор порядка выполнения соединения отношений, находящихся в разных узлах сети, способа выполнения соединения каждых двух таких отношений и узла, в котором должно находиться результирующее отношение. (Как и в System R, выполнение запроса, включающего n соединений отношений, всегда производится как n-1 попарное соединение).
Кортежи внешнего отношения, удовлетворяющие локальному предикату ограничения, также посылаются в узел P, где и выполняется их соединение с кортежами временного отношения. * Удовлетворяющие локальному предикату ограничения кортежи внешнего отношения посылаются в третий узел P, и для каждого из этих кортежей посылается запрос в узел N на выборку кортежей, имеющих соответствующие значения поля (полей) соединения. Эти порции кортежей передаются в узел P, где и выполняется соединение. При выполнении соединения любым из перечисленных способов возможно достижение параллелизма и конвееризации. Чтение кортежей внутреннего и внешнего отношений может производиться параллельно. Во время выполнения соединения в узле N кортежей внутреннего отношения с переданным кортежем внешнего отношения может производиться чтение и передача следующего кортежа внешнего отношения. Однако заметим, что в System R* возможностям распараллеливания выполнения запросов уделяется меньшее внимание, чем, например, в распределенном варианте известной системы баз данных INGRES [74]. Приведенные в [41] способы выполнения соединения удаленных отношений не исчерпывают все возможные способы. В последних публикациях (например, [51]) приводятся другие возможные способы выполнения соединений, основанные на более тонких методах. Появление новых предложений в [51] естественно, поскольку работа авторов [50-51] связаны с изучением поведения системы в реальных условиях потока запросов. В рассматриваемый ими вариант System R* были внедрены средства, позволяющие количественно оценить эффекты, достигнутые в ходе оптимизации запроса, и сравнить их с возможными альтернативными вариантами. Очень ценно, что упомянутые средства доступны, фактически, на уровне пользователя; в SQL были добавлены соответствующие предложения. В [51] приведены интересные экспериментальные данные, на основе которых можно подвергать конструктивной критике употребляемые методы и предлагать их усовершенствования. Эта работа кажется очень полезной, если иметь в виду перспективы выпуска на базе System R* коммерческого продукта. | |

Распределенная компиляция запросов

Как мы уже отмечали, запросы на языке SQL до своего реального выполнения подвергаются компиляции. Как и в случае System R компиляция запроса может производиться на стадии прекомпиляции прикладной программы, написанной на традиционном языке программирования (PL/1, Cobol, ассемблер) с включением предложений SQL, или в динамике выполнения транзакции при выполнении предложения PREPARE. С точки зрения пользователей процесс компиляции в System R* приводит к тем же результатам, что и в System R: для каждого предложения SQL образуется программа к машинных кодах (секция модуля доступа), вызовы которой помещаются в текст исходной прикладной программы.

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

Следуя [41], будем называть главным узлом тот узел сети, в котором инициирован процесс компиляции предложения SQL, и дополнительными узлами - те узлы, которые вовлекаются в этот процесс в ходе его выполнения. На самом грубом уровне процесс компиляции можно разбить на следующие фазы:

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

2. В главном узле генерируется глобальный план выполнения запроса, в котором учитывается лишь порядок взаимодействий узлов при реальном выполнении запроса. Для выработки глобального плана используется расширение техники оптимизации, применяемой в System R.
На этом вопросе мы остановимся более подробно в следующем подразделе. Глобальный план отображается в преобразованном соответствующим образом дереве запроса. 3. Если в глобальном плане выполнения запроса участвуют дополнительные узлы, производится его декомпозиция на части, каждую из которых можно выполнить в одном узле (например, локальная фильтрация отношения в соответствии с заданным в условии выборки предикате ограничения). Соответствующие части запроса (во внутреннем представлении) рассылаются в дополнительные узлы. 4. В каждом узле, участвующем в глобальном плане выполнения запроса (главном и дополнительных) выполняется завершающая стадия выполнения компиляции. Эта стадия включает, по существу, две последние фазы процесса компиляции запроса в System R: оптимизацию и генерацию машинных кодов. Производится проверка прав пользователя, от имени которого производится компиляция, на выполнение соответствующих действий; происходит обработка представлений базы данных (здесь имеются тонкости, связанные с тем, что представления могут включать удаленные отношения; ниже мы еще остановимся на этом, а пока будем считать, что в запросе употребляются только имена базовых отношений); осуществляется локальная оптимизация обрабатываемой части запроса в соответствии с имеющимися индексами; наконец, производится генерация кода. В отличие от секций модуля доступа System R, которые включали только индивидуальный код и обращения к RSS, образовывающиеся при компиляции запроса в System R* программные единицы (подсекции) включают еще и обращения к сетевому компоненту системы для необходимых транспортных взаимодействий. Каждая подсекция помещается в локальный каталог базы данных соответствующего узла, в который, кроме того, заносится информация, характеризующая зависимость корректности программного кода от состояния локальных объектов (например, индексов). Это необходимо в соответствии с требованием локальной автономии узлов. Должно быть возможно произвести некоторые локальные действия (например, уничтожить индекс) без оповещения об этом удаленных узлов.


При выбранной в System R* схеме такое действие приведет к объвлению некорректными всех локальных подсекций модулей доступа, в которых использовался данный индекс. При попытке использования подсекции ее некорректность будет обнаружена, и последует перекомпиляция запроса без какого-либо взаимодействия с другими узлами. Как и в System R, компиляция запросов в System R* производится в пределах некоторой служебной транзакции. Как и вообще в распределенных системах баз данных, управление транзакциями в System R* существенно сложнее, чем в System R. Более подробно мы рассмотрим этот вопрос ниже, а пока заметим, что наиболее важная проблема связана с завершением распределенных транзакций, поскольку изменения, произведенные в распределенной базе данных операциями данной транзакции, должны быть либо зафиксированы во всех участвующих в выполнении транзакции узлах, либо должны полностью отсутствовать. Для достижения этой цели в System R*, как и в большинстве распределенных систем управления базами данных, употребляется двухфазный протокол завершения транзакции. В соответствии с этим протоколом при завершении транзакции все ее участники сначала оповещаются инициатором транзакции о намерении ее завершить, и только затем, в случае, если все участники выразили на это согласие (зафиксировали свои изменения), происходит реальное завершение транзакции со снятием синхронизационных захватов. Так обстоит дело и при завершении транзакции, в рамках которой производилась компиляция запросов (это может быть служебная транзакция, инициированная прекомпилятором, или обычная пользовательская транзакция, в которой выполняется предложение SQL PREPARE) по отношению к произведенным в различных узлах сети подсекциям модуля доступа. Рассмотрим теперь особенности процесса компиляции в System R* запросов, в которых участвуют представления. Как мы уже отмечали, особенностью представлений, допустимых в System R*, является то, что они могут быть определены на отношениях, распределенных в сети. Исходя из того, что одним из предназначений представлений является защита некоторых атрибутов отношений от несанкционированного использования, в компиляторе System R* нельзя было использовать технику слияния дерева запроса с деревьями представлений, поскольку при этом терялась привязка представления к тому узлу, на котором оно было создано.


Из-за этого в некоторых узлах сети могли появиться данные, которые не должны быть видимы в этих узлах по условиям авторизации, т.е. защита могла бы быть нарушена. Поэтому обнаружение того, что отношение является не базовым, а представлением, в System R* производится только в дополнительном узле - владельце представления. В нем и производится слияние поддерева запроса, переданного в дополнительный узел для окончательной обработки, с деревьями представлений. Но в результате этого слияния может образоваться дерево, не все объекты которого являются локальными для этого узла. Если действительно возникает такая ситуация, то дополнительный узел начинает действовать как главный по отношению к выработанному дереву запросу, т.е. в нем вырабатывается глобальный план выполнения части запроса, производится его декомпозиция, и части подзапроса рассылаются в дополнительные узлы. Из публикаций не очень ясно, что будет, если представление определяется не на базовых отношениях, а на представлениях: происходит ли их раскрытие при обработке предложения DEFINE VIEW или откладывается до реального выполнения запроса на представлении верхнего уровня. Мы склоняемся к тому, что разумнее было бы использовать первый подход, но неясно, согласуется ли это с требованиями защиты. Во любом случае способ обработки запросов на представлениях, применяемый в System R*, обеспечивает меньшие возможности оптимизации выполнения таких запросов по сравнению с подхо- дом System R, поскольку при выработке плана выполнения запроса на стадии его компиляции в главном узле в общем случае учитываются не все возможные соединения, которые потребуются при выполнении запроса (некоторые из них могут быть скрыты в представлении). Поэтому в конечном распределенном плане порядок выполнения соединения может оказаться неоптимальным. В публикациях по System R* не отражен вопрос, касающийся поддержки глобальной целостности баз данных. Из общих соображений должно быть разрешено определять условия целостности и условные воздействия, касающиеся удаленных отношений, но в каких узлах нужно проверять условия целостности и выполнять условные воздействия исходя из тех же соображений защиты данных - неясно.Похоже, что этот вопрос не решен в имеющихся реализациях System R*. Здесь особенно трудно выдержать разумный компромисс между базовым требованием максимальной автономности локальных баз данных и желанием обеспечить глобальную автоматическую поддержку целостности распределенной базы данных. | |

Распределенная система управления базами данных System R*

В 1979 г. сотрудники научно-исследовательской лаборатории фирмы IBM в Сан-Хосе приступили к разработке на основе практически завершенного к этому времени проекта System R распределенной системы управления базами данных System R*. Как отмечается в [53], проект был завершен к 1984 г., но это, видимо, означает лишь то, что к этому времени появился реально функционирующий прототип системы, поскольку публикации по System R* продолжают активно появляться до сих пор (например, [50-52]), и эти публикации носят далеко не обзорный характер, а посвящаются проблемам, решаемым в настоящее время, т.е. не решенным ранее.

Незавершенность работы следует еще и из того, что до сих пор фирма IBM не выпустила ни одного коммерчески доступного продукта, основанного на System R*, в отличие от того, что сразу после завершения проекта System R появился коммерческий фирменный продукт SQL/DS. Более того, подчеркивая экспериментальный характер проекта, в [49] авторы отмечают, что как принято в IBM, разработчики System R* не гарантируют появление каких-либо функций этой системы в коммерческих программных продуктах.

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

В System R* используется мощное средство сетевого взаимодействия CICS/ISC; в публикациях практически не встречается рассмотрение особенностей транспортного сетевого взаимодействия, и мы в этой статье также не будем касаться этих вопросов. Заметим лишь, что CICS/ISC обеспечивает надежную передачу сообщений между узлами сети, скрывая особенности среды передачи. Поэтому System R* может функционировать и в высокоскоростных локальных сетях, и в более медленных территориально распределенных сетях. Как отмечается в [51], скоростные оценки среды передачи учитываются в оценочных формулах оптимизатора.

| |

Расширение модели транзакции в XSQL

Как мы отмечали выше, приложения САПР нуждаются, кроме средств организации сложных объектов, в расширении и пересмотре понятия транзакции. В.Ким с разными соавторами в [63] предлагал ввести целую иерархию понятий транзакций со своими правилами согласованности и протоколами на каждом уровне, а в [67] предлагалась очень общая модель версий объектов в базах данных САПР. Вообще, последние работы этого автора отличаются слишком большим уровнем общности. Все эти работы содержат интересные предложения, но они настолько далеки от реализации (а гипотетическая реализация их настолько сложна), что практически работы становятся неинтересны. Видимо в этом и разошелся В.Ким с разработчиками XSQL, которые, начиная еще с System R, всегда отличались стремлением к простоте.

Для точности отметим, что в [68] В.Ким возвращается к практическим вопросам реализации систем управления базами данных для САПР. В этой статье утверждается, что основным отличием проводимой им (и другими разработчиками MCC) работы от XSQL является то, что разработчики из Сан-Хосе черезчур заботятся о сохранении неизменной подсистемы управления памятью RSS (на наш взгляд это вполне естественно: прежде, чем менять хорошо зарекомендовавший себя продукт, нужно по крайней мере убедиться в том, что его средства недостаточны).

По этому поводу интересно рассмотреть решение проблемы с длинными "инженерными" транзакциями в XSQL [65]. Управление транзакциями основано на одновременой работе с общей базой данных и набором частных баз данных (последние могут, но не обязаны, располагаться на рабочих станциях). Перед доступом к объекту он должен быть явно перемещен в частную базу данных, и об этом производится запись в специальном управляющем отношении, хранящемся в общей базе данных (делается долговременный захват).

Работа с общей базой данных происходит в терминах традиционных "коротких" транзакций, но конец такой транзакции не приводит к автоматическому снятию долговременных захватов, появившихся при работе этой транзакции.
Для обновления объекта в общей базе данных требуется наличие соответствующего долговременного захвата (что в общем случае может потребовать переговоров пректировщиков, одновременно работающих с данным объектом). Долговременные захваты снимаются либо по явной команде, либо при сбросе объекта в общую базу данных. Заметим, что XSQL обеспечивает работу лишь с общей базой данных. Программное обеспечение частных баз данных может быть очень различно (например, тоже с использованием XSQL или на основе прикладных систем). Главное - это соблюдение правил работы с общей базой данных, а это XSQL гарантирует. Имеется четкое разделение функций между логическим уровнем XSQL и RSS. Как и в System R, обеспечение синхронизации операций параллельно выполняемых коротких транзакций относится к числу функций RSS. Наличие длинных транзакций вообще неизвестно RSS. Управление ими (впрочем, как видно из изложенного выше, очень простое) осуществляется на логическом уровне RSS. Трудно сказать, является ли достаточным для инженерных разработок механизм управления транзакциями, реализованный в XSQL. Видимо, об этом можно судить только на основе опыта. В доступных публикациях такой анализ пока не проводился. Но по крайней мере одно преимущество реализации механизма длинных транзакций в XSQL очевидно - это простота и ненакладность (о чем, кстати, можно судить, исходя из небольшого объема данного подраздела, в котором содержится вся существенная информация). | |

Развитие System R для использования в нетрадиционных приложениях

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

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

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

1. Существует возможность описывать сложные объекты за счет включения в отношения атрибутов соединений. Более того, можно извлечь из базы данных сложный объект (или его представление) за один запрос, но этот запрос при традиционной организации базы данных потребует выполнения нескольких операций соединения и не сможет быть выполнен с требуемой для САПР эффективностью. Кроме того, плоская форма сложного объекта, которую можно получить за счет реляционного запроса, не очень-то удобна для последующей обработки в оперативной памяти.
2. Существует возможность взаимодействовать с базой данных в пределах транзакции, которая является атомарной единицей изменения базы данных и результаты работы которой либо полностью отображаются в состоянии базы данных, либо полностью отсутствуют. Система баз данных гарантирует нормальный конец транзакции только в том случае, если транзакция не нарушила логическую целостность базы данных, причем критерии логической целостности достаточно жестки. Такой механизм транзакций и соответствующей синхронизации непригоден для САПР, критерии логической целостности баз данных которых изменчивы, и даже в соответствии с этими критериями базы данных могут долго находиться в нецелостных состояниях. 3. Система управления базами данных поддерживает информацию о предшествующих состояниях баз данных в форме журналов изменений. Журнал используются системой при восстановлениях баз данных после сбоев процессора или поломок внешних носителей, но пользователи не имеют возможности явного доступа к накопленной в журнале информациии. САПР нуждаются в таких возможностях. Более точно, САПР требуются средства доступа к предыдущим состояниям объектов базы данных. Резюмируя отмеченные несогласованности между возможностями реляционных систем управления базами данных и потребностями САПР, подчеркнем, что использованию реляционных систем в САПР мешают нормализованность отношений, ограниченность понятия транзакций и отсутствие средств явной работы с предыдущими состояниями объектов. Вместе с тем, все традиционные возможности систем баз данных тоже полезны в САПР, и, следовательно, желательно появление систем управления базами данных, обладающих некоторыми новыми возможностями, но не утративших предыдущие. Работы над развитием традиционных СУБД в этом направлении интенсивно ведутся. В этом разделе мы рассмотрим развитие System R для обеспечения потребностей САПР и других нетрадиционных приложений. Как мы неоднократно отмечали, System R получила развитие в нескольких направлениях. На базе этой системы возникли два коммерческих продукта фирмы IBM - SQL/DS и DB2, реляционные СУБД, оснащенные всеми необходимыми сервисными средствами.На протяжении ряда лет велись работы над распределенной СУБД System R* . Отдельным направлением является разработка прототипа СУБД для инженерных приложений XSQL [65], и именно на этой системе мы остановимся. XSQL интересна своим комплексным подходом к решению проблем. Она предоставляет возможности работы со сложными объектами, в ней расширяется традиционное понятие транзакции и т.д. При этом разработчики стремятся в наибольшей степени использовать базовый подход System R, меняя в нем как можно меньше. В частности, базовым языком запросов XSQL остается известный язык SQL, в который добавлены конструкции для определения и манипулирования сложными объектами. Мы рассмотрим следующие аспекты системы XSQL: подход к организации и управлению сложными объектами; управление транзакциями; управление версиями. | |

Рисунки

tid = <N, i> --T------------------¬ i ¦ ¦Область описателей¦ ¦ ¦ ¦ L-+------------------+ ¦ i-тый описатель +-¬ +------------------+ ¦ +------------------+ ¦ ¦ ¦ ¦ ¦ ¦ ¦ +------------------+ ¦ ¦ i-тый кортеж +-- +------------------+ L------------------- Cтраница номер N

Рис.1 Переход от tid'а кортежа к кортежу без косвенности.

tid = <N, i> --T------------------¬ --T------------------¬ i¦ ¦Область описателей¦ j ¦ ¦Область описателей¦ ¦ ¦ ¦ ¦ ¦ ¦ L-+------------------+ ¦ ¦ ¦ ¦ i-тый описатель +- - - ¬ ¦ +------------------+ ¦ (tid = <M, j>) ¦ L-+ j-тый описатель +-¬ +------------------+ ¦ +------------------+ ¦ +------------------+ +------------------+ ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦ L - - - ¦ ¦ ¦ ¦ ¦ +------------------+ ¦ ¦ ¦ ¦ j-тый кортеж +-- ¦ ¦ +------------------+ L------------------- L------------------- Cтраница номер N Cтраница номер M

Рис.2 Переход от tid'а кортежа к кортежу с косвенностью.

------T-----T-----T-----T-----¬ ¦ X ¦ S ¦ IX ¦ IS ¦ SIX ¦ ------+-----+-----+-----+-----+-----+ ¦ X ¦ нет ¦ нет ¦ нет ¦ нет ¦ нет ¦ +-----+-----+-----+-----+-----+-----+ ¦ S ¦ нет ¦ да ¦ нет ¦ да ¦ нет ¦ +-----+-----+-----+-----+-----+-----+ ¦ IX ¦ нет ¦ нет ¦ да ¦ да ¦ нет ¦ +-----+-----+-----+-----+-----+-----+ ¦ IS ¦ нет ¦ да ¦ да ¦ да ¦ да ¦ +-----+-----+-----+-----+-----+-----+ ¦ SIX ¦ нет ¦ нет ¦ нет ¦ да ¦ нет ¦ L-----+-----+-----+-----+-----+------

Рис. 3. Таблица совместимости захватов.

Время ----------------------------------------------- Т р Т1 +-------+ ¦ ¦ а ¦ ¦ н Т2 +-------+---------+ ¦ з ¦ ¦ а Т3 +----+-----------------------+ к ¦ ¦ ц Т4 ¦ +-------------+ ¦ и ¦ ¦ и Т5 ¦ +-------------+ Контрольная точка Мягкий сбой (момент tc) (момент tf)

Рис.4 Категории транзакций при мягком сбое.

Тип Тип ¦ Грам. ¦ Оптим. ¦ Ген. ¦ Выполнение предложения секции разбор кода ¦ -------+--------+-----¬¦ ---------¬ Запрос на COMPILESECT ¦ В р е м я ¦ ¦ Время ¦ выборку, ¦ ¦ ¦¦ ¦ ¦ вставка, ¦ прекомпиляции ¦ ¦выполне-¦ удаление, ¦ ¦ ¦¦ ¦ния ¦ модификация L---------------------- L--------- ¦ ------¬¦ ¦ ¦ ---------¬ Создание INTERSECT ¦Время¦ ¦ Время ¦ отношения, ¦ ¦пре- ¦¦ ¦ ¦ ¦ ¦ начало ¦компи¦ ¦выполне-¦ транзакции ¦ ¦ляци覦 ¦ ¦ ¦ния ¦ и т.д.
L------ L--------- ¦ ------¬¦ -------+------+----------¬ Операции PARSEDSECT ¦Время¦ ¦ В р е м я ¦ над времен- ¦ ¦пре- ¦¦ ¦ ¦ ными (не ¦компи¦ ¦ ¦ существую- ¦ ¦ляци覦 ¦ в ы п о л н е н и я ¦ щими во ¦ ¦ ¦ ¦ время пре- ¦ ¦ ¦¦ ¦ ¦ компиляции) ¦ ¦ ¦ ¦ отношениями ¦ L------¦ L------T------T-----------

Предложение INDEFSECT ¦ -------+--------+------+----------¬ динамичес- ¦ В р е м я ¦ кой компи- ¦ ¦ ¦ ляции ¦ в ы п о л н е н и я ¦ (PREPARE и ¦ ¦ ¦ EXECUTE) L---------------------------------- ¦ ¦ ¦ ¦

Рис. 5 Выполнения фаз обработки для разных типов запросов.

Compilesect Intersect Parsesect Indefsect ------------T------------T-----------T-----------T-----------¬ Auxcall ¦Выполняется ¦Выполняется¦Динамически¦ Не исполь-¦ ¦программа в ¦стандартная¦вызываются ¦ зуется ¦ ¦машинных ко-¦программа ¦оптимизатор¦ ¦ ¦дах, содер- ¦под управ- ¦и генератор¦ ¦ ¦жащаяся в ¦лением со- ¦кодов для ¦ ¦ ¦секции ¦держимого ¦преобразо- ¦ ¦ ¦ ¦секции ¦вания сек- ¦ ¦ ¦ ¦ ¦ции в Com- ¦ ¦ ¦ ¦ ¦pilesect ¦ ¦ ¦ ¦ ¦или Inter- ¦ ¦ ¦ ¦ ¦sect, затем¦ ¦ ¦ ¦ ¦выполняется¦ ¦ ¦ ¦ ¦(преобразо-¦ ¦ ¦ ¦ ¦вания про- ¦ ¦ ¦ ¦ ¦изводятся ¦ ¦ ¦ ¦ ¦только в ¦ ¦ ¦ ¦ ¦виртуальной¦ ¦ ¦ ¦ ¦памяти) ¦ ¦ ------------+------------+-----------+-----------+-----------+ Opencall ¦Программа в ¦Не исполь- ¦Не исполь- ¦Не исполь- ¦ ¦машинных ко-¦зуется ¦зуется ¦зуется ¦ ¦дах, содер- ¦ ¦ ¦ ¦ ¦жащаяся в ¦ ¦ ¦ ¦ ¦секции, вы- ¦ ¦ ¦ ¦ ¦полняется с ¦ ¦ ¦ ¦ ¦кодом опера-¦ ¦ ¦ ¦ ¦ции OPEN ¦ ¦ ¦ ¦ ------------+------------+-----------+-----------+-----------+ Fetchcall ¦Программа в ¦Не исполь- ¦Не исполь- ¦Не исполь- ¦ ¦машинных ко-¦зуется ¦зуется ¦зуется ¦ ¦дах, содер- ¦ ¦ ¦ ¦ ¦жащаяся в ¦ ¦ ¦ ¦ ¦секции, вы- ¦ ¦ ¦ ¦ ¦полняется с ¦ ¦ ¦ ¦ ¦кодом опера-¦ ¦ ¦ ¦ ¦ции FETCH ¦ ¦ ¦ ¦ ------------+------------+-----------+-----------+-----------+ Closecall ¦Программа в ¦Не исполь- ¦Не исполь- ¦Не исполь- ¦ ¦машинных ко-¦зуется ¦зуется ¦зуется ¦ ¦дах, содер- ¦ ¦ ¦ ¦ ¦жащаяся в ¦ ¦ ¦ ¦ ¦секции, вы- ¦ ¦ ¦ ¦ ¦полняется с ¦ ¦ ¦ ¦ ¦кодом опера-¦ ¦ ¦ ¦ ¦ции CLOSE ¦ ¦ ¦ ¦ ------------+------------+-----------+-----------+------------ ------------T------------------------T-----------T-----------¬ Setupcall ¦Текущее состояние секции¦Не исполь- ¦Вызываются ¦ ¦уничтожается, вызываются¦зуется ¦граммати- ¦ ¦грамматический анализа- ¦ ¦ческий ана-¦ ¦тор, оптимизатор и гене-¦ ¦лизатор, ¦ ¦ратор кодов для построе-¦ ¦оптимизатор¦ ¦ния новой секции (Com- ¦ ¦и генератор¦ ¦pilesect или Intersect) ¦ ¦кодов для ¦ ¦по новому предложению ¦ ¦построения ¦ ¦SQL ¦ ¦секции ¦ ¦ ¦ ¦(Compile- ¦ ¦ ¦ ¦sect или ¦ ¦ ¦ ¦Intersect) ¦ ¦ ¦ ¦для указан-¦ ¦ ¦ ¦ного пред- ¦ ¦ ¦ ¦ложения SQL¦ ------------+------------T-----------+-----------+-----------+ Describecall¦Вырабатыва- ¦Не исполь- ¦Не исполь- ¦Не исполь- ¦ ¦ется описа- ¦зуется ¦зуется ¦зуется ¦ ¦тель резуль-¦ ¦ ¦ ¦ ¦тирующего ¦ ¦ ¦ ¦ ¦отношения ¦ ¦ ¦ ¦ ------------+------------+-----------+-----------+------------

Рис. 6 Типы секций и вызовов.

|

Синхронизация в System R

System R с самого начала задумывалась как многопользовалельская система, обеспечивающая режим мультидоступа к базам данных. Поэтому вопросам синхронизации доступа всегда уделялось очень большое внимание. Разработчики System R сформулировали и частично решили много проблем синхронизации, соответствующие публикации (например, [5], [10-11]) давно стали классикой, и на них ссылаются практически во всех работах, связанных с синхронизацией в системах управления базами данных. Тем не менее, мы считаем полезным рассмотреть этот вопрос еще раз и попытаемся привести историческую ретроспективу решений в области синхронизации в System R. Предварительно заметим, что вопросы синхронизации находятся в тесной связи с вопросами журнализации изменений и восстановления состояния базы данных. Поэтому этот и следующий подразделы также связаны, и нам снова придется временами забегать вперед.

Начнем с рассмотрения целей, которыми руководствовались разработчики System R при выработке своего подхода к синхронизации. Дело в том, что начальной целью синхронизации операций было не обеспечение изолированности пользователей, а поддержка средств обеспечения логической целостности баз данных. Как мы отмечали во введении, логическая целостность баз данных System R поддерживается на основе наличия ранее сформулированных и запомненных в каталогах базы данных ограничений целостности. В конце каждой транзакции или при выполнении явного предложения SQL проверяется ненарушение ограничений целостности изменениями, произведенными в данной транзакции. Если обнаруживается нарушение ограничений целостности, с помощью операции RSS RESTORE производится откат транзакции, нарушившей ограничения.

Для того, чтобы можно было корректно выполнить такой откат, необходимо, чтобы до конца транзакции объекты базы данных, изменявшиеся транзакцией, не могли изменяться и другими транзакциями. В противном случае возникает так называемая проблема потерянных изменений. Действительно, пусть транзакция 1 изменяет некоторый объект базы данных A.
Затем другая транзакция 2 также изменяет объект A, после чего производится откат транзакции 1 (по причине, например, нарушения ей ограничений целостности). Тогда при следующем чтении объекта A транзакция 2 увидет его состояние, отличное от того, в которое он перешел в результате его изменения транзакцией 2. Исходным постулатом System R было то, что потерянные изменения допускать нельзя, и обеспечение этого являлось минимальным требованием к системе синхронизации. Соответствующий режим выполнения транзакций называется в System R первым уровнем совместимости транзакций. Это наиболее низкий уровень синхронизации, вызывающий минимальные накладные расходы в системе. Технически синхронизация на первом уровне совместимости предполагает долговременные (до конца транзакции) синхронизационные захваты изменяемых объектов базы данных и отсутствие каких-либо захватов для читаемых объектов. С точки зрения обеспечения логической целостности баз данных первый уровень совместимости вполне удовлетворителен, но вызывает некоторые проблемы внутри транзакций. Основная проблема - возможность чтения грязных данных. Действительно, читающая транзакция абсолютно не синхронизуется с изменяющими транзакциями, и поэтому в ней может быть прочитано некоторое промежуточное с логической точки зрения состояние объекта (мы подчеркиваем, что "грязным" объект может быть только на логическом уровне; физическую согласованность в базе данных поддерживает другой, "физический" уровень синхронизации RSS, на котором мы остановимся позже). Следующий, второй уровень совместимости транзакций System R обеспечивает отсутствие грязных данных. Технически синхронизация на втором уровне совместимости предполагает долговременные синхронизационные захваты (до конца транзакции) изменяемых объектов и кратковременные (на время выполнения операции) захваты читаемых объектов. Второй уровень совместимости транзакций System R гарантирует отсутствие грязных данных, но не свободен от еще одной проблемы - неповторяющихся чтений.


Если транзакция два раза (подряд или с некоторым временным промежутком) читает один и тот же объект базы данных, то состояние этого объекта может быть разным при разных чтениях, поскольку в промежутке между ними (а он может возникнуть, даже если чтения идут в транзакции подряд) другая транзакция может модифицировать объект. Эту проблему решает третий уровень совместимости транзакций System R, являющийся тем самым уровнем максимальной изолированности пользователей, о котором мы говорили раньше. Технически синхронизация на третьем уровне совместимости предполагает долговременные (до конца транзакции) синхронизационные захваты всех объектов, читаемых и изменяемых в данной транзакции. В начальных версиях System R обеспечивались на самом деле все перечисленные уровни совместимости транзакций. Соответственно, существовали параметры операции RSS BEGIN TRANSACTION, определявшие уровень совместимости данной транзакции. Однако, уже первый опыт использования прототипа System R показал, что наиболее применительным является третий уровень совместимости. При этом существовали приложения, которые устраивал первый уровень (в основном, приложения, связанные со статистической обработкой, в которых ошибки "грязных" данных исправлялись за счет большого числа чтений). Второй уровень совместимости оказался практически неприменимым. В результате в последних версиях разработчики оставили только третий уровень совместимости, и далее мы будем иметь в виду только его. Поскольку интерфейс RSS - покортежный, то логично производить синхронизацию в RSS именно на уровне кортежей или, вернее, их уникальных идентификаторов - tid'ов. Заметим, однако, что если две или более транзакций читают один кортеж, то с точки зрения синхронизации это вполне допустимо, а если хотя бы одна транзакция изменяет кортеж, то она должна блокировать все остальные транзакции, выполняющие операции чтения или изменения данного кортежа. Из этого следует потребность в двух разных режимах захватов кортежей - совместном режиме (для чтения) и монопольном (для изменений).


Следуя терминологии System R, далее мы будем называть эти режимы режимом S (совместным) и режимом X (монопольным). Естественно формулируются правила совместимости захватов одного объекта в режимах S и X: захват режима S совместим с захватом режима S и несовместим с захватом режима X; захват режима X несовместим с захватом любого режима. Соответственно, при чтении кортежа RSS прежде всего устанавливает захват этого кортежа в режиме S; при вставке, удалении или модификации кортежа - в режиме X. Если к этому моменту кортеж захвачен от имени другой транзакции в режиме, несовместимом с требуемым, транзакция, обратившаяся к RSS, блокируется, и требование захвата кортежа ставится в очередь до тех пор, пока не возникнут условия удовлетворения требуемого захвата, т.е. не будут сняты конфликтующие захваты с кортежа. В принципе режим покортежных захватов достаточен для удовлетворения требований, ранее сформулированных в этом подразделе. Следует отметить, что большинство реляционных систем баз данных и ограничиваются покортежными (или даже более грубыми постраничными) захватами. Тем не менее в контексте System R синхронизация такого типа недостаточна. Соответствующие проблемы и предложения по поводу их решения впервые были сформулированы в [5, 10-11]. Основной проблемой является возможность появления корежей-фантомов при повторных сканированиях отношений в одной транзакции (даже на третьем уровне совместимости). Действительно, после первого сканирования все прочитанные кортежи будут захвачены в режиме S, из-за чего никакая другая транзакция не сможет удалить или модифицировать такие кортежи. Но ничто не мешает вставить в другой транзакции в то же отношение новый кортеж, значения полей которого удовлетворяют условиям сканирования первой транзакции. Тогда при повторном сканировании того же отношения с теми же условиями сканирования будет прочитан кортеж, которого не было при первом сканировании, т.е. появится кортеж-фантом. В [10] был предложен подход к решению проблемы фантомов на основе так называемых предикатных захватов.


Идея подхода состоит в том, что при сканировании следует на самом деле захватывать не индивидуальные прочитанные кортежи, а все виртуальное множество кортежей, которые могли бы быть прочитаны при данном сканировании. Для этого достаточно "захватить" условие (предикат), которому должны удовлетворять все кортежи при данном сканировании. Например, если должны быть прочитаны кортежи отношения со значением поля a > 5, то захватывается предикат a > 5. Если некоторая другая транзакция выполняет операцию, например, вставки в то же отношение кортежа со значением поля a > 5, то предикатный захват, предшествующий реальному выполнению этой операции, должен конфликтовать с захватом первой транзакции и т.д. Естественно, что чем более точно формулируется предикат, тем больше реальная параллельность выполнения транзакций в системе с предикатными захватами. С этой точки зрения наибольшего уровня асинхронности можно было бы достичь, если допустить использование в качестве синхронизационных предикатов условий выборки, удаления или модификации языка SQL (или другого языка запросов высокого уровня). Но с другой стороны, чем более общий вид предикатов допускается, тем сложнее становится проблема обнаружения совместимости соответствующих захватов. Как отмечается в [10], достаточно легко реализуется система предикатных захватов, в которой предикаты представляют собой логические выражения, состоящие из простых предикатов сравнения полей отношения с константными значениями. Разработчики System R не пошли и на такую систему, но, как мы покажем ниже, некоторые идеи предикатных захватов использовали. При наличии только покортежных захватов неясным остается вопрос синхронизации в RSS покортежных операций и операций создания и уничтожения отношений и индексов и добавления полей к существующему отношению. Непонятно, как сочетать покортежные захваты с возможность явного захвата отношения и т.д. Очевидно, что общая система предикатных захватов такие проблемы снимает, но как мы уже отмечали, разработчики System R не пошли на ее реализацию.


Вместо этого, как описывается в [5, 11], был разработан протокол иерархических гранулированных захватов (с некоторыми элементами предикатных захватов). Основная идея состоит в том, что имеется некоторая иерархия памяти хранения кортежей: сегмент-отношение-кортеж. Объекты каждого уровня иерархии могут быть захвачены. Кроме того, можно захватывать диапазон значений любого индекса. Набор возможных режимов захватов расширяется так называемыми целевыми (intented) захватами. Семантически целевой захват "сложного" объекта (сегмента или отношения) означает намерение данной транзакции устанавливать целевые или обычные захваты на более низком уровне иерархии. Введены следующие типы целевых захватов: IX (intented to X), IS (intented to S) и SIX (shared, intented to X). Захват объекта в режиме IX соответствует намерению транзакции производить захваты объектов ниже по иерархии в режимах IX или X. Захват объекта в режиме IS соответствует намерению транзакции производить захваты объектов ниже по иерархии в режимах IS или S. Наконец, захват объекта в режиме SIX соответствует захвату объекта в режиме S и намерению транзакции захватывать объекты ниже по иерархии в режиме X. Из этого следуют правила совместимости захватов разных режимов, изображенные на Рис. 3. Протокол синхронизации с использованием перечисленных режимов захватов следующий: Чтобы захватить объект (например, кортеж отношения) в режиме S (X), предварительно установить захваты в режиме IS (IX) соответствующие объекты выше по иерархии (в случае захвата кортежа - сегмент и отношение). При этом захваты должны устанавливаться, начиная от корня иерархии (в нашем случае - сначала для сегмента, затем для отношения и только потом для кортежа). Очевидно, что протокол иерархических захватов решает проблему совместимости глобальных захватов сложного объекта (например, захватов отношения в режиме S) с захватами подобъектов этого объекта (кортежей). Но также очевидно, что протокол, вообще говоря, не решает проблему фантомов.


Если отношение сканируется без использования индекса, то отсутствие фантомов можно гарантировать, если предварительно захватить все отношение в режиме S. Тогда в соответствии с иерархическим протоколом никакая другая транзакция не сможет занести в это отношение новый кортеж, потому что будет блокирована при попытке захватить отношение в режиме IX (захваты отношения в режимах S и IX несовместимы). Можно, конечно, захватывать все отношение и при сканировании с использованием индекса. Таким образом можно решить проблему фантомов, но это очень неэффективное решение, потому что резко ограничивает возможности параллельного выполнения транзакций. Любая только читающая отношение транзакция конфликтует с любой транзакций, изменяющей это отношение. С другой стороны, в RSS при сканировании отношения по индексу имеется дополнительная информация (диапазон сканирования), которая ограничивает множество кортежей, среди которых не должны возникать фантомы. Исходя из этих соображений было предложено ввести в систему синхронизации элементы предикатных захватов. Заметим сначала, что технически захваты сегментов, отношений и кортежей трактуются единообразно, как захваты tid'ов. При захвате кортежа на самом деле захватывается его tid. При захвате сегмента или отношения на самом деле захватывается tid описателя соответствующего объекта во внутренних отношениях описателей таких объектов (сегментов и отношений). Предлагалось расширить систему синхронизации, разрешив применять захваты к паре идентификатор индекса - интервал значений ключа этого индекса. К такой паре разрешено применять захваты в любом из допустимых режимов, причем два захвата совместимы в том и только в том случае, если они совместимы в соответствии с таблицей на Рис.5 или указанные диапазоны значений ключей не пересекаются. При наличии такой возможности, если открывается сканирование отношения по индексу, отношение захватывается в режиме IS, и в этом же режиме захватывается пара идентификатор индекса - диапазон сканирования.


При занесении (удалении) кортежа отношение захватывается в режиме IX, и в этом же режиме для каждого индекса, определенного на данном отношении захватывается пара идентификатор индекса - значение ключа из затрагиваемого операцией кортежа. Тогда читающие транзакции реально конфликтуют только с теми изменяющими транзакциями, которые затрагивают диапазон сканирования. При этом решается проблема фантомов и асинхронность транзакций ограничивается "по существу", т.е. только тогда, когда их параллельное выполнение влечет проблемы. Заметим сразу, что описанное решение проблем синхронизации далеко от идеального. Во-первых, по-прежнему при сканировании отношения без использования индексов отсутствие фантомов можно гарантировать только при полном захвате всего отношения в режиме S. Во-вторых, даже при сканировании по индексу условие реальной выборки кортежа часто может быть строже простого указания диапазона сканирования, а это значит, что требуемый захват слишком сильный, т.е. охватывает более широкое множество кортежей, чем то, которое будет реальным результатом сканирования. Видимо, по этим причинам, а также по причинам требуемого усложнения системы синхронизации описанные средства борьбы с фантомами не были реализованы в System R (по крайней мере, это следует из заключительных публикаций). Более того, в силу половинчатости этого решения и слишком большого ограничения степени асинхронности разработчики отказались и от неявных захватов отношения в режиме S при сканировании без использования индексов. (Напомним, что возможность явного захвата отношения целиком осталась). Тем самым, System R не гарантирует отсутствие фантомов при повторном сканировании отношения. Опыт System R в области синхронизации оказал очень большое влияние на разработчиков реляционных СУБД во всем мире. Особенно это касается предложений по части предикатных захватов. В ряде существующих или пректируемых СУБД предикатные захваты составляют основу системы синхронизации, которая, конечно, при этом становится существенно более сложной, чем в System R.


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

Трансляция запросов и поддержка времени выполнения

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

Как мы уже отмечали во введении, разработчики System R выбрали при реализации SQL подход, основанный на компиляции предложений этого языка в коды объектной ЭВМ (IBM/370). Это означает, что при непосредственном выполнении запроса выполняется программа, содержащая только программный код, необходимый для выполнения этого запроса (включающий, конечно, обращения к RSS), и ничего лишнего. Как неоднократно утверждают разработчики (например, в [24-27]), они пошли на этот шаг в стремлении повысить эффективность выполнения запросов за счет прямого выполнения программного кода, не содержащего лишних команд. Утверждается, что даже в случае интерактивной работы, когда откомпилированный запрос будет заведомо выполняться только один раз, накладные расходы на генерацию машинного кода окупаются эффективностью рабочей программы. Это подтверждается приводимыми в публикациях экспериментальными данными.

Тем не менее, существует альтернативный подход, при котором компиляция запросов, конечно, тоже производится, но генерируется не объектный код, а некоторое процедурное внутреннее представление запроса на промежуточном языке, которое затем интерпретируется при выполнении запроса.
Такой подход применяется, например, в широко известной реляционной СУБД INGRES [72]. Как нам кажется, кроме отмечаемой разработчиками System R увеличивающейся эффективности выполнения запроса, при выборе их подхода существенны и другие обстоятельства. Во-первых, System R - не мобильная система (в отличие от INGRES). Она ориентирована исключительно на ЭВМ семейства IBM/370 и поэтому перед ее разработчиками не стояла проблема переписывания генератора кодов при переносе системы на ЭВМ с другой системой команд. Во-вторых, в силу особенностей операционных систем IBM перед разработчиками не стояла проблема динамической загрузки программы в память задачи во время ее выполнения. Все операционные системы IBM поддерживают операцию "загрузи и выполни". Поэтому нет проблем с выполнением динамически компилируемых запросов. Наконец, в-третьих, генератор кодов компилятора SQL в System R достаточно прост. Как мы покажем ниже, его удалось реализовать в виде "сборщика" рабочей программы из сравнительно небольшого числа ранее подготовленных программных фрагментов. Заметим еще по этому поводу, что и в System R не сразу появилась компиляция предложений SQL в коды машины. В начальных версиях системы использовалась интерпретация, и только накопленный опыт позволил выработать окончательный подход. На уровне пользователя System R допускает два вида интерфейса (оба на основе SQL). Первый вид интерфейса основан на использовании традиционного языка программирования (основным таким языком является традиционный язык фирмы IBM PL/1), в который разрешается включать предложения SQL, соответствующим образом помеченные. Язык SQL содержит средства, позволяющие параметризовать запросы значениями переменных объемлящей программы и получать результаты выполнения запросов в переменных этой программы. Для "стыковки" языка SQL, результатами выполнения запросов которого являются отношения, т.е. множества кортежей, с традиционным языком программирования в SQL введены средства последовательного покортежного просмотра результирующих отношений (аппарат курсоров).


После обработки текста программы прекомпилятором SQL и компилятором PL/1 производится набор объектных модулей, компоновка которых дает рабочую программу, при выполнении которой будут выполнены и те запросы, которые встретятся в потоке управления программы. Это очень грубая схема, которая тем не менее соответствует представлениям пользователей. Далее мы детализируем ее. Второй вид интерфейса, поддерживаемого System R, - интерактивный. При работе с этим интерфейсом пользователи используют базовое "реляционное" подмножество SQL, в котором запрещено использование средств, предназначенных для стыковки с традиционным языком программирования (в частности, запрещено использование аппарата курсоров). Результатами выполнения запросов пользователей являются таблицы-отношения, которые и отображаются на экранах терминалов. Естественно, что средства интерактивного взаимодействия включают редактор, облегчающий формулирование запросов, и компонент, позволяющий описывать - 58 форматы таблиц при изображении их на экране. Нас эти особенности в этой статье занимать не будут. Здесь для нас более интересно то, что интерактивный интерфейс реализуется на основе использования интерфейса первого рода. На самом деле, программа, обеспечивающая интерактивный интерфейс с System R, строится как и любая другая программа, включающая предложения SQL. Возможности обеспечения интерактивного режима, когда заранее неизвестен набор запросов, которые поступят с терминала, обеспечиваются двумя операторами SQL, позволяющими динамически откомпилировать и выполнить запрос. Параметром предложения SQL PREPARE является текстовая строка, которая должна содержать текст предложения SQL, допустимый для использования в интерактивном режиме. Оператор PREPARE - выполняемый. При его выполнении производится компиляция задаваемого предложения SQL, и после его выполнения можно выполнить динамически появляющуюся рабочую программу выполнения запроса с помощью оператора EXECUTE. (Мы опускаем некоторые детали; например, после выполнения оператора PREPARE можно узнать тип компилировавшегося запроса, т.е.


допустимо ли по отношению к его результату использовать курсор.) Таким образом, базовым интерфейсом System R следует считать интерфейс первого типа, когда предложения SQL встраиваются в программу на традиционном языке программирования. С использованием этого базового интерфейса можно создать множество различных прикладных систем, в том числе, и интерактивных. Так что средство интерактивного взаимодействие с использованием базового диалекта SQL - это лишь пример одной из возможных прикладных программ. В коммерческих развитиях System R DB2 и SQL/DS таких интерфейсных подсистем гораздо больше. Например, на тех же принципах реализован интерфейс Query-By-Ecsample [73]. Поэтому в дальнейшей части этого подраздела нас будет интересовать реализация в System R только базового интерфейса. Как описывется в [26], схема обработки программы на традиционном языке (PL/1, Cobol или ассемблер), включающей предложения SQL, является следующей. Программа обрабатывается прекомпилятором SQL, который просматривает исходный текст в поиске специальным образом помеченных предложений SQL. При нахождении каждого такого предложения прекомпилятор выполняет его трехфазную обработку. Для выполнения первой фазы обработки вызывается программа грамматического разбора предложений SQL. Эта программа производит синтаксический анализ полученного предложения и формирует его внутреннее древовидное представление. Кроме того, программа грамматического разбора формирует два списка имен - список имен "входных" переменных, значениями которых должен параметризоваться запрос, и список имен "выходных" переменных, в которые должны помещаться значения полей кортежей результирующего отношения запроса при его последовательном просмотре. Внутреннее представление запроса и два этих списка являются ответными параметрами программы грамматического разбора. На второй фазе, которая начинается, естественно, только при успешном завершении первой, выработанное дерево запроса передается следующему компоненту, который в System R называется оптимизатором. (Мы выделили это слово, поскольку компонент выполняет далеко не только оптимизирующие действия.) Если при выполнении грамматического разбора предложений SQL взаимодействие с базой данных не требуется, то оптимизатор активно использует данные из служебных отношений-каталогов базы данных.


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


На втором шаге оптимизатора проверяются права пользователя, от имени которого производится прекомпиляция, на выполнение действий, выражаемых запросом. Для этого используется служебное отношение-каталог описаний прав доступа зарегистрированных пользователей базы данных. Нарушение прав доступа расценивается как фатальная ошибка прекомпиляции, выполнение которой прекращается с выдачей соответствующей диагностики и без формирования какого-либо результата. Имеется класс предложений SQL, для которых процесс компиляции заканчивается на втором шаге оптимизатора, - класс "интерпретируемых" предложений. К этому классу относятся такие предложения, как CREATE TABLE, CREATE IMAGE и т.д. Выполнение такого типа предложений производится по жесткой предопределенной для каждого вида предложений схеме, и было бы расточительностью генерировать для каждого предложения рабочую программу, которая, в сущности, является стандартной подпрограммой. Такие предложения и выполняются в System R стандартными подпрограммами подсистемы поддержки времени выполнения. Прекомпилятор же для запроса этого класса формирует специальную секцию модуля доступа, которая содержит необходимую информацию для вызова соответствующей стандартной подпрограммы при выполнении запроса. При успешном завершении второго шага работы оптимизатора и при наличии потребности (т.е. если обрабатываемый запрос не относится к классу интерпретируемых) вызывается третий шаг оптимизатора с передачей ему модифицированного дерева запроса. В запросе могут употребляться имена базовых (хранимых) отношений и имена представлений базы данных. При выполнении третьего шага на основе анализа каталога отношений определяется, используются ли в данном запросе представления. Если оказывается, что используются, то для каждого представления из каталога представлений выбирается его внутренняя форма в виде дерева разбора с именами, замененными на идентификаторы, и дерево обрабатываемого запроса сливается с деревьями представлений. В результате порождается преобразованное дерево исходного запроса, в котором употребляются только идентификаторы базовых отношений.


Здесь следует сделать два замечания. Первое замечание касается обработки запросов на изменение отношений базы данных (INSERT, DELETE и UPDATE). Как и в любом другом запросе, в запросах этого вида изменения могут относиться и к базовым отношениям, и к представлениям. Но далеко не для всех представлений определена семантика операций изменения. На самом деле, при выполнении оператора SQL CREATE VIEW производится анализ создаваемого представления на предмет возможности выполнения над ним операций изменения. Мы не будем вдаваться в подробности этого анализа (это отдельная и важная тема, которой до сих пор посвящается много публикаций), но заметим, что в описателе представления помечено, разрешены ли над представлением операции изменения. Если при выполнении третьего шага оптимизатора выясняется, что в запросе на изменение отношения базы данных используется "неизменяемое" представление, то это рассматривается как фатальная ошибка прекомпиляции с соответствующими последствиями. Второе замечание относится к учету существующих в базе данных условий целостности и условных воздействий. В [26] по этому поводу ничего не говорится, но третий шаг работы оптимизатора - наиболее удобный и естественный момент для проведения соответствующих действий. Для этого необходимо воспользоваться каталогами условий целостности и условных воздействий. Если оказывается, что выполнение обрабатываемого запроса должно привести в действие выполнение некоторых условных воздействий, то естественно было бы для каждого такого условного воздействия выбрать внутренее представление собственно воздействия из его описателя и произвести слияние с деревом обрабатываемого запроса. В базе данных могут содержаться условия целостности двух типов. К первому типу относятся условия целостности, определяемые предложением SQL ASSERT с ключевым словом IMMEDIATE. В соответствии с семантикой SQL такие условия должны проверяться немедленно при совершении соответствующих действий. Если анализ показывает, что обрабатываемый запрос должен вызвать немедленную проверку некоторых условий, то естественно для каждого из них произвести слияние внутреннего представления условия с деревом обрабатываемого запроса.


Ко второму типу условий целостности относятся условия, проверка которых должна производиться при завершении транзакции или при выполнении явного оператора SQL INFORCE INTEGRITY. Достаточно неразумно проверять при окончании транзакции все условия целостности, существующие в базе данных. Поэтому при выполнении третьего шага оптимизатора естественно было бы выбрать из множества условий целостности второго типа подмножество, соответствующее данному запросу, и передать идентификаторы этих условий прекомпилятору для их общей сборки. На четвертом шаге вырабатывается внутреннее процедурное представление запроса. Для этого сначала с использованием отношения-каталога индексов опознается множество индексов, которые можно было бы использовать при выполнении обрабатываемого запроса. Далее составляются все возможные планы выполнения данного запроса, т.е. способы его выполнения, представленные во внутренней форме. (Здесь следует оговориться, что не для всех запросов формируются все возможные планы. Для некоторых типов запросов, например, для запросов с соединениями нескольких отношений, их слишком много. В этом случае на основе эвристик некоторые планы вообще не рассматриваются.) Вслед за этим происходит процесс, который и следовало бы называть оптимизацией. Из множества возможных планов выполнения запроса выбирается один, который на основании существующей ко времени прекомпиляции статистической информации является оптимальным по времени выполнения. В силу особой важности этого момента мы рассмотрим его отдельно в следующем подразделе. Выбранный оптимальный план выполнения запроса (путь доступа) представляется путем структурных модификаций дерева запроса на внутреннем процедурном языке ASL (Access Specification Language - язык спецификации доступа) [16]. Опорными элементами ASL являются операции RSS, но конструкции языка имеют более высокий уровень, включая, например, возможности задания итераций в форме, наиболее часто требующейся при выполнении запросов; возможности вычисления встроенных функций и т.д.


Язык ориентирован на упоминавшийся выше подход к генерации кодов на основе сборки рабочей программы из сравнительно небольшого числа заранее подготовленных фрагментов. Формированием внутреннего представления запроса на языке ASL завершается работа оптимизатора, и прекомпилятор приступает к выполнению третьей фазы прекомпиляции - генерации рабочей программы выполнения запроса в машинных кодах. Соотвествующая процедура формирует рабочую программу выполнения запроса в кодах IBM/370, используя способ ее сборки из фрагментов (в [16] отмечается, что используется библиотека, включающая около 100 фрагментов). В результате образуется секция модуля доступа. Мы не упомянули о еще одном специфическом случае - обработке предложения динамического вызова компилятора SQL PREPARE. Прекомпилятор распознает предложения PREPARE (и EXECUTE), и для каждого предложения PREPARE производит специальную "пустую" секцию модуля доступа, содержащую лишь информацию о том, что во время выполнения предложения нужно будет вызвать компилятор SQL с передачей ему динамически полученной текстовой строки. Итак, при работе прекомпилятора могут образовываться секции модуля доступа четырех типов, называемые в [26] PARSESECT, INTERSECT, COMPILESECT и INDEFSECT. Секция типа PARSESECT соответствует запросу, который успешно прошел грамматический разбор, но в котором употребляются имена отношений, не существующих к моменту прекомпиляции. Такая секция содержит дерево грамматического разбора и начальный текст запроса на SQL. Секция типа INTERSECT соответствует "интерпретируемому" запросу и содержит также дерево запроса (но с именами, замененными на идентификаторы) и начальный текст запроса. Секция типа COMPILESECT содержит машинные коды полученной при прекомпиляции рабочей программы выполнения запроса и исходный текст запроса. Наконец, секция типа INDEFSECT соответствует предложению SQL PREPARE. О содержимом секций такого типа мы уже говорили. Для каждого обрабатываемого предложения SQL тем самым естественно выделяются фазы грамматического разбора, оптимизации, генерации кодов и собственно выполнения.


На Рис. 5 показано разделение функций для разных типов секций между этапами прекомпиляции и выполнения. После успешного завершения обработки всех встретившихся в тексте исходной программы предложений SQL прекомпилятор выполняет завершающие действия, которые состоят в формировании из образованных секций модуля доступа - модуля, содержащего программы и данные всех образованных при прекомпиляции секций, который, как мы опишем ниже, специальным образом регистрируется в каталоге базы данных и который загружается в память задачи на стадии выполнения программы. Кроме того, прекомпилятор модифицирует текст исходной программы для обеспечения ее связи с модулем доступа. Эта модификация состоит в том, что все вхождения в текст исходной программы выполняемых предложений SQL заменяются на вызовы стандартной программы поддержки выполнения, называемой в [26] XRDI, с передачей ей параметров, характеризующих соответствующую секцию модуля доступа и требуемую операцию в этой секции. Мы выделили в предыдущем предложении слово "выполняемых", потому что SQL включает один невыполняемый оператор LET identifier BE <query>. Обработка такого предложения на стадии прекомпиляции приводит к образованию соответствующей секции модуля доступа, по отношению к которой в дальнейшем можно употреблять операторы SQL OPEN, FETCH, DESCRIBE и CLOSE. Семантически идентификатор, с которым связан запрос на выборку, содержащийся в предложении LET, означает идентификатор курсора; он указывается в других операциях, связанных с тем же запросом. Из текста исходной программы оператор LET убирается. На Рис.6 перечислены типы секций и возможные типы операций, которые могут вызываться в этих секциях (с использованием вызова упомянутой выше стандартной программы XRDI). Приведем некоторые пояснения по поводу Рис.6. В секциях модуля доступа, полученных при обработке предложений SQL, отличных от запросов на выборку, можно вызвать операции Auxcall, Describecall и Setupcall. Обращение к операции Auxcall вызывает выполнение либо программы в машинных кодах (если секция имеет тип Compilesect), либо соответствующей типу предложения стандартной программы (если секция имеет тип Intersect).


Как отмечается в [26], в секциях этого рода допускается и выполнение операции Describecall, но при этом всегда возвращается один и тот же результат, по которому можно определить, что секция соответствует не запросу на выборку. Выполнение такого проверочного действия требуется, если секция образовалась динамически на стадии выполнения путем вовлечения оператора PREPARE, поскольку тогда в динамике неизвестно, какому типу запроса она соответствует. Выполнение операции Setupcall допустимо только для секций, которые были сформированы динамически при выполнении операции PREPARE. Вызов операции Setupcall производится при выполнении следующей операции PREPARE, относящейся к той же секции. Производится обработка строки, содержащей слудующее предложение SQL, путем последовательного прохождения фаз грамматического разбора, оптимизации и генерации кодов. В результате содержимое секции в вируальной памяти полностью заменяется на новое. При этом, в частности, может измениться и тип секции. В секциях модуля доступа, полученных при прекомпиляции или динамической компиляции предложений SQL типа SELECT (т.е. запросов на выборку), доступны пять операций - Opencall, Fetchcall, Closecall, Describecall и Setupcall. Если секция образована в период прекомпиляции, то используются главным образом три первые операции. При этом первой операцией по отношению к одной секции должна быть операция Opencall. Концептуально выполнение этой операции можно рассматривать как формирование временного отношения, содержащего результат запроса. Достаточно часто это и на самом деле так, например, в случае, когда в запросе указана необходимость сортировки результатов. В более простых случаях можно избежать реального построения такого временного отношения и генерировать кортежи результата по мере потребности. В любом случае после выполнения вызова Opencall, соответствующего операции SQL OPEN <идентификатор курсора>, секция приводится в состояние, позволяющее получать очередной кортеж результата в памяти программы с помощью вызова операции Fetchcall.


Каждый вызов такой операции, соответствующий операции Fetch <идентификатор курсора> приводит к занесению в указанные переменные программы значений полей очередного кортежа результата. Такой покортежный просмотр результирующего отношения запроса прекращается либо при исчерпании результата, либо при вызове в секции операции Closecall, соответстующем операции SQL Close <идентификатор курсора>. В любом случае выполнение операции Close требуется перед повторным использованием секции, начиная с операции Open. При выполнении операции Describecall в секциях, соотвествующих запросам на выборку, вырабатывается описание результирующего отношения запроса, содержащее для каждого поля этого отношения его имя (если оно у него есть; в результирующем списке запроса могут указываться не только имена полей, но и выражения) и тип. Естественно, что для запросов, обрабатываемых в период прекомпиляции, эта операция не требуется, поскольку вырабатываемая информация доступна в статике. Однако, эта операция необходима при выполнении динамически компилируемых запросов. Например, при использовании SQL в интерактивном режиме операция Describecall позволяет правильно отформатировать результат запроса на экране дисплея, не заставляя специальным образом анализировать введенный запрос. Наконец, использование операции Setupcall в секциях этого рода допустимо (как и раньше) только для секций, которые были образованы динамически при выполнении операции PREPARE. Если секция модуля доступа образована при обработке прекомпилятором предложения SQL PREPARE, то в ней доступна только операция Setupcall, которая производит в виртуальной памяти первый готовый к выполнению вариант этой секции (т.е. вариант не типа Indefsect). Как мы уже отмечали, при успешном завершении работы прекомпилятора, образуются модифицированный текст исходной программы, не содержащий уже предложений SQL, и модуль доступа, в который входят все построенные секции. Далее исходная программа обрабатывается обычным образом с использованием соответствущего компилятора, редактора связей и т.д.


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


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


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

Управление транзакциями и синхронизация

Выполнение транзакции в распределенной системе управления базами данных System R*, естественно, является распределенным. Транзакция начинается в главном узле при обращении к какой-либо секции ранее подготовленного (на этапе компиляции) модуля доступа. Как и в System R, модуль доступа загружается в виртуальную память задачи, обращение к секции модуля доступа - это вызов подпрограммы. Однако, в отличие от System R, эта подпрограмма, кроме своего локального программного кода и вызовов функций RSS, содержит еще и вызовы удаленных подсекций модуля доступа. Эти вызовы интерпретируются в духе вызовов удаленных процедур. Тем самым выполнение одной транзакции, инициированной в некотором узле сети A влечет, вообще говоря, инициирование транзакций в дополнительных узлах. Основной новой по сравнению с System R проблемой является проблема согласованного завершения распределенной транзакции, чтобы результаты ее выполнения во всех затронутых ею узлах были либо отображены в состояние локальных баз данных, либо полностью отсутствовали.

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

Для описания протокола используется следующая модель. Имеется ряд независимых транзакций-участников распределенной транзакции, выполняющихся под управлением транзакции-координатора. Решение об окончании распределенной транзакции принимается координатором. После этого выполняется первая фаза завершения транзакции, когда координатор передает каждому из участников сообщение "подготовиться к завершению". Получив такое сообщение, каждый участник переходит в состояние готовности как к немедленному завершению транзакции, так и к ее откату. В терминах System R это означает, что буфер журнала с записями об изменениях базы данных участника выталкиваются на внешнюю память, но синхронизационные захваты не снимаются.
После этого каждый участник, успешно выполнивший подготовительные действия, посылает координатору сообщение "готов к завершению". Если координатор получает такие сообщения ото всех участников, то он начинает вторую фазу завершения, рассылая всем участникам сообщение "завершить транзакцию", и это считается завершением распределенной транзакции. Если не все участники успешно выполнили первую фазу, то координатор рассылает всем участникам сообщение "откатить транзакцию", и тогда эффект воздействия распределенной транзакции на состояние баз данных отсутствует. По отношению к особенностям реализации двухфазного протокола завершения транзакции в System R* заметим еще следующее. В качестве координатора выступает транзакция, выполняющаяся в главном узле, т.е. та, по инициативе которой возникли дополнительные транзакции. Тем самым, наличие центрального координирующего узла не требуется, что соответствует требованию автономности узлов. Для откатов транзакций используется базовый механизм точек сохранения System R. Наконец, классический протокол двухфазного завершения оптимизирован, чтобы сократить число необходимых сообщений. Детальное описание реализации протокола в System R* содержится в [42]. Как и в System R, согласованность состояния баз данных при параллельном выполнении нескольких транзакций в System R* обеспечивается на основе механизма синхронизационных захватов объектов базы данных при соблюдении двухфазного протокола захватов. Напомним, что это означает разбиение каждой транзакции с точки зрения синхронизации на две фазы - рабочую фазу, на которой захваты только устанавливаются, и фазу завершения, когда все захваты объектов базы данных, произведенные данной транзакцией, снимаются. Синхронизация производится в точности так же, как и в System R: каждая транзакция-участник обращается к локальной базе данных через RSS своего узла. Основной новой проблемой является проблема возможных распределенных тупиков, которые могут возникнуть между несколькими распределенными транзакциями, выполняющимися параллельно. (Тупики между транзакциями - участниками одной распределенной транзакции невозможны, поскольку все участники получают один общий идентификатор транзакции и не конфликтуют по синхронизации).


Для обнаружения распределенных синхронизационных тупиков в System R* применяется оригинальный распределенный алгоритм, не нарушающий требования автономности узлов сети и минимизирующий число передаваемых по сети сообщений и необходимую процессорную обработку. Основная идея алгоритма состоит в том, что в каждом узле периодически производится анализ на предмет существования тупика с использованием информации о связях транзакций по ожиданию ресурсов, локальной в данном узле и полученной от других узлов. При проведении этого анализа обнаруживаются либо циклы ожиданий, что означает наличие тупика, либо потенциальные циклы, которые необходимо уточнить в других узлах. Эти потенциальные циклы представляются в виде специального вида строк. Строка представляет собой по сути дела список транзакций. Все транзакции упорядочены в соответствии со значениями своих идентификаторов ("номеров транзакций"). Строка передается для дальнейшего анализа в следующий узел (узел, в котором выполняется самая правая в строке транзакция) только в том случае, если номер первой транзакции в строке меньше номера последней транзакции. (Это оптимизация, уменьшающая число передаваемых по сети сообщений). Этот процесс продолжается до обнаружения тупика. Если обнаруживается наличие синхронизационного тупика, он разрушается за счет уничтожения (отката) одной из транзакций, входящей в цикл. В качестве жертвы выбирается транзакция, выполнившая к этому моменту наименьший объем работы. Эта информация также передается по сети вместе со строками, описывающими связи транзакций по ожиданию. В заключение раздела еще раз заметим, что мы рассмотрели в нем далеко не все аспекты архитектуры и реализации System R*. Как отмечается в [53], это большая и сложная система, в которой применяется много разнообразных технических ухищрений. Однако, как нам кажется, мы рассмотрели большинство (возможно, не все) из наиболее интересных решений, принятых в этой системе. | |

Управление версиями объектов в XSQL

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

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

Следуя [66], рассмотрим общую модель управления версиями в XSQL. Прежде всего отметим, что в первой реализации механизма версий разработчики XSQL не стремились к экономии внешней памяти. Отмечается, что в дальнейшем, возможно, будет реализован более экономный механизм. Управление версиями производится на основе базового понятия сложного объекта. Для каждого объекта может существовать множество версий, составляющих объект проектирования. С объектом проектирования (ОП) связывается идентификатор.

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

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

Версию можно объявить замороженной (frozen). В общем случае в процессе проектирования создается несколько версий, пока не будет достигнут некоторый согласованный уровень, который можно отдать на использование другим проектировщикам.
В этот момент версия замораживается, после чего не допускаются ее удаление и модификации до тех пор, пока ее явно не разморозит пользователь. Средства замораживания и размораживания версий доступны пользователям, и ими следует пользоваться осторожно. Замороженная версия ОП с максимальным номером идентифицируется парой <идентификатор ОП, LAST FROZEN> (последняя замороженная версия). Диалект SQL, используемый в XSQL, включает следующие средства управления объектами проектирования и версиями: - операторы создания и уничтожения объектов проектирования; - операторы создания и уничтожения версий (допускается уничтожение указанной версии; текущей версии; всех версий, более "молодых", чем последняя замороженная; всех незамороженных версий; версий с номерами из указанного интервала); - операторы замораживания и размораживания версий; - операторы выборки объектов проектирования и их версий; - операторы выборки мета-информации по поводу объектов проектирования и их версий (например, число существующих версий). Следующий существенный аспект управления версиями связан с тем, что в одном объекте проектирования могут находиться ссылки на другие объекты проектирования. Пусть, например, существуют два объекта проектирования ОП1 и ОП2, и имеются ссылки из ОП1 на ОП2. Оказывается неудобным хранить в версиях ОП1 ссылки на версии ОП2. Это влечет накладные расходы и не позволяет разным пользователям ОП1 использовать в одной версии ОП1 разные версии ОП2. Для решения этой проблемы предлагается техника, основанная на понятиях родовых ссылок и среды. Родовая ссылка - это ссылка на объект проектирования, в которой не уточняется, какая версия будет использвана. Среда - это именованное бинарное отношение, состоящее из пар <идентификатор ОП, номер версии>. Каждая пара специфицирует номер версии, которая должна быть использована при разрешении родовой ссылки на соответствующий объект проектирования. Если для некоторого объекта проектирования среда не содержит такой пары, при разрешении родовой ссылки используются правила умолчания, которые также специфицируются (можно указать, что по умолчанию выбирается текущая версия или последняя замороженная версия объекта проектирования).


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


Введено понятие логического кластера версий или кластеров. Версия или кластер могут входить в несколько кластеров. Существуют операции, позволяющие задать имена типов кластеров, участвующих в структуризации объекта проектирования, и их связи по вложенности; операции порождения и уничтожения экземпляров кластеров; операции выборки кластеров и версий. Имена вырожденных кластеров "объект проектирования" и "версия" предопределены. При определении типов кластеров контролируется доступность любого промежуточного кластера из корня - объекта проектирования и листа - версии из любого промежуточного кластера. Использование кластеров допускается также при определении среды: пару <идентификатор ОП, номер версии> можно расширить до триплета <идентификатор ОП, идентификатор кластера, номер версии>. При этом номер версии может быть задан явно или с помощью идентификаторов LF и C, но понимается как номер версии в указанном кластере, а не в объекте проектирования в целом. Отмечается, что механизм кластеров необязателен для использования, и если его не использовать, т.е. работать только на уровне версий объекта проектирования, то существование этого механизма не приводит к дополнительным накладным расходам. Работа с версиями в текущей версии реализована над базовым уровнем XSQL. Как отмечается в [66], это позволило проверить правильность идей, после чего, если этого потребуют соображения эффективности, можно перенести некоторые части схемы ниже интерфейса XSQL. Из последнего замечания следует, что на момент публикации достаточного опыта XSQL с механизмом версии еще не было. Завершая этот подраздел, заметим, что разработчиками XSQL предложен достаточно сложный механизм управления версиями (но все-таки гораздо более простой, чем описанный в [67]). Мы не исключаем, что спустя некоторое время появятся публикации, описывающие более простую, эффективно реализуемую схему управления версиями в этой же системы (последователи System R неоднократно проходили подобный путь в своих разработках). | |

Система управления реляционными базами данных

Система управления реляционными базами данных System R разрабатывалась в исследовательской лаборатории фирмы IBM в 1975-1979 г.г. Эта работа оказала революционизирующее влияние на развитие теории и практики реляционных систем во всем мире. Именно System R практически доказала жизнеспособность реляционного подхода к управлению базами данных. После успешного завершения работ по созданию прототипа этой системы, получения экспериментальных результатов ее использования был разработан целый ряд коммерчески доступных реляционных систем, в том числе и на основе непосредственного развития System R (возможности одной из коммерчески доступных реляционных систем - DB2 описываются в [30]). Этот аспект System R, безусловно, очень важен, но не менее, а может быть и более важен практический опыт разработчиков этой системы. Практически во всех более поздних реляционных СУБД в той или иной степени используются методы, примененные в System R. По поводу организации System R существует обширная библиография [1-27]. К сожалению, эти публикации носят недостаточно систематический характер. Нет ни одной статьи или книги, в которой рассматривались бы все вопросы организации System R. Следует отметить, правда, что достаточно подробно касается отдельных аспектов System R в своих книгах К.Дейт [30-33], но в основном в иллюстративных целях, рассматривая каждое решение как одно из нескольких возможных. Кроме того, Дейт касается главным образом внешних особенностей System R (и ее последователей), а технические решения, как правило, не рассматривает вообще. Поэтому в данной работы мы приводим систематический обзор архитектурных особенностей System R (конечно, не очень подробный по причине ограниченности объема). После завершения разработки прототипа System R фирма IBM активно продолжала работы по реляционным СУБД, причем в нескольких направлениях. Первое направление мы уже отмечали разработка коммерческих реляционных СУБД [29, 30, 35]. Этому направлению посвящена переведенная книга Дейта [30], и здесь его рассматривать не будем.
Второе направление - построение распределенной реляционной СУБД на основе идей System R. Прототип такой системы, System R*, был успешно разработан в IBM. Эта работа также существенно обогатила опытом исследователей и разработчиков распределенных СУБД. Ей также посвящено большое количество публикаций [38-53], но имеется только одна (и очень краткая) переведенная статья [53]. В данной работе мы рассмотрим основные особенности System R* более подробно. Наконец, третье важное направление - исследование и разработка реляционных систем, предназначенных для нетрадиционных приложений. Это очень важное направление, потому что основная критика реляционных систем связана как раз с их неприменимостью (или неэффективностью) в приложениях, связанных с иерархичностью данных (например, системах автоматизации проектирования). Как нам кажестся, и в этом направлении разработчики фирмы IBM достигли большого продвижения. Здесь очень интересно проанализировать, как начиная с достаточно сложных предложений по модификации базовых подходов System R, исследователи пришли к очень простым и естественным решениям, не требующим таких модификаций, но вполне удовлетворяющим потребности приложений (наверное, с последним утверждением не все согласятся). По этому предмету существует не очень большое количество публикаций [54-61], видимо, по той причине, что работа еще не завершена. Тем более, на наш взгляд, полезно привести их обзор. Соответственно, оставшаяся часть статьи состоит из трех основных разделов. В Разделе 2 мы рассматриваем основные архитектурные аспекты организации System R. В частности, обсуждается развитие базового языка этой системы SQL, для которого в настоящее время разрабатывается международный стандарт [35]. В Разделе 3 рассматриваются принципы организации распределенной CУБД System R*. При этом основное внимание уделяется не сетевым проблемам, а вопросам, связанным более с управлением базами данных (не потому, что они более важны, а в силу специфики данной работы). Наконец, в четвертом разделе мы рассмотрим развитие и текущее состояние дел в области расширения System R для использования в нетрадиционных приложениях (главным образом, в САПР).В заключение мы приводим выводы, следующие, на наш взгляд, из опыта и истории развития System R, которые полезно иметь в виду разработчикам реляционных СУБД. Заметим, что эта статья не является введением в реляционные базы данных. Предполагается, что читатель имеет представление об основных идеях реляционного подхода, и основные термины этого подхода используются без предварительных определений и пояснений. Более того, предполагается по крайней мере поверхностное знакомство с реляционным языком SQL. Необходимую предварительную информацию можно получить в прекрасных вводных книгах Дейта [30, 31] и Ульмана [32]. |

В этой статье на основании

В этой статье на основании многочисленных публикаций исследователей и разработчиков научно-исследовательской лаборатории фирмы IBM в г.Сан-Хосе мы привели обзор наиболее интересных свойств реляционной системы управления базами данных System R и двух систем, разработанных на основе идей и реализации System R, - распределенной реляционной системы System R* и системы, ориентированной на нетрадиционные для реляционных СУБД приложения, XSQL. Нам кажется, что последовательное изложение материала, относящегося к одному направлению исследований и разработок в области СУБД, будет полезно и специалистам, и читателям, просто интересующимся проблемами организации баз данных. Кроме того, нам хотелось показать, что при правильном выборе базовых архитектурных принципов организации системы управления базами данных эта система продолжает оставаться жизнеспособной и развивающейся на протяжении многих лет. Разработка System R и следующих за ней систем не только принесла большой практический и теоретический вклад в области систем баз данных, но и воспитала несколько поколений высококвалифицированных специалистов. | |

Журнализация и восстановление в System R

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

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

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

Жесткие сбои приводят к полной или частичной потере содержимого баз данных на внешней памяти. Тем не менее цель процесса восстановления та же, что и в случае мягкого сбоя: после завершения этого процесса база данных должна содержать все изменения, произведенные транзакциями, закончившимися к моменту сбоя, и не должна содержать ни одного изменения, произведенного транзакциями, не закончившимися к моменту сбоя. В случае жесткого сбоя единственно возможный подход к восстановлению состояния базы данных может быть основан на использовании ранее произведенной копии базы данных.
В общем случае процесс восстановления после жесткого сбоя существенно более накладен, чем после мягкого сбоя. Как отмечает Дейт [34], любое восстановление состояния базы данных должно основываться на наличии некоторой дополнительной, избыточной информации. Из общих соображений очевидно, что для восстановления базы данных необходима информация, которая не теряется при сбоях, вызывающих потребность в восстановлении. Тем самым, задача любой СУБД и System R, в частности, состоит в выборе некоторого базового механизма поддержки такой избыточной информации, который удовлетворял бы потребностям всех используемых типов восстановлений. Алгоритмы восстановления System R основаны на двух базовых средствах - ведении журнала и поддержке теневых состояний сегментов. Рассмотрим сначала механизм журнализации. Мы уже упоминали о наличии журнала в предыдущих подразделах. Журнал это отдельный файл внешней памяти, для которого для надежности обычно поддерживаются две копии и в который помещается информация по поводу всех операций изменения состояния базы данных. В предыдущем подразделе мы упоминали об использовании журнала для отката транзакции по явной операции RESTORE или при неявных откатах при разрушении тупиков. Та же схема употребляется и при откатах индивидуальных транзакций при сбоях. Механизм индивидуального отката основан на обратном выполнении всех изменений, произведенных данной транзакции (undo). При этом из журнала в обратном хронологическому порядке выбираются все записи об изменении базы данных, произведенные от имени данной транзакции. Для этого необходима идентификация всех записей в журнале. В System R все записи одной транзакции связываются в один список в порядке обратном хронологическому. Ссылка в списке представляет собой адрес записи в файле-журнале. Поскольку схема индивидуального отката едина для всех ситуаций индивидуальных сбоев, в частности для ситуации разрушения тупиков, то обратное выполнение операций сопровождается снятием установленных при прямой работе транзакции синхронизационных захватов с объектов базы данных.


Следовательно, после выполнения индивидуального отката транзакции ситуация в системе такова, как если бы транзакция никогда и не начиналась. Специфика мягкого сбоя системы состоит в утрате состояния оперативной памяти. В оперативной памяти находятся буфера базы данных. Поддерживаются буфера двух сортов: буфера журнала и буфера собственно базы данных. Буфера журнала содержат последние записи в журнал. Имеются два буфера журнала. Как только один буфер полностью заполняется, производится его запись в файл-журнал и продолжается заполнение второго буфера. Таким образом при обычной работе системы обмены с файлом журнала не приводят к приостановке работы. Буфера базы данных содержат копии страниц базы данных, которые использовались в последнее время. В силу обычных в программировании принципов локализации ссылок после помещения копии страницы базы данных в буфер достаточно вероятно, что эта страница потребуется в ближайшем будущем. Поэтому наличие копии страницы в буфере позволит избежать потребности в обмене с устройством внешней памяти, когда эта страница понадобится в следующий раз. Заметим, что размер буферного пула СУБД во многом определяет ее производительность. Более того, как отмечает Дейт в [34], обычная реляционная СУБД такая, как System R, при наличии достаточного размера буферного пула вполне конкурентноспособна по отношению к системам, основанным на специализированной аппаратуре машин баз данных. Задача System R по обеспечению надежного завершения транзакций, т.е. гарантированию наличия произведенных ими изменений в базе данных, требует наличия на внешней памяти информации об этих изменениях. Реально для этого при оканчивании любой транзакции поддерживается гарантированное присутствие в файле-журнале все записей об изменениях, произведенных этой транзакцией. При использовании буферизации для записи в журнал для этого достаточно насильственно вытолкнуть на внешнюю память недозаполненный буфер журнала. Под насильственным выталкиванием понимается запись буфера на внешнюю память в соответствии не с логикой ведения журнала, а с логикой оканчивания транзакции.


Только после произведения такого насильственного выталкивания буфера журнала транзакция считается закончившейся. Заметим, что последней записью в журнале от любой изменяющей базу данных транзакции является запись о конце транзакции. Эти записи используются при восстановлении. Рассмотрим теперь (пока не совсем точно) как осуществляется в System R восстановление базы данных после мягкого сбоя. Основой алгоритма восстановления является то, что система придерживается правила упреждающей записи в журнал (WAL Write Ahead Log). Это правило означает, что при выталкивании любой страницы из буфера страниц сначала гарантируется наличие в файле журнала записи, относящейся к изменениям этой страницы после момента ее вталкивания в буфер. Поскольку записи в журнал блокируются, то для соблюдения правила WAL перед выталкиванием страницы данных необходимо вытолкнуть недозаполненный буфер журнала, если он содержит запись, относящуюся к изменению страницы. Применение правила WAL гарантирует, что если на внешней памяти находится страница базы данных, то в файле журнала находятся все записи об операциях, вызвавших изменение этой страницы. Обратное неверно: в файле журнала могут содержаться записи об изменении некоторых страниц базы данных, а сами эти изменения могут быть не отражены в состояниях страниц на внешней памяти. При окончании любой транзакции (т.е. выполнении операции RSS END TRANSACTION) производится выталкивание недозаполннного буфера журнала и тем самым гарантируется наличие в журнале полной информации обо всех изменениях, произведенной данной транзакцией. Насильственное выталкивание страниц буфера базы данных не производится (слишком накладно было бы производить такие выталкивания при окончании любой транзакции). Тем самым после мягкого сбоя состояние базы данных на внешней памяти может не соответствовать тому, которое должно было бы быть после оканчивания транзакций. Следовательно, после мягкого сбоя некоторые страницы на внешней памяти могут не содержать информации, помещенной в них уже закончившимися транзакциями, а другие страницы могут содержать информацию, помещенную транзакциями, которые к моменту сбоя не закончились.


При восстановлении необходимо добавить информацию в страницах первого типа и удалить информацию в страницах второго типа. System R периодически устанавливает системные контрольные точки. Более подробно мы остановимся на этом ниже. Пока заметим лишь, что при установлении такой контрольной точки производится насильственное выталкивание на внешнюю память буфера журнала и всех буферов страниц. Это дорогостоящая операция, и выполняется она достаточно редко. При каждой системной контрольной точке в журнал помещается специальная запись. Предположим, что последняя системная контрольная точка устанавливалась в момент времени tc, я мягкий сбой произошел в некоторый более поздний момент времени tf. Тогда все транзакции системы можно разбить на пять категорий (как показано на Рис.4). Транзакции категории Т1 начались и кончились до момента tc. Следовательно, все произведенные ими изменения базы данных надежно находятся на внешней памяти, и по отношению к ним никаких действий при восстановлении производить не нужно. Транзакции категории Т2 начались до момента tc, но успели кончиться к моменту мягкого сбоя tf. Изменения, произведенные такими транзакциями после момента tc, могли не попасть на внешнюю память, и при восстановлении должны быть повторно произведены. Транзакции категории Т3 начались до момента tc, но не кончились к моменту сбоя. Все их изменения, произведенные до момента tc, и, возможно, некоторые изменения, произведенные после момента tc, содержатся на внешней памяти. При восстановлении их необходимо удалить. Транзакции категории Т4 начались после момета установки системной контрольной точки и успели закончиться до момента сбоя. Их изменения могли не отобразиться на внешнюю память; при восстановлении их необходимо выполнить повторно. Наконец, транзакции категории Т5 начались после момента tc и не закончились к моменту сбоя. Их изменения должны быть удалены из страниц на внешней памяти.(При классификации транзакций мы следуем [34]. Из этой же книги почерпнут Рис.4.)


В принципе можно было бы выполнить все необходимы восстановительные действия после мягкого сбоя, основываясь только на информации из журнала. Соответствующий алгоритм описан, например, в [34]. Однако, в System R ситуация несколько упрощается за счет применения техники теневых страниц. Принцип теневых страниц давно использовался в файловых системах (например, [71]), поддерживающих файлы со страничной организацией. В соответствии с этим принципом после открытия файла на изменение модифицированные страницы записываются на новое место внешней памяти (т.е. под них выделяются свободные блоки внешней памяти). При этом на внешней памяти сохраняется старая (теневая) таблица отображения страниц файла на внешнюю память, а в оперативной памяти по ходу изменения файла формируется новая таблица. При закрытии файла заново сформированная таблица записывается на внешнюю память, образуя новую теневую таблицу, а блоки внешней памяти, содержащие предыдущие образы страниц файла, освобождаются. При сбое процессора тем самым автоматически сохраняется состояние файла, в котором он находился перед последним открытием (конечно, с возможной потерей некоторых блоков внешней памяти, которые затем собираются с помощью специальной утилиты). Допускаются операции явной фиксации текущего состояния файла и явного отката состояния файла к точке последней фиксации. В System R применяется развитие идей теневого механизма в контексте мультидоступных баз данных. Как мы уже отмечали, сегменты баз данных System R представляют собой файлы со страничной организацией. Соответственно, существуют и таблицы приписки этих файлов на блоки внешней памяти. При выполнении операции установки системной контрольной точки после выталкивания буферов страниц на внешнюю память таблицы отбражения всех сегментов также фиксируются на внешней памяти, т.е. становятся теневыми. Далее до следующей контрольной точки доступ к страницам сегментов производится через таблицы отображения, располагаемые в оперативной памяти, и каждая изменяемая страница любого сегмента записывается на новое место внешней памяти с коррекцией соответствующей текущей таблицы отображения.


Тогда, если происходит мягкий сбой, все сегменты автоматически переходят в состояние, соответствующее последней системной контрольной точке, т.е. изменения, произведенные позже момента установления этой контрольной точки, в них просто не содержатся. Это достаточно сильно упрощает процедуру восстановления после мягкого сбоя. Система вообще не должна предпринимать никаких действий по отношению к изменениям транзакций типа Т5: этих изменений нет на внешней памяти. При восстановлении достаточно выполнить обратные изменения транзакций типа Т3 (undo в терминологии System R), повторно выполнить изменения транзакций типа Т2 (redo в терминологии System R; заметим, кстати, что эти изменения можно теперь выполнять безусловно, не заботясь о том, что они, возможно, и так содержатся на внешней памяти). Кроме того, нужно просто повторить изменения транзакций типа Т4. Естественно, что начинать действия по журналу следует с записи о последней конрольной точке. Справедливости ради, отметим, что на самом деле теневой механизм используется в System R главным образом не для упрощения процедуры восстановления после мягкого сбоя. Как мы уже отмечали, без этого можно обойтись. Главная причина в другом, а именно, в том, что восстановление базы данных можно начинать только от ее физически согласованного состояния. Дело в том, что в журнал помещается информация об изменении объектов базы данных, а не страниц. Например, в журнале может находиться информация о модификации кортежа в виде триплета <tid, старое состояние кортежа, новое состояние кортежа>. Реально же при выполнении операции модификации изменяются несколько страниц: исходная страница; возможно, страница замены, если кортеж не поместился в исходную страницу; страницы индексов. И так происходит при выполнении любой операции изменения базы данных. Поскольку буфера страниц выталкиваются на внешнюю память по отдельности, то к моменту мягкого сбоя на внешней памяти может возникнуть набор физически рассогласованных страниц, не соответствующий никакой журнализуемой операции.


При таком состоянии внешней памяти восстановление по журналу невозможно. Когда выполняется операция установки системной контрольной точки, то до насильственного выталкивания буферов страниц система дожидается завершения всех операций всех транзакции и до окончания выталкивания не допускает выполнения новых операций. Поэтому теневое состояние всех сегментов базы данных физически согласовано и может служить основой восстановления по журналу. При жестких сбоях утрачивается содержимое всех или части сегментов базы данных. Для восстановления базы данных используются журнал и ранее произведенная копия базы данных. В System R допускается посегментное восстановление. Для этого копия сегмента переписывается с архивного носителя на заново выделенный рабочий носитель, а затем по журналу повторяются все изменения, производившиеся в объектах этого сегмента после момента копирования. Поскольку в момент жесткого сбоя содержимое оперативной памяти не утрачивается, то возможно продолжение выполнения транзакций после завершения восстановления. Более того, если авария коснулась только части сегментов базы данных, то транзакции могут продолжать работу на фоне процесса восстановления с объектами базы данных, расположенными в неповрежденных сегментах. Единственным требованием к архивной копии сегмента является то, что страницы в ней должны находиться в физически согласованном состоянии (поскольку восстановление ведется в терминах записей журнала). Поэтому для создания архивной копии сегмента достаточно лишь дождаться конца выполнения операций над объектами данного сегмента и запретить начало новых операций до конца копирования. Тем самым, выполнение архивной копии не требует перевода системы в какой-либо особый режим работы и только незначительно тормозит нормальную работу транзакций. В заключение данного подраздела заметим, что в первых версиях System R в качестве архивного носителя использовались магнитные ленты. Однако, как отмечается в [23], со временем стало ясно, что во-первых, надежность магнитных лент существенно меньше надежности магнитных дисков, а во-вторых, они стали уступать и в емкости.Поэтому в последних версиях системы использовалась только дисковая память. И последнее замечание. Журнал System R располагается в файле большого, но постоянного размера. Он используется в циклическом режиме. Когда записи журнала достигают конца файла, они начинают помещаться в его начало. Поскольку переход на начало файла можно считать утратой предыдущего журнала, этот переход сопровождается копированием сегментов базы данных. В некоторых других системах, как отмечается в [34], используется подход с архивизацией самого журнала. | |

---

---