Проектирование POSTGRES: как задумывалась популярная СУБД

8 июля у PostgreSQL юбилей — ей исполняется 30 лет. В 1996 году Марк Фурнье из компании Networking Services предоставил первый внешний сервер для разработки опенсорсного проекта Postgres. До этого СУБД разрабатывали на мощностях Калифорнийского университета в Беркли .

В день рожденья PostgreSQL мы публикуем перевод статьи, которая послужила основой СУБД. Кстати, у неё тоже юбилей — 40 лет с момента выхода.

Аннотация

В этой статье представлен предварительный проект новой системы управления базами данных (СУБД) под названием POSTGRES, преемника реляционной системы баз данных INGRES. Основные цели проектирования новой системы:

1. обеспечить лучшую поддержку сложных объектов;

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

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

4. упростить код СУБД для восстановления после сбоев,

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

6. как можно меньше изменить (лучше всего совсем не изменять) реляционную модель.

В статье описываются язык запросов, интерфейс языка программирования, архитектура системы, стратегия обработки запросов и система хранения новой системы.

1. Введение

Реляционная система управления базами данных (СУБД) INGRES была реализована в 1975–77 годах в Калифорнийском университете. Начиная с 1978-го создавались различные прототипные расширения для поддержки распределённых баз данных [STON83a], упорядоченных отношений [STON83b], абстрактных типов данных [STON83c] и QUEL как типа данных [STON84a]. Кроме того, мы предложили, но так и не прототипировали новый интерфейс прикладного программирования [STON84b]. Версию INGRES Калифорнийского университета «достаточно сильно переделали», так что включить значимую новую функциональность стало крайне затруднительно. Ещё одна проблема в продолжении расширения существующей системы заключается в том, что многие из предложенных нами идей было бы трудно интегрировать в эту систему из-за прежних проектных решений. Следовательно, мы создаём новую систему баз данных под названием POSTGRES (POST inGRES). 

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

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

2. Обсуждение целей проектирования

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

Первая цель — поддержка сложных объектов [LORI83, STON83c]. Инженерные данные, в отличие от бизнес-данных, более сложны и динамичны. Хотя необходимые типы данных можно смоделировать в реляционной системе, производительность приложений оказывается неприемлемой. Рассмотрим простой пример. Нам нужно хранить в базе данных коллекцию географических объектов (например, многоугольников, линий и окружностей). В обычной реляционной СУБД мы бы создали отношение для каждого типа объекта с соответствующими полями:

POLYGON (id, other fields)
CIRCLE (id, other fields)
LINE (id, other fields)

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

DISPLAY(color, position, scaling, obj-type, object-id)

Поле "object-id" является идентификатором кортежа в отношении, определяемом полем "obj-type" (то есть POLYGON, CIRCLE или LINE). При таком представлении для построения отображения пришлось бы выполнить следующие команды:

foreach OBJ in {POLYGON, CIRCLE, LINE} do
    range of O is OBJ
    range of D is DISPLAY
    retrieve (D.all, O.all)
    where D.object-id = O.id 
    and D.obj-type = OBJ

К сожалению, ни одна реляционная система не выполнит эту коллекцию команд достаточно быстро, чтобы «нарисовать экран» в реальном времени (то есть за одну или две секунды). Проблема в том, что независимо от быстродействия вашей СУБД ей нужно выполнить слишком много запросов, чтобы извлечь данные для объекта. Нужно уметь хранить объект в поле DISPLAY так, чтобы его можно было получить всего одним запросом. Следовательно, наша первоочередная цель — устранить этот недостаток. 

Вторая цель POSTGRES — упростить расширение СУБД, чтобы её можно было применять в новых предметных областях. Обычная СУБД имеет небольшой набор встроенных типов данных и методов доступа. Многим приложениям требуются специализированные типы данных (например, геометрические для CAD/CAM или тип данных позиции с широтой и долготой для картографических приложений). Хотя эти типы данных можно имитировать с помощью встроенных типов, результирующие запросы получаются многословными и запутанными, а производительность может быть низкой. Простой пример с использованием прямоугольников представлен в [STON86].

Наилучшим решением для таких приложений была бы возможность добавлять в СУБД новые типы данных и новые операторы. Более того, B-деревья подходят только для  определённых видов данных, а для некоторых из них часто требуются новые методы доступа. Например, K-D-B-деревья [ROBI81] и R-деревья [GUTM84] подходят для доступа к точечным и полигональным данным соответственно.

Следовательно, наша вторая цель — позволить включать в СУБД новые типы данных, операторы и методы доступа. Кроме того, крайне важно, чтобы их могли реализовать не эксперты, а значит, пользовательский код должен обладать простым интерфейсом. Другие исследователи тоже преследуют похожую цель [DEWI85]. 

Третья цель POSTGRES — поддержка активных баз данных и правил. Многие приложения проще всего программировать с использованием механизмов оповещения и триггеров. Например, приложения с потоком форм, такие как система баг-репортов, требуют активных форм, которые передаются от одного пользователя другому [TSIC82, ROWE82]. Приложение баг-репортов должно уведомлять менеджера группы сопровождения программы, если программист не исправит назначенную ему ошибку с высоким приоритетом к указанной дате. Оповещатель базы данных должен отправлять сообщение менеджеру, чтобы привлечь его внимание к проблеме. Для поддержания согласованности и распространения обновлений в базе данных можно использовать триггеры. Например, удаление кортежа отдела в отношении DEPT может вызвать обновление, удаляющее всех сотрудников этого отдела из отношения EMP. 

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

1. Нормальная нагрузка составляет 8 часов аудиторной нагрузки в год.

2. Ответственный за составление расписания получает снижение нагрузки на 25%.

3. Заведующий кафедрой освобождается от преподавания.

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

5. Курсы, на которых меньше 10 студентов, засчитываются из расчёта 0,1 часа аудиторной нагрузки за каждого студента.

6. Курсы, на которых больше 50 студентов, дают дополнительные часы аудиторной нагрузки из расчёта 0,01 часа за каждого студента сверх 50.

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

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

Четвёртая цель POSTGRES — сократить объём кода СУБД для поддержки восстановления после сбоев. В большинстве СУБД объём такого кода огромен: его сложно писать, тестировать и отлаживать, а ещё в нём множество особых случаев. Поскольку одна из наших целей — разрешить пользовательские методы доступа, модель восстановления после сбоев должна быть как можно более простой и легко расширяемой. Предлагаемый нами подход состоит в том, чтобы рассматривать логи как обычные данные, управляемые СУБД. Это упростит код восстановления и одновременно обеспечит поддержку доступа к историческим данным.

Следующая цель — по возможности использовать новые технологии. Оптические диски, в т. ч. записываемые, становятся доступными на коммерческом рынке. Они медленнее, но привлекают соотношением цены/производительности и надёжностью. Архитектура системы, включающая оптические диски в иерархию хранения, будет преимуществом. Ещё одна технология, которую мы предвидим, — многопроцессорные рабочие станции. Мы хотим спроектировать POSTGRES так, чтобы использовать преимущества этих CPU-ресурсов. Наконец, проект, способный эффективно использовать специализированное аппаратное обеспечение, мог бы стать убедительным аргументом в пользу проектирования и реализации специально разработанных VLSI-чипов. Итак, наша пятая цель — исследовать архитектуру, которая сможет эффективно использовать оптический диск, несколько тесно связанных процессоров и специально разработанные VLSI-чипы.

Последняя цель POSTGRES — внести как можно меньше изменений в реляционную модель. Во-первых, многие пользователи в сфере обработки бизнес-данных познакомятся с реляционными концепциями, и этот фреймворк по возможности следует сохранить. Во-вторых, мы считаем, что исходный аргумент Кодда о «спартанской простоте» [CODD70] сегодня так же справедлив, как и в 1970 году. Наконец, существует много семантических моделей данных, но до сих пор не появилась небольшая модель, которая решала бы проблемы всех пользователей. Например, иерархия генерализации не решит задачу структурирования CAD-данных, а проектные модели, разработанные CAD-сообществом, не смогут работать с иерархиями генерализации. Мы считаем, что новую систему следует строить не на большой и сложной модели данных, а на небольшой, простой и расширяемой. Мы полагаем, что сможем достичь целей, сохранив реляционную модель. Другие исследователи стремятся к похожим целям, но используют иные подходы [AFSA85, ATKI84, COPE84, DERR85, LORI83, LUM85].

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

