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

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

АХУНОВ Алексей Ножипович

ИНТЕГРАЦИЯ ИНФОРМАЦИИ В РЕЛЯЦИОННЫХ БАЗАХ ДАННЫХ НА ОСНОВЕ ВИРТУАЛЬНОГО РЕПОЗИТОРИЯ

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

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

Уфа - 2004

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

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

профессор Юсупова Нафиса Исламовна

Официальные оппоненты: доктор технических наук,

профессор Буренин Владимир Алексеевич

Ведущее предприятие - Республиканский Научно-Технологический

Информационный Комплекс «Баштехинформ»

Защита состоится 21 декабря 2004 года в часов на заседании диссертационного совета К-212.288.01 Уфимского государственного авиационного технического университета по адресу: 450000, Уфа-центр, ул. К.Маркса, 12, УГАТУ.

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

Автореферат разослан 19 ноября 2004 г.

Ученый секретарь

диссертационного совета

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

доктор физико-математических наук, профессор Асадуллин Рамиль Мидхатович

доцент

Р. А. Гараев

гооб>-4

20Т5"

шччьъ

ОБ1ЦАЯ ХАРАКТЕРИСТИКА РАБОТЫ

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

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

Интеграция информационных сред и их модернизация должны отвечать и другому важному требованию, а именно, поддерживать так называемые "унаследованные" системы (legacy systems). Этим термином обозначают системы, базирующиеся на морально устаревших технологиях, но имеющие в силу исторических причин критическое значение для существования предприятия или организации.

Роль XML (extensible Markup Language - расширяемый язык разметки) как универсального формата обмена данными и гибкой технологической платформы широко признана. Разнообразные исследовательские проекты в INRIA, AT&T Labs, IBM Almaden и университета Висконсина посвящены проблеме отображения XML на реляционные базы данных. Сегодня все ведущие системы управления реляционными базами данных построены на базе результатов этих исследований и обеспечивают экспорт данных в формате XML в той или иной степени. Однако, большинство из них направлены на создание базы данных «с чистого листа» и не приюдны для реинжиниринга «унаследованных» сис1ем. Многие исследователи сходятся во мнении, что реляционные базы данных в общем не являются идеальными для хранения XML, однако в случае, когда XML данные берут свое начало в реляционной базе данных и не требуется эффективного механизма записи, такой способ хранения может оказаться наиболее приемлемым выбором.

Вопросами интеграции информации в реляционных базах данных на основе XML технологий активно занимаются различные научные коллективы у нас в стране и за рубежом (Мельников A.B., Миронов В.В., Когаповский М.Р., М. Fernandez, D. Florescu, J. Shanmagasundaram, I. Tatarinov, D. Suciu). Однако большинство решений в этой области носит преимущественно эвристический характер.

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

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

- разработка общей архитектуры виртуальных репозиториев на базе открытых стандартов;

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

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

- разработка модели иерархических документов в реляционной системе;

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

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

Результаты, выносимые на защиту:

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

• модели представления иерархических документов вложенной последовательностью кортежей;

• эквивалентные вложенным последовательностям модели представления иерархических документов последовательностью путевых проекций;

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

- метод предотвращения аномалий обновления путем учета семантических ограничений;

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

Научная новизна. Новыми являются следующие разработки и исследования автора:

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

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

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

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

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

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

- основанные на модели путевых проекций алгоритмы построения запросов на языке SQL для публикации документов XML из реляционных баз данных;

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

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

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

) Предложенные модели и методы внедрены в отделе информационных технологий Государственного ведомства водных путей Германии в качестве опытного 1 программного обеспечения в совокупности с методикой использования. Ре? .¡ультаты работы использованы в ряде проектов Исследовательского Центра Информатики города Карлсруэ (Германия) связанных с интеграцией информации в геоинформационных системах, и информационных системах для защиты окружающей среды.

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

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

Исследования проводились в рамках федеральной целевой программы «Интеграция науки и высшего образования Российской Федерации на 2002-2006 гг.» по проекту «Фундаментальные исследования и новые технологии проектирования сложных технических систем» и частично поддержаны грантом РФФИ 03-

07-90242 «Интернет-комплекс поддержки выполнения проектов фундаментальных исследований сложных систем с применением интеллектуальных технологий на базе экспертных систем» (2003-2005 гг.)

Разработанное автором программное обеспечение зарегистрировано в Отраслевом фонде алгоритмов и программ Государственного координационного центра.

Апробация работы. Основные положения и результаты работы докладывались на следующих научно-технических конференциях: й международной конференции по проблемам технологий для электронных сервисов VLDB TES'2002 (23-24 августа 2002 г., Гонконг, Китай); 4-й Международной конференции по проблемам информатики и информационных технологий CSIT2002 (18-20 сентября 2002 г., Патры, Греция); 5-й Международной конференции по проблемам информатики и информационных технологий CSIT'2003 (16-18 сентября 2003 г., Уфа, Россия); 14-й Международной конференции «Информатика в защите окружающей среды» Envirolnfo'2003 (24-26 сентября 2003 г., Коттбус, Германия).

