Развитие объектно-ориентированных систем управления базами данных

Вид материала

Документы

Содержание Требования к ООСУБД Объектная ориентированность Поиск информации Существующие системы Направления поиска B1 Fransçois Bancilhon “Object-Oriented Database Systems”, ACM Press 1988 B2 F1 Leonidas Fegaras, David Maier “ F3 Leonidas Fegaras, David Maier “ S2 Anthony J.H. Simons, “Theory of Classification”, Journal of Object Technology, Vol.1 2, 2003 W1

Подобный материал:

• Реферат "Принципы проектирования и использования многомерных баз данных" Введение, 295.28kb.
• Программа дисциплины Системы управления базами данных Семестры, 22.73kb.
• Ландшафт области управления данными: аналитический обзор, 531.27kb.
• Системы управления базами данных, 313.7kb.
• «Прикладная информатика (по областям)», 1362.72kb.
• Сводный научный отчет за 2010 г по совместному проекту «Разработка объектно-ориентированных, 204.3kb.
• Проектирование базы данных, 642.58kb.
• Проектный практикум, 61.84kb.
• Программа вступительного экзамена по специальности 05. 13. 18 Математическое моделирование,, 115.33kb.
• Тема Базы данных. Системы управления базами даннях (12 часов), 116.1kb.

Развитие объектно-ориентированных систем управления базами данных

Антон Злыгостев sinclair@axmor.com


Don't worry about what anybody else is going to do… The best way to predict the future is to invent it. Really smart people with reasonable funding can do just about anything that doesn't violate too many of Newton's Laws!¹

Alan Kay, 1971

Введение

ODMG: 10 лет спустя

Прошло 10 лет с тех пор, как Object Data Management Group (ODMG) опубликовала свой стандарт языка для манипуляции объектными данными (ODMG 1.0). Этот шаг был призван упорядочить усилия разработчиков и исследователей всего мира, направленные на создание эффективных и гибких систем по управлению данными. Тем не менее, в настоящее время подавляющее лидерство остается за реляционными системами управления базами данных (РСУБД).

Целью данной работы является построение высокоэффективной объектно – ориентированной системы управления базами данных (ООСУБД), которая была бы лишена недостатков, присущих существующим системам.

Мотивация

К данному моменту опубликовано весьма значительное количество обоснований полезности и даже необходимости разработки ООСУБД, поэтому здесь я не буду подробно на этом останавливаться.

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

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

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

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

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

Требования к ООСУБД

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

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

Объектная ориентированность

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

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

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

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

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

Наиболее перспективным, с точки зрения эффективности труда, подходом в настоящее время считается поведенческий. Его основоположником является автор самого термина «ООП» Алан Кей. Именно этот подход предполагается положить в основу разрабатываемой системы. Перечислим те свойства, которые должны поддерживаться системой, с краткой расшифровкой принятого в данном контексте значения:

1. Идентичность. Существование указателей на объект, и возможность проверить тот факт, что два указателя указывают на один и тот же объект.
   
2. Инкапсуляция. Разделение интерфейса и его реализации. Интерфейс суть набор сообщений, которые обязан обрабатывать объект.
   
3. Классификация. Класс объекта полностью определяет его поведение. В сочетании с детерминизмом это свойство означает, что если двум объекта одного и того же класса послать одну и ту же последовательность сообщений, они будут находиться в неразличимых состояниях. В частности, с каждым классом ассоциирован набор интерфейсов, которые реализут все объекты данного класса.
   
4. Наследование. Интерфейсы могут быть унаследованы друг от друга. Объект, реализующий унаследованный интерфейс, обязан реализовывать и наследуемый интерфейс.
   
5. Полиморфизм. Наличие указателей на интерфейс, ведущих к возможности предоставить различные реализации одного и того же интерфейса его потребителям.
   

Надежность

Требования к надежности СУБД традиционно выражаются аббревиатурой ACID. Она расшифровывается следующим образом:

1. Atomicity – атомарность, возможность группировать действия в последовательности, которые гарантированно выполняются целиком либо не выполняются вообще. Такая группа действий называется транзакцией.
   
2. Consistency – целостность и согласованность. Гарантия того, что некоторый набор предикатов над совокупностью данных будет выполнен после окончания любой транзакции.
   
3. Isolation – изоляция. Возможность одновременного выполнения нескольких транзакций так, чтобы они «не мешали» друг другу, т.е. ограничения целостности выполнялись. Различают несколько уровней изоляции транзакций; максимальный – упорядочиваемый (serializable) – означает получение такого состояния совокупности данных в результате одновременного выполнения множества транзакций, которое эквивалентено результату выполнения тех же транзакций последовательно в некотором порядке.
   
4. Durability – сохраняемость. Гарантия того, что изменение данных, произошедшее в результате успешной транзакции, будет сохранено (на практике это требование смягчают, т.к. абсолютная сохраняемость недостижима в связи с техническими свойствами носителей).
   

Поиск информации

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

К проектируемой системе предъявляются следующие требования:

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

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

2. масштабируемость системы. В данном случае под масштабируемостью подразумевается достаточно медленное падение производительности при росте числа объектов в совокупности. Детальное обсуждение вопросов производительности выходит за рамки данного реферата. Вкратце установим, что хорошей масштабируемостью считается логарифмическая зависимость условной ресурсоемкости операций над совокупностью от числа объектов в ней (T ~ O(log(N))), удовлетворительной – линейная.
   

Существующие системы

История

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

Теоретики мотивируют необходимость таких систем и жалуются на отсутствие адекватного математического аппарата для построения эффективных и гибких систем: «В то время, как оригинальная работа Кодда установила цель, задав спецификацию реляционной системы (модель данных и язык запросов), подобной спецификации не существует для объектно-ориентированных систем. Отсутствует явный консенсус по поводу того, что считать объектно-ориентированной системой, не говоря уж об объектно-ориентированной системе базы данных²» ([B1])

В то же время практики строят работоспособные системы управления базами данных, в той или иной степени поддерживающими парадигму объектно-ориентированного программирования. Начиная с 1984 года Дэвид Майер, Джордж Коуплэнд и другие разрабатывают GemStone – объектно-ориентированную СУБД для языка Smalltalk ([M1], [M2]).

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

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

В 1993 году консорциум поставщиков ООСУБД ODMG (Object Database Management Group) выпускает стандарт ODMG 1.0. Этот стандарт описывает требования к основным компонентам ООСУБД:

- Языку определения объектов (ODL-93)

- Языку запросов к объектам (OQL-93)

- Взаимодействию с наиболее популярными на тот момент объектно-ориентированными языками программирования (С++ и Smalltalk).

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

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

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

В [G1] вводится промежуточный функциональный язык OFL для оптимизации выполнения запросов на произвольных языках объектных запросов (OQL). В [F1] Леонидас Фегарас в соавторстве с Дэвидом Майером вводят исчисление моноидов для эффективного представления запросов на OQL. Затем, в [F1, F2] это исчисление применяется для разворачивания вложенных запросов. Дальнейшее развитие данной теории проводится в [F3]. В [J1] и [Z1] предложены методы оптимизации выполнения агрегирующих запросов.

В конце девяностых теоретики ООСУБД предпринимают попытки обойти ограничения стандарта ODMG: в [L1] вводится новый дедуктивный язык объектно-ориентированных баз данных, в [B2] предложено расширение ODMG для поддержки семантической оптимизации запросов.

Критика

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

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

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

