Содержание к диссертации
Введение
1. Методы управления XML-данными и актуальные проблемы, связанные с интеграцией данных 8
1.1 Язык разметки XML 8
1.2 Схемы XML-данных 12
1.3 Языки манипулирования XML-данными... 17
1.4 Технологии управления XML-данными 21
1.5 Системы интеграции данных 25
1.6 Формальное описание систем виртуальной интеграции данных 31
1.7 Выводы 36
2. Свойства схем данных XML 38
2.1 Структурные ограничения XML 39
2.2 Классы структурных схем 45
2.3 Преобразования структурных схем 46
2.4 Нормальные формы структурных схем 50
2.5 Применение Нормальных форм 53
2.6 Ограничения целостности XML 56
2.7 Выводы 58
3. Создание отображений схем XML 59
3.1 Методы спецификаций отображений между схемами 60
3.2 Алгебра манипулирования деревьями для модели XML-данных 63
3.3 Операции алгебры манипулирования XML 72
3.3.1 Вспомогательные домены 73
3.3.2 Примеры схем XML 74
3.3.3 Синтаксис и семантика операций алгебры 75
3.3.4 Свойства операций алгебры 92
3.3.5 Трансляция алгебраических выражений наХОиегу 94
3.4 Сопоставление структурных схем XML 103
3.4.1 Сопоставление структурных схем XML «вручную» 104
3.4.2 Автоматическое сопоставление структурных схем XML 107
3.5 Выводы 111
4. Использование методов создания отображений схем XML в системе виртуальной интеграции BizQuery . 112
4.1 Архитектура системы BizQuery 112
4.2 Фаза разверты ван ия 114
4.3 Спецификация отображения. BizQuery Mapper 116
4.4 Сравнение реализаций 121
4.5 Вы воды 124
Заключение 125
Литература 126
- Формальное описание систем виртуальной интеграции данных
- Нормальные формы структурных схем
- Алгебра манипулирования деревьями для модели XML-данных
- Спецификация отображения. BizQuery Mapper
Введение к работе
Актуальность
Интеграция данных из гетерогенных источников является одним из основных направлений исследований сообщества специалистов по базам данных. Основная цель разработки систем интеграции заключается в создании средств унифицированного доступа к данным, содержащимся в источниках разного типа. Существует несколько видов платформ интеграции данных: федеративные системы, хранилища данных, с архитектурой посредников. Системы интеграции с архитектурой посредников, получившие в последнее время большое распространение, являются частным случаем более широкого класса систем -систем виртуальной интеграции данных. Основная идея подхода, используемого в системах виртуальной интеграции, заключается в создании не материализованного (виртуального) представления данных, находящихся в гетерогенных источниках. Это представление обычно определяется схемой - глобальной схемой данных. Таким образом, основная задача проектирования системы виртуальной интеграции заключается в спецификации взаимосвязи схем источников гетерогенных данных и глобальной схемы. Все запросы конечного пользователя, работающего с системой виртуальной интеграции, формулируется в терминах глобальной схемы; затем, исходя из спецификации отображения, запросы переписываются в термины локальных источников; после чего они отправляются на исполнение в локальные базы данных, а полученные ответы комбинируются.
Еще одна проблема, с которой сталкиваются разработчики систем виртуальной интеграции, связана с тем, что данные и схемы локальных источников могут определяться в терминах различных моделей данных. В связи с этим значительно усложняется спецификация отображения схем, а также процедура выполнения запроса пользователя. Для устранения дополнительных трудностей, связанных с этой проблемой, в системах виртуальной интеграции широко используются методы трансляции моделей.
Появление языка 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-документа (наподобие графических языков запросов).
Доклады и научные публикации
ПО ТЕМЕ ДИССЕРТАЦИИ опубликованы следующие работы:
"Канонические формы схем XML", Л.Г. Новак, С.Д. Кузнецов, Программирование, ном. 5, 2003
"Свойства схем данных XML ", Л.Г. Новак, С.Д. Кузнецов, Труды ИСП РАН, том 4,2003
"Mediation system implementation based on definition of XML global views", L.Novak, 0127/2/?coll=%2A&Selection=
"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-в.
Формальное описание систем виртуальной интеграции данных
Настоящий раздел состоит из трех частей. В первой части раздела приводятся формальные определения, описывающие фундаментальные понятия, относящиеся к теории баз данных. Затем мы предлагаем метод формальной спецификации систем виртуальной интеграции. Наконец, мы приводим описание системы виртуальной интеграции BizQuery, выраженное в терминах приведенных вьпие определений и рассматриваем основные характеристики данной системы.
Определение 1.1 (Модель данных [Сос180,ЦЛ85,Ког98]) Модель данных есть совокупность трех компонентов: 1) (структурная часть) набор структурных типов, которые предназначаются для формирования наборов данных в терминах данной модели; 2) (манипуляционная часть) набор операторов или правил вывода, которые применяются к произвольным экземплярам структурных типов из первого пункта в целях получения данных; 3) (ограничения целостности) набор ограничений целостности, которые явным или неявным образом задают набор согласованных состояний баз данных или согласованных изменений состояния баз данных. Подобное определение модели данных является общепринятым в сообществе специалистов в теории баз данных. Однако в то же время, авторы стандартов XML употребляют другую трактовку модели данных, выделяя в ней исключительно структурную часть. Далее мы будем придерживаться последнего подхода, поскольку он является более естественным для XML. Определение 1.2 (Экземпляр данных) Экземпляр данных модели М есть совокупность определенных сущностей, структура которых описывается в рамках модели М. Определение 1.3 (База данных над моделью М) База данных над моделью М есть конечное множество экземпляров данных модели М. Введем следующие обозначения: DcM означает, что D - экземпляр данных модели М; Г(М) - множество всех баз данных над моделью М. Рассмотрим следующий пример. Реляционная модель RM обеспечивает способ представления данных — в виде отношениями. Тогда T(RM) - это множество всех различных конечных наборов отношений. Определение 1.4 (Сигнатура данных) Сигнатура данных есть спецификация структурных и операционных характеристик экземпляров данных. На примере реляционных баз данных сигнатура - это схема отношения (имя и конечный набор имен доменов). Определение 1.5 (Ограничения целостности данных) Ограничения целостности представляют собой набор логических выражений, предписывающих зависимости для множества экземпляров данных. Форма ограничений определяется выбором логического языка: ограничения целостности представляется логической формулой, в которой отсутствуют свободные переменные [АВ01]. Определение 1.6 (Схема базы данных над моделью) Схема базы данных над моделью М - это пара (Sig.E), где Sig - это конечное множество сигнатур экземпляров данных модели М , а Е- ограничения целостности. Языком спецификации схем (язык определения данных) называется язык, выражения которого используются для формулирования ограничений целостности и сигнатуры данных. Применительно к реляционным базам данным, схемы могут состоять из спецификации отношений (сигнатур), а также первичных, внешних ключей и других видов ограничений целостности. Мы опускаем определения термина схема данных в силу того, что он очевидно следует из предыдущего определения. Определение 1.7 (Соответствие баз данных схеме) База данных D соответствует схеме S, если экземпляры данных, входящие в D удовлетворяют спецификации сигнатуры, а также на D выполняются все ограничения целостности. Соответствие данных D схеме S обозначается так: D=S. Множество всех баз данных, соответствующих S, обозначается DB(S). DB(S) с Г(М). Определение 1.8 (Алгебра экземпляров модели) Алгебра экземпляров модели М — это набор операций, использующих экземпляры модели в качестве операндов и возвращающих экземпляры в качестве результата. Набор операций, задающий алгебру, замкнут относительно операции композиции. Алгебра экземпляров модели соответствует манипуляционной части из определения 1.1. Определение 1.9 (Язык запросов) Язык запросов модели М - это язык, выражения которого являются операциями, использующими в качестве операндов базы данных над моделью М и возвращающими в качестве результата множество экземпляров данных. Как правило, любое выражение языка запросов можно записать в виде композиции операций алгебры соответствующей модели. Определение 1.10 (Тождественный запрос, заданный схемой) Пусть Q — язык запросов над моделью М, S - схема базы данных над моделью М. Запрос Sf, выраженный на языке Q , называется тождественным запросом, заданным схемой S, если VD,DeDB(S)= Jf(D)=D. В языке запроса SQL, тождественный запрос имеет следующий вид: SELECT from Table. В XQuery- FOR $i IN document ("dod .xml") RETURN $l. Определение 1.11 (конструктивное отображение баз данных) Отображение множества баз данных над моделью Мі на множество баз данных над моделью М2: ц: Г(Мі) - Г(Мг) называется конструктивным, если: 1) (j.(0)=0; база данных, состоящая из пустого множества экземпляров, отображается на пустую базу данных над другой моделью; 2) D 0= u D) 0; 3) DM D2= 0= H(DIU D2)= H(DI)U H(D2). Определение 1.12 (Конструктивное отображение языков спецификаций схем) Отображение множества схем над моделью Мь выраженных на языке Li, на множество схем над моделью М2, выраженных на языке L2: ст: L\— L2 называется конструктивным, если: 1) DB(S)= 0 DB(a(S))= 0; 2) DB(S0 с DB(S2) = DB(CT(S0) CDB(CT(S2)). Определение 1.13 (Согласованные отображения баз данных и схем) Пусть задано конструктивное отображение множества баз данных над моделью Мі на множество баз данных над моделью М2: \і: Г(Мі) —Г(Мг). Пусть также задано конструктивное отображение множества схем над моделью Мі, выраженных на языке Li, на множество схем над моделью М2, выраженных на языке L2: ст: Li-» L2. Отображение \х согласовано с отображением с, если выполняется следующее условие:
Заметим, что три последних определения формализуют далеко не все способы отображения моделей. Более подробную информацию о методах отображения можно получить в работах [ЦЛ85, К83].
Структура систем виртуальной интеграции. Далее в данном разделе, мы представим формальное описание структуры систем виртуальной интеграции, содержащих гетерогенное представление данных, находящихся в различных источниках. Структура гетерогенного представления описывается глобальной схемой. Основная задача, возникающая при разработке системы виртуальной интеграции, заключается в формировании отображения между глобальной схемой и схемами локальных баз данных. Следующие три базовых определения приводятся в работе [Len02], однако в них внесено существенное дополнение.
Нормальные формы структурных схем
Как видно из рисунка, все узлы дерева помимо корня являются листами. Для формирования структурной схемы, необходимо выполнить следующие действия: 1) Множество Е формируется следующим образом: для каждого узла типа «элемент», мы создаем отдельный тип элемента 2) Множество А формируется следующим образом: для каждого узла типа «атрибут», мы создаем отдельный тип атрибута. Доменный тип состоит из одного значения — значения данного узла в документе 3) Множество Т формируется следующим образом: для каждого текстового узла в документе мы создаем отдельный домен, состоящий только из одного значения 4) Отображение а задается по следующим правилам: для любого типа элемента е -множество а(е) состоит из типов атрибутов, соответствующих атрибутам того XML-элемента, по которому создавался данный тип элемента. 5) Отображение р задается по следующим правилам: для любого типа элемента Є — р(е) - это выражение вида (Єо,..,еп) где Є это либо тип элемента, либо домен, задаваемый і-м дочерним узлом того элемента XML, который задавал е. 6) Тип элемента Г (корневой тип) задается корневым элементом дерева XML. Легко убедиться, что исходный документ удовлетворяет данной схеме. Также любой XML документ, удовлетворяющий данной схеме, совпадает с исходным документом. То есть схема является тривиальной.
Индуктивный переход осуществляется следующим образом. Пусть утверждение доказано для документа, максимальная глубина которого равна П. Пусть у нас есть документ XML глубины п+1. В терминах XML модели, его можно представить в виде дерева глубины п+1. Рассмотрим множество поддеревьев, с корнями в дочерних узлах корневого документа исходного дерева. Их максимальная глубина не превышает П. По предположению индукции им ставится в соответствие тривиальные схемы. Общая схема формируется путем объединения множеств Е,Т А каждой из этих тривиальных схем, создания нового типа элемента г, соответствующего корню документа, и типов атрибутов Аг, соответствующих атрибутам корневого элемента. Отображение а(г) возвращает множество типов атрибутов Аг, а р(г)=(го,..,Гп)? где Г, - идентификатор корневого типа элемента тривиальной схемы, порожденного і-м узлом. D
Способ создания тривиальной схемы, использованный в утверждении 2.2, задает инъективное отображение множества документов XML на множество схем. Этот результат будет использоваться в следующей главе работы. Легко показать, что все домены из множества Т - доменных типов тривиальной схемы содержат в точности одно значение. Сформулируем еще одно очевидное утверждение, которым мы воспользуемся в следующей главе. Лемма 2.1 (Достаточное условие тривиальности) Любая схема S=(T,E,A,p,a,r) такая, что для любого типа элементов е, регулярное выражение р(е) имеет вид Гь-Jn, где Г; есть символы базового алфавита, и все типы из множества Т содержат в точности одно значение является тривиальной или пустой схемой.П В этом разделе мы приводим классификацию структурных схем. Данный метод заимствован из работы [MLM01], где он используется для классификации грамматик деревьев. Определение 2.8 {Локальные структурные схемы) Структурная схема называется локальной, если не существует двух типов элементов с одинаковым именем. Структурная схема в примере 2.3 является локальной, в то время как схема в примере 2.4 не является таковой. Следующее утверждение верно для всех локальных схем. Утверждение 2.3 (Единственность интерпретации) Пусть S=(T,E,A,p,a,r) локальная структурная схема и XML-документ D валиден для S. Пусть также любые два типа из множества Т не пересекаются и для любого типа элемента е, мультимножество типов атрибутов из множества а(е) содержит только уникальные значения. Тогда существует и притом единственная интерпретация документа D в терминах S. Существование интерпретации следует из самой формулировки утверждения. Для доказательства единственности воспользуемся формулировкой интерпретации. Из правила согласования имён элементов, и локальности схемы следует, что в любой интерпретации каждый элемент XML-документа должен отображаться на один и тот же тип элемента, так как имена всех типов уникальны. Из того, что любые два домена не пересекаются и из свойства согласования текстовых узлов следует, что в любой интерпретации каждый текстовый узел документа XML должен отображаться на один и тот же тип узла. Таким образом, достаточно проверить, что отображение атрибутов сохраняется в любой интерпретации. Это следует из свойств согласования атрибутов с элементами, согласования имен и значений атрибутов и из того, что для любого типа элемента е, мультимножество имен типов атрибутов из множества а(е) содержит только уникальные значения. Прежде чем описать следующий класс структурных схем, приведем следующее определение, относящееся к регулярным выражениям: Определение 2.9 (Допустимые символы) Пусть Г — регулярное выражение над множеством М. Тогда Дм(г) - это множество, содержащее все элементы из М, которые присутствуют в записи регулярного выражения. Например, если Е={0(1,2}, то Ам((0 ,1 ))= {0,1} Теорема 2.2 (Критерий допустимости) Пусть г- регулярное выражение над Е. Тогда VeєЕ: єєАм(г) 3s=feo,..e,.i,e,et+],..,e,J: s\=r Доказательство очевидно. D Определение 2.10 (Однотипные структурные схемы) Структурная схема S=(T,E,A,p,a,r) называется однотипной, если для любого типа элемента е, все типы элемента из множества ДЕ(Р(Є)) обладают разными именами. Определение 2Л\(Ограничено-однотипные структурные схемы) Структурная схема S=(T,E,A,p,a,r) называется ограниченно-однотипной, если для любого типа элемента е, выполняется следующее условие: Vs1=(e0,..,en), Vs2=( е 0,..,е т), где Si\=p(e) и s2\=p(e), V\: Vj i в)- е/= пате(е,) пате(е)) Следующие два утверждения очевидны и будут приведены без доказательств. Утверждение 2.4 (Вложение типов) Любая локальная структурная схема является однотипной структурной схемой. Любая однотипная структурная схема является ограниченно-однотипной структурной схемой Утверждение 2.5 (Достаточное условие однотипности) Пусть структурная схема S T.EAp.a.r) обладает следующим свойством: VeeE: \Ам(р(е))\ =1 (Количество допустимых символов не превышает 1). Тогда S является однотипной структурной схемой. U
Утверждение 2.6 (Единственность интерпретации) Пусть S=(T,E,A,p,a,r) ограниченно-однотипная структурная схема и XML-документ D валиден для S. Пусть также любые два домена из множества Т не пересекаются и для любого типа элемента е, мультимножество имен типов атрибутов из множества а(е) содержит только уникальные значения. Тогда существует и притом единственная интерпретация документа D в терминах S.
Для доказательства этого утверждения необходимо воспользоваться свойством согласования содержания элемента.
В заключении этого раздела, заметим, что исследования, проведенные в работе [MLM01] показали, что множество структурных схем, соответствующих схемам, выраженным на языке DTD принадлежит классу локальных структурных схем. Множество структурных схем, соответствующих схемам, выраженным на языке DTD принадлежит классу однотипных структурных схем. И, наконец, множество структурных схем, соответствующих схемам, выраженным на языке Relax NG, является полным множеством структурных схем.
Алгебра манипулирования деревьями для модели XML-данных
В этом разделе мы приводим краткий обзор способов применения нормальных форм при решении типичных задач управления данными.
Валидация XML-документов. Валидация XML-документов является одним из наиболее распространенных средств для управления XML-документами. Валидация документов используется при создании XML-СУБД, обмене сообщениями, трансформации XML-документов. Одна из основных проблем при валидации документа заключается в том, что до сих пор не существует единого стандарта для XML схем: схемы могут быть выражены на языках DTD, XML Schema, Relax NG, и т. д. Однако на сегодняшний день существует ряд исследований, ориентированных на создание универсального валидатора. В этих работах схемы представляются в виде регулярных грамматик деревьев, аналогичных структурным схемам. Основная часть алгоритмов валидации - разбор списка потомков - заключается в следующем: определить удовлетворяет ли упорядоченный список потомков данного элемента его модели содержания (структурному ограничению).
Преобразование схем к первой нормальной форме, как впрочем, и применение эквивалентных преобразований имеют следующее значение для алгоритмов валидации. 1) После преобразования к 1НФ операции и + устраняются, что позволяет воспользоваться алгоритмами валидации «классических» регулярных выражений, определяемых как замыкание операций " ", "", "," над базовым алфавитом. 2) Количество конкатенации ("") становится меньше и все они становятся внешними, что сильно структурирует модель содержания. Это приводит к упрощению алгоритма разбора списка потомков. Сопоставление схем. Задача сопоставления схем заключается в поиске эквивалентных частей в разных схемах. Решение этой проблемы применяется для интеграции данных. В текущее время ведутся исследования по автоматическому поиску зависим остей [RB01]. Методы автоматического сопоставления схем можно классифицировать следующим образом [RB01]. - Поиск по схемам/поиск по данным. Алгоритмы сопоставления схем могут исследовать зависимости только в схемах или зависимости по валидным XML документам. Элементный/структурный. Поиск зависимостей может применяться либо к отдельным элементам, либо к структурам (фактически, учитываются или нет структурные ограничения) - Лингвистический/логический. Поиск зависимостей осуществляется по лингвистическому принципу (например, по именам элементов) или по семантическим ограничениям (например, по типам данным). В первую очередь, приведение схем к нормальным формам оказывает влияние на элементный лингвистический поиск. Приведение схем к ЗНФс заданным отношением порядка существенно упрощает поиск зависимостей и фактически сводит задачу к поиску изоморфных поддеревьев в деревьях с именованными узлами и с ребрами, размеченными « », «+» и «?». Подробнее способы сопоставления схем будут описаны в следующей главе. Трансляция модели данных. Как уже отмечалось выше, одна из основных задач, встречающихся при создании систем виртуальной интеграции, заключается в трансляции моделей, в терминах которой определяются данные из источников, в термины «единой» модели данных. Еще одна причина использования трансляции модели заключается в том, что несмотря на то, что модель данных XML и языки запросов, основанные на ней, завоёвывают в последнее время всё большую популярность, потребность хранения XML-данных в «традиционных» СУБД до сих пор остаётся. Обосновано это тем, что многолетний опыт, накопленный при изучении и реализациях реляционных и объектно-ориентированных СУБД невозможно игнорировать. XML- Relational Одним из основных направлений исследования методов трансляции моделей является трансляция XML-модели данных в реляционную[8ТН99,МЕ02]. Отличительными особенностями реляционной модели данных являются: отсутствие упорядоченности кортежей и атрибутов; трехуровневая модель (отношение-кортеж- атрибут), в отличие от произвольной глубины XML-схем; отсутствие атрибутов, имеющих своим значением множество; отсутствие рекурсии. Существует различные методы автоматического представления XML-документов в реляционных СУБД. - Хранение XML- данных в BLOB. Модельно-ориентированная трансляция. Данный вид трансляции не зависит от структурных ограничений, определенных в схеме схемы, а целиком опирается на свойства модели данных XML [SYU99].
Трансляция, ориентированная на данные. Данные алгоритмы трансляции оперируют с XML-данными, не представленными никакой схемой [DFS98]. На начальном этапе трансляции производится вывод схемы, представляющей XML-данные. Трансляция с оценкой эффективности. Алгоритм трансляции, представленный в работе [BFR02], анализирует способ трансляции XML-данных таким образом, чтобы запросы, предопределенные приложением, выполнялись наиболее эффективно.
Структурно-ориентированная трансляция. Эта трансляция опирается на информацию, полученную из XML-схемы. В алгоритмах этого типа [STH99,ML02] используются структурные ограничения, явно присутствующие в схеме, а также выводятся неявные ограничения, исследуемые в процессе анализа схемы. Проведенные исследования [STH99,ML02], касающиеся проблемы структурно-ориентированной трансляции из XML в реляционную модель выявили ряд возникающих трудностей и показали методы решения:
1) Наличие конкатенации в модели содержания. Например, пусть у нас есть определение модели содержания элемента !ELEMENT г (аЬ) . Переводя в реляционную модель, наиболее близким отображением будет таблица г с двумя полями: а и Ь. Однако эта схема не будет отражать тот факт, что в элементе г может встретиться либо а либо Ь. Поэтому необходимо добавить семантическое ограничение: «если значение в поле а непустое, то значение в поле b должно быть пустым и наоборот». Если есть вложенные конкатенации (то есть конкатенации не на самом верхнем уровне регулярного выражения), мы должны использовать 1НФ для вынесения конкатенации на самый верхний уровень.
2) Наличие оператора Клини ( ). Если в модели содержания какого-то узла встречается другой элемент с оператором ( !ELEMENT г а ), то в этом случае для элемента придется создавать отдельное отношение. Если же структура содержит вложенные операторы ( !ELEMENT г (а ,Ь) ), то количество отношений существенно увеличится. Обычно для решения этой проблемы используются преобразования схем аналогичных ЗНФ (упрощение схемы).
Однако, на наш взгляд, правильнее использовать 2 НФ для представления схемы XML: Во первых, 2НФ оставляет практически всю семантику схемы Во вторых, семантика порядка, которая теряется во 2НФ, не оказывает никакого влияния на трансляцию в реляционную модель, вследствие отсутствия семантики порядка в реляционной модели. XML- Semistructured
Другим направлением трансляции XML является трансляция в полуструктурированные и объектно-ориентированные модели. Существенное отличие этих моделей от реляционной заключается в том что, данные представляются в виде ориентированного графа с именованными узлами. Последнее свойство, как правило, снимает необходимость использования 2НФ и ЗНФ. Поэтому, в общем случае транслируется схема, приведенная к 1НФ или непосредственно исходная схема.
Спецификация отображения. BizQuery Mapper
В этом разделе мы подробно опишем различные способы спецификации отображения между локальными схемами и глобальной схемой в терминах языка запроса к данным, представленным в терминах определенной модели. Заметим что, несмотря на то, что исследования, проводимые в последующих разделах, в целом касаются модели данных XML и языка запросов XQuery, предлагаемые методы имеют общий характер и применимы в системах виртуальной интеграции и системах обмена данными, созданных на базе любой «древовидной» модели данных и языков запросов.
Один из наиболее принципиальных вопросов, с которым сталкиваются разработчики систем виртуальной интеграции, состоит в том, существует ли фиксированная глобальная схема до того момента, когда происходит спецификация отображения или же наоборот, глобальная схема выводится исходя из манипуляций, проделываемых с локальными схемами. В англоязычной литературе первый, обратный, подход принято называть reverse engineering, а второй, прямой, global engineering. Для реализации этих подходов используется совершенно разные технологии, о которых уже упоминалось выше: сопоставление схем и определение представления. Рассмотрим подробнее каждый из этих способов создания отображения.
Определение представления. Задача определения представления над локальными источниками заключается в составлении запроса к данным из локаїьньгх источников и получении схемы данных, описывающей результат применения запроса к полученным данным. Как видно из описания, этот способ задания отображения более характерен для прямого подхода: структурные характеристики глобальной схемы, даже если она задана, не учитываются при формировании запроса к исходным данным. Однако использование дополнительных средств, таких как верификация схемы представления, которые будут описаны далее, позволяет учитывать свойства глобальной схемы для составления запроса таким образом, чтобы получаемая схема представления соответствовала глобальной схеме. Рассмотрим основные технологические способы определения представления.
Написание запросов вручную. Пользователю предоставляется возможность написания выражения на языке запросов, поддерживаемого системой, вручную. У такого способа определения представления существует масса недостатков: сложность составления запросов к данным из большого количества источников; вероятность появления ошибок в запросах и т. д. При использовании языка XQuery появляются дополнительные сложности для написания запросов вручную, связанные с относительной сложностью самого языка. Во-первых, существуют такие запросы, для которых схема получаемых данных статически не выводима или может меняться при изменении данных в источниках. Во-вторых, согласно замечанию из раздела 1.4, достаточно нетривиально сформулировать многие запросы, характерные для управления гетерогенными данными, в силу того, что операции алгебры XQuery определяются в терминах узлов и их последовательностей. Вследствие этих и других недостатков, использование такого способа определения представлений, по нашему мнению является нецелесообразным.
Определение представления в терминах высокоуровневой алгебры. Использование вспомогательных средств для написания запросов очень часто применяется на практике. Сюда включены такие способы, как графические языки запросов, наборы запросов-шаблонов и т. д. После того, как пользователь формулирует представление при помощи высокоуровневых средств, производится автоматическая трансляция в термины языка запросов.
Для создания представления на языке XQuery над моделью XML, нами была разработана алгебра манипулирования структурами, представленными в виде деревьев [ПОЗ]. С одной стороны, в силу того, что как XML-документ, так и его структурная схема может быть представлена в виде дерева (см. глава 2), использование алгебры такого рода оправдано. С другой стороны, наличие таких высокоуровневых операций, характерных для управления наборами данных, как проекция, выборка, соединение, и т.д., значительно упрощает процедуру написания представления. Более подробное описание преимуществ алгебр манипулирования деревьями перед алгебрами управления узлами деревьев можно получить в работах [JKC02, JLS01]. Каждая операция алгебры - есть отображение из декартова произведения множества схем на само множество схем. Над алгеброй манипулирования деревьями введена операция композиции, обладающая свойством замкнутости. Отсюда следует, что композиция произвольных операций алгебры манипулирования деревьями, сама является операцией манипулирования деревьями (свойство композитивности). Другое важное свойство операций алгебры заключается в следующем: схема результата применения операции алгебры к любому набору данных, определяемых исходной схемой статически выводима (свойство выводимости). Из композитивности и выводимости следует, что новое представление может определяться, как на исходных схемах, так и на промежуточных представлениях, что упрощает создание больших представлений. Эти и другие свойства алгебры манипулирования деревьями, а также, образующие алгебры и алгоритмы трансляции на язык XQuery будут рассмотрены в следующих разделах.
Несмотря на то, что определение представления в терминах высокоуровневой алгебры является очень удобным средством для спецификации запроса, остаются вопросы каким образом использовать при обратном подходе проектирования системы. Для того чтобы пользователь мог создавать представления, схемы которых согласованы с глобальной схемой данных, используются следующие технологии.
Определение представления в терминах высокоуровневой алгебры с верификацией. После того как задано представление с использованием высокоуровневых средств, мы получаем его схему. Для того чтобы определить, совпадает ли полученная схема с глобальной, используются алгоритмы верификации. Алгоритмы верификации позволяют определить отличаются ли две схемы, и если отличаются, то каким образом. Пользователь может на основании этого анализа переформулировать представление таким образом, чтобы его схема не отличалась от глобальной схемы.
При использовании структурной схемы XML как языка спецификации схем процедура верификации схем имеет много разновидностей. Например, мы можем проверять схемы на эквивалентность после приведения их к ЗНФ или вообще не учитывать операции
Полуавтоматическое определение представления в терминах высокоуровневой алгебры. Технология полуавтоматического определения представления заключается в том, что создается набор кандидатских выражений в терминах алгебры таких, что схема результата относительно близка к глобальной схеме. После чего пользователь выбирает наиболее приемлемый запрос, редактирует его и получает нужное отображение. Алгоритмы, создающие эти запросы, должны учитывать семантические связи между локальными схемами и глобальной схемой, а также эквивалентные части локальных схем. Для выполнения такого рода задач, как правило, требуется анализ данных источников, а также использование методов сопоставления схем. К сожалению, на данный момент, практически не существует исследовательских работ и программных продуктов с применением этой технологии.