3. POSTQUEL

В этом разделе описывается язык запросов, поддерживаемый POSTGRES. Реляционная модель сохранена в том виде, в каком была описана в исходном определении Кодда [CODD70]. База данных состоит из набора отношений, содержащих кортежи с одинаково определёнными полями, причём значения в одном поле имеют один и тот же тип данных. Язык запросов основан на языке запросов INGRES — QUEL [HELD75]. В QUEL были внесены несколько расширений и изменений, поэтому новый язык называется POSTQUEL, чтобы отличать его от исходного языка и расширений QUEL, описанных в других работах [STON85a, KUNG84].

Большая часть QUEL осталась без изменений. Следующие команды включены в POSTQUEL без изменений: Create Relation, Destroy Relation, Append, Delete, Replace, Retrieve, Retrieve into Result, Define View, Define Integrity и Define Protection. Команда Modify, которая задавала структуру хранения для отношения, была исключена, поскольку все отношения хранятся в специальной структуре, предназначенной для поддержки исторических данных. Команда Index сохранена, чтобы можно было определять другие пути доступа к данным.

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

3.1. Определение данных

Предусмотрены следующие встроенные типы данных:

1. целые числа (integer);

2. числа с плавающей точкой;

3. символьные строки фиксированной длины;

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

5. POSTQUEL;

6. процедуры (procedure).

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

Массивы переменной длины предназначаются для приложений, которым нужно хранить большие однородные последовательности данных (например, данные обработки сигналов, изображения или звук). К полям этого типа обращаются стандартным способом (например, EMP.picture[i] обозначает i-й элемент массива picture). Особый случай массивов — текстовый тип данных, представляющий собой одномерный массив символов. Следует отметить, что массивы могут динамически расширяться.

Поля типа POSTQUEL содержат последовательность команд для манипулирования данными. К ним обращаются с помощью обычной точечной нотации. Однако если поле типа POSTQUEL содержит команду retrieve, то данные, задаваемые этой командой, могут неявно адресоваться с помощью множественной точечной нотации, например EMP.hobbies.battingavg, как было предложено в другой работе [STON84a] и впервые высказано Заниоло в GEM [ZANI83].

Поля типа procedure содержат процедуры на языке программирования общего назначения со встроенными командами манипулирования данными, например EQUEL [ALLM76] или Rigel [ROWE79]. Поля типов procedure и POSTQUEL можно выполнять с помощью команды Execute. Предположим, задано отношение со следующим определением:

EMP(name, age, salary, hobbies, dept)

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

execute (EMP.hobbies) 
where EMP.name = “Smith”

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

Поля типов POSTQUEL и procedure можно использовать для представления сложных объектов с общими подобъектами и поддержки нескольких представлений данных. Примеры — в следующем разделе о сложных объектах.

Помимо этих встроенных типов данных можно определять пользовательские типы с помощью интерфейса, похожего на интерфейс ADT-INGRES [STON83c, STON86]. Средства пользовательских типов данных позволяют определять новые типы данных и операторы.

3.2. Сложные объекты

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

Разделяемые сложные объекты могут быть представлены полем типа POSTQUEL, которое содержит последовательность команд для извлечения данных из других отношений, представляющих подобъекты. Например, при наличии отношений POLYGON, CIRCLE и LINE, определённых выше, можно определить объектное отношение, представляющее сложные объекты, составленные из многоугольников, окружностей и линий. Определение объектного отношения было бы следующим:

create OBJECT (name = char[10], obj = postquel)

Таблица на рисунке 1 показывает примерные значения для этого отношения. Отношение содержит описание двух сложных объектов с именами "apple" и "orange." Объект "apple" состоит из многоугольника и окружности, а объект "orange" состоит из линии и многоугольника. Обратите внимание, что оба объекта совместно используют многоугольник с id, равным 10.

Рисунок 1. Пример отношения OBJECT

Множественные представления данных позволяют хранить кешированную копию данных в структуре, подходящей для конкретной задачи, сохраняя при этом простой доступ через реляционное представление. Многие примеры такого использования встречаются в системах баз данных (например, дескрипторы отношений в основной памяти) и в системах форм [ROWE85]. Множественные представления можно поддерживать, определив процедуру, которая преобразует одно представление (например, реляционное) в другое (например, в список отображения, пригодный для графического дисплея). Процедура преобразования хранится в базе данных. В нашем примере со сложным объектом отношение OBJECT будет иметь дополнительное поле с именем display, содержащее процедуру, которая создаёт список отображения для объекта, хранящегося в POLYGON, CIRCLE и LINE:

create OBJECT(name=char[10], obj=postquel, display=cproc)

Значение, хранящееся в поле display, — это процедура на языке C. Она выполняет запросы к базе данных, чтобы получить подобъекты, из которых состоит объект, и создаёт для него представление в виде списка отображения.

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

create OBJPROC(name=char[12], proc=cproc)
append to OBJPROC(name=“display-list”, proc=“...source code...”)

Теперь запись в поле display для объекта apple будет такой:

execute (OBJPROC.proc)
with (“apple”)
where OBJPROC.name=“display-list”

Эта команда выполняет процедуру, создающую альтернативное представление, и передаёт ей имя объекта. Обратите внимание, что поле display можно изменить на значение типа POSTQUEL, поскольку в OBJECT хранится не сама процедура, а команда для её выполнения. На этом этапе процедура может выполнить команду для получения данных. Поскольку процедуре передали имя объекта, она может выполнить следующую команду, чтобы получить его значение:

execute (OBJECT.obj)
where OBJECT.name=argument

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

Поля типов POSTQUEL и procedure могут эффективно поддерживаться за счёт сочетания компиляции и предварительных вычислений, описанных в разделах 4 и 5.

3.3. Данные, изменяющиеся во времени

POSTQUEL позволяет пользователям сохранять и запрашивать исторические данные и версии [KATZ85, WOOD83]. По умолчанию данные в отношении никогда не удаляются и не обновляются. Обычные выборки всегда обращаются к текущим кортежам в отношении. К историческим данным можно обратиться, указав желаемое время при определении переменной кортежа. Например, чтобы получить исторические данные о сотрудниках, пользователь пишет:

retrieve (E.all) 
from E in EMP["7 January 1985"]

Этот запрос возвращает все записи о сотрудниках, которые работали в компании на 7 января 1985 года. Предложение From, которое похоже на механизм SQL для определения переменных-кортежей [ASTR76], заменяет команду QUEL Range. Команда Range была удалена из языка запросов, поскольку определяла переменную-кортеж на всё время выполнения пользовательской программы. Поскольку запросы могут храниться как значения полей, область видимости переменных-кортежей должна быть ограничена. Предложение From делает область видимости определения локальной — только для текущего запроса.

Обозначение в квадратных скобках для доступа к историческим данным неявно определяет снапшот [ADIB80]. Реализация запросов, обращающихся к такому снапшоту, подробно описана в разделе 5 и выполняет поиск по истории отношения, чтобы найти соответствующие кортежи. Пользователь может материализовать снапшот, выполнив команду Retrieve-into, которая создаёт копию данных в другом отношении.

Приложения, которым не нужно хранить исторические данные, могут задавать точку отсечения для отношения. Данные старше этой точки удаляются из базы данных. Точки отсечения задаются командой Discard. Команда:

discard EMP before "1 week"

удаляет данные в отношении EMP, которые старше одной недели.

Команды:

discard EMP before "now"

и

discard EMP

оставляют в EMP только текущие данные.

Также можно писать запросы, которые обращаются к данным, валидным между двумя датами. Нотация:

relation-name[date1, date2]

