Содержание к диссертации
Введение
Глава 1. Обзор методов интеграции данных 12
1.1. Проблематика интеграции данных 12
1.2. Классификация подходов к интеграции данных 13
1.3. Архитектура систем интеграции данных по принципу посредников 17
Глава 2. Технологии Семантического Веб и дескриптивная логика 19
2.1. Технологии Семантического Веб 19
2.2. Математический аппарат дескриптивной логики 19
2.3. Трансляция языка веб-онтологий OWL в дескриптивную логику 24
2.4. Сопоставление диалектов дескриптивной логики 25
2.5. Языки запросов и ответ на запросы относительно онтологии 26
Глава 3. Математическая модель системы интеграции данных на основе онтологии 31
3.1. Система определений и формализация задачи 31
3.2. Семантика ответа на запросы в системе интеграции данных на основе онтологии .35 CLASS Глава 4. Интеграция больших объемов данных на основе онтологии 39 CLASS
4.1. Переформулировка запросов относительно системы интеграции данных 39
4.2. Анализ существования точной переформулировки 41
4.3. Дескриптивная логика DLtrb 47
4.4. Трансляция языка веб-онтологий OWL в дескриптивную логику DLtn0 53
4.5. Нормализация онтологии DLtrio 56
4.6. Вычисление ответов на запросы относительно онтологии DLtno 59
Глава 5. Алгоритм переформулировки запросов для систем интеграции данных на основе онтологии 65
5.1. Рассматриваемый класс задач 65
5.2. Алгоритм построения переформулировки 65
5.2.1. Этап 1. Переформулировка запроса относительно аксиом глобальной онтологии 66
5.2.2. Этап 2. Переформулировка запроса относительно отображений 74
5.2.3. Этап 3. Переформулировка запроса относительно аксиом онтологии источников 78
5.2.4. Этап 4. Минимизация запроса .-. 78
5.3. Корректность и анализ алгоритма 80
Глава 6. Анализ и применение полученных результатов 84
6.1. Анализ выразительных возможностей рассматриваемого класса систем интеграции данных 84
6.2. Сравнение со смежными работами 85
6.3. Направления дальнейших исследований 89
6.4. Методология построения систем интеграции данных на основе полученных результатов 89
6.5. Применение полученных результатов 90
Заключение 93
Список использованных источников 94
Список иллюстраций
- Классификация подходов к интеграции данных
- Трансляция языка веб-онтологий OWL в дескриптивную логику
- Дескриптивная логика DLtrb
- Переформулировка запроса относительно отображений
Введение к работе
Актуальность темы следует из возросшего интереса к проблеме интеграции данных в различных сферах деятельности, связанных с накоплением и эффективным использованием информации.
Интеграция данных является одним из наиболее востребованных направлений в современной информационной индустрии. Интенсивное развитие информационных технологий и сети Интернет привело к накоплению огромных объемов данных в различных источниках, разнородных, автономно разработанных, представляющих информацию различными способами, содержащих взаимосвязанные и взаимно противоречивые сведения. Интеграция и совместное использование информации из множества таких источников данных является сложной задачей, остающейся неизменно актуальной на протяжении последних десятилетий.
Интеграция данных необходима для крупных организаций, в которых информация разбросана по различным специализированным системам, построенным в разное время и для разных целей, для повышения эффективности внутриведомственного и межведомственного взаимодействия государственных органов, для предоставления более качественных поисковых сервисов в сети Интернет, обеспечивающих получение согласованной информации из множества структурированных источников данных. Интеграция данных играет сегодня ключевую роль и для научной деятельности. В настоящее время всё большие объемы научной информации становятся в том или ином виде доступны в сети Интернет. В то же время, возможности существующих поисковых систем общего назначения не позволяют обеспечить эффективный поик научной информации, что ставит вопрос о разработке специализированных поисковых систем, интегрирующих интересующие научных сотрудников сведения.
Задача интеграции данных в настоящее время в той или иной степени исследована для различных условий, преимущественно, в контексте реляционных баз данных. В то же время предложенные подходы к решению задачи имеют недостатки и ограничения, и многие актуальные вопросы остаются открытыми.
Актуальным направлением исследований в этой области является применение к задаче интеграции данных аппарата дескриптивной логики, прежде всего в контексте Семантического Веб (Semantic Web).
Технологии Семантического Веб являются молодым и перспективным направлением развития современной информационной индустрии. Утвержденные World Wide Web Консорциумом (W3C) в 2004 году модель описания информационных ресурсов RDF (Resource Description Framework) и язык веб-онтологий OWL (Web Ontology Language) определили стандартный способ семантически богатого описания распределенной в сети Интернет информации. В этой связи представляется целесообразным рассматривать их применение в контексте современных систем интеграции распределенных данных.
Формальной основой языка веб-онтологий OWL является так называемая дескриптивная логика - математический аппарат, предназначенный для представления терминологического знания о предметной области. Применение в системе интеграции данных аппарата дескриптивной логики вместо реляционной модели данных позволяет существенно расширить выразительные возможности системы. Онтологии позволяют специфицировать структуру и семантику терминов системы интеграции данных и информационных источников, выразить различные формы сложных ограничений целостности в системе интеграции данных, правила логического вывода.
Ключевой проблемой при рассмотрении задачи интеграции данных в контексте дескриптивной логики является ее трудноразрешимость или неразрешимость для достаточно выразительных диалектов дескриптивной логики. В то же время на практике важно сочетать выразительные возможности выбранного диалекта дескриптивной логики с эффективной работой с большими объемами данных.
В данной работе рассмотрен вопрос построения систем интеграции данных с применением аппарата дескриптивной логики и предложен выбор диалекта дескриптивной логики, который целесообразно использовать при интеграции больших объемов данных, хранимых в реляционных базах данных. Рассмотрен метод вычисления ответа на запрос к такой системе интеграции данных, предполагающий предварительную переформулировку исходного запроса, и предложен алгоритм переформулировки запроса для выбранного диалекта дескриптивной логики.
Таким образом, работа посвящена актуальной задаче интеграции данных с применением дескриптивной логики и технологий Семантического Веб, а предложенные в ней математическая модель, методы и алгоритмы формируют прочный фундамент для построения таких систем интеграции данных на практике.
Целью диссертационной работы является разработка математической модели системы интеграции данных, основанной на применении аппарата дескриптивной логики, и исследование методов вычисления ответа на запрос к такой системе при условии интеграции больших объемов данных.
В работе исследованы и решены следующие задачи:
Проведено сопоставление выразительных возможностей и вычислительных характеристик различных диалектов дескриптивной логики.
Предложена методика интеграции данных, основанная на применении аппарата дескриптивной логики, разработана математическая модель системы интеграции данных на основе онтологии, формализованы понятия ответа на запрос и переформулировки запроса в такой системе интеграции данных.
Предложен и обоснован выбор максимального, в определенном смысле, диалекта дескриптивной логики, для которого возможна эффективная интеграция больших объемов данных.
Предложен и обоснован алгоритм построения точной переформулировки запроса для выбранного класса систем интеграции данных на основе онтологии.
Разработан прототип системы исполнения распределенных запросов в среде Единого Научного Информационного Пространства РАН (ЕНИП РАН).
Научная новизна работы заключается в том, что в диссертационной работе рассмотрен перспективный класс систем интеграции данных, отличительной особенностью которого является применение аппарата дескриптивной логики для более гибкого описания семантической взаимосвязи терминов, ограничений целостности, правил логического вывода.
В отличие от предшествующих работ по интеграции данных, полученный в данной работе результат имеет следующие особенности:
В основу рассматриваемого класса систем интеграции данных положен мощный математический аппарат дескриптивной логики, что является ключевым отличием от большинства смежных работ, рассматривающих интеграцию данных на основе реляционной модели данных и других семантически более бедных моделей данных.
В работе предложена оригинальная математическая модель системы интеграции данных, основанная на аппарате дескриптивной логики.
В работе рассматриваются выразительные системы интеграции данных, в которых отображения онтологии задаются парами конъюнктивных запросов с ограничениями, несмотря на допущение в онтологиях достаточно сложных ограничений целостности. Более того, показывается, что рассматриваемые системы в определенном смысле обладают максимально допустимыми выразительными возможностями для эффективного использования на практике. В предшествующих работах, посвященных применению дескриптивной логики к задаче интеграции данных, рассматривались существенно более ограниченные по выразительным возможностям отображения, позволяющие устранить меньшее число семантических конфликтов между информационными источниками. Таким образом, полученный в работе результат представляет собой существенный шаг вперед по расширению систем интеграции данных аппаратом дескриптивной логики.
Для выбранных условий задачи предложен алгоритм переформулировки запросов в системе интеграции данных на основе онтологии, представляющий собой новый существенный вклад в технологии интеграции данных, а также позволяющий непосредственно использовать полученный результат для практических задач.
Кроме того, разработан прототип системы исполнения распределенных запросов в среде Единого Научного Информационного Пространства РАН (ЕНИП РАН), позволяющий обеспечить виртуальную иптеграцию данных различных научных учреждений в ЕНИП. Такая система позволяет расширить ЕНИП новым сервисом ответа на поисковые запросы с учетом разнородности информационных источников ЕНИП, при этом, в отличие от предшествующей реализации поисковых сервисов ЕНИП, не требуется предварительной репликации или индексации информации из источников.
Практическая ценность работы заключается в том, что предложенные математическая модель, методы и алгоритмы могут служить основой для практической реализации систем интеграции данных на основе стандартов «Семантического Веб» (RDF. OWL, SPARQL).
Непосредственное применение полученные в работе теоретические результаты нашли в проекте «Единое Научное Информационное Пространство РАН» (ЕНИП РАН). Работа расширяет полученные ранее результаты по ЕНИП новыми функциональными возможностями. Предложенные в диссертационной работе математическая модель системы интеграции данных на основе онтологии и практический алгоритм переформулировки запросов в такой системе представляют собой фундамент для виртуальной интеграции данных различных научных учреждений в рамках ЕНИП.
На основе полученных в диссертационной работе теоретических результатов разработан прототип системы исполнения распределенных запросов в среде ЕНИП. Такой поисковый сервис позволяет динамически получать ответы на поисковые запросы, выраженные в терминах OWL онтологии ЕНИП. При исполнении запроса в системе обеспечивается соединение сведений из релевантных информационных источников ЕНИП, и на основе таких сведений формируется интегрированный согласованный ответ. При этом система позволяет преодолеть семантическую разнородность информационных источников, то есть, различие схем данных (онтологии) источников. В отличие от предшествующей реализации поисковых сервисов ЕНИП, не требуется предварительной репликации или индексации сведений из информационных источников - вычисляемый системой ответ включает исключительно актуальные сведения, полученные непосредственно из источников данных.
Помимо ЕНИП, полученные в работе результаты могут быть использованы при построении других распределенных информационных систем, предполагающих виртуальную интеграцию данных из разнородных источников. В частности, в настоящее время широко востребованы специализированные поисковые системы, интегрирующие информацию из различных Интернет-сайтов и систем, по некоторой тематике. Полученный в работе результат представляет метод построения таких поисковых систем на основе технологий Семантического Веб.
Основные научные и практические результаты, выносимые на защиту
В диссертационной работе представлены следующие результаты, выносимые на защиту:
Предложена математическая модель систем интеграции данных на основе онтологии, введена система определений на базе математического аппарата дескриптивной логики, формализованы понятия ответа на запрос и переформулировки запроса в системах интеграции данных на основе онтологии.
В рамках предложенной модели исследованы условия существования точной переформулировки запроса на выбранном языке запросов. Предложен и обоснован выбор диалекта дескриптивной логики, который целесообразно использовать при интеграции больших объемов данных, хранимых в реляционных базах данных.
Разработан алгоритм построения точной переформулировки запроса для выбранного класса систем интеграции данных на основе онтологии.
Предложена методология разработки систем интеграции данных на основе онтологии, в соответствии с формальной моделью.
На основе полученных теоретических результатов разработан прототип системы и комплекс программ исполнения распределенных запросов в среде Единого Научного Информационного Пространства РАН (ЕНИП РАН), предназначенной для виртуальной интеграции данных различных научных учреждений в ЕНИП РАН.
Публикации
По теме диссертации опубликовано 20 работ, в том числе две [1,2] из списка изданий, рекомендованных ВАК РФ:
Бездушный А.А. Математическая модель системы интеграции данных на основе онтологии // Журнал «Вестник НГУ», серия «Информационные технологии» — Новосибирск, 2008. - Т.6, вып.2. - С 15-40.
Бездушный А.Н., Кулагин М.В., Серебряков В.А., Бездушный А.А., Нестеренко А.К., Сысоев Т.М. Предложения по наборам метаданных для научных информационных ресурсов // Журнал «Вычислительные Технологии» - Новосибирск, 2005 - Т. 10, ВЫП.7.-С. 29-48.
Бездушный А.А., Бездушный А.Н., Серебряков В.А., Филиппов В.И. Интеграция метаданных Единого Научного Информационного Пространства РАН. — М.: Вычислительный Центр им. А.А. Дородницына РАН, 2006. - 238 с.
Бездушный А.А. Распределенное исполнение SPARQL-запросов в гетерогенной среде // Моделирование и обработка информации: Сборник научных трудов / Моск. физ.-тех. ин-т. - М., 2008. - С. 230-235.
Bezdushny А.А., Bezdushny A.N., Nesterenko А.К., Serebriakov V.A., Sysoev Т.М. Integrated System of Information Resources of the Russian Academy of Sciences II Proceedings of the 8th World Multi-Conference on Systemics, Cybernetics and Informatics SCI 2004, Orlando, Florida - 2004. - P. 462-467.
Бездушный A.A., Бездушный A.H., Нестеренко А.К., Серебряков В.А., Сысоев Т.М. Архитектура RDFS-системы. Практика использования открытых стандартов и технологий Semantic Web в системе ИСИР // Электронные библиотеки: перспективные методы и технологии, электронные коллекции: Труды V всероссийской научной конференции / Изд-во СПбГУ. - СПб., 2003. - С. 45-60.
Бездушный А.А., Бездушный А.Н., Нестеренко А.К., Серебряков В.А., Сысоев Т.М. Java и XML технологии новой версии ИСИР // Современные технологии в информационном обеспечении науки (ред. Н. Е. Калёнов) — М., 2003. - С. 182-205.
Бездушный А.А., Бездушный А.Н., Жижченко А.Б., Кулагин М.В., Серебряков В.А. RDF схема метаданных ИСИР // Современные технологии в информационном обеспечении науки (ред. Н. Е. Калёнов) —М., 2003.-С. 141-159.
Bezdushny A.A., Nesterenko A.K. ISIR Architecture for Web-Repository Integration II Сборник докладов Первого весеннего коллоквиума молодых исследователей в области баз данных и информационных систем (SYRCoDIS'2004) - СПб., 2004. - С. 60-66.
Бездушный А.А., Бездушный А.Н, Нестеренко A.K, Серебряков В.А., Сысоев Т.М. Возможности технологий ИСИР в поддержке Единого Научного Информационного Пространства РАН // Электронные библиотеки: перспективные методы и технологии, электронные коллекции: Труды VI всероссийской научной конференции — М., 2004. — С. 254-262.
Бездушный А.А., Бездушный А.Н., Жижченко А.Б., Калёное Н.Е., Кулагин М.В., Серебряков В.А. Предложения по наборам метаданных для научных информационных ресурсов ЕНИП РАН // Электронные библиотеки: перспективные методы и технологии, электронные коллекции: Труды VI всероссийской научной конференции - М, 2004. - С. 277-284.
Бездушный А.А., Нестеренко A.K, Сысоев Т.М. , Бездушный А.Н., Серебряков В.А. Архитектурные решения ИСИР на платформах Java и XML // Интегрированная система информационных ресурсов: архитектура, реализация, приложения: Сборник трудов / Вычислительный Центр им. А.А. Дородницына РАН. - М., 2004. — С. 78-95.
Бездушный А.А. Роль технологий Semantic Web в решениях ИСИР //Интегрированная система информационных ресурсов: архитектура, реализация, приложения: Сборник трудов / Вычислительный Центр им. А.А. Дородницына РАН. — М., 2004. — С. 36-55.
Бездушный А.А., Нестеренко А.К., Сысоев Т.М., Кулагин М.В. Semantic Web и OWL-онтологии в разработке ИСИР-систем // Научный сервис в сети Интернет: Труды Всероссийской научной конференции. / Изд-во МГУ. — М., 2004. - С. 188-191.
Бездушный А.А., Бездушный А.Н., Серебряков В.А. Схемы метаданных ЕНИП: практика применения OWL в ЕНИП // Информационное обеспечение науки: новые технологии (ред. Н. Е. Калёнов) - М., 2005. - С. 155-182.
Бездушный А.А. Применение технологий Semantic Web для обеспечения интеропера-белыюго обмена научной информацией // Современные проблемы фундаментальных и прикладных наук: Труды 48-й научной конференции МФТИ. Часть VII. / Моск. физ.-тех. ин-т. - М., 2005. - С. 209-211.
17'. Бездушный А.А. Схемы метаданных для научных информационных ресурсов ЕНИП РАН // Порядковый анализ и смежные вопросы математического моделирования: Труды IV международной научной конференции. / Институт прикладной математики и информатики. - Владикавказ, 2006. - С. 260 - 271.
18. Бездушный А.А. Архитектура интеграции данных ИСИР // Современные проблемы фундаментальных и прикладных наук. Часть VII: Труды 49-й научной конференции МФТИ. / Моск. физ.-тех. ин-т. - М., 2006. - С. 230-231.
19.Бездушный А.А., Бездушный А.Н., Нестеренко A.K, Серебряков В.А., Сысоев Т.М., Теймуразов КБ., Филиппов В.И. Информационная Web-система «Научный институт»
на платформе ЕНИП. - М.: Вычислительный Центр им. А.А. Дородницына РАН, 2007.-248 с. 20. Бездушный А.А. RQuery - язык запросов к источникам данных Semantic Web II Современные проблемы фундаментальных и прикладных наук. Часть 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 проводится анализ выразительных возможностей рассмотренного класса систем интеграции данных на основе онтологии. Приводится сравнение со смежными работами, анализируются направления дальнейших исследований. Описывается методология построения программных систем интеграции данных, соответствующих предложенной математической модели. Рассмотрено практическое применение полученных результатов в контексте Единого Научного Информационного Пространства РАН. Приводится описание прототипа системы исполнения распределенных запросов в среде Единого Научного Информационного Пространства РАН (ЕНИП РАН). Рассматривается также спектр других актуальных задач, для решения которых могут быть применены полученные результаты.
В заключении приведены основные результаты диссертационной работы.
Классификация подходов к интеграции данных
Существующие подходы к интеграции данных можно классифицировать по следующим основным критериям:
- Модели данных и функциональные возможности источников. Методы интеграции данных и предоставляемые пользователю возможности во многом определяются «качеством» интегрируемой информации. Может рассматриваться интеграция структурированных источников данных (таких как, например, реляционные базы данных), слабоструктурированных (например, HTML, XML) и неструктурированных данных (например, документов). При этом источники данных могут предоставлять в той или иной степени полноценный интерфейс доступа к данным, в том числе, язык запросов.
- Глобальная модель данных и функциональные возможности системы интеграции — определяют способ подачи информации пользователю, возможности системы по работе с информацией в источниках: доступ «только на чтение» или «чтение-запись», глобальный язык запросов.
- Степень материализации данных. Система интеграции данных может получать информацию из источников непосредственно по запросу пользователя, либо перманентно собирать и физически накапливать такую информацию, и на основе накопленной информации отвечать на запросы пользователя. Первый подход принято называть виртуальной интеграцией данных, второй — материализацией данных из источников. Системы, предполагающие материализацию данных, позволяют обеспечить быстрое исполнение запросов после того, как процесс материализации завершен, но при этом материализованные данные могут быстро устаревать. Кроме того, для хранения материализованных данных из источников может потребоваться большое количество ресурсов (дискового пространства). Напротив, виртуальная интеграция не требует ресурсов для хранения данных, получаемых из источников, и по запросу пользователя выдает исключительно актуальные сведения, но получение данных может занять некоторое время, обуславливаемое сетевыми задержками. Возможны также гибридные подходы.
— Степень связности представляемой пользователю информации. В сильно связных системах информация представляется пользователю в терминах некоторой единой системы понятий (глобальной схемы данных), таким образом скрывая различные системы понятий (схемы данных), используемые для представления информации в источниках данных, при этом некоторым образом обеспечивается взаимосвязь понятий. В слабо связных системах единой системы понятий не вводится, и пользователь должен иметь дело с различными системами понятий различных источников, самостоятельно решать проблемы устранения семантических конфликтов.
— Степень семантической интеграции (устранения семантических конфликтов). Информация об одном и том же реальном объекте может присутствовать, полностью или частично, в различных источниках данных. Источники данных могут содержать взаимосвязанные и взаимно противоречивые сведения. Для того чтобы представить пользователю целостное и непротиворечивое представление данных из таких источников система должна определенным образом соединять результаты, получаемые из различных источников. Чем лучше система решает эту задачу, тем более полезной она будет для пользователя, однако известно, что в общем случае такая задача сложна [46].
— Подход к разработке системы интеграции данных «снизу вверх» или «сверху вниз». При разработке системы интеграции данных «снизу вверх» требуется обеспечить интегрированный доступ к заданным источникам данных. Основной задачей при этом является интеграция схем данных источников и предоставление пользователю их «смыслового объединения», глобальная схема данных является в определенной степени производной от схем данных источников. В таких случаях часто рассматриваются процедурная спецификация способа извлечения информации из источников. Зачастую подразумевается, что новые источники данных не могут быть динамически добавлены в систему без повторения всего процесса и расширения глобальной схемы данных. Напротив, при разработке системы интеграции данных «сверху вниз» процесс разработки системы начинается с моделирования некоторой системы понятий (глобальной схемы данных), исходя из интересующих пользователя аспектов информации, доступ к которой должна предоставить система. Далее для каждого добавляемого в систему источника специфицируется семантическое отображение между схемой данных источника и глобальной схемой данных, используемое системой при извлече ний информации по запросу пользователя. Новые источники данных в такую систему могут быть добавлены динамически. Можно отметить следующие распространенные сегодня типы информационных систем, обеспечивающих интегрированный доступ к информации из множества источников: - Распределенные СУБД (распределенные системы управления базами данных); - «Хранилища данных» (Data warehouse); - Федеративные БД (FDB); - Системы интеграции данных по принципу посредников (MBIS); - Системы интеграции данных по принципу взаимодействия равноправных узлов (Р2Р). Распределенные СУБД позволяют построить интегрированную систему, состоящую из нескольких баз данных (в большинстве случаев рассматриваются реляционные БД). Возможность построения распределенных баз данных предусмотрена сегодня в продуктах всех крупнейших поставщиков РСУБД. Распределенные РСУБД предоставляют, как правило, полноценные функциональные возможности, принятые для реляционных баз данных. Степень разнородности и автономности источников при этом предполагается минимальной, семантическая интеграция данных не рассматривается.
«Хранилища данных» (Data warehouse) основаны на принципе материализации данных, в таких системах осуществляется предварительный (или перманентный) сбор информации из источников и накопление ее в центральном хранилище. Накопленная информация предоставляется пользователю, в режиме «только для чтения». «Хранилища данных» также широко представлены в продуктах крупнейших поставщиков РСУБД. Основной проблемой таких систем является поддержка актуальности данных, поскольку накопленная информация может быстро устаревать. Кроме того, хранение накопленной информации может требовать существенных ресурсов. Применение «хранилищ данных» считается целесообразным прежде всего в тех случаях, когда пользовательские запросы могут быть достаточно сложными, и производительность при выполнении таких запросов является критичной (например, аналитическая обработка данных).
Федеративные БД отвечают за интеграцию БД с учетом как различности модели данных, так и семантической неоднородности схем БД, с формированием единой виртуальной схемы, и за предоставление возможности выполнения с интегрированной БД всех операций, свойственных традиционным БД. С целью структурировать процесс отображения данных из БД-компонента в интегрирующую БД, была предложена 5-уровневая архитектура. На первом шаге преодолеваются все различия моделей данных разных БД сведением их к выбранной единой канонической модели. Каждая БД-компонент решает, какие данные она предоставляет в интегрирующую БД выбором «схемы экспорта». На втором шаге интегрирующая БД решает, какие данные из «схем экспорта» ее интересуют, формируя «схемы импорта». На третьем шаге федеративная СУБД отображает схемы импорта в единую интегрирующую схему, устраняя семантическую неоднородность представления данных.
Трансляция языка веб-онтологий OWL в дескриптивную логику
Здесь А - атомарный концепт, Ci..n — концепт, RQ — абстрактная роль, R i п — атрибут, Rs — абстрактная роль, не имеющая, транзитивных вложенных ролен (с учетом рефлексивно-транзитивного замыкания, см. [ЗО]), а; є Са, с; є Cd, n 1, d — допустимый примитивный тип данных1. Неформально, сложный концепт задает некоторый класс объектов на основе других концептов и ролей с помощью следующих конструкторов: - Верхний концепт Т. содержащий все объекты; - Нижний концепт 1, не содержащий объектов; - Атомарный концепт А є Nc; - Дополнение концепта - С - задает класс объектов, не принадлежащих к С; - Конъюнкция концептов Сі П С? — задает класс объектов, принадлежащих одновременно к обоим концептам Сі и СУ, - Дизъюнкция концептов Ci U Сі — задает класс объектов, принадлежащих к Сі или С2; - Универсальное ограничение VRQ.C - задает класс объектов, которые роль R , связывает только с объектами из класса С (аналогично VRdi..Rdn.D - со значениями типа D); - Экзистенциальное ограничение 3R0.C — задает класс объектов, связываемых ролью Ra с объектом из класса С (аналогично 3Rdi..Rdn.D — со значением типа данных D); - Ограничения мощности n Rs. n R i (и соответственно n Rs, n Rd) — задают классы объектов, связываемых заданной ролью не менее чем (не более чем) с п объектами (значениями); - Перечисление {ai...., ап} - задает концепт перечислением множества объектов.
Теперь мы готовы дать определение допустимых видов высказываний онтологии. Определение 3. Терминология для SHOXAfP) может включать следующие аксиомы: - Сі С С2, где Сь С2- концепты (аксиома вложения концептов); - Roi Е Ro2, где Roi, Ro2- абстрактные роли (аксиома вложения абстрактных ролей); - R ii E Rj2, где Rdi, Rd2- атрибуты (аксиома вложения атрибутов); - Trans(R0), где R0 - абстрактная роль (аксиома транзитивности роли).
В дальнейшем мы будем также использовать сокращенную нотацию Ci = Сі, подразумевая под этим пару аксиом Сі Е С2, С2 Е С], и аналогично для ролей.
Определение 4. Множество фактов онтологии Л содержит высказывания формы А(а) или Р(а,Ь), где А є Nc - атомарный концепт, Р є NRo U NRd — атомарная роль, а є Са, b є С.
Отметим, что рассматривая только атомарные высказывания в множестве фактов Л мы не ограничиваем общность задачи по сравнению со случаем, когда в Л допускаются сложные высказывания в форме С(а) или R(a,b), где С- (сложный) концепт, R— (сложная) роль, а є Са, Ъ є С. Действительно, любое такое сложное высказывание мы можем заменить атомарным Ас(а) или Р (а,Ь), где Ас є Nc, PR Є NR0 U NRJ, при условии, что терминология пополняется искусственными аксиомами Ас Е С, С Е Ас, либо PR Е R, R Е PR, соответственно (если такие аксиомы допускаются используемым диалектом дескриптивной логики).
Пример 1. Рассмотрим следующие аксиомы (1-2) и высказывания множества фактов (3):
(1) Корова Е Животное П 3ест.(Растение U Зчасть.Растение): корова = животное, которое ест растения или их части
(2) 3 Направление = Направление П - размещение.(Отель П 3 категория. {3 }): 3 направление о направление, в котором нет отелей категории не 3 (3) Направление {OrlandoJFL); Отель (RosenCenlreHotel); категория {RosenCentreHotel, 5 ) размещение (Orlando_FL, RosenCentreHotel) и
Теперь перейдем от рассмотрения синтаксиса высказываний онтологии к их семантике. Введем ключевые понятия интерпретации и модели онтологии, которые формализуют семантику онтологии (см. также [30]).
Определение 5. Интерпретацией X онтологии О—{Т. Л} называется пара (Д , ), где Д — непустое множество объектов, называемое областью определения интерпретации Т, а — функция интерпретации, которая сопоставляет каждому концепту терминологии Тнекоторое подмножество А7, а каждой роли — подмножество декартова произведения А7 х Д7. Функция интерпретации определяется индуктивно, в зависимости от конструкций используемого диалекта дескриптивной логики. Следующее определение функции интерпретации вводится для SHOXN D) (обозначения те же, что и выше): - Р7 С Д7 х Д7 (каждой атомарной роли Р сопоставляется подмножество А7 х Д7) - (а.Ь) єР;« (Ь,а) є (Р У (обратные роли Р ) - Л с д (каждому атомарному концепту сопоставляется подмножество Д7) - d7 С Д7 (каждому примитивному типу данных сопоставляется подмножество А7) - Т7 = А7 (верхний концепт представляет А7) - J.7 = 0 (нижний концепт — пустое множество) - (-С)7 = А7 \ С7 (дополнение С7 в А7) - (Сі П С2)7 = С/ П С27 (пересечение) - (Сі U С2)7 = С/ U С27 (объединение) - (VR0.C); = {а є A71 Vb є Д7: (a,b) є R07 - - b є с } (универсальное ограничение абстр. роли) - (BRQ.C) = {а Є Д I ЗЬ є С : (a,b) є Rj} (экзистенциальное ограничение абстрактной роли) - (3Rdi Rdn-D)7 = (а є Д71 3bi...bn є D7: (a,bj) є Rd/Vi L.n} (экзистенциальное огр. атрибута) - (VRdi...Rdn.D)7 = {а є Д71 Vbi...bn є A7: (a,b,) є Rd/-» b є D7 Vi=l ..п} (экзист-е огр. атрибута) - ( n Rs) = {а є Д I {b I (a,b) є Rs7} n} (минимальная мощность, аналогично n Rj) - ( n Rs) = {а є Д I {b I (a,b) є Rs7} n] (максимальная мощность, аналогично n Rj) - ({ai,..., an}) = {ai,..., an } (перечисление концепта) Определение б. Интерпретация X называется моделью терминологии % если она удовлетворяет всем высказываниям в Т. Для SHOXMV) это означает, что: - Для любой аксиомы Сі Е С2 є Тверно С/ С С27; - Для любой аксиомы Ri Е R2 є Тверно R/ С R27; - Для любой аксиомы Trans(R+) є Тверно (a,b) є R+/ л (b,c) є R+/ - (a,c) є R+/; Определение 7. Интерпретация X называется моделью множества фактов Л, если она удовлетворяет всем высказываниям в Л: - Для любой аксиомы А(а) є А верно а1 є А7; - Для любой аксиомы Р(а,Ь) є Л верно (а7,Ь;) є Р7; Определение 8. Интерпретация X называется моделью онтологии 0={% Л}, если она является моделью Ти Л.
Множество моделей онтологии О будем обозначать Л4(0), терминологии Т— Л4(Т), множества фактов Л — Л4(Л). Онтология О называется непротиворечивой, если имеет модели, то есть М(0) ф 0 (и аналогично X, Л).
Интерпретация X є M.(Q) называется моделью концепта С относительно О, если С1 Ф 0. Концепт называется непротиворечивым, если он имеет модели. Определение 9. Отношение логического следствия 1= определим в соответствии с функцией интерпретации следующим образом: - JNC(a)4»a7C7; - Jt=R(a,b)o(a7,b7) є R;; - XNCiEC2 s Ci7CC27; - JNRi ER2OR/CR/;
Индуктивно отношение логического следствия вводится для любых высказываний а (X \= а), являющихся логическими комбинациями указанных видов простых высказываний. Например, Т(= С(а) Л 3b R (а,Ь) оЛс л ЭЬ7: (а7,Ь7) є R7.
Высказывание алогически следует из онтологии О [Q\=- а), если Х\= ос VJe МІР).
Определение 10. Будем говорить, что объект а є Ca принадлежит к концепту С относительно О, если О t= С(а) (то есть, а7 є С7 VZ є Л4(0)). Будем говорить, что концепт Сі содержится в концепте С2 относительно О (Сі Е0 С2), если О 1= Сі Е С2- (то есть, Сі С Ст VX єЛ4(0)). Концепт Сі эквивалентен концепту Сч относительно О (Сі =0 С2), если Сі Е0 С2 и С2 Е0 С! (то єсть, С/ = С27 VJe Л4(0)).
Определение 11. Будем говорить, что некоторый язык дескриптивной логики принимает уникальность имен, если различные константы представляют различные сущности предметной области, то есть, не допускается эквивалентность объектов, представленных различными константами: а Ф b - а ф У.
Предположение уникальности имен, как правило, принимается в диалектах дескриптивной логики, не предоставляющих конструктора номиналов {ai,..., ап}, и не принимается, если диалект поддерживает номиналы. В SHOlMV) (OWL-DL) уникальность имен не принята.
Дескриптивная логика DLtrb
Рассмотрим вопрос поиска максимально выразительного диалекта дескриптивной логики, при использовании которого в системах интеграции данных на основе онтологии всегда существует точная переформулировка конъюнктивного запроса в реляционное исчисление.
Мы предложим диалект дескриптивной логики, обозначаемый в дальнейшем Т Шо (аббревиатура trio — от tractable integration of ontologies, т.е. диалект, допускающий интеграцию онтологии с полиномиальным временем ответа), и покажем, что этот диалект обладает указанным свойством, и что расширение его приводит к потере такого свойства.
Основное отличие предлагаемого диалекта Т ию от рассмотренного во второй главе диалекта SHOXNa ) (OWL-DL) заключается в запрете ряда конструкторов, а также ограничении формы аксиом вложения концептов.
Введем определение языка ТЭС ю, в соответствии с общей системой определений для дескриптивної! логики, рассмотренной в главе 2.
Пусть С — бесконечное множество констант, состоящее из двух непересекающихся подмножеств Сл объектов и Си значений примитивных типов данных. Пусть Nc — множество имен концептов, NRo - множество имен абстрактных ролей, NRd — множество имен атрибутов. Множество всех имен в онтологии будем также называть алфавитом N = Nc U NR0 U NRJ. Атомарной ролью будем называть Р є NR„ U NRJ, атомарным концептом А є Nc. Абстрактной ролью называется роль R0 є NRo или обратная роль R0 для любой R0 є NR0. Атрибутом называется роль Rj є NRd.
В диалекте 2?Апо мы будем рассматривать ограниченную форму аксиом вложения концептов, в этой связи вводится понятие простого концепта. Для определения простых концептов может быть использовано более ограниченное число конструкторов дескриптивной логики, чем для определения сложного концепта (синтаксическое подмножество).
Определение 34. Для языка дескриптивной логики T tno множество концептов С и множество простых концептов CL определяются согласно следующей синтаксической нотации : CL - A I 3R0 I 3 I CLI П CL2 С -» T 111 A -A С, П C2 3R0 3Rd 3Ro.C 3Rdi...Rd„.d 1 -3R0 -3Rd Здесь и далее A - атомарный концепт, C(i.n) — концепт, в том числе простой концепт, Сць.п) — простой концепт, Р(І) — атомарная роль (т.е. атомарная абстрактная роль или атрибут), Р0(І) — атомарная абстрактная роль, R(,) — роль (т.е. абстрактная роль или атрибут), R0(,) -абстрактная роль, Rd(i) — атрибут, d — допустимый примитивный тип данных. Определение 35. Терминология Т на языке дескриптивной логики А может включать следующие формы аксиом: - CL Е С, где CL - простой концепт, С - концепт (аксиома вложения концептов); - R0i Е Ro2, Rdi Е Rd2, где R j, R02- абстрактные роли, Rdi, Rd2— атрибуты (аксиомы вложения ролей); - Roi Е " Ког, R-di Е _,Rd2, где Roi, R02— абстрактные роли, Rdi, R — атрибуты (аксиомы неперекрываемости ролей); - p(Rd) Е d, где Rd - атрибут, d — допустимый примитивный тип данных, р задает множество всех значений R (аксиома типа значений атрибута ). С учетом приведенных определений, функция интерпретации для языка дескриптивной логики то вводится следующим образом.
Определение 36. Функция интерпретации для языка дескриптивной логики Т Сию определяется индуктивно согласно следующим правилам: - Р сд х Д7(каждой атомарной роли Р сопоставляется подмножество Д7 х Д7) - (а,Ь) еР « (Ь,а) є (Р )7 (обратные роли Р") - А7 С Д7 (каждому атомарному концепту сопоставляется подмножество Д7) - d7 С Д7 (каждому примитивному типу сопоставляется подмножество А7) - Т7 = А7 (верхний концепт представляет Д7) - JL = 0 (нижний концепт — пустое множество) - (--А)7 = Д7 \ А7 (дополнение А7 в А7) - (-.R) 7 = (Д7 х Д7) \ R7 (дополнение А7 в Д7) - (i3 R) = Д7 \ R7 (дополнение R7 в Д7) - (Сі П С2)7 = С/ П С27 (пересечение) - (3R0)7 = {а є Д71 ЗЬ є Д7: (а,Ь) є Rj} (простое экзистенциальное ограничение абстр. роли) - (BRd)7 = {а є Д71 ЗЬ є Д7: (а,Ь) є Rd7} (простое экзистенциальное ограничение атрибута) - (3Ro.C)7 = {а є А71 ЗЬ є С7: (а,Ь) є R0 } (экзистенциальное ограничение абстрактной роли) - (3RJI...Rdn.d)7 = {а є Д71 3bi...bn є d7: (a,b;) є Rj/Vi l ..n} (экзистенциальное огр. атрибута) - (p(Rd))/ = {b є Д71 (a,b) є Rd7} (тип значений атрибута)
Остальные определения для диалекта Т Сщ0 вводятся согласно предложенной в главе 2 системой. В диалекте Vtno не допускается конструктор номиналов {ai..an}, и принимается положение уникальности имен (см. Определение 11).
Приведенный ниже пример наглядно показывает, что предложенный диалект является весьма выразительным: Пример 6. Предположим, имеется: (1) 3 размещение на_курорте Е Курорт (2) 3 размещение на_курорте Е Размещение (3) Отель Е Размещение (4) Мотель Е Размещение (5) Кемпинг Е Размещение (6) Отель П Мотель Е -L Отель П Кемпинг Е -Ц Мотель П Кемпинг Е -L (7) 3 имеет_бассейн Е Отель (8) 3 имеет_пляж Е Размещение (9) р(имеет_бассейн) = xsd:boolean (true), р(имеет_пляж) = xsd:boolean (true) (10) 3 ресторан_при_отеле Е Ресторан (11) 3 ресторан_при_отеле Е Отель (12) 3 предлагает_развлечение Е Размещение (13) 3 предлагает_развлечение Е Развлечение (14) Купание Е Развлечение (15) ВодныеВидыСпорта Е Развлечение (16) ЛетниеВидыСпорта Е Развлечение (17) ЗимниеВидыСпорта Е Развлечение ... (18) 3 имеет_оснащение Е Отель (19) 3 имеет_оснащение Е Оснащение (20) КонференцЗал Е Оснащение (21) ДетскаяПлощадка С Оснащение (22) КонференцЗал П ДетскаяПлощадка Е -L (23) 3 имеет_категорию Е Отель (24) 3 имеет_категорию Е КатегорияОтеля (25) 5 Е КатегорияОтеля, 4 Е КатегорияОтеля, 3 Е КатегорияОтеля, 2 Е КатегорияОтеля (26) 4 + п 3 Е -L, 4 + П - 2 Е -Ц 3 + п - 2 Е 1 (27) Подразумеваем также 5 (85 ), 4 (54 ), 3 (83 ), 2 (52 ) (вместо номиналов) (28) 3 рейтинг" Е Рейтинг (29) 3 оценка Е Рейтинг (30) 3 оценка" Е РейтинговаяОценка
Переформулировка запроса относительно отображений
Проанализируем выразительные возможности рассмотренного класса систем интеграции данных на основе онтологии и покажем, каким образом такие системы интеграции данных позволяют устранить различные виды семантических конфликтов.
Ключевое преимущество систем интеграции данных на основе онтологии — это более выразительные примитивы моделирования, которые предлагается использовать для описания предметной области. Онтологии позволяют специфицировать структуру и семантику терминов системы интеграции данных и информационных источников, выразить различные формы сложных ограничений целостности в системе интеграции данных. Кроме того, весьма полезным и удобным на практике является тот факт, что онтологии позволяют выразить логические следствия.
Системы, описанные с помощью онтологии, проще интегрировать и сопоставлять, за счет того, что предметная область описана более полно, нежели это можно сделать с помощью, например, реляционных таблиц. Кроме того, при описании глобальных понятий с помощью онтологии, отображения терминов источников могут быть записаны более четко, нежели это имеет место при использовании реляционной модели данных. Даже несмотря на то, что мы ограничиваем себя рамками эффективной интеграции больших реляционных баз данных, а соответственно ограничиваем и возможности используемого диалекта дескриптивной логики (T Cttio), можно утверждать, что примитивы моделирования остаются достаточно выразительными (см., в частности, Пример 6).
Легко показать, что все распространенные виды семантических и структурных конфликтов в источниках данных, могут быть успешно урегулированы с помощью предложенных в работе методов. Мы кратко проиллюстрируем это утверждение ниже. Семантические конфликты: - Синонимы. Два понятия А и В могут иметь разное наименование, но одинаковый смысл. Урегулирование такого конфликта осуществляется отображениями в форме: А(х,у) С В(х,у), А(х) С В(х), соответственно. - Гомонимы. Два понятия могут иметь одинаковое наименование, но различный смысл. Урегулирование такого конфликта осуществляется переименованием: А"(х,у) А(х,у), А (х) С А(х), соответственно (либо в онтологиях А" Е А). - Конфликты классификации. Два понятия могут перекрываться, но не совпадать. Та кие конфликты могут быть урегулированы адекватными аксиомами в онтологиях, ко торые могут быть использованы для более точной спецификации семантики понятий, а также в некоторых случаях — отображениями, с указанием значений или условий в запросах. Здесь можно привести множество иллюстраций, в том числе демонстри рующих преимущество онтологического подхода к моделированию предметной области. Ниже несколько примеров: Журналист п Эсоздатель.Статья С Автор, Режиссер п Президент С ±, Режиссер П Эимеет_сценарий С Автор, Писатель С Автор А (а,Ь) Л Ь=1 С В (а,с) Л с 2 Структурные конфликты: - Несоответствие размерностей отношений, позиций. Например, концепт в одной он тологии и роль в другой. Приведем примеры урегулирования конфликта: 3R С С,, Ci(x) С С2(х) R(x,y) с С(х) R(x,l)cC(x) R(x,y) С Р(у,х) - Различные типы данных, различные единицы измерения, декомпозиция атрибутов. Такие конфликты могут быть урегулированы с помощью расширенных отображений, содержащих функцию преобразования переменных: ФИО(х) С Фамилия(а) Л Имя (Ь) Л Отчество (с), х=а+Ь+с длина_в_километрах (х, km) С длина_в_метрах (x,m), кт=1000 т - Несоответствие структуры данных. В некоторых случаях могут быть урегулирова ны аксиомами онтологии, например:
Журнал С Зтип.Тип_Журнал. Таким образом, предложенные в работе методы позволяют эффективно справляться с проблемами разнородности информации в источниках данных, и аксиомы онтологии играют в этом важную роль.
Задача ответа на запросы в системе интеграции данных, в том числе смежная задача ответа на запросы с использованием представлений (вариант для LAV-систем интеграции), в той или иной степени рассмотрена в литературе для различных моделей данных, включая реляционную модель данных, объектную модель данных, слабоструктурированные данные, XML, а также некоторые диалекты дескриптивной логики. При этом для разных моделей данных, разных языков запросов и разных механизмов отображения схем (спецификации представлений) для решения задачи используются существенно различные алгоритмы, и имеют место различные условия разрешимости задачи.
Наибольшее внимание рассматриваемая проблема получила в контексте реляционных баз данных, прежде всего в связи тем, что задача ответа на запросы с использованием представлений (LAV) непосредственно применима также к оптимизации запросов в реляционной СУБД с материализованными представлениями. В этом случае рассматривается возможность переформулировки исходного пользовательского запроса таким образом, чтобы снизить время его исполнения за счет использования предварительно подготовленных материализованных представлений.
Обзор основных работ, посвященных задаче ответа на запросы с использованием представлений (и переформулировки запросов с использованием представлений) в реляционной модели данных приведен в [7]. В этом обзоре рассматриваются также три алгоритма (Bucket-алгоритм, алгоритм обратных правил и алгоритм MiniCon), предназначенных для переформулировки конъюнктивных запросов (в том числе с арифметическими сравнениями) к отношениям глобальной реляционной схемы в объединение конъюнктивных запросов (UCQ) к реляционным схемам источников данных, для конъюнктивных LAV-отображений. Эти алгоритмы были разработаны для первых систем интеграции данных: Bucket-алгоритм был реализован в системе Information Manifold [12], а алгоритм обратных правил - в системе InfoMaster. Можно отметить также не попавшие в обзор алгоритмы [41, 42]. В обзоре [7] приводится также перечень работ, рассматривающих расширение стандартной реляционной задачи переформулировки запросов с использованием представлений, в частности, агрегацией в запросах или отображениях, ограничениями целостности (см. также [34, 35]), ограничениями доступа и пр. Кроме того, приводятся ссылки на результаты для других моделей данных, в том числе, для слабоструктурированных данных.
В работе [11] приводятся характеристики вычислительной сложности ответа па запросы с использованием представлений в реляционной модели данных. Рассматриваются корректные (гд С qr) и эквивалентные (гд = qr) LAV-отображения, задаваемые конъюнктивными запросами CQ (в т.ч. с неравенствами CQ ), их объединениями (UCQ), рекурсивными Datalog-запросами, или произвольными формулами реляционного исчисления. Аналогично, рассматриваются различные формы пользовательских запросов к системе. Среди основных выводов: задача в принципе неразрешима, когда запросы либо отображения представлены произвольными формулами реляционного исчисления, а также неразрешима в ряде случаев при использовании рекурсивных представлений. Кроме того, задача трудноразрешима (со-АҐР) за исключением случая корректных отображений, задаваемых конъюнктивными запросами CQ (в т.ч. CQ?), при формулировке пользовательских запросов на языках CQ, UCQ, или Datalog. Отсюда следует, в частности, что класс полиномиально разрешимых задач ответа на запросы даже в реляционных LAV-системах интеграции данных крайне ограничен.
Первая попытка рассмотреть задачу переформулировки запросов относительно LAV-системы интеграции данных в контексте дескриптивной логики была представлена в работе [14] (1997). В работе показывается, что максимальная переформулировка терминологических (задаваемых описанием концепта или ролью) запросов для дескриптивной логики ЛСМ в UCQ относительно корректных CQ-АСЛҐ отображений возможна только при наложении жестких ограничений на форму отображений (отсутствие экзистенциальных переменных), что неприемлемо на практике. Помимо этого, в [14] доказывается разрешимость более простой задачи, в которой пользовательские запросы, отображения и переформулировки задаются терминологическими запросами в дескриптивной логике ACCAf R, (то есть, описанием концепта или ролью на языке ACCNfo).
Похожие диссертации на Математическая модель интеграции данных на основе дескриптивной логики
