Содержание к диссертации
Введение
Глава 1 Управление хранимыми XML-данными , 8
1.1 Технологии платформы XML для управления данными 8
1.1.1 Язык XML, .слабоструктурированные данные и платформа XML 8
1.1.2 Модель данных XPath и XQuery 13
1.1.3 Язык путевых выражений XPath и язык запросов XQuery 15
1.2 Управление хранимыми XML-данными в полнофункциональной XML-СУБД. 21
1.2.1 Полнофункциональная XML-СУБД ...21
1.2.2 Требования к полнофункциональной XML-СУБД в контексте управления хранимыми данными 24
1.3 Подходы к хранению XML-данных 26
1.3.1 Связи между узлами: по значению или по ссылке? 26
1.3.2 Определение отношения предок-потомок и порядка документа; нумерующая схема ...28
1.3.3 Использование реляционных СУБД для хранения XML-данных 30
1.3.4 Специально разработанные методы для хранения XML-данных 31
1.4 Выводы 33
Глава 2 Метод хранения XML-данных во внешней памяти на основе описывающей схемы 34
2.1 Описывающая схема XML-документа и структурные путевые выражения 34
2.1.1 Использование описывающей схемы XML-документа для выполнения запросов, заданных в виде абсолютных структурных путевых выражений 42
2.2 Организация хранения XML-данных во внешней памяти на основе описывающей схемы 44
2.2.1. Блоки данных 46
2.2.2 Частичный порядок дескрипторов узлов 47
2.2.3 Структура дескриптора узла 48
2.2.4 Связи между дескрипторами узлов 50
2.2.5 Фиксированный размер дескриптора узла в блоке 50
2.2.6 Таблица косвенности 53
2.2.7 Хранение текстовых данных 55
2.2.8 Нумерующая схема 55
2.3 Оценка метода хранения XML-данных во внешней памяти на основе описывающей схемы 57
2.3.1 Методика оценки стоимости выполнения операций над базой данных 57
2.3.2 Оценка стоимости выполнения запросов, заданных в виде абсолютных структурных путевых выражений , 60
2.3.3 Оценка стоимости изменения данных 74
2.3.3.1 Микрооперация вставки узла 74
2.3.3.2 Микрооперация удаления узла 82
2.3.4 Навигация по документу 84
2.3.5 Экспериментальные данные 85
2.3.6 Сравнение с другими методами хранения XML-даиных 86
2.4 Выводы 87
Глава 3 Управление памятью для хранимых XML-данных и слоистая организация адресного пространства 88
3.1 О необходимости разработки единого адресного пространства базы данных для представления данных во внешней и оперативной памяти 88
3.2 Слоистая организация адресного пространства базы данных 93
3.2.1 Требования к управлению памятью для хранимых XML-данных 93
3.2.2 Слоистое адресное пространство 94
3.2.3 Страничная организация слоистого адресного пространства 98
3.2.4 Реализация слоистого адресного пространства 100
3.2.4.1 Отображение на виртуальное адресное пространство процесса * 102
3.2.4.2 Отображение на буферную память 104
3.2.4.3 Отображение на внешнюю память 106
3.2.5 Переход по указателю в слоистом адресном пространстве 107
3.2.5.1 Понятие текущей страницы 111
3.2.5.2 Переход по указателю в слоистом адресном пространстве для программиста111
3.2.6 Реализация слоистого адресного пространства в многопользовательской среде 112
3.2.7 Дополнительные возможности слоистого адресного пространства 115
3.2.8 Экспериментальные данные 117
3.2.9 Преимущества и недостатки слоистого адресного пространства 118
3.2.10 Слоистое адресное пространство и методы управления памятью,
основанные на приеме "подмены" указателей 120
3.3 Выводы 122
Глава 4 Пути доступа к XML-данным, хранимым на основе описывающей схемы... 123
4.1 Задача поиска оптимального пути доступа к данным 123
4.2 Вычисление абсолютного структурного путевого выражения с предикатом ..., 127
4.2.1 Абсолютное структурное путевое выражение с предикатом 127
4.2.2 Способы вычисления абсолютного структурного путевого выражения с предикатом 128
4.2.3 Метрика оценки стоимости и селективность путевых выражений 132
4.2.4 Оценка стоимости вычисления выражения способом "сверху-вниз" 136
4.2.5 Оценка стоимости вычисления выражения способом "снизу-вверх" 141
4.2.6 Оценка стоимости вычисления выражения способом "фильтрации с помощью нумерующей схемы" 143
4.2.7 Комбинирование способов вычисления выражения 143
4.3 Выводы 145
Заключение , 146
Литература
- Язык XML, .слабоструктурированные данные и платформа XML
- Использование описывающей схемы XML-документа для выполнения запросов, заданных в виде абсолютных структурных путевых выражений
- Слоистая организация адресного пространства базы данных
- Вычисление абсолютного структурного путевого выражения с предикатом
Введение к работе
Актуальность темы
В настоящее время язык XML используется как основное средство унифицированного представления данных различной степени структурированности и все шире применяется при обработке слабоструктурированных данных. В связи с этим возрастают и объемы накопленных XML-данных, которыми необходимо управлять. Ключевыми компонентами технологии управления XML-данными являются язык путевых выражений XPath и декларативный язык запросов XQuery. В большинстве случаев именно скорость выполнения XPath- и XQuery-запросов определяет производительность системы управления XML-данными в целом. Однако для эффективного управления большими объемами XML-данных и быстрого выполнения запросов к ним требуется решение ряда системных задач: организация XML-данных во внешней памяти, управление памятью и обработка данных в оперативной памяти. Решение этих проблем и определяет актуальность диссертационной
работы.
Цель и задачи работы
Целью диссертационной работы является исследование и разработка механизмов хранения и обработки XML-данных в рамках полнофункциональной системы управления базами данных. Для достижения этой цели были поставлены следующие задачи:
-
разработка метода хранения XML-данных во внешней памяти, эффективно поддерживающего выполнение как запросов, так и операций изменения данных;
-
разработка метода управления памятью, отражающего специфику обработки XML-данных;
-
разработка методов выполнения запросов к XML-данным и оценка их эффективности.
Научная новизна
Научной новизной обладают следующие результатылиссертапионной
Работы: і^^^м^й^яі
1 БИБЛИОТЕКА /
разработан оригинальный метод хранения XML-данных, опирающийся на описывающую схему XML документа;
разработан оригинальный механизм управления памятью, позволяющий поддерживать адресное пространство большой размерности на стандартной архитектуре процессора;
разработан оригинальный метод выполнения XPath-запросов над предложенным внутренним представлением.
Практическая значимость
Разработанные методы могут служить основой для создания систем управления XML-данными: систем интеграции данных, систем трансформации данных и систем управления базами данных. Кроме того, механизмы управления памятью могут использоваться при создании широкого класса информационных систем, которым необходимо манипулировать большими объемами данных в оперативной памяти.
На базе предложенных методов и подходов были разработаны прототипы системы хранения XML-данных и системы выполнения XQuery-запросов. Эти прототипы были использованы в качестве основы для создания в ИСП РАН производственной XML-СУБД Sedna и семейства продуктов BizQuery, в которое входит система виртуальной интеграции данных на основе XML, система трансформации XML-данных, а также процессор XQuery.
Апробация работы и публикации
По материалам диссертации опубликовано пять печатных работ [1-5]. Основные положения работы докладывались на следующих конференциях и семинарах:
на десятой международной научной конференции студентов, аспирантов и молодых ученых «Ломоносов-2003»;
на седьмой международной конференции Advances in Databases and Information Systems (ADBIS) 2003;
на первом Весеннем коллоквиуме молодых исследователей в области баз данных и информационных систем (SYRCoDIS) 2004;
на девяносто первом и девяносто седьмом семинарах Московской Секции ACM SIGMOD (2004 и 2005 гг);
на семинаре "Современные сетевые технологии" под руководством д.ф.-м.н., профессора Васенина В.А. (2005 г).
Структура и объем диссертации
Язык XML, .слабоструктурированные данные и платформа XML
Язык XML, слабоструктурированные данные и платформа XML Расширяемый язык разметки (Extensible Markup Language, сокращенно XML) [6] является подмножеством стандартного обобщенного языка разметки (Standard Generalized Markup Language, сокращенно SGML) [7]. XML изначально был разработан для представления информационных ресурсов Web нового поколения и, в частности, как замена языка гипертекстовой разметки (Hyper Text Markup Language, HTML) [8]. Язык определяется стандартом консорциума W3C [9] — сейчас действует версия XML 1.0 (третья редакция), принятая в феврале 2004 года.
При создании XML была предпринята попытка обобщения наиболее важных преимуществ и наиболее широко используемых особенностей SGML. Полученный компактный язык специально предназначался для передачи и обработки данных в Web. Одним из основных достоинств языка является расширяемость, а именно, возможность вводить свои теги разметки. Однако применение языка XML не ограничивается только областью Web, для которой этот язык создавался. В настоящее время XML активно применяется как средство обмена данными между различными приложениями и как универсальный формат представления слабоструктурированных данных [10,11].
К слабоструктурированным данным относят такие данные, в которых можно выделить некоторую структуру (в этом их отличие от аудио или видео данных), но структура этих данных не достаточно строгая для хранения их в традиционных системах (реляционных, объектно-ориентированных). Ниже перечислены основные особенности слабоструктурированных данных, которые раскрывают их сущность и определяют требования к системам управления такими данными [12].
Неявная структура. Во многих данных, хотя и имеется некоторая достаточно строгая структура, эта структура по каким-либо причинам не описывается четко и формально (как, например, схема реляционной базы данных). К таким данным относятся текстовые документы (с дополнительной разметкой) или HTML страницы на Web-серверах (в этом случае некоторое, но не полное представление о структуре могут дать теги);
Частичная структурированность. В некоторых случаях часть имеющихся данных имеет правильную структуру. Тогда для хранения этой части используются традиционные СУБД и придумываются методы связи этой части данных с оставшимися данными, которые не удалось структурировать и поэтому приходится хранить в других системах (файловая система, специализированные системы и т.п.);
Частое изменение структуры. Структура слабоструктурированных данных часто меняется, что необходимо учитывать при разработке систем, работающих с такими данными;
Апостериорная, а не априорная схема данных. Традиционные СУБД опираются на принцип фиксированной схемы данных. Поэтому сначала описывается схема базы данных, и только затем база наполняется данными (схема данных — априорная). При работе со слабоструктурированными данными целесообразно применять обратный подход — сначала заполняется база данных, а затем определяется, какую структуру она имеет, то есть при заполнении базы данных вырисовывается ее схема (апостериорная схема).
Не будет преувеличением сказать, что язык XML является сегодня стандартом de-facto представления слабоструктурированных данных. В определенном роде появление XML послужило катализатором развития систем управления базами данных, основанных на модели слабоструктурированных данных. Благодаря языку XML в сообществе баз данных возникло новое направление исследований — базы
XML-данных. О популярности этого направления можно судить по количеству докладов на ведущих конференциях по базам данных (SIGMOD [13], VLDB [14]) — более 30% работ посвящается этой тематике (больше, чем какому-либо другому направлению). Возрастает количество применений XML как формата хранения данных и в индустрии баз данных — о поддержке XML и сопутствующих стандартов в своих продуктах заявляют производители ведущих традиционных реляционных и объектно-реляционных СУБД (Oracle [15], IBM [16] и Microsoft [17]).
В настоящей работе язык XML представляет интерес именно как формат представления (слабоструктурированных) данных. Как будет сказано ниже, на базе XML построена модель данных, которая служит основой систем управления базами XML-данных. Задачи таких систем в широком смысле состоят в хранении больших объемов XML-данных во внешней памяти и их обработке, включая эффективный выбор частей XML-документов в соответствии с пользовательскими запросами, а также изменение хранимых данных.
На рисунке 1.1 представлен пример XML-документа. Тело XML-документа состоит из элементов разметки (markup) и непосредственного содержимого документа — данных, представленных в текстовой форме (content). XML-тэги предназначены для определения, элементов документа, их атрибутов и других конструкций языка. Более подробно типы узлов XML-документа рассматриваются в подразделе 1.1.3. XML-документ определяется в спецификации языка XML как объект данных, который является правильно сформированным (well-formed) в соответствии с требованиями спецификации XML. Все эти требования носят простой и естественный характер и направлены на единообразную интерпретацию XML-документа различными синтаксическими анализаторами XML; например, требуется, чтобы для каждого открывающего тэга, определяющего некоторую область данных в документе, обязательно имелся парный закрывающий тэг.
Ниже приводится список особенностей языка XML, делающих его универсальным форматом для представления (слабоструктурировашшх) данных: XML является форматом одновременно понятным и человеку и компьютеру (human readable и machine readable); XML представляет собой простой текст, свободный от лицензирования и каких-либо ограничений; благодаря поддержке Unicode [18], XML является мультиязыковым форматом; XML является платформо-независимым языком; у XML имеется строго определенный, относительно простой синтаксис, что обеспечивает его единообразную интерпретацию разными синтаксическими анализаторами; XML-данпые являются самоописываемыми, то есть определяют как структуру данных, так и значения.
Использование описывающей схемы XML-документа для выполнения запросов, заданных в виде абсолютных структурных путевых выражений
Идея описанного в этой главе метода хранения XML-данных во внешней памяти заключается в том, что для организации данных на жестком диске используется описывающая схема документа с целью минимизации количества операций ввода/вывода при выполнении запроса, сформулированного в виде абсолютного структурного путевого выражения. Для наглядной демонстрации метода рассмотрим XML-документ, показанный на рисунке 2.2, и абсолютное структурное путевое выражение /library/book/title, адресованное к этому документу. В соответствии с этим запросом необходимо выбрать все названия (title) книг (book) из библиотеки (library). Пользуясь определением путевого выражения, можно выполнить этот запрос над описывающей схемой XML-документа. Поскольку, по нашему предположению, описывающая схема умещается в оперативную память, это не составит труда. Результатом выполнения путевого выражения над описывающей схемой будет ноль или большее число узлов. В соответствии со следствием 2.1 ответ на запрос следует искать только среди узлов документа, соответствующих полученным узлам схемы. В частности, если результат представляет собой пустую последовательность (не найден ни один узел), то исходный документ также не содержит ни одного узла, удовлетворяющего путевому выражению. В нашем случае будет выбран один узел описывающей схемы, которому соответствуют, вообще говоря, несколько узлов документа. Но каким образом можно выбрать эти узлы?
Предположим, что каждый узел описывающей схемы служит точкой доступа к узлам документа, соответствующим этому узлу схемы. Например, в узле схемы может содержаться указатель на цепочку соответствующих ему узлов документа. Тогда описывающая схема играет роль универсального структурного индекса для абсолютных структурных путевых выражений. Однако наличие такого индекса само по себе не гарантирует эффективного доступа к данным. Действительно, в случае доступа к данным на жестком диске основным критерием эффективности является количество операций ввода/вывода [65]. Ведь искомые узлы (соответствующие найденному узлу описывающей схемы) могут быть разбросаны по блокам внешней памяти, и количество операций ввода/вывода при использовании описывающей схемы в качестве точки доступа может быть сопоставимо с количеством операций ввода/вывода при обходе исходного дерева документа. Поэтому XML-данные на диске должны быть организованы особым образом.
В предлагаемом подходе все узлы XML-документа хранятся в блоках внешней памяти фиксированного размера. При этом узлы XML-документа распределены по этим блокам таким образом, что в одном блоке могут находиться только узлы, соответствующие одному узлу описывающей схемы. Блоки, соответствующие одному узлу описывающей схемы (то есть те блоки, которые содержат узлы документа, соответствующие этому узлу схемы) связываются в список. Для каждого узла описывающей схемы имеется указатель на начало списка блоков, соответствующих этому узлу. Такая организация хранения обеспечивает кластеризацию XML-докумеита в соответствии с описывающей схемой этого документа.
Чтобы выполнить запрос, приведенный в начале этого подраздела, нам необходимо прочитать с диска узлы, удовлетворяющие этому запросу, включая всех потомков этих узлов, которые требуются для сериализации результата. В соответствии с описывающей схемой искомые узлы (элементы title) могут содержать в качестве потомков только текстовые узлы. Иначе говоря, для ответа за запрос необходимо прочитать те и только те блоки, которые соответствуют узлам схемы /library/book/title и /library/book/title/text(). Заметим, что ни один "лишний" блок (не содержащий искомых узлов), прочитан не будет. Более того, в ответе будут фигурировать есе узлы, хранящиеся в блоках, запланированных для чтения.
Таким образом, используя кластеризацию XML-документа на диске в соответствии с описывающей схемой, мы минимизируем количество операций ввода/вывода при формировании ответа на запрос, сформулированный в виде абсолютного структурного путевого выражения. При этом мы полагаем, что временем выполнения этого запроса на описывающей схеме можно пренебречь, так как описывающая схема мала по сравнению с документом и помещается в оперативной памяти. В этом состоит основная идея предлагаемого в работе метода организации хранения XML-данных во внешней памяти. Далее в этой главе приводятся ответы на важные оставшиеся вопросы: Каким образом на диске представляются узлы документа? Как связаны узлы между собой? К чему приводят изменения данных?
В большинстве методов хранения XML-документов во внешней памяти (в частности, описанных в главе 1) разделяется структурная и текстовая составляющие документа. В подходе, предлагаемом в этой работе, мы, помимо такого деления, вводим еще понятие описывающей схемы на уровне хранения данных. Таким образом, описываемый метод хранения оперирует тремя сущностями:
Слоистая организация адресного пространства базы данных
Требования к управлению памятью для хранимых XML-данных
Особенности метода хранения XML-данных, описанного в главе 2, предъявляют ряд требований к управлению памятью в системах, реализующих этот метод. Таким образом, прежде чем переходить к детальному описанию метода управления памятью, представленного в данном разделе, автор считает необходимым сформулировать и пояснить требования к этому методу, выдвигаемые особенностями хранения XML-данных. Именно на предмет соответствия этим требованиям будет проанализирован представленный ниже метод управления памятью.
3. Адресное пространство базы данных должно иметь размер, достаточный для представления всех сущностей базы — XML-документов, а также служебной информации, включая индексные структуры, ограничения целостности, информацию о разграничении доступа и т.п. Ориентировочные требования к размеру XML-документов, которые должна уметь обрабатывать XML-СУБД общего назначения, составляют сегодня как минимум гигабайты3. При этом желательно, чтобы не было серьезных ограничений (кроме места на жестком диске) на количество одновременно хранящихся в базе данных XML-документов. Таким образом, в выборе размера адресного пространства стоит ориентироваться на 48-ми или 64-х разрядные пространства, которые позволят адресовать всю хранимую в СУБД информацию. Забегая вперед, отметим, что сегодня большинство персональных компьютеров и многие серверы нижнего и среднего ценового уровня имеют 32-х разрядную адресацию оперативной памяти.
4. Операция разыменования указателя должна быть эффективной. В силу того, что узлы XML-документа связаны между собой указателями и переходы по указателям происходят очень часто, скорости перехода по указателю должно быть уделено особое внимание.
5. Требуется сократить накладные расходы, связанные с переключением страниц. Это требование тесно связано с предыдущим. В силу кластеризации узлов XML-документа в соответствии с описывающей схемой, многие операции (такие, как переход от отца к сыну и наоборот, в некоторых случаях переход к соседу и др.) приводят к смене текущей страницы, то есть страницы, с которой в данный момент работает транзакция. Так как параллельные транзакции конкурируют между собой за буфера оперативной памяти, требуется отслеживать и соответствующим образом разрешать ситуации, когда одна транзакция хочет вытолкнуть страницу памяти, которая является текущей для другой транзакции, — то есть требуется некоторый механизм синхронизации. И в механизме синхронизации должна учитываться та особенность, что переключение текущей страницы происходит часто.
6. Требуется сократить накладные расходы, связанные с "подменой" указателей, или полностью избеэюать их. В разделе 3.1 были показаны преимущества и недостатки приема "подмены" указателей. Метод управления памятью должен обеспечивать те же преимущества и одновременно должен бороться с недостатками.
7. Управление механизмом вытеснения блоков. Требуется, чтобы метод управления памятью обеспечивал свободу в выборе алгоритма вытеснения страниц, а не полагался, например, на алгоритмы вытеснения, применяемые в операционной системе,
Метод управления буферной памятью, рассматриваемый в данной главе, базируется на механизме виртуальной памяти операционной системы. Как уже говорилось выше, именно механизм виртуальной памяти позволяет обеспечить доступ к данным, объем которых превышает размер оперативной памяти, и в то же время позволяет быстро переходить по указателю. Однако прямому использованию виртуального адресного пространства, предоставляемого операционной системой, для представления объектов базы данных может препятствовать размер виртуального адресного пространства.
Действительно, подавляющее большинство вычислительных машин, которые используются в качестве серверов баз данных в настоящее время, имеют 32-х разрядную архитектуру, а значит и 32-х разрядную адресацию памяти. Это означает, что объем памяти, адресуемой процессом выполнения, составляет 4 Гбайт, что явно недостаточно для представления всех сущностей современной базы данных. Для решения этой проблемы было предложено слоистое адресное пространство (САП).
Замечание 3.2 В дальнейшем все рассуждения касаются вычислительной машины с 32-х разрядной адресацией. При этом предполагается, что для адресации объектов в памяти используются указатели размером 4 байта (32 бита), и размер памяти, отводимой для хранения целых чисел (тип int в языке С), также составляет 4 байта (32 бита).
Идея слоистой организации адресного пространства базы данных, которая составляет основу рассматриваемого в этой главе метода управления памятью, заключается в создании собственного механизма виртуальной памяти над виртуальной памятью операционной системы, который позволял бы адресовать сколь угодно большое (заранее заданное) количество объектов базы данных.
Вычисление абсолютного структурного путевого выражения с предикатом
Общая идея вычисления абсолютного структурного путевого выражения с предикатом состоит в следующем. Описывающая схема XML-документа позволяет осуществить быстрый переход как к целевым узлам документа, так и к предикатным узлам. Однако для фильтрации целевых узлов по предикатным узлам необходимо установить отношение предок-потомок, что можно сделать несколькими способами. Учитывая возможности описанного в главе 2 представления XML-данных во внешней памяти, можно выявить следующие способы вычисления Р (рисунок 4.1). "Сверху-вниз" {top-down). Находим узлы документа, удовлетворяющие абсолютному структурному путевому выражению Pg, и для каждого полученного узла xg вычисляем относительное структурное путевое выражение Рг. Выражение Рг вычисляется в контексте узла xg, и поэтому используются указатели на первых "детей по схеме". Для каждого узла хр, полученного в результате вычисления выражения Рп проверяется предикат. Если хотя бы один из узлов хр удовлетворяет предикату, то узел xg удовлетворяет абсолютному структурному путевому выражению с предикатом Р. Необходимо отметить, что если у узла xg имеется несколько узлов-потомков хр, то после нахождения первого узла хр, удовлетворяющего предикату, нет необходимости проверять предикат для всех оставшихся узлов хр. Данный способ вычисления Р, является, пожалуй, наиболее очевидным и естественным, учитывая то, что XML-документ представляет собой дерево узлов, связанных между собой указателями; однако далеко не всегда он оказывается самым быстрым. "Снизу-вверх" (bottom-up). Находим узлы документа, удовлетворяющие абсолютному структурному путевому выражению Рр, и для каждого полученного узла хр вычисляем предикат. Для тех узлов хр, которые удовлетворяют предикату, выполняем переход посредством косвенного указателя на родителя к узлу-предку xgt который соответствует узлу описывающей схемы dxs. При этом попутно производится удаление дубликатов, так как нескольким узлам хр, вообще говоря, может соответствовать один узел xs. "Фильтрация с помощью нумерующей схемы" (numbering scheme based filter). Находим узлы документа, удовлетворяющие абсолютному структурному путевому выражению Рр, и для каждого полученного узла хр вычисляем предикат. Независимым образом находим узлы документа xg, удовлетворяющие абсолютному структурному путевому выражению Pg. Выполняем фильтрацию узлов xs по наличию у них узла-потомка (узлов-потомков) хр, удовлетворяющих предикату. Фильтрация осуществляется с использованием нумерующей схемы.
Проиллюстрируем описанные три способа выполнения абсолютного структурного путевого выражения с предикатом на запросе (4.1). Метод "сверху-вниз" предполагает вычисление абсолютного структурного путевого выражения /library/book, а затем для каждого выбранного элемента book — вычисление относительного путевого выражения issue/year. В результат попадают только те элементы book, для которых значение year равно 2005. Метод "снизу-вверх" предполагает выполнение абсолютного структурного путевого выражения /library/book/issue/year, проверку предиката и, наконец, вычисление выражения ../.. для узлов year, успешно прошедших проверку. Метод "фильтрации с помощью нумерующей схемы" предполагает фильтрацию узлов, удовлетворяющих абсолютному структурному путевому выражению /library/book, по наличию у них потомков, удовлетворяющих абсолютному структурному путевому выражению /library/book/issue/year с условием равенства содержимого узлов числовому значению 2005. Фильтрация производится при помощи нумерующей схемы документа.
Следует отметить, что не имея никаких сведений о хранимых данных, вообще говоря, невозможно определить, какой из способов вычисления является лучшим. Действительно, опишем на идейном, неформальном уровне три гипотетические ситуации, в каждой из которых оптимальным будет соответствующий способ вычисления выражения.
Пусть узел dxg является родителем узла dxp (рисунок 4.2а), у каждого из узлов xg имеется большое количество детей Хр, и предикат, налагаемый на узлы хр, имеет малую селективность, то есть многие из узлов хр удовлетворяют этому предикату. При вычислении Р способом "сверху-вниз" будут прочитаны все узлы xR и только часть узлов Хр, так как если для данного узла xg уже нашелся узел хр, удовлетворяющий предикату, то можно пропустить всех непрочитанных детей узла xg и переходить к следующему узлу xg. Так как dxg является родителем узла dxp, то никаких других узлов читать не требуется. Способы вычисления Р "снизу-вверх" и "фильтрации с помощью нумерующей схемы" требуют прочтения всех узлов xg и Хр, плюс некоторых записей таблицы косвенности (при переходе к родителю) и нумерующих чисел вне дескриптора узла (если нумерующие числа хранятся вне дескриптора узла).
Пусть узел dxg является родителем узла dxp (рисунок 4.2Ь), лишь немногие из узлов xg имеют в качестве детей по одному узлу Хр, и селективность предиката на узлы хр высокая. При вычислении Р способом "снизу-вверх" будут прочитаны все узлы хр и только небольшая часть узлов xg, для которых дети удовлетворяют предикату. Способы вычисления Р "сверху-вниз" и "фильтрации с помощью нумерующей схемы" требуют прочтения всех узлов Xg и Хр. Таким образом, в случае, когда расходы на чтения записей таблицы косвенности при вычислении выражения способом "снизу-вверх" ниже, чем чтение всех узлов Xg, данный способ обеспечивает преимущество относительно двух других способов вычисления Р.
Пусть узлы dxg и dxp разделяет большое количество других узлов (рисунок 4.2с), узлов Xg и Хр достаточно много (и тех и других), и селективность предиката на узлы хр средняя. В этом случае способ вычисления Р "фильтрацией с помощью нумерующей схемы" обладает преимуществом перед двумя другими способами за счет возможности определять отношение предок-потомок между двумя узлами за константное время, без необходимости читать узлы документа, находящиеся между узлами Xg и хр, что, так или иначе, необходимо при использовании любого из двух других способов.
Таким образом, каждый из описанных выше способов вычисления абсолютного структурного путевого выражения с предикатом может быть оптимальным в зависимости от конкретных экземпляров данных. Следовательно, выбор лучшего способа вычисления должен полагаться на оценку стоимости плана выполнения запроса, реализующего указанный способ. Построению такой оценки будут посвящены следующие подразделы.
Похожие диссертации на Исследование и разработка методов организации выполнения и физической оптимизации запросов к XML-данным
