Низкая цена
Всего 249a за скачивание одной диссертации
Скидки
75 диссертаций за 4900a по акции. Подробнее
О проекте

Электронная библиотека диссертаций — нашли диссертацию, посмотрели оглавление или любые страницы за 3 рубля за страницу, пополнили баланс и скачали диссертацию.

Я впервые на сайте

Отзывы о нас

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

Год: 2005

Номер работы: 84012

Автор:

Стоимость работы: 249 e

Без учета скидки. Вы получаете файл формата pdf

Оглавление и несколько страниц
Бесплатно

Вы получаете первые страницы диссертации в формате txt

Читать онлайн
постранично
Платно

Просмотр 1 страницы = 3 руб



Оглавление диссертации:

Первая

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

главах.

1.1 Технологии платформы 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 (третья редакция),

Системы управления базами данных строятся на основе модели данных, которая определяет совокупность правил структурирования данных в базах данных, допустимых операций над ними и ограничений целостности, которым они должны удовлетворять; механизмы каждой СУБД конструируются на основе той или иной модели данных, реализуя комплекс языковых средств определения данных и манинулирования данными, воплощающих концепции модели [29]. Для XMLориентированных СУБД (или нросто XML-СУБД) модель данных' описы

В настоящее время основным языком запросов к XML-данным является язык XQuery. XQuery для XML является тем же, чем язык запросов SQL является для реляционных 15 данных. Язык XQuery происходит от языка Quilt [31], создателем которого является Дон Чемберлип (Don Chamberlin) — соавтор SQL. Спецификация языка XQuery неразрывно связана с языком путевых выражений XPath и во многом на пего опирается. Назначение языка XPath состоит в адресации структурных частей документов. Выражение языка XPath назыв

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

Как говорилось в разделе

1.1, под системой управления базами XML-данных (XMLориентированной СУБД, или просто XML-СУБД) понимается СУБД, основанная на модели данных XPath и XQuery, XML-СУБД должна поддерживать язык путевых выражений XPath и язык запросов XQuery. Определение СУБД, как программной системы, предназначенной для создания и хранения базы данных на основе некоторой модели данных, обеспечения логической и физической целостности содержащихся в ней данных, надежного и эффективного

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

в настоящем разделе мы сначала остановимся на двух важных задачах, которые приходится решать при проектировании структур хранения XML-данных: • обеспечение связи между узлами XML-документа; • индивидуальность узлов и поддержка порядка документа. Затем мы рассмотрим два принципиально разных подхода к хранению XML-данных: • использование ипфраструктуры реляционных баз данных для хранения XMLданных; • разработка так называемых прирожденных (native) XML-СУБД, которые создаются специально для хран

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

1.3.2 Определение отношения предок-потомок \л порядка документа: нумерующая схема Особенности модели данных XPath и XQuery, заключающиеся в древовидности структуры данных и упорядоченности узлов дерева, обуславливают необходимость реализации средств, позволяющих легко устанавливать иерархические связи между узлами (предок-потомок или отец-сып), а также сравнивать два узла в соответствии с порядком их следования в документе. Для рещения подобных задач используется сопоставление узлов с уникаль

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

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

Популярность и активное использование тех1юлогий платформы XML приводит к росту объемов XML-данных, которые необходимо хранить, запрашивать и изменять. Это, в свою очередь, создает предпосылки для возникновения нового класса систем управления базами данных, основанных на модели данных XPath и XQuery, — XMLСУБД. В настоящей главе проведен анализ существующих методов и подходов к организации структур хранения XML-данных во внешней памяти, выработапы требовапия к полнофункциональной системе упра

Настоящая

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

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

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

2.2, и абсолютное структурное путевое выражение / l i b r a r y / b o o k / t i t l e

в большинстве методов хранения XML-дoк)/мeнтoв во внешней памяти (в частности, описанных в главе

1) разделяется структурная и текстовая составляющие документа. В подходе, предлагаемом в этой работе, мы, помимо такого деления, вводим еще понятие описывающей схемы па уровне хранения данных. Таким образом, описываемый метод хранения оперирует тремя сущностями: • Описывающая схема XML-документа. Описывающая схема представляет собой скелет XML-документа, то есть схематично показывает возмо

