На правах рукописи

Казаков Илья Анатольевич

МЕТОДЫ ОБРАБОТКИ РЕЛЯЦИОННЫХ

ДАННЫХ В ОБЪЕКТНЫХ ДЕСКРИПТИВНЫХ

ЛОГИКАХ

05.13.17 – теоретические основы информатики

Автореферат

диссертации на соискание учёной степени

кандидата физико-математических наук

Красноярск 2012

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

Научный руководитель:

профессор Манцивода Андрей Валерьевич

Официальные оппоненты: доктор физико–математических наук, доцент Пальчунов Дмитрий Евгеньевич, Институт математики СО РАН, лаборатория теории вычислимости и прикладной логики, ведущий научный сотрудник доктор физико–математических наук, профессор Сафонов Константин Владимирович, ФГБОУ ВПО Сибирский государственный аэрокосмический университет, кафедра прикладной математики, заведующий кафедрой Федеральное государственное бюджетное

Ведущая организация:

учреждение науки Институт проблем управления им. В. А. Трапезникова Российской академии наук (г. Москва)

Защита состоится 29 мая 2012 г. в 14 часов 15 минут на заседании диссертационного совета Д 212.099.11 при Сибирском федеральном университете по адресу: 660074, г. Красноярск, ул. акад. Киренского, 26, ауд. УЛК 115.

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

Автореферат разослан 28 апреля 2012 г.

Учёный секретарь диссертационного совета Покидышева Людмила Ивановна

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

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

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

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

Motik B. Bridging the Gap Between OWL and Relational Databases// In proc.: The 16 th International Conference on World Wide Web. ACM Press, 2007. P. 807– Rosati R. On Combining Description Logic Ontologies and Nonrecursive Datalog Rules // Lecture Notes in Computer Science. Springer, 2008. V. 341. P. 13–27.

Mazzocchi S. Closed World vs. Open World // The First Semantic Web Battle. 2005. – URL:

http://www.betaversion.org/ stefano/linotype/news/91/ Цель диссертационной работы: Разработка метода обработки реляционных данных в рамках объектной дескриптивной логики, а также реализация и апробирование данного метода на основе системы распределенной обработки информации.

Основные задачи диссертационной работы.

1. Разработка метода формализации реляционных структур данных в рамках объектных дескриптивных логик OODL.

2. Разработка метода аксиоматизации замкнутого мира баз данных на языке дескриптивной логики.

3. Разработка подхода к построению алгебр Кодда в рамках логики 4. Реализация и апробирование метода распределенной обработки реляционных данных в OODL в рамках системы обработки знаний Libretto.

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

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

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

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

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

Основные положения, выносимые на защиту:

1. Метод формализации реляционных структур данных в логике OODL и его обоснование.

2. Аксиоматическая система, описывающая парадигму замкнутого мира баз данных на языке дескриптивных логик, и теорема о минимальной 3. Метод определения операций алгебры Кодда в рамках объектных теорий баз данных и его обоснование.

4. Апробация подхода к логической обработке реляционных данных на основе экспериментальной реализации метода формализации реляционных структур в рамках системы Libretto.

Личный вклад автора состоит в следующем:

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

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

3. Формализованы базовые операции алгебры Кодда в логике OODL, показана их выразимость на языке Libretto, а также доказано, что преобразования теорий баз данных полностью соответствуют преобразованиям баз данных при аналогичных операциях алгебры Кодда (в нераздельном соавторстве совместно с руководителем и А.А. Гаврюшкиной).

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

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

1. Свидетельство о регистрации программы для ЭВМ No. Система разработки методанных для мультимедийных ресурсов от 11 января 2011 г. Правообладатель ГОУ ВПО ИГУ. Авторы Москвина А.С., Казаков И.А., Манцивода А.В., Кохо М.А.

2. Свидетельство о регистрации программы для ЭВМ No. Онлайн система поддержки работы отдела аспирантуры высшего учебного заведения от 22 января 2010 г. Правообладатель ГОУ ВПО ИГУ. Авторы Казаков И.А., Малых А.А., Манцивода А.В.

