Объектно-ориентированные базы данных

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

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

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

Первой формализованной и общепризнанной моделью данных была реляционная модель Кодда [98]. В этой модели, как и во всех следующих, выделялись три аспекта - структурный, целостный и манипуляционный.

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

Ограничения целостности выражаются с помощью средств логики первого порядка

Манипулирование данными осуществляется на основе реляционной алгебры или равносильного ей реляционного исчисления.

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

Основные трудности объектно-ориентированного моделирования данных проистекают из того, что такого развитого математичекого аппарата, на который могла бы опираться общая объектно-ориентированная модель данных, не существует. В большой степени поэтому до сих пор нет базовой объектно-ориентированной модели. С другой стороны, в [63] со ссылкой на недоступную нам работу Майера [99] утверждается, что общая объектно-ориентированная модель данных в классическом смысле и не может быть определена по причине непригодности классического понятия модели данных к парадигме объектной ориентированности.

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

Во-первых, следуя практике многих ООБД, предлагается выделить два уровня моделирования объектов: нижний (структурный) и верхний (поведенческий). На структурном уровне поддерживаются сложные объекты, их идентификация и разновидности связи "isa". База данных - это набор элементов данных, связанных отношениями "входит в класс" или "является атрибутом". Таким образом, БД может рассматриваться как ориентированный граф. Важным моментом является поддержание наряду с понятием объекта понятия значения (позже мы увидим, как много на этом построено в одной из успешных объектно-ориентированных СУБД O2 [29]).

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

Автор [63] не представляет полной формальной модели структурного уровня ООБД, но выражает уверенность, что текущего уровня понимания достаточно, чтобы формализовать такую модель. Что же касается поведенческого уровня, предложен только общий подход к требуемому для этого логическому аппарату (логики первого уровня недостаточно).

Важным, хотя и недостаточно обоснованным предположением Беери является то, что двух традиционных уровней - схемы и данных для ООБД недостаточно. Для точного определения ООБД требуется уровень мета-схемы (см. также [65]), содержимое которой должно определять виды объектов и связей, допустимых на схемном уровне БД. Мета-схема должна играть для ООБД такую же роль, какую играет структурная часть реляционной модели данных для схем реляционных баз данных.

Имеется достаточное количество других публикаций, относящихся к теме объектно-ориентированных моделей данных [61-62, 64, 65-68], но они либо затрагивают достаточно частные вопросы, либо используют слишком серьезный для этого обзора математический аппарат (к числу последних относится работа Леллани и Спиратоса [68], в которой объектно-ориентированная модель данных определяется на основе теории категорий).

Для иллюстрации текущего положения дел мы кратко рассмотрим особенности конкретной модели данных, применяемой в объектно-ориентированной СУБД O2 [29, 32] (это, конечно, тоже не модель данных в классическом смысле).

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

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

Объекты и значения могут быть именованными. С именованием объекта или значения связана долговременность его хранения (persistency): любые именованные объекты или значения долговременны; любые объект или значение, входящие как часть в другой именованный объект или значение, долговременны.

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

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

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

Поддерживается предопределенный класс "Оbject", являющийся корнем решетки классов; любой другой класс является неявным наследником класса "Object" и наследует предопределенные методы ("is_same", "is_value_equal" и т.д.).

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

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

Языки программирования систем ООБД и языки запросов

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

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

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

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

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

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

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

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

Языки запросов к ООБД и методы оптимизации

Как отмечают многие исследователи и разработчики (например, [1, 2]), объектно-ориентированная система БД представляет собой объединение системы программирования и СУБД (альтернативная, но не более проясняющая суть дела точка зрения состоит в том, что объектно-ориентированная СУБД - это СУБД, основанная на объектно-ориентированной модели данных [2]).

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

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

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

К моменту написания данной работы нам неизвестен какой-либо язык программирования ООБД, который был бы спроектирован целиком заново, начиная с нуля. Естественным подходом к построению такого языка было использование (с необходимыми расширениями) некоторого существующего объектно-ориентированного языка. Начало расцвета направления ООБД совпало с пиком популярности языка Smalltalk-80. Этот язык оказал большое влияние на разработку первых систем ООБД, и, в частности, использовался в качестве языка программирования [4, 5]. Во многом опирается на Smalltalk и известная коммерчески доступная система GemStone [6-7].

Трудности с эффективной практической реализацией языка Smalltalk побудили разработчиков систем ООБД к поиску альтернативных базовых языков. Известная близость объектно-ориентированного и функционального подходов к программированию позволяет достаточно успешно опираться на функциональные языки программирования. В частности, язык Лисп (Common Lisp) является основой проекта ORION [8]. В этом проекте Лисп является и инструментальным языком, и базой объектно-ориентированного языка программирования в среде ORION.