2. Хранение текстовой части XMLдокумента обсуждается в подразделе

2.2.7. element library ^^-••' text text Ч Рисунок

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

2.3). Блоки, в свою очередь, содержат дескрипторы узлов документа, соответствующих д

2.2.1. Блоки данных Все блоки, используемые для хранения дескрипторов узлов, организованы одинаковым образом. Они имеют фиксированный размер, в начале каждого блока расположен заголовок этого блока, а оставшуюся часть блока занимают дескрипторы узлов. Заголовок блока содержит следующую информацию: L Указатели на предыдущий одному и узлу 46 последующий соседние схемы, блоки. Блоки, в соответствующие описывающей связаны двунаправленный список, и необходимо иметь средства для перехода к соседним

Многие конструкции языков запросов XPath и XQuery опираются на понятие норядка документа, рассмотренного в главе 1. Таким образом, для эффективного выполнения запросов, чтобы избежать нромежуточных сортировок для восстановления порядка документа, требуется поддержка порядка документа на уровне хранения. В соответствии с этим требованием, для дескрипторов узлов, соответствующих одному узлу описывающей схемы, должен поддерживаться порядок документа. Однако для упрощения операции изменения данны

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

2.2.3 Структура дескриптора узла Общая структура дескриптора узла для всех типов узлов XML-документа показана на рисунке

2.4. Дескриптор узла имеет следующие поля: 48 1. Левый сосед и правый сосед (left sibling и right sibling соответственно) — "длинные" указатели, ссылающиеся на левого и правого соседей соответственно; 2. Следующий в блоке и предыдущий в блоке (next in block и previous in block соответственно) — "короткие" указат

Дескринторы узлов, а также некоторые другие сущности (например, блоки с дескрипторами) связываются между собой указателями. Указатели бывают двух типов: (1) "короткие" указатели и (2) "длиппые" указатели, или просто указатели, "Короткие" указатели используются для ссылок в пределах одного блока и представляют собой смещение в этом блоке. Размер "коротких" указателей относительно мал — 16-ти бит достаточно для блоков размером 64 Кбайта. "Длинные&quo

2.2.5 Фиксированный размер дескриптора узла в блоке Одпа из осповных задач при проектировании дескрипторов узлов заключалась в том, чтобы сделать их фиксированного размера. Это имеет ключевое значение для операций изменения данных, так как существенно упрощает учет свободного места в блоке и вставку узлов. Из рисунка

2.4 следует, что количество детей у узла XML-документа — это именно тот параметр, из-за которого размер дескриптора может варьироваться. Очевидпо, что дескрипторы не всех у

2.2.6 Таблица косвенности Как отмечалось в подразделе

2.2.4, наличие физических указателей на узлы по указателю, однако приводит к в случае изменения данных. В случае изменения благотворно влияет на скорость перехода определенным трудностям положения узла все другие ссылающиеся на него объекты должны быть также изменены, чтобы отразить новое положение измененного узла. Изменение положения узла может вызываться следующими причинами: 1. Сдвиг узлов при вставке другого узла с целью сохран

2.2.7 Хранение текстовых данных Текстовая составляющая XML-документа представляет собой набор строк переменной длины, которые хранятся в блоках внешней памяти. Хранение строк неременной длины в базе данных является сложной, но хорошо изученной задачей, для которой существует устоявшееся решение — слоттированные страницы {slotted page) [68]. В предлагаемом в настоящей работе методе хранения XML-данных не нредъявляются какие-либо особые требования к хранению строк, и поэтому разумно использоват