3. Всероссийская научно-методическая конференция Телематика (Санкт-Петербург, 2008, 2009, 2011 гг.).

4. Международная конференция Мальцевские чтения (Новосибирск, 5. Всероссийская конференция Искусственный интеллект и управление (ИИУ-2011, Геленджик, 2011).

Публикации. По результатам диссертации опубликовано 7 научных статей, тезисов, докладов (в том числе 2 статьи в журналах, входящих в Перечень ведущих и рецензируемых журналов и изданий ВАК РФ 2008г. ).

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

Основное содержание работы

Во введении диссертации дается краткий анализ работы, ее значимость и актуальность. Приводится обзор и описание структуры работы.

В первой главе производится общее описание проблематики исследования, приводится обзор литературы и наработок из области исследования. В разделе 1.2 приводятся общие сведения о дескриптивных логиках.

В разделе 1.3 подробно рассказывается о логике OODL и об объектных теориях. В разделе 1.4 приводятся общие сведения о базах данных. В разделе 1.5 рассказывается о построении объектной теории базы данных, а в разделе 1.6 рассказывается о том, что необходимо сделать для того, чтобы построенную теорию привести в соответсвие с замкнутым миром баз данных – дополнить теорию аксиомами замкнутости.

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

Первое направление связано с интерпретацией теорий в дескриптивных логиках как баз данных. В этом контексте можно упомянуть как работы, базирующиеся на представлении в дескриптивных логиках ER-моделей (например, Bergamaschi et al, 19941 и Calvanese et al, 19992 ), так и методы семантического описания данных, напрямую базирующиеся на дескриптивBergamaschi S., Nebel B. Acquisition and validation of complex object database schemata supporting multiple inheritance. Applied Intelligence, 1994. 4(2). P. 185–203.

Calvanese D., Lenzerini M., Nardi D. Unifying class-based representation formalisms. Journal of Articial Intelligence Research, 1999. Ch. 11. P. 199–240.

ных логиках Borgida et al, 19893 и Bergamaschi et al, 19924. Отметим, что данные работы, ориентируясь на объектное представление информации, не позволяют работать с реляционными структурами.

Второе направление реализует идею работы с реляционными базами данных через механизмы абстрактного и концептуального представляения на основе ER–моделей (entity–relationship models). Этот подход обсуждается в Borgida et al, 20045. Основной проблемой данного подхода является то, что он не позволяет работать с базами данных напрямую, а использует для этого посредника в виде ER–моделей. Это снижает практическую значимость, поскольку ER–модели используются и поддерживаются при разработке баз данных далеко не всегда. Сами ER–модели сложны для обычного разработчика, поэтому появление дополнительной логической надстройки над ER–моделями делает данный подход недоступным для широких кругов пользователей.

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

Здесь основная группа исследований связана с объединением формализмов дескриптивных логик (используемых для концептуального описания предметных областей) и правил языка типа Datalog (для работы с реляционными данными). С этим направлением связано большое количество работ, среди которых можно упомянуть Motik et al. 20056 и Rosati, 20057.

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

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

Ключевым отличием нашего подхода от других является то, что мы не счиBorgida A., Etherington D. Hierarchical knowledge bases and ecient disjunctive reasoning. Proceedings of the rst international conference on Principles of knowledge representation and reasoning. December 1989.

P. 33–43.

Bergamaschi S., Sartori C. On taxonomic reasoning in conceptual design, ACM Transactions on Database Systems (TODS), 1992. V.17 n.3, P. 385–422.

Borgida A., Lenzerini M., Rosati R. Description Logic Handbook // The Description Logic Handbook:

Theory, Implementation, and Applications. Cambridge University Press, 2004. Ch 16 – Description Logics for Data Bases. P. 472– Motik B., Sattler U., Studer R. Query answering for OWL-DL with rules. Journal of Web Semantics, 2005. 3(1). P. Rosati R. On the decidability and complexity of integrating ontologies and rules. Joutnal of Web Semantics, 2005. 3(1) P. 61 73.

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

Из этого немедленно следует, что свойством замкнутости можно и нужно управлять. Другими словами, должна существовать возможность явного указания, какая часть данных обладает свойством замкнутости, а какая не обладает (например, может постепенно расширяться). На самом деле и в подходах, упомянутых выше, такая возможность имеется. Например, в Datalog свойство замкнутого мира реализуется через использование немонотонного правила отрицание как неудача ( negation as failure ), унаследованного от языка Prolog. Разработчик базы данных имеет возможность выбора – применять это правило, или нет. Но цена такого решения высока, поскольку гибридный формализм, объединяющий дескриптивные логики и правила Datalog, является сложным как с теоретической точки зрения (например, в работе Rosati 20088 было показано, что он имеет высокий уровень сложности даже в случае нерекурсивных описаний в Datalog), так и практической. Мы считаем, что высокая сложность не оставляет шансов для широкого применения данного подхода на практике, поскольку требует от пользователя уровня компетентности, недоступного для основной массы разработчиков баз данных.

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

Rosati R. On Combining Description Logic Ontologies and Nonrecursive Datalog Rules // Lecture Notes in Computer Science. 2008. Vol. 341. Web Reasoning and Rule Systems. P. 13 27.

Подчеркнем, что в данном обзоре не затрагиваются методы, ориентированные на работу с данными в рамках очень выразительных дескриптивных логик (см., например, Hustadt 20059 ). Во главу угла нами ставилась не выразительность (выразительных логик достаточно много), а задача адаптации логик к программированию и веб-технологиям. Здесь мы следовали хорошо известному принципу, приписываемому Тому Мелхаму10 :

формальные методы не будут оказывать серьезное влияние до тех пор, пока не смогут применяться людьми, которые в них ничего не понимают ( formal methods will never have a signicant impact until they can be used by people that don’t understand them ).

В разделе 1.3 подробно рассказывается о логике OODL и об объектных теориях.

Рассмотрим дескриптивную логику OODL. Язык этой логики включает имена концептов Ci, имена ролей Ri, имена доменов Di, имена объектов Oi, логические константы и и квантор всеобщности T.F, где T – роль или атрибут, а F – либо атомарный концепт, либо имя типа данных из D. Кроме того, в OODL включаются – инверсные роли при кванторах всеобщности: T.F, где T – либо роль, либо атрибут, а F – либо атомарный концепт, либо имя типа – кардинальности n.T и n.T, где n N0, а T – либо роль, либо атрибут, либо инверсия роли/атрибута.

Определение 1 Выражениями логики OODL являются:

где C – имя концепта, F – произвольный концепт, T – свойство • Фактологические аксиомы (факты) C(o), R(o, o ), P (o, v), где C, R, P – имена концепта, роли и атрибута, соответственно, o, o – имена объектов, v – элемент типа данных.

Hustadt U., Motik B., and Sattler U. Data complexity of reasoning in very expressive description logics.

In Proc. of IJCAI 2005, pages 466–471, 2005.

Pierce, Benjamin. Types and Programming Languages. MIT Press, 2002. P. 339.

Определим интерпретацию I конструкций OODL. Выражения OODL интерпретируются на множестве объектов, причем имена объектов oi интерпретируются как элементы основного множества oI, концепты – как подмножества F, роли и атрибуты – как подмножества декартовых произведений RI и P I D, соответственно. Интерпретация I выражений OODL на множестве объектов должна удовлетворять следующим правилам. Семантика концептов:

Семантика аксиом:

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

Определение 2 Объектной теорией O логики OODL в словаре W = Малых А.А., Манцивода А.В. Объектно–ориентированная дескриптивная логика // Известия ИГУ.

Серия математика. – No.1. – 2011. С.57–72.

C, R, P, O назовем непротиворечивую теорию, T Box которой состоит из конечного множества аксиом наследования, домена, ранга, max– и min–кардинальности, удовлетворяющую следующим условиям:

1. множество аксиом наследования в O ациклично;

2. каждое свойство T (R P) обладает в O ровно одной аксиомой домена и ровно одной аксиомой ранга.

В разделе 1.4 приводятся общие сведения о базах данных.

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

Считаем, что каждая область данных содержит выделенный элемент NULL, причем Обозначим Пусть ID и A счетные множества имен (идентификаторов) и D конечное множество имен доменов. Множества ID, A и D попарно не пересекаются.

Определение 3 k-местное табличное отношение есть тройка r = Rr, body r, headerr, где Rr ID – имя отношения;

имя домена Dij для 1 j k, причем Ai = Aj при i = j.

Конечное множество body r называется телом табличного отношения, а кортеж headerr заголовком r.

Сигнатурой (sign(r)) отношения r назовем множество а элементы сигнатуры атрибутами. Будем говорит, что атрибут A имеет тип данных D в отношении r, если пара A, D является одной из координат заголовка отношения r.

Будем говорить, что табличные отношения r1 и r2 согласованы, если либо sign(r1 ) sign(r2 ) =, либо типы данных атрибутов из sign(r1 ) sign(r2 ) в отношении r1 и в отношении r2 совпадают.

Определение 4 База данных DB = {r1, r2,..., rn } это конечное множество попарно согласованных табличных отношений. Сигнатурой базы данных DB назовем множество всех ее атрибутов: sign(DB) = i=1 sign(r ).

В разделе 1.5 описано как по базе данных DB построить объектную теорию этой базы данных ODB. Объектная теория ODB содержит всю позитивную информацию о базе данных DB, то есть явно определяет, что в ней содержится. Однако базы данных основаны на парадигме замкнутого мира. Это означает, что для корректного определения базы данных как объектной теории необходимо описать также негативную информацию, то есть описать то, чего нет в базе данных. Поэтому в разделе 1.4 понятие теории базы данных расширено добавлением аксиом замкнутости CW.

В разделе 1.6 доказана основная теорема, которая утверждает, что введенные аксиомы замкнутости вместе с объектной теорией однозначно задают базу данных:

Теорема 1 Пусть DB база данных с объектной теорией O и множеством аксиом замкнутости CW. Для любой интерпретации I следующие условия эквивалентны:

2. I является минимальной моделью O.

Данная теорема показывает, что теория O + CW допускает только те модели, позитивная информация которых полностью описывается теорией O.

Другими словами, эти модели не могут содержать никакую дополнительную информацию, кроме описанной в O.

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

Таким образом основным результатом первой главы является обоснованный метод формализации реляционных структур в логике OODL и аксиоматическая система позволяющая описать парадигму замкнутого мира в логике SHOIN (D).

Во второй главе показано, что операции алгебры Кодда выразимы в терминах объектных теорий.

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

В разделе 2.1 приводятся определения операций алгебры Кодда. Реляционная алгебра Кодда представляет собой набор таблиц баз данных с заданными на них операциями. Основными операциями алгебры Кодда являются: операция выборки, операция проекции, операция пересечения, операция объединения, операция декартова произведения.

Будем говорить, что атрибуты A и B некоторой базы данных DB согласованы, если они имеют один и тот же тип данных в DB. Также, будем говорить, что атрибут A согласован с некоторым элементом v D, где D D, если атрибут A имеет тип данных D в DB.

Определение 5 Пусть DB – база данных. Выражение A rel x назовем элементарным предикатом выборки, где A sign(DB), x (sign(DB) D), A согласован с x и rel {=, =,, }. Предикат выборки – это либо элементарный предикат выборки, либо один из ¬p1, p1 p2, p1 p2, где p1, p2 – предикаты выборки.

Предикат выборки p определен на отношении r = Rr, body r, headerr, если все атрибуты, входящие в p, принадлежат сигнатуре r. Предикат p истинен на кортеже t body r (обозначаем DB |= p(t), где DB база данных, содержащая отношение r), если p определен на r, и при подстановке вместо каждого атрибута A, входящего в p, значения t(A), получившееся булево выражение является истинным, где истинность элементарных предикатов определяется истинностью полученных равенств и неравенств в соответствующих доменах (предполагаем, что каждая область данных линейно упорядочена по типу натуральных, целых или рациональных чисел).

Пусть предикат выборки p определен на отношении r, в таком случае на r определена операция выборки:

где r – отношение с новым именем Rr ID, такое, что В разделе 2.2 операции алгебры Кодда формализуются на языке объектных теорий. Пусть O + CW объектная теория с аксиомами замкнутости базы данных DB и C1, C2 концепты, соответсвующие в теории O табличным отношениям r1, r2. Для каждой операции алгеры Кодда мы ввели аналог этой операции на объектных теориях (обозначим через ) и описали алгоритм преобразования объектной теории O + CW в объектную теории O + CW под действием операции, примененной к концепту C1 (концептам C1 и C2 ).

Рассмотрим операцию выборки с предикатом выборки p, примененную к отношению r DB.

Лемма 1 Пусть O+CW объектная теория с аксиомами замкнутости базы данных DB, C концепт, соответствующий в теории O табличному отношению r, Ep аналог операции выборки p, тогда 1) Ep применима к концепту C тогда и только тогда, когда p (r) определено, 2) Если Ep применима к концепту C, то теория O + CW, полученная из теории O + CW под действием операции EP примененной к концепту C, является теорией базы данных DB {p (r)} Утверждения леммы верны также для всех остальных операций алгебры Кодда. Таким образом, верна теорема:

