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


Разбиение на классы ячеек - часть 2


, такого, что

$ a>x>b$

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

Лемма 1   Если

$ (A,\le)$

— конечное частично упорядоченное множество, то

$ a\le b$

тогда и только тогда, когда

$ a=b$

, или когда существует конечная последовательность элементов

$ x_0, \ldots,x_{n-1}$

такая, что

$ x_0=a$

,

$ x_{n-1}=b$

и

$ x_i\prec x_{i+1}$

для

$ 0\le i < n-1$

.

Отношение покрываемости в решетке

$ T_l$

будет выглядеть следующим образом:

$\displaystyle \prec = \{(0,a),(0,b),(a,1),(b,1)\}$

На диаграмме частично упорядоченного множества

$ (A,\le)$

элементы изображаются в виде маленьких кружочков

$ \circ$

; кружки, соответствующие элементам x и у, соединяются прямой линией тогда и только тогда, когда один из них покрывает другой; если x покрывает y, то кружок, соответствующий элементу x, помещается выше кружка, соответствующего элементу y. Отметим, что в диаграмме пересечение двух линий не обозначает элемент. Диаграмма для решетки

$ T_l$

изображена на рисунке .

Рис. 5.3:

Диаграмма решетки

$ T_l$

\begin{figure} \begin{picture}(106,106) \put(5,55){\circle*{2}} \put(0,60){a}... ...105){\line(1,-1){50}} \put(105,55){\line(-1,-1){50}} \end{picture} \end{figure}

Определение 5.3   Отношение покрытия для решетки куба

Кортеж

$ c \in CL(r)$

покрывает базовый (фактический) кортеж

$ t \in r$

, если

$ c\ge_g t$

.

Определение 5.4   Отношение эквивалентности по покрытию

Определим отношение эквивалентности

$ \equiv_{cov}$

как транзитивное и рефлексивное замыкание

$ R$

, где:

$ R:~~a,b \in CL(r)$

$\displaystyle R(a,b) \Longleftrightarrow \exists T\in CL(r), \forall t \in T \l... ... t' \notin T: t'\in r\\ ,a\ge_g t' ~\mbox{или}~b\ge_g t'\\ \end{array}\right. $

Введенные определения и теоремы позволяют утверждать, что разбиение по покрытию формирует полную решетку куба, только ячейками этой решетки будут являться классы ячеек обычной решетки. Причем у каждого класса будет существовать верхняя и нижняя грань, решетка будет связанной и выпуклой. Значения всех дистрибутивных и алгебраических функций для всех ячеек подобного класса эквивалентности будет совпадать.

Рассмотрим тот же пример, только на этот раз разбиение будет вестись по покрытию (рис. ).

Рис. 5.4:

Разбиение по покрытию

Соответствующая решетка по классам показана на рис. .

Рис. 5.5:

Классы разбиения по покрытию

Таким образом, для получившегося куба нам нужно хранить только две ячейки на класс, верхнюю и нижнюю грань. Остальные ячейки выводятся из верхней и нижней грани, т.к. классы разбиения по покрытиям''полны'' в смысле введенного частичного порядка.

Для Quotient Cube предложено две структуры хранения данных: QC - Tables [12] и QC-Trees [11].

QC-Table — простая таблица, в которой для каждого класса хранится верхняя и нижняя грань. Предложены алгоритмы создания QC-Table и вставки/удаления классов. Такие таблицы неэффективны по времени обработки запросов, т.к. каждый запрос требует просмотра почти всей таблицы.




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