задаёт отношение, содержащее все кортежи, которые находились в отношении в некоторый момент времени между date1 и date2. Любую из этих дат можно опустить, чтобы задать все данные с момента создания до фиксированной даты (relation-name[,date]), все данные от фиксированной даты до текущего момента (relation-name[date,]), все данные, когда-либо существовавшие в отношении (relation-name[]). Например, запрос:

retrieve (E.all)
from E in EMP[]
where E.name = "Smith"

возвращает всю информацию о сотрудниках с фамилией Smith, которые работали в компании в любой момент времени.

POSTQUEL поддерживает трёхуровневую иерархию памяти: 1) основная память, 2) вторичная память (магнитные диски), 3) третичная память (оптические диски). Текущие данные хранятся во вторичной памяти, а исторические данные мигрируют в третичную. Однако пользователи могут запрашивать данные, не зная, где они физически хранятся. 

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

newversion EMPTEST from EMP

создаёт версию EMPTEST, основанную на отношении EMP. Если пользователь хочет создать версию, которая не изменяется при дальнейших обновлениях базового отношения, как в большинстве систем управления исходным кодом [TICH82], он может создать версию на основе снимка. 

Команда Merge позволяет слить изменения из версии обратно в базовое отношение. Пример команды Merge:

merge EMPTEST into EMP

Команда Merge использует полуавтоматический механизм разрешения конфликтов между изменениями в версии и базовом отношении [GARC84].

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

3.4. Итерационные запросы, оповещатели, триггеры и правила

В этом разделе описываются команды POSTQUEL для задания итеративного выполнения запросов, оповещателей [BUNE79], триггеров [ASTR76] и правил.

Итеративные запросы необходимы для поддержки транзитивного замыкания [GUTM84 KUNG84]. Итерация задаётся добавлением звездочки ("*") к команде, которая должна выполняться многократно. Например, чтобы построить отношение, включающее всех людей, которыми кто-либо управляет прямо или косвенно, используется команда Retrieve*-into. Предположим, задано отношение сотрудника (employee) с полями «имя» (name) и «менеджер» (manager):

create EMP(name=char[20],...,mgr=char[20],...)

Следующий запрос создаёт отношение, содержащее всех сотрудников, которые работают на Джонса (Jones):

retrieve* into SUBORDINATES(E.name, E.mgr)
   from E in EMP, S in SUBORDINATES
   where E.name="Jones" or E.mgr=S.name

Эта команда продолжает выполнять команду Retrieve-into до тех пор, пока в отношении SUBORDINATES не происходит изменений.

Модификатор "*" можно добавить к любой из команд манипулирования данными POSTQUEL: Append, Delete, Execute, Replace, Retrieve и Retrieve-into. Сложные итерации, такие как эвристический алгоритм поиска A-*, могут быть заданы с помощью последовательностей таких итерационных запросов [STON85b].

Оповещатели и триггеры задаются добавлением к запросу ключевого слова "always". Например, оповещатель задаётся командой Retrieve вида:

retrieve always (EMP.all) where EMP.name = "Bill"

Эта команда возвращает данные прикладной программе, которая её выдала, всякий раз, когда запись сотрудника Bill изменяется (строго говоря, данные возвращаются программе через портал, описание которого приведено в разделе 4). Триггер — это запрос обновления (то есть команда Append, Replace или Delete) с ключевым словом “always”. Например:

delete always DEPT
where count(EMP.name by DEPT.dname 
where EMP.dept = DEPT.dname) = 0

Этот триггер удаляет записи в DEPT о подразделениях, в которых нет сотрудников.

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

Команды "always" поддерживают управляющую структуру прямого вывода (forward-chaining), в которой обновление пробуждает набор оповещателей и триггеров, которые, в свою очередь, могут активировать другие команды. Этот процесс завершается, когда новые команды больше не пробуждаются. POSTGRES также поддерживает модель управления обратного вывода (backward-chaining).

Классический подход к поддержке вывода (inference) заключается в расширении механизма представлений (view) или его аналогов дополнительными возможностями (например, [ULLM85, WONG84, JARK85]). Канонический пример — определение отношения ANCESTOR на основе хранимого отношения PARENT:

PARENT (parent-of, offspring)

Отношение ANCESTOR может быть определено следующими командами:

range of P is PARENT
range of A is ANCESTOR
define view ANCESTOR (P.all)
define view* ANCESTOR (A.parent-of, P.offspring)
where A.offspring = P.parent-of

Обратите внимание, что представление ANCESTOR определяется несколькими командами, которые могут включать рекурсию. Запрос:

retrieve (ANCESTOR.parent-of) where ANCESTOR.offspring = "Bill"

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

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

define view DESK-EMP (EMP.all, desk = "steel") where EMP.age < 40
define view DESK-EMP (EMP.all, desk = "wood") where EMP.age >= 40
define view DESK-EMP (EMP.all, desk = "wood") where EMP.name = "hotshot"
define view DESK-EMP (EMP.all, desk = "steel") where EMP.name = "bigshot"

В этом примере сотрудники старше 40 лет получают деревянный стол, а младше 40 — металлический. Однако “hotshot” и “bigshot” являются исключениями из этих правил: “hotshot” получает деревянный стол, а “bigshot” — металлический, независимо от возраста. В этом случае запрос:

retrieve (DESK-EMP.desk) where DESK-EMP.name = "bigshot"

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

POSTGRES поддерживает правила с обратным выводом (backward-chaining) с помощью виртуальных столбцов (то есть столбцов, значения которых не хранятся физически). Данные в таких столбцах выводятся по запросу на основе правил и не могут быть изменены напрямую, кроме как путём добавления или удаления правил. Правила задаются добавлением ключевого слова “demand” к запросу. Таким образом, в примере DESK-EMP отношение EMP будет иметь виртуальное поле desk, которое определяется четырьмя правилами:

replace demand EMP (desk = "steel") where EMP.age < 40
replace demand EMP (desk = "wood") where EMP.age >= 40
replace demand EMP (desk = "wood") where EMP.name = "hotshot"
replace demand EMP (desk = "steel") where EMP.name = "bigshot"

Третья и четвёртая команды имеют более высокий приоритет, чем первая и вторая. Запрос, обращающийся к полю desk, вызывает выполнение команд “demand”, чтобы определить соответствующее значение desk для каждого выбранного кортежа EMP.

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

4. Интерфейс с языком программирования

В этом разделе описывается интерфейс языка программирования (HITCHING POST) к POSTGRES. При проектировании HITCHING POST и средств POSTGRES мы преследовали три цели. Во-первых, мы хотели разработать и реализовать механизм, который упростил бы создание приложений с навигационным доступом к данным. Во-вторых, HITCHING POST должен был быть достаточно мощным, чтобы на его основе можно было реализовать все программы, работающие с базой данных, включая интерактивный терминальный монитор и любые препроцессоры для встраиваемых языков запросов. И наконец, мы хотели предоставить средства, позволяющие разработчику приложений настраивать производительность своих программ (то есть находить баланс между гибкостью и надёжностью, с одной стороны, и производительностью — с другой).

Любая команда POSTQUEL может быть выполнена внутри программы. Кроме того, предоставляется механизм, называемый «портал» (portal), который позволяет программе извлекать данные из базы данных. Портал похож на курсор [ASTR76], за исключением того, что он допускает произвольный доступ к данным, определённым запросом, и позволяет извлекать более одной записи за раз. Описываемый здесь механизм порталов отличается от ранее разработанного нами варианта [STON84b], однако цель остаётся той же. В следующих подразделах описываются команды определения порталов и доступа к данным через них, а также средства повышения производительности выполнения запросов (компиляция и fast-path).

4.1. Порталы

Портал определяется командой Retrieve-portal или Execute-portal. Например, следующая команда определяет портал с именем P:

retrieve portal P(EMP.all) where EMP.age < 40

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

Программа извлекает данные из бэкенда в буфер с помощью команды Fetch. Например, команда:

fetch 20 into P

