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

• Ахунов, Алексей Ножипович
• кандидат технических наук
• 2004

Оглавление диссертации кандидат технических наук Ахунов, Алексей Ножипович

Введение

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. Была произведена интерпретация результатов эксперимента. Показана алгоритмическая эффективность реализации прототипа.

Список литературы диссертационного исследования кандидат технических наук Ахунов, Алексей Ножипович, 2004 год

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/.