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


QC-Trees


QC-Tree — дерево с разделением префиксов, где грани представляются строчками, а связи отражают необходимые отношения drill-down. Основной идеей QC-деревьев является то, что верхние грани классов куба хранят всю необходимую информацию для выполнения запросов. Т.е. при данном подходе не хранятся даже нижние грани классов. При такой структуре хранения данных запросы над Quotient-кубами выполняются эффективнее запросов над DWARF-кубами. Достигается это превосходство на основе аналогичного по смыслу устранения суффиксной и префиксной избыточностей. QC-деревья позволяют устранять суффиксную избыточность за счет того, что хранятся только классы, а не отдельные ячейки. Префиксная избыточность устраняется за счет свойств самой структуры QC-tree.

Определение 5.5   QC-Tree куба Q — это орграф

$ (V,E)$

, в котором:

  • $ E = E' \vee E'', E' -$
       ребра и
    $ ~E'' -$
       связи, причем
    $ (V,E')$

    — это дерево;

  • каждая вершина содержит метку, равную значению одного из измерений;
  • для каждой верхней грани
    $ b$

    существует и единственна вершина

    $ v \in V$

    такая, что строчное представление

    $ b$

    совпадает с последовательностью меток вершин на пути от корня к

    $ v$

    в (V,

    $ E'$

    ); эта вершина хранит агрегирующее значение для

    $ b$

    .

  • предположим, что
    $ D$

    и

    $ С$

    — классы в

    $ Q$

    ,

    $ b_1 = (x_1,\ldots,x_n)$

    и

    $ b_2 = (y_1,\ldots,y_n)$

    — их верхние грани, и что

    $ С$
    — потомок
    $ D$

    (например, что

    $ С$

    напрямую специализирует (drills-down)

    $ D$

    ) в

    $ Q$

    ; тогда для каждого измерения

    $ D_i$

    , на котором различаются

    $ b_1$

    и

    $ b_2$

    , существует либо ребро дерева, либо связь (маркированная

    $ y_i$

    ) из вершины

    $ (x_1,\ldots,x_n)$

    в вершину

    $ (y_1,\ldots,y_n)$

    .

Только последнее из условий требует каких-либо объяснений. Оно просто утверждает, что если С напрямую специализирует D в Q, то это возможно либо по ребру дерева, либо по связи из какого-либо префикса пути, представляющего верхнюю грань С, к вершине, которая приведет к верхней грани D.


Таблица 5.2:

Классы и верхние грани Quotient Cube

Класс Верхняя Грань
С1 (ALL,ALL,ALL)
С2 (R1,ALL,ALL)
С3 (ALL,книги,ALL)
С4 (ALL,ALL,осень)
С5 (R1,книги,весна)
С6 (R1,еда,осень)
С7 (R2,книги,осень)


Рис. 5.6:

QC-Tree

Доказана теорема, о том, что QC-дерево для каждого Quotient куба уникально. Существуют алгоритмы создания/поддержки QC-деревьев. Выполнение запросов на QC-деревьях сильно отличается от аналогичных алгоритмов в других методах, т.к. необходимо ''выводить'' содержимое ячейки из верхней и нижней гранях класса. Аналогично, поддержка изменений информации требует пересмотра решетки классов, что, в общем случае, замедляет внесение изменений. В таблице показаны классы и верхние грани Quotient-куба для примерных данных из таблицы , а на рис. — соответствующее QC-Tree.




Начало  Назад  Вперед