Теорема 2 Операции алгебры Кодда определимы в объектных теориях баз данных.

Эта теорема доказывает, что построенный нами формализм является в полной мере подходящим для описания баз данных.

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

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

В разделе 3.1 приводится описание архитектуры системы Libretto.

Это необходимо для описания всех аспектов практического применения разработанного метода. Система Libretto базируется на одноименном языке запросов к хранилищам объектных моделей. Архитектура системы Libretto позволяет реализовать различные подходы к работе с БД.

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

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

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

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

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

Функции Libretto API, используемого для реализации метода подмены хранилища, можно разделить на два типа:

1. функции, относящиеся к структуре онтологии, такие как получение информации о классах, т- или о-свойствах;

2. функции, относящиеся к объектам, такие как получение объектов, значений их т- или о-свойств.

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

В разделе 3.4 рассматривается метод трансляции Libretto– программ в SQL. Основная идея данного метода – это подмена интерпретатора языка Libretto. Вместо абстрактной Libretto–машины новый транслятор переводит Libretto–код непосредственно в SQL. В связи с ограничениями, обусловленными различием архитектур Libretto и SQL, таким образом может быть оттранслирован код, написанный на ограниченном подмножестве Libretto. Если запрос выходит за рамки этого подмножества, то можно использовать первый способ – подмены хранилища.

