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

кандидата физико-математических наук
Бездушный, Алексей Анатольевич
город
Москва
год
2008
специальность ВАК РФ
05.13.18
цена
450 рублей
Диссертация по информатике, вычислительной технике и управлению на тему «Математическая модель интеграции данных на основе дескриптивной логики»

Автореферат диссертации по теме "Математическая модель интеграции данных на основе дескриптивной логики"

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

Математическая модель интеграции данных на основе дескриптивной логики

Специальность 05.13.18 - математическое моделирование, численные методы и комплексы программ

АВТОРЕФЕРАТ диссертации на соискание ученой степени кандидата физико-математических наук

003455793

Москва-2008

/

003455793

Работа выполнена на кафедре математического моделирования сложных процессов и систем Московского физико-технического института (государственного университета)

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

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

Серебряков Владимир Алексеевич

Официальные оппоненты:

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

член-корреспондент РАН Флёров Юрий Арсениевич

доктор технических наук, профессор

Кузнецов Сергей Дмитриевич

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

Новосибирский государственный университет

Защита состоится « ЛУ » декабря 2008 года в (22 час. на заседании диссертационного совета Д 212.156.05 в Московском физико-техническом институте (государственном университете) по адресу: 141700, г. Долгопрудный Московской обл., Институтский пер., д. 9, ауд. 903 КПМ.

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

/I

Автореферат разослан « » ноября 2008 г.

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

Федько О.С.

Общая характеристика работы

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

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

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

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

Актуальным направлением исследований в этой области является применение к задаче интеграции данных аппарата дескриптивной логики, прежде всего в контексте Семантического Веб (Semantic Web).

Технологии Семантического Веб являются молодым и перспективным направлением развития современной информационной индустрии. Утвержденные World Wide Web Консорциумом (W3C) в 2004 году модель описания информационных ресурсов RDF (Resource Description Framework) и язык веб-онтологий OWL (Web Ontology Language) определили стандартный способ семантически богатого описания распределенной в сети Интернет информации. В этой связи представляется целесообразным

рассматривать их применение в контексте современных систем интеграции распределенных данных.

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

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

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

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

Цель работы

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

В работе исследованы и решены следующие задачи:

1. Проведено сопоставление выразительных возможностей и вычислительных характеристик различных диалектов дескриптивной логики.

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

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

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

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

5. Разработан прототип системы исполнения распределенных запросов в среде Единого Научного Информационного Пространства РАН (ЕНИП РАН).

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

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

В отличие от предшествующих работ по интеграции данных, полученный в данной работе результат имеет следующие особенности:

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

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

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

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

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

Практическая ценность

Непосредственное применение полученные в работе теоретические результаты нашли в проекте «Единое Научное Информационное Пространство РАН» (ЕНИП РАН). Работа расширяет полученные ранее результаты по ЕНИП новыми функциональными возможностями. Предложенные в диссертационной работе математическая модель системы интеграции данных на основе онтологий и практический алгоритм переформулировки запросов в такой системе представляют собой фундамент для виртуальной интеграции данных различных научных учреждений в рамках ЕНИП.

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

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

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

Апробация работы

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

Всероссийская научная конференция "Электронные библиотеки: перспективные методы и технологии, электронные коллекции" (Санкт-Петербург, 2003; Пущино, 2004).

Научно-практический семинар "Новые технологии в информационном обеспечении науки" (Таруса, 2003-2005).

Международная конференция The 8th World Multi-Conference on Sys-temics, Cybernetics and Informatics - SCI 2004 (Orlando, Florida, 2004). Международный коллоквиум Spring Young Researcher's Colloquium On Database and Information Systems - SYRCoDIS (Санкт-Петербург, 2004).

Всероссийская научная конференция "Научный сервис в сети Интернет" (Новороссийск, 2004).

Международная конференция "Порядковый анализ и смежные вопросы математического моделирования" (Владикавказ, 2006). Научная конференция МФТИ (Долгопрудный, 2005-2007). Научные семинары отдела Систем математического обеспечения Вычислительного Центра им. A.A. Дородницына РАН (Москва, 20032008).

Научные семинары кафедры математического моделирования сложных процессов и систем МФТИ (ГУ) (Москва, 2005-2008).

Публикации

По теме диссертации опубликовано 20 работ, в том числе две [1, 2] из списка изданий, рекомендованных ВАК РФ.

Структура и объем работы

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

Краткое содержание работы Введение

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

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

Глава 1. Обзор методов интеграции данных

В первой главе охарактеризовано текущее состояние отрасли, приведен обзор методов предоставления интегрированного доступа к данным, указаны области применимости, преимущества и недостатки различных подходов. В частности, рассматриваются архитектурные принципы распределенных СУБД, «хранилищ данных», федеративных БД, систем интеграции данных по принципу посредников, по принципу взаимодействия равноправных узлов (Р2Р). Рассматривается способ классификации такого рода систем. Поясняются принципы проектирования и разработки систем интеграции данных «сверху вниз» и «снизу вверх».

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

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

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

В завершение главы рассматриваются различные подходы к спецификации семантического отображения терминов. Дается сравнение подходов

Local-as-view (LAV), Global-as-view (GAV), описываются их преимущества и недостатки, рассматривается также гибридный подход (GLAV).

Глава 2. Технологии Семантического Веб и дескриптивная логика

Глава 2 дает обзор стандартов Семантического Веб (Semantic Web): унифицированной модели данных RDF (Resource Description Framework), языка веб-онтологий OWL (Web Ontology Language), языка запросов SPARQL, и рассматривает математическую основу языка веб-онтологий OWL - дескриптивную логику (Description logics). В этой главе вводятся необходимые для дальнейшего изложения определения.

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

В главе вводится формальная система определений, унифицирующая понятия различных диалектов дескриптивной логики, а также проводится систематизация и сравнение выразительных возможностей ряда диалектов дескриптивной логики. Специфицируется методика трансляции онтоло-гий, выраженных на языке OWL, в формальную систему. Онтологией в работе называется пара О — {Т, Л}, где:

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

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

концепты С, могут определяться на основе атомарных концептов А с помощью ряда конструкторов. В дескриптивной логике SHOJ.VP), соответствующей языку OWL-DL, концепты определяются следующей нотацией: С Т 111 A hC I С, П С21 С, u С21 VR0.C I 3R0.C | >n Rs | <n Rs I (a,,..., an} I >n Rd I <n Rd | VRd..Rdn.D | 3Rdl..Rdn.D Также в современных диалектах дескриптивной логики выделяют аксиомы вложения ролей Rj с R2 и аксиомы транзитивности ролей Trans(R).

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

