Методы создания гетерогенного представления локальных данных в системах виртуальной интеграции на платформе XML тема диссертации и автореферата по ВАК РФ 05.13.11, кандидат физико-математических наук Новак, Леонид Григорьевич

• Новак, Леонид Григорьевич
• кандидат физико-математических наук
• 2003

Оглавление диссертации кандидат физико-математических наук Новак, Леонид Григорьевич

Введение.

1. Методы управления XML-данными и актуальные проблемы, связанные с интеграцией данных.

1.1 Язык разметки XML.

1.2 Схемы XML-данных.

1.3 Языки манипулирования XML-данными.

1.4 Технологии управления XML-данными.

1.5 Системы интеграции данных.

1.6 Формальное описание систем виртуальной интеграции данных.

1.7 Выводы.

2. Свойства схем данных XML.

2.1 Структурные ограничения XML.

2.2 Классы структурных схем.

2.3 Преобразования структурных схем.

2.4 Нормальные формы структурных схем.

2.5 Применение Нормальных форм.

2.6 Ограничения целостности XML.

2.7 Выводы.

3. Создание отображений схем XML.

3.1 Методы спецификаций отображений между схемами.

3.2 Алгебра манипулирования деревьями для модели XML-данных.

3.3 Операции алгебры манипулирования XML.

3.3.1 Вспомогательные домены.

3.3.2 Примеры схем XML.

3.3.3 Синтаксис и семантика операций алгебры.

3.3.4 Свойства операций алгебры.

3.3.5 Трансляция алгебраических выражений на XQuery.

3.4 Сопоставление структурных схем XML.

3.4.1 Сопоставление структурных схем XML «вручную».

3.4.2 Автоматическое сопоставление структурных схем XML.

3.5 Выводы.

4. Использование методов создания отображений схем XML в системе виртуальной интеграции BizQuery.—.

4.1 Архитектура системы BizQuery.

4.2 Фаза развертывания.

4.3 Спецификация отображения. BizQuery Mapper.

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

4.5 Выводы.

Введение диссертации (часть автореферата) на тему «Методы создания гетерогенного представления локальных данных в системах виртуальной интеграции на платформе XML»

Актуальность

Интеграция данных из гетерогенных источников является одним из основных направлений исследований сообщества специалистов по базам данных. Основная цель разработки систем интеграции заключается в создании средств унифицированного доступа к данным, содержащимся в источниках разного типа. Существует несколько видов платформ интеграции данных: федеративные системы, хранилища данных, с архитектурой посредников. Системы интеграции с архитектурой посредников, получившие в последнее время большое распространение, являются частным случаем более широкого класса систем -систем виртуальной интеграции данных. Основная идея подхода, используемого в системах виртуальной интеграции, заключается в создании не материализованного (виртуального) представления данных, находящихся в гетерогенных источниках. Это представление обычно определяется схемой - глобальной схемой данных. Таким образом, основная задача проектирования системы виртуальной интеграции заключается в спецификации взаимосвязи схем источников гетерогенных данных и глобальной схемы. Все запросы конечного пользователя, работающего с системой виртуальной интеграции, формулируется в терминах глобальной схемы; затем, исходя из спецификации отображения, запросы переписываются в термины локальных источников; после чего они отправляются на исполнение в локальные базы данных, а полученные ответы комбинируются.

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

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

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

Данные XML представлены в текстовом формате в соответствии со строгими правилами корректности. Это делает данные независимыми от создавшего их приложения и значительно облегчает доступ к ним.

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

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

Цели работы

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

Формальное описание структуры систем виртуальной интеграции.

- Свойства схем данных XML. Трансляция схем данных других моделей в схемы XML-данных.

- Спецификация отображения между схемами интегрируемых данных и глобальной схемой.

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

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

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

Методы

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

Научные результаты

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

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

