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

• Фомичев, Андрей Владимирович
• кандидат физико-математических наук
• 2005

Оглавление диссертации кандидат физико-математических наук Фомичев, Андрей Владимирович

Оглавление.

Введение.

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

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

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

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

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

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

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

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

Глава 1 Управление хранимыми XML-данными.

1.1 Технологии платформы XML для управления данными.

1.1.1 Язык XML, .слабоструктурированные данные и платформа XML.

1.1.2 Модель данных XPath и XQuery.

1.1.3 Язык путевых выражений XPath и язык запросов XQuery.

1.2 Управление хранимыми XML-данными в полнофункциональной XML-СУБД.

1.2.1 Полнофункциональная XML-СУБД.

1.2.2 Требования к полнофункциональной XML-СУБД в контексте управления хранимыми данными.

1.3 Подходы к храпению XML-данных.

1.3.1 Связи между узлами: по значению или по ссылке?.

1.3.2 Определение отношения предок-потомок и порядка документа: нумерующая схема.

1.3.3 Использование реляционных СУБД для хранения XML-данных.

1.3.4 Специально разработанные методы для хранения XML-данных.

1.4 Выводы.

Глава 2 Метод хранения XML-данных во внешней памяти на основе описывающей схемы.

2.1 Описывающая схема XML-документа и структурные путевые выражения.

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

2.2 Организация хранения XML-данных во внешней памяти на основе описывающей схемы.

2.2.1. Блоки данных.

2.2.2 Частичный порядок дескрипторов узлов.

2.2.3 Структура дескриптора узла.

2.2.4 Связи между дескрипторами узлов.

2.2.5 Фиксированный размер дескриптора узла в блоке.

2.2.6 Таблица косвенности.

2.2.7 Хранение текстовых данных.

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

2.3 Оценка метода хранения XML-данных во внешней памяти на основе описывающей схемы.

2.3.1 Методика оценки стоимости выполнения операций над базой данных.

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

2.3.3 Оценка стоимости изменения данных.

2.3.3.1 Микрооперация вставки узла.

2.3.3.2 Микрооперация удаления узла.

2.3.4 Навигация по документу.

2.3.5 Экспериментальные данные.

2.3.6 Сравнение с другими методами хранения XML-данных.

2.4 Выводы.

Глава 3 Управление памятью для хранимых XML-данных и слоистая организация адресного пространства.

3.1 О необходимости разработки единого адресного пространства базы данных для представления данных во внешней и оперативной памяти.

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

3.2.1 Требования к управлению памятью для хранимых XML-данных.

3.2.2 Слоистое адресное пространство.

3.2.3 Страничная организация слоистого адресного пространства.

3.2.4 Реализация слоистого адресного пространства.

3.2.4.1 Отображение на виртуальное адресное пространство процесса.^.

3.2.4.2 Отображение на буферную память.

3.2.4.3 Отображение на внешнюю память.

3.2.5 Переход по указателю в слоистом адресном пространстве.

3.2.5.1 Понятие текущей страницы.

3.2.5.2 Переход по указателю в слоистом адресном пространстве для программиста.

3.2.6 Реализация слоистого адресного пространства в многопользовательской среде.

3.2.7 Дополнительные возможности слоистого адресного пространства.

3.2.8 Экспериментальные данные.

3.2.9 Преимущества и недостатки слоистого адресного пространства.

3.2.10 Слоистое адресное пространство и методы управления памятью, основанные на приеме "подмены" указателей.

3.3 Выводы.

Глава 4 Пути доступа к XML-данным, хранимым на основе описывающей схемы.

4.1 Задача поиска оптимального пути доступа к данным.

4.2 Вычисление абсолютного структурного путевого выражения с предикатом. 127 4.2.1 Абсолютное структурное путевое выражение с предикатом.

4.2.2 Способы вычисления абсолютного структурного путевого выражения с предикатом.

4.2.3 Метрика оценки стоимости и селективность путевых выражений.

4.2.4 Оценка стоимости вычисления выражения способом "сверху-вниз".

4.2.5 Оценка стоимости вычисления выражения способом "снизу-вверх".

4.2.6 Оценка стоимости вычисления выражения способом "фильтрации с помощью нумерующей схемы".

4.2.7 Комбинирование способов вычисления выражения.

4.3 Выводы.

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

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

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

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

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

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

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

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

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

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

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

1.1. Для важного подкласса XPath-запросов (абсолютных структурных XPath-запросов) доказана оптимальность разработанных структур данных по числу требуемых операций ввода-вывода;

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

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

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

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

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

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

3. Разработан оригинальный метод выполнения XPath-запросов над предложенным внутренним представлением.

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

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

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

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