Для реализации данного метода определяется подмножество Libretto, на котором будет работать транслятор:

Определение 6 Определим множества Libretto–запросов Lsql и предикатов Psql как наименьшие множества, удовлетворяющие следующим условиям:

1. если N – имя класса или свойства, то N Lsql и N является 2. если N – имя свойства, то инверсное свойство N Lsql и N является шагом.

3. если d D, где D – тип данных (целочисленный, строковый и т.д.), то d Lsql и d является шагом.

4. если S Lsql является шагом и R Psql, то S[R] Lsql и также является шагом.

5. если P, S Lsql, причем S является шагом, то P/S Lsql.

7. если R1, R2 Psql, то Трансляция в SQL производится на основе набора правил и шаблонов.

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

В общем случае запрос на Libretto имеет форму пути, состоящего из нескольких шагов:

Нулевой шаг – start – задает начальный контекст, от которого производятся все дальнейшие переходы. Промежуточные шаги step1, step2,...

задают последовательность переходов. Последний шаг stepN определяет значение всего запроса. Если интерпретировать данный путь как запрос к базе данных, то на первом шаге мы получаем один или несколько объектов, которые интерпретируются как строки таблицы. Переход от шага к шагу интерпретируется как переход по связям между таблицами. Последний шаг обозначает получаемое значение, которое в SQL–запросе находится в блоке SELECT. Внутри каждого шага может присутствовать предикат в квадратных скобках, фильтрующий контекстные значения.

