автореферат диссертации по информатике, вычислительной технике и управлению, 05.13.17, диссертация на тему:Методы обработки реляционных данных в объектных дескриптивных логиках

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

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

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

ЛОГИКАХ

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

Автореферат диссертации на соискание учёной степени кандидата физико-математических наук

1 7 м.М> 2012

005044145

Красноярск — 2012

005044145

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

Научный руководитель: доктор физико-математических наук,

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

Официальные оппоненты: доктор физико-математических наук, доцент

Пальчунов Дмитрий Евгеньевич, Институт математики СО РАН, лаборатория теории вычислимости и прикладной логики, ведущий научный сотрудник

доктор физико-математических наук, профессор Сафонов Константин Владимирович, ФГБОУ ВПО «Сибирский государственный аэрокосмический университет», кафедра прикладной математики, заведующий кафедрой

Ведущая организация: Федеральное государственное бюджетное

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

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

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

Автореферат разослан

апреля 2012 г.

Учёный секретарь диссертационного совета

Покидышева Людмила Ивановна

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

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

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

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

'Motik В. Bridging the Gap Between OWL and Relational Databases// In proc.: The 16 th International Conference on World Wide Web. ACM Press, 2007. P. 807-81G

2Rosati E. On Combining Description Logic Ontologies and Nonrecursive Datalog Rules // Lecture Notes in Computer Science. Springer, 2008. V. 341. P. 13-27.

3Maz/o<chi S. Closed World vs. Open World // The First Semarilie Web Bal.ll«. 2005. - URL: http://www.betaversion.org/ stefano/linotype/news/91/

Цель диссертационной работы: Разработка метода обработки реляционных данных в рамках объектной дескриптивной логики, а также реализация и апробирование данного метода на основе системы распределенной обработки информации.

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

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

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

3. Разработка подхода к построению алгебр Кодда в рамках логики OOVC..

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

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

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

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

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

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

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

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

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

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

3. Метод определения операций алгебры Кодда в рамках объектных теорий баз данных и его обоснование.

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

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

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

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

руководителем).

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

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

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

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

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

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

4. Международная конференция «Мальцевские чтения» (Новосибирск, 2011).

5. Всероссийская конференция «Искусственный интеллект и управление» (ИИУ-2011, Геленджик, 2011).

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

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

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

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

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

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

Первое направление связано с интерпретацией теорий в дескриптивных логиках как баз данных. В этом контексте можно упомянуть как работы, базирующиеся на представлении в дескриптивных логиках ER-моделей (например, Bergamaschi et al, 19941 и Calvanese et al, 19992), так и методы семантического описания данных, напрямую базирующиеся на дескриптив-

1 Bergamaschi S., Nebel В. Acquisition and validation of complex object database schemata supporting multiple inheritance. Applied Intelligence, 1994. 4(2). P. 185-203.

2Calvanese D.. Lenzerini M., Nardi D. Unifying class-based representation formalisms. Journal ot' Artificial Intelligence Research, 1009. Ch. 11. P. 109-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, обосновывается принципиальным отличием дескриптивных логик от реляционных моделей. Это отличие объясняется с тем, что семантика реляционных моделей базируется на парадигме замкнутого мира, поэтому в рамках открытого мира дескриптивных логик формализация реляционных моделей невозможна.

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

3Borgida A.. Etherington D. Hierarchical knowledge bases and efficient disjunctive reasoning. Proceedings of the first international conference on Principles of knowledge representation and reasoning. December 1989. P. 33-43.

4Bergamasclii S., Sartori C. On taxonomic reasoning in conceptual design, ACM Transactions on Database Systems (TODS), 1992. V.lTn.3, P. 385^22.

5Borgida 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-494

"Motik В., Sattler U., Studer R. Query answering for OWL-DL with rules. Journal of Web Semantics, 2005. 3(1). P. 41—60

7Rosati 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), так и практической. Мы считаем, что высокая сложность не оставляет шансов для широкого применения данного подхода на практике, поскольку требует от пользователя уровня компетентности, недоступного для основной массы разработчиков баз данных.

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

8 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 significant impact until they can be used by people that don't understand them»).

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

Рассмотрим дескриптивную логику ÖÖVC. Язык этой логики включает имена концептов Cj, имена ролей Дг-, имена доменов Di, имена объектов Oi, логические константы Т и 1 и квантор всеобщности VT.f, где Т -роль или атрибут, a F - либо атомарный концепт, либо имя типа данных из Т>. Кроме того, в ООТ>£ включаются