Основные положения работы докладывались на десятой международной научной конференции студентов, аспирантов и молодых ученых «Ломоносов-2003», на седьмой международной конференции Advances in Databases and Information Systems (ADBIS) 2003, на первом Весеннем коллоквиуме молодых исследователей в области баз данных и информационных систем (SYRCoDIS) 2004, на девяносто первом и девяносто седьмом семинарах Московской Секции ACM SIGMOD (2004 и 2005 гг), на семинаре "Современные сетевые технологии" под руководством д.ф.-м.н., профессора Васенина В.А. (2005 г).

По материалам диссертации опубликовано пять печатных работ [1,2,3,4,5].

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

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

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

4.3 Выводы

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

Заключение

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

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

1.1. Для важного подкласса XPath-запросов (абсолютных структурных XPath-запросов) доказана оптимальность разработанных структур данных по числу требуемых операций ввода-вывода;

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

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

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

• Оптимизация размера дескриптора узла с целью сокращения объема памяти, занимаемой данными;

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

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

Список литературы диссертационного исследования кандидат физико-математических наук Фомичев, Андрей Владимирович, 2005 год

1. Фомичев А.В., "Методы эффективного выполнения XQuery запросов к XML данным", Материалы Международной конференции студентов и аспирантов по фундаментальным наукам "Ломоносов 2003", Москва, 2003

2. Konstantin Antipin, Andrey Fomichev, Maxim Grinev, Sergey Kuznetsov, Leonid Novak, Peter Pleshachkov, Maria Rekouts, and Denis Shiryaev, "Efficient Virtual Data Integration Based on XML", Proceedings of ADBIS 2003

3. Антипин K.B., Фомичев A.B., Гринев M.H., Кузнецов С.Д., Новак Л.Г., Плешачков П.О., Рекуц М.П., Ширяев Д.Р., Оперативная интеграция данных на основе XML: системная архитектура BizQuery, Труды Института системного программирования РАН, 2004

4. Andrey Fomichev, "XML Storing and Processing Techniques", Proceedings of SYRCoDIS 2004

5. Максим Гринев, Сергей Кузнецов, Андрей Фомичев, "Особенности СУБД Sedna. XML-СУБД Sedna: технические особенности и варианты использования", журнал "Открытые системы" #8, издательство "Открытые системы", 2004

6. Extensible Markup Language (XML) 1.0 (Third Edition), W3C Recommendation 4th February 2004, Fran£ois Yergeau, Tim Bray, Jean Paoli, С. M. Sperberg-McQueen, Eve Male, http://www.w3.org/TR/! 998/REC-xml-19980210

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

8. HTML 4.01 Specification, W3C Recommendation 24 December 1999, Dave Raggett, Arnaud Le Hors, Ian Jacob, http://www.w3.org/TR/1999/REC-html401 -19991224

9. World Wide Web Consortium (W3C), http://www.w3.org/

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

11. Buneman P., Semistructured data. In proceedings of the ACM SIGMOD/SIGACT Conference on Principle of Database Systems (PODS), Tucson, AZ, 1997, May, 117121

12. Гринев, М., Системы управления полуструктурированными данными, журнал "Открытые системы" #05-06, издательство "Открытые системы", 1999

13. ACM SIGMOD (Special Interest Group on Management of Data) Conference, http://www.sigmod.org/sigmod/

14. Very Large Data Bases (VLDB) Conference, http://www.vldb.org/dblp/db/conf/vldb/index.html

15. Zhen Hua Liu, Muralidhar Krishnaprasad, Vikas Arora: Native XQuery processing in Oracle XMLDB. SIGMOD Conference 2005

16. Matthias Nicola, Bert Van der Linden: Native XML Support in DB2 Universal Database. VLDB 2005

17. Shankar Pal, Istvan Cseri, Oliver Seeliger, Michael Rys, Gideon Schaller, Wei Yu, Dragan Tomic, Adrian Baras, Brandon Berg, Denis Churin, Eugene Kogan: XQuery Implementation in a Relational Database System. VLDB 2005

18. ISO/IEC 10646: Universal multi-octet character set UCS, ed. M. Suignard

19. Когаловский, M.P., Стандарты платформы XML и базы данных, Российские Электронные Библиотеки, 2001,http://www.elbib.ru/index.phtml?page=elbib/rus/methodology/xmlbase/tutorial

20. W3C Web Services Activity, http://www.w3.org/2002/ws/

21. W3C Semantic Web. http://www.w3.org/2Q01/sw/

22. SOAP Version 1.2, W3C Recommendation 24 June 2003, http://www.w3.org/TR/soapl 2

23. XML Path Language (XPath) 2.0, W3C Candidate Recommendation 3 November 2005, ed. Anders Berglund et al, http://www.w3.org/TR/2005/CR-xpath20-20Q51103/

24. XML Query Working Group, http://www.w3.org/XML/Query/

