- Модифицируемость и уничтожаемость версий
- Идентификаторы версий
- Иерархия вывода версий
- Параметризуемое управление версиями
Технологии реляционных баз данных на сегодняшний день являются доминирующими, если исходить из числа установок продуктов. В течение последних лет активно развивалась технология объектно-ориентированных баз данных, направленная отчасти на преодоление недостатков реляционной модели данных. Хотя коммерческие объектно-ориентированные СУБД не завоевали значительных успехов на рынке, наиболее важные их аспекты несомненно найдут отражение в реализациях новых версий реляционных баз данных. Фундаментом технологий баз данных нового поколения станет сочетание отношений и объектов. Но и этот фундамент будет нуждаться в расширениях, направленных на решение по крайней мере четырех важнейших проблем - управление мультимедийными данными, долговременными транзакциями, пространственными данными, хронологическими данными. В последние 10-20 лет в этих областях проводились интенсивные исследования и были получены многие полезные результаты. Тем не менее сегодня лишь немногие промышленные СУБД включают средства для решения какой-либо из этих проблем. Цель настоящей статьи - сформулировать ряд предметов для краткосрочных исследований и разработок, которые могли бы стать основой для решений перечисленных проблем, пригодных к реализации в коммерческих СУБД. По каждой из проблем мы дадим обзор предпосылок и практических целей и либо сформулируем конкретное предложение, являющееся базой для реализации, либо приведем список тем для краткосрочных исследований, направленных на ее решение.
1. Введение
В последнее время на рынке появились объектно-ориентированные СУБД и сопутствующие инструментальные средства - отчасти в ответ на ожидаемый рост использования объектно-ориентированных языков, а отчасти как попытка преодолеть некоторые существенные недостатки реляционных баз данных, связанные с внутренними ограничениями реляционной модели. Хотя эти продукты не получили значительного распространения на рынке, они тем не менее внесли вклад в наше понимание преимуществ объектно-ориентированного подхода к проектированию баз данных и управлению ими. Это привело к тому, что многие поставщики реляционных баз данных сейчас планируют дополнить свои продукты объектно-ориентированными средствами проектирования и управления базами данных. В то же время поставщики объектно-ориентированных баз данных осознали, что основное препятствие к рыночному успеху для них - это отсутствие поддержки полномасштабного непроцедурного языка запросов, совместимого с ANSI SQL, и предполагают дополнить свои системы таким языком запросов. Компания UniSQL разработала систему баз данных и средства разработки приложений как раз такого типа, к которому стремятся привести свои продукты поставщики и реляционных, и объектно-ориентированных баз данных.
Очевидно, что основу СУБД нового поколения составят технологии, объединяющие черты реляционных и объектно-ориентированных баз данных, т. е. реляционных баз данных, расширенных понятиями инкапсуляции (методов), призвольных типов данных, вложенных объектов и наследования, или, наоборот, объектно-ориентированных баз данных, дополненных непроцедурным языком запросов, совместимым с ANSI SQL, и множеством средств, имеющихся в современных реляционных базах данных (таких как автоматическая оптимизация запросов, представления, ограничения, управление метаданными, полномочия доступа, триггеры, управление транзакциями, двухфазовая фиксация транзакций, параметризуемая настройка производительности и т. д.).
Система баз данных - это инструмент, при помощи которого разработчики создают приложения, и компоненты СУБД времени выполнения входят в состав приложений. Таким образом, если в СУБД нет какого-либо необходимого средства, то разработчики вынуждены заниматься его реализацией в рамках своего приложения. В современных СУБД отсутствует ряд важных возможностей, часто требующихся как при разработке приложений, так и для поддержки их выполнения. К числу таких возможностей относятся управление мультимедийными данными, управление долговременными транзакциями, поддержка пространственных данных и хронологических данных (исторических данных и управления версиями). На изучение этих были направлены интенсивные усилия исследователей. Однако сегодня существует лишь очень небольшое число продуктов, в которых поддерживается хотя бы одна их этих возможностей. UniSQL и ORION (ITASCA) [49] поддерживают средства управления мультимедийными данными. В ORION [32] и Versant реализован один аспект управления долговременными транзакциями, а именно механизм перемещения объекта из базы данных общего пользования в личные базы данных и обратно (checkout/checkin). ORION [10] и Versant поддерживают версии простых объектов (отдельных записей).
Планы исследований и разработок ведущих поставщиков реляционных и объектно-ориентированных баз данных, работы комитета по стандартам ANSI SQL-3 и многие другие факторы показывают, что базы данных нового поколения будут опираться на объединение реляционной и объектно-ориентированной моделей данных. Мы убеждены также, что новое поколение баз данных, основанных на этом фундаменте, будет включать поддержку мультимедийных данных, долговременных транзакций, пространственных и хронологических данных. СУБД UniSQL - первая коммерческая реляционная и объектно-ориентированная система баз данных. Она уже включает мощные средства для управления мультимедийными данными, а в новые версии, которые появятся в 1994-95 гг., войдет поддержка долговременных транзакций, пространственных и хронологических данных. Настоящая статья представляет собой, по существу, план исследований и разработок для UniSQL на ближайшие несколько лет.
Мы полагаем, что накопленных результатов исследований в целом достаточно для реализации всех перечисленных средств в коммерческих СУБД. Тем не менее необходимы некоторые дополнительные изыскания, которые должны развиваться по двум направлениям. Одно направление - это критическая оценка лучших из известных результатов по критериям полезности и практической реализуемости. Это, видимо, приведет к пересмотру (и, возможно, отрицанию) отдельных результатов. Другое направление - это решение еще ряда задач из относительно небольшого списка.
В своей статье мы приводим темы для краткосрочных исследований по каждой из четырех упомянутых выше областей, с учетом задачи реализации соответствующих средств в коммерческих СУБД. По каждой из областей дается обзор преследуемых практических целей и либо формулируется конкретное предложение, являющееся базой для реализации, либо приводится список тем для краткосрочных исследований.
2. Управление мультимедийными данными
В компьютерной индустрии наблюдается усиливающаяся тенденция поддержки нечисловых данных. Доступность недорогих устройств для запечатления информации (цифровые камеры, цифровые сканеры, цифровые аудиоустройства и т. п.) в сочетании с дешевой массовой памятью (цифровые аудиоленты, оптические диски), а также дисплейные устройства высокого разрешения создали предпосылки для возникновения нового класса компьютерных приложений, оперирующих с мультимедийными данными. Мультимедийные приложения распространяют концепцию гипертекста на множество новых типов данных помимо текстового - аудиоданные, графические образы, видео, анимация.
Многие коммерческие СУБД проигрывают из-за отсутствия поддержки произвольных типов данных, данных неограниченного размера и данных, хранящихся на устройствах, отличных от магнитных дисков. Они умеют работать с весьма ограниченным набором типов данных, таких как целые числа и числа с плавающей точкой, даты, денежные суммы, текстовые цепочки и большие бинарные объекты (BLOB - Binary Large Object). Кроме того, они не приспособлены для работы с данными, хранимыми на приобретающих все большее распространение носителях типа CD-ROM или видеодисках.
В этом разделе дается обзор основных целей управления мультимедийными данными, представлены решения, реализованные в СУБД UniSQL, и приведен список направлений для исследований и дальнейших разработок.
2.1. Определения и требования
В общем случае работа с мультимедийными данными требует поддержки произвольных типов данных и данных из произвольных источников. К произвольным типам данных относятся числовые и текстовые данные, поддерживаемые традиционными СУБД; большие неструктурированные объекты - текст, графический образ, видео, анимация и т. п.; сложные структурированные данные - диаграммы, графики, таблицы, массивы и т. п.; составные документы, которые объединяют элементы данных всех этих типов. К произвольным источникам данных относятся собственная база данных; внешние (удаленные) базы данных; файловая система; устройства ввода, хранения и представления (вывода) данных; наконец, программы генерации и потребления данных (например система обработки текстов).
Из приведенных выше определений вытекает следующий список требований к управлению мультимедийными данными.
- Способность воспроизводить произвольные типы данных (включая составные документы) и средства спецификации программ (процедур), взаимодействующих с произвольными источниками данных.
- Выполнение запросов, модификаций, вставок, удалений по отношению к мультимедийным данным (включая выборку мультимедийных данных на основе ассоциативного поиска внутри них, как минимум, для текста).
- Спецификация и выполнение абстрактных операций над мультимедийными данными, например "проигрывание", "быстрый прогон вперед", "пауза", "перемотка" для одномерных данных типа текстовых или аудиозапись; "показ", "расширение", "сжатие" для двумерных данных типа растрового представления графического образа.
- Единообразный способ работы с разнородными источниками данных; здесь подразумевается универсальность доступа и возможность миграции данных с одного источника на другой.
2.2. Средства работы с мультимедийными данными в СУБД UniSQL
СУБД UniSQL спроектирована с учетом всех перечисленных выше требований. СУБД ORION представляла собой предварительный вариант системы, где были реализованы некоторые из этих требований, в частности абстрактные типы данных, запросы к мультимедийным данным и манипулирование ими, абстрактные операции над мультимедийными данными [49]. Объектно-ориентированный базис UniSQL позволяет определять произвольные типы данных, помимо типов, поддерживаемых традиционными СУБД. В UniSQL также решена проблема данных произвольного размера на произвольных носителях при помощи менеджера расширенной памяти (ESM - Extended Memory Manager). ESM по существу является глобальным контроллером для произвольных менеджеров памяти. Как показано на рисунке 1, ESM состоит из менеджеров памяти трех типов - менеджера больших объектов (LOM - Large Object Manager), который управляет большими объектами в собственной базе данных (на магнитных дисках); менеджера интерфейса с файловой системой (FBOM - File Based Object Manager), который управляет объектами, хранящимися в файлах; менеджера агентов (AM - Agent Manager), который контролирует произвольные пользовательские программы, производящие доступ к данным или генерирующие их.
Рисунок 1.
ESM как глобальный контроллер менеджеров памяти.
С точки зрения ESM, менеджер памяти - это просто драйвер устройства, на котором хранятся объекты произвольных размеров, структур и типов. ESM, в частности, расширяет функциональность базы данных, обеспечивая хранение и выборку больших объектов (текстовых документов, графических образов, сегментов аудиоинформации), которые были созданы и записаны в рамках файловых систем. Тем самым исключается необходимость предварительной загрузки файлов в базу данных, для того чтобы данные файла можно было использовать совместно с форматированными записями, хранящимися в базе. Компонент LOM был создан для повышения гибкости и эффективности хранения и выборки больших объектов за счет предоставления специализированных структур данных и алгоритмов. FBOM можно рассматривать как альтернативную реализацию LOM, предназначенную для работы с большими объектами, которые были созданы и будут продолжать использоваться в рамках другой (файловой) парадигмы хранения данных, отличной от парадигмы базы данных.
Обобщенные большие объекты
Мы объединили обычные большие объекты (LO - Large Object) и файловые объекты (FBO - File Based Objects) в общую конструкцию обобщенного большого объекта (GLO - General Large Object). GLO - это системный класс с соответствующими операциями (методами) для доступа к объектам и их модификации. Обобщив LO и GLO, мы упростили пользовательский интерфейс за счет выделения общего подмножества функций для этих классов. Среди операций класса GLO - чтение, запись, уничтожение, усечение, вставка, дописывание и др.
Нетрудно создать составные объекты, включающие GLO. Пример составного объекта - объект с информацией об архитектурном памятнике, который содержит описание и архитектурный образ. Атрибутами такого объекта могли бы быть type_of_image (тип графического образа), type_of_structure (тип структуры хранения), architect (фамилия архитектора), construction_ date (дата сооружения), ассоциированные с образом архитектурного памятника, хранимым в GLO. В запросах могут участвовать компоненты, отличные от GLO.
Как и обычные объекты, объекты GLO перед чтением или изменением блокируются. Транзакции, в которых модифицируются объекты GLO, могут быть зафиксированы или прерваны. В частности, изменения, сделанные в объектах GLO, могут быть ликвидированы при прерывании транзакции или при восстановлении базы после краха системы.
Управление программами посредством агентов
Как упоминалось выше, агенты предоставляют интерфейс к произвольным программам, которые осуществляют доступ к данным или генерируют их. Благодаря этим компонентам появляется возможность воспринимать данные, генерируемые программным способом, а также возбуждать внешние процессы при доступе к определенным данным.
В UniSQL определен системный класс агентов с заданными методами. Пользователи могут создавать экземпляры объектов этого класса так же, как и экземпляры объектов любого пользовательского класса. Пользователь имеет возможность описать путем наследования от системного класса свой класс агентов, приспособленных для нужд приложения. Среди предопределенных методов системного класса агентов - запуск, приостановка, возобновление, терминирование.
Наиболее существенные атрибуты агента - команда shell, список объектов GLO, имя хоста. Атрибут команда shell - это определенным образом отформатированная строка, содержащая текст команды Unix (или имя программы), которую нужно запустить. Формат строки сходен с форматом первого аргумента команды printf в языке C - строка может содержать заполнители, соответствующие объектам GLO, с которыми будет взаимодействовать агент. Атрибут список объектов GLO содержит имена объектов GLO, которые подставляются в строку команды shell, перед тем как передать ее на выполнение интерпретатору. Третий атрибут задает имя хоста, на котором нужно запустить полученную команду shell.
Функциональность GLO и функциональность агентов реализованы в виде отдельных компонентов СУБД UniSQL. На рисунке 2 показано взаимодействие разных компонентов ESM и их отношение в типичной конфигурации клиент-сервер. Менеджер больших объектов LOM реализован на серверной стороне, а менеджер агентов (AM) и менеджер файловых объектов (FBOM) выполняются на клиентской стороне.
Рисунок 2.
Типичная конфигурация системы и расположение компонентов ESM.
Миграция объектов
В мультимедийной среде возможны три вида миграции данных: "запечатление" данных, воспроизведение (представление) данных, перемещение данных. При запечатлении объект данных перемещается с устройства запечатления в память или даже сразу на устройство воспроизведения (например аудиоданные направляются с микрофона на устройство голосового воспроизведения). При воспроизведении данные поступают из памяти или с устройства запечатления на воспроизводящее устройство. При перемещении данные переносятся с устройства хранения на другое (или на то же самое) устройство хранения (допустим перепись файлового объекта из файла в базу данных, или перепись объекта базы данных в файл, или запись в файл объекта, отфильтрованного посредством процесса и т. п.).
Запечатление данных. Запечатление данных - это просто занесение данных в объект GLO. Такое действие производится в разные моменты жизни GLO. После создания объекта данные в него могут быть занесены процедурой инициализации, которая либо записывает данные, предопределенные по умолчанию, либо служит для указания о том, что данный объект является FBO или LO. В случае FBO начальные данные, вероятно, уже существуют в файле и доступны для непосредственного использования. Если это объект LO, то инициализирующая процедура должна занести в него какие-либо начальные данные. После создания (и, возможно, инициализации) пользователь может добавлять, удалять, замещать данные.
Запечатление данных производится с одного из множества типов источников данных посредством "настроенного" на него агента. Так, агент может быть процессом, который управляет fax-аппаратом, или процессом, осуществляющим ввод аудиоинформации с микрофона.
Воспроизведение данных. На основе предопределенной в UniSQL встроенной иерархии классов мультимедиа возможно определение новых классов для представления разнообразных типов данных.
Например, класс аудиообъектов в UniSQL описывает интерфейс для воспроизведения аудиоинформации. Пользователь может настроить имеющийся интерфейс, определив требования к аппаратуре в виде дополнительных атрибутов в подклассе, наследуемом от системного класса аудиообъектов.
Перемещение данных. Существует множество осмысленных комбинаций источников и получателей для миграции данных в богатой мультимедийной среде, где поддерживается совместимый доступ к разным источникам данных. Ниже приведены некоторые примеры перемещений данных, представляющие очевидный интерес:
LO в FBO
FBO в LO
LO в LO
FBO в FBO
Миграция объектов реализуется как функция специального агента, которому нужно указать источник и потребитель данных. Агент, атрибут строка shell которого содержит значение "MIGRATE", сообщит Менеджеру агентов, что нужно скопировать данные из первого объекта GLO в атрибуте список объектов GLO во второй объект GLO этого списка.
2.3. Направления исследований и разработок
Тот факт, что для управления мультимедийными данными нужно уметь обрабатывать помимо обычных типов данных еще и большие неструктурированные объекты, влечет за собой необходимость пересмотра единиц данных, с которыми имеют дело механизмы управления полномочиями и управления одновременным доступом. Управление одновременным доступом в традиционных базах данных производится на уровне страниц или даже целых таблиц, а не на уровне отдельных записей. Единица управления полномочиями - это обычно таблица или столбец, но опять же не отдельная запись. В мультимедийной среде логической единицей доступа является объект, такой как, например, составной документ, поэтому единицей управления полномочиями и согласования одновременного доступа в этой среде должен быть отдельный объект (т. е. сущность, сравнимая с записью в реляционной базе данных).
Источник мультимедийных данных, скажем устройство приема информации со спутника, может порождать данные в таком темпе, что система баз данных не в состоянии будет обрабатывать их в режиме реального времени. Следовательно, нужно более пристальное исследование взаимоотношений между СУБД и источниками мультимедийных данных, так чтобы обеспечить какую-то степень совмещения ввода и вывода в реальном времени с обработкой данных (выполнением запросов и модификаций).
В некоторых ситуациях возникает необходимость синхронизировать воспроизведение мультимедийных данных для пользователя. Пример - синхронизация воспроизведения аудио и видеоданных. Потребность синхронизации создает временные зависимости в конкретном акте воспроизведения данных. При этом подразумевается определенный уровень кооперации между разными механизмами презентации для разных типов данных. В какой-то мере эту проблему можно отнести к специфическим проблемам приложений, поскольку для каждого мультимедийного приложения характерны индивидуальные требования по синхронизации.
3. Долговременные транзакции
Цель механизма долговременных транзакций - моделирование долговременных интерактивных сеансов взаимодействия с базой данных в прикладной среде. В такой ситуации неприменимо фундаментальное предположение о кратковременном характере транзакций, которое лежит в основе традиционной модели. Реализация традиционной модели транзакций в условиях долговременных сеансов приведет к недопустимо длительным задержкам транзакций, пытающихся установить блокировки для доступа к данным, и может привести к большим потерям выполненных действий, когда транзакция прерывается по инициативе пользователя или в результате системного сбоя.
В литературе предлагается много подходов к проблеме управления долговременными транзакциями. Следует отметить, что существует определенная путаница относительно этого понятия. Тому есть, по крайней мере, две причины. Во-первых, различается множество вариантов и оттенков того, что называют долговременными транзакциями - транзакции интерактивно работающих пользователей, транзакции кооперативно работающих пользователей, простые длительно выполняющиеся транзакции, транзакции, которые можно представить в виде последовательностей хорошо определенных субтранзакций, транзакции, соответствующие иерархической организации пользователей в терминах выполняемых ими ролей, и т. п. Во-вторых, предлагаемые модели долговременных транзакций разрабатывались, в основном, в расчете на обеспечение максимальной гибкости взаимодействия пользователей, но без рассмотрения тех критериев согласованности, которым они должны удовлетворять.
Цель выработки модели транзакции - предоставить строгую основу для автоматического поддержания согласованного состояния базы данных в условиях, когда одновременно выполняется множество операций чтения и записи и при этом существует возможность системных сбоев [21, 8]. Критерий согласованности, принятый в традиционных базах данных, - это сериализуемость. Сериализуемость поддерживается в них при помощи механизма блокировок, служащего для управления одновременным доступом, и механизма журнализации, который обеспечивает восстановление после сбоев. "Транзакции", которые не предполагают автоматического контроля согласованности базы данных, в сущности нельзя назвать транзакциями. Необязательно принимать в качестве критерия согласованности для долговременных транзакций именно сериализуемость, но какой-то критерий согласованности для них должен предусматриваться.
Выделяются две принципиально различных модели долговременных интерактивных сеансов взаимодействия с базами данных: модель единой базы данных и модель множества баз данных. Модель единой базы данных соответствует ситуации, когда множество транзакций разделяют одну общую базу. Модель множества баз данных охватывает ситуацию, когда множество транзакций оперирует с множеством баз данных.
Наибольшее число исследований в этой области посвящено модели одной базы данных. В большинстве работ основное внимание сфокусировано на двойственной проблеме длительных задержек и потерь результатов выполнения операций, которые характерны для долговременных транзакций [1, 19, 35, 36, 13, 15, 46, 12, 26].
Модель множества баз данных представлена предложениями для архитектур, где имеется разделяемая и несколько частных баз данных и поддерживаются операции взятия (check out) данных из разделяемой базы в частные и возврата (check in) данных из частных баз в разделяемую [28, 30, 34, 32]. Каждый пользователь может иметь свою частную базу с данными, взятыми из разделяемой базы, и модифицировать эти данные, а затем возвращать их в разделяемую базу.
Для построения модели одной базы данных необходимо определить понятие согласованности базы данных, протоколы управления одновременным доступом и протоколы восстановления, отличные от тех, которые приняты в традиционных СУБД. Если мы хотим поддерживать некоторое "разумное" понятие согласованности (т. е. такое, которое могло бы обеспечиваться автоматически), то нужно рассмотреть "конфликтные" ситуации, когда одна транзакция вступает в конфликт с другой по доступу к данным. Если мы хотим избежать длительных ожиданий, то следует принять некоторый механизм разрешения конфликтов путем "торга", при этом пользователям приходится иметь дело с тонкостями механизма управления одновременным доступом. Модель единой базы данных подходит преимущественно для ситуаций, когда трудно заранее выделить какие-то логические разделы базы данных, соответствующие выполняемым заданиям, и пользователи тесно сотрудничают в процессе работы.
Модель множества баз данных может быть полезна для "обхода" конфликтных ситуаций, присущих долговременным сеансам взаимодействия с базой данных. Поскольку каждый пользователь имеет возможность копировать данные из разделяемой базы данных и работать со своей частной базой, не связанной (по крайней мере явно) с общей разделяемой базой, то тем самым он избегает конфликтов. Например, несколько пользователей могут одновременно модифицировать одни и те же данные, не дожидаясь, пока остальные завершат свои изменения. Но, когда придет время возвращать измененные данные в общую базу, они войдут в нее в виде новой версии, для чего необходим механизм управления версиями [10, 11, 29]. Далее если данные в частной базе содержат ссылки на данные из разделяемой базы или наоборот, то частная база данных фактически оказывается подключенной к разделяемой. Например, выполнение запроса в общем случае требует доступа и к частной, и к разделяемой базам данных, даже если запрос сформулирован в терминах одной только частной базы [32]. Модель множества баз данных предпрочтительнее в тех ситуациях, когда заранее легко выделить логические разделы базы данных, соответствующие предполагаемым заданиям, и пользователи не могут или не должны кооперироваться при их выполнении.
Обе модели долговременных транзакций корректны, каждая из них имеет преимущества в определенных обстоятельствах. Поэтому в СУБД общего назначения обе они должны поддерживаться. Соотношение между моделью одной базы данных и моделью множества баз данных такое же, как между подходами одной версии и множества версий в управлении одновременным доступом [7]. Остаток этого раздела посвящен предложениям для этих двух моделей. Первое - это механизм кооперативных транзакций для модели одной базы данных. Во втором описывается архитектура разделяемой/частных баз данных для поддержки модели множества баз данных.
В литературе можно найти также различные предложения для вложенных (составных) транзакций. Понятие составной транзакции аналогично идее составных сложных объектов в моделировании данных. Транзакция может рекурсивно запустить (разветвиться в) несколько субтранзакций, которые выполняются параллельно, и каждая из них завершается или прерывается независимо от остальных. Механизм вложенных транзакций разрабатывался, в первую очередь, как средство для использования параллелизма, присущего вычислениям; изначально он не предназначался для решения проблем долговременных транзакций. Однако идея сопоставления иерархической группы пользователей (например организационной структуры компании или структуры подрядчиков/субподрядчиков и т. п.) некоторой составной транзакции послужила основой для ряда предложений по использованию составных транзакций в контексте долговременных интерактивных сеансов взаимодействия с базой данных [30, 1, 26]. Все эти предложения предполагают наличие одной базы данных и могут рассматриваться как варианты модели одной базы данных, где индивидуальные транзакции ставятся в соответствие пользователям в некоторой иерархической структуре, которая определяется в терминах ролей, исполняемых сотрудниками в рамках кооперативного проекта, подразумевающего доступ к базе данных. Идея вложенных транзакций, несомненно полезная, добавляет новую степень сложности с точки зрения как семантики, так и реализации.
3.1. Кооперативные транзакции
Кооперативные транзакции - это транзакции, выполняемые в пределах одной разделяемой базы данных в кооперативной интерактивной рабочей среде. Из-за своей интерактивной природы, кооперативные транзакции длятся значительно дольше обычных. Далее, в отличие от традиционных транзакций, кооперативные не должны (необязательно должны) быть полностью изолированными.
Фундаментальная проблема, связанная с кооперативными транзакциями, - это отсутствие для них четких критериев согласованности. Разумной основой для выработки такого критерия могло бы стать принятие принципа сериализуемости для коллекций транзакций, но не для отдельных транзакций внутри коллекций. То есть коллекции транзакций в этом смысле должны вести себя по отношению друг к другу как отдельные традиционные транзакции. Будем называть подобные коллекции кооперативных транзакций группами (team) транзакциями. В пределах групп транзакций требование строгой изоляции, принятое в традиционных системах, снимается, так что отдельные транзакции в рамках своей группы могут осуществлять кооперативный доступ к разделяемой базе данных.
Таким образом, задача сводится к определению надлежащего понятия согласованности доступа к базе данных для кооперативных транзакций в пределах группы. Одна из возможностей - применить понятие согласованности уровня 1 (чтение незафиксированных данных) или уровня 2 (стабильность курсора) [21]. Сериализуемость в этой классификации эквивалентна критерию согласованности уровня 3. Согласованность уровня 2 предотвращает чтение грязных данных, но не гарантирует повторяющегося чтения. Этот уровень согласованности достигается, если блокировки по записи сохраняются до конца транзакции, а блокировки по чтению действительны лишь пока идет чтение. Согласованность уровня 1 предотвращает потерю изменений, но допускает грязное чтение и неповторяющееся чтение. Для обеспечения согласованности этого уровня достаточно сохранять блокировки по записи до конца транзакции, а блокировки по чтению можно вообще не запрашивать. Считается, что согласованность уровня 2 не дает существенного улучшения надежности совместного доступа, поэтому для кооперативных транзакций разумнее остановиться на уровне 1.
Очевидная проблема, связанная с поддержкой согласованности уровня 1 (а также уровней 2 и 3), заключается в том, что блокировки по записи сохраняются до конца транзакции, а значит, остальные транзакции не могут в это время получить доступ к данным. В среде долговременных интерактивных сеансов нежелательно надолго блокировать данные, с которыми сообща работают кооперирующиеся пользователи. Один из возможных подходов - разрешить при определенных обстоятельствах прерывание блокировок, установленных кооперативной транзакцией, со стороны других транзакций [25]. Таким образом, предлагается объединить понятие согласованности уровня 1 (или 2) с идеей мягких (допускающих прерывание) блокировок.
Суть мягких блокировок состоит в следующем. Пользователь может запросить у системы мягкие блокировки на одни данные и обычные, жесткие, - на другие. При запросе мягких блокировок задаются также некоторые параметры, которые определяют, например, кто имеет право нарушать блокировки, следует ли при этом просить подтверждения у исходного обладателя, следует ли посылать ему уведомление о том, что произошло прерывание блокировок. Пользователь, прервавший блокировку, становится ее обладателем.
Мягкие блокировки при этом всегда остаются мягкими. То есть мягкая блокировка, захваченная некоторой кооперативной транзакцией у другой транзакции, может затем перейти к третьей и т. д. Мягкая блокировка не может быть превращена в жесткую, так же, как невозможно и обратное преобразование жесткой блокировки в мягкую.
Кооперативная транзакция Т1, мягкие блокировки которой были прерваны транзакцией Т2, может в дальнейшем снова их захватить. С точки зрения традиционной модели транзакций, при кооперативных транзакциях возможно неповторяющееся чтение, грязное чтение и даже потери изменений. Но нарушение мягких блокировок происходит по общему согласию в рамках команды сотрудничающих пользователей, и, когда мягкая блокировка прерывается, владение ею (и, следовательно, ответственность за целостность данных) переходит от одной кооперативной транзакции к другой. Таким образом, при прерывании мягкой блокировки целостность базы данных не нарушается, если только данные, к которым относилась мягкая блокировка, полностью стирается как из памяти приложения/пользователя, так и из базы данных.
Будем говорить, что данные полностью стерты из памяти, если соблюдаются два условия. Во-первых, исходная кооперативная транзакция с момента прерывания блокировки никак не использует свое предыдущее знание о данных. Во-вторых, все изменения или добавления (вставки) данных, возможно, сделанные исходной транзакцией до прерывания блокировки, исключаются при восстановлениях базы данных после сбоев и при откатах транзакций. Если эти два условия соблюдаются и если все кооперативные транзакции, между которыми происходил обмен блокировками, либо все фиксируются, либо все откатываются, то можно утверждать, что кооперативные транзакции удовлетворяют даже критерию сериализуемости. На практике вряд ли возможно запретить приложениям или пользователям не использовать свое знание о данных после того, как мягкая блокировка была прервана. Но даже и в этом случае, если изменения данных исключаются при восстановлениях после сбоев, можно утверждать, что кооперативные транзакции удовлетворяют критерию совместимости уровня 1.
3.2. Разделяемая и частные базы данных
Архитектура разделяемой и частных баз данных со средствами взятия/возврата, дополненными механизмами триггеров и управленния версиями, - разумный инструмент для удовлетворения потребностей некоторых сред с долговременными интерактивными взаимодействиями с базами данных. Разумеется, средства взятия/возврата данных реализуются при помощи операций чтения-записи и, следовательно, опираются на встроенные в СУБД механизмы управления транзакциями. Долговременный характер сеансов не порождает проблем при выполнении транзакций по отношению к частным базам данных, не требующих доступа к разделяемой базе, поскольку такие транзакции не приводят к конфликтам по доступу. Для транзакций, требующих доступа к разделяемой базе данных, можно использовать либо традиционные средства управления, либо средства управления кооперативными транзакциями.
Основательной проработкой архитектуры разделяемой и частных баз данных можно считать описанный в [32] прототип объектно-ориентированной СУБД ORION, если отвлечься от некоторых технических вопросов, не нашедших адекватного решения в этой системе. Предложенная в ORION семантика операций взятия/возврата данных может быть взята за основу при реализации подобных средств в коммерческих СУБД.
Имеющий достаточные полномочия пользователь может создать одну или более частных баз данных. Для пользователя его частная база данных представляет собой логическое расширение разделяемой базы. Разделяемая база данных доступна всем, к частной же обращается только создавший ее пользователь. Схема частной базы данных является логическим расширением глобальной схемы разделяемой базы.
Владелец частной базы данных заполняет ее либо путем непосредственного создания объектов в ней, либо путем взятия объектов из разделяемой базы. Взятие объекта реализуется как копирование его из разделяемой базы в частную. Возврат - обратная по отношению к взятию операция, но при этом происходит не копирование, а перемещение данных из частной базы данных в разделяемую.
Пользователь берет либо один или несколько объектов, задавая их при помощи идентификаторов, либо множество объектов, определяемое некоторым выражением запроса.
Объект частной базы может ссылаться на объекты разделяемой, и наоборот. Эта ситуация возникает, если операция взятия применяется к отдельным объектам, а не к их замыканиям, где под замыканием понимается множество, включающее исходный объект и все объекты, на которые он прямо или рекурсивно ссылается. В таком случае и возвращаться будут также отдельные объекты, а не замыкания.
Остается еще ряд семантических вопросов, требующих осмысления. Первый - следует ли применять операции взятия/возврата всегда только к замыканиям объектов. Если разрешить эти операции только для замыканий, то упростится выполнение запросов и в какой-то степени усилится разграничение между разделяемой и частными базами данных. Но при этом в частные базы придется копировать и те данные, которые пользователю не нужны.
Другой вопрос - следует ли требовать взаимно-однозначного соответствия между множествами забираемых и возвращаемых объектов? То есть обязательно ли всегда возвращать сразу все взятые ранее объекты или можно возвратить только часть, а некоторые оставить в частной базе данных?
Далее, если пользователи имеют полную свободу именования классов в частных базах данных, то при возвращении их в разделяемую базу данных могут возникать конфликты. Принятый в ORION подход к решению этой проблемы - регистрация всех имен в глобальном сервере имен (даже если класс создается в частной базе данных); новое имя отвергается, если возникает конфликт с уже зарегистрированным именем. Но это не слишком удачное решение, поскольку оно ведет к нарушению "автономии" частных баз данных.
3.3. Направления исследований и разработок
Наиболее насущный вопрос для продвижения исследований в области долговременных транзакций - проработка таксономии (классификации) кооперативных транзакций, включая иерархические организации транзакций. Установленная таксономия вместе с существующими моделями согласованности баз данных могла бы послужить основой для разработки и реализации одного или нескольких механизмов кооперативных транзакций. Таксономия должна опираться на тщательное рассмотрение типа и значимости прикладной среды, для которой формулируется то или иное предложение, а также подразумеваемого класса согласованности. Предложения, не предполагающие определенного класса согласованности, должны отвергаться так же, как и предложения, охватывающие слишком узкие или специфические прикладные области. Неплохой отправной точкой для исследований в данном направлении можно считать работу [2], где даже приведена некоторая таксономия существующих предложений, но, по нашему мнению, необходима более качественная таксономия, опирающаяся на тщательный критический анализ имеющихся предложений.
4. Управление пространственными данными
В области управления пространственными данными в последние два десятка лет проводились весьма интенсивные исследования, нацеленные, главным образом, на разработку структур для хранения и индексации пространственных данных. Были предложены, в частности, такие структуры, как GridFile [38] (а также ее разновидность BangFile [17]); древовидные структуры, расширенные для хранения представлений многомерных точек, например quad-деревья [16, 6, 42], K-D-деревья [6] (K-D-B-деревья [40], где предусмотрены средства хранения K-D-деревьев во вторичной памяти, и пространственные K-D-деревья [39]); древовидные структуры для хранения представлений прямоугольников, например R-деревья [23] (R+-деревья [14, 45, 22], R*-деревья [4] и параллельные R-деревья [27], представляющие собой расширенные или оптимизированные версии R-деревьев). Однако ни в одной из коммерческих СУБД нет средств для непосредственного определения пространственных данных, для формулирования запросов с условиями поиска, затрагивающими такие данные. Список тем для ближайших исследований (в убывающем порядке важности и срочности) видится нам следующим образом.
Во-первых, необходимо распространить существующие методы оптимизации на запросы, относящиеся к пространственным данным, т. е. запросы, условия поиска которых ссылаются на пространственные данные. В частности, следует разработать разумную стоимостную модель для вычисления селективности пространственных операторов.
Во-вторых, нужны дополнительные исследования с целью экспериментальной проверки сравнительной производительности наиболее перспективных структур хранения и индексации, предложенных к настоящему времени. При этом важно рассмотреть более широкий класс операций, чем обычно используемый в подобных проверках довольно узкий набор.
В-третьих, поскольку трудно предусмотреть в одной СУБД все возможные структуры индексации и все мыслимые операции, которые в принципе могут оказаться полезными, то следует подумать о том, чтобы система была относительно легко расширяемой за счет определения дополнительных структур данных и операторов.
В следующих пунктах эти вопросы рассматриваются более подробно.
4.1. Обработка и оптимизация запросов
Пространственные операторы реализуются как операторы сравнения в предикатах поиска и как функции постпроцессирования, применяемые к результатам запросов. Каждый из таких операторов допускает сравнение некоторого предоставленного пользователем пространственного объекта со значением пространственного атрибута (т. е. атрибута, доменом которого является некоторый пространственный тип данных) в каждой записи базы данных.
Для поддержки пространственных операторов в механизмы обработки и оптимизации запросов необходимо внести следующие изменения/дополнения.
- Обработчик запросов должен уметь выполнять пространственные предикаты, т. е. предикаты, включающие пространственные операторы сравнения.
- Стоимостная модель для вычисления селективности операторов должна быть дополнена правилами для пространственных операторов.
Первый из перечисленных пунктов важен независимо от того, используется ли при обработке запросов индексация пространственных данных. Поскольку для аппроксимации произвольных форм, представляющих интерес для приложений, применяются минимальные ограничивающие прямоугольники, то объекты, выбранные индексацией по прямоугольным областям, должны еще пройти фазу постпроцессирования.
Оптимизатор должен уметь принимать решения о том, дает ли выгоду применение индекса по сравнению с простым последовательным поиском. В данном случае нежелательно и даже не следует определять слишком детальную и точную стоимостную модель. Стоимостная модель, используемая в реляционных базах данных, опирается на не всегда реалистичные предположения (такие как равномерность распределения значений ключа индексации, независимость значений в разных столбцах и т. п.), а также на существующую статистику о базе данных (например мощность таблицы, минимальное и максимальное значение ключа индексации и др.), которая в общем случае не соответствует текущему состоянию базы данных [44]. В сущности для оптимизации пространственных запросов достаточна приближенная стоимостная модель, сравнимая по точности с той, которая используется для оптимизации обычных реляционных запросов.
Стоимостная модель для пространственных предикатов
Мы предлагаем следующий подход к определению стоимостной модели для оценки селективности пространственных предикатов. Для обеспечения этих оценок СУБД должна хранить следующую информацию (если, для простоты изложения, рассматривать только прямоугольные области - расширение для k-мерных данных очевидно).
- N: мощность - общее число пространственных объектов.
- Диапазон изменения координат по каждому измерению (т. е. максимальное и минимальное значения по каждому измерению).
Селективность оператора точного сопоставления равна 1/N; это эквивалентно селективности стандартного оператора сравнения на равенство. Самый низкий уровень селективности 1 достигается, когда все записи удовлетворяют предикату.
Селективность операторов слева-от, справа-от, ниже, выше для заданного значения координаты вычисляется так же, как и для стандартных предикатов <,>:
1 / (максимальное_значение_по_i-му_измерению - значение_координаты)
Например, для предиката "слева от области {(x1,y1), (x2,y2)}, где x2>x1, максимальное значение по координате x равно x-max, а минимальное равно 0, селективность вычисляется по формуле
1 / (x-max - x1)
Заметим, что формулу селективности можно уточнить, если хранить информацию о поддиапазонах, то есть, если полный диапазон для каждого измерения разбить на несколько, возможно, неравных поддиапазонов, и хранить информацию о числе объектов в каждом из них, то эти сведения помогут более точно оценивать селективность операторов.
Селективности предикатов содержится-в, содержит, находится-в-радиусе-R-от, ближайший, наиболее-удаленный выражается в виде объединений и/или пересечений соответствующих селективностей по каждому измерению. Рассмотрим селективность предиката пересекает-область {(x1,y1), (x2,y2)}, проиллюстрированного на рисунке 3, где x1 > x2, максимальное значение для измерения X есть x-max, а для измерения Y - y-max, и минимальные значения для обоих измерений равны 0. Для вычисления его селективности сначала вычисляются селективности предикатов выше y2, ниже y1, левее x1, правее x2, а затем берется объединение всех этих селективностей.
Рисунок 3.
Диапазоны изменения координат для 2-мерных данных.
Обработка пространственных соединений
В реляционных базах данных соединение используется для сопоставления кортежей двух или более таблиц по значению заданных пользователем столбцов этих таблиц. В реляционной СУБД для вычисления соединений поддерживаются, в основном, два алгоритма - алгоритм вложенных циклов и алгоритм сортировок со слияниями [44]. Оператор пространственного пересечения, включающий два или более множества пространственных объектов, требует реализации пространственных соединений. Пространственное соединение сопоставляет пространственные кортежи (т. е. кортежи, содержащие пространственные данные), принадлежащие двум или более таблицам, на основе задаваемых пользователем пространственных атрибутов этих таблиц.
В литературе по обработке пространственных соединений принят пространственный эквивалент алгоритма вложенных циклов. Необходимо также разработать пространственный эквивалент алгоритма сортировок со слияниями. Поскольку пространственные данные многомерны, то не вполне очевидно, что понимать под их "сортировкой". В алгоритме соединения методом сортировок со слияниями в реляционных базах данных сортировка выполняется для подготовки кортежей таблиц к соединению так, чтобы соединение можно было выполнить за один проход по каждой таблице.
4.2. Структуры для представления пространственных данных
Основное направление исследований в области управления пространственными данными - это структуры данных для хранения и представления пространственных данных. Результаты этих исследований были внедрены в ряде географических информационных систем (GIS - geographical information system). Наиболее популярны среди известных структур данных R-деревья, которые используются для представления неточечных объектов (в частности прямоугольных областей). Серьезная проблема, связанная с R-деревьями, заключается в том, что они допускают перекрытие ограничивающих прямоугольников. Поскольку каждый объект, находящийся в одной из этих перекрывающихся областей, принадлежит только одному ограничивающему прямоугольнику, то в общем случае требуется просмотр множества ветвей дерева индексации. Для R-деревьев были предложены некоторые оптимизирующие методы [41, 45, 4].
Хотя в области исследования сравнительной производительности вариантов R-деревьев и некоторых других структур была проделана определенная работа [41, 45, 14, 22, 4, 24], не ясно тем не менее, достаточно ли представительны имеющиеся результаты. Можно перечислить, по крайней мере, несколько невыясненных проблем. Во-первых, большинство исследований производительности проводилось не на основе фактических реализаций структур данных в рамках полномасштабных СУБД; в этом отношении работа [22] наиболее реалистична. Непонятно, насколько существенно влияют принятые в аналитических исследованиях упрощающие предположения на полученные результаты.
Во-вторых, в большинстве исследований производительности рассматривается лишь несколько типов пространственных операторов (например, "найти все объекты, содержащие заданную точку", "найти все области, пересекающие заданную область"); множество рассматриваемых операторов необходимо существенно расширить. Так, если приложение имеет дело только с точками, линиями и областями, то можно выделить шесть классов пространственных операторов: область-область, линия-область, точка-область, линия-линия, точка-линия, точка-точка. В каждом из этих классов найдется несколько достаточно осмысленных операций. В классе область-область помимо очевидного оператора точного сопоставления можно назвать также операторы пересекает, содержит, находится-в- заданном-направлении (левее, правее, выше, ниже), находится-в-радиусе-R-от, ближайший, наиболее-удаленный и др. При этом структура данных, которая обеспечивает хорошую производительность для операторов класса область-область, не обязательно окажется подходящей для операторов класса линия-линия.
4.3. Расширяемая архитектура
Существует несколько предложений, касающихся создания "расширяемых" СУБД, среди них - предложения построить сложный расширяемый оптимизатор запросов [18], даже генератор оптимизаторов, охватывающий несколько моделей данных [20], вплоть до предложения о разработке конфигуратора СУБД, строящего систему управления базами данных из нескольких исходных модулей, которые представляют собой строительные блоки СУБД [3]. Идея расширяемой архитектуры СУБД для поддержки пространственных объектов имеет весьма существенные основания. Во-первых, структура индексов, поддерживаемая в существующих СУБД, вполне вероятно, может оказаться неподходящей для некоторых приложений. Во-вторых, не слишком практично было бы встраивать в СУБД поддержку всех возможных пространственных операторов; но тогда некоторым приложениям может не хватить предусмотренного в СУБД множества операторов, достаточного для широкого класса приложений.
Если мы хотим иметь СУБД, допускающую добавление дополнительных структур индексации и/или пространственных операторов, то при проектировании такой СУБД, в первую очередь, следует позаботиться именно о средствах поддержки расширений. Ниже мы рассмотрим, как требование расширяемости влияет на архитектуру СУБД.
Во-первых, посмотрим, во что обойдется возможность добавлять новые структуры индексов. Новая структура данных должна сосуществовать с уже имеющимися. Значит, для каждой структуры данных нужен отдельный менеджер индекса, который поддерживал бы базовые функции индексирования.
Между менеджерами индексов и модулем обработки запросов должен быть еще программный модуль, называемый обобщенным менеджером индексов (GIM - General Index Manager). GIM - "тонкий" программный слой поверх индивидуальных менеджеров индексов, реализующий высокоуровневые функции индексирования, которые могут не поддерживаться в каждом отдельном менеджере индексов. Например, операция поиска в замкнутой области, если она не обеспечивается менеджером индекса, может быть реализована в GIM посредством операций индексного поиска. Вставка множества элементов в индекс реализуется над менеджером индексов в виде последовательности вставок отдельных элементов. То есть каждая такая операция реализуется через базовые функции, предоставляемые менеджерами индексов.
Оптимизатор запросов должен быть спроектирован так, чтобы для добавления стоимостных моделей любых дополнительно встраиваемых пространственных операторов не приходилось изменять код существующего оптимизатора. Та часть оптимизатора, которая занимается вычислением селективности предикатов, должна быть организована таким образом, чтобы новые предикаты и правила вычисления их предикатов добавлялись как параметры оптимизатора. Например, СУБД может содержать структуру данных, где хранятся модели селективности всех поддерживаемых операторов, и команды для добавления/удаления/изменения стоимостной модели предиката.
Обработчик запросов также должен уметь вызывать устанавливаемые алгоритмы, т. е. модули вычисления предикатов для вновь определяемых пространственных операторов.
На рисунке 4 показана суть этих изменений в архитектуре обработчика запросов, оптимизатора запросов и менеджера индексов.
Рисунок 4.
Расширяемая архитектура обработки запросов. IM - Менеджер индексов
(Index Manager), PEM - модуль вычисления предикатов (Predicate Evaluation
Module).
5. Управление хронологическими данными
К управлению хронологическими данными относятся две проблемы: управление историческими данными и управление версиями. Обе они были предметом исследований в течение уже более десятка лет. Один из сложных аспектов управления хронологическими данными состоит в том, что здесь нет четких границ между прерогативами приложения и СУБД. То есть не понятно, какую часть типичной семантики и средств управления такими данными следует встраивать непосредственно в СУБД, а что следует оставить в ведении приложения. Далее в этом разделе мы приведем список вопросов для исследований, которые должны прояснить эту фундаментальную проблему.
5.1. Исторические данные
Основное внимание в исследованиях этого направления уделялось определению семантики времени и временных интервалов, а также вопросам выявления семантики запросов и модификаций, относящихся к историческим данным, которые хранятся как атрибуты записей [47, 48]. Как правило, в контексте реляционных баз данных хронологический атрибут определяется для хранения исторической последовательности значений атрибута. Исторические данные состоят из элемента данных и временного интервала, на протяжении которого значение элемента данных действительно. Далее могут формулироваться запросы на выборку исторических данных по заданному интервалу времени для хронологического атрибута. Механизм поддержки хронологических атрибутов аналогичен используемому для поддержки атрибутов с множественными атрибутами в таких СУБД, как UniSQL.
При отсутствии поддержки хронологических атрибутов, разработчики приложений, где нужно моделировать исторические данные и управлять ими, заменяют хронологические атрибуты парой атрибутов, в одном из которых хранится интервал времени, а в другом - элемент данных. Это, конечно, может приводить к дублированию данных в строках таблицы и к более сложным предикатам в запросах. Насущно необходимая тема для исследований в области управления хронологическими данными - количественно оценить разницу в производительности (и даже в продуктивности) при использовании СУБД, прямо поддерживающей хронологические атрибуты, и СУБД, которая не поддерживает ни атрибутов с множественными значениями, ни хронологических атрибутов. Если будут убедительно доказаны преимущества поддержки хронологических данных, то это послужит существенным стимулом для поставщиков СУБД к тому, чтобы дополнить свои продукты подобными средствами.
5.2. Управление версиями
Несмотря на то что существует множество предложений по поддержке версий в контексте компьютерного конструирования и проектирования программного обеспечения [10, 29], отсутствие общепринятой точки зрения на семантику версий было основным препятствием к реализации поддержки версий в СУБД. Интуитивно ясно, что, в силу различий между парадигмами файлов и баз данных, модель управления версиями в СУБД не может быть столь же проста, как та, что применяется в файловых системах для поддержки разработок программного обеспечения. В базе данных, по-видимому, необходимо хранить версии не только отдельных объектов (таких как программный модуль или документ), но также и коллекций объектов (например составных документов, руководств пользователя и др.) и, возможно, даже схемы базы данных (определений таблиц, классов, коллекций таблиц или классов).
Можно выделить три направления исследований и разработок в области поддержки версий. Первое связано с идеей "параметризуемого управления версиями". Речь идет о разработке и реализации такой системы управления версиями, поведение которой можно было бы регулировать при помощи ряда системных параметров. Вероятно, это единственное жизнеспособное решение проблемы, если учесть многообразие альтернатив для практически всех аспектов управления версиями (модифицируемость и уничтожаемость версий, идентификаторы версий, временные метки версий, иерархия вывода версий). Второе направление - это тщательный критический анализ всех имеющихся разумных альтернатив для каждого аспекта управления версиями, с тем чтобы отбросить или пересмотреть те из них, которые окажутся непрактичными или некорректными. Третья сфера исследований - проработка семантики и вопросов реализации поддержки версий для коллекций объектов [9] и для схем баз данных [31]. Далее в этом разделе мы рассмотрим варианты решений для разных аспектов управления версиями и охарактеризуем подробнее идею параметризуемого управления версиями.
Модифицируемость и уничтожаемость версий
В работе [10] предлагается различать три типа версий - промежуточные (transient), стабильные (stable) и опубликованные (released). Промежуточная версия может быть изменена или уничтожена своим создателем в любой момент. Стабильные версии можно только изменять, но не уничтожать. С опубликованными версиями нельзя делать ни того ни другого. Из любой версии возможен вывод множества новых, т. е. все множество версий имеет иерархическую структуру. Если из некоторой промежуточной версии выведена новая промежуточная, то исходная автоматически переводится в разряд стабильных.
В связи с этим предложением возникает ряд вопросов, по которым нет пока единого мнения. Допустимо ли уничтожение неконечных версий? Что происходит с производными версиями, если уничтожается их родительская версия? Что понимается под изменением версии, имеющей потомков, в которые, возможно, было скопировано ее содержимое, - следует ли распространять внесенные изменения на все дерево производных версий?
Высказывается также мнение о том, что понятия модифицируемости и уничтожаемости следует применять не к отдельным версиям, а к их коллекциям.
Идентификаторы версий
Практически во всех предложениях, относящихся к управлению версиями, с каждой версией объекта ассоциируется идентификатор. Что касается способов поддержки идентификаторов версий и доступа к ним, то здесь можно выделить по крайней мере три альтернативы.
Первая заключается в том, чтобы хранить идентификатор версии как внутренний элемент данных, не относящийся к числу атрибутов. Это означает, что идентификатор версии никак не связан с семантикой атрибутов. Но раз это не атрибут, то для доступа к нему необходим специальный синтаксис. Так, для выборки объекта с идентификатором версии 1 пришлось бы использовать, например, такой SQL-подобный синтаксис:
SELECT x FROM verclass x
WHERE VERSION IS 1
Спецификация VERSION IS 1 здесь - языковое расширение для доступа к идентификатору версии. Преимущество этого подхода - строгое выделение понятия версии и способа доступа к нему. Недостаток - необходимость расширения синтаксиса SQL.
Вторая альтернатива - хранение идентификатора версии в виде системного атрибута (атрибута, автоматически определяемого системой и имеющего некоторые допонительные свойства). Преимущество этого подхода в том, что не нужно расширять стандартный синтаксис SQL для описания доступа к идентификаторам версий. Допустим, что если для класса объектов запрашивается поддержка версий, то система автоматически определяет в нем атрибут version_id. Предыдущий пример тогда будет выглядеть следующим образом:
SELECT x FROM verclass x
WHERE version_id = 1
Недостаток этого подхода - проблемы, возникающие при работе с иерархиями наследования классов в объектно-ориентированных системах. Следует, в частности, решить, будет ли атрибут идентификатора версии автоматически наследоваться при определении подклассов. Если допустить, что он всегда автоматически наследуется, то в результате поддержку версий придется распространять на все классы, независимо от того, хотят ли этого создатель и пользователи классов. Для того чтобы избежать этого, можно было бы поддерживать две иерархии наследования - одну для классов с поддержкой версий, другую для классов без него. Но тогда может возникнуть необходимость дублировать определения классов и атрибутов по двум иерархиям наследования. (Тот же вопрос возникает и для обсуждавшейся выше первой альтернативы. Как будут вести себя в примере выше подклассы класса verclass, для которых не задана поддержка версий? Должны ли они молча исключаться при обработке подобных запросов?)
Третья альтернатива заключается в том, чтобы пользователь определял для хранения идентификатора версии обычный атрибут. Разумеется, пользовательский атрибут, предназначенный для этой цели, должен быть неизменяемым, и при создании новой версии пользователь обязан заносить в него ее идентификатор. Прочая семантика атрибутов для него сохраняется.
Желательно, чтобы идентификаторы версий генерировались системой автоматически. Но здесь все не так просто. Трудно предложить единый алгоритм генерации идентификаторов версий, поскольку семантика идентификаторов определяется приложением. Единственное, что реально может гарантировать система - это уникальность значений идентификаторов. При этом приложение может предпочесть идентификаторы вида "1.0", "1.1", "1.2" и т. д. или, например "1.a", "1.b", 2.c" и т. п.
Таким образом, вопрос сводится к тому, каким образом разрешить пользователям "регистрировать" алгоритмы генерации идентификаторов версий. Многообещающим подходом можно считать определение соответствующих методов. Остается только решить, как вызывать такой метод и какими должны быть его аргументы. Например, можно задать все это явно в определении классов, как в следующем примере:
CREATE CLASS person
(name string, age integer, vid integer)
METHOD vid_generator():integer
VERSION vid AUTOMATIC vid_generator;
Здесь спецификация VERSION имеет дополнительное описание AUTOMATIC vid_ generator, которое задает автоматическую генерацию идентификатора версии и указывает, что для этого нужно применить метод vid_generator.
Иерархия вывода версий
Одни утверждают, что структура вывода версий должна быть иерархической (древовидной), другие - что она должна соответствовать направленному ациклическому графу (DAG - directed acyclic graph). Древовидная структура позволяет выводить одну или более версий из одной исходной версии. В структуре DAG возможен вывод новой версии из нескольких исходных. Для простоты мы будем в оставшейся части этого пункта использовать термин "иерархия" для обозначения и древовидной, и DAG-структуры вывода версий.
Остается еще вопрос о том, должна ли СУБД брать на себя поддержку иерархий вывода версий. Существует мнение, что поддержка иерархии версий и ее обработка - это функции приложения. Аргументация здесь схожа с той, о которой говорилось при обсуждении вопросов генерации идентификаторов версий. СУБД ничего не известно об отношении "предок-потомок" между объектами в кластере (коллекции) версий. СУБД, возможно, в состоянии определить это отношение в момент создания новой версии, но в дальнейшем приложение может изменить его. Если приложение должно иметь полный контроль над структурой иерархии версий, то почему бы не возложить на него всю ответственность за ее поддержание? Достаточную ли функциональность в данной области предоставляет система, для того чтобы можно было включить в нее эти средства?
Еще один связанный с предыдущим вопрос - что значит вывести одну версию из другой? Означает ли это, что атрибуты выведенного объекта инициализируются значениями атрибутов исходного? Если нет, то почему нужно считать данный объект выведенным из исходного? Не достаточно ли тогда просто добавить этот новый объект к кластеру версий и оставить инициализацию атрибутов в ведении приложения? Если приложение желает установить между некоторыми двумя версиями отношение "родитель-потомок", то оно может сделать это обычными средствами модификации объектов.
Если смысл создания новой версии состоит в том, что атрибуты нового объекта инициализируются значениями атрибутов исходного объекта, то что тогда понимать под выводом версии из нескольких исходных? В этом случае система не в состоянии определить, каким образом пользователь пожелает слить атрибуты исходных версий в новой версии. Рассмотрим, например, следующую инструкцию:
CREATE VERSION "0.9"
FROM "0.5", "0.8"
OF SELECT chip FROM chip
WHERE designer = "scottie"
Каковы значения атрибутов создаваемой версии? Если они не определены, то установить их должно приложение. Но в таком случае оно могло бы определить и иерархию вывода при помощи обычных атрибутов тогда же, когда устанавливаются значения прочих атрибутов.
Разумный подход состоит в том, чтобы СУБД поддерживала лишь фундаментальные функции управления версиями, т. е. она должна уметь добавить новый объект к кластеру версий с присвоением ему идентификатора версии. Вся семантика более высокого уровня определяется на прикладном уровне. С упрощением семантики (на уровне СУБД) соответственно упрощается и синтаксис:
INSERT INTO person(name, age)
VALUES ("jeff", 34)
AS VERSION OF
SELECT person FROM person
WHERE name="jeff";
Это выглядит почти как обычное предложение INSERT, но спецификация AS VERSION OF говорит о том, что новый объект при занесении в базу данных должен быть добавлен к кластеру версий объекта из списка выборки.
Параметризуемое управление версиями
Как показано выше, для каждого аспекта поддержки версий существует множество осмысленных альтернатив. Вероятно, неразумно было бы в реализации СУБД ограничить каждый такой аспект только одной возможностью. Недостаточно гибкая система будет обречена на неуспех, поскольку ее поведение окажется неприемлемым для пользователей, чьи потребности и предпочтения не совпадают с выбором, сделанным разработчиками СУБД. По-видимому, наилучшим решением была бы параметризуемая система поддержки версий. Идея состоит в том, чтобы выделить в реализации такой системы два компонента. Один компонент должен предоставлять инфраструктуру для всех базовых функций, необходимых для обеспечения всех осмысленных альтернатив для каждого аспекта поддержки версий. Другой компонент будет представлять собой механизм, который позволяет выбрать предпочтительные для него альтернативы, т. е. приспосабливать систему к своим потребностям.
Например, инфраструктура может быть рассчитана на поддержку любой структуры вывода версий: простая цепочка, иерархия, направленный ациклический граф. Далее, в ней могут поддерживаться различные понятия уничтожаемости и модифицируемости версий: неконечная версия может/не может быть уничтожена; стабильная версия может/не может быть уничтожена и т. д. При этом пользователь (или системный администратор) имеет возможность выбрать в качестве структуры вывода версий, например, иерархию, определить, что неконечные версии не подлежат удалению, стабильные версии также не подлежат удалению и т. п.
6. Заключение
Тенденции в индустрии баз данных прямо указывают на то, что в основу постреляционных баз данных должна лечь технология, объединяющая в себе реляционную и объектно-ориентированную модели данных, а также непроцедурный язык, в котором стандартные возможности ANSI SQL дополняются средствами объектно-ориентированного проектирования баз данных и манипулирования объектами. Выделяются как минимум четыре проблемы, которые были предметом интенсивных исследований и усилий по прототипированию в последние 10-20 лет. К ним относятся управление мультимедийными данными, долговременные транзакции, управление пространственными данными и управление хронологическими данными. Научные изыскания и реализации прототипов систем дали множество весьма полезных результатов, и предлагаемый здесь список тем для краткосрочных исследований нацелен на то, чтобы получить наконец реальные плоды, т. е. реализовать накопленные результаты в коммерческих постреляционных СУБД. В своей статье мы привели для каждой из четырех проблем обзор целей, преследуемых при ее решении, и сформулировали конкретные предложения по доведению соответствующих иссследований и разработок до стадии практической применимости или, по крайней мере привели список тем, на которых следует сосредоточить усилия в ближайшем будущем.
Литература
1. F. Bancilhon, W. Kim, H. Korth. A model of CAD Transactions. - Proc. Intl. Conf. on Very Large Data Bases, August 1985, Stockholm, Sweden.
2. N. Barghouti, G. Kaiser. Concurrency Control in Advanced Database Applications. - ACM Computing Surveys, vol. 23, no. 3, Sept. 1991, pp. 269-317.
3. D. Batory et al. GENESIS: An Extensible Database Management System. - IEEE Trans. on Software Engineering, vol. 14, no. 11, Nov. 1988.
4. N. Beckman, H-P Kriegel, R. Schneider, and B. Seeger. The R*-Tree: An Efficient and Robust Access Method for Points and Rectangles. - Proc. ACM SIGMOD Intl. Conf. on Management of Data, Atlantic City, New Jersey, May 1990, pp 322-331.
5. C. Beery, P. Bernstein, and N. Goodman. A Model for Concurrency Control in Nested Transaction Systems, J/2, ACM 36, pp. 230-269.
6. J. Bentley. Multidimensional Binary Search Trees Used for Associative Searching. - Comm. of ACM, vol. 18, no. 9, 1975.
7. P. Bernstein, and N. Goodman. Multiversion Concurrency Control Theory and Algorithms. - ACM Transactions on Database System, vol. 8, no. 4, December 1983, pp 465-483.
8. P. Berstein, V. Hadzilacos, and N. Goodman. Concurrency Control and Recovery in Database Systems. - Addison-Wesley, Reading, Mass. 1987.
9. E. Bertino, W. Kim, and J. Garza. Composite Objects Revisited. - Proc. ACM SIGMOD Intl. Conf. on Management of Data, Portland, Oregon, June 1989.
10. H.T. Chou, and W. Kim. A Unifying Framework for Versions in a CAD Environment. - Proc. Intl. Conf. on Very Large Data Bases, August 1986, Kyoto, Japan.
11. H.T. Chou, and W. Kim. Versions and Change Notification in an Object-Oriented Database System. - Proc. Design Automation Conference, June 1988.
12. P. Chrysanthis, and K. Ramamritham. ACTA: A Framework for Specifying and Reasoning about Transaction Structure and Behavior. - Proc. ACM SIGMOD Intl. Conf. on Management of Data, May, 1990, pp. 194-203.
13. A. El Abdadi, and S. Toueg. The Group Paradigm for Concurrency Control Protocols. - IEEE Trans. on Knowledge and Data Engineering, vol 1, no. 3, Sept. 1989, pp 376-386.
14. C. Faloutsos, T. Sellis, and N. Roussopoulos. Analysis of Object-Oriented Spatial Access Methods. - Proc. ACM SIGMOD Intl. Conf. on Management of Data, San Francisco, Calif., May 1987, pp. 426-439.
15. M. Fernandez, and S. Zdonik. Transaction Groups: A Model For Controlling Cooperative Work. - Proc. 3rd. Intl. Workshop on Persistent Object Systems: Their Design, Implementation, and Use, Jan. 1989, Morgan Kaufman, pp. 128-138.
16. R. Finkel, and J. Bentley. Quadtrees: A Data Structure for Retrieval on Composite Keys. - Acta Informatica, vol. 4, no. 1, 1974.
17. M. Freeston. The BANG File: A New Kind of Grid File. - Proc. ACM SIGMOD Intl. Conf. on Management of Data, San Francisco, Calif., May 1987, pp. 260-269.
18. J. Freytag. A Rule-Based View of Query Optimization. - Proc. ACM SIGMOD Intl. Conf. on Management of Data, pp. 173-180, San Francisco, Calif., 1987.
19. H. Garcia-Molina, and K. Salem. Sagas. - Proc. SIGMOD Intl. Conf. on Management of Data, May 1987, pp. 249-259.
20. G. Graefe, and D. DeWitt. The EXODUS Optimizer Generator. - Proc. ACM SIGMOD Intl. Conf on Management of Data, pp. 160-172, San Francisco, Calif., 1987.
21. J.N. Gray. Notes on Data Base Operating Systems. - IBM Research Report: RJ2188, IBM Research, San Hose, Calif., 1978.
22. D. Greene. An Implementation and Performance Analisis of Spatial Data Access Methods. - Proc. IEEE Intl. Conf. on Data Engineering, Feb. 1989, Los Angeles, Calif., pp. 606-615.
23. A. Guttman. R-Trees: A Dynamic Index Structure for Spatial Searching. - Proc. ACM SIGMOD Intl. Conf. on Management of Data, Boston, Mass., June 1984, pp. 47-57.
24. E. Hoel, and H. Samet. A Qualitative Comparison of Data Structures for Large Line Segment Databases. - Proc. ACM SIGMOD Intl. Conf. on Management of Data, San Diego, Calif. June 1992.
25. M. Hornick, and S. Zdonik. A Shared, Segmented Memory System for an Object-Oriented Database. - ACM Trans. on Office Informanion Systems, vol. 5, no. 1, Jan. 1987, pp. 70-95.
26. IEEE Data Engineering Bulletin special issue on Unconventional Transaction Management (ed. Ahmed Elmagarmid), March, 1991.
27. I. Kamel, and C. Faloutsos. Parallel R-Trees. - Proc. ACM SIGMOD Intl. Conf. on Management of Data, San Diego, Calif., June, 1992.
28. R. Katz, and S. Weiss. Design Transaction Management. - Proc. 21st Design Automation Conference, Alburquerque, New Mexico, June 1984.
29. R. Katz. Towards a Unified Framework for Version Modelling in Engineering Databases. - ACM Computing Surveys, vol. 22, no. 4, Dec. 1990, pp. 375-408.
30. W. Kim, D. McNabb, R. Lorie, and W. Plouffe. A Transaction Mechanism for Engineering Design Databases. - Proc. Intl. Conf. on Very Large Databases, Singapore, 1984.
31. W. Kim, and H. Chou. Versions of Schema for Object-Oriented Databases. - Proc. Intl. Conf. on Very Large Data Bases, Long Beach, Calif., Sept. 1988.
32. W. Kim, N. Ballou, J. Garza, D. Woelk. A Distributed Object-Oriented Database System Supporting Shared and Private Databases. - ACM Trans. on Office Information Systems, Jan. 1991, pp. 31-51.
33. W. Kim, J. Garza, A. Keskin. Spatial Data Management: Research Directions. - Proc. Intl. Symposium on Large Spatial Databases, June 1993, Singapore.
34. P. Klahold, G. Schlageter, R. Unland, and W. Wilkes. A Transaction Model Supporting Complex Applications in Integrated Information Systems. - Proc. ACM SIGMOD Intl. Conf. on Management of Data, May 1985, pp. 388-401.
35. H. Korth, W. Kim, F. Bansilhon. On Long-Duration CAD Transactions. - Information Science, Oct. 1988.
36. H. Korth, and G. Speegle. Formal Model of Correctness without Serialisability. - Proc. SIGMOD SIGMOD Intl. Conf. on Management of Data, June 1988, pp. 379-386.
37. E. Moss. Nested Transactions: An Approach to Reliable Distributed Computing. - MIT Press, 1985.
38. J. Nievergelt, H. Hinterberger, and K. Sevcik. The GridFile: An Adaptable Symmetric Multikey File Structure. - ACM Trans. on Database Systems, vol. 9, no.1, March 1984.
39. B-C. Ooi. Efficient Query Processing in Geographic Information Systems. - Lecture Notes in Computer Science, Springer-Verlag, 1990.
40. J. Robinson. The K-D-B Tree: A Search Structure for Large Multidimensional Dynamic Indexes. - Proc. ACM SIGMOD Intl. Conf. on Management of Data, Ann Arbor, Michigan, April 1981.
41. N. Roussopoulos, and D. Leifker. Direct Spatial Search on Pictorial Databases Using Packed R-Trees - Proc. ACM SIGMOD Intl. Conf. on Management of Data, Austin, Texas, May 1985.
42. H. Samet. The Quadtree and Related Hierarchical Data Structures. - ACM Computing Surveys, vol. 16, no. 2, June 1984.
43. B. Seeger, H-P. Kriegel. The Buddy-Tree: An Efficient and Robust Access Method for Spatial Data Base Systems. - Proc. Intl. Conf. on Very Large Data Bases, Brisbane, Australia, August 1990, pp. 590-601.
44. P. Selinger, et al. Access Path Selection in a Relational Database Management System. - Proc. ACM SIGMOD Intl. Conf. on Management of Data, Boston, Mass., May 1979, pp. 23-34.
45. T. Sellis, N. Roussopoulos, and C. Faloutsos. The R+-Tree: A Dynamic Index for Multi-Dimensional Objects. - Proc. Intl. Conf. on Very Large Data Bases, Brighton, England, 1987, pp. 507-518.
46. A. Skarra, and S. Zdonik. Concurrency Control and Object-Oriented Databases. - Object-Oriented Concepts, Databases, and Applications (W. Kim, and F. Lochovsky, eds.), Addison-Wesley/ACM Press, 1989.
47. R. Snodgrass, and I. Ahn. Temporal Databases. - IEEE computer, vol. 19, no. 9, Sept. 1986, pp. 35-42.
48. R. Snodgrass. The Temporal Query Language TQuel. - ACM Trans. on Database Systems, vol. 12, no. 2, June 1987, pp. 247-298.
49. D. Woelk, and W. Kim. Multimedia Information Management in an Object-Oriented Database System. - Proc. Intl. Conf. on Very Large Data Bases, Brighton, England, Sept. 1987, pp. 319-329.
Won Kim, Jorge F. Garza, Bruce Graham. UniSQL, Inc. 8911 Capital of Texas Highway, Suite 2300 Austin, Texas 78759