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

Институт Системного Программирования Российской Академии Наук

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

Новак Леонид Григорьевич

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

Специальность 05.13.11 - математическое и программное обеспечение вычислительных машин, комплексов и компьютерных сетей

АВТОРЕФЕРАТ

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

Москва-2003

Работа выполнена в Институте Системного Программирования Российской Академии Наук.

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

доктор технических наук, Кузнецов Сергей Дмитриевич.

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

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

Васенин Валерий Александрович;

кандидат технических наук, доцент

Вендров Александр Михайлович.

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

Вычислительный центр Российской Академии

Защита диссертации состоится «0^>» 2003 года в /О

часов на заседании диссертационного совета Д 002.087.01 в Институте Системного Программирования Российской Академии Наук по адресу: 109004, Москва, Большая Коммунистическая ул., д. 25.

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

Автореферат разослан « СУ2_ » Се^^ 2003

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

С.П. Прохоров

2.00 3-А

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

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

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

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

Появление языка XML, а также развитие Web привело к появлению большого количества систем виртуальной интеграции. В последнее время модель данных 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-3]

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

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

Работа состоит из введения, четырех глав, заключения и списка литературы. Общий объем диссертации 131 страница. Список литературы содержит 100 наименований. Работа содержит 30 иллюстраций.

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

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

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

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

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

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

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

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

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

Определение 1 (Тождественный запрос, заданный схемой) Пусть Q - язык запросов над моделью М, S - схема базы данных над моделью М.

Запрос б f, выраженный на языке Q , называется тождественным

запросом, заданным схемой S, если

VD, DeDB(S)=> (D)=D.

В языке запроса SQL, тождественный запрос имеет следующий вид: SELECT * from Table. В XQuery - FOR $i IN document ("doc1 .xml") RETURN $l.

Определение 2 (конструктивное отображение баз данных) Отображение множества баз данных над моделью Mi на множество баз данных над моделью Мг: ц: Г(Мт) —>Г(Мг) называется конструктивным, если:

1) ц(0)=0; база данных, состоящая из пустого множества экземпляров, отображается на пустую базу данных над другой моделью;

2) D*0=>n(D)

3) 0,002= 0=>|i(DiU D2)= H(DI)U H(D2).

Определение 3 (Конструктивное отображение языков спецификаций схем) Отображение множества схем над моделью Мь

выраженных на языке Ьь на множество схем над моделью М2, выраженных на языке Ь2: ст: Ь2 называется конструктивным, если:

1) ОВ(Б)= 0о БВ(ст(8))= 0;

2) ОВ(8,) с= ОВ(32) => ВВ(ст(8,)) сОВ(ст(52)).

Определение 4 (Согласованные отображения баз данных и схем) Пусть задано конструктивное отображение множества баз данных над моделью М1 на множество баз данных над моделью М2: ц: ЦМч) —>Г(Мг). Пусть также задано конструктивное отображение множества схем над моделью Мь выраженных на языке Ьь на множество схем над моделью М2, выраженных на языке Ь2: ст: Ь,—> Ь2. Отображение ц согласовано с отображением ст, если выполняется следующее условие:

БК^ц(0)|=ст(8).

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

Определение 5 (Система Виртуальной Интеграции) Система Виртуальной Интеграции I - это набор объектов (С,5,\Л/,Ос,Оз,М), где:

в -это глобальная схема данных над моделью вм, выраженная на языке вь

в - это набор объектов {Б|}, где Б, - это схема базы данных, содержащейся в ьм локальном источнике, над моделью , выраженная

на языке С1 ;

\Л/ - это набор объектов {\Л/-,}, где - это пара согласованных отображений {мь ст,}. ц;: Г( ) ->Г( ; ст,: С^ -> вь

Ос - это язык запросов над моделью вм!

Оэ - это набор объектов {О,}, где О-, - это язык запросов над моделью См

М — это отображение между 8 и б, составленное, как набор утверждений, ставящих в соответствие запросы к данным, удовлетворяющим глобальной схеме, и запросы к базам данных из источников. Утверждения могут принимать следующие формы: или Где - это выражение на языке запросов <30, а

Чз=Чз(01,..рп)=я'(ц1(я1(В1)),.,^1п(яп(Вп)), где , ц'- выражение на языке Ое ,и VI - выражение на языке О

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

Определение 6 (Глобальная база данных) Пусть 1=(С,3,\Л/,0з,08.М) - система виртуальной интеграции. Пусть Также -база данных ¡-го источника. Тогда база данных Ч7 над моделью вм является глобальной базой данных, соответствующей данным из источников, если:

1) Т|=С

