Языки программирования объектно-ориентированных баз данных и оптимизация запросов

Сергей Кузнецов

Введение
Две функции языка программирования ООБД
Общее представление языка запросов ООБД
Оптимизация запросов в системах ООБД
Заключение
Список литературы

Введение

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

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

Часто возникает впечатление, что хотя ограничения существующих систем пытаются объяснять некими принципиальными соображениями (например, что развитые возможности конструирования классов, подкрепленные средствами наследования классов позволяют ограничиться запросами только на одном классе объектов), на самом деле эти ограничения являются следствием недостаточно развитой технологии. Кажется, что в условиях отсутствия признанного лидера в области ООСУБД (каким была, например, компания IBM со своим проектом System R в области РСУБД), единственным путем к выработке такой технологии является продолжающаяся (иногда дублирующая) работа исследователей.

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

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

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

1. Две функции языка программирования ООБД

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

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

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

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

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

2. Общее представление языка запросов ООБД

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

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

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

3. Оптимизация запросов в системах ООБД

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

Оптимизация запросов хорошо исследована и разработана в контексте реляционных БД [9]. Известны методы синтаксической и семантической оптимизации на уровне непроцедурного представления запроса, алгоритмы выполнения элементарных реляционных операций, методы оценок стоимости планов запросов.

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

На самом деле, похожая ситуация существует и в РСУБД, при оптимизации запроса над представлением БД. В этом случае условия также формулируются в терминах внешних атрибутов (атрибутов представления), и в целях оптимизации запроса эти условия должны быть преобразованы в условия, определенные на атрибутах хранимых отношений. Хорошо известным методом такой "предоптимизации" является подстановка представлений [10], которая часто (хотя и не всегда в случае использования языка SQL) обеспечивает требуемые преобразования. Альтернативным способом выполнения запроса на представлением (иногда единственным возможным) является материализация представления.

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

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

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

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

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

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

Шаг D: Если теперь появились конъюнкты, представляющие собой простые предикаты сравнения на основе переменных состояния и констант, использовать эти конъюнкты для выработки оптимального плана выполнения запроса. Если же такие конъюнкты получить не удалось, единственным способом "отфильтровать" (супер)класс объектов является его последовательный просмотр с полным вычислением (возможно упрощенного) логического выражения для каждого объекта.

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

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

Заключение

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

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

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

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

Литература

Malkolm Atkinson, Francois Bansilhon, David DeWitt, Klaus Dittrich, David Maier, Stanley Zdonik. The Object-Oriented Database System Manifesto // 1st Int. Conf. Deductive and Object-Oriented Databases, Kyoto, Japan, Dec. 4-6, 1989
Kyung-Chang Kim, Won Kim, Darrell Woelk. Acyclic Query Processing in Object-Oriented Databases // Entity-Relationship Approach: Bridge User: 7th Int. Conf., Rome, Nov. 16-18, 1988.- 329-346
B. Paul Jenq, Darrell Woelk, Won Kim, Wan-Lik Lee. Query Processing in Distributed ORION // Advances in Database Technology - EDBT'90.- Lecture Notes in Computer Science.- 416, 1990.- 169-187
C. Lecluse, P. Richard. The O2 Database Programming Language // 15th Int. Conf. Very Large Data Bases, Amsterdam, Aug. 22-25, 1989.- 411-422
O. Deux et al. The Story of O2 // IEEE Trans. Knowledge and Data Eng.- 2, N 1.- 1990.- 91-108
Sergei D. Kuznetsov. OODBMS's Query and Programming Languages: What Do They Provide and What Do We Need (Extended Abstract). Submitted to the Second East-West Workshop on Advanced Databases.
С.Д.Кузнецов. Об основаниях ненавигационных языков запросов систем объектно-ориентированных баз данных // Труды Рабочего семинара "Перспективы развития систем баз данных и информационных систем", М., Московская секция ACM SIGMOD, ИПИ РАН, 1993, стр. 44-53
С.Д.Кузнецов. О подходе к естественной интеграции объектно-ориентированного языка программирования и непроцедурного языка запросов к объектно-ориентированным базам данных. Представлено на Семинаре Киевской секции ACM SIGMOD, октябрь 1993.
С.Д.Кузнецов. Методы оптимизации выполнения запросов в реляционных СУБД // Тем. изд. "Итоги науки и техники. Вычислительные науки". Т.1. Стр. 76-153
Stonebraker M. Implementation of Integrity Constraints and Views by Query Modification // Proc. ACM SIGMOD Int. Conf. Manag. Data, San Jose, Calif., May 23-26, 1975. New York, 1975.- C. 65-78