жество объектов, и каждой роли - декартово произведение таких множеств. Интерпретация I называется моделью онтологии О = {% .Д} (Те М(0)), если она удовлетворяет всем высказываниям в Ти А. Высказывание логически следует из онтологии, если оно истинно для всех моделей онтологии. Онтология, не имеющая моделей, называется противоречивой.

В завершение главы вводится нотация для запросов на выборку данных и определяется семантика ответа на запросы относительно онтологии дескриптивной логики. Введенная формальная нотация для языка запросов ставится в соответствие синтаксической нотации языка 5РАЯС?Ь.

В частности, рассматривается класс конъюнктивных запросов с простыми ограничениями СО,$-С над некоторым диалектом дескриптивной логики £, задаваемых в форме:

600 — Ai-l.-nP.CZi) А Лн)т С.©, где £>(Х) - заголовок запроса, а справа указано определение запроса, некоторая конъюнктивная формула (Х,Х) от переменных из векторов X и У. Переменные из вектора X, указанного в заголовке запроса, называются свободными переменными запроса. Первая конъюнкция в определении запроса содержит атомы концептов С(а) или ролей К (а, Ь), а вторая -ограничения ор^и) или (иор2 V), где ор], ор2 - встроенные предикаты (например, операторы сравнения), а, Ь - переменные или константы, и - переменная, у - константа.

Множеством ответов на запрос Q относительно интерпретации 1 называется множество векторов констант таких, что при подстановке их вместо свободных переменных в определении запроса £>, формула ЗУ (ЬЮ является истинной в I:

<2(1) « {11ЗУ е^аю, х = (сь...,сп), с, 6 С} Множеством ответов на запрос <2 относительно онтологии О называется множество векторов констант которые являются ответами на запрос Q относительно любой ее модели:

0(0) ^ Ц\2\= Ж) VIе М(О), I = (с„..,,сп), с,е С} Здесь и далее 1И Q(t) по определению означает { е 2(2).

Глава 3. Математическая модель системы интеграции данных на основе онтологий

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

Система интеграции данных на основе онтологий для т источников данных Ль-Дщ формально определяется как = (0Г, {СД1)1=| п„ У7}, где: - 0Г= [ТГ, Аг] - глобальная онтология, непротиворечивая и выраженная на языке дескриптивной логики £г, без ограничения общности

= 0. Глобальная онтология проектируется «сверху» исходя из аспектов предметной области, которые должна представлять система интеграции данных, и содержит термины, в которых пользователь может формулировать запросы к системе.

- {Сд,},=|..т - конечное множество онтологии источников Ой= {ТА„ *4Д,}, непротиворечивых и выраженных на языке дескриптивной логики Физически информация, моделируемая множеством фактов Лд„ некоторым образом хранится в источнике данных Д„ и доступна через интерфейс запросов соответствующего адаптера.

- Т- конечное множество отображений между глобальной онтологией Сг и множеством онтологий источников {0Д1}|=1 т. Рассматриваются отображения, задаваемые формулами Яд-" qг, где

Яд и яг - некоторые запросы с одинаковым числом свободных переменных в терминах {0Д1},=| ,т и 0Г соответственно, а знак обозначает одно из отношений {с, э, =} (семантика таких отображений вводится ниже понятием глобальной модели). Ключевым классом отображений, для которого в работе предлагается эффективный алгоритм ответа на запросы, являются так называемые корректные конъюнктивные ОЬАУ-отображения с простыми ограничениями: цд с где Яд, Яг е С<25-£.

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

Семантика ответа на запросы относительно системы интеграции данных на основе онтологий Ч* определяется следующим образом. Рассматриваются возможные модели Тг глобальной онтологии Ог, корректные относительно всех отображений в Ч', то есть такие, что для каждого отображения яд- Яг в Ч* верно Яд(Од) - Яг (?г)> где Од = {и,=1.пД"д„ 11=1. т Лд,} - объединение онтологий источников, — обозначает одно из отношений {с, 2, =} между указанными множествами ответов на запрос. Такие Тг называются глобальными моделями системы интеграции Ч*, множество всех глобальных моделей Ч' обозначается .Ч(Ч').

Множеством точных ответов на запрос <2 относительно системы интеграции данных Ч* называется множество векторов констант которые являются ответами на запрос Q относительно любой глобальной модели: 6(40« 0(1)4(4*)} Это определение означает, что такие ответы логически следуют из фактов и высказываний онтологий источников, отображений, а также высказываний глобальной онтологии.

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

гий и предлагается способ сведения этой задачи к известной задаче ответа на запросы относительно отдельной онтологии. Для этого предлагается алгоритм вычисления множества извлеченных фактов _4ret({C)Al}i=l m, J7), содержащего все высказывания, получаемые из источников данных на основе отображений Т, и вводится понятие извлеченной онтологии'. окк{Ч>)=[ТГ, Лг.({Од, },=,.,„ Л)

Доказана следующая теорема. Пусть задана система интеграции данных Ч* = (Ог, {Од,}ы..П1, JF}, где отображения онтологий JFзаданы в форме Яд С qr, где qr е CQS-Cr. В таком случае множество глобальных моделей системы интеграции данных Ч1 совпадает с множеством моделей извлеченной онтологии:

М (Ч>) = М (С\П(Ч<))

Таким образом, для вычисления множества точных ответов на запрос Q относительно системы интеграции данных достаточно вычислить ответ на этот запрос относительно извлеченной онтологии: Q (XV) = Q (Огс, (Ч')).

Глава 4. Интеграция больших объемов данных на основе онтологий

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

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

2) На втором этапе соответственно полученный запрос исполняется системой-посредником.

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

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

Запрос Q' называется точной переформулировкой запроса Q на основе системы интеграции данных Ч*, если:

1) Все концепты или роли, используемые в запросе являются терминами онтологий источников {СЗд,}1=1.т системы интеграции Ч';

2) Множество ответов на запрос Q' относительно объединения всех онтологий источников Од = {и,=1..т'?д,. 11=1. тА,} совпадает с множеством точных ответов на запрос 0 относительно системы интеграции данных <2'(0д) = £> (¥).

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

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