В разделе также рассматриваются варианты Libretto–запросов, не подпадающие под общую схему работы. К ним можно отнести обработку инверсного о-свойства в Libretto–запросе, формирование вложенных SQL– запросов, а также трансляцию Libretto–предикатов.

С использованием правил трансляции нами был разработан транслятор подмножества языка Libretto в SQL. На основе комплекса вычислительных экспериментов, проведенных на БД реального уровня, был сделан сравнительный анализ двух подходов – подмены хранилища и подмены интерпретатора. Эксперименты продемонстрировали очевидные преимущества в плане эффективности метода, основанного на подмене интерпретатора. В среднем ускорение составляет 1–2 порядка по сравнению с методом подмены хранилища. Таким образом, если структура запроса позволяет применить к нему метод подмены интерпретатора, то нужно выбирать этот вариант, и только в обратном случае необходимо обращаться к хотя и более общему, но принципиально менее эффективному методу подмены хранилища.

В заключении сформулированы основные результаты, полученные в работе.

Результаты и выводы Основным результатом работы является формализация реляционных баз данных в дескриптивной логике SHOIN (D). Формализация подразумевает под собой:

1. Описание реляционных данных средствами логики OODL– через построение объектных теорий баз данных;

2. Решение проблемы несоответствия парадигм замкнутого мира баз данных и открытого мира дескриптивных логик через расширение объектных теорий баз данных аксиомами замкнутости;