- Разработаны два основных подхода к созданию отображений: алгебра манипулирования XML-схемами, базовые операции которой ориентированы на управление деревьями в высокоуровневых терминах, и сопоставление XML-схем; разработаны алгоритмы трансляции результатов отображения в выражения на языке запросов XQuery, которые используются в качестве фактической спецификации отображения локальных схем на глобальную схему.

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

Результаты данной работы применяются в промышленной системе виртуальной интеграции BizQuery. Разработан программный продукт, BizQuery Mapper, предназначенный для спецификации отображения гетерогенных данных, в данные, соответствующие глобальной схеме информационной системы. BizQuery Mapper позволяет задавать отображения при помощи достаточно простого графического интерфейса пользователя. Генерация запроса XQuery совершается автоматически, с использованием алгоритмов, представленных в данной работе. Отдельно стоит заметить, что концепции, предложенные в работе, могут послужить основой создания программных средств, предназначенных для создания произвольных запросов к данным с использованием графического представления схемы XML-документа (наподобие графических языков запросов).

Доклады и научные публикации

ПО ТЕМЕ ДИССЕРТАЦИИ опубликованы следующие работы:

1) "Канонические формы схем XML", Л.Г. Новак, С.Д. Кузнецов, Программирование, ном. 5, 2003

2) "Свойства схем данных XML ", Л.Г. Новак, С.Д. Кузнецов, Труды ИСП РАН, том 4,2003

3) "Mediation system implementation based on definition of XML global views", L.Novak, www.compscipreprints.com/comp/Preprint/novaklg/2003 0127/2/?coll=%2A&Selection=

4) "Efficient Virtual Data Integration Based on XML", Konstantin Antipin, Andrey Fomichev, Maxim Grinev, Sergey Kuznetsov, Leonid Novak, Peter Pleshachkov, Maria Rekouts, Denis Shiryaev, proceedings of ADBIS 2003

Основные положения работы докладывались на семинаре Московской секции АСМ SIGMOD и на семинаре «Современные сетевые технологии» под руководством д.ф.м.н. Васенина В.А. Результаты диссертации вошли в отчеты по проектам РФФИ 02-01-01088-а и 02-07-90300-в.

1. Методы управления ХМ1-данными и актуальные проблемы, связанные с интеграцией данных

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

Глава организована следующим образом. В первом разделе приводится общее описание языков разметки. Затем следует подробное рассмотрение языка XML. Обсуждаются его основные характеристики, приводится логическая структура XML-документов, а также способы применения технологии XML.

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

В третьем разделе описаны различные языки запросов к XML-данным. Особое внимание уделяется языку запросов XQuery как к наиболее популярному языку запросов к XML-данным, поддерживаемым консорциумом W3C.

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

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

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

1.1 Язык разметки XML

Всемирная паутина» (WWW) приобретает в последнее время ведущее значение как средство для передачи и распространения данных. Вследствие этого наблюдается значительный рост объема данных, представленных в формате, удобном для обмена по интернету. Наиболее распространенными языками форматирования данных являются SGML (Standard Generalized Markup Language) [IS086], HTML (Hypertext Markup Language) [RHJ99] и XML (Extensible markup language) [BPSOO]. Все эти языки являются языками разметки данных, представленных в текстовом формате. Под разметкой здесь понимается набор правил оформления текста, задающих правила обработки и семантику данных. Рассмотрим типичные виды разметки документа [BOUOO].

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

Структурная разметка. Информирует о структуре документа, а именно — о его разбиении на абзацы, параграфы и т.д.

Семантическая разметка. Этот вид разметки информирует о содержании данных. Разметка типов. Информирует о типе передаваемых данных

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

Язык SGML. Этот язык разметки был утвержден в 1986 году в качестве стандарта определения языков разметки. Фактически SGML является метаязыком для определения других языков. Это очень мощное и одновременно сложное средство, поэтому все его возможности редко используются на практике.

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

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

