архив
Обзор алгоритмов MOLAP
Юрий Кудрявцев, факультет ВМиК МГУ
Подразделы
- Точечные запросы (Point queries)
- Интервальные запросы.(Range queries)
- Обратные запросы. (Iceberg queries)
- Intelligent Roll-Up запросы
Виды запросов к кубам
Точечные запросы (Point queries)
При запросах этого вида возвращается агрегирующее значение меры в какой-то ячейке куба, координаты которой задаются в запросе. Все прочие запросы можно переписать, используя серии точечных запросов. Поэтому время выполнения точечных запросов является одной из важнейших характеристик алгоритма хранения OLAP данных.
SELECT регион, продукт, время, SUM(продажи) FROM Продажи
WHERE (регион = R1) AND (продукт = книги) AND (время = весна)
Результат: ячейка (R1, книги, весна)
Интервальные запросы (Range queries)
При запросах этого вида возвращается некоторый набор точек куба, удовлетворяющий заданным условиям.
SELECT регион, продукт, SUM(продажи) FROM Продажи
WHERE ((регион = R1) OR ((регион = R2)) AND ((продукт = книги) OR
(продукт = еда))
GROUP BY регион, продукт
Результат: продажи книг и еды в R1 и R2
Обратные запросы (Iceberg queries)
В отличие от точечных и интервальных запросов, для ответа на запрос данного типа используются значения меры (агрегирующие значения). Обратный запрос возвращает все ячейки куба, удовлетворяющие ограничениям, наложенным на значение меры пользователем.
SELECT регион, продукт, время, AVG(продажи)
FROM Продажи CUBE BY регион, продут, время // создается куб
HAVING AVG(продажи) >= 6 // в условии HAVING заключается ограничение на значение меры
Существует множество алгоритмов, ориентированных на обработку исключительно обратных запросов (см например [20,4]). Более подробное обсуждение одного из подобных алгоритмов будет дано далее в разделе Вычисление Iceberg кубов.
Intelligent Roll-Up запросы
Этот термин был введен в работе [20], где был представлен алгоритм создания куба для обработки данного типа запросов. Запрос можно сформулировать следующим образом:''Каковы наиболее общие условия, при которых значение меры является заданным?''
В отличие от обратных запросов, в данном типе запросов полностью используются все характеристики кубов (иерархичность, многомерность). Легко заметить, что SQL-запросы в таком случае будут иметь сложную структуру, т.к. необходимы именно наиболее общие условия, т.е. максимальные с точки зрения иерархий измерений точки многомерного пространства.
Забегая вперед, отметим, что алгоритм Quotient Cube и представление куба с помощью верхних граней обеспечивают быстрый ответ на подобные запросы, т.к. по определению верхняя грань разбиения и есть наиболее общее условие равенства меры определенному значению.