2) V теМ дс(Ч')=Я5(01,..рп)

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

Определение 7 (Определенный результат запроса к системе виртуальной интеграции). Пусть £2(1) — множество глобальных баз данных, соответствующих данным из источников {0|}, р - произвольный запрос на языке запросов Ое над моделью вм- Тогда множество

- является определенным результатом запроса ц к системе

виртуальной интеграции I над базами данных (01,. .,0^. Множество Ри= (^д(ЧР) называется возможным результатом запроса.

"РеП (/)

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

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

запроса к XML-данным (XQuery), без использования подвыражения на языках запросов над моделями данных в источниках.

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

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

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

Определение 8 {Структурные схемы XML документов) Структурная схема XML документов есть совокупность (Т,Е,А,р,а,г), где:

• Т - множество примитивных типов данных;

• Е - множество типов элементов; тип элемента состоит из имени и условного обозначения, являющегося уникальным идентификатором типа;

• А - множество типов атрибутов. Каждый тип включает в себя:

о имя атрибута;

о тип данных;

о идентификатор обязательности (должно ли всегда задаваться значение атрибута);

о уникальный идентификатор типа атрибута;

• р есть функция из множества Е в reg({E,T}). р;Е-> reg({id(E),TJ), где id(E)- множество уникальных идентификаторов типа элемента, а reg(X)- есть регулярное выражение над множеством X

• а есть функция из множества Е в множество всех подмножеств множества А - pows(A). a: E->pows(A). Для любого типа элемента е типы атрибутов из множества а(е) должны обладать уникальным именем;

• геЕ называется типом корневого элемента. Для Множества Е должно быть соблюдено следующее условие: Ve0e Е, е фт 3 (е^е^.. en): Vi<n е,еЕ иЭ последовательность s=[ao,..,aj.1,eilaj,..an] se^щ(Е),т) (р(е|+1)), еп=г. Это условие означает «достижимость до любого элемента от корня» (5Ие(г) - множество всех порождаемых последовательностей регулярного выражения г над множеством Е (регулярное множество)).

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

Определение 9 (.Интерпретация) Интерпретация I XML документа D в терминах структурной схемы S=(T,E,A,p,a,r) - это набор отображений 1=(ф,г|,а), где

ф — это отображение Ер, -множества элементов документа, на множество Е;

т| - это отображение Aq, -множества атрибутов документа на множество А;

ст - это отображение То, - множества текстовых узлов документа на множество Т. Также должны выполняться следующие условия:

(согласование имен элементов)Пустъ name - функция, ставящая в соответствие узлу документа его имя. Тогда Vee ED: name(e)= name (ф(е));

(согласование имен и значений атрибутов)Пусть value- функция, ставящая в соответствие узлу документа его значение. Тогда VaeAo: name(a)=name(ri(a)), value(a) edom(ri(a)), где dom(x) -это домен принимаемых значений типа атрибута; (согласование текстовых узлов)УХ& Тр: value(t) ест (t); (согласование атрибутов с элементами)Пусть Ае={а,} i=[0,..,ne] -множество атрибутов элемента е. Тогда Vee Ер: Vi е [0,.., пе] Л(Э|) еа(ф(е));

(согласование обязательных атрибутов) ф*1(е8) — множество элементов документа D, которые отображаются в тип элемента es. Также пусть R(es) - это подмножество a(es), в которое входят те и только те типы атрибутов, у которых проставлен идентификатор обязательности. Тогда VeseE Vase R(es) Уееф"1(е5) Зае А,, :

Л(а)= as;

(согласование корневого элемента) Дня Го — корневого элемента документа D: ф(го)=г;

(согласование содержания элемента)Пусть Се = [ео,..,еп] — есть упорядоченная последовательность элементов и текстовых узлов, вложенных в е. Тогда У ее Е0:1(е0),.., 1(е„) |= р(ф(е)), где l(e¡) - это одно из двух отображений {ф,а} (в зависимости от типа узла).

Определение 10 (Валидность) Документ D является валидным документом для структурной схемы S {удовлетворяет схеме S), если существует интерпретация I документа D в терминах S (Обозначается D|=S).

Заметим, что далеко не всегда существует единственная интерпретация одного и того же документа. Другим характерным примером является структурная схема, для которой не существует ни один XML-документ, который ей удовлетворяет: DB(S)=0. В разделе 1.4 приводился пример такой схемы. Частным случаем такой схемы является элементарная схема (Sa)- схема, не содержащая ни одного типа атрибута, элемента и домена. Далее, мы представляем еще один тип структурных схем - тривиальные схемы.

Определение 11 (Тривиальные схемы) Структурная схема называется тривиальной, если существует и притом единственный XML документ, удовлетворяющий данной схеме.

Утверждение 1 (Существование тривиальной схемы) Для любого XML документа существует тривиальная структурная схема, которой данный документ удовлетворяет.

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

Далее, в третьем разделе, мы определяем три вида отношения на множестве схем XML и изучаем различные преобразования схем XML, сохраняющие данные отношения. Опишем все три вида отношений.

Определение 12 (Эквивалентность структурных схем) Схемы D и D' эквивалентны, если множества валидируемых XML документов каждой из этих схем совпадают.

Определение 13 (Ослабленная интерпретация) Ослабленной интерпретацией I XML документа D в терминах структурной схемы S=(T,E,A,p,a,r) называется набор отображений 1=(ф,ф,ст), удовлетворяющий всем свойствам интерпретации, кроме согласования содержания элемента. Условие согласования содержания элемента заменяется следующим:

(согласование содержания элемента) Пусть Се = [ео,..,еп] — есть упорядоченная последовательность элементов и текстовых узлов, вложенных в е. Тогда Vee ED: l(ei<(o)).--> Kek(n)) |= Р(Ф(е)). где

k(i)- есть подстановка на множестве {0,..,п}

Определение 14 ( Ослабленная Валидность) Документ D является ослабленно-валидным документом для структурной схемы S (слабо удовлетворяет схеме S), если существует ослабленная интерпретация I в терминах S (Обозначается D|«S).

Определение 15 (Слабая эквивалентность структурных схем) Схемы D и D' слабо эквивалентны, если множества слабо валидируемых XML документов каждой из этих схем совпадают.

Определение 16 (Упрощение схемы) Схемы D' является упрощением схемы D, если множество валидируемых документов первой схемы принадлежит множеству слабо-валидируемых элементов второй.

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

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

Слабо-эквивалентные - приводящие к схеме, слабо-эквивалентной иходной

Упрощающие - приводящие к схеме являющейся упрощением исходной схемы

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

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

Определение 17 (Конъюнктшно-множественные регулярные выражения) Конъюнктивно-множественные (к.-м.) регулярные выражения над множеством Е (гедкм(Е^определяются следующим образом:

1) е- к.-м. регулярное выражение, где е обозначает «пустой список»

2) Ve е Е: е- к.-м. регулярное выражение

3) Если Г! - к.-м. регулярное выражение, то (Г|), г^- к.-м. регулярные выражения

4) Если Г! и Tz- к.-м. регулярные выражения, то П, г2 - к.-м. регулярные выражения