2.2.8 Нумерующая схема Предлагаемый в работе метод организации хранения XML-данных во внешней памяти, вообще говоря, методе ортогонален используемой схема нумерующей снособствует схеме. В рассматриваемом хранения нумерующая решению традиционных задач, включающих поддержку выполнения операций XPath и XQuery, опирающихся на понятие порядка документа. Среди более специфичных задач можно выделить поддержку операции слияния (см. подраздел

2) и различных способов выполнения XPath-запросов с предикатами (см. главу 4). Тем не менее, оценки стоимости операций изменения данных, приводимые в настоящей работе (см. подраздел

2.3.3), могут быть получены только для неперестраиваемой нумерующей схемы (см. классификацию нумерующих схем в главе 1). В реализации рассматриваемого метода хранения в рамках XML-СУБД Sedna использовалась префиксная неперестраиваемая нумерующая схема SLS [49], предложенная коллегами автора. Эта нумерующая с

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

2.3.1 Методика оценки стоимости выполнения операций над базой данных Прежде, чем оценивать эффективность метода хранения XML-данных во внешней памяти, представленного в этой главе, необходимо ввести метрику, которая будет использоваться для решения поставленной задачи. В вопросе выбора метрики научное сообщество в области баз данных имеет единодушное мнение. Последние 25 лет эталонной формулой оценки стоимости выполнения запроса является формула, введенная Патрицией Селинджер в процессе разра

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

2.1.1, и описание структур хранения XML-данных из раздела

2.2, мы сформулируем алгоритм выполнения запросов, заданных в виде абсолютных структурных путевых выражений. Для достижения этой цели требуется ввести и обсудить несколько операций. Операция перехода к сосе

