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

• Гринева, Мария Павловна
• кандидат физико-математических наук
• 2007

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

Оглавление.

Введение.

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

Цель и задачи работы.

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

Научная новизна работы.

Практическая значимость.

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

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

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

Глава 1 Активные СУБД.

1.1 Активные СУБД и триггеры.

1.1.1 Триггеры.

1.1.2 Общая форма определения триггеров.

1.1.3 Язык определения триггеров.

1.1.4 Семантика выполнения триггеров.

1.1.5 Архитектура активных СУБД.

1.1.6 Основные аспекты реализации активных СУБД.

1.2 Триггеры в реляционных СУБД.

1.2.1 Триггеры в стандарте SQL.

1.2.2 Методы реализации триггеров в РСУБД.

1.3 Выводы.

Глава 2 Проблемы и задачи реализации поддержки активного поведения XML-СУБД.

2.1 Платформа XML.

2.1.1 Расширяемый язык разметки XML.

2.1.2 Язык запросов XQuery.

2.1.3 Язык модификаций XML-данных.

2.2. Аспекты реализации XML-СУБД.

2.2.1 Связи между узлами XML-документа в XML-СУБД.

2.2.2 Описывающая схема.

2.2.3 Нумерующая схема.

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

2.3.1 Анализ применимости методов реализации триггеров РСУБД.

2.3.2 Существующие методы реализации XML-триггеров.

2.4 Выводы.

Глава 3 Язык определения и семантика выполнения XML-триггеров.

3.1 XML-триггеры на модификацию данных.

3.1.1 Инициирующие события.

3.1.2 Выполнение, ориентированное на экземпляр, и выполнение, ориентированное на набор экземпляров.

3.1.3 Действия.

3.1.4 Выполнение нескольких XML-триггеров одной группы.

3.1.5 Видимость изменений данных.

3.1.6 Пример.

3.2 XML-триггеры на выборку данных.

3.2.1 Инициирующие события.

3.2.2 Действия.

3.2.3 Взаимодействие с операциями модификации.

3.2.4 Выполнение нескольких XML-триггеров.

3.2.5 Пример.

3.3 Выводы.;.

Глава 4 Методы реализации XML-триггеров для XML-СУБД.

4.1 Методы реализации XML-триггеров на модификацию данных.

4.1.1 «Наивный» метод реализации XML-триггеров на модификацию данных.

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

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

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

4.2. Методы реализации XML-триггеров на выборку данных.

4.2.1. «Наивный» метод реализации XML-триггеров на выборку данных.

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

4.3 Выводы.

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

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

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

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

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

Цель и задачи работы

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

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

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

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

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

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

1. Разработаны язык определения и семантика выполнения двух видов XML-триггеров: XML-триггеров на модификацию данных и XML-триггеров на выборку данных. Язык определения и семантика выполнения разработанных XML-триггеров учитывают специфику XML-модели данных.

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

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

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

Научная новизна работы

Научной новизной обладают следующие результаты диссертационной работы:

1. Разработан язык определения XML-триггеров на модификацию данных и XML-триггеров на выборку данных.

2. Разработана семантика выполнения XML-триггеров на модификацию данных и XML-триггеров на выборку данных.

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

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

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

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

Разработанные методы могут быть использованы для реализации предложенных XML-триггеров в XML-СУБД.

На основе предложенных методов реализации XML-триггеров на модификацию данных разработана подсистема поддержки XML-триггеров на модификацию данных в промышленной XML-СУБД Sedna, разрабатываемой в ИСП РАН.

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

По теме диссертации опубликовано восемь работ [1-8]. Основные положения работы докладывались на следующих конференциях и семинарах:

• на первом и втором весенних коллоквиумах молодых исследователей в области баз данных и информационных систем (SYRCoDIS) (2004 и 2005 гг);

• на семинаре шестнадцатой международной конференции по базам данных и экспертным системам (DEXA), посвященном логическим аспектам и приложениям ограничений целостности (LAAIC) (2005 г);

• на семинаре семнадцатой международной конференции по базам данных и экспертным системам (DEXA), посвященном средствам управления XML-данными (XANTEC) (2006 г);

• на двенадцатой международной конференции студентов, аспирантов и молодых ученых «Ломоносов-2005»;