- инверсные роли при кванторах всеобщности: VT~.F, где Т - либо роль, либо атрибут, a F - либо атомарный концепт, либо имя типа данных;

- кардинальности > п.Т и < п.Т, где п е No, а Т - либо роль, либо атрибут, либо инверсия роли/атрибута.

- имена объектов о, о', о\, 02, ■ ■.

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

• Концепты вида

С, Т, _L, VT.F, VT-.F, > п.Т, < п.Т

где С - имя концепта, F - произвольный концепт, Т - свойство (роль или атрибут).

• Терминологические аксиомы вида Fi С F2, где F\,F% - концепты.

• Фактологические аксиомы (факты) С(о), R(o, о'), Р(о, v), где С, R, Р - имена концепта, роли и атрибута, соответственно, о, о' - имена объектов, и элемент типа данных.

9Hustadt U., Motik В., and Sattler U. Data complexity of reasoning in very expressive description logics. In Proc. of IJCAI 2005, pages 466-471, 2005.

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

и

Определим интерпретацию I конструкций ООТ>С. Выражения ООТ>С интерпретируются на множестве объектов Д, причем имена объектов Ог интерпретируются как элементы основного множества о{ € Д, концепты - как подмножества F/ С Д, роли и атрибуты - как подмножества декартовых произведений В1 С Д х Д и Р1 С Д х V, соответственно. Интерпретация I выражений ООТ>С на множестве объектов Д должна удовлетворять следующим правилам. Семантика концептов:

Концепт Пример Семантика

С W отап С1 с Д

MT.F \/hasChild.\V отап {х\{у\(х,у)еТ1}СР1}

WT'.F VhasChild~ .Man {х | {у 1 (у,х) е Т1} С

> п.Т > 1 .hasChild {х\ \\{у\(х,у)еТ'}\\>п}

< п.Т < 2JiasChild {х\ 11(2/1 (х,у)еТ<}\\ <п)

т T Т' = Д

_1_ VhasChild.-L ±1 = Ч>

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

Аксиома

F\ С F2 С{о) R(o, о') P(o,v)

Пример Семантика

Girl Ц Female F{ С F2J

Woman(Marie) о 6 С1

hasChild(Marie, John) {о1, о'1) еЯ'.й'сДхД Аде(Магге, 25) {о1, v') G Р1, Р1 С Д х V

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

С\ С С-2 (аксиома наследования)

3 Т С С (аксиома домена)

3 Т~ Ц С (аксиома ранга)

С С > п.Т (аксиома гшп-кардинальности)

С Ц < п.Т (аксиома тах-кардинальности)

Определение 2 Объектной теорией О логики ООТ>С в словаре УУ =

11Мальгх Л.Л., МатщшшдаЛ.В. Объектпо-орпгптиронаппан дпекринтишгаи логика // Ипиестин ИГУ. Серия математика. — N0.1. - 2011. С.57-72.

{С, TZ, V, О) назовем непротиворечивую теорию, ТВох которой состоит из конечного множества аксиом наследования, домена, ранга, max и тт-кардинальности, удовлетворяющую следующим условиям:

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

2. каждое свойство Т G (TZöV) обладает в О ровно одной аксиомой домена и ровно одной аксиомой ранга.

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

Dom = {Vu ... ,Vm}

Считаем, что каждая область данных содержит выделенный элемент NULL, причем

Vi n Vj = {NULL} для Vi, Vj £ Dom, г ф j

Обозначим

V = vx и... и vrn

Пусть ID) и А — счетные множества имен (идентификаторов) и D — конечное множество имен доменов. Множества ГО, А и D попарно не пересекаются.

Определение 3 k-местное табличное отношение есть тройка г = {Rr, bodyr, headerг), где

- Rr € ID - имя отношения;

- body,. С Vh х Vi% x ... x Vh, I bodyr \ < oo, V{j G Dom для 1 <j< k;

- headerr = ((Ль Dh),..., (Ak, Dh}}, где Aj E A, Di} G D и Д. есть ■амя домена для 1 < j < к, причем Aj ф Aj при г ф j.

Конечное множество bodyr называется телом табличного отношения, а кортеж headerT — заголовком г.

Сигнатурой (sign(г)) отношения г назовем множество

sign(r) = {Аь .. .,Ак},

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

Будем говорить, что табличные отношения г1 и г2 согласованы, если либо sign{г1) П sign{г2) = 0, либо типы данных атрибутов из sign^1) П sign(г2) в отношении г1 и в отношении г2 совпадают.

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

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

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

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

1. I \= О + CW.

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

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

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

дескриптивной логики STíOXAÍ(D), была доказана корректность данной операции.

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

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

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

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

Будем говорить, что атрибуты А и В некоторой базы данных DB согласованы, если они имеют один и тот же тип данных в ©В. Также, будем говорить, что атрибут А согласован с некоторым элементом v € D, где D G Ш>, если атрибут А имеет тип данных D в ID®.

Определение 5 Пусть КШ - база данных. Выражение A reí х назовем элементарным предикатом выборки, где A G sú/n(MB), х 6 (sign(BB) U Р), А согласован с х и reí е {=, ф, С, <, >, >}• Предикат выборки это либо элементарный предикат выборки, либо один из Pi Vp2> Pi Арг, zdepi,p2 - предикаты выборки.

Предикат выборки р определен на отношении г = (Rr, bodyr, headerr), если все атрибуты, входящие в р, принадлежат сигнатуре г. Предикат р истинен на кортеже t € bodyT (обозначаем Ш f= pit), где DB — база данных, содержащая отношение г), если р определен на г, и при подстановке вместо каждого атрибута А, входящего в р, значения t(A), получившееся булево выражение является истинным, где истинность элементарных предикатов определяется истинностью полученных равенств и неравенств в соответствующих доменах (предполагаем, что каждая область данных линейно упорядочена по типу натуральных, целых или рациональных чисел).

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

о>(г) = г',

где г' - отношение с новым именем Дг< € ГО, такое, что

bodyr, = {t | t 6 bodyt и {r} p(t)}, headerr< = headerT

В разделе 2.2 операции алгебры Кодда формализуются на языке объектных теорий. Пусть О Н- CW — объектная теория с аксиомами замкнутости базы данных DB и С\, Сг — концепты, соответсвующие в теории О табличным отношениям гь г2. Для каждой операции алгеры Кодда а мы ввели аналог этой операции на объектных теориях (обозначим через а*) и описали алгоритм преобразования объектной теории О + CW в объектную теории О' + CW' под действием операции а*, «примененной» к концепту Ci (концептам С\ и С2).

Рассмотрим операцию выборки с предикатом выборки р, примененную к отношению г е К®.

Лемма 1 Пусть O+CW — объектная теория с аксиомами замкнутости базы данных DB, С концепт, соответствующий в теории О табличному отношению г, а*Е — аналог операции выборки ар, тогда

1) ст*Е «применима» к концепту С тогда и только тогда, когда ар(г) определено,

2) Если а*Ер «применима» к концепту С, то теория О' + CW', полученная из теории О + CW под действием операции о*Ер «примененной» к концепту С, является теорией базы данных DB U {о-р(г)}

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

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

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

Во второй главе были выражены операции алгебры Кодда в логике ООТ>С и была доказана корректность такого выражения. Таким образом

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

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

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

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

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

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

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

Далее следует описание двух методов реализации механизмов работы с базами данных на Libretto: метода подмены хранилища и метода подмены интерпретатора (трансляции Libretto в SQL). Оба способа базируются на отображении базы данных ГО в соответствующую ей объектную теорию Он, поскольку прежде чем начать работу с базой данных, необходимо предоставить 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-запросов L$ф и предикатов 1?Sqi как наименьшие множества, удовлетворяющие следующим условиям:

1. если N - имя класса или свойства, то N £ Lи N является шагом.

2. если N - имя свойства, то инверсное свойство ~ Лг € Lи ~ N является шагом.

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

4- если S € L i является шагом и Re Р 8ф то 5[ñ] G L ^ и также является шагом.

5. если P,Se L8ф, причем S является шагом, то P/S € L

6. если РиР2 € L8ф то Ргге1Р2 6 Рsq¡, где reí Е { ==,!=,<,>,<=,>=}•

1. если R\,R2 S №3ф то

notRi, R\andR2, Ri or R2 e

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

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

start/stepl/step2/ .../stepN

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

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

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

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

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

Результаты и выводы

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

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

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

3. Моделирование реляционных структур на алгебраическом уровне через представление операций алгебры Кодда в терминах логики OOVC-,

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

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

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

1. Казаков И. А. Алгебры Кодда и дескриптивные логики // Изв. Иркут. гос. ун-та. Сер.: Математика. - 2011,- Т. 4, № 3. -С. 68-73

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

Работы, опубликованные в других научных изданиях:

1. Gavryushkina А.А., 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. - С. 47.

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

Научное издание

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

МЕТОДЫ ОБРАБОТКИ РЕЛЯЦИОННЫХ ДАННЫХ В ОБЪЕКТНЫХ ДЕСКРИПТИВНЫХ ЛОГИКАХ

Автореферат

Подписано в печать 26.04.2012. Формат 60x901/16 Усл. печ. л. 1,0. Тираж 100 экз. Заказ 31

Издательство ИГУ 664003, Иркутск, бульвар Гагарина, 36

Введение

1 Базы данных как онтологии

1.1 Обзор литературы и имеющийся .мировой опыт.

1.2 Дескриптивные логики и общие проблемы

1.2.1 Дескриптивные логики

1.2.2 Система вывода в БЬ

1.2.3 Проблемы использования логики.

1.2.4 Проблема объединения логической и реляционной .модели данных

1.2.5 Наш подход.

1.3 Дескриптивные логики и объектные теории.

1.3.1 Основные понятия дескриптивных логик.

1.3.2 Логика ООТ>С и объектные теории.

1.4 Базы данных.

1.5 Объектные теории баз данных.

1.6 Аксиомы замкнутости.

2 Формализация операций алгебры Кодда

2.1 Операции алгебры Кодда.

2.1.1 Операция выборки.

2.1.2 Операция проекции

2.1.3 Операция объединения.

2.1.4 Операция вычитания.

2.1.5 Операция декартова произведения.

2.2 Формализация операций алгебры Кодда в объектных теориях

2.2.1 Формализация операции выборки .5G

2.2.2 Формализация операции проекции.

2.2.3 Формализация операции объединения.

2.2.4 Формализация операции вычитания.

2.2.5 Формализация операции декартова произведения

3 Реализация Libretto на реляционных базах данных

3.1 Описание системв1 Libretto

3.2 Отображение структуры БД в Libretto

3.3 Метод подмены хранилища.

3.4 Трансляция Libretto в SQL.

3.4.1 Трансляция элементарных запросов.

3.4.2 Трансляция путей

3.4.3 Трансляция инверсных свойств.

3.4.4 Вложенные запросы.

3.4.5 Предикаты

3.4.6 Сравнение реализаций.

Актуальность проблемы

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

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

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

Цели исследования

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

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

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

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

3. Разработка подхода к построению алгебр Кодда в рамках логики OOVC.

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

Методы исследования

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

Научная новизна

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

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

Научная и практическая значимость работы

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

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

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

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

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

3. Метод определения операций алгебры Кодда в рамках объектных теорий баз данных и его обоснование.

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

Структура и объем диссертации

Основные результаты диссертации опубликованы в следующих работах:

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

1. Казаков И. А. Алгебры Кодда и дескриптивные логики / И. А. Казаков // Изв. Иркут. гос. ун-та. Сер.: Математика. - 2011-Т. 4. 3. -С. 68-7-3

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

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

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

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

6. Манцивода А.В. Казаков И.А. Система поддержки деятельности аспирантуры ИРУ на базе OntoBox // Труды XVI Всероссийской научно-методической конференции "Телематика'2009". - С-Иб.; 2009. - С. 47.

7. Малых А.А. Казаков И.А. Доступ к онтологиям через VYEB. Вазовый подход в системе Мета2 // Труды XV Всероссийской научно-методической конференции "Телематика''20087 - С-Пб. 2008. - С. 314.

В число указанных работ входят две статьи |1. 2] из «Перечня ведущих и рецензируемых журналов и изданий ВАК РФ». Работа [2] выполнены в нераздельном соавторстве с научным руководителем. Из совместной публикации [2] в диссертационную работу включены результаты, полученные автором самостоятельно и не затрагивающие интересы других соавторов.