2.3.3 Оценка стоимости изменения данных Принятый в этой работе подход к модификации XML-данных опирается на тот факт, что любую модификацию XML-документа можно выразить через последовательность операций вставки и/или удаления узлов. Далее в работе эти операции носят названия микроопераций вставки/удаления узлов (это название они получили в противовес (более крупным) онерациям изменения данных языкового уровня (например, [39,40]), которые позволяют манипулировать часть подраздела несколькими п

3.1 Микрооперация вставки узла В комплексе стандартов XML Query не определяется понятие операции изменения XML-данных вообще и онерации вставки узла, в частности. На интуитивном уровне под вставкой узла в XML-документ мы понимаем изменение XML-документа таким образом, чтобы результирующий XML-документ донолнительно к узлам исходного документа, находящимся в прежних структурных отношениях, содержал вставляемый узел в заданной позиции. При этом уникачьные идентификаторы {node identity) узлов ис

3.2 Микрооперация удаления узла Удаление узла из XML-документа определяется аналогично операции вставки узла, то есть на интуитивном уровне под удалением узла из XML-документа понимается изменение XML-документа таким образом, чтобы результирующий документ содержал все узлы исходного документа в тех же структурных отношениях, кроме заданного узла, который отсутствует в результирующем документе. В дальнейшем мы рассматриваем операцию удаления содержащего потомков. Для последовательностью операц

2.3.4 Навигация по документу Оценим метод хранения XML-данных на основе описывающей схемы с позиции навигации по документу. Устройство дескриптора узла (см. подраздел

2.2.3) позволяет 84 естественным образом осуществлять переход к узлам документа в ближайшей окрестности рассматриваемого узла: левому и правому соседям, первым детям "по схеме" и родителю. Переход к соседним узлам и дочерним узлам представляет собой разыменование указателя, а переход к родителю — разыменование ко

2.3.5 Экспериментальные данные Оценки, полученные для метода хранения XML-данных на основе описываюшей схемы, формально обоснованы. Реализация этого метода, выполненная в рамках работы над XML-СУБД Sedna, подтверждает их правильность. Результаты тестов производительности доступны на сайте проекта [35] в разделе Benchmarks. Минимальное число модифицированных блоков 2 Максимальное число модифицированных блоков 97 Среднее число модифицированных блоков

6.74 Рисунок

2.15 Результаты те

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

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

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

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

3.1 о необходимости разработки единого адресного пространства базы данных для представления данных во внешней и оперативной памяти Как уже обсуждалось в главе 1, в системах управления данными, ориентированных на навигационный подход, обычно используется понятие указателя даже на модельном уровне, К таким системам отгюсят иерархические, сетевые и объектноориентированные СУБД. Вполне естественно, что при реализации этих систем для представления указателей модельного уровня используются указател

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

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

3.2.2 Слоистое адресное пространство Метод управления буферной памятью, рассматриваемый в данной главе, базируется на механизме виртуальной памяти операционной системы. Как уже говорилось выще, именно механизм виртуальной памяти позволяет обеспечить доступ к данным, объем которых превышает размер оперативной памяти, и в то же время позволяет быстро переходить по указателю. Однако прямому использовапию виртуального адресного пространства, предоставляемого операционной системой, для представлен

4 будет подробно рассмотрен вопрос выбора размера слоя, однако сейчас стоит сказать, что на практике уместно использовать слои размером ~1 Гбайт. Как и в любом адресном пространстве, в САП также вводится понятие адреса, который определяется следующим образом. Определение

3.2 Адресом в слоистом адресном пространстве называется пара (layer, addr), где layer — номер слоя (представляет собой целое число) и addr — адрес объекта в этом слое (представляет собой указатель). Замечание

3.3

4, такой выбор значений addr обусловлен потребностью отображепия адреса САП (xptr) в адресное пространство процесса путем отбрасывания первой части xptr (а именно layer). Значения pxwpi заранее на этапе реализации (что подробно обсуждается 96 выбираются позднее) и являются (

3.1) одинаковыми для всех слоев. Необходимо отметить, что на практике значение pi всегда отлично от нуля в силу того, что начало адресного пространства процесса (и в частности, нулевой адрес) зарезервированы операци

3.2.3 Страничная организация слоистого адресного пространства Слоистое адресное пространство предназначено, прежде всего, для объектов базы данных, а не для программ пользователей (в том числе и тех, которые управляют объектами базы данных). То есть программы, которые призваны работать с объектами базами данных (а это, прежде всего, подсистема выполнения занросов и другие утилиты) совершенно не обязаны размещать свой код и локальные данные в САП. Они могут быть размещены в виртуальной памяти,

4, а здесь мы ответим на второй вопрос. Когда говорят про оперативную память или виртуальную память, подразумевают, что данный ресурс видится пользователю как единый непрерывный кусок памяти, в котором принята последовательная адресация. Пользователь может завести в памяти объект произвольного размера (естественно, размер объекта не должен превышать размер памяти) и адресовать любую часть этого объекта посредством указателя па объект и смещения до этой части объекта. Система же должна обеспеч

5, САП сохранит возможность быстрого перехода по указателю, как в виртуальном адресном пространстве, плюс будет иметь размер, существенно превосходящий размер виртуального адресного пространства.

3.2.4 Реализация слоистого адресного пространства САП реализуется через отображение на виртуальное адресное прострапство процесса. В реализации САП должны учитываться три основных момента: 3. Как указывалось в предыдущем нодразделе, САП предназначено для объектов базы данных, а не для размещения кода и локальных данных программ, управляющих объектами базы данных. Поэтому нужно уметь совмещать САП и адресное пространство процесса; 4. Как говорилось в разделе

3.1, использование приема &qu

1 требования эффективного перехода по указателю. Пользовательская сессия 1 (layer, addr) Слоистое адресное пространство — addr Область отображения САП Виртуальное адресное пространство процесса \^ MapViewOfFile (Windows) mmap (Linux) Буферная память VirtualLock (Windows) miock (Linux) Менеджер буферной памяти Диск layer* s + {addr-p\ Рисунок

3.3 Реализация слоистого адресного пространства Мы будем исходить из того, что система управления базами данных имеет следующую архитектур

4.1 Отображение на виртуальное адресное пространство процесса Чтобы транзакция имела возможность работать с объектами САП, необходимо уметь отображать страницы САП на виртуальное адресное пространство процесса. При этом под виртуальным адресным пространством процесса попимается именно набор адресов, который в случае 32-х разрядной архитектуры вычислительной машины расположен в диапазоне 0x00000000 - OxFFFFFFFF. Важно подчеркнуть, что под виртуальным адресным пространством понимается именно ре

4.2 Отображение на буферную память Для обеспечения работы со страницей САП она должна быть загружена в оперативную память. Для этого используется память, которая является совместно доступной для всех пользовательских сессий и мепеджера буферной памяти. На рисунке

3.3 она обозначена как буферная память. Пользовательские сессии не имеют собственной памяти, в которой располагаются страницы САП, — они обязаны работать с общей памятью. Таким образом, мы избегаем возникновения копий одних и т

4.3 Отображение на внешнюю память Отображение САП на внешнюю память не представляет никакой сложности. В простейщем случае САП отображается на файл базы данных. Тогда для страницы с адресом xptr = (layer, addr) смещение в файле определяется по формуле (см. рису1юк

3.3) / = layer • S + {addr -

рх) где S — размер слоя САП, р\ — левая граница области отображения САП. При необходимости можно применять различные методы кластеризации блоков внешней памяти, использовать для хранения базы

3.2.5 Переход по указателю в слоистом адресном пространстве Переход по указателю (или разыменование указателя) САП xptr = (layer, addr) заключается в том, что обеспечивается адрес виртуального адресного пространства процесса, по которому доступен данный объект. Используя этот адрес, программа может совершать все те же действия пад объектом, как если бы объект находился не в САП, а в виртуалыюм адресном пространстве процесса. В соответствии с правилами отображения САП на виртуальное адресное п

5.1 Понятие текущей страницы Иногда может возникнуть такая ситуация, что по логике программы необходимо работать то с одной страницей xptrl = (layerl, addr), то с другой страницей xptr2 = (1ауег2, addr), причем эти страницы имеют одинаковое смещение в слое (addr), но разные слои (layerl и 1ауег2), то есть отображаются на один адрес виртуального адресного пространства. Очевидно, что для обеих страниц одновременно не может существовать отображение в адресное пространство процесса. Однако благод

5.2 Переход по указателю в слоистом адресном пространстве для программиста Чтобы проиллюстрировать, что представляет собой САП и переход по указателю в САП для программиста, обратимся к следующему примеру. На рисунке

3.5 представлена реализация функции d m : p a r e n t из модели данных XPath и XQuery с 111 учетом внутреннего представления хранимых XML-данных представленного в главе 2. В качестве аргумента функция получает указатель на дескринтор узла XMLдокумента в САП. Макрос GETPAREN

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

3.2.4, у каждой пользовательской сессии имеется свое адресное пространство, то есть выполняющиеся транзакции не конфликтуют за адреса области САП. Иначе говоря, разные транзакции могут работать с произвольными страницами (даже теми, которые имеют одинаковые смещения в слое, но разные номера слоев), не мешая одна другой но адресам. Однако нараллельные транзакции конкурируют за буфе

3.2.7 Дополнительные возможности слоистого адресного пространства В данном подразделе мы рассмотрим дополнительные возможности САП, которые могут быть полезны при разработке программ над САП. В зависимости от логики запроса в СУБД некоторые блоки с данными могут иснользоваться только для чтения, а некоторые как для чтения, так и для записи. В случае, когда на блок с данными изменяется, необходимо диск. Использование САП может пометить блок как образом измененный, чтобы при вытеснении этого бл

3.2.8 Экспериментальные данные Подсистема управления памятью требуется не сама по себе, а для обеспечения функционирования других подсистем (в нашем случае, подсистемы выполнения запросов). Поэтому имеет смысл тестировать управлепие памятью в рамках той системы, для которой она предназначена, — в нашем сл5Д1ае это система управления XML-данными, опирающаяся на метод хранения данных из главы 2. В подразделе

3.2.5 было теоретически показано преимущество САП над методами "подмены"

3.2.9 Преимущества и недостатки слоистого адресного пространства Мы завершили описание метода слоистой организации адресного пространства базы данных и готовы подвести итоги. Основным итогом является следующее утверждение. Утверждение

3.3 Метод слоистой организации адресного пространства базы данных исключает операцию "подмены" указателей. Доказател ьство Истинность данного утверждения следует из утверждения

3.1 и из описапия метода слоистой организации адресного про

3.2.10 Слоистое адресное пространство и методы управления памятью, основанные на приеме "подмены" указателей Развитие методов управления памятью, использующих прием "подмены" указателей, исторически связано с появлением объектно-ориентированных баз данных. Потребность в хранении объектов во внешней памяти и обеспечении прозрачного доступа к этим объектам из пользовательских программ привело к созданию специализированных систем унравления данными и оригинальных методов упра

3.3 Выводы Основной вывод данной главы заключается в том, что прием "подмены" указателей является не едипственным способом борьбы за скорость перехода по указателю в базах дапных. Автором предложен метод управления памятью, который демонстрирует производительность не хуже, чем методы, основанные на "подмене" указателей. При этом предложенный метод предоставляет единое громадное адресное пространство для всех объектов базы данных. Кроме того, метод свободен от недостатков,

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

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

4.1 Задача поиска оптимального пути доступа к данным Как говорилось в главе 1, языки XPath и XQuery являются декларативными, то есть запрос, выраженный на любом из этих языков, не содержит в себе алгоритма выполнения, и, вообще говоря, возможно несколько способов его выполнения. Поиск оптимального по некоторым критериям алгоритма выполнения запроса составляет задачу оптимизации запросов к данным. Известпо, что в зависимости от качества решения этой задачи, время выполнения запросов может отли

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

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

4.2.2 Способы вычисления абсолютного структурного путевого выражения с предикатом Рассматривая снособы вычисления абсолютного структурного нутевого выражения с нредикатом, мы будем руководствоваться возможностями вводить структур данных, описанных в главе онтимальным 2, иначе говоря, не будем поиска узлов и/или использовать удовлетворяющих донолнительные структуры данных такие, как индексы. Также мы будем считать, что способом XML-документа, абсолютному структурному путевому выражению, являе

4.2.3 Метрика оценки стоимости и селективность путевых выражений Оптимальным планом вынолнения занроса нолагается нлан, который имеет наименьшую стоимость. Для оценки стоимости нланов выполнения занроса необходима единая метрика. В главе 2 уже вводилось понятие стоимости алгоритма (или плана) выполнения занроса, в соответствии с которым стоимость измеряется количеством обменов с внешней намятью (онределение

2.10). Этой же метрикой мы будем руководствоваться и далее в этой главе. к сож

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

4.1 Пусть некоторому узлу dx описывающей схемы XML-документа соответствует т узлов. Пусть узлу dy, являющемуся непосредственным нотомком узла dx, соответствует тг узлов, причем эти узлы равномерно распределены между узлами, соответствующими узлу схемы dx

4.2.5 Оценка стоимости вычисления выражения способом "снизувверх" В настоящем подразделе выводится оценка стоимости вычисления абсолютного структурного путевого выражения с предикатом способом "снизу-вверх". Сначала рассмотрим частный случай, когда узел онисывающей схемы dxp является дочерним узлом узла dXg. Пусть dXp соответствуют Пр узлов документа, которые равномерно распределены по Ьр блокам, dXg — Ug узлов, которые равномерно распределепы но bg блокам, и ссылки на эти

в настоящем подразделе выводится оценка стоимости вычисления абсолютного структурного путевого выражения с предикатом способом "фильтрации с помощью нумерующей схемы" при соблюдении условий (*) из подраздела

4.2.4. Следуя рассматриваемому способу вычисления выражепия, мы должны прочитать все узлы, соответствующие dxp, и проверить для них предикат. Очевидно, что стоимость выполнения этой операции Ь, (так как мы вынуждены прочитать все блоки). Также требуется прочитать все узлы,

В подразделе

4.2.2 были сделаны ограничивающие предположения относительно Pg и Рр, а именно, что результатом применения Pg к dX является единственный узел dXg, а результатом применения Рр к dX — узел dXp. В этом подразделе ограничения. мы сформулируем принцины, позволяющие снять поставленные Пусть результатом применения Pg к dX будет набор из п узлов описывающей схемы dXg,dxl,...,dXg. Тогда для каждого узла dx'g,i = hn можно произвести поиск оптимального способа вычисления предик