• на семинаре «Проблемы современных информационно-вычислительных систем» под руководством д.ф.-м.н, профессора Васенина В.А. (2005 г);

• на сто тринадцатом семинаре Московской Секции ACM SIGMOD (2006 г);

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

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

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

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

4.3 Выводы

В настоящей главе описаны разработанные автором методы реализации XML-триггеров в XML-СУБД. В первом разделе данной главы были рассмотрены методы реализации XML-триггеров на модификацию данных: «наивный» метод; метод, основанный на использовании фиксаторов на описывающей схеме; метод, основанный на объединении планов выполнения путевых выражений. «Наивный» метод реализации представляет собой наиболее простой и очевидный подход к реализации. Анализ «наивного» метода показал, что поиск инициируемых XML-триггеров, который является частью обработки XML-триггеров при выполнении операции модификации, требует неприемлемых для практических приложений накладных расходов. По этой причине автором разработаны описанные далее в первом разделе методы, позволяющие определять инициируемые XML-триггеры эффективным образом: метод, основанный на использовании фиксаторов на описывающей схеме, и метод, основанный на объединении планов выполнения путевых выражений. Эффективность предложенных методов подтверждается экспериментальными оценками, описанными в заключении первого раздела.

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

Заключение

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

1. Разработаны язык определения и семантика выполнения двух видов XML-триггеров: XML-триггеров на модификацию данных и XML-триггеров на выборку данных. Язык определения и семантика выполнения разработанных XML-триггеров учитывают специфику XML-модели данных.

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

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

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

Список литературы диссертационного исследования кандидат физико-математических наук Гринева, Мария Павловна, 2007 год

1. Рекуц М.П.: Виды ограничений целостности в базах XML-данных. Труды Института Системного Программирования РАН. Том 8. Часть 2. Москва 2004.

2. М. Rekouts: Application Programming Interface for XML DBMS: design and implementation proposal. Proc. of SYRCoDIS 2004. S.Petersburg, Russia.

3. M. Rekouts, M. Grinev: Introducing Trigger Support for XML Database Systems. Proc. of SYRCoDIS 2005, S.Petersburg, Russia.

4. M. Rekouts: Incorporating Active Rules Processing into Update Execution in XML Database Systems. Proc. of DEXA Workshops 2005, pp. 831-836. ISBN 0-7695-24249. Copenhagen, Denmark.

5. М. Rekouts, М. Grinev, A. Boldakov: A Method for XQuery Transform Implementation Based on Shadow Mechanism. Proc. of DEXA Workshops 2006, pp. 470-475. Krakow, Poland.

6. M. П. Гринева, M. H. Гринев: Триггеры на выборку данных в XML-ориентированных СУБД: эффективная реализация с использованием теневого механизма. Программирование. М.: Наука, 2007. - N 4. - С. 32-45.

7. М. Rekouts, Н. Christiansen: Integrity Checking and Maintenance with Active Rules in XML Databases. Proc. of BNCODWebim. 2007, pp. 59-67. ISBN 0-76952912-7 Glasgow, UK.

8. L. Brownston, R. Farrell, E. Kant, N. Martin: Programming Expert Systems in OPS5: An Introduction to Rule-Based Programming. Addison-Wesley, Reading, Massachusetts, 1985.

9. H. Jasper, O. Zukunft, H. Behrends: Time Issues in Advanced Workflow Management Applications of Active Databases, Proc. of ATRDB, 1995.

10. K.P. Eswaran, D.D. Chamberlin: Functional specifications of a subsystem for data base integrity. Proc. of 1st VLDB Conference, 1975.

11. K.P. Eswaran: Specifications, implementations and interactions of a trigger subsystem in an integrated database system. IBM Research Report, 1976.

12. CODASYL data description language committee. CODASYL Data Description Language Journal of Development, 1973

13. M. Stonebraker: Implementation of integrity constraints and views by query modification. Proc. of ACM SIGMOD, 1975.

14. M. Stonebraker, L. Rowe, M. Hirohama: The implementation of POSTGRES. IEEE Transactions on Knowledge and Data Engineering, 1990.