Апробация результатов

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

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

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

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

4. Международная конференция «Мальцевские чтения».

Личный вклад автора

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

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

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

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

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

Благ одар мости

Хочется выразить благодарность моему научному руководителю проф. A.B. Манциводс за неоценимую помощь в написании диссертации, а также коллективу преподавателей, студентов и аспирантов кафедры информационных систем ИГУ за ценную помощь.

Заключение

В данной работе была построена модель реляционных баз данных в терминах объектных теорий [6] в рамках логической архитектуры OOVC С SH01J\f(D). Показано, что предлагаемый подход позволяет смоделировать не только структуру реляционных баз данных, но и парадигму замкнутого мира, действующую в этих базах. Так же средствами объектных теорий были смоделированы основные операции алгебры Код-да. такие как выборка, проекция, объединение, вычитание и декартово произведение.

В работе рассматривается подход к отображению реляционных баз данных в логическую среду объектных дескриптивных логик. На основе этого подхода, связанного с моделированием информации из баз данных с помощью объектных теорий Q^s и их расширений Oj^. определяется метод работы с базами данных в рамках декларативного подмножества языка Libretto. Также исследуются вопросы эффективности данного метода с точки зрения построения Libretto-запросов и их трансляции в язык SQL. Проводится анализ экспериментальной реализации данного метода в рамках языка Libretto 0.9.