Публикации.

Основные материалы диссертационной работы опубликованы в 12 научных трудах, в том числе в виде научных статей в 3-х международных и 2-х российских научных изданиях.

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

ОСНОВНОЕ СОДЕРЖАНИЕ РАБОТЫ

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

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

К основным подходам к интеграции информации можно о гнести федеративные базы данных, хранилища данных и медиаторы. Архитектура этих подходов схематично показана на рис. 1.

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

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

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

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

••j ^ ^ -g

c.jEâ--~ -isr—c^l

Федеративные базы Хранилище данных Медиатор и оболочки данных

Рисунок 1. Подходы к интеграции информации

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

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

с

<ÇL->ml

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

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

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

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

Таблица 1. Разработки, связанные с построением XML-преставлений

поддержка унаследованных систем переносимость между СУБД

извлечение информации обновление информации

eXist, Sleepy Cat нет (схема БД формируется из схемы XML) нет (схема БД формируется из схемы XML) есть(работа с множеством СУБД)

Microsoft SQLXML отображение в соответствии со схемой XML, аннотированной переменными отношений (ограниченный подход, могут потребоваться дополнительные преобразования) команды обновления (ир-dategrams), работающие для переменных отношений (ограниченный подход, могут потребоваться триггеры типа INSTEAD) нет(работа только с продуктами Microsoft SQL Server и Microsoft IIS)

Oracle XMLDB есть (отображение в соот-вествии со схемой XML, аннотированной типами и запросом SQL, получающим данные этих типов) ограниченный подход - только для несложных отображений, в общем случае - триггеры типа INSTEAD нет(работа только с СУБД Oracle)

XTABLES (XQuery) есть (язык XQuery достаточно мощный и гибкий для создания произвольных отображений) нет (используемый язык XQuery не предназначен для обновляемых представлений) есть(работа с множеством СУБД)

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

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

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

Функциональные требования целесообразно разделить на уровни, которые принято называть уровнями соответствия (рис. 2). Первые два уровня соответствия заимствованы из спецификации инициативы XML:DB. Первый уровень был разбит на два подуровня (1а и 16) в связи с виртуальным характером репозитория. Следующие уровни являются экстраполяцией первых двух с учетом других функций, описанных в той же спецификации.

Модуль обнаружения аномалий

Содержимое для*

записи в БД

Запрос уровня 1а извлечение ресурса из коллекции

Запросы уровня 16 создание и удаление ресурса внутри коллекции

Настраиваемая оболочка

Конфигурация

Запросы 1-го уровня создание и удаление» коллекции

Менеджер коллекций

Схема

-4

Обработчик схем - | генератор оболочек

Запрос 2-го уровня XPath

Преобразователь запросов

Запрос 3-го уровня частичное обновление

Схема результата 4 запроса

Сужающий

запрос

Преобразователь схем

ё ге ■а X х S о i а>

Место обнофюния

Диспетчер обновлений

.Журнальная запись

Запросы 4-го уровня начало. Фиксация и откат транзакции

Менеджер транзакций

Рисунок 2. Архитектура виртуального репозитория

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

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

Для трех главных функций виртуального репозитория, соответствующих двум подуровням первого уровня соответствия и второму уровню, а именно: чтение ресурсов, запись ресурсов и работа с частями ресурсов (выборка и частичное обновление), предлагаются методы реализации. Все эти методы используют схему XML, аннотированную командами и запросами языка SQL. На рис. 3 показана синтаксическая диаграмма схемы XML, в которой аннотирован корневой элемент record вместе с несколькими дочерними элементами и агри-бутами (аннотации показаны прямоугольниками с текстом).

@\d — -xs integer ¡"KeywoidlD | -<title> — xs string гИ1е

-<temporalCoverage> — — @start--xs date

—@end--xs date

<spat>alCoverage> - - @west— -@east _ jj north— -©south - -xsfloari

___ <record>

I SELECT ID KeywordlD.Title StartDate, Ena Date. WestBL. EastBL, SouthBL. NorthBL FROM Record

INSERT INTO Record [ID. Title. StartDate, EndDate WestBL. EastBL. South BL NorthBL) VALUES (@td. title. iemporalCoverage/@start, tempofalCoverage/@end > spatialCoverage/@west spotralCoverage/@east spatiQiCoverage/@north. spatKjlCoveroge/@south)

-<keyword> -<workflow>

-xs string -

<date> <stage>

StartDate | EndDate -xs floatrvfeitBLl -xs float! EcbtBl! ~xs float[ÄBL]

; SouthBL I — —xs integer -xs date

-xs string"--"creation"

—"publication" —"revision"

Рисунок 3. Синтаксическая диаграмма схемы XML, аннотированной командами и запросами SQL

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