15. M. Stonebraker, A. Jhingran, J. Goh, S. Potamianos: On rules, procedures, caching and views in data base systems. Proc. of ACM SIGMOD, 1990.

16. S. Potamianos: Semantics and Performance of Integrated DBMS Rule Systems. Ph.D. thesis, University of California, Berkeley, 1990.

17. J. Goh: Rule Processing with Query Rewrite. Master's thesis, University of California Berkeley, 1991.

18. X. Qian, G. Wiederhold: Incremental recomputation of active relational expressions. IEEE Transactions on Knowledge and Data Engineering. 1991.

19. С.Д. Кузнецов: Основы баз данных. Издательство Интернет-Университет Информационных Технологий, 2005.

20. J. Melton: Advanced SQL: 1999. Understanding Object-Relational and Other Advanced Features. Morgan Kaufmann Publishers, 2003.

21. D. Suciu: Semistructured data and XML. Kluwer Academic Publishers, 2000.

22. P. Buneman: Semistructured data. Proc. of ACM SIGMOD/SIGACT Conference on Principle of Database Systems (PODS), Tucson, 1997.

23. M. Гринев: Системы управления полуструктурированными данными. Журнал «Открытые системы» №05-06, издательство «Открытые системы», 1999.

24. The World Wide Web Consortium (W3C). Extensible Markup Language (XML) 1.0 (Third Edition) W3C Recommendation. Jean Paoli, С. M. Sperberg-McQueen et al., 2004.

25. The World Wide Web Consortium (W3C). HTML 4.0 Specification. W3C Recommendation. D. Raggett, A. Le Hors, I. Jacobs, 1998. http://www.w3 .org/TR11998/REC-html40-19980424

26. ISO 8879. Information Processing Text and Office Systems - Standard Generalized Markup Language (SGML), 1986

27. The World Wide Web Consortium (W3C). XQuery 1.0 and XPath 2.0 Data Model: W3C Recommendation. M. Fernandez, M. Kay et at. (eds.), 2007. http://www.w3.org/TR/xpath-datamodel/

28. The World Wide Web Consortium (W3C). XQuery 1.0: An XML Query Language: W3C Recommendation. S. Boag et al. (eds.), 2007. http://www.w3 .org/TR/xquery

29. The World Wide Web Consortium (W3C). XML Path Language (XPath) 2.0: W3C Recommendation. D. Chamberlin, M. Fernandez, M. Kay et al. (eds.), 2007. http://www.w3 ,org/TR/xpath20/

30. The World Wide Web Consortium (W3C). XQuery 1.0 and XPath 2.0 Functions and Operators: W3C Recommendation. J. Melton et al. (eds.), 2007. http://www.w3.org/TR/xpath-functions/

31. The World Wide Web Consortium (W3C). Namespaces in XML 1.0: W3C Recommendation, 2006. http://www.w3.org/TR/xmI-names/

32. T. Fiebig, S. Helmer, C.-C. Kanne, G. Moerkotte, J. Neumann, R. Schiele, T. Westmann: Anatomy of a native XML base management systems. VLDB Journal Vol. 11, Num. 26,2002.

33. Software AG. Tamino the XML Power Database. Technical report, Software AG, 2001.

34. H. Jagadish et al.: TIMBER: A native system for quering XML. Proc of SIGMOD, 2003.

35. W. Meier: eXist: An Open Source Native XML Database. Proc. of Web, Web-Services, and Database Systems 2002, Erfurt, Germany.

36. X. Meng, D. Luo, M. Lee et al.: OrientStore: A Schema Based Native XML Storage System. Proc of VLDB, 2003.

37. J. McHugh, S. Abiteboul, R. Goldman, D. Quass, J. Widom.: Lore: A Database Management System for Semistructured Data. SIGMOD Record Vol. 26, N. 3, 1997.

38. N.A. Aznauryan, S.D. Kuznetsov, L. G. Novak, and M. N. Grinev.: SLS: A Numbering Scheme for Large XML Documents. Programming and Computer Software, N. 1, Vol. 32,2006.

39. Гринев M. H., Кузнецов С.Д., Фомичев А. В.: XML-СУБД Sedna: технические особенности и варианты использования. Открытые системы №8,2004.