Отсутствие семантической разметки. HTML не несет информации о значении данных, содержащихся в элементах

Неотделимость содержания от разметки. HTML нецелесообразно использовать для обмена данными.

Язык XML, как и HTML, предназначен для описания данных, содержащихся в документе. Свое название (Расширяемый Язык Разметки) он получил по той причине, что набор тегов языка не фиксирован. Другим фундаментальным отличием от HTML является тот факт, что разметка документа является семантической. Перечислим основные достоинства языка XML.

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

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

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

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

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

- Использование готовых решений. При управлении данными, как правило, возникает необходимость решения «шаблонных» задач: верификации данных, лексического и синтаксического разбора и т.д. Переход к формату XML позволяет избежать необходимости создания своих собственных приложений для решения подобных задач.

- XML файл может быть прочитан человеком.

- XML поддерживается большим количеством стандартов. Эти стандарты предназначены для того, чтобы гарантировать совместимость приложений пользователя и готовых решений. В их число входят стандарты API для лексического и синтаксического анализа (SAX [SAX]), стандарт для управления объектной моделью документа (DOM [W3C1]) и другие стандарты, которые будут рассмотрены ниже.

Как видно из перечисленных достоинств, в XML заложен потенциал для революционных изменений в области хранения и обработки данных. xml version="1.0" encoding="ISO-8859-l" ?> <Initialization> <DividerLoeattonl>426</DividerLocationl> <DividerLocation2>400</DividerLocation2> <MainWindow width="1032" height=u748" /> <StartFile>C:\Mapper\newmap\XQDTD.xml</StartFile> <ShowLabels>true</ShowLabels> <Virtual>false</Virtual>

Plaf> com.sun.java.swing.plaf.windo ws. WindowsLookAndFeel</Plaf>

BizqueryCünn>http://vault, ispras .ru:8000/BizQuery/urn:SOAPInterfaceToBizQuery.wsdl</BizqueryConn>

BizqueryComp>true</BizqueryComp> </Initialization>

Рис 1-1 Пример XML-документа

Поскольку набор тегов XML не фиксирован, одним из основных методов применения XML является его использование как инструмента для создания своего собственного языка. Достигается эту путем ограничения набора тегов, содержащихся во входных или выходных документах, обрабатываемых приложением. Для спецификаций ограничений такого рода используются языки описания схем XML, которые будут обсуждены ниже. В настоящее время существует довольно большое количество языков, порожденных XML: MathML [IM01], CML [MR99], PML [RCG99], используемых в приложениях определенных предметных областей.

Прежде, чем перейти к описанию логической модели XML, рассмотрим пример XML-документа (рис 1.1).

Как видно из рисунка 1.1 документ XML состоит из двух частей: пролога и содержания. Содержание, в свою очередь, есть множество тегов разметки и текста. Каждому открывающему тегу соответствует закрывающий тег с тем же именем (последовательность символов после открывающейся угловой скобки до пробела или до закрывающейся угловой скобки), причем выполняются два условия, обязательные для всех XML-документов (это часть определения правильно сформированного документа):

Вложенность тегов. Если открывающий тег ai встречается по тексту раньше, чем открывающий тег Эг, то соответствующий ai закрывающий тег bi встречается по тексту позже, чем закрывающий тег Ьг, соответствующий аг. В этом случае элемент Эг (часть содержимого документа, находящегося между тегами Эг и Ьг) является вложенным для ai.

Элемент верхнего уровня. Существует такой элемент, в который вложены все остальные элементы документа( в примере на рис. 1.1 таким элементом является Initialization)

Также стоит обратить внимание на то, что в открывающих (или пустых) тегах может присутствовать непустое множество строк вида Имя ="Значение", называемое атрибутами элемента. Для атрибутов также должно выполняться условие правильного сформирования: Каждый атрибут из множества атрибутов данного элемента должен обладать уникальным именем. В примере на рис 1.1 элемент MainWindow содержит атрибуты width и height.

