Разработка модели родительской селективности для оптимизации запросов в XML базах данных Чернышев Г.А. 545 гр. Научный руководитель Барашев Д. В.

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

Виды селективности Селективность узла n и набора предикатов s - количество узлов с тегом n, которые удовлетворяют набору предикатов s. Родительской селективностью узла n будет называться та часть узлов p, которая будет найдена при вычислении запроса (такого, что узел n – входит в запрос) выходящего из p.

XML алгебра Механизм оптимизации Правильный порядок вычислений может дать преимущество в скорости в десятки раз

Схема использования модели селективности

Вычисление родительской селективности Родительская селективность для дочернего узла n и родительского p показывает распространенность этой связки вершин. может быть вычислена по формуле:

Построение оптимального плана Опр: суммарная стоимость вычисления двух путей, исходящих из одной вершины, будет сумма стоимостей вычисления первого снизу вверх и второго сверху вниз В общем случае: 1)Сортируем детей по родительской селективности 2)Вычисляем путь с наименьшей селективностью снизу вверх 3)Сверху вниз, в порядке возрастания, считаем остальные пути.

Как считать Fan-out(n,p)? (стандартная модель) Быстрое вычисление, могут пользоваться уже хранящимися данные Не точна, основана на наивных предположениях Дополнительной памяти не требует

Как считать Fan-out(n,p)? (предложенное решение)

Свойства полученной модели Сжатие статистики. Если в графе много похожих кустов, можно хранить данные о n самых частых, остальные вычислять старым методом Масштабируемость системы: выделяя больше памяти – получаем лучший результат Возможности для паралеллизации (хранение структуры, исполнение алгоритма)

Измерения Измерение количества проверок предикатов на истинность Количество требуемой памяти (максимальное) для хранения промежуточных результатов

Тесты

Заключение Придумана модель селективности: структура данных Написана тестовая система Произведены тесты. Показано улучшение измеряемых характеристик