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

• Автор: Фомичев, Андрей Владимирович
• Шифр специальности: 05.13.11
• Научная степень: Кандидатская
• Год защиты: 2005
• Место защиты: Москва
• Количество страниц: 153 с. : ил.

Оглавление
Введение

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

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

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

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

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

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

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

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

Глава 1 Управление хранимыми Xданными

1.1 Технологии платформы X для управления данными.
1.1.1 Язык X, .слабоструктурированные данные и платформа X
1.1.2 Модель данных X и X.
1.1.3 Язык путевых выражений X и язык запросов X
1.2 Управление хранимыми Xданными в полнофункциональной XСУБД .
1.2.1 Полнофункциональная XСУБД.
1.2.2 Требования к полнофункциональной XСУБД в контексте управления хранимыми данными
1.3 Подходы к хранению Xданных
1.3.1 Связи между узлами по значению или по ссылке.
1.3.2 Определение отношения предокпотомок и порядка документа нумерующая схема.
1.3.3 Использование реляционных СУБД для хранения Xданных.
1.3.4 Специально разработанные методы для хранения Xданных
1.4 Выводы.
Глава 2 Метод хранения Xданных во внешней памяти на основе описывающей схемы
2.1 Описывающая схема Xдокумента и структурные путевые выражения
2.1.1 Использование описывающей схемы Xдокумента для выполнения запросов, заданных в виде абсолютных структурных путевых выражений
2.2 Организация хранения Xдаиных во внешней памяти на основе описывающей схемы
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 Оценка метода хранения Xданных во внешней памяти на основе описывающей схемы
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 Сравнение с другими методами хранения Xданных.
2.4 Выводы.
Глава 3 Управление памятью для хранимых Xданных и слоистая организация адресного пространства.
3.1 О необходимости разработки единого адресного пространства базы данных для представления данных во внешней и оперативной памяти.
3.2 Слоистая организация адресного пространства базы данных
3.2.1 Требования к управлению памятью для хранимых Xданных
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. Слоистое адресное пространство и методы управления памятью, основанные на приеме подмены указателей.
3.3 Выводы
Глава 4 Пути доступа к Xданным, хранимым на основе описывающей схемы.
4.1 Задача поиска оптимального пути доступа к данным
4.2 Вычисление абсолютного структурного путевого выражения с предикатом
4.2.1 Абсолютное структурное путевое выражение с предикатом.
4.2.2 Способы вычисления абсолютного структурного путевого выражения с предикатом
4.2.3 Метрика оценки стоимости и селективность путевых выражений
4.2.4 Оценка стоимости вычисления выражения способом сверхувниз
4.2.5 Оценка стоимости вычисления выражения способом снизувверх
4.2.6 Оценка стоимости вычисления выражения способом фильтрации с помощью нумерующей схемы.
4.2.7 Комбинирование способов вычисления выражения
4.3 Выводы.
Заключение
Литература


Тогда для хранения этой части используются традиционные СУБД и придумываются методы связи этой части данных с оставшимися данными, которые не удалось струкгурировать и поэтому приходится хранить в других системах файловая система, специализированные системы и т. Частое изменение структуры. Апостериорная, а не априорная схема данных. Традиционные СУБД опираются на принцип фиксированной схемы данных. Поэтому сначала описывается схема базы данных, и только затем база наполняется данными схема данных априорная. При работе со слабоструктурированными данными целесообразно применять обратный подход сначала заполняется база данных, а затем определяется, какую структуру она имеет, то есть при заполнении базы данных вырисовывается се схема апостериорная схема. Не будет преувеличением сказать, что язык X является сегодня стандартом представления слабоструктурированных данных. В определенном роде появление X послужило катализатором развития систем управления базами данных, основанных на модели слабоструктурированных данных. Xданных. О популярности этого направления можно судить по количеству докладов на ведущих конференциях по базам данных I , V более работ посвящается этой тематике больше, чем какомулибо другому направлению. Возрастает количество применений X как формата хранения данных и в индустрии баз данных о поддержке X и сопутствующих стандартов в своих продуктах заявляют производители ведущих традиционных реляционных и объектнореляционных СУБД , I и i . В настоящей работе язык X представляет интерес именно как формат представления слабоструктурированиых данных. Как будет сказано ниже, на базе X построена модель данных, которая служит основой систем управления базами Xданных. Задачи таких систем в широком смысле состоят в хранении больших объемов Xданных во внешней памяти и их обработке, включая эффективный выбор частей Xдокументов в соответствии с пользовательскими запросами, а также изменение хранимых данных. Рисунок 1. На рисунке 1. Xдокумента. Тело Xдокумента состоит из элементов разметки и непосредственного содержимого документа данных, представленных в текстовой форме . Более подробно типы узлов Xдокумента рассматриваются в подразделе 1. Xдокумеит определяется в спецификации языка X как объект данных, который является правильно сформированным в соответствии с требованиями спецификации X. Все эти требования носят простой и естественный характер и направлены на единообразную интерпретацию Xдокумента различными синтаксическими анализаторами X например, требуется, чтобы для каждого открывающего тэга, определяющего некоторую область данных в документе, обязательно имелся парный закрывающий тэг. Xданные являются самоописываемыми, то есть определяют как структуру данных, так и значения. При обсуждении X было бы ошибкой ограничиться только возможностями самого языка разметки. Наряду с созданием стандарта этого языка консорциум 3, формирующий техническую политику развития и разрабатывающий стандартизованные спецификации дтя этой среды, на самом деле одновременно формирует новую платформу платформу X, основой которой является язык X. Функциональность этой платформы определяется целым комплексом взаимосвязанных стандартов, часть из которых уже принята 3, а другие находятся в стадии разработки. X . Тем не менее, все стандарты платформы X тесно переплетены между собой. В настоящей работе X рассматривается в контексте управления данными, поэтому нас, в первую, очередь интересуют стандарты, разрабатываемые рабочей группой 3, которая носит название X . Целью этой рабочей группы является предоставление гибких средств построения запросов для извлечения данных из реальных и виртуальных документов и коллекций документов, расположенных локально или в , обеспечивая, таким образом, взаимодействие между миром и миром баз данных. Рабочей группой X определяются стандартов, из которых мы подробнее остановимся на трех модели данных X и X подраздел 1. X и языке запросов X подраздел 1. Рассматриваемые далее стандарты опираются па ряд спецификаций платформы X, краткую сводку которых мы приведем здесь. Пространства имен X .