Теперь мы можем описать логическую структуру документа XML. XML-документ состоит из иерархического множества вложенных элементов с некоторым элементом верхнего уровня - корневым элементом. Каждый непустой элемент может быть представлен следующим образом: имя, множество атрибутов, ">", содержимое, "</", имя,">") Аналогично, пустой элемент: имя, множество атрибутов, "/>") Во множество атрибутов входят объекты следующего типа: имя атрибута, "=", множество значений)

В свою очередь "содержание" - есть упорядоченное множество, состоящее из элементов и текста- последовательности литер, не содержащих разметку. Заметим, что здесь и далее, мы не рассматриваем другие части структуры документа, такие как: инструкции по обработке, вложения, пространства имен, в силу того, что они не имеют отношение к исследованию, проделанному в настоящей работе. Правила, задающие порядок на содержании каждого элемента в совокупности формируют отношение порядка на всем множестве узлов (элементы и текст) XML-документа. Это отношение порядка называется порядком документа. Заметим, что термины «узел», «текст» и «порядок документа» более строго определены в стандарте [FMM03], который будет описан ниже.

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

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

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

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

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

1.2 Схемы XML-данных

Прежде чем перейти к описанию схем XML-данных, целесообразно более четко обозначить понятие модель данных XML. К сожалению, на данный момент не существует единой, общепринятой спецификации модели данных XML, охватывающей ее структурную составляющую. Однако, в силу того, что данное понятие явным образом используется во многих стандартах XML, его невозможно игнорировать. Существует несколько установившихся способов моделирования структуры XML-данных, используемых в тех или иных спецификациях. В их число входят описания модели данных, определенные в следующих спецификациях: Infoset [СТ01], PSVI [TBMMOO],DOM [W3Cl],XQuery 1.0 data model [FMM03]. В дальнейшем, если не будет уточняться, под моделью данных XML мы будем понимать именно модель данных XQuery 1.0 (в следующем разделе подробно описываются основные концепции данного стандарта). Заметим, что здесь сознательно рассматривается исключительно структурная составляющая модели данных XML: ограничения целостности и операционная составляющая будет обсуждаться в этом и следующем разделах.

Структура экземпляров модели данных XML близка" к структуре полуструктурированных данных [АЫ97]. Экземпляры полуструктурированной модели данных могут быть представлены в виде направленного графа с именованными ребрами. Узлы графа обозначают объекты, а ребра - связь между ними. Объекты бывают двух типов — атомарные и составные. Значение атомарного объекта принадлежит одному из базовых типов модели (строки, числа и т. д.). Значением же составного является некоторый идентификатор.

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

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

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

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

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

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

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

Document Type Definition {DTD). Язык DTD [BPS00], подъязык XML, является на данный момент наиболее простым и распространенным средством спецификации ограничений. Возможности выразительной мощности этого языка существенно ниже, чем в других языках спецификаций схем [Lau99, SAH00]. Основными компонентами спецификации DTD являются спецификации содержания элементов с данным именем и атрибутов. Рассмотрим пример DTD-схемы:

ELEMENT ELEMENT

VAVyvW/WvW-AAAlA.

ELEMENT ELEMENT

UWWWW^WVWv

ELEMENT ELE.MENTv ELEMENT ELEMENT

WAWvVt'iA/uWWÄi ELEMENT

WSW^WWi/i'y'/'iWkV»

ATTLIST