40. Фомичев А. В.: Исследование и разработка методов организации выполнегия и физической оптимизации запросов к XML-данным. Диссертация на соискание ученой степени кандидата физико-математических наук, ВмиК МГУ, Москва, 2006.

41. А.А. Болдаков, М.Н. Гринев: Расширение языка XQuery функциональными update-выражениями. Препринт ИСП РАН, 2006.

42. I. Tatarinov, Z. Ives, A. Halevy, D. Weld: Updating XML. Proc. of SIGMOD Conference, 2001.

43. P. Lehti: Design and Implementation of a Data Manipulation Processor for an XML Query Language, Diplomarbeit, 2001.

44. J. Simeon, P. Wadler: The Essence of XML, Proc. of FLOPS, 2002.

45. J. Bailey, G. Papamarkos, A. Poulovassilis, P.T. Wood: An Event-Condition-Action Language for XML. Proc. of Web Dynamics, 2004

46. J. Bailey, A. Poulovassilis, P. Wood: Analysis and Optimisation of Event-Condition-Action Rules on XML, Computer Networks, Volume 39,2005.

47. Коллекция пьес Шекспира в формате XML. «Shakespeare in XML». http://www.ibiblio.org/xml/examples/shakespeare/

48. Digital Bibliography & Libraiy Project: DBLP XML records, http://dblp.uni-trier.de/xml/

49. M. Grinev: Rewriting-based Optimization for XQuery Transformational Queries -Revisited. Technical Report, MODISISPRAS, 2004.

50. Raymod A. Lorie: Physical Integrity in a Large Segmented Database. ACM Transactions on Database Systems, Vol.2, No. 1, (1977) 91-104

51. A. Schmidt, F. Waas, M. L. Kersten, M. Carey, I. Manulescu, R. Busse: XMark: A Benchmark for XML Data Management. Proc. of VLDB, 2002.

52. F. Fabret, M. Reignier, E. Simon: An adaptive algorithm for incremental evaluation of production rules in databases. Proc. of VLDB, 1993.

53. Y.-W. Wang, E. Hanson: A performance comparison of the Rete and TREAT algorithm for testing database rule conditions. Proc. of ICDE, 1992.

54. Oracle Database. Technical report, http://www.oracle.com/database/index.html

55. IBM DB2 Data Server. Technical report. http://www.oracle.com/database/index.html

56. Microsoft SQL Server. Technical report. http://www.microsoft.com/sql/default.mspx

57. Open Source Database PostgreSQL. Documentation on internals, http http://www.postgresql.0rg/docs/8.O/static/internals.html

58. The World Wide Web Consortium (W3C). XQuery 1.0 and XPath 2.0 Functions and Operators. A. Malhotra, J. Melton, N. Walsh. Jan 2007. http://www.w3.org/TR/xpath-functions

59. D. Chamberlin: XQuery: An XML Query Language. IBM Systems Journal, Vol. 41, No. 4,2002.

60. The World Wide Web Consortium (W3C). XQuery Update Facility. W3C Working Draft. D. Chamberlin, D. Florescu, J. Robie. 2006, Jan. http://www.w3.org/TR/xqupdate

61. S. Abiteboul: Querying Semi-Structured Data. Proc.of ICDT, 1997

62. R. Bourret: XML and Databases. Technical report, 2005. http://www.rpbourret.com/xml/XMLAndDatabases.htm

63. XHive Corporation. XHive/DB. Documentation Extras. http://www.x-hive.com/products/db/specs.html

64. A. Bonifati, S. Paraboschi: Active XQuery. Proc. of Web Dynamics, 2004.

65. The World Wide Web Consortium (W3C). XML Schema Part 2: Datatypes Second Edition. W3C Recommendation. 2004, October. http://www.w3.org/XML/Schema.

66. A. Fomichev, M. Grinev, S. Kuznetsov: Descriptive Schema Driven XML Storage. ISP RAS. Technical Report, 2004.

67. U. Dayal, А.Р. Buchmann, S. Chakravarthy: The HiPAC Project. Active Database Systems. Chapter 7. Morgan Kaufmann Publishers, 1996.

68. N. Gehani, H.V. Jagadish: Active Database Facilities in Ode. Active Database Systems. Chapter 8. Morgan Kaufmann Publishers, 1996.