3. Моделирование реляционных структур на алгебраическом уровне через представление операций алгебры Кодда в терминах логики 4. Апробация подхода к логической обработке реляционных данных на основе экспериментальной реализации метода формализации реляционных структур в рамках системы Libretto.

Основные положения дисертации опубликованы в следующих работах.

Работы, опубликованные в изданиях, рекомендованных ВАК РФ:

1. Казаков И. А. Алгебры Кодда и дескриптивные логики // Изв. Иркут.

гос. ун-та. Сер.: Математика. – 2011.– Т. 4, № 3. –C. 68– 2. Казаков И. А., Манцивода А.В. Базы данных как онтологии // Изв.

Иркут. гос. ун-та. Сер.: Математика. – 2011.– Т. 4, № 1. –C. 20– Работы, опубликованные в других научных изданиях:

1. Gavryushkina A.A., Kazakov I.A. A formalization of the Codd’s relational algebra in logic SHOIN(D) [Text] // International conference "Mal’tsev meeting". - Novosibirsk, 2011. - P. 134-135.

2. Казаков И.А. Объектные теории баз данных [Текст] // Труды 4-й Всероссийской мультиконференции по проблемам управления МКПУ– 2011. – 2011. – С. 145–147.

3. Казаков И.А. Управление базами данных в системах онтологий [Текст] // Труды XVIII Всероссийской научно-методической конференции ”Телематика’2011”. – С–Пб., 2011. – С. 266–268.

4. Манцивода А.В., Казаков И.А. Система поддержки деятельности аспирантуры ИГУ на базе OntoBox // Труды XVI Всероссийской научно-методической конференции ”Телематика’2009”. – С–Пб., 2009.

5. Малых А.А., Казаков И.А. Доступ к онтологиям через WEB. Базовый подход в системе Мета2 // Труды XV Всероссийской научнометодической конференции ”Телематика’2008”. – С–Пб., 2008. – С.