Потребности в еще более эффективной реализации заставляют использовать в качестве основы объектно-ориентированного языка языки более низкого уровня. Например, в системе VBASE [9] наряду со специально разработанным языком TDL, предназначенным для определения типов, используется объектно-ориентированное расширение языка Си - COP (C Object Processor). В уже упоминавшемся проекте O2 [10-13] наряду с функциональным объектно-ориентированным языком программирования [14] используются два объектно-ориентированных расширения языков Бейсик и Си. При этом, насколько можно судить по публикациям, наибольшее распространение среди пользователей этой системы (она уже коммерчески доступна) получил язык CO2, являющийся расширением языка Си. Возможно это связано лишь с широкой (и все более возрастающей) популярностью языка Си (и его объектно-ориентированного потомка Си++), ставшего поистине девизом "настоящих программистов". Может быть, причины более глубинны (например, языки более высокого уровня слишком ограничительны для программистов-профессионалов; недаром большинство современных реализаций языков более высокого уровня выполняются именно на языке Си). Тем не менее, современная ситуация именно такова, и мы считаем полезным привести краткое описание основных особенностей языка CO2 [12-13, 15].

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

Имя любого объекта трактуется как указатель на значение этого объекта; разыменование производится с помощью обычного оператора Си '*'. Доступ к значению объекта возможен только из метода его класса, если только при перечислении методов оператор '*' не объявлен явно публичным.

Поддерживается операция порождения нового объекта указанного класса. В отличие от языка Си++ в CO2 невозможно совместить создание нового объекта с его инициализаций (понятие метода-конструктора начального значения объекта в CO2 не поддерживается). Для инициализации необходимо либо явно обратиться к соответствующему методу класса с указанием вновь созданного объекта (поддерживается соответствующий механизм "передачи сообщений", означающий на самом деле вызов функции), либо воспользоваться оператором '*' и явно присвоить новое значение, если '*' - публичный оператор для данного класса.

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

Основой манипулирования объектами, хранимыми в БД, является расширенное по сравнению с языком Си средство итерации. Итератор применим к значениям-множествам или спискам. Фактически он означает последовательное применение оператора-тела цикла ко всем элементам множества или списка. Если мы вспомним, что долговременно хранимому классу объектов неявно соответствует одноименное значение-множество с элементами-объектами данного класса, то становится понятно, что итератор языка CO2 обеспечивает явную навигацию в классах объектов. Единственное, что остается от привычных пользователям СУБД языков запросов, - это ограниченная возможность указания характеристик требуемых в цикле объектов (это делается путем использования оператора разыменования и явного указания условий на атрибуты; конечно, для этого нужно, чтобы оператор '*' был объявлен публичным в данном классе).

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

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

Беери [17] отмечает существование трех подходов. Первый подход - языки, являющиеся объектно-ориентированными расширениями языков запросов реляционных систем. Наиболее распространены языки с синтаксисом, близким к известному языку SQL [18]. Это связано, конечно, с общим признанием и чрезвычайно широким распространением этого языка. В частности, в своем Манифесте третьего поколения [19] СУБД М. Стоунбрекер и его коллеги по комитету перспективных систем БД утверждают необходимость поддержания SQL-подобного интерфейса во всех СУБД следующего поколения.

Второй подход основывается на построении полного логического объектно-ориентированного исчисления. По поводу построения такого исчисления имеются теоретические работы (например, [20]), но законченный и практически реализованный язык запросов нам неизвестен. Видимо, к этому же направлению строго теоретически обоснованных языков запросов можно отнести и работу Леллани и Спиратоса [21], основанную на алгебраической теории категорий.

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

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

В языке запросов объектно-ориентированной СУБД ORION [23-24] полностью поддерживается принцип инкапсуляции объектов. В реализованном варианте языка запросы могут основываться только на одном классе (хотя в [24] описывается подход к определению запроса на нескольких классах в стиле расширения семантики реляционного оператора соединения). Синтаксис языка ориентирован на SQL. Очень развит набор допустимых предикатов селекции. В частности, для атрибута, доменом которого является суперкласс, можно указать имя интересующего пользователя подкласса.

Язык запросов системы Iris [25-26] находится в значительной степени под влиянием реляционной парадигмы. Даже название этого языка OSQL отражает его тесную связь с реляционным языком SQL. По сути дела, OSQL - это реляционный язык, рассчитанный на работу с ненормализованными отношениями. Естественно, при таком подходе в OSQL нарушается инкапсуляция объектов.