Для записи ресурсов предлагается использовать аннотации в виде команд SQL (таких как INSERT, UPDATE, DELETE), внутри которых разрешены выражения XPath, позволяющие ссылаться на части обновляемого документа. Такой подход к обновлению информации позволяет исключить необходимость вмешательства в реляционную систему (такие как, например, написание триггеров). Для предотвращения аномалий обновления предлагается использовать не традиционный метод нормализации, а метод учета семантических ограничений. Ненормализованные документы XML, содержащие повторяющиеся поддеревья (избыточность), допустимо рассматривать как древовидные развертки сетевых структур. Можно условиться, что информация в виртуальном репозитории хранится в виде сети, и каждый раз, когда происходит ее отправка пользователю, сеть разворачивается в дерево. Для того чтобы правильно сворачивать деревья в сеть перед записью информации в базу данных, нужно уметь идентифицировать тождественные узлы. Предлагается брать за основу ограничения целостности, существующие в реляционной базе данных, и производить вывод семантических ограничений для узлов виртуальных документов. В отличие от нормализации, которая сопровождается декомпозицией отношений и документов, предлагаемый метод учета семантических ограничений направлен на сохранение иерархической структуры документов, которая является естественной для XML.

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

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

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

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

Сценарий реинжиниринга унаследованной системы включает в себя следующие этапы анализ старой системы (AS IS) и требований к новой (ТО ВЕ), построение общей схемы медиатора в соответствии с требованиями к новой системе, проектирование и инсталляция системы «ТО ВЕ», создание оболочек для чтения данных из старой и новой систем и оболочки для записи в новую систему Описания оболочек в виде аннотированных схем регистрируются в соотвествуюших коллекциях, являющихся дочерними по отношению к коллекции с общей схемой. Теперь доступны для чтения данные как из старой, так и из новой системы (в силу наличия обеих оболочек), однако при записи данные поступают только в новую систему. При этом довольно просто может быть произведена процедура импорта: следует прочитать ресурсы из коллекции, соответствующей старой системе (а не родительской) и записать их в коллекцию новой системы

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

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

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

2. Кортежи в отношениях не упорядочены по определению. Элементы в документе XML связаны локальным порядком и порядком просмотра документа.

3. Рекурсивные схемы XML являются вполне естественными и допускают неограниченную степень вложенности элементов. Такую вложенность несложно моделировать и «плоскими» отношениями, однако запросы на таких структурах зачастую далеко не тривиальны.

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

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

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

(А,В,С,1),Е) 6)

I I

(F,G,H) (I,J)

А В С D Е __F G Н I J

¡1 ~' ~f~i |i i

А В

R

D А Е F

1 ' * i

3

4

Q

ABC I--G

D Е F

l

3 —г ----_j

4 j

Rixi Q

Рисунок 4. Вложенное отношение и вкладывающее соединение

В работе доказывается, что введенная операция вкладывающего соединения обладает двумя полезными свойствами Так, если г, д п р - вложенные отношения на схемах Я, <2 и Р соответственно, а и Ь - атрибутные пути в схеме Я, то при выполнении нескольких других условий имеет место свойство ассоциативности:

(г>°<д)>ю°<р = г>°4(д>1'<1 р)

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

(г>°<д)>ь< р = (г>ь<I р) >°<д

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

Следующим шагом в улучшении моделей является поддержка произвольных (в том числе рекурсивных) схем. Предлагается заменить древовидную схему более общей схемой, основанной на произвольном конечном ориентированном графе с вершиной, из которой достижимы все остальные. Это обобщение приводит к появлению неофаниченных по длине путей. Кроме того, множество путей для конечной схемы произвольного вида может оказаться бесконечным, если в соответствующем графе присутствуют циклы. Атрибутные пути больше не могут однозначно идентифицировать пути в схеме. Восстановимость схемы основывается на знании множества путей и соотвествующих атрибутных путей. Основываясь на том наблюдении, что множество путей схемы является регулярным языком, задача восстановимости схемы по множеству путей сводится к задаче распознавания регулярной грамматики по конечному множеству предложений ее языка. Грамматика задается четверкой 0(5') = (£,£/,,где 5 -корневая схема, выступающая в качестве стартового нетерминала, и - множество всех возможных имен атрибутов (множество терминальных символов), иг-множество всевозможных имен схем (нетерминальных символов), Р- множество продукций, которое формируется следующим образом:

Здесь а1,...а> е и обозначают простые атрибуты, а хр еи- сложные атрибуты схемы. Сложные атрибуты схем выступают в качестве терминальных символов и участвуют в продукциях.

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

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

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

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

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

серий тестов, каждая из которых включала документы одинаковой сложности (в смысле их структуры). Использовалось два критерия сложности схемы документов, названных шириной и глубиной схемы. Говоря неформально, глубина - это максимальная степень вложенности элементов, а ширина -количество атрибутов и дочерних элементов внутри каждого элемента. Для каждой серии были сгенерированы тесты различного размера, которые были подобраны так, что максимальный размер тестового документа в текстовом формате был приблизительно равен 50 Мб.

Таблица 2. Сравнение средней скорость обработки информации и ее динамики для продукта вОЬХМЬ и исследовательского прототипа

Глубина Ширина Средняя ско- Падение скорости Падение скоро-

схемы схемы рость обработки при увеличении сти при увеличе-

(Кб/сек) глубины (%) нии ширины (%)

SQL- Прото- SQL- Прото- SQL- Прото-

XML тип XML Тип XML Тип

3 2 281 124

3 3 269 120 4 3

3 4 191 104 29 13

3 5 108 90 43 13

3 6 54 78 50 13

3 7 29 61 46 22

4 2 186 97 34 22

4 3 49 74 82 39 74 24

4 4 32 42 83 60 35 43

5 2 96 69 48 29

6 2 22 42 77 39

Результаты эксперимента, часть которых можно видеть в табл. 2, показывают, что исследовательский прототип показывает более низкую, нежели SQLXML, производительность на тестовых документах с простой структурой. Это происходит главным образом из-за высоких накладных расходов платформы (XSLT на базе Java), на основе которой реализован прототип. Несмотря на это, прототип выигрывает в производительности на тестовых документах с более сложными схемами. Причиной являются специальные приемы повышения эффективности публикации документов XML из отношений, такие как повторное использование атрибутов и предварительное вычисление соединений. Первый прием основан на том наблюдении, что выражения SQL для получения путевых проекций содержат очень много NULL значений. Повторное использование атрибутов позволяет сократить такие выражения, избавляя от большинства пустых значений в результате. Второй прием состоит в исключении повторного вычисления

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

Исследовательский протип был исиользован в проекте Исследовательского центра информатики города Карлсруэ для Государственного ведомства водных путей Германии в качестве опытного программного обеспечения для интеграции реляционных баз данных в Береговую информационную систему северного моря (NOKIS).

ОСНОВНЫЕ ВЫВОДЫ И РЕЗУЛЬТАТЫ РАБОТЫ

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

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

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

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

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

1. Ахунов А.Н., Валиков А.Н. Визуализация географических карт на основе масштабируемых пространственных запросов // Принятие решений в условиях неопределенности: Сб. науч. тр. - Уфа: УГАТУ, 2002. С.298-308

2. Ахунов А.Н., Валиков А.Н. Интеграция информационных систем с базами данных посредством XML (на англ.) // 4-я Международная конференция по проблемам информатики и информационных технологий. CSIT2002.-Патрас, Греция, 2002.-С.25.

3. Ахунов А.Н., Валиков А.Н., Казакос В. Удаленный вызов методов для веб-приложений (на англ.) // 4-я Международная конференция по проблемам

информатики и информационных технологий. С81Т'2002.-Патрас, Греция, 2002.-С.65.

4. Валиков А.Н., Ахунов А.Н., Шмидт А. Архитектура модель-преобразования для веб-приложений (на англ.) // 3-я Международная конференция по проблемам технологий для электронных сервисов. VLDB TES'2002.-C.29-37.

5. Ахунов А.Н., Валиков А.Н. Методика декомпозиции систем в рамках компонентно-ориентированной архитектуры (на англ.) // 5-я Международная конференция по проблемам информатики и информационных технологий CSIT2003. Уфа, УГАТУ, 2003.-Т.-1.-С.29-37

6. Валиков А.Н., Ахунов А.Н. Программа для ЭВМ: Библиотека Web -Models. // Код программы по ЕСПД .03524577.00457-01 ОФАП, 2003.

7. Валиков А.Н., Ахунов А.Н. Программа для ЭВМ: Библиотека xml.transform. // Код программы по ЕСПД .03524577.00458-01 ОФАП, 2003.

8. Валиков А.Н., Ахунов А.Н. Программа для ЭВМ: Библиотека Web -Actions. И Код программы по ЕСПД .03524577.00456-01 ОФАП, 2003.

9. Казакос В., Ахунов А.Н., Паоли X., Беренс С., Низинг X., Ломбардо С. Редактирование данных, соответствующих IS019115 в проекте Eurosion (на англ.) // 17-я Международная конференция: Информатика в защите окружающей среды.-Envirolnfo'2003. Котбус, Германия, 2003.-С.248-254.

10.Валиков А.Н., Ахунов А.Н. Программа для ЭВМ: Библиотека InfoZip. // Код программы по ЕСПД .03524577.00497-01 ОФАП, 2004.

11.Ахунов А.Н., Юсупова Н.И., Валиков А.Н. Путевые проекции для моделировании XML в отношениях (на англ.) // 6-я Международная конференция по проблемам информатики и информационных технологий. CSIT2004.-Будапешт, Венгрия, 2004.-С.145-148.

12.Ахунов А.Н., Юсупова Н.И. Предотвращение аномалий обновления путем учета семантических ограничений. // Принятие решений в условиях неопределенности. Вопросы моделирования: Межвуз.науч.сб., Уфа: УГАТУ, 2004. -С.26-33.

Ахунов Алексей Ножипович

ИНТЕГРАЦИЯ ИНФОРМАЦИИ В РЕЛЯЦИОННЫХ БАЗАХ ДАННЫХ НА ОСНОВЕ ВИРТУАЛЬНОГО РЕПОЗИТОРИЯ

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

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

Подписано в печать 17.11.2004 Формат 60x84 1/16 Бумага писчая №1. Печать плоская. Гарнитура Times. Усл.печ.л. 1 jO. Уч. -изд.л. 0,9 Тираж 100 экз. Заказ № 639

Уфимский государственный авиационный технический университет Центр оперативной полиграфии 450000, Уфа-центр, ул. К.Маркса, 12

2006-4 2075

15«

Введение

1 Анализ предметной области

1.1 Обзор технологий интеграции информации.

1.2 Обзор моделей доступа к данным

1.3 Обзор существующих разработок медиаторов XML для реляционных систем.

1.3.1 Пример.

1.3.2 XTABLES на базе расширения SQL.

1.3.3 Microsoft SQLXML./

1.3.4 Oracle XML DB.,

1.3.5 XTABLES на базе XQucry

1.4 Выводы.

2 Архитектура и методы реализации

2.1 Анализ требований к виртуальному реиозиторию

2.1.1 Общесистемные требования.

2.1.2 Инициатива XML:DB

2.1.3 Функциональные требования.

2.2 Построение архитектуры

2.2.1 Перечень компонент и аспектов архитектуры.

2.3 Методы реализации

2.3.1 Чтение ресурсов: Обработка аннотированной схемы

2.3.2 Запись ресурсов: Систематический учет зависимостей по данным

2.3.3 Работа с частями ресурсов: Двухфазное исполнение запросов .G

2.4 Варианты использования .G

2.4.1 Интеграция гетерогенных источников.G

2.4.2 Реинжиниринг унаследованной системы.G

2.4.3 Генерация реляционных баз данных па основе автоматического аннотирования .GG

2.5 Выводы. . .GG

3 Модели иерархических документов в реляционной системе

3.1 Вложенные отношения. . G

3.2 Операция вкладывающего соединения

3.3 Вложенные последовательности кортежей.

3.4 Более гибкие схемы

3.5 Выводы.

4 Анализ эффективности предложенных методов и моделей

4.1 Разработка исследовательского прототипа

4.2 Постановка эксперимента.

4.3 Анализ результатов экперимепта.

4.4 Интерпретация результатов эксперимелта.

4.4.1 Линейная зависимость времени обработки от размера результата.

4.4.2 Падение скорости обработки при росте сложности схемы ИЗ

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

4.4.4 Более низкая средняя скорость обработки у прототипа на тестах с несложными схемами.

4.5 Выводы.

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

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

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

Интеграция информационных сред и их модернизация должны отвечать и другому важному требованию, а именно, поддерживать так называемые "унаследованные" системы (legacy systems). Этим термином обозначают системы, базирующиеся на морально устаревших технологиях, но имеющие в силу ис торических причин критическое значение для существования предприятия или организации.

Роль XML (extensible Markup Language - расширяемый язык разметки) как универсального формата обмена данными и, прежде всего, гибкой технологической платформы широко признана. Разнообразные исследовательские проекты в INRIA, AT&T Labs, IBM Almaden и универсистета Висконсина посвящены проблеме отображения XML на реляционные базы данных. Сегодня все ведущие системы управления реляционными базами данных построены на базе результатов этих исследований и обеспечивают экспорт данных в формате XML в той или иной степени. Многие исследователи сходятся во мнении, что реляционные базы данных в общем не являются идеальными для хранения XML, однако в случае, когда XML данные берут свое начало в реляционной базе данных и пе требуется эффективного механизма записи, такой способ храпения может быть приемлемым. Значительная часть разработок направлена на решения "с чистого листа" и не пригодна для реинжииириит "унаследованных" систем.

Вопросами интеграции информации и реляционных базах данных па основе XML технологий активно занимаются различные пауные коллективы у нас в стране (Мельников А.В., Миронов В.В., Когаловский М.Р.) и за рубежом (М. Fernandez, D. Florescn, J. Shanmagasundarain, I. Tatarinov, D. Suciii). Однако большинство решений в этой области носит преимущественно эвристический характер.

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

Цель работы и задачи исследования

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

• разработка общей архитектуры виртуальных репозиториев на базе открытых стандартов;

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

• разработка подходов к интеграции информации, реинжинирингу "унаследованных" систем и генерации баз данных на основе виртуального репозитория;

• разработка модели иерархических документов в реляционной системе;

• исследование эффективности применения предложенных моделей, методов, подходов на основе вычислительного эксперимента.

Методика исследования

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

Результаты, выносимые на защиту

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

• методы реализации административных вариантов использования виртуального репозитория;

• модели иерархических документов в реляционной системе;

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

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

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

Новыми являются следующие разработки и исследования автора:

• альтернативный метод предотвращения аномалий обновления на основе систематического учета зависимостей;

• подход к эффективному исполнению запросов XML на основе двухфазной обработки и понятия сужающих запросов;

• подход к моделированию иерархических документом со схемами произвольной структуры (включая рекурсивные) па основе вложенных последовательностей кортежей;

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

Практическая значимость и внедрение результатов

Практическую значимость имеют предложенные и разработанные актором:

• основанные на модели путевых проекций алгоритмы построения запросов на языке SQL для публикации документов XML из реляционных баз данных;

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

• исследовательский прототип системы публикации документов XML из реляционных баз данных;

• исследовательская платформа для иллюстрации предложенного теор-тетического подхода к моделированию XML в реляционных системах.

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

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

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

Исследования проводились в рамках федеральной целевой программы "Интеграция науки и высшего образования Российской Федерации на 20022006 гг." по проекту "Фундаментальные исследования и новые технологии проектирования сложных технических систем" и частично поддержаны грантом РФФИ 03-07-90242 "Интернет-комплекс поддержки выполнения проектов фундаментальных исследований сложных систем с применением интеллектуальных технологий на базе экспертных систем" (2003-2005 гг.)

Разработанное автором программное обеспечение зарегистрировано в Отраслевом фонде алгоритмов и программ Государственного координационного центра.

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

Основные положения и результаты работы докладывались па следующих научно-технических конференциях: 3-й международной конференции по проблемам технологий для электронных сервисов VLDB TES'2002 (23-24 августа 2002 г., Гонконг, Китай); 4-й Международной конференции по проблемам информатики и информационных технологий CSIT'2002 (18-20 сентября 2002 г., Патры, Греция); 5-й Международной конференции по проблемам информатики и информационных технологий CSIT'2003 (16-18 сентября 2003 г., Уфа, Россия); 14-й Международной конференции "Информатика в защите окружающей среды" Envirolnfo'2003 (24-26 сентября 2003 г., Коттбус, Германия).

Публикации

Основные материалы диссертационной работы опубликованы в 12 научных трудах, в том числе в виде научных статей в 3-х международных и 2-х российских научных изданиях.

Структура работы

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

4.5 Выводы

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

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

Заключение

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

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

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

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

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

3.

4.

Был поставлен и проведен вычислительный эксперимент, в ходе которого была исследована эффективность применения предложенных в работе подходов, методов и моделей. В рамках эксперимента производилось сравнение производительности обработки данных исследовательским прототипом и программным продуктом Microsoft SQL XML. Результаты эксперимента показали, что при усложнении структуры публикуемых документов соотношение производительносгей изменяется в пользу исследовательского прототипа. На используемых тестах достигалось более чем двухкратное превышение производительности прототипа над эталонным продуктом.

6. Была произведена интерпретация результатов эксперимента. Показана алгоритмическая эффективность реализации прототипа.

1. Ахунов А. Н., Валиков А. Н. Визуализация географических карт, на основе масштабируемых пространственных запросов // Принятие решений в условиях неопределенности: Межвуз.науч.сб. — Уфа: УГАТУ, 2002.— С. 298-308.

2. Ахунов А. Н., Юсупова Н. И. Предотвращение аномалий обновления путем учета семантических ограничений // Принятие решений в условиях неопределенности. Вопросы моделирования: Межвуз.науч.сб. — Уфа: УГАТУ, 2004.-С. 26-33.

3. Базы данных. Интеллектуальная обработка информации / В. В. Кор-неев, А. Ф. Гареев, С. В. Васютин, В. В. Райх. — М.: Нолидж, 2000.— 352 с.

4. Бойко В. В., Савинков В. М. Проектирование баз данных информационных систем. 2-е изд., перераб. и доп. — М.: Финансы и статистика, 1989. — 350 с.

5. Валиков А. Н. Технология XSLT. — СПб.: Издательство "БХВ-Петербург", 2002. 544 с.

6. Вендров А. М. Проектирование программного обеспечения экономических информационных систем.— М.: Финансы и статистика, 2000.— 352 с.

7. Гарсия-Молина Г., Ульман Д., Уидом Д. Системы баз данных. Полный курс: Пер. с англ. — М.: Издательский дом "Вильяме", 2003.— 1088 с- •

8. Гасанов Э. Э., Кудрявцев В. Б. Теория хранения и поиска информации. — М.: ФИЗМАТЛИТ, 2002. 288 с.

9. Дейт К. Д. Введение в системы баз данных, 7-е издание: Пер. с англ.— М.: Издательский дом "Вильяме", 2002.— 1072 с.

10. Зверев Г. Н. Основания теоретической информатики: Учеб.пособие для вузов. Ч.Ю.: Иерархические материально-информационные системы.— Уфа: УГАТУ, 2001.- 170 с.

11. Калиниченко JI. А. Методы и средства интеграции неоднородных баз данных. — М.: Наука, 1983. — 423 с.

12. Касьянов В. Н., Евстигнеев В. А. Графы в программировании: обработка, визуализация и применение.— СПб.: Издательство "БХВ-Петербург", 2003. 1104 с.

13. Кнут Д. Э. Искусство программирования, 3. изд.: Пер. с англ. — М.: Издательский дом "Вильяме", 2002.— Т. 1: Основные алгоритмы. — 720 с.

14. Кнут Д. Э. Все про ТеХ: Пер. с англ.— М.: Издательский дом "Вильяме", 2003.-560 с.

15. Когаловский М. Р. Энциклопедия технологий баз данных. — М.: Финансы и статистика, 2002. — 800 с.

16. Кузнецов О. П. Дискретная математика для инженера. — М.: Энерго-атомиздат, 1988. — 479 pp.

17. Мельников А. В. Система обработки информации и управления: архитектура и программное обеспечение // Сб.науч. тр. Юо/с.-Уральского гос.ун-та. — 1998. — 147 с.

18. Миронов В. В., Юсупова Н. И. XML-технологии в базах данных. Введение. Учебное пособие. — Уфа: Уфимск.гос.авиац.техн.ун-т, 2004.— 182 с.

19. Одинцов И. О. Профессиональное программирование. Системный подход. СПб.: БХВ, 2002. - 512 с.

20. Останин А. Н. Применение математических методов и ЭВМ. Планирование и обработка результатов эксперимента: Учеб. пособие для вузовпо спец. 01.02 "Прикладная математика". — Минск: Высш. шк., 1989. — 217 с.

21. Пакштпас А. Синтаксически-ориентированные компоненты распределенных систем. Инструменты разработки на основе формальных описаний. — М.: Наука, 1992. — 272 с.

22. Подсевалов В. В. Теоретико-множественные методы представления и преобразования информации: Учеб. пособие.— Тула: ТулПИ, 1988.— 90 с.

23. Смальян Р. М. Теория формальных систем. — М.: Наука, 1981.— 207 с.

24. Ульман Д. Д. Основы систем баз данных. Пер. с англ. М.Р. Когаловско-го, В.В. Котуговского. — М.: Финансы и статистика, 1983. — 334 с.

25. Филд А., Харрнсон П. Функциональное программирование: Пер. с англ. М.: Мир, 1993. - 637 с.

26. Abiteboul S., Ginsburg S. Tuple sequences and lexicographic indexes // J. ACM. — 1986.— Vol. 33, no. 3.- Pp. 409-422.

27. Abiteboul S., Vianu V. Equivalence and optimization of relational transactions // J. ACM. — 1988. — Vol. 35, no. 1.- Pp. 70-120.

28. Akhounov A., Valikov A. Connecting Frameworks to Databases with XML // Proceedings of the 4th International Workshop on Computer Science and Information Technologies (CSIT'02). 2002.

29. Akhounov A., Valikov A. Guidelines for System Decomposition within the Component-Oriented Architecture // Proceedings of • the 5th International Workshop on Computer Science and Information technologies (CSIT'2003). 2003. - Pp. 69-73.

30. Akhounov A., Yussupova N., Valikov A. Path Projections for Modelling XML in Relations // Proceedings of the 6th International Workshop on Computer Science and Information technologies (CSIT'2004). — Vol. 1.— 2004. Pp. 145-148.

31. Arenas. M., Libkin L. An information-theoretic approach to normal forms for relational and XML data j j Proceedings of the twenty-second ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems. ACM Press, 2003.- Pp. 15-26.

32. Arenas M., Libkin L. A normal form for XML documents // ACM Trans. Database Syst. 2004. - Vol. 29, no. 1. - Pp. 195-232.

33. Armstrong W. Dependency structures of database relationships // Proceddings of the 1974 IFIP Congress. 1974. - Pp. 580-583.

34. Bancilhon F., Spyratos N. Update semantics of relational views // ACM Trans. Database Syst. — 1981. Vol. 6, no. 4. - Pp. 557-575.

35. Beeri C., Fagin R., Howard J. H. A complete axiomatization for functional and multivalued dependencies in database relations / / Proceedings of the 1977 ACM SIGMOD international conference on Management of data. — ACM Press, 1977. Pp. 47-61.

36. Bonifati A., Ceii S. Comparative analysis of five XML query languages // SIGMOD Rec. 2000. - Vol. 29, no. 1. - Pp. 68-79.

37. Brzozowski J. A. Derivatives of Regular Expressions // J. ACM. — 1964. — Vol. 11, no. 4. Pp. 481-494.

38. Camps R. Domains, relations and religious wars // SIGMOD Rec. — 1996. — Vol. 25, no. 3. Pp. 3-9.

39. Chaudhuri S., Dayal U. An overview of data warehousing and OLAP technology // SIGMOD Rec. 1997. - Vol. 26, no. 1. - Pp. 65-74.

40. Codd E. F. A relational model of data for large shared data banks // Commun. ACM. 1970. - Vol. 13, no. 6. - Pp. 377-387.

41. Codd E. F. Further normalization of the database relational model // Database Systems. — 1972.

42. Colby L. S. A recursive algebra and query optimization for nested relations // Proceedings of the 1989 ACM SIGMOD international conference on Management of data. ACM Press, 1989. - Pp. 273-283.

43. Editing ISO 19115 Compliant Metadata in EUROSION / W. Kazakos, A. Akhounov, H. Paoli et al. // Proceedings of the 17th International Conference on Information Technology for Environmental Protection. — 2003.-Pp. 248-254.

44. Proceedings of the 20th Conference on Foundations of Software Technology and Theoretical Computer Science. — Springer-Verlag, 2000.— Pp. 11-45.

45. Geographic Information Metadata, 2003.

46. Gradecki J. D., Lesiecki N. Mastering Aspect J: aspect-oriented programming in Java. — Wiley, 2003. 434 pp.

47. Giiting R. H., Zicari R., Choy D.M. An algebra for structured office ^ documents // A CM Trans. Inf. Syst. 1989. - Vol. 7, no. 2. - Pp. 123-157.

48. Higgins S. XML Database Developer's Guide - Oracle XML DB, 2002.

49. Ives Z. G., Halevy A. Y., Weld D. S. An XML query engine for network-bound data // The VLDB Journal. 2002. - Vol. 11, no. 4. - Pp. 380-402.

50. Jaeschke G., Schek H. J. Remarks on the algebra of non first normal form relations // Proceedings of the 1st ACM SIGACT-SIGMOD symposium on

51. У" Principles of database systems. — ACM Press, 1982. — Pp. 124-138.

52. Keys for XML / P. Buneman, S. Davidson, W. Fan et al. // Proceedings of the tenth international conference on World Wide Web. — ACM Press, 2001.-Pp. 201-210.

53. Lee D., Chu W. W. Comparative analysis of six XML schema languages // ' SIGMOD Rec. 2000. - Vol. 29, no. 3. - Pp. 76-87.s

54. Liu H.-C., Rarnamohanarao K. Algebraic equivalences among nested relational expressions // Proceedings of the third international conference on Information and knowledge management. — ACM Press, 1994. — Pp. 234243.

55. May W., Ludascher• B. Understanding the global semantics of referential actions using logic rules // ACM Trans. Database Syst.— 2002.— Vol. 27, no. 4. Pp. 343-397.

56. MSDN Library, http://msdn.microsoft.com/library.

57. Ontologies and markup languages. http://www.semanticweb.org / knowmarkup.html.

58. Ozsoyoglu Z. M., Yuan L.-Y. A new normal form for nested relations // ACM Trans. Database Syst. 1987.-Vol. 12, no. 1.- Pp.' 111-136.

59. Resource Definition Framework (RDF): Concepts and Abstract Syntax. — 2004. http://www.w3.org/TR/rdf-concepts/.

60. Roth M. A., Korth H. F., Silberschatz A. Extended algebra and calculus for nested relational databases // ACM Trans. Database Syst.— 1988.— Vol. 13, no. 4. Pp. 389-417.

61. RRXS: Redundancy reducing XML storage in relations / Y. Chen, S. Davidson, С. Hara, Z. Zheng // Proceedings of the 29th VLDB Conference. 2003.

62. Sheth A. P., Larson J. A. Federated database systems for managing distributed, heterogeneous, and autonomous databases // ACM Cornput. Surv. 1990. - Vol. 22, no. 3. - Pp. 183-236.

63. SilkRoute: A framework for publishing relational data in XML / M. Fernandez, Y. Kadiyska, D. Suciu et al. // ACM Trans. Database Syst. — 2002.- Vol. 27, no. 4.- Pp. 438-493.

64. Storing and querying ordered XML using a relational database system / I. Tatarinov, S. D. Viglas, K. Beyer et al. // Proceedings of the 2002 ACM SIGMOD international conference on Management of data. — ACM Press, 2002.-Pp. 204-215.

65. Ullman J. D. Principles of Database and Knowledge-Base Systems: Volume I. — Computer Science Press, 1988.

66. Ullman J. D. Principles of Database and Knowledge-Base Systems: Volume II: The New Technologies. W. H. Freeman к Co., 1990.

67. Valikov A., Akhounov A., Schmidt A. A Model-Transformers Architecture . for Web Applications // Proceedings og the 3rd VLDB Workshop on

68. Technologies for E-Serviccs (TES'02). 2002. - Pp. 29-37. ■ •

69. Valikov A., Alexei A., Kazakos W. Remote Method Invocation for Web Applications // Proceedings of the 4th International Workshop on Computer

70. Science and Information Technologies (CSIT'02). 2002.• •

71. Wiederhold G. Mediators in the Architecture of Future Information Systems // Computer. 1992. - Vol. 25, no. 3. - Pp. 38-49.

72. Wiederhold G. Mediation in information systems // ACM Comput,. Sum.— 1995. Vol. 27, no. 2. - Pp. 265-267.

73. XML Path Language (XPath) Version 1.0.- 1999. http://www.w3.org/TR/xpath/.

74. XML Schema Part 0: Primer. — 2001. http://www.w3.org/TR/xmlschema-0/.

75. XML Schema Part 1: Structures. — 2001. http://www.w3.org/TR/xmlscherria-l/.

76. XQuery 1.0: An XML Query Language. — 2003. http://www.w3.org/TR/xquery.

77. XSL Transformations XSLT Version 2.0.- " 2003. http://www.w3.org/TR/xslt20/.