извлекает первые двадцать записей в портале во фронтенд-программу. К этим записям можно обращаться с помощью индексов и ссылок на поля в P. Эти записи доступны через индексацию и обращение к полям портала P. Например, P[i] обозначает i-й кортеж, полученный последней командой Fetch, а P[i].name — поле name в этом кортеже. Последующие вызовы Fetch заменяют ранее загруженные данные в буфере frontend-программы.

Идея портала заключается в том, что данные в буфере — это данные, которые в данный момент отображаются в браузере. Команды, вводимые пользователем в терминале, преобразуются в команды базы данных, которые изменяют данные в буфере, после чего те перерисовываются. Например, если пользователь выполняет команду прокрутки вперёд на половину экрана, frontend-программа (браузер) преобразует её в команду Move, за которой следует команда Fetch. Следующая последовательность команд загружает данные в буфер, что при отображении создаёт эффект прокрутки:

move P forward 10
fetch 20 into P

Команда Move перемещает «текущую позицию» так, чтобы она указывала на 11-й кортеж в портале, а команда Fetch извлекает кортежи с 11-го по 30-й в порядке, определённом планом выполнения запроса. «Текущая позиция» портала — это первый кортеж, возвращённый последним вызовом Fetch. Если после этого выполнялись команды Move, то текущей позицией считается первый кортеж, который был бы возвращен при следующем Fetch. Команда Move имеет несколько вариантов, упрощающих реализацию навигационных операций. Она позволяет перемещать позицию вперёд, назад, в абсолютную позицию или к первому кортежу, удовлетворяющему предикату.

Например, для прокрутки назад на половину экрана используются команды:

move P backward 10
fetch 20 into P

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

move P forward to 63

Наконец, предусмотрена команда Move, которая выполняет поиск вперёд или назад до первого кортежа, удовлетворяющего условию. Например, чтобы найти первого сотрудника с зарплатой больше 25 000:

move P forward to salary > 25K

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

Чтобы извлекать только кортежи, удовлетворяющие предикату, команда Fetch используется следующим образом:

fetch 20 into P where salary > 25K

Бэкенд продолжает выполнять план запроса до тех пор, пока не найдёт 20 подходящих кортежей или пока не исчерпает данные портала.

Порталы существенно отличаются от курсоров тем, как выполняется обновление данных. Если курсор установлен на запись, её можно напрямую изменить или удалить. В портале данные не обновляются напрямую. Вместо этого используются команды Delete или Replace на отношениях, из которых формируются данные портала.

Предположим, пользователь через браузер изменяет зарплату сотрудника по фамилии Smith. Если запись Smith уже находится в буфере, браузер преобразует это в последовательность команд:

replace EMP(salary=NewSalary) 
where EMP.name = "Smith"
fetch 20 into P

Команда Replace изменяет кортеж Smith в отношении EMP, а команда Fetch синхронизирует буфер в браузере с данными в базе данных. Мы выбрали этот косвенный подход к обновлению данных, потому что он имеет смысл для модели портала как плана запроса. Мы выбрали такой непрямой способ обновления, потому что он согласуется с моделью портала как выполняющегося плана запроса. В нашей предыдущей формулировке [STON84] портал рассматривался как упорядоченное представление, а обновления интерпретировались как обновления представления. Мы считаем, что обе модели допустимы, однако модель через план запроса требует меньше кода. 

Помимо команды Retrieve-portal, порталы могут определяться через команду Execute. Например, если отношение EMP содержит поле типа POSTQUEL с именем “hobbies”:

EMP (name, salary, age, hobbies)

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

SOFTBALL (name, position, batting-avg)
COMPUTERS (name, isowner, brand, interest)

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

execute portal H(EMP.hobbies) where EMP.name = "Smith"

Эта команда определяет портал с именем “H”, привязанный к записям о хобби сотрудника Smith. Поскольку у человека может быть несколько хобби, представленных более чем одной командой Retrieve в поле hobbies, записи в буфере могут иметь разные типы. Следовательно, HITCHING POST должен предоставлять функции, позволяющие программе определять количество полей, а также тип, имя и значение каждого поля в каждой записи, загруженной в буфер.

4.2. Компиляция запросов и fast-path

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

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

CODE(id, owner, command)

Поля “id” и “owner” образуют уникальный идентификатор каждой сохранённой команды. Поле “command” содержит команду, которую необходимо скомпилировать. Предположим, разработчик браузера отношений, описанного выше, хочет скомпилировать команду Replace, которая изменяет значение поля зарплаты сотрудника. Программа может добавить эту команду с соответствующими параметрами в каталог CODE следующим образом:

append to CODE(id=1, owner=‘‘browser’’,
command=‘‘replace EMP(salary=$1) where EMP.name=$2’’)

Здесь $1 и $2 обозначают аргументы команды. Теперь чтобы извлечь команду Replace, изменяющую зарплату Smith, программа выполняет следующую команду:

execute (CODE.command)
with (NewSalary, "Smith")
where CODE.id = 1 and CODE.owner = "browser"

Эта команда выполняет сохранённую команду Replace, подставив вместо параметров переданные аргументы.

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

Скомпилированные запросы работают быстрее, чем запросы, которые разбираются и оптимизируются во время выполнения. Однако для некоторых приложений даже этого оказывается недостаточно. Проблема заключается в том, что сама команда Execute, вызывающая скомпилированный запрос, всё равно должна быть обработана. Чтобы устранить эти накладные расходы, предусмотрен механизм fast-path. В приведённой выше команде Execute изменяются только список аргументов и уникальный идентификатор, определяющий, какой запрос необходимо выполнить. HITCHING POST предоставляет функцию времени выполнения, позволяющую передавать эту информацию бэкенд-процессу в двоичном формате. Например, предыдущую команду Replace можно вызвать следующим образом:

exec-fp(1, "browser", NewSalary, "Smith")

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

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

5. Архитектура системы

В этом разделе описывается то, как мы предлагаем реализовать POSTGRES. В первом подразделе рассматривается структура процессов. Во втором описывается реализация обработки запросов, включая поля типов POSTQUEL, procedure и пользовательских типов данных. Третий подраздел посвящён реализации оповещателей, триггеров и правил. Наконец, в четвёртом подразделе рассматривается подсистема хранения данных, которая обеспечивает поддержку данных, изменяющихся во времени.

5.1. Структура процессов

Код СУБД должен выполняться в отдельном процессе по отношению к прикладным программам, обращающимся к базе данных, чтобы обеспечить защиту данных. Возможны две модели организации процессов: один процесс СУБД на каждую прикладную программу (модель process-per-user) [STON81] и один процесс СУБД для всех прикладных программ (серверная модель). Серверная модель обладает многими преимуществами с точки зрения производительности, особенно на больших вычислительных системах, где критична высокая скорость работы. Например, она позволяет совместно использовать открытые файловые дескрипторы и буферы, а также уменьшить накладные расходы на переключение задач и обмен сообщениями.

Однако такой подход требует создания достаточно полноценной специализированной операционной системы. Напротив, модель «один процесс на пользователя» значительно проще в реализации, хотя на большинстве существующих операционных систем она обеспечивает более низкую производительность. После долгих обсуждений мы решили реализовать POSTGRES именно по модели process-per-user, поскольку ресурсы разработчиков были ограничены. POSTGRES — чрезвычайно амбициозный проект, и мы сочли, что дополнительная сложность серверной архитектуры не оправдывает риск вообще не довести систему до рабочего состояния. Поэтому на текущем этапе мы планируем реализовать POSTGRES как систему с архитектурой process-per-user поверх Unix 4.3 BSD.

Структура процессов POSTGRES показана на рисунке 3. Процесс POSTMASTER будет содержать менеджер блокировок — поскольку в 4.3 BSD отсутствуют разделяемые сегменты памяти — и будет управлять демонами, выполняющими различные сервисные функции базы данных, например асинхронную компиляцию пользовательских команд. На каждой машине будет работать только один процесс POSTMASTER, который запускается во время инициализации системы (sysgen).

Рисунок 3. Структура процессов POSTGRES