На наш взгляд, особый интерес представляет декларативный язык запросов системы O2 RELOOP [27]. В общих словах, это декларативный язык запросов с SQL-ориентированным синтаксисом, основанный на специально разработанной для модели O2 алгебре объектов и значений. (Кстати, это не единственная работа в направлении построения алгебры для объектно-ориентированных моделей данных. См., например, [28].) На наш взгляд, особенно впечатляющим качеством языка RELOOP является естественность его построения в общем контексте модели O2. Запрос задается всегда на значении-множестве или списке. Если мы вспомним, что долговременному классу в O2 соответствует одноименное значение-множество, то тем самым можно определить запрос на любом хранимом классе. Результатом запроса может являться объект, значение-множество или значение-список. При этом элементами значений-множеств могут являться объекты (простая выборка), либо значения-кортежи с элементами-объектами разных классов (например). В совокупности эти особенности языка позволяют формулировать запросы над несколькими классами (специфическое соединение, порождающее не новые объекты, а кортежи из существующих объектов), а также употреблять вложенные подзапросы.

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

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

В большинстве систем по сути дела применяется тот же подход к оптимизации запросов, который использовался в реляционных системах: формируется набор альтернативных планов, оценивается стоимость каждого из них и выбирается план с наименьшей стоимостью. (Подробный обзор современных методов оптимизации запросов в реляционных СУБД и нерешенных проблем можно найти в [29].) Возможность применения такого подхода в СУБД ORION и O2 (да и в других) опирается на то, что объекты в этих системах не полностью инкапсулированы. Наряду с методами, в объектах видны и некоторые атрибуты, и если условие выборки задано через эти атрибуты, оптимизатор запросов, которому известны внутренняя структура объектов и набор существующих индексов, получает возможность выбора. Если же условие выборки можно формулировать только через методы, при подходах ORION и O2 единственным возможным способом выборки объектов класса будет последовательный просмотр всех объектов этого класса.

Здоник [30] отмечает, что основная проблема с оптимизацией запросов к ООБД связана с расширяемостью набора типов в такой БД. Каждый новый тип вводит собственную алгебру, неизвестную оптимизатору запросов. Например, оптимизатор не имеет информации о возможной коммутативности двух операций типа и т.д. Здоник полагает, что возможному решению проблемы оптимизации могло бы способствовать формальное определение алгебраических свойств операций типа при его разработке. Примерно такой подход применяется в оптимизаторах, основанных на наборе правил, применяемых в расширяемых СУБД (например, [31]).

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

Взгляд на реляционную алгебру

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

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

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

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

Заметим, что хотя в реляционной модели данных имя схемы отношения совпадает с именем экземпляра отношения (это очень похоже на то, как в ООБД имя класса часто пытаются использовать одновременно как имя типа объекта и имя множества объектов), неявно возникает понятие типа отношения, которое не обязательно именовать по причине простоты определения эквивалентных (однотипных) схем отношений.

Основные определения и формулировка алгебры классов

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

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

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

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

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

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

Объединение классов.

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

Тип результирующего класса совпадает с типом классов-операндов. После выполнения операции результирующий класс становится суперклассом обоих классов-операндов. Обозначим классы-операнды A и B, а результирующий класс - C. Все объекты классов A и B непосредственно принадлежат также и классу C.

Пересечение классов.

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

Тип результирующего класса совпадает с типом классов-операндов. После выполнения операции результирующий класс становится подклассом каждого из классов-операндов. Обозначим классы-операнды A и B, а результирующий класс - C. Все объекты, непосредственно принадлежащие классу C, непосредственно принадлежат также и классам A и B.

Декартово произведение классов.

Операция декартова произведения классов является двуместной и применима к любым двум классам решетки классов (статической или динамической).

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

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

Селекция класса.

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

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

Проекция класса.

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

Тип результирующего класса C является супертипом типа класса A с сигнатурой, полученной путем удаления из сигнатуры типа класса A функций, указанных в S. Объекты класса C являются вновь создаваемыми объектами ООБД и обладают новыми идентификаторами. Хотя тип класса C является супертипом типа класса A, класс С не является суперклассом класса A. В динамической решетке классов его можно считать только подклассом корневого класса динамической решетки классов.

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

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

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

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

Оптимизация запросов к ООБД

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

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

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

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

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

Особенности управления транзакциями в системах ООБД

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

Какой-либо подход, в котором предлагался бы полный набор средств управления транзакциями, полностью согласующийся с парадигмой объектной ориентированностью, нам неизвестен. Одна из наиболее продвинутых работ, проводимых в этом направлении в рамках германского проекта VODAK, описывается в [93].

В основе управления транзакциями в системе VODAK находится разработанный ранее в контексте инженерных СУБД механизм транзакций со вложенными подтранзакциями [109]: вызов любого действия в объекте равносилен образованию новой подстранзакции. В отличие от традиционного механизма вложенных подтранзакций в данном случае заранее не определена максимальная вложенность транзакций. При синхронизации транзакций используется знание о семантике объектов, в том числе информация о коммутативности операций. (Аналогичный подход описан в [110].)

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

Размещено на Allbest.ru