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

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

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

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

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

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

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

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

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

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

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

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

12 Тесты

13

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