Основным результатом работы является формализация реляционных баз данных в дескриптивной логике S7iOTj\f(IJ). Формализация подразумевает под, собой.

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

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

3. Моделирование реляционных структур на алгебраическом уровне через представление операций алгебры Кодда в терминах логики OOVC:

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

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

1. Гончаров. С.С. Свириденко. Д.И. Е-программирование // В кн.: Логико-математические проблемы МОЗ. - Вычислительные системы. Вып. 107. - Новосибирск. 1985. - С.3-29.

2. Казаков H.A. Алгебры Кодда и дескриптивные логики // Изв. Иркут. гос. ун-та. Сер.: Математика. 201L- Т. 4. № 3. -С. 68-73

3. Казаков H.A. Манцивода A.B. Вазы данных как онтологии // Изв. Иркут. гос. ун-та. Сер.: Математика. 2011- Т. 4. № 1. -С. 20-30

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

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

6. Малых A.A. Манцивода A.B. Объектно-ориентированная дескриптивная логика // Известия ИГУ. Серия математика. Хо.1. - 2011.

7. Малых. A.A. Манциво/1а A.B. Ульянов B.C. Логические архитектуры и объектно-ориентированный подход // Вестник НГУ. Серия: Математика. механика, информатика. 2009. - Т9. - .VQ3. - С. 64-85.