Доказаны леммы, определяющие необходимые условия существования точной переформулировки на заданном языке запросов. Пусть в системе интеграции данных возможна точная переформулировка запроса на языке (3£г над дескриптивной логикой £г в запрос на языке <2£к над дескриптивной логикой £д, где £г и £д - диалекты глобальной онтологии и онтологий источников, соответственно. В таком случае, сложность ответа на ОСц запросы для онтологий на дескриптивной логике £д относительно объема множества фактов онтологии Щ не ниже сложности ответа на запросы на языке 0£г для системы интеграции данных Ч* относительно суммарного объема фактов всех источников в системе Щ^.тА,!. которая в свою очередь не ниже сложности ответа на запросы на языке С!£г для онтологий на дескриптивной логике £г относительно объема множества фактов онтологии |Л|.

Как следствие, сформулирована теорема, задающая необходимое условие существования точной переформулировки конъюнктивного запроса в виде формулы реляционного исчисления. Показано, что для того, чтобы всегда существовала точная переформулировка С(2-£г запроса относительно Ч* в виде формулы реляционного исчисления, необходимо, чтобы сложность ответа на С(2-£г запросы для онтологий на языке дескриптивной логики £г относительно объема фактов онтологии |.Д| лежала в классе СООЭРЛСЕ.

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

Рассматривается вопрос поиска максимально выразительного диалекта дескриптивной логики, допускающего точную переформулировку конъюнктивных запросов в реляционное исчисление. Вводится диалект Т>Саю, обладающий указанным свойством (аббревиатура trio - от tractable intégration of ontologies, т.е. диалект, допускающий интеграцию онтологий с полиномиальным временем ответа).

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

- CL Е С - ограниченная аксиома вложения концептов, где:

CL А | 3R01 3Rd | CL1 п CL2

С Т 111 А | -.А | С, п С21 3R01 3Rd | 3R0.C | 3Rdl..Rdn.D | -3R01 -3Rd

- R0i E Ro2> Rdi E Rd2 - аксиомы вложения ролей;

- R0i E "'Ког, Rdi E -iR^- аксиомы различия ролей;

- p(Rd) E d - аксиома типа значений атрибута.

Показано, что диалект Р£„;0 - максимальный в том смысле, что расширение этого диалекта рядом других конструкторов или видов аксиом приводит к невозможности точной переформулировки конъюнктивных запросов в реляционное исчисление.

Приводится спецификация соответствия диалекта VjCuio конструкциям языка веб-онтологий OWL. Рассматривается метод вычисления множества ответов на запрос относительно онтологии для дескриптивной логики 'РС1по, используемый в дальнейшем для доказательства корректности основного предлагаемого в работе алгоритма построения переформулировки запроса.

Сформулирована и доказана также используемая в дальнейшем теорема о существовании точной переформулировки. Пусть система интеграции данных ¥ = {Ог, {OJ_, m, F] такова, что 0Г и 0Д, выражены на некотором диалекте дескриптивной логики С, все отображения онтологий 1F заданы в форме qA С qr, где qr е СО,%-С. Пусть пользовательский запрос Q к системе задается в форме объединения конъюнктивных запросов Q e UCQs-£. Пусть g' есть объединение максимальных переформулировок запроса Q в форме конъюнктивных запросов с простыми ограничениями CQs-C. Тогда Q' является максимальной переформулировкой запроса Q на языке l(C.Qs-£, и Q' является точной переформулировкой запроса Q относительно системы интеграции данных

Глава 5. Алгоритм переформулировки запросов для систем интеграции данных на основе онтологий

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

Доказана следующая теорема. Пусть система интеграции данных Ч* = {Од,},=!..„„ Л такова, что:

- Глобальная онтология Ог непротиворечива и выражена на языке дескриптивной логики £г = Г>£,по;

- Онтологии источников данных 0Д| непротиворечивы и выражены на языке дескриптивной логики £д = P£tr¡0;

- Отображения f заданы в форме qA С qr, где qü, qr е CQ^-V£tno - конъюнктивные запросы с простыми ограничениями над дескриптивной логикой Т>£то.

Пусть пользовательский запрос Q к системе Ч1 задается в форме объединения конъюнктивных запросов Q£r = Z/CQs-P£tno- Тогда существует точная переформулировка запроса Q на основе системы интеграции данных Ч' на языке запросов Q£r = UCQS, то есть, представимая в виде объединения реляционных конъюнктивных запросов в терминах источников.

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

Предварительными условиями для предлагаемого алгоритма переформулировки запросов являются:

1) Нормализация Т>Сто терминологий Тг и {7^,}1=1.т применением к аксиомам ряда правил нормализации.

2) Проверка непротиворечивости системы интеграции данных Ч;, то есть существования глобальных моделей Ч*, что эквивалентно непротиворечивости извлеченной онтологии (9ret (Ч/). В случае, если данные в источниках в какой-то степени противоречат аксиомам глобальной онтологии, ответ на запрос относительно системы интеграции данных является по определению бессмысленным.

Предлагаемый алгоритм переформулировки запросов включает следующие основные этапы:

1) Переформулировка относительно аксиом глобальной онтологии;

2) Переформулировка относительно отображений онтологий;

3) Переформулировка относительно аксиом онтологий источников;

4) Минимизация полученного запроса.

На первом этапе алгоритма производится построение промежуточной переформулировки пользовательского запроса Q е UCQ$-'D£tno с учетом аксиом глобальной онтологии Тг. Основная идея этапа заключается в том, чтобы «закодировать» в запрос необходимые аксиомы терминологии Тг.

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

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

На третьем этапе алгоритма производится сведение полученного после предыдущих этапов ЫСО.%-Т>С 1Ш запроса, сформулированного в терминах онтологий источников, в реляционный запрос из класса ЫСО^ (подкласс реляционного исчисления). Для этого требуется «закодировать» в запрос аксиомы онтологий источников данных, что делается полностью аналогично первому этапу, относительно объединения всех аксиом источников и^-.т^Д]-

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

В результате выполнения всех этапов алгоритма вычисляется точная переформулировка исходного ИСО,&-Т>С1по запроса относительно системы интеграции ¥ в виде объединения реляционных конъюнктивных запросов с ограничениями (¿/ССЬ), в которых упоминаются только атомарные концепты и роли онтологий источников данных. Для исполнения полученного запроса могут быть применены известные методы, используемые для реляционной модели данных.

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

Глава 6. Анализ и применение полученных результатов

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

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

В предлагаемой архитектуре всякий адаптер к информационному источнику сопровождается онтологией на языке OWL (на диалекте £>£„,0), содержащей семантическое описание источника. Адаптер реализует внешний интерфейс ответа на SPARQL запросы, и обеспечивает трансляцию таких запросов во внутренний язык запросов источника данных, например SQL.

Глобальная онтология системы интеграции данных также формулируется на языке веб-онтологий OWL, в рамках диалекта VCxrm.

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

- В онтологиях источников с помощью конструкций языка OWL (позволяют выразить терминологические отображения);

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

- С помощью отображений в виде пары SPARQL запросов С qr, где запрос в терминах источников qA в общем случае может быть произвольным запросом, который может быть исполнен адаптерами, а форма запроса в терминах глобальной онтологии qr ограничена сводимостью к классу CQs-

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

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

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

