Обзор алгоритмов MOLAP

       

Свойства DWARF-куба


  • Это ациклический ориентированный граф с одной корневой вершиной, имеющий ровно D уровней, где D-число измерений.
  • Вершины уровня D (листья) содержат ячейки вида {ключ, агрегирующее значение}.
  • Вершины на уровнях, отличных от уровня D, (нелистовых) содержат ячейки вида {ключ, указатель}. Ячейка С в нелистовой вершине уровня i указывает на вершину уровня i+1, которую она обобщает. С — родительская вершина для обобщаемой вершины.
  • В каждой вершине имеется специальная ячейка, которая содержит псевдо-значение ALL как ключ. Эта ячейка содержит указатель или на нелистовую вершину, или на агрегирующее значение листовой вершины.
  • Ячейки на i-ом уровне содержат ключи, являющиеся значениями i-того измерения куба. Внутри одной вершины не может встречаться повторения ключа.
  • Каждая ячейка

    на i-ом уровне структуры отвечает последовательности

    из i ключей, входящих в путь от корня до ячейки. Такой путь соответствует оператору group by с (D-i) не указанными измерениями. Все группировки, содержащие

    в качестве префикса, будут относиться к ячейкам, являющимся потомками

    в структуре куба. Для всех подобных группировок их общий префикс будет хранится единожды.

  • Когда две или более группировки создают одинаковые вершины и ячейки, их хранение обобщается (поглощается), чтобы можно было хранить только одну копию. В таком случае результирующая вершина будет достижима более чем одним путем из корня, причем все пути будут иметь одинаковый суффикс. Если вершина N — обобщающая, то все ее потомки будут обобщающими вершинами.



    Содержание раздела