Исполняющая система POSTGRES (run-time system) выполняет команды от имени одной прикладной программы. При этом одна программа может иметь одновременно несколько выполняющихся команд. Протокол обмена сообщениями между прикладной программой и бэкенд-процессом построен по простой схеме «запрос — ответ». Сообщение-запрос содержит идентификатор команды и последовательность байтов, представляющих её аргументы. Сообщение-ответ включает код результата выполнения и, при необходимости, данные, запрошенные данной командой. В отличие от INGRES [STON76] бэкенд не «заполняет» канал связи потоком данных по собственной инициативе. Вместо этого фронтенд запрашивает ограниченный объем данных каждой командой.

5.2. Обработка запросов

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

5.2.1. Поддержка новых типов

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

Основная идея заключается в том, что каждый метод доступа обеспечивает эффективный поиск для определённого набора операторов. Например, в случае B-деревьев такими операторами являются {<, =, >, >=, <=}. Кроме того, эти операторы должны удовлетворять определенному набору правил. Для B-деревьев этот набор имеет следующий вид:

P1) key-1 < key-2 and key-2 < key-3 then key-1 < key-3
P2) key-1 < key-2 implies not key-2 < key-1
P3) key-1 < key-2 or key-2 < key-1 or key-1 = key-2
P4) key-1 <= key-2 if key-1 < key-2 or key-1 = key-2
P5) key-1 = key-2 implies key-2 = key-1
P6) key-1 > key-2 if key-2 < key-1
P7) key-1 >= key-2 if key-2 <= key-1

Метод доступа на основе B-дерева будет работать с любым набором операторов, удовлетворяющих этим правилам. Протокол определения новых операторов будет аналогичен механизму, описанному для ADT-INGRES [STON83c]. После определения операторов пользователю достаточно указать, какой именно набор операторов должен использоваться при построении индекса. Подробный синтаксис этой процедуры приведён в [STON86].

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

relation.column OPR value

Эти два значения могут быть включены в определение каждого оператора OPR. Кроме того, оптимизатору необходима информация о селективности соединений (join selectivity) для каждого оператора, который может участвовать в операции соединения, а также сведения о допустимых стратегиях выполнения соединения. В частности, стратегия вложенных циклов (nested iteration) применима всегда, а стратегии merge join и hash join работают лишь в ограниченном числе случаев. Для каждого оператора оптимизатор должен знать, можно ли использовать merge join (если можно, то какой оператор следует использовать для сортировки каждого отношения) и hash join. Предлагаемый нами протокол включает всю эту информацию непосредственно в описание каждого оператора.

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

5.2.2. Поддержка процедурных данных

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

1. компиляция плана выполнения для команд POSTQUEL

2. выполнение этого плана и получение результата.

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

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

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

Мы предлагаем ввести новый тип блокировок — I-блокировки (I locks). Матрица совместимости I-блокировок приведена на рисунке 4. При компиляции команды или предварительном вычислении результата POSTGRES устанавливает I-блокировки на все объекты базы данных, к которым происходило обращение во время компиляции или выполнения. Такие блокировки должны быть постоянными (то есть сохраняться после аварийного завершения системы), иметь тонкую гранулярность (вплоть до отдельных кортежей или даже полей), поддерживать эскалацию до более грубого уровня, корректно обнаруживать так называемые фантомы (phantoms) [ESWA75]. В работе [STON85a] предлагается наиболее эффективный способ удовлетворить всем этим требованиям — хранить I-блокировки непосредственно внутри записей данных.

Рисунок 4. Матрица совместимости I-блокировок

Символ «*» в таблице совместимости на рисунке 4 означает, что установка блокировки записи (write lock) на объект, уже содержащий одну или несколько I-блокировок, не приводит к конфликту. Вместо этого все предварительно вычисленные объекты, удерживающие эти I-блокировки, просто объявляются недействительными. Поэтому такие блокировки назвали invalidate-me locks («сделай меня недействительным»). Пользователь может выполнить команду

retrieve (relation.I) where qualification

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

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

5.2.3. Оповещатели, триггеры и вывод

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

Оповещатели и триггеры задаются добавлением ключевого слова “always” к соответствующей команде. Предлагаемый способ реализации команд “always” заключается в том, что команда выполняется до тех пор, пока не перестанет оказывать какой-либо эффект. После этого она выполняется ещё один раз, при этом на все объекты, которые команда читает или изменяет, устанавливается специальный тип блокировок — T-блокировки (T locks). Матрица совместимости T-блокировок приведена на рисунке 5. Каждый раз, когда транзакция записывает объект данных, на который установлена T-блокировка, менеджер блокировок просто пробуждает соответствующую команду “always”. Спящие команды “always” хранятся в системном отношении в поле типа POSTQUEL. Как и I-блокировки, T-блокировки должны быть постоянными, иметь тонкую гранулярность и поддерживать эскалацию до более грубых уровней. Кроме того, идентификаторы команд, удерживающих T-блокировки, можно получить через специальное поле T, автоматически добавляемое ко всем отношениям.

Рисунок 5. Матрица совместимости T-блокировок

Напомним, что механизм логического вывода реализуется с помощью виртуальных полей, то есть команд “demand”. Команды “demand” реализуются практически так же, как и команды “always”. Каждая команда “demand” сначала выполняется до тех пор, пока не будет определён набор объектов, которые она предполагает изменить. После этого на каждый такой объект устанавливается D-блокировка (D lock), а сама команда сохраняется в поле типа POSTQUEL системных каталогов. Матрица совместимости D-блокировок приведена на рисунке 6. Символ «&» в этой матрице означает, что если выполняемая команда пытается прочитать объект, на котором установлена D-блокировка, то соответствующая команда “demand” должна быть подставлена в выполняемую команду с помощью алгоритма, аналогичного механизму модификации запросов (query modification), чтобы сформировать новую команду. Полученная команда представляет собой подцель, которую система POSTGRES пытается выполнить. Если при выполнении этой подцели встречается ещё одна D-блокировка, возникает новая подцель. Этот процесс продолжается до тех пор, пока какая-либо подцель не завершится успешно и не сформирует окончательный результат. Кроме того, полученный результат может быть закеширован в поле и при необходимости автоматически аннулирован, если команды промежуточных целей в процессе выполнения устанавливают I-блокировки. Таким образом, механизм работает как разновидность унификации в стиле PROLOG [CLOC81], реализованная на уровне базы данных, и поддерживает вычисления по схеме обратного вывода.

Подробное описание алгоритма и предлагаемая схема назначения приоритетов приведены в [STON85b].

Рисунок 6. Матрица совместимости D-блокировок

5.3. Система хранения данных

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

Все отношения будут храниться в виде куч (heap), как и в [ASTR76], с необязательным набором вторичных индексов. Кроме того, отношения можно объявить «почти упорядоченными», и POSTGRES будет стремиться размещать кортежи как можно ближе к порядку сортировки по заданному столбцу. Наконец, для отношений могут быть созданы вторичные индексы, каждый из которых физически состоит из двух отдельных индексов: один — для кортежей, находящихся на магнитном диске, другой — для размещённых на оптическом диске. Оба индекса хранятся в отдельных файлах файловой системы UNIX на магнитном диске. Кроме того, для каждого отношения автоматически создаётся вторичный индекс по полю уникального идентификатора, которое будет описано в следующем подразделе. Этот индекс позволяет выполнять последовательное сканирование любого отношения.

5.3.1. Формат данных

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

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

• IID — неизменяемый идентификатор данного кортежа;

• tmin — временная метка, начиная с которой данный кортеж считается действительным;

• BXID — идентификатор транзакции, установившей значение tmin;

• tmax — временная метка, после которой данный кортеж становится недействительным;

• EXID — идентификатор транзакции, установившей значение tmax;

• v-IID — неизменяемый идентификатор кортежа в этой или другой версии;

• descriptor — дескриптор, расположенный в начале кортежа.

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

5.3.2. Правила обновления и доступа

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

Чтобы найти все записи, удовлетворяющие условию QUAL в момент времени T, система в рантайме должна найти на магнитном диске все записи, удовлетворяющие одному из следующих условий:

1. tmin < T < tmax, BXID и EXID принадлежат зафиксированным (committed) транзакциям, выполняется условие QUAL;

2. tmin < T, tmax = NULL, BXID принадлежит зафиксированной транзакции, выполняется условие QUAL;

3. tmin < T, BXID принадлежит зафиксированной транзакции, EXID принадлежит незавершённой (not committed) транзакции, выполняется условие QUAL.

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

5.3.3. Журнал POSTGRES и ускоритель транзакций

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

Рассмотрим три идентификатора транзакций:

• T1 — самый «молодой» идентификатор транзакции, который уже был выдан;

• T2 — тоже «молодая» транзакция, но гарантированно более старая, чем самая старая из всех активных транзакций;

• T3 — «молодая» транзакция, которая старше самой старой зафиксированной транзакции, данные которой всё ещё находятся на магнитном диске.

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

Для любой транзакции с идентификатором между T1 и T2 нужно знать, в каком из трёх состояний она находится:

• 0 = отменена (aborted);

• 1 = зафиксирована (committed);

• 2 = выполняется (in progress).

Для транзакций с идентификаторами между T2 и T3 состояние «выполняется» уже невозможно, поэтому журнал можно хранить гораздо компактнее — по одному биту на транзакцию. Для транзакций, более старых, чем T3, процесс vacuum уже успел перенести все соответствующие записи в архивное хранилище. Во время этого процесса все изменения, принадлежащие отменённым транзакциям, могут быть отброшены. Следовательно, все записи, попавшие в архив, принадлежат успешно завершённым транзакциям. Для транзакций, более старых, чем T3, журнал не понадобится.

Предлагаемая структура журнала представляет собой упорядоченное отношение LOG формата:

• line-id — поле упорядочивания, предоставляемое методом доступа;

• bit-1[1000] — битовый вектор;

• bit-2[1000]  — второй битовый вектор.

Состояние транзакции с номером i хранится в бите (с номером остаток от деления i на 1000) в записи журнала с номером i/1000.

Мы предполагаем, что имеется несколько тысяч бит (примерно 1–10 Кбайт) специальной защищённой оперативной памяти, предназначенной для хранения последних 10–100 блоков журнала, образующих его «хвост». Такая память дублируется или даже утраивается и поддерживается источником бесперебойного питания. Предполагаемая аппаратная организация этой памяти выглядит следующим образом. Представим себе кольцевой пул из n блоков, каждый размером 2000 бит. Когда требуется место для нового блока, самый старый блок переиспользуется. Аппаратная часть поддерживает два указателя: первый указывает на текущий максимальный идентификатор транзакции (T1, или high-water mark) и на тот бит, который будет использован следующим, а второй — на самую старую транзакцию, всё ещё находящуюся в буфере (low-water mark), и на соответствующий ей бит. Когда указатель high-water приближается к low-water, один блок журнала должен быть «надёжно» записан на диск и становится частью уже сохранённых блоков журнала. После этого указатель low-water сдвигается на 1000 транзакций вперёд. Указатель high-water, напротив, продвигается каждый раз при запуске новой транзакции. Аппаратная часть должна поддерживать следующие операции:

• сдвинуть high-water  (то есть начать новую транзакцию);

• записать один блок журнала на диск и обновить low-water;

• отменить транзакцию;

• зафиксировать транзакцию.

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

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

Если система выполняет около пяти транзакций в секунду, отношение LOG будет занимать примерно 20 Мбайт в год. Хотя предполагается наличие достаточно большого объема буферной памяти, очевидно, что в системах с очень высокой интенсивностью транзакций невозможно удерживать все необходимые части отношения XACT в оперативной памяти. В этом случае постоянные обращения к журналу для проверки состояния отдельных транзакций становятся слишком дорогими. Именно поэтому POSTGRES предусматривает дополнительный механизм — ускоритель транзакций, который будет описан далее.

Мы ожидаем, что практически все транзакции с идентификаторами между T2 и T3 будут успешно зафиксированы (committed). Поэтому мы будем использовать второе отношение XACT в качестве фильтра Блума (Bloom filter) [SEVR76] для обнаружения отмененных транзакций. Отношение XACT имеет кортежи следующего вида:

• line-id  — поле упорядочивания, предоставляемое методом доступа;

• bitmap[M] — битовый массив размера M.

Для каждой отменённой транзакции, идентификатор которой (XACTID) находится в диапазоне между T2 и T3, необходимо выполнить следующее обновление. Пусть N — число транзакций, приходящихся на одну запись отношения XACT, а LOW = T3 − remainder(T3 / N). 

replace XACT (bitmap[i] = 1)
where XACT.line-id = (XACTID - LOW) modulo N
 and i = hash(remainder((XACTID - LOW) / N))

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

Таким образом, всякий раз, когда системе времени выполнения необходимо определить, была ли некоторая транзакция C-XACTID (лежащая между T2 и T3) успешно зафиксирована или отменена, она проверяет значение

bitmap[ hash (reaminder((C-XACTID - LOW) / N))]

Если в соответствующем бите находится 0, это означает, что C-XACTID обязательно была успешно зафиксирована (committed). Если же обнаруживается 1, то транзакция могла и завершиться успешно, и быть отменена. В этом случае необходимо обратиться к отношению LOG, чтобы определить её истинное состояние.

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

5.3.4. Анализ ускорителя

Предположим, что для буферизации доступно B бит оперативной памяти и M = 1000. Эти B бит могут использоваться либо для хранения части (или всего) отношения LOG, либо для хранения части (или всего) отношения XACT. Кроме того, предположим, что вероятность отмены транзакции равна F, а значение N выбрано таким образом, что в среднем в каждом массиве bitmap установлено X бит. Тогда N = X / F. В этом случае для хранения Q транзакций потребуется Q бит в отношении LOG и Q × F × 1000 / X бит в ускорителе. Если эта величина больше Q, то ускоритель оказывается бесполезным, поскольку занимает больше памяти, чем сам журнал LOG. Поэтому далее предполагается, что F × 1000 / X << 1. В этом случае проверка состояния транзакции по журналу LOG приводит к страничному промаху с вероятностью

FAULT(LOG) = 1 − B / Q

При использовании ускорителя вероятность страничного промаха равнаP(XACT) = 1 − (B × X) / (Q × F × 1000)

С вероятностью X / 1000 в структуре данных ускорителя будет обнаружена единица. Если B < Q × F × 1000 / X, то всё доступное буферное пространство занято ускорителем. В этом случае для окончательной проверки того, была ли транзакция зафиксирована или отменена, неизбежно потребуется обращение к отношению LOG, а значит обязательно произойдёт страничный промах. Следовательно,FAULT(XACT) = P(XACT) + X / 1000.

Если же значение B больше, часть буферной памяти может быть выделена под LOG и вероятность страничного промаха уменьшается.

Разность между вероятностями страничного промаха при использовании журнала и ускорителя delta = FAULT(LOG) − FAULT(XACT) максимизируется при выборе X = 1000 * square-root (F).

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

Рисунок 7. Ожидаемое число ошибок в зависимости от размера буфера

Как видно из графика, ускоритель проигрывает только в том случае, когда объём доступной буферной памяти совсем незначителен или почти достаточен для хранения всего журнала целиком. Кроме того, size (XACT) = square-root (F) * size (LOG), и если B = size(XACT), то вероятность страничного промаха уменьшается с FAULT (LOG) = 1 - square-root (F) до FAULT (XACT) = square-root (F).

Например, если F = 0,01, то требования к объёму буферной памяти уменьшаются в десять раз, а вероятность страничного промаха снижается с 0,9 до 0,1.

Даже если F = 0,1, отношение XACT требует лишь треть того буферного пространства, и при этом вдвое уменьшает вероятность страничного промаха.

5.3.5. Управление транзакциями