В завершение рассмотрено практическое применение полученных результатов в контексте Единого Научного Информационного Пространства РАН. Приводится описание прототипа системы исполнения распределенных запросов в среде Единого Научного Информационного Пространства РАН (ЕНИП РАН). Рассматривается также спектр других актуальных за-

дач, для решения которых могут быть применены полученные результаты.

Заключение

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

Основные результаты работы

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

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

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

4. Предложена методология разработки систем интеграции данных на основе онтологий, в соответствии с формальной моделью.

5. На основе полученных теоретических результатов разработан прототип системы и комплекс программ исполнения распределенных запросов в среде Единого Научного Информационного Пространства РАН (ЕНИП РАН), предназначенной для виртуальной интеграции данных различных научных учреждений в ЕНИП РАН.

Список публикаций по теме диссертации

1. Бездушный A.A. Математическая модель системы интеграции данных на основе онтологий // Журнал «Вестник НГУ», серия «Информационные технологии» - Новосибирск, 2008. - T.6, вып.2. - С 15-40.

2. Бездушный А.Н., Кулагин М.В., Серебряков В.А., Бездушный A.A., Не-стеренко А.К., Сысоев Т.М. Предложения по наборам метаданных для научных информационных ресурсов // Журнал «Вычислительные Технологии» - Новосибирск, 2005 - Т. 10, вып.7. - С. 29-48.

3. Бездушный A.A., Бездушный А.Н., Серебряков В.А., Филиппов В.И. Интеграция метаданных Единого Научного Информационного Пространства РАН. - М.: Вычислительный Центр им. A.A. Дородницына РАН, 2006.-238 с.

4. Бездушный A.A. Распределенное исполнение SPARQL-запросов в гетерогенной среде // Моделирование и обработка информации: Сборник научных трудов / Моск. физ.-тех. ин-т. - М., 2008. - С. 230-235.

5. Bezdushny A.A., Bezdushny A.N., Nesterenko А.К., Serebriakov V.A., Sysoev Т.М. Integrated System of Information Resources of the Russian Academy of Sciences // Proceedings of the 8th World Multi-Conference on Systemics, Cybernetics and Informatics SCI 2004, Orlando, Florida -2004. - P. 462-467.

6. Бездушный A.A., Бездушный A.H., Нестеренко А.К., Серебряков В.А., Сысоев Т.М. Архитектура RDFS-системы. Практика использования открытых стандартов и технологий Semantic Web в системе ИСИР // Электронные библиотеки: перспективные методы и технологии, электронные коллекции: Труды V всероссийской научной конференции / Изд-во СПбГУ. - СПб., 2003. - С. 45-60.

7. Бездушный A.A., Бездушный А.Н., Нестеренко А.К., Серебряков В.А., Сысоев Т.М. Java и XML технологии новой версии ИСИР // Современные технологии в информационном обеспечении науки (ред. Н. Е. Калёнов) - М., 2003. - С. 182-205.

8. Бездушный A.A., Бездушный А.Н., Жижченко А.Б., Кулагин М.В., Серебряков В.A. RDF схема метаданных ИСИР // Современные технологии в информационном обеспечении науки (ред. Н. Е. Калёнов) - М., 2003.-С. 141-159.