Product (Name, Developer?, Summary?,

Name (# PCDATA) >

Developer (# PCDATA) >

Summary (#PCDATA)>

Description (Para | List)+>

Para (#PCDATA | Link) *>

List (Item+) >

Item (#PCDATA | Link)*>

Link (# EMPTY )>

Link URL CDATA #REQUIRED>

Description?) >

Рис 1-2 Пример схемы DTD

Как видно из примера на рис 1.2, каждому элементу с определенным именем соответствует регулярное выражение, определенное на множестве имен элементов и спецификаторов текстового содержания (#PCDATA или #EMPTY). Кроме того, для элемента с данным именем определяется множество атрибутов. Каждому атрибуту приписывается признак обязательности его наличия в XML-документе и тип. Основные недостатки этого языка заключаются в следующем:

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

XML Schema. Язык XML Schema [ТВММ00] является более мощным, чем DTD и, следовательно, может быть использован в более широком классе XML-приложений. По сравнению с языком DTD, в него включены следующие дополнительные возможности: большое количество встроенных примитивных типов данных;

- поддержка сложных типов, определенных пользователем; механизм наследования типов (расширением и ограничением);

- абстрактные и агрегативные типы; возможность задания контекстной зависимости содержания элемента;

- механизм поддержки пространства имен [BIIL99]; поддержка ключей; представление схемы документа в формате XML .

Несмотря на большое количество возможностей, введенных в XML Schema, существует ряд недостатков, которых не удалось избежать при проектировании языка. Во-первых, было доказано [MLM01], что с точки зрения формальной теории регулярных грамматик деревьев, множество схем, выраженных в терминах XML Schema, соответствует множеству однотипных грамматик деревьев (Single-type tree grammar). В то же время, существует более широкий класс грамматик - множество регулярных грамматик деревьев (.Regular tree grammar), некоторые из которых не могут быть описаны в терминах языка. Во-вторых, в работе [Ка01] обсуждается сложность и избыточность некоторых механизмов языка, что выявляет недостатки проектирования. Однако, несмотря на перечисленные недостатки, язык XML Schema является де-факто стандартным средством спецификации ограничений, поддерживаемым консорциумом W3C.

Relax NG. Язык Relax NG [СМ01], основанный на языках спецификаций регулярных грамматик деревьев TREX [ClaOl] и RELAX [MurOOb], предназначен для описания шаблонов структуры и содержания XML-документов. Несмотря на то, что Relax NG обладает более ограниченными возможностями для создания схем XML-данных по сравнению с XML Schema, он приобретает все большую популярность. Это происходит в силу следующих обстоятельств:

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

- Выразительная мощность. Согласно исследованиям, проведенным в работах [MLM01, MLM00], множество схем, созданных на языке Relax NG, соответствует наиболее широкому классу грамматик деревьев - регулярным грамматикам деревьев.

- Поддержка. В настоящее время спецификация Relax NG успешно утверждается в качестве стандарта ISO.

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

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

Встроенные типы. Типы, предоставленные спецификацией языка. Типы, определяемые пользователем. В некоторых языках существует механизм определения собственных простых типов (XML Schema, Sox [DFH99], DSD [KMSOO])

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

Пустое значение (NULL). Поддержка специального значения, которое означает отсутствие либо незнание определенного значения (только в XML Schema).

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

Значение по умолчанию.

Выбор атрибутов. Возможность наложения дополнительных ограничений, обуславливающих включение тех или иных атрибутов в элемент (Schematron [JelOO], DSD). Например, для элемента животное с атрибутами рост и размер в холке можно поставить условие, что в элементе должен присутствовать либо один атрибут, либо другой. Опционалъность присутствия. Возможность указания обязан ли присутствовать данный атрибут в элементе или нет. Ограничения на домен.

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

Значение содержания по умолчанию.

Поддержка типов содержания. Существует четыре типа содержания элементов:

Пустое содержание. Элемент не содержит вложенных элементов и текста

Текстовое содержание. Элемент содержит только текст. Элементное содержание. Элемент содержит только данные. Смешанное содержание. Элемент содержит вложенный текст и данные

Спецификация последовательности вложения элементов. В примере на рис 1.2 содержание элемента Product описано как последовательность вложения элементов:

ELEMENT Product (Name, Developer?, Summary?, Description?)>

Спецификация необязательности существования вложенного элемента. В примере на рис 1.2 элемент Developer, вложенный в содержание элемента Product, представлен как необязательный.

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

Спецификация множественности вложения элемента. Определяет минимальное и максимальное количество экземпляров субэлемента, вложенных в элемент в допустимом документе. В примере на рис 1.2 экземпляр элемента List может содержать один или больше элементов Item.

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

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

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

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

Заключение диссертации по теме «Математическое и программное обеспечение вычислительных машин, комплексов и компьютерных сетей», Новак, Леонид Григорьевич

4.5 Выводы

В разработке представленной системы виртуальной интеграции BizQuery, основанной на модели данных XML/XQuery, использовались научные результаты, полученные в рамках настоящей работы. Реализация методов спецификации отображения в приложении BizQuery Mapper позволяет осуществлять внедрение системы интеграции с использованием различных подходов, описанных в предыдущей главе. Еще одно существенное подспорье, позволяющее эффективно и быстро совершать фазу развертывания заключается в ориентации приложения на конечного пользователя, имеющего сравнительно небольшой уровень квалификации, а именно: предоставление удобного интуитивно понятного графического интерфейса создание средств автоматического построения отображения реализация набора тестов, позволяющих произвести оценку качества отображений непосредственно на этапе разработки

Заключение

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

Приведено фундаментальное определение систем виртуальной интеграции; Разработан общий метод спецификации отображений между локальными схемами и глобальной схемой;

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

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

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

Список литературы диссертационного исследования кандидат физико-математических наук Новак, Леонид Григорьевич, 2003 год

1. К83. Калиниченко J1.A. "Методы и средства интеграции неоднородных баз данных"1. М.: Наука, 1983. 424 с

2. Ког98. М. Р. Когаловский "Абстракции и модели в системах баз данных", 1998, СУБД НОЗ] L.Novak, "Mediation system implementation based on definition of XML globalviews",www.compscipreprints.com/comp/Preprint/novakIg/20030127/2/?coll=%2A& Select ion=

3. ШОЗ. Ширяев Д.Р. "Автоматическая генерация графических пользовательскихинтерфейсов доступа к интегрированным данным на основе диаграмм классов UML", Труды ИСП РАН, том 4, 2003 НКОЗ. Л.Г. Новак, С.Д. Кузнецов, "Канонические формы схем XMU\

4. Программирование, ном. 5, 2003 НК03+. Л.Г. Новак, С.Д. Кузнецов,"Свойства схем данных XML ", Труды ИСП РАН, том 4, 2003

5. BCF03. S. Boag, D. Chamberlin, D. Florescu, J. Robie, J. Sim'eon, et al (Eds). "XQuery 1.0: An XML Query Language". W3C Working Draft, May. 2003. http://www.w3.org/TR/xquery/ BCV99] Bergamaschi, S., S. Castano, and M. Vincini:"Semantic Integration of

6. Semistructured and Structured Data Sources".SIGMOD Record 28(1), 1999, 54-59. BFR02. P. Bohannon, J. Freire, P. Roy, and J. Simeon. "From XML Schema to Relations: A

7. Cost-Based Approach to XML Storage". In IEEE ICDE, San Jose, CA, Feb. 2002 BHL 99. T. Bray, D. Hollander, and A. Layman (Eds). "Namespaces in XML". W3C

8. Recommendation, Jan. 1999. http://www.w3.org/TR/REC-xml-names/ BMW01. A. Bruggemann-Klein, M. Murata and D.Wood. "Regular tree and regular hedgelanguages over unranked alphabets", 2001, technical report HKUST-TCSC-2001-0,

9. Cat96. Rick Cattell et al. "The Object Database Standard: ODMG-93, Release 1.2". Morgan

10. DFF99. A. Deutsch, M. F. Fernandez, D. Florescu, A. Y. Levy, and D. Suciu.

11. A Query Language for XML". In Int'l World Wide Web Conf.(WWW), Toronto, Canada, May 1999.

12. STOREDIn ACM SIGMOD, Philadephia, PA, Jun. 1998. FL01. W. Fan and L. Libkin. "On XML integrity constraints in the presence of dtds". In

13. Proc. ACM PODS, 2001. FMM03. M. Fernandez, A. Malhotra, J. Marsh, et al. "XQuery 1.0 andXpath 2.0 Data Model".W3C Working Draft 02 May 2003. In http://www.w3.org/TR/xpath-datamodel/

14. FSOO. W. Fan and J. Simeon. "Integrity Constraints for XML". In ACM PODS, Dallas, TX,1. May 2000.

15. GJ79. M.R. Garey and D.S.Johnson. "Computers and Intractability", Freeman, 1979 GK02+] Grinev, M., Kuznetsov, S.: "UQL: A Query Language on Integrated Data in Terms of

16. GMT02. G.Gardarin, A. Mensch, A. Tomasic "An introducion to the e-XML Data Integration Suite", 2002

17. GPQ97. H. Garcia-Molina, Y. Papakonstantinou, D. Quass, A. Rajararnan, Y. Sagiv, J.

18. Ullman, V. Vassalos, and J. Widom, "The TSIMM1S Approach to Mediation: Data Models and Languagesin: Journal of Intelligent Information Systems, 2 (1997) 117132

19. GUW02. H. Garcia-Molina, J.D. Ullman, J. Widom "Database Systems Complete Book\2002, Prentice Hall

20. HalOl. A. Y. Halevy. "Answering queries using views: A survey".Very Large Database J.,10(4):270-294,2001. HD80. Hall, P., G. Dowling: "Approximate String MatchingComputing

21. Survey 12: 4,381-402,1980 HKM01 . S. Helmer, C.-C. Kanne, G. Moerkotte. "Isolation in XML Bases ".Technical Report,2001

22. HMR02. H. Do, S. Melnik, and E. Rahm. "Comparison of schema matching evaluations". In Proceedings of the 2nd Int. Workshop on Web Databases (German Informatics Society), 2002.

23. HMU01J Hopcroft, J.E., Motwani, R. & Ullman, J.D. " Introduction to Automata Theory,1.nguages, and Computation",2001, Addison-Wesley (2nd ed.) HVP00. H. Hosoya, J. Vouillon, and B. Pierce. "Regular expression types for XML". In Int.

24. C01. D. Lee, M. Mani, F. Chiu, and W. W. Chu., "Nesting-based Relational-to-XML

25. Schema TranslationIn Int'l Workshop on the Web and Databases (WebDB), Santa Barbara, CA, May 2001. LMC02. Dongwon Lee, Murali Mani, Frank Chiu, Wesley W. Chu, "NeT and CoT:

26. Translating Relational Schemas to XML Schemas using Semantic Constraints ",CIKM, 2002

27. MLM00. M. Mani, D. Lee, and M. Murata. "Reasoning about XML schema languages using formal language theory". Technical report, IBM Almaden Research Center, 2000. Log# 95071.

28. MLM01. M. Murata, D. Lee, and M. Mani. "Taxonomy of XML Schema Languages using

29. Formal Language Theory". In Extreme Markup Languages, Montreal, Canada, 2001. MR99. Peter Murray-Rust and Henry S. Rzepa "Chemical Markup, XML, and the Worldwide

30. PTUOO. Palopoli, L. G. Terracina, and D. Ursino: The System DIKE:Towards the SemiAutomatic Synthesis of Cooperative Information Systems and Data Warehouses. ADBIS-DASFAA 2000, Matfyzpress, 108-117.

31. PV02. Y. Papakonstantinou, V. Vassalos,"Architecture and Implementation of an XQuery-based Information Integration Platformin: Data Engineering Bulletin, March 2002

32. RB01 . E. Rahm, and P.A. Bernstein. "A Survey of Approaches to A utomatic Schema MatchingVLDB Journal 10(4):334-350. Dec. 2001

33. RCG99. Ram A., Catrambone R., Guzdial M.J., Kehoe C.M., McCrickard S., Stasko J.T.1999). "PML: Adding Flexibility to Multimedia Presentations". IEEE Multimedia, April-June 1999.

34. RJB98. James Rumbaugh, Ivar Jacobson, Grady Booch "The Unified Modeling Language Reference Manual (Addison-Wesley Object Technology Series) ",Addison-Wesley,1998

35. RHJ99J D. Raggett, A. L. Mors, and I. Jacobs (Eds). "HTML 4.01 SpecificationW3C Recommendation, Dec. 1999.http://www.w3.org/TR/html4/.

36. RLS98. J. Robie, J. Lapp, D. Schach. "XML Query Language (XQL) ". http://www.w3.org/TandS/QL/QL98/pp/xql.html

37. SAH00. A. Sahuguet "Everything you ever wanted to know about DTDs, but were afraid to askii. Proc. 3d international workshop on the web and databases (WebDB), Dallas,TX,2000

38. SAX. SAX 2.0 "Simple API for XML". In http://www.saxproject.org

39. SKR01. H. Su, H. Kuno, and E. Rundensteiner. "Automating the transformation of XML documents". In Proceedings of the Workshop on Web Information and Data Management, 2001.

40. SL90. A. Sheth and J. Larson. "Federated Databases: Architectures and Integration", ACM

41. Comput. Surv. (September 1990), 22(3): 183-236.

42. STH99. J. Shanmugasundaram, K. Tufte, G. He, C. Zhang, D. DeWitt, and J. Naughton. "Relational Databases for Querying XML Documents: Limitations and Opportunities". In VLDB, Edinburgh, Scotland, Sep. 1999

43. SYU99J T. Shimura, M. Yoshikawa, and S. Uemura. "Storage and Retrieval of XML

44. Documents using Object-Relational Databases". In Int'l Conf. on Database and Expert Systems Applications (DEXA), pp. 206-217,Florence, Italy, Aug. 1999.

45. TBMM00. H. S. Thompson, D. Beech, M. Maloney, and N.Mendelsohn (Eds). "XML Schema Part 1: Structures", W3C Recommendation, May 2001. http://www. w3. org/TR/xmlschema-1/.

46. TDC00J F. Tian, D. J. DeWitt, J. Chen, and C. Zhang. "The design and performance evaluation of alternative XML storage strategies" Technical report, CS Dept., University of Wisconsin, 2000. In www.cs.wisc.edu/niagara/papers/vldbOOXML.pdf.

47. TIH01. I. Tatarinov, Z. G. Ives, A. Y. Halevy, and D. S. Weld. "UpdatingXML". In SIGMOD Conference, 2001.

48. U1197. J. D. Ullman. "Information integration using logical views". In Proc. of the 6th Int.

49. Conf. on Database Theory (ICDT'97), volume 1186 of Lecture Notes in Computer Science, pages 19-40. Springer, 1997.

50. Wei02| F. Weigel. "A Survey of Indexing Techniques for Semistructured Documents", 2002

51. Wor02. Robert P Worden. "Eight Challenges in Data Integration", Charteris pic, 2002

52. W3C1 . W3C Recommendation. "Document Object Model (DOM) Level 3

53. Specification". In http://www.w3.Org/DOM/.2003 ZSS92. Kaizhong Zhang, Richard Statman, Dennis Shasha: "On the Editing Distance

54. Between Unordered Labeled Trees''''. Information Processing Letters 42(3): 133-139 (1992).

55. ZS90. K. Zhang and D. Shasha. "Fast algorithms for unit cost editing distance betweentrees". Journal of Algorithms, 11(6):581-621, 1990.