Если происходит сбой, при котором содержимое базы данных на диске остаётся неповреждённым, то системе восстановления достаточно продвинуть значение T2 до T1, пометив все транзакции, находившиеся в момент сбоя в состоянии выполнения (in progress), как отменённые (aborted). После этого система может вернуться к обычной работе. Ожидается, что восстановление после подобных «мягких» сбоев будет практически мгновенным.

Защита от «жёстких» сбоев, при которых данные на диске оказываются повреждены, будет обеспечиваться зеркалированием файлов базы данных, размещённых на магнитных дисках, на уровне целых томов (volume by volume) или отдельных файлов (file by file).

Мы предполагаем использовать обычный менеджер блокировок с двухфазным протоколом блокировок, который будет работать как с блокировками чтения (R) и записи (W), так и с блокировками типов I, T и D. Ожидается, что блокировки R и W будут храниться в традиционной таблице блокировок, а все остальные типы блокировок — в записях данных. Единственное расширение, которое мы планируем реализовать, — механизм блокировки объектов (object locking). В этом случае пользователь может объявить, что его хранимые процедуры должны выполняться вообще без каких-либо блокировок. Разумеется, если два пользователя одновременно попытаются выполнить одну и ту же хранимую процедуру, один из них будет заблокирован, поскольку первый исполнитель установит блокировку записи (write lock) на кортеж, содержащий выполняемую процедуру. Таким образом, если группа пользователей гарантирует отсутствие «слепых» обращений (blind accesses) к отдельным частям объекта (то есть никто не обращается напрямую к отношениям, содержащим компоненты объекта, в обход самой процедуры), согласованность данных может быть обеспечена за счёт установки обычных блокировок чтения и записи только на процедурные объекты, без какой-либо блокировки объектов, из которых они состоят.

5.3.6. Методы доступа

Мы предполагаем реализовать вторичные индексы на основе B-деревьев (B-tree) и OB-деревьев (OB-tree) [STON83b]. Кроме того, наш механизм абстрактных типов данных (ADT) поддерживает произвольное множество пользовательских методов индексирования. Каждый такой индекс в действительности представляет собой пару индексов: один — для записей, расположенных на магнитном диске, второй — для архивных записей. Первый индекс имеет структуру index-relation(user-key-or-keys,pointer-to-tuple) и использует ту же организацию, что и вторичные индексы в существующем INGRES. Второй индекс содержит указатели на архивные кортежи и, помимо пользовательских ключей, автоматически включает поля tmin и tmax.

При такой организации запросы, удовлетворяющие условию where relation.key = value интерпретируется как where relation["now"].key = valueи требуют обращения только к индексу магнитного диска. Более общий запрос вида where relation[T].key = value требует поиска как по индексу магнитного диска, так и по архивному индексу.

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

Любая команда POSTQUEL Replace создаёт новую запись данных с соответствующими значениями BXID и tmin, добавляет записи во все определённые ключевые индексы и изменяет значение tmax у обновляемого кортежа. Команда POSTQUEL Append выполняет только первый и второй шаги, а команда Delete — только третий. Если хранить указатель от старого кортежа к новому, POSTGRES сможет обновлять только те индексы, ключевые поля которых действительно изменились. Такая оптимизация позволяет значительно сократить число операций записи на диск ценой некоторого увеличения сложности выполнения. Мы планируем реализовать именно эту оптимизацию.

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

order page1, page2

Неудачный сбой может оставить многоуровневое дерево индекса в состоянии, когда некоторые страницы индекса оказываются висячими, то есть на них больше не указывает ни одна другая страница дерева. Аналогичным образом в куче могут остаться незавершённые записи данных, до которых невозможно добраться через некоторые индексы. Такие «висячие» кортежи будут удаляться процессом vacuum, поскольку поле EXID у них будет содержать значение not committed. К сожалению, если такие записи отсутствуют во всех индексах, для их обнаружения придётся периодически полностью сканировать память. Висячие страницы индекса должны удаляться традиционными методами сборки мусора.

Упорядоченные отношения создают в нашей системе особую проблему. Для её решения мы предлагаем немного изменить структуру OB-деревьев. В частности, каждое место, где в исходной работе [STON83b] использовался счётчик количества идентификаторов кортежей в поддереве, предлагается заменить следующей структурой:

• counter-1 — тот же счётчик, что и раньше;

• flag — бит опасности (danger bit).

Каждая операция вставки или удаления в OB-дереве при изменении counter-1 устанавливает бит опасности. Если операция чтения обнаруживает, что у некоторого элемента установлен этот бит, выполнение алгоритма временно прерывается. После этого считывающий процесс заново вычисляет значение counter-1, проходя вниз по дереву. Затем он возвращается вверх, обновляя значение counter-1 и одновременно сбрасывая бит опасности. После завершения этой процедуры выполнение первоначального алгоритма продолжается. Таким образом, каждая следующая транзакция автоматически исправляет структуру дерева, оставшуюся в промежуточном состоянии после предыдущей операции вставки или удаления.

5.3.7. Очистка диска

Любую запись с успешно зафиксированными (committed) транзакциями BXID и EXID можно перенести на оптический диск или другой носитель для долговременного хранения. Кроме того, все записи, у которых BXID или EXID относятся к отменённым (aborted) транзакциям, можно удалить. Эти две задачи выполняет специальный демон vacuum. В результате число записей, остающихся на магнитном диске, практически совпадает с числом записей, у которых поле EXID равно нулю. Другими словами, магнитный диск хранит текущее состояние базы данных. Архивное хранилище, напротив, содержит исторические записи, при этом процесс vacuum гарантирует, что все архивные записи корректны. Следовательно, системе POSTGRES в рантайме никогда не приходится проверять корректность архивных записей.

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

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

Некоторые пользователи могут захотеть, чтобы недавно изменённые записи некоторое время оставались на магнитном диске. Для этого предлагается разрешить пользователю задавать правило работы процесса vacuum следующей командой: vacuum rel-name where QUAL

Разумным примером такого условия может быть vacuum rel-name where rel-name.tmax < now - 20 days.

В этом случае процесс очистки не будет удалять записи из магнитной копии отношения rel-name, пока указанное условие не станет истинным.

5.3.8. Управление версиями

Версии будут реализованы путём создания дифференциального файла [SEVR76] для каждой отдельной версии. Дифференциальный файл будет содержать кортежи, которые были добавлены или удалены относительно базового отношения. Для каждой версии будут строиться вторичные индексы, аналогичные индексам базового отношения, на основе которого эта версия была создана.

Алгоритм выполнения команд POSTQUEL над версиями начинается с просмотра дифференциального отношения, соответствующего самой версии. Для каждого кортежа, удовлетворяющего условию запроса, значение его v-IID заносится в список «уже просмотренных идентификаторов» [WOOD83]. Если позднее встречается кортеж, чей IID уже присутствует в этом списке, такой кортеж отбрасывается. Поскольку кортежи просматриваются в обратном хронологическом порядке, сначала всегда обнаруживается самая новая версия кортежа, после чего становится понятно, что все более ранние варианты следует игнорировать. Если рассматриваемая версия построена поверх другой версии, обработка продолжается в дифференциальном файле следующей версии. В конечном итоге достигается базовое отношение, после чего процесс завершается.

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

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

• если это вставка (insert), добавить запись в более старую версию;

• если это удаление (delete), удалить соответствующую запись из более старой версии;

• если это обновление (replace), выполнить последовательность из вставки и удаления.

Конфликт возникает в том случае, если попытаться удалить запись, которая уже была удалена. Подобные ситуации должны разрешаться вне рамок самого алгоритма. Для разрешения таких конфликтов могут оказаться полезными методы, описанные в работе [GARC84].

Более старую версию можно прокрутить вперёд до более новой, выполнив описанные выше операции, а затем просто переименовав старую версию.

6. Резюме

POSTGRES предлагает поддержку сложных объектов за счёт расширяемой системы типов, позволяющей определять новые типы столбцов отношений, операторов для работы с этими столбцами и методы доступа. Такой механизм хорошо подходит для сравнительно «простых» сложных объектов. Более сложные объекты, особенно содержащие разделяемые подобъекты или несколько уровней вложенности, рекомендуется определять с помощью процедур POSTGRES. Процедуры оптимизируются путём кеширования как скомпилированных планов выполнения, так и готовых результатов.

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

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

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

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