9. Bezdushny A.A., Nesterenko A.K. ISIR Architecture for Web-Repository Integration II Сборник докладов Первого весеннего коллоквиума молодых исследователей в области баз данных и информационных систем (SYRCoDIS'2004) - СПб., 2004. - С. 60-66.

10. Бездушный A.A., Бездушный А.Н., Нестеренко А.К., Серебряков В.А., Сысоев Т.М. Возможности технологий ИСИР в поддержке Единого Научного Информационного Пространства РАН // Электронные библиотеки: перспективные методы и технологии, электронные коллекции: Труды VI всероссийской научной конференции - М., 2004. - С. 254-262.

11. Бездушный A.A., Бездушный А.Н., Жижченко А.Б., Калёнов Н.Е., Кулагин М.В., Серебряков В.А. Предложения по наборам метаданных для научных информационных ресурсов ЕНИП РАН // Электронные биб-

- 19-

лиотеки: перспективные методы и технологии, электронные коллекции: Труды VI всероссийской научной конференции - М., 2004. - С. 277-284.

12. Бездушный A.A., Нестеренко А.К, Сысоев Т.М. , Бездушный А.Н., Серебряков В.А. Архитектурные решения ИСИР на платформах Java и XML // Интегрированная система информационных ресурсов: архитектура, реализация, приложения: Сборник трудов / Вычислительный Центр им. A.A. Дородницына РАН. - М., 2004. - С. 78-95.

13. Бездушный A.A. Роль технологий Semantic Web в решениях ИСИР // Интегрированная система информационных ресурсов: архитектура, реализация, приложения: Сборник трудов / Вычислительный Центр им. A.A. Дородницына РАН. - М., 2004. - С. 36-55.

14. Бездушный A.A., Нестеренко А.К., Сысоев Т.М., Кулагин М.В. Semantic Web и OWL-онтологии в разработке ИСИР-систем // Научный сервис в сети Интернет: Труды Всероссийской научной конференции. / Изд-во МГУ. -М., 2004. -С. 188-191.

15. Бездушный A.A., Бездушный А.Н., Серебряков В.А. Схемы метаданных ЕНИП: практика применения OWL в ЕНИП // Информационное обеспечение науки: новые технологии (ред. Н. Е. Калёнов) - М., 2005. -С.155-182.

16. Бездушный A.A. Применение технологий Semantic Web для обеспечения интероперабельного обмена научной информацией // Современные проблемы фундаментальных и прикладных наук: Труды 48-й научной конференции МФТИ. Часть VII. / Моск. физ.-тех. ин-т. - М.,

2005.-С. 209-211.

17. Бездушный A.A. Схемы метаданных для научных информационных ресурсов ЕНИП РАН // Порядковый анализ и смежные вопросы математического моделирования: Труды IV международной научной конференции. / Институт прикладной математики и информатики. -Владикавказ, 2006. - С. 260 - 271.

18. Бездушный A.A. Архитектура интеграции данных ИСИР // Современные проблемы фундаментальных и прикладных наук. Часть VII: Труды 49-й научной конференции МФТИ. / Моск. физ.-тех. ин-т. - М.,

2006.-С. 230-231.

19. Бездушный A.A., Бездушный А.Н., Нестеренко А.К., Серебряков В.А., Сысоев Т.М., Теймуразов К.Б., Филиппов В.И. Информационная Web-система «Научный институт» на платформе ЕНИП. - М.: Вычислительный Центр им. A.A. Дородницына РАН, 2007. - 248 с.

20. Бездушный A.A. RQuery - язык запросов к источникам данных Semantic Web // Современные проблемы фундаментальных и прикладных наук. Часть VII: Труды 50-й научной конференции МФТИ. / Моск. физ.-тех. ин-т. - М., 2007. - Т.2 - С. 57-59.

В работах с соавторами личный вклад автора заключается в создании методов разработки распределенных систем и интеграции данных на основе OWL-онтологий и дескриптивной логики, в соответствии с формальной моделью. Автором предложен основанный на применении OWL-онтологий подход к интеграции данных в Интегрированной Системе Информационных Ресурсов (ИСИР), Едином Научном Информационном Пространстве РАН (ЕНИП РАН), создан соответствующий комплекс программных модулей.

Для заметок

Заказ № 143/11/08 Подписано в печать 11.11.2008 Тираж 80 экз. Усл. п.л. 1,25

„ ООО "Цифровичок", тел. (495) 797-75-76; (495) 778-22-20 www.cfr.ru; е-тай:т/о(ар/г.ги

Оглавление автор диссертации — кандидата физико-математических наук Бездушный, Алексей Анатольевич

Введение.

Глава 1. Обзор методов интеграции данных.

1.1. Проблематика интеграции данных.

1.2. Классификация подходов к интеграции данных.

1.3. Архитектура систем интеграции данных по принципу посредников.

Глава 2. Технологии Семантического Веб и дескриптивная логика.

2.1. Технологии Семантического Веб.

2.2. Математический аппарат дескриптивной логики.

2.3. Трансляция языка веб-онтологий OWL в дескриптивную логику.

2.4. Сопоставление диалектов дескриптивной логики.

2.5. Языки запросов и ответ на запросы относительно онтологии.

Глава 3. Математическая модель системы интеграции данных на основе онтологий.

3.1. Система определений и формализация задачи.

3.2. Семантика ответа на запросы в системе интеграции данных на основе онтологий

Глава 4. Интеграция больших объемов данных на основе онтологий.

4.1. Переформулировка запросов относительно системы интеграции данных.

4.2. Анализ существования точной переформулировки.

4.3. Дескриптивная логика DLtrio.

4.4. Трансляция языка веб-онтологий OWL в дескриптивную логику DLtr10.

4.5. Нормализация онтологий DLtr,0.

4.6. Вычисление ответов на запросы относительно онтологий DLtno.

Глава 5. Алгоритм переформулировки запросов для систем интеграции данных на основе онтологий.

5.1. Рассматриваемый класс задач.

5.2. Алгоритм построения переформулировки.

5.2.1. Этап 1. Переформулировка запроса относительно аксиом глобальной онтологии.

5.2.2. Этап 2. Переформулировка запроса относительно отображений.

5.2.3. Этап 3. Переформулировка запроса относительно аксиом онтологий источников.

5.2.4. Этап 4. Минимизация запроса.-.

5.3. Корректность и анализ алгоритма.

Глава 6. Анализ и применение полученных результатов.

6.1. Анализ выразительных возможностей рассматриваемого класса систем интеграции данных.

6.2. Сравнение со смежными работами.

6.3. Направления дальнейших исследований.

6.4. Методология построения систем интеграции данных на основе полученных результатов.

6.5. Применение полученных результатов.

Введение 2008 год, диссертация по информатике, вычислительной технике и управлению, Бездушный, Алексей Анатольевич

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

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

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

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

Актуальным направлением исследований в этой области является применение к задаче интеграции данных аппарата дескриптивной логики, прежде всего в контексте Семантического Веб (Semantic Web).

Технологии Семантического Веб являются молодым и перспективным направлением развития современной информационной индустрии. Утвержденные World Wide Web Консорциумом (W3C) в 2004 году модель описания информационных ресурсов RDF (Resource Description Framework) и язык веб-онтологий OWL (Web Ontology Language) определили стандартный способ семантически богатого описания распределенной в сети Интернет информации. В этой связи представляется целесообразным рассматривать их применение в контексте современных систем интеграции распределенных данных.

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

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

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

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

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

В работе исследованы и решены следующие задачи:

1) Проведено сопоставление выразительных возможностей и вычислительных характеристик различных диалектов дескриптивной логики.

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

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

4) Предложен и обоснован алгоритм построения точной переформулировки запроса для выбранного класса систем интеграции данных на основе онтологии.

5) Разработан прототип системы исполнения распределенных запросов в среде Единого Научного Информационного Пространства РАН (ЕНИП РАН).

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

В отличие от предшествующих работ по интеграции данных, полученный в данной работе результат имеет следующие особенности:

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

2) В работе предложена оригинальная математическая модель системы интеграции данных, основанная на аппарате дескриптивной логики.

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

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

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

Практическая ценность работы заключается в том, что предложенные математическая модель, методы и алгоритмы могут служить основой для практической реализации систем интеграции данных на основе стандартов «Семантического Веб» (RDF. OWL, SPARQL).

Непосредственное применение полученные в работе теоретические результаты нашли в проекте «Единое Научное Информационное Пространство РАН» (ЕНИП РАН). Работа расширяет полученные ранее результаты по ЕНИП новыми функциональными возможностями. Предложенные в диссертационной работе математическая модель системы интеграции данных на основе онтологии и практический алгоритм переформулировки запросов в такой системе представляют собой фундамент для виртуальной интеграции данных различных научных учреждений в рамках ЕНИП.

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

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

Основные научные и практические результаты, выносимые на защиту

В диссертационной работе представлены следующие результаты, выносимые на защиту:

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

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

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

4. Предложена методология разработки систем интеграции данных на основе онтологии, в соответствии с формальной моделью.

5. На основе полученных теоретических результатов разработан прототип системы и комплекс программ исполнения распределенных запросов в среде Единого Научного Информационного Пространства РАН (ЕНИП РАН), предназначенной для виртуальной интеграции данных различных научных учреждений в ЕНИП РАН.

Публикации

По теме диссертации опубликовано 20 работ, в том числе две [1,2] из списка изданий, рекомендованных ВАК РФ:

1. Бездушный A.A. Математическая модель системы интеграции данных на основе онто-логий // Журнал «Вестник НГУ», серия «Информационные технологии» — Новосибирск, 2008. - Т.6, вып.2. - С 15-40.

2. Бездушный А.Н., Кулагин М.В., Серебряков В.А., Бездушный A.A., Нестеренко А.К., Сысоев Т.М. Предложения по наборам метаданных для научных информационных ресурсов // Журнал «Вычислительные Технологии» - Новосибирск, 2005 - Т. 10, вып.7. — С. 29-48.