8. Малых A.A. B.C. Ульянов. Модульность в системе А/1ета2 с использованием JavaFX. // Труды Всероссийской конференции «Телемати-ка'2008». С.-Петербург, 2008

9. Малых A.A., Ульянов B.C. Организация пользовательского интерфейса информационных систем на основе онтологии // Вестник Бурятского университета. Серия 13: Математика и информатика. Улан-Удэ.: Изд-во Бурят, ун-та, - Вып. 3. 2007, С. 250-253.

10. Малых A.A., МанциводаА.В. Онтобокс: онтологии для объектов // Известия Иркутского государственного университета. Иркутск. - Серия «Математика». Том 3. 2009 с. 94-104.

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

12. Маигдивода A.B. Липовченко В.А. Применение логического программирования к обработке знаний // Вестник Бурятского университета. Серия 13. Математика и информатика. Улан-Удэ: Изд-во Бурят, унта, 2006. - Вып. 2. - С.50-57.

13. Мапцивода A.B., Стукушин П.О. Спецификации как онтологии // Журнал "Программные продукты и системы1'. М., 2009. - №4.-0.37-43.

14. Мапцивода A.B., Малых A.A. Представление и обработка знаний в Интернете: Информационные ( пстемы и логика. Иркутск: Издательство Иркутского ун-та, 2005. - Вып. 2. - 1Пс.

15. Машдивода A.B. Малых A.A. OnLoBox: ядро системы «Мета-2» // Труды Всероссийской научно-методической конференции «Телемати-ка;2009». С-Пб., 2008. - С.120-121.

16. Машдивода A.B. Романова O.A. Создание информационно-справочной системы по математическому анализу на основе оплайн-консультации. // Труды Всероссийской научно- мед одической конференции «Телема-тика;2009». С-Пб., 2008.

17. Мапцивода A.B. Ульянов B.C. Онтологические системы и задачи управления контентом // Труды Всероссийской конференции «Теле-матика'2005». С.-Петербург. 2005.

18. Манцивода A.B. Петухин В. А. Компилятор функционально-логического языка Флэнг // Вычислительные системы, вып. 146. 1992, с. 61-75.

19. Манцивода A.B. Флэнг язык искусственного интеллекта // Кибернетика, 1993, No. 5, с.350-367.

20. A.B. Манцивода. Е-программирование и проблемы дискретной оптимизации// Иркутск, 1994, 245с. ¡Электронный ресурс. URL: http://teacode.com/flang'/book/sigma-book.pdf-За гл. с экрана (дата обращения: 26.04.12).

21. Манцивода A.B. Казаков LI.А. Система поддержки деятельности аспирантуры ИВУ па базе OntoBox /,/ Труды XVI Всероссийской научно-методпчес кои конференции "Те.ломатпка;2009!\ С-Пб., 2009. - С. 47.

22. Манцивода A.B. Москвина A.C. Хранение метаданных в мультимедийных файлах // Труды Всероссийской научно-методической конференции «Телематика'2009». С-Г16.; 2009. - С.147.

23. Стукушин И.О. Малых A.A. Формализация стандартов через дескриптивные логики // Труды Всероссийской научно-методической конференции « Те л е м а т и к а; 2009 ». С-Пб., 2009. - С. 420-421.

24. Ульянов B.C. Создание системы управления ресурсами. Труды Всероссийского конкурса «Информационно-телекоммуникационные системы»., С-П6., 2005. -С. 95-96.

25. Ульянов B.C. Использование онтологий в задачах построения биологических информационных ресурсов // Материалы VII школы-семинара «Математическое моделирование и информационные технологии». -Иркутск: Изд-во ИДСТУ, 2005. С.31.

26. Братко. И. Программирование на языке Пролог для искусственного интеллекта. VI.: Мир. 1990. - 560с.

27. Ульянов B.C. Бесконечные ленивые маркированные деревья // Известии Иркутского государственного университета. Иркутск. - Серия «Математика». Том 3. 2009 с. 183-193.

28. Хоггер. К. Введение в логическое программирование. М.:Мир. 1988.- 348с.

29. Чень Ч. Ли Р. Математическая логика и автоматическое доказательство теорем. М.: Наука. 1983. - 360 с.

30. Чери С. Готлоб Г. Танка Л. Логическое программирование и базы данных. — AT: Мир., 1992. 352с.

31. Abiteboul S. Hull R.B. Vianu V. Poundations of Databases Addison-Wesley. 1995. - 68op.

32. Baader F. The Description Logic Handbook: Theory. Implementation. Applications / P. Baader. D. Calvanese . D.L. McGuinness. D. Xardi. P.P. Patel-Schneider. Cambridge. - 2003. - P.574.

33. Baader P. Sattler U. Xumber restrictions on complex roles in description logics ,// In Proceedings 0f KR-96. 1996. - P. 328-339.

34. Bergamaschi S.;nd Bernhard Nebel. Acquisition and validation of complex object database schemata supporting multiple inheritance. Applied Intelligence. 4(2): 185-203, 1994.

35. Bergamaschi S., Sartori C. On taxonomic reasoning in conceptual design, ACM Transactions on Database Systems (TODS), v.17 n.3, p.385-422, Sept. 1992.

36. Borgida A. Etherington D. Hierarchical knowledge bases and efficient disjunctive reasoning. Proceedings of the first international conference on Principles of knowledge representation and reasoning, p.33-43, December 1989.

37. Borgida A., Lenzerini M., Rosati R. Description Logics for Data Bases

38. Borgida A. On the relative expressiveness of description logics and predicate logics // Artificial Intelligence. 1996. - Vol. 82. - P.353-367.

39. Brachman R. A Structural Paradigm for Representing Knowledge // BBN Report No.3605. Cambridge, 1978.

40. Brachman R., Schmolze J. An Overview of the KL-ONE Knowledge Representation System // Cognitive Sci. 1985. - Vol.9.

41. Calvanese D. Lenzerini VI., Xardi D. Unifying class-based representation formalisms. ,J. of Artificial Intelligence Research, 11:199-240, 1999.

42. Damasio C.V. et al. Supporting Open and Closed World Reasoning on the Web / Carlos Viegas Damasio. Anastasia Analyti. Grigoris Antoniou and Gerd Wagner // Lecture Notes in Computer Science. 2006. Volume 4187.- 2006. P. 1-49-163.

43. DatalogDL: Datalog Rules Parameterized by Description Logics. / J. .Mei and others // Canadian Semantic Web. Springer Scries: Semantic Web and Beyond. Canada. 2006. - V.2. - P.171-188.

44. Donini F. Lenzcrini M. Nardi D. Schaerf A. AL-log: integrating Datalog and description logics //J. of Intelligent and Cooperative Information Systems. 1998. - V.10. - P.227-252.

45. Ershov. Yu.L. Goncharov. S.S. Sviridenko. D.I. Semantic Programming // Information piocessing. Pioc. IFIP 10th World Comput. Congress. Dublin.- v. 10. 1986. - P. 1093-1100.

46. Gavryushkina A.A. Kazakov LA. A formalization of the Codcl's relational algebra in logic SI40L\(D) Text. // International conference "MaLtsev meeting". Xovosibiisk, 2011. - P. 134-135.

47. Goncharov S.; Ershov Yu. Sviridenko D. Semantic programming // 10th Woild Congress Inclination Piocessing;86. Dublin. 1986. - P. 1093-1100.

48. Haarslev. V. On the scalability of description logic instance retrieval. /'/ Haarslev V., Moeller R. // Journal of Auromated Reasoning 41(2) -August 2008. P. 99-142.

49. Haarslev V. Moller R. Racer: An OWL Reasoning Agent for the Semantic Web // In Proc. Products and Services of Web-basecl Support Systems, in conjunction with the 2003 1EEE/WIC International Conference on Web Intelligence. Canada, 2003. - P.91-95.

50. Hibernate: Mapping an Object-Oriented Domain A4odel to a Relational Database Электронный pecypc|. URL: hups://'www.hibernate.org/ -Загл. с экрана (дата обращения: 2G.04.12).

51. Horrocks I. Using an expressive description logic: FaCT or fiction? //' Proceedings of the Sixth International Conference «Principles of Knowledge Representation and Reasoning». San Francisco:Morgan Kaufmann, L998. - P.636-647.

52. Horrocks I. Parsia В., Patel-Schneider P., Hencller ,J. Semantic web architecture: Stack or two towers? // Principles and Practice of Semantic Web Reasoning. Berlin:Springer, 2005. - Lecture Notes in Computer Science. - Vol. 3703. - P.37-41.

53. Horrocks I., Patel-Schneider P. Reducing OWL entailment to description logic satisfiability. .J. of Web Semantics, 1 (4):345-357, 2004.

54. Hustadt U., Mot.ik В. Sattler U. Data complexity of reasoning in very expressive description logics. In Proc. of IJCAI 2005, pages 466-47L 2005.

55. Hustadt. U. Reasoning in Description Logics by a Reduction to Disjunctive Datalog.// Iiystaclt Ullrich. Motik Boris. Sattler Ulrike // Journal of Automated Reasoning 39(3). 2007. - P. 351-384.

56. KAON2 | Электронный ресурс. URL: http://kaon2.semanticweb.org/ -Загл. с экрана (дата обращения: 26.04.2012).

57. Levy. A. Combining horn rules and description logics in CARIN / A. Levy. M. Rousset // Artificial Intelligence. 1998. - V.104. - P.163-209.

58. Libretto Электронный ресурс. URL: http://ontobox.org/ - Загл. с экрана (дата обращения: 26.04.12).

59. Malykh A. A-lantsivoda A. A Query Language for Logic Architectures // Proceedings of 7th International Conference "Perspectives of System Informatics". Springer-Verlag Berlin Heidelberg. Lecture Notes in Computer Science 5947. - 2010. - P.294-305.

60. Adantsivoda. A. Semantic Programming for Semantic Web /'/ Invited Talk. Proceedings of the 9th International Asian Logic Conference. .Novosibirsk. 2005. - P. 17-21.

61. Mantsivoda A. Petukhin V. Compiling Liang // Proceedings of 2nd Russian Conference on Logic Programming. St.Petersburg. 1991. No. 592 in1.cture Notes in Computer Science. Springer, pp. 286-293; Springer-Verlag, 1992.

62. Mantsivoda A. Petukhin V. Weimann A. Memory Management of Constraints' in Plang// Proc. of 10th Int. Conf on Logic Programming, (eel. by D.S.Warren), MIT Press, 1993, p.633-646.

63. Mantsivoda A. Logic and Large Combinatorial Problems (invited talk) // Workshop on Non-standard Logics and Logical Aspects of Computer Science, Kanazawa, Japan, December 5-8, 1994, p.24-33.

64. Mantsivoda A. Flang: A Functional-Logic Language // Lecture Notes in Computer Science. Berlin: Springer. 1992. - Vol. 567. - P.257-270.

65. Mantsivoda A., Lipovchenko V., Malvkh A. Logic Programming in Knowledge Domains // Lecture Notes in Computer Science. Berlin: Springer, 2006. - P.451-452.

66. Mantsivoda A., Lipovchenko V., Malvkh A. Logic Programming in Knowledge Domains (Full version) // Известия ИГУ. Серия .математика. T.l. Иркутск: '

67. Mazzocchi S. Closed World vs. Open World: the First Semantic Web Battle ¡Электронный ресурс. URL: http://www.betavc.rsion.org/ stefano/linotype/news/91/ - Загл. с; экрана (дата обращения: 26.0Т12).

68. Minsky М. A Framework for Representing Knowledge // The Psychology of Computer Vision. Xew York. 1975. P.211-277.

69. Motik B., Sattler U., Studer R. Query answering for OWL-DL with rules. •J. of Web Semantics., 3(l):41-60, 2005

70. Motik B. Horrocks I. Sattler U. Bridging the Gap Between OWL and Relational Databases. Journal of Web Semantics: Science, Services and Agents on the World Wide Web, 7(2):74—89, 2009.

71. Motik, B. Representing Structured Objects using Description Graphs // A4otik Boris, Grau Bernardo Cuenca. Horrocks Ian, Sattler Ulrike. // KR. 2008. - P. 296-306.

72. Motik B. Bridging the Gap Between OWL and Relational Databases // In proc.: The 16 th International Conference on World Wide Web. ACAd Press, 2007. P.807-816

73. Parchunov, D. GABEIv for Ontology Generation// Zeiger, Josef: Herclina, Philip: Oberprantacher. Andreas (Hrsg.): Lernen und Entwicklung in Organisationen, Wien: LIT-publishing Company, 2006, p. 87-107.

74. Palchunov, D. Lattices of relatively axiomatizable classes// S.O.Kuznetsov and S. Schmidt (Eds.), ICFCA 2007. Lecture Notes in Artificial Intelligerice \o. 4390, Springer-Verlag, Berlin Heidelberg, 2007, pp. 221-239

75. Pellet 9.;ioKTpowHbiii peeypcj. URL:liUp://www.mindswap.org/2003/pellet,/ Заг.л. с экрана (дата обращения: 26.04.12).

76. Pierce. Benjamin. Types and Programming Languages. MIT Press, p. 339 (2002).

77. Pin-shan Chen. P. The Entity-Relationship .Model: Toward a Unified View of Data // ACM Transactions on Database Systems. 1976. - V.l. - P. 9-36.

78. Proc. of the First International Conference «Rules and Rule Markup Languages for the Semantic Web». Berlin.- Springer-Verlag.- 2005.

79. Proc. of the Second International Conference «Rules and Rule Markup Languages for the Semantic Web». Berlin - Springer-Verlag.- 2006.

80. Puleston. C. Integrating Object-Oriented and Ontological Representations //' Puleston Colin. Parsia Bijan, Cunningham James. Rector Alan L. // A Case Study in Java and OWL. P. 130-145.

81. Riazanov A. Voronkov A. The Design and Implementation of Vampire // AI Communications. -2002. Vol.15. - P.91-110.

82. Rosati. R. The limits and possibilities of combining Description Logics and Datalog/ R. Rosati // Rules and Rule Markup Languages for the Semantic Web. Second International Conference. November 2006. - P.3-4

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

84. Rosati R. On the decidability and complexity of integrating ontologies and rules. .J. of Web Semantics. 3(l):61-73, 2005.

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

86. Schmidt-Schauss M. Smolka G. Attributive concept descriptions with complements // Artificial Intelligence. 1991. - V.48. - P.1-2G.

87. SWRL. A Semantic Web Rule Language Combining OWL and RuleML Электронный ресурс. URL: http://www.w3.oig/Submission/SWRL/- Загл. с экрана (дата обращения: 26.04.12).

88. The Rule Markup Initiative Электронный ресурс. URL: http://ruleml.org/ - Загл. с экрана (дата обращения: 26.04.2012).

89. Tsarkov D. Riazanov A. Bechhofer S. Horrocks I. Using Vampire to reason with OWL. // Proc. of ISWC 2004. Lecture Notes in Computer Science. -Berlin: Springei, 2004. Vol.3298. - P.471-485.

90. W3C: About the World Wide Web Consortium Электронный ресурс. -URL: http://www.w3.org/Consoitium/ Загл. с экрана (дата обращения: 26.04.12).

91. W3C Semantic Web Activity Электронный ресурс. URL: http://wwww3.org/2001/sw/ - Загл. с экрана (дата обращения: 26.04.12).

92. Web Ontology Language (OWL). Электронный pccvpc|. URL: www wS.oig/2004/0\'VL - Загл с экрана (дата обращения. 26.04.12).