Определение 18 (Первая нормальная форма) Схема S=(T,E,A,p,a,r) представлена в первой нормальной форме (эквивалентная форма), если: Ve е Е р(е)=г0|..|гп, где Vi n е regKM({id(E),T})

Теорема 1 (Существование первой нормальной формы) Для любой схемы S=(T,E,A,p,a,r) существует схема эквивалентная ей, которая представлена в первой нормальной форме.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

трансляция алгебраических выражений сохраняет семантику операций алгебры (iконструктивность);

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

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

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

Статическая выводимость результата. Пусть S<i,..,Sn - схемы XML, А - операция алгебры. Тогда схема S=A(S1,..,Sn) должна быть статически выводимой, то есть семантика операций такова, что получаемая схема не зависит от наборов данных, соответствующим исходным схемам.

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

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

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

Сохранение свойств тривиальности. Пусть S^ .. Sn-тривиальные схемы. Тогда для любого n-арного алгебраического выражения А схема S: S=A(S1> .. Sn) является тривиальной или элементарной. Данное свойство - свойство замкнутости на данных-позволяет воспринимать алгебру манипулирования схемами как язык манипулирования данными.

Теорема 2 (Корректность алгебры) Пусть DB(S) - множество XML-документов, удовлетворяющих схеме S. Тогда для любой алгебраической операции А и набора схем Si,..,Sn , Т,,..,Тп, таких что DB(SJc= DB(Ti) => DBfAfS^.S,,)) с DB(A(Tb..,T^).

Утверждение 2 (сохранение валидности) Пусть Х- документ XML, <р(Х) - соответствующая тривиальная схема. D - произвольная схема XML, такая что X\=D. Тогда для любой унарной операции А верно следующее: <р ~1(А(<р (X)))\~A(D), где (p ~1 (S) - документ XML, соответствующий тривиальной схеме.

Утверждение 3 (Сохранение отношения эквивалентности) Даны две структурных схемы S и S'. Тогда для любой унарной операции А верно следующее: если S и S' эквивалентны, то A(S) эквивалентно A(S').

Теорема 3 Пусть WDB(S) - множество XML-документов слабо всшидируемых схемой S. Тогда для любой алгебраической операции А и набора схем Si,..,S„ , ТЬ..,ТП, таких что l¥DB(Sj)a WDB(T) => WDB(A(Si,..,S„)) s WDB(A(Tb..,Tn)).

Утверждение 4 (Сохранение отношения слабой эквивалентности) Даны две структурных схемы S и S'. Тогда для любой унарной операции А верно следующее: если S и S' слабо эквивалентны, то A(S) слабо эквивалентно A(S').

Теорема 4 (Замкнутость 3 нормальной формы) Если схема S представлена в 3 нормальной форме, то для любой операции алгебры А, A(S') также представлена в третьей нормальной форме.

Теорема 5 (Полнота для реляционной алгебры) Существует метод трансляции реляционной модели RelToXml, инъективно отображающий реляционную базу данных на тривиальную схему, структурную схему, и для любого выражения реляционной алгебры Q, существует выражение Q' в терминах алгебры манипулирования деревьями, причем выполняется следующее условие: RelToXml (Q(D))-Q'(RelToXml (D))

Трансляция алгебры на языки запросов. Введем следующие обозначения: Q - алгебра манипулирования XML-схемами, Q - язык запроса к XML-данным. Трансляция операций алгебры D. на язык запроса Q это отображение ц:0—> Q, обладающее следующими свойствами:

1) (Коммутативная диаграмма) Пусть X - произвольный документ XML, aeCl - операция алгебры. Тогда а(ф(Х))= ср(ц(а)(Х)) (где ф(Х) - тривиальная схема соответствующая XML-документу):

2) (Гомеоморфизм) Va,ßeQ,

X

-XML-документа:

u(g)(u(ß)(X))= u(ocß)

X)

Ф

а

X

S >

i L ф

X'

Свойства трансляции сохраняются для операций алгебры с произвольной арностью.

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

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

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

Mapper с другими приложениями, ориентированными на управление схемами интегрируемых данных.

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

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

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

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

По теме диссертации опубликованы следующие работы

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

2) "Mediation system implementation based on definition of XML global views", L.Novak, www.compscipreprints.com "Efficient Virtual Data

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

Издательство ООО "МАКС Пресс". Лицензия ИД № 00510 от 01.12.99 г. Подписано к печати 01,09.2003 г. Формат 60x90 1/16. Усл.печл. 1,5. Тираж 100 экз. Заказ 576. Тел. 939-3890, 939-3891,928-1042. Тел./факс 939-3891. 119992, ГСП-2, Москва, Ленинские горы, МГУ им. М.В.Ломоносова.

£oo3-fl

i 154 1 1

Введение.

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, а также развитие 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, переводящего данные, соответствующие исходной схеме, в данные, соответствующие конечной схеме.

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.