3. Бездушный A.A. Бездушный А.Н., Серебряков В.А., Филиппов В.И. Интеграция метаданных Единого Научного Информационного Пространства РАН. — М.: Вычислительный Центр им. A.A. Дородницына РАН, 2006. - 238 с.

4. Бездушный A.A. Распределенное исполнение SPARQL-запросов в гетерогенной среде // Моделирование и обработка информации: Сборник научных трудов / Моск. физ.-тех. ин-т. - М., 2008. - С. 230-235.

5. Bezdushny A.A., Bezdushny A.N., Nesterenko A.K., Serebriakov V.A., Sysoev Т.М. Integrated System of Information Resources of the Russian Academy of Sciences // Proceedings of the 8th World Multi-Conference on Systemics, Cybernetics and Informatics SCI 2004, Orlando, Florida - 2004. - P. 462-467.

6. Бездушный A.A., Бездушный A.H., Нестеренко А.К., Серебряков В.А., Сысоев Т.М. Архитектура RDFS-системы. Практика использования открытых стандартов и технологий Semantic Web в системе ИСИР // Электронные библиотеки: перспективные методы и технологии, электронные коллекции: Труды V всероссийской научной конференции / Изд-во СПбГУ. - СПб., 2003. - С. 45-60.

7. Бездушный A.A., Бездушный А.Н., Нестеренко А.К., Серебряков В.А., Сысоев Т.М. Java и XML технологии новой версии ИСИР // Современные технологии в информационном обеспечении науки (ред. Н. Е. Калёнов) — М., 2003. - С. 182-205.

8. Бездушный A.A., Бездушный А.Н., Жижченко А.Б., Кулагин М.В., Серебряков В.А. RDF схема метаданных ИСИР // Современные технологии в информационном обеспечении науки (ред. Н. Е. Калёнов) —М., 2003. - С. 141-159.

9. Bezdushny A.A., Nesterenko A.K. ISIR Architecture for Web-Repository Integration // Сборник докладов Первого весеннего коллоквиума молодых исследователей в области баз данных и информационных систем (SYRCoDIS'2004) - СПб., 2004. - С. 60-66.

10.Бездушный А.А., Бездушный А.Н., Нестеренко А.К., Серебряков В.А., Сысоев Т.М. Возможности технологий ИСИР в поддержке Единого Научного Информационного Пространства РАН // Электронные библиотеки: перспективные методы и технологии, электронные коллекции: Труды VI всероссийской научной конференции — М., 2004. — С. 254-262.

11. Бездушный А.А., Бездушный А.Н., Жижченко А.Б., Калёное Н.Е., Кулагин М.В., Серебряков В.А, Предложения по наборам метаданных для научных информационных ресурсов ЕНИП РАН // Электронные библиотеки: перспективные методы и технологии, электронные коллекции: Труды VI всероссийской научной конференции - М., 2004. - С. 277-284.

12.Бездушный А.А., Нестеренко А.К, Сысоев Т.М. , Бездушный А.Н., Серебряков В.А. Архитектурные решения ИСИР на платформах Java и XML // Интегрированная система информационных ресурсов: архитектура, реализация, приложения: Сборник трудов / Вычислительный Центр им. А.А. Дородницына РАН. - М., 2004. - С. 78-95.

13.Бездушный А.А. Роль технологий Semantic Web в решениях ИСИР //Интегрированная система информационных ресурсов: архитектура, реализация, приложения: Сборник трудов / Вычислительный Центр им. А.А. Дородницына РАН. - М., 2004. - С. 36-55.

14.Бездушный А.А., Нестеренко А.К., Сысоев Т.М., Кулагин М.В. Semantic Web и OWL-онтологии в разработке ИСИР-систем // Научный сервис в сети Интернет: Труды Всероссийской научной конференции. / Изд-во МГУ. — М., 2004. - С. 188-191.

15.Бездушный А.А., Бездушный А.Н., Серебряков В.А. Схемы метаданных ЕНИП: практика применения OWL в ЕНИП // Информационное обеспечение науки: новые технологии (ред. Н. Е. Калёнов) - М., 2005. - С. 155-182.

16. Бездушный А.А. Применение технологий Semantic Web для обеспечения интеропера-белыюго обмена научной информацией // Современные проблемы фундаментальных и прикладных наук: Труды 48-й научной конференции МФТИ. Часть VII. / Моск. физ.-тех. ин-т. - М„ 2005. - С. 209-211.

17. Бездушный А.А. Схемы метаданных для научных информационных ресурсов ЕНИП РАН // Порядковый анализ и смежные вопросы математического моделирования: Труды IV международной научной конференции. / Институт прикладной математики и информатики. - Владикавказ, 2006. - С. 260 - 271.

18.Бездушный А.А. Архитектура интеграции данных ИСИР // Современные проблемы фундаментальных и прикладных наук. Часть VII: Труды 49-й научной конференции МФТИ. / Моск. физ.-тех. ин-т. - М., 2006. - С. 230-231.

19.Бездушный А.А., Бездушный А.Н., Нестеренко А.К., Серебряков В.А., Сысоев Т.М., Теймуразов КБ., Филиппов В.И. Информационная Web-система «Научный институт» на платформе ЕНИП. - М.: Вычислительный Центр им. А.А. Дородницына РАН, 2007.-248 с.

20. Бездушный А.А. RQuery - язык запросов к источникам данных Semantic Web // Современные проблемы фундаментальных и прикладных наук. Часть VII: Труды 50-й научной конференции МФТИ. / Моск. физ.-тех. ин-т. - М., 2007. - Т.2 - С. 57-59.

В работах с соавторами личный вклад автора заключается в создании методов разработки распределенных систем и интеграции данных на основе технологий «Семантического Веб» (Semantic Web) и OWL-онтологий. Автором предложен основанный на применении OWL-онтологий подход к интеграции данных в Интегрированной Системе Информационных Ресурсов (ИСИР), Едином Научном Информационном Пространстве РАН (ЕНИП РАН), создан соответствующий комплекс программных модулей.

Апробация

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

- Всероссийская научная конференция "Электронные библиотеки: перспективные методы и технологии, электронные коллекции" (Санкт-Петербург, 2003; Пущино, 2004).

- Научно-практический семинар "Новые технологии в информационном обеспечении науки" (Таруса, 2003-2005).

- Международная конференция The 8th World Multi-Conference on Systemics, Cybernetics and Informatics - SCI 2004 (Orlando, Florida, 2004).

- Международный коллоквиум Spring Young Researcher's Colloquium On Database and Information Systems - SYRCoDIS (Санкт-Петербург, 2004).

- Всероссийская научная конференция "Научный сервис в сети Интернет" (Новороссийск, 2004).