25. XQuery 1.0: An XML Query Language, W3C Candidate Recommendation 3 November 2005, ed. Scott Boag et al, httn://www.w3.org/TR/2005/CR-xquery-20Q51103/

26. Namespaces in XML, World Wide Web Consortium 14-January-1999, ed. Tim Bray et al, http://www.w3.org/TR/1999/REC-xml-names-19990114

27. XML Schema Part 2: Datatypes Second Edition, W3C Recommendation 28 October 2004, ed. Paul V. Biron et al,httn://www.w3.org/TR/2004/REC-xmlschema-2-20041028/

28. RELAX NG schema language for XML, http://www.relaxng.org/

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

30. XQuery 1.0 and XPath 2.0 Data Model (XDM), W3C Candidate Recommendation 3 November 2005, ed. Mary Fernandez et al, http://www.w3.org/TR/20Q5/CR-xpath-datamodel-20051103/

31. Mary Fernandez, Jerome Simeon: Growing XQuery, In Proc of ECOOP'2003 (European Conference on Object-Oriented Programming)

32. Dean Meltz, Rick Long, Mark Harrington, Robert Hain, Geoff Nicholls, An Introduction to IMS: Your Complete Guide to IBM's Information Management System, IBM Press, 2004 CODASYL DBTG Report, April 1971

33. Alfons Kemper, Donald Kossmann: Adaptable Pointer Swizzling Strategies in Object Bases. ICDE 1993: 155-162 46. Li, Q., Moon, В.: Indexing and Querying XML Data for Regular Path Expressions,

34. Proceedings of the 27th VLDB Conference, Roma, Italy, 2001

35. J. McHugh, S. Abiteboul, R. Goldman, D. Quass, J. Widom. Lore: A Database Management System for Semistructured Data, SIGMOD Record, 2001

36. Patrick O'Neil, Elizabeth O'Neil, Shankar Pal, Istvan Cseri, Gideon Schaller, Nigel Westbury: ORDPATHs: Insert-Friendly XML Node Labels, In Procof the ACM SIGMOD Conference, 2004

37. H.A. Азнаурян, С.Д. Кузнецов, Л.Г. Новак, М.Н. Гринев: SLS: Нумерующая схема для больших XML-документов, Программирование, 2006, № 1 (принята к публикации)

38. Goldman R., McHugh J., Widom J. From simistructured data to XML: Migrating the Lore data model and query language. In ACM SIGMOD Workshop on the Web (WebDB), Philadelphia, PA, 1999

39. Tian, F., DeWit, D., Chen, J., Zhang, C.: The Design and Performance Evaluation of Alternative XML Storage Strategies. SIGMOD Record 31(1): 5-10 (2002)

40. Igor Tatarinov, Stratis Viglas, Kevin S. Beyer, Jayavel Shanmugasundaram, Eugene J. Shekita, Chun Zhang: Storing and querying ordered XML using a relational database system. SIGMOD Conference 2002: 204-215

41. Jagadish, H., Al-Khalifa, S., Chapman, A., Lakshmanan, L., Nierman, A., Paparizos S., Patel, J., Srivastava D., Wiwatwattana N. Wu, Y. and Yu, C.: TIMBER: A Native XML Database, The VLDB Journal, Volume 11, Issue 4 (2002)

42. Al-Khalifa, S., Jagadish, H., Patel, J., Wu, Y., Koudas, N. Srivastava, D.: Structural Joins: A Primitive for Efficient XML Query Pattern Matching, Proceedings of ICDE 2002, San Jose, California

43. Barbara Catania, Wen Qiang Wang, Beng Chin Ooi, Xiaoling Wang: Lazy XML Updates: Laziness as a Virtue of Update and Structural Join Efficiency. SIGMOD Conference 2005

44. Fiebig, Т., Helmer, S., Kanne, C.-C., Moerkotte, G., Neumann, J., Schiele, R., Westmann, Т.: Anatomy of a native XML base management system, The VLDB Journal, Volume 11, Issue 4 (2002)

45. Leela, K., Haritsa, J.: SphinX: Schema-conscious XML Indexing, Technical Report, TR-2001-04, DSL/SERC, http://dsl.serc.iisc.ernet.in/pub/TR/TR-2001-04.pdf

46. Xiaofeng Meng, Daofeng Luo, Mong-Li Lee, Jing An: OrientStore: A Schema Based Native XML Storage System. VLDB 2003

47. Albrecht Schmidt, Florian Waas, Martin L. Kersten, Michael J. Carey, Ioana

48. Manolescu, Ralph Busse: XMark: A Benchmark for XML Data Management. VLDB 2002

49. Stephane Bressan, Gillian Dobbie, Zoe Lacroix, Mong-Li Lee, Ying Guang Li, Ullas Nambiar, Bimlesh Wadhwa: X007: Applying 007 Benchmark to XML Query Processing Tool. CIKM 2001

50. Shakespeare in XML the collection of Shakespeare's plays marked up in XML, http://www.ibiblio.org/xml/examples/shakespeare/

51. DBLP XML records, http://dblp.uni-trier.de/xml/

52. L. Mignet, D. Barbosa, P. Veltri. The XML Web, A First Study. Proc. 12th Intl.WWW Conference, Budapest, 2003

53. Грииев M.H.: Модельно-языковые средства управления данными, Диссертация на соискание ученой степени кандидата физико-математических наук, Москва, 2003

54. Surajit Chaudhuri: An Overview of Query Optimization in Relational Systems. PODS 1998

55. Persistent Heap, http://modis.ispras.ru/~fomichev/tools/ph/ph.htm

56. Э. Таненбаум, Современные операционные системы, 2-е издание, «Питер», 2002

57. Silberschatz, A., Korth, Н., Sudarshan, S.: Database System Concepts, Third Edition, McGraw-Hill, 1997

58. Patricia G. Selinger, Morton M. Astrahan, Donald D. Chamberlin, Raymond A. Lorie, Thomas G. Price: Access Path Selection in a Relational Database Management System. SIGMOD Conference 1979

59. XSLT 2.0 and XQuery 1.0 Serialization, W3C Working Draft 15 September 2005, ed. Michael Kay et al,http://www.w3.org/TR/2005/WD-xslt-xquerv-serialization-20050915/

60. Гектор Гарсиа-Молина, Джеффри Ульман, Дженнифер Уидом: Системы баз данных. Полный курс, «Вильяме», 2003

61. Michael J. Carey, David J. DeWitt, Joel E. Richardson, Eugene J. Shekita: Object and

62. File Management in the EXODUS Extensible Database System. VLDB 1986

63. Microsoft Developers Network, http://msdn.microsoft.com/

64. Linux Documentation (including Manual Pages), http://www.linux.org/docs/index.html

65. Hong-Tai Chou, David J. DeWitt: An Evaluation of Buffer Management Strategies for Relational Database Systems. VLDB 1985

66. David R. Butenhof, Programming with POSIX Threads, Addison-Wesley, 1997

67. Seth J. White, David J. DeWitt: A Performance Study of Alternative Object Faulting and Pointer Swizzling Strategies. VLDB 1992

68. Wilson, P., Kakkad, S.: Pointer Swizzling at Page Fault Time: Efficiently and Compatibly Supporting Huge Address Spaces on Standard Hardware, Proceedings of Workshop on Object Orientation and Operating Systems, Paris, France, 1992

69. Wilson, P., Kakkad, S.: Pointer Swizzling at Page Fault Time: Efficiently and Compatibly Supporting Huge Address Spaces on Standard Hardware, Proceedings of Workshop on Object Orientation and Operating Systems, Paris, France, 1992

70. C. Lamb, G. Landis, J. Orenstein, D. Weinreb, "The ObjectStore Database System", Communications of the ACM, Vol. 34, No. 10, October 1991.

71. Seth J. White, David J. DeWitt: QuickStore: A High Performance Mapped Object Store. SIGMOD Conference, 1994

72. Goetz Graefe, William J. McKenna: The Volcano Optimizer Generator: Extensibility and Efficient Search. ICDE 1993

73. Laura M. Haas, Johann Christoph Freytag, Guy M. Lohman, Hamid Pirahesh: Extensible Query Processing in Starburst. SIGMOD Conference 1989

74. Ashraf Aboulnaga, Alaa R. Alameldeen, Jeffrey F. Naughton: Estimating the Selectivity of XML Path Expressions for Internet Scale Applications. VLDB 2001

75. Wei Wang, Haifeng Jiang, Hongjun Lu, Jeffrey Xu Yu: Bloom Histogram: Path Selectivity Estimation for XML Data with Updates. VLDB 2004

76. Neoklis Polyzotis, Minos N. Garofalakis, Yannis E. Ioannidis: Selectivity Estimation for XML Twigs. ICDE 2004

77. Куржанский А.Б., Учебник по курсу «Динамическое программирование и процессы управления», 2005

78. Goetz Graefe, David J. DeWitt: The EXODUS Optimizer Generator. SIGMOD Conference 1987

79. Gregory Piatetsky-Shapiro, Charles Connell: Accurate Estimation of the Number of

80. Tuples Satisfying a Condition. SIGMOD Conference, 1984

81. S. B. Yao: Approximating Block Accesses in Database Organizations, Communications of the ACM, Volume 20 , Issue 4, April 1977

82. George Diehr, Aditya N. Saharia: Estimating Block Accesses in Database Organizations. IEEE Trans. Knowl. Data Eng. 6(3): 497-499 (1994)