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

• Автор: Лукичев, Максим Сергеевич
• Шифр специальности: 05.13.11
• Научная степень: Кандидатская
• Год защиты: 2009
• Место защиты: Санкт-Петербург
• Количество страниц: 120 с. : ил.

Оглавление

1. Методы и средства обработки запросов

1.1. Модель данных X и язык запросов X

1.1.1. Модель данных X

1.1.2. Язык X

1.1.2.1. Навигационные выражения.

1.1.2.2. Элементарные операции.

1.1.2.3. выражения.

1.1.2.4. Условные и кванторпые выражения.

1.2. Основные принципы оптимизации запросов

1.2.1. Основные понятия.

1.2.2. Основные элементы оптимизатора.
1.2.3. Алгоритмы поиска оптимального плана
1.2.3.1. Алгоритм динамического программирования.
1.2.3.2. Стохастические алгоритмы поиска.
1.3. Основные методы выполнения.
1.3.1. Методы сортировки и хэширования для больших объмов данных
1.3.1.1. Сортировка
1.3.1.2. Хэширование.
1.3.2. Алгоритмы соединения.
1.3.2.1. Алгоритм вложенных циклов.
1.3.2.2. Алгоритм сортировки и слияния.
1.3.2.3. Алгоритм хэширующего соединения.
1.3.3. Прямое и обратное вычисление навигационного выражения.
1.3.4. Структурное соединение.
1.3.5. Целостное соединение.
1.4. Xалгебры
1.4.1. Обзор и классификация Xалгебр
1.4.2. Анализ требований к алгебре для высокопроизводительного оптимизатора.
1.5. Выводы.
2. Алгебра Х3иегузапросов X
2.1. Структуры данных алгебры.
2.2. Основные операции алгебры .
2.2.1. Базисные операции.
2.2.2. Дополнительные операции.
2.3. Основные тождества операций
2.4. Построение алгебраического выражения.
2.4.1. Нормализация запроса
2.4.2. Трансляция в выражения алгебры
2.5. Оптимизация
2.5.1. Изменение порядка блоков
2.5.2. Исключение избыточных операций
2.5.3. Преобразования, обеспечивающие ленивые вычисления.
2.6. Обсуждение.
2.7. Выводы.
3. Эффективные методы поиска оптимального плана
3.1. Основные понятия.
3.1.1. Модель стоимости
3.1.2. Граф классов частичных планов.
3.1.3. Блочный алгоритм
3.2. Оптимизация для ХСиегу
3.3. Выводы.
4. Прототип исполнителя запросов и численные эксперименты
4.1. Прототип исполнителя запросов ХЛнвиег.
4.1.1. Организация хранилища данных и исполнителя запросов СУБД еХ1Б1
4.2. Постановка экспериментов
4.2.1. Эталонный набор данных и запросов ХМагк.
4.2.2. Описание экспериментов
4.3. Выводы.
Введение
Актуальность


В четвёртой главе представлены описание прототипа исполнителя запросов на основе алгебры XAnswer, постановка экспериментов и анализ результатов. За последнее десятилетие XML [] приобрёл значительное распространение как универсальное средство обмена данными, став одним из основных стандартов обмена информации между информационными системами. В результате существенного роста размера ХМL-данных появилась острая необходимость в создании эффективных и удобных методов извлечения данных. Это стало предпосылкой для появления таких языков, как Lorel, Quilt, XQL, XMIv-QL, XPath и XQuery (). Наибольшую популярность среди них получили XQuery [] и его подмножество XPat. XML Query Working Group в World Wide Web Consortium (W3C). Первая группа- (document community), в основном была заинетере-сована в использовании XML как попятного и читаемого формата передачи данных. Наиболее важным для них является разработка новых инструмет-ов для более удобного управления и трансформации относительно небольших XML документов. Вторая группа, (data community) рассматривает XML в основном как формат хранения данных, фокусируясь на разработке языков запросов и методов хранения для эффективного поиска в очень больших объёмах XML данных. Модель данных XML. Основным понятием модели данных XML является понятие последовательности (sequence) []. Последовательность представляет собой упорядоченный набор элементов (item), при этом набор может быть пустым. Каждый элемент может быть либо узлом (node), либо атомарным значением (atomic value). Атомарное значение является экземпляром атомарного типа данных, который в свою очередь является либо одним из -х базовых типов [], таких как строки, целые и десятичные числа, либо получен в результате сужения другого атомарного типа. Каждый узел может принадлежать одному из семи типов: доку-мент(document), элелюнт (clement), атрибут (attribute), текст (text), область видимости (namespace), команда обработки (processing instruction) и комментарий (comment). В зависимости от типа узлы могут иметь другие узлы в качестве детей, что позволяет организовать узлы в иерархию. При этом, каждый узел обязан иметь уникальный идентификатор и не допускается наличие двух детей с одинаковым идентификатором. Элементы и атрибуты имеют имена и типизированные значения, представляющие собой последовательность из нуля или большею числа атомарных значений. Все узлы иерархии находятся в определённом порядке,называемом порядком документа (document, order), в котором следовали бы узлы, если бы иерархия узлов представлялась в виде XML. Несмотря на то, что порядок документа узлов различных иерархий определяется в реализации, он обязан быть последовательным, то есть все узлы одной иерархии должны располагаться либо до, либо после всех узлов в другой иерархии. При этом порядок некоторой последовательности может быть отличен от порядка документа. Однако, одна последовательность не может быть элементом другой. Последовательность, содержащая единственный элемент (то есть узел или атомарное значение) считается идентичной этому элементу. Последовательность может быть нулевой длины, в таком случае она может быть использована для предоставления отсутствующей или неизвестной информации. Также, в модели данных XML существует понятие ошибочного значения (error value), которое используется для обозначения результата вычисления выражения, содержащего ошибку. При этом, error value не может присутствовать в последовательности вместе с каким-либо другим значением. Язык XQuery. Навигационные выражения. Одним из базовых элементов XQuery являются навигационные выражения, основанные на синтаксисе языка XPath [|. Такое выражение состоит из шагов (location step), где каждый шаг характеризуется осыо (axis), условием перехода (node test) и предикатом, ко торому должны удовлетворять узлы попадающие в результирующую последовательность. Результатом вычисления является последовательность, сформированная на последнем шаге. Оси описывают отношения в иерархии между текущим (контекст-ным)узлом и узлами, выбираемыми на некотором шаге. Таким образом ни namespace, ни attribute в их число не входят.