- Международная конференция "Порядковый анализ и смежные вопросы математического моделирования" (Владикавказ, 2006).

- Научная конференция МФТИ (Долгопрудный, 2005-2007).

- Научные семинары отдела Систем математического обеспечения Вычислительного Центра им. А.А. Дородницына РАН (Москва, 2003-2008).

- Научные семинары кафедры математического моделирования сложных процессов и систем МФТИ (ГУ) (Москва, 2005-2008).

Краткое содержание работы

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

В главе 2 дается обзор стандартов Семантического Веб (Semantic Web) и рассматривается математическая основа языка веб-онтологий OWL — дескриптивная логика. Вводятся необходимые для дальнейшего изложения определения.

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

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

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

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

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

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

ЗАКЛЮЧЕНИЕ

В диссертационной работе получены следующие научные и практические результаты:

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

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

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

4. Предложена методология разработки систем интеграции данных на основе онтологий, в соответствии с формальной моделью.

5. На основе полученных теоретических результатов разработан прототип системы и комплекс программ исполнения распределенных запросов в среде Единого Научного Информационного Пространства РАН (ЕНИП РАН), предназначенной для виртуальной интеграции данных различных научных учреждений в ЕНИП РАН.

В заключение хочу поблагодарить моего научного руководителя д.ф.-м.н. В.А. Серебрякова и моего отца к.ф.-м.н. А.Н. Бездушного, без которых данная работа не могла бы осуществиться. Хочу поблагодарить также всех сотрудников отдела систем математического обеспечения Вычислительного Центра им. A.A. Дородницына РАН, принимавших участие в разработке Единого Научного Информационного Пространства РАН.

Библиография Бездушный, Алексей Анатольевич, диссертация по теме Математическое моделирование, численные методы и комплексы программ

1. Бездушный А.А., Бездушный А.Н., Серебряков В.А., Филиппов В.И. Интеграция метаданных Единого Научного Информационного Пространства РАН. М.: Вычислительный Центр им. А.А. Дородницына РАН, 2006. - 238 с.

2. Бездушный А.Н., Кулагин М.В., Серебряков В.А., Бездугииый А А., Неетеренко А.К., Сысоев Т.М. Предложения по наборам метаданных для научных информационных ресурсов // Журнал «Вычислительные Технологии» — Новосибирск, 2005 Т. 10, вып.7. - С. 29-48.

3. RDF Primer, http://www.w3.org/TR/rdf-primer/

4. OWL Web Ontology Language, http://www.w3.org/TR/owl-features/

5. SPARQL Query Language for RDF, http://wwAv.w3.org/TR/rdf-sparql-query/

6. Baader, F., Calvanese, D., McGuinness, D., Nardi, D., Patel-Schneider, P.F., The Description Logic Handbook: Theory, Implementation and Applications / Cambridge University Press, 2003.

7. Halevy, A.Y., Answering queries using views. A survey. // VLDB Journal: Very Large Data Bases, 2001, vol. 10, no. 4, pp. 270-294.

8. Halevy, A.Y., Rajaraman, A., Ordille, J., Data integration: the teenage years // VLDB Journal: Very Large Data Bases, 2006.

9. Lenzerini, M., Data integration: A theoretical perspective // In Proceedings of the 21st ACM SI-GACT-SIGMOD-STGART Symposium on Principles of Database Systems (PODS 2002), 2002, pp. 233-246.

10. Levy, A.Y., Rajaraman, A., Ordille, J J., Querying Heterogeneous Information Sources Using Source Descriptions // In Proceedings of the International Conference on Very Large Databases (VLDB), 1996.

11. Chaw at he, S., Garcia-Molina, IL, Hammer, J., Ireland, K., Papakonstantinou, Y., Ullman, J., Widom, J., The TSIMMIS project: Integration of heterogeneous information sources // In proceedings of IPS J, Tokyo, Japan, 1994.

12. Beeri C., LevyA.Y., Roussel M.-С., Rewriting queries using views in description logics // In Proceedings of the Sixteenth ACM SIG-SIGMOD-SIGART Symposium on Principles of Database