Литература

1. [ADIB80] Adiba, M.E. and Lindsay, B.G., "Database Snapshots," IBM San Jose Res. Tech. Rep. RJ-2772, March 1980.

2. [AFSA85] Afasarmanesh, H., et. al., "An Extensible Object-Oriented Approach to Database for VLSI/CAD," Proc. 1985 Very Large Data Base Conference, Stockholm, Sweden, August 1985.

3. [ALLM76] Allman, E., et. al., "Embedding a Relational Data Sublanguage in a General Purpose Programming Language," Proc. 1976 ACM-SIGPLAN-SIGMOD Conference on Data, Salt Lake City, Utah, March 1976.

4. [ASTR76] Astrhan, M. et. al., "System R: A Relational Approach to Data," ACM-TODS, June 1976.

5. [ATKI84] Atkinson, M.P. et. al., "Progress with Persistent Programming," in Database, Role and Structure (ed. P. Stocker), Cambridge University Press, 1984.

6. [BUNE79] Bunemann, P. and Clemons, E., "Efficiently Monitoring Relational Data Bases," ACM-TODS, Sept. 1979.

7. [CLOC81] Clocksin, W. and Mellish, C., "Programming in Prolog," Springer-Verlag, Berlin, Germany, 1981.

8. [CODD70] Codd, E., "A Relational Model of Data for Large Shared Data Bases," CACM, June 1970.

9. [COPE84] Copeland, G. and D. Maier, "Making Smalltalk a Database System," Proc. 1984 ACM-SIGMOD Conference on Management of Data, Boston, Mass., June 1984.

10. [DERR85] Derritt, N., Personal Communication, HP Laboratories, October 1985.

11. [DEWI85] DeWitt, D.J. and Carey, M.J., "Extensible Database Systems," Proc. 1st International Workshop on Expert Data Bases, Kiowah, S.C., Oct. 1984.

12. [ESWA75] Eswaren, K., "A General Purpose Trigger Subsystem and Its Inclusion in a Relational Data Base System," IBM Research, San Jose, Ca., RJ 1833, July 1976.

13. [GARC84] Garcia-Molina, H., et. al., "Data-Patch: Integrating Inconsistent Copies of a Database after a Partition," Tech. Rep. TR# 304, Dept. Elec. Eng. and Comp. Sci., Princeton Univ., 1984.

14. [HELD75] Held, G. et. al., "INGRES: A Relational Data Base System," Proc. 1975 National Computer Conference, Anaheim, Ca., June 1975.

15. [GUTM84] Gutman, A., "R-trees: A Dynamic Index Structure for Spatial Searching," Proc. 1984 ACM-SIGMOD Conference on Management of Data, Boston, Mass., June 1984.

16. [JARK85] Jarke, M. et. al., "Data Constructors: On the Integration of Rules and Relations," Proc. 1985 Very Large Data Base Conference, Stockholm, Sweden, August 1985.

17. [KATZ85] Katz, R.H., Information Management for Engineering Design, Springer-Verlag, 1985.

18. [KUNG84] Kung, R. et. al., "Heuristic Search in Database Systems," Proc. 1st International Workshop on Expert Data Bases, Kiowah, S.C., Oct. 1984.

19. [LORI83] Lorie, R., and Plouffe, W., "Complex Objects and Their Use in Design Transactions," Proc. Eng. Design Applications of ACM-IEEE Data Base Week, San Jose, CA, May 1983.

20. [LUM85] Lum, V., et. al., "Design of an Integrated DBMS to Support Advanced Applications," Proc. Int. Conf. on Foundations of Data Org., Kyoto Univ., Japan, May 1985.

21. [ROBI81] Robinson, J., "The K-D-B Tree: A Search Structure for Large Multidimensional Indexes," Proc. 1981 ACM-SIGMOD Conference on Management of Data, Ann Arbor, Mich., May 1981.

22. [ROWE79] Rowe, L.A. and Shoens, K., "Data Abstraction, Views, and Updates in Rigel," Proc. 1979 ACM-SIGMOD Conference on Management of Data, Boston, MA, May 1979.

23. [ROWE82] Rowe, L.A. and Shoens, K., "FADS - A Forms Application Development System," Proc. 1982 ACM-SIGMOD Conference on Management of Data, Orlando, FL, June 1982.

24. [ROWE85] Rowe, L., "Fill-in-the-Form Programming," Proc. 1985 Very Large Data Base Conference, Stockholm, Sweden, August 1985.

25. [SELI79] Selinger, P. et. al., "Access Path Selection in a Relational Data Base System," Proc. 1979 ACM-SIGMOD Conference on Management of Data, Boston, Mass., June 1979.

26. [SEVR76] Severence, D., and Lohman, G., "Differential Files: Their Application to the Maintenance of Large Databases," ACM-TODS, June 1976.

27. [STON75] Stonebraker, M., "Implementation of Integrity Constraints and Views by Query Modification," Proc. 1975 ACM-SIGMOD Conference, San Jose, Ca., May 1975.

28. [STON76] Stonebraker, M., et. al., "The Design and Implementation of INGRES," ACM-TODS, September 1976.

29. [STON81] Stonebraker, M., "Operating System Support for Database Management," CACM, July 1981.

30. [STON83a] Stonebraker, M., et. al., "Performance Analysis of a Distributed Data Base System," Proc. 3rd Symposium on Reliability in Distributed Software and Data Base Systems, Clearwater, Fla., Oct. 1983.

31. [STON83b] Stonebraker, M., "Document Processing in a Relational Database System," ACM TOOIS, April 1983.

32. [STON83c] Stonebraker, M., et. al., "Application of Abstract Data Types and Abstract Indexes to CAD Data," Proc. Engineering Applications Stream of 1983 Data Base Week, San Jose, Ca., May 1983.

33. [STON84a] Stonebraker, M. et. al., "QUEL as a Data Type," Proc. 1984 ACM-SIGMOD Conference on Management of Data, Boston, Mass., June 1984.

34. [STON84b] Stonebraker, M. and Rowe, L.A., "PORTALS: A New Application Program Interface," Proc. 1984 VLDB Conference, Singapore, Sept. 1984.

35. [STON85a] Stonebraker, M., "Extending a Data Base System with Procedures," (submitted for publication).

36. [STON85b] Stonebraker, M., "Triggers and Inference in Data Base Systems," Proc. Islamoora Conference on Expert Data Bases, Islamoora, Fla., Feb. 1985, to appear as a Springer-Verlag book.

37. [STON85c] Stonebraker, M. et. al., "An Analysis of Rule Indexing Implementations in Data Base Systems," (submitted for publication).

38. [STON86] Stonebraker, M., "Inclusion of New Types in Relational Data Base Systems," Proc. Second International Conference on Data Base Engineering, Los Angeles, Ca., Feb. 1986.

39. [TICH82] Tichy, W.F., "Design, Implementation, and Evaluation of a Revision Control System," Proc. 6th Int. Conf. on Soft. Eng., Sept. 1982.

40. [TSIC82] Tsichritzis, D.C., "Form Management," CACM 25, July 1982.

41. [ULLM85] Ullman, J., "Implementation of Logical Query Languages for Data Bases," Proceedings of the 1985 ACM-SIGMOD International Conference on Management of Data, Austin, TX, May 1985.

42. [WONG84] Wong, E., et al., "Enhancing INGRES with Deductive Power," Proceedings of the 1st International Workshop on Expert Data Base Systems, Kiowah SC, October 1984.

43. [WOOD83] Woodfill, J. and Stonebraker, M., "An Implementation of Hypothetical Relations," Proc. 9th VLDB Conference, Florence, Italy, Dec. 1983.

44. [ZANI83] Zaniolo, C., "The Database Language GEM," Proc. 1983 ACM-SIGMOD Conference on Management of Data, San Jose, Ca., May 1983.