Однако совсем недавно в Journal of Object Technology вышел (и продолжает выходить цикл статей Антони Симонса (Anthony J.H. Simons) [S2], в котором автор делает попытку представить все многообразие объектных моделей в систематическом виде. Это позволяет надеяться на прогресс в области формализации существующих решений ООСУБД и поиску новых, которые не были замечены во время этапа эмпирического поиска.

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

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

Направления поиска

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

Во-первых, предполагается рассмотреть модель, основанную на поведении, а не структуре объектов. Основные вопросы и идеи, требующие исследования:

• Определение семантики предикатов и формализация требования П2 в рамках данного подхода.
  
• Анализ выполнимости требования П2 для различных случаев. Рассмотрение концепции индексации данных, как возможности модификации их представления без изменения семантики модели. Сравнение данной концепции с методиками индексации, применяемыми в РСУБД (одномерные индексы, многомерные индексы, полнотекстовый поиск, агрегатные индексы в OLAP-системах). Определение набора метаданных, необходимого и достаточного ядру системы для оптимизации предикатных запросов.
  
• Анализ выполнимости требований Н1-Н2 в рамках данного подхода. Рассмотрение Java–подобного механизма исключений для управления транзакциями. Определение набора метаданных, необходимого ядру системы для оптимизации поддержки восстановления от сбоев. (Возможные кандидаты: флаг наличия/отсутствия у метода побочных эффектов как признак выполнимости в рамках предикатного запроса и определения необходимого уровня блокировки; включение списка исключений в сигнатуру метода для управления журналированием)
  
• Применение смешанных вычислений для глобальной оптимизации модели: набор методов определяет выполняемые запросы; имея должную метаинформацию как о семантике, так и о представлении объектов, можно статически построить оптимальные планы выполнения этих запросов.
  

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

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

для подмешивания требуемой функциональности в пользовательский тип.

Ссылки

B1 Fransçois Bancilhon “Object-Oriented Database Systems”, ACM Press 1988

B2 Domenico Beneventano, Sonia Bergamaschi “Description Logics for Semantic Query Optimization in Object-Oriented Database Systems”, ACM Transactions on Database Systems, Vol. 28, No. 1, March 2003

C1 Michael J. Carey et al, “The BUCKY Object-Relational Benchmark”, Proceedings of the 1997 ACM SIGMOD international conference on Management of data

F1 Leonidas Fegaras, David Maier “Towards an Effective Calculus for Object Query Languages”, ACM Press 1995

F2 Leonidas Fegaras “Query unnesting in object-oriented databases”, ACM SIGMOD Record, Proceedings of the 1998 ACM SIGMOD international conference on Management of data

F3 Leonidas Fegaras, David Maier “Optimizing object queries using an effective calculus”, ACM Transactions on Database Systems (TODS) 2000

G1 Georges Gardarin, Fernando Machuca, Philippe Pucheral “OFL: A Functional Execution Model for Object Query Languages”, ACM Press 1995

J1 Michael Jaedicke, Bernhard Mitschang, “On Parallel Processing of Aggregate and Scalar Functions in Object-Relational DBMS”, Proceedings of the 1998 ACM SIGMOD international conference on Management of data

L1 Mengchi Liu, Gillian Dobbie, “A Logical Foundation for Deductive Object-Oriented Databases”, ACM Transactions on Database Systems, Vol. 27, No. 1, 2002

M1 George P. Copeland, David Maier “Making Smalltalk a database system” Proceedings of the ACM/SIGMOD international Conference on the Management of Data, 1984.

M2 David Maier, Jacob Stein, Allen Otis, Alan Purdy “Development of an object-oriented DBMS”, ACM Press 1986

S1 Alan Snyder, “Encapsulation and inheritance in object-oriented programming languages”, Proceedings of OOPSLA '86, ACM SIGPLAN Notices, 21(11):38-45, 1986

S2 Anthony J.H. Simons, “Theory of Classification”, Journal of Object Technology, Vol.1 2, 2003

W1 Kim, W., “Object-Oriented Database Systems: Promises, Reality, and Future,” in Modern Database Systems: The Object Model, Interoperability and Beyond, pp. 255-280, Kim, W., ed., ACM Press, Addison Wesley, 1995

Z1 Donghui Zhang, Vassilis J. Tsotras, Dimitrios Gunopulos, “Efficient Aggregation over Objects with Extent”, ACM PODS June 2002