13. Systems (PODS'97), 1997 / ACM Press, New York, NY, pp. 99-108.

14. Bander, F., Kusters, R., Molitor, R, Rewriting concepts using terminologies II In Proc. of the 17th International Conference on Knowledge Representation and Reasoning (KR 2000), Morgan Kaufmann Publishers, San Francisco, CA. 2000, pp. 297-308.

15. Goasdoué, F., Rousset, M.-C., Rewriting Conjunctive Queries using Views in Description Logics with Existential Restrictions // Description Logics (DL 2000), 2000, pp. 113-122.

16. Goasdoué, F., Rousset, M.-C., Answering Queries using Views: a KRDB Perspective for the Semantic Web // ACM Journal Transactions on Internet Technology (TOIT), 2004, vol. 4, no. 3, pp. 255-288.

17. Calvanese D., De Giacomo G., Lenzerini M. Answering queries using views in description logics // In Proc. of the 17th Nat. Conf. on Artificial Intelligence (AAAI 2000), pp. 386-391.

18. Calvanese, D., De Giacomo, G., Lembo, D., Lenzerini, M., Rosati, R., Data complexity of query answering in description logics // In Proc. of the 2005 Description Logic Workshop (DL'2005), volume 147 of CEUR Electronic Workshop Proceedings, 2005.

19. Calvanese, D., De Giacomo, G., Lembo, D. Lenzerini, M., Rosati, R., Vetere, G., DL-Lite: Practical reasoning for rich DLs // In Proc. of the 2004 Description Logic Workshop (DL' 2004), volume 104 of CEUR Electronic Workshop Proceedings, 2004.

20. Poggi, A., Lembo, D. Calvanese, D., De Giacomo, G., Lenzerini, M., Rosati, R., Linking data to ontologies // J. on Data Semantics, 2008, pp. 133-173.

21. Calvanese, D., De Giacomo, G., Lenzerini, M., Rosati, R., View-based query answering over description logic ontologies // In Proc. of the 11 th Int. Conf. on the Principles of Knowledge Representation and Reasoning (KR 2008), 2008.

22. Patel-Schneider, P. F., Horrocks, L, Motik, B., OWL 1.1 Web Ontology Language: Structural Specification and Functional-Style Syntax, 2006, http://www.w3.org/2007/OWL/wiki/Syntax

23. Baader, F.; Brandt, S.; and Lutz, C., Pushing the EL envelope // In Proc. of the 19th Int. Joint Conf. on Artificial Intelligence (IJCAI 2005) , 2005, pp. 364-369.

24. Grosof, B., Volz, R., Horrocks, I. Decker, S., Description Logic Programs: Combining Logic Programs with Description Logics // In Proc. of the 12th International World Wide Web Conference (WWW 2003), 2003.

25. Hi/stand, U., Mofik, B., Saltier, U., Data Complexity in Very Expressive Description Logics // In Proc. of the 19th Joint Int. Conf. on Artificial Intelligence (IJCAI 2005), 2005.

26. Tobies, S., Complexity Results and Practical Algorithms for Logics in Knowledge Representation, Ph.D. Dissertation, 2002.

27. Grau, B.C., OWL 1.1 Web Ontology Language Tractable Fragments. http://www.w3.org/Subinission/owll 1-tractable/

28. RDF Vocabulary Description Language 1.0: RDF Schema, http://www.w3.org/TR/rdf-schema/

29. Gryz, J., Query rewriting using views in the presence of functional and inclusion dependencies // J. Information Systems, 1999, vol. 24, no. 7, pp. 597-612.

30. Call, A., Lembo, D., Rosati, R., Query rewriting and answering under constraints in data integration systems // In Proc. of the Eighteenth International Joint Conference on Artificial Intelligence (IJCAI 2003). 2003, pp. 16-21.

31. Abiteboul, S., Hull. R., Vianu, V. Foundations of Databases. Addison-Wesley, Reading, MA 1995.

32. Vardi, M. Y. The complexity of relational query languages // In STOC-82. 1982, pp. 137- 146.

33. Johnson, D.S., Klug, A.C. Testing containment of conjunctive queries under functional and inclusion dependencies//J. Comput. Syst. Sci. 28(1), 167-189, 1984.

34. Pottinger, R., Halevy, A. MiniCon: A scalable algorithm for answering queries using views // VLDB Journal: Very Large Data Bases, 2001. vol. 10, no. 2-3, pp. 182-198, 2001.

35. Oian, X. Query folding // In Proc. of 12th IEEE International Conference on Data Engineering (ICDE'96), pp. 48-55, 1996.

36. Mitra, P. An algorithm for answering queries efficiently using views // In Proc. of the 12th Australasian database conference, 2001.

37. Wang, J., Maher, M., Topor, R., Rewriting General Conjunctive Queries Using Views // Tn Proc. of 13th Australasian Database Conference (ADC'2002), 2002.

38. P. Kolaitis, D. Martin, M. Thakur. On the complexity of the containment problem for conjunctive queries with build-in predicates // In Proc. of PODS'98, Seattle, WA, 1998.

39. Van der Meyden, R. Logical Approaches to Incomplete Information: A Survey // In J. Chomicki and G. Saake, eds., Logics for Databases and Information Systems, chapter 10. Kluwer Academic Publishers, Boston, 1998.

40. Isabel F. Cruz, Huiyong Xiao, and Feihong Hsu. Peer-to-Peer Semantic Integration of XML and RDF Data Sources. University of Illinois, Chicago, 2004.

41. S. Bergamachi, S. Castano, A. Ferrara, F. Grandi, F. Guerra, G. Ornetti, M. Vincini. Description of the methodology for the integration of strongly heterogeneous sources, 2002.

42. Heiner Stuckenschmidt, Frank van Harmelen. Information Sharing on the Semantic Web, Springer, 2003.

43. Lachlan M. Mackinnon, David H. Marwick, M. Howard Wilhams. A Model for Query Decomposition and Answer Construction in Heterogeneous Distributed Database Systems // Journal of Intelligent Information Systems 11,69-87, 1998.

44. Budi Yuwono, DikL. Lee. Search and Ranking Algorithms for Locating Resources on the World Wide Web. The Ohio State University, 1996.

45. Brendon Caoon, Kathryn S. McKinley. Perfomance Evaluation of a Distributed Architecture for Information Retrieval. University of Massachusetts, 1996.

46. Norbert Fuhr. Models for Integrateed Information Retrieval and Database Systems. University of Dortmund, Germany, 1996.

47. Jan Jannick, Prasenjit Mitra, Erich Neuhold, Srmivasan Picjai, Rudi Studer, Gio Wiederhold. An Algebra for Semantic Interoperation of Semistructured Data. Stanford University, 2000.

48. Mike Uschold, Michael Gruninger. Ontologies: Principles, Methods and Applications. Knowledge Engineering Review, vol. 11, n.2, 1996.

49. Susanne Busse, Ralf-Detlef Kutsche, Ulf Leser, Herbert Weber. Federated Information Systemts: Concepts, Terminology and Architectures. Technische Universität Berlin, 1999.

50. Ismail Khalil Ibrahim, Wieland Schwinger. Data Integration in Digital Libraries: Approaches and Challenges. Software Competence Center Hagenberg, 2000.

51. William H. Wilson, Nadine Marcus, Graeme S. Halford. Access to Relational Knowledge: a Comparison of Two Models. University of New South Wales, 2000.

52. Marco Schorlemmer, Yannis Kalfoglou. On Semantic Interoperability and the Flow of Information. The University of Edinburgh, 2003.

53. Michel Klein. Combining and relating ontologies: an analysis of problems and solutions. Vrije Univesiteit, 2000.

54. Amarnath Gupta, Bertram Ludascher, Maryann E. Martone. Registering Scientific Information Scources for Semantic Meditaion. University of California 2002.

55. Farshad Hakimprour, Andreas Geppert. Resolving Semantic Heterogeneity in Schema Integration: an Ontology Based Approach. University of Zurich, 2001.

56. Peter McBrien and Alexandra Poulovassilis. A Formalizsation of Semantic Schema Integration. King's College London, 1998.

57. Catherine Houstis, Christos Nikolaou, Spyros Lalis, Saranlos Kapidakis, Vassilis Chrisophides. Towards a Next Generation of Open Scientific Data Repositories and Services. University of Crete, 1998.

58. Hector Garcia-Molina, Yannis Papakonstantinou, Dalian Quass, Anand Rajaraman, Yehoshua Sagiv, Jeffrey Ullman, Vasilis Vassalos, Jennifer Widom. The TSIMMIS Approach to Mediation: Data Models and Languages. Stanford University, 1997.

59. Philip Homburg, Leendert van Doom, Maarten van Steen, Andrew S. Tanenbaum, Wiebren de Jonge. An Object Model for Flexible Distributed Systems. Vrije Universiteit, 1995.1. СПИСОК ИЛЛЮСТРАЦИЙ

60. Рис. 1. «Проблемные измерения» интеграции данных.13

61. Рис. 2. 5-уровневый подход федеративных БД.16

62. Рис. 3. Системы интеграции данных по принципу посредников.17

63. Рис. 4. Структура онтологий ЕНИП.91