Помощь в написании студенческих работ
Антистрессовый сервис

Исследование и разработка методов организации выполнения и физической оптимизации запросов к XML-данным

Диссертация: Исследование и разработка методов организации выполнения и физической оптимизации запросов к XML-данным
ДиссертацияПомощь в написанииУзнать стоимостьмоей работы

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

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

Содержание

  • Актуальность темы
  • Цель и задачи работы
  • Основные результаты работы
  • Научная новизна работы
  • Практическая значимость
  • Доклады и печатные публикации
  • Структура и объем диссертации
  • Краткое содержание работы
  • Глава 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-данными являются язык путевых выражений 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-запроса с предикатом, основанный на оценке стоимости возможных планов выполнения данного запроса.

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

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

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

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

Показать весь текст

Список литературы

  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-19 980 210
  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 -19 991 224
  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, 117 121
  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 10 646: 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-19 990 114
  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−20 041 028/
  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-20 051 103/
  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-20 050 915/
  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)
Заполнить форму текущей работой

Сессия? Спокойно!