Практически ориентированная концептуальная модель OLAP

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

1. Введение

Концептуальная модель - это (минимальный) набор абстрактных понятий, описывающих отдельную область применения, класс задач или систем. Концептуальная модель служит основой для проектирования базы данных и разработки системы. При этом каждый новый объект этой базы данных должен быть классифицирован в соответствии с понятиями этой модели. Это же справедливо и в отношении каждой операции.

В данной статье описана концептуальная модель для области применения так называемых OLAP-систем.

2. Задача

Задача OLAP-систем - измерять некоторые важные характеристики динамического мира, например, компании, организации, общества и так далее. К величинам, подлежащим измерению, можно отнести общий объем платежей в месяц, среднее число дней, проведенных пациентом в отделении интенсивной терапии, и тому подобное.

3. Основанные на времени факты

Для того, чтобы измерять интересующие характеристики мира, этот динамический мир должен быть представлен в OLAP-системе некоторым формальным образом. Один из способов его представления - набор основанных на времени фактов (time-based facts). Основанный на времени факт (ОВФ) - это логическое утверждение о внешнем мире, которое истинно в определенное время. Основанные на времени факты могут быть двух типов:

• факт события (Event fact) устанавливает, что некое событие произошло в некоторый момент времени. Например, 5 экземпляров товара определенного типа были проданы 1-го ноября, или решение инвестировать 5 млн. долларов было принято 12 декабря, и так далее.
• Факт состояния (State fact) определяет, что некоторые объекты находились в неком состоянии или месте и так далее, в определенное время. Например, 5 экземпляров товара находились на складе 1-го ноября. Пациент был доставлен в больницу 12-го декабря, и так далее.

• Предикат (predicate) определяет, какой тип логического утверждения представляет факт (то есть логическое имя предиката). Например, Продажа (что-то было продано), Решение (было принято какое-то решение), Госпитализация (некое лицо было доставлено в больницу).
• Временной признак (timestamp) устанавливает, когда факт имел силу в реальном мире. Точность временного признака может меняться от одного факта к другому или от приложения к приложению. Временной признак может быть установлен с точностью до секунды, минуты, часа, дня, недели, месяца и так далее. Его точность выбирается в зависимости от требований приложения. Временные признаки с неопределенной точностью имеют следующий смысл:
  Если признак неточный, как, например, точность даты, и ОВФ относится к типу события, такой признак означает, что событие произошло в какой-то момент времени, лежащий в данном интервале.
  Если признак неточный, как, например, точность даты, и ОВФ относится к типу состояния, такой признак означает, что это состояние было превалирующим в течение некоторого или (большей части) времени, лежащего в данном интервале.

• Атрибут более детально определяет событие или состояние. Например, для предиката Решение может использоваться атрибут Тип решения (инвестирование/реорганизация). Для предиката Госпитализация - атрибут тип больничного отделения (куда положили пациента). Каждый атрибут определяется своим именем и набором значений. Все основанные на времени факты с одним и тем же предикатом делят одинаковый набор атрибутов, хотя для отдельного ОВФ могут быть известны не все значения.
• Объект является абстракцией, используемой для представления физических объектов и процессов из области данного приложения. Примерами физических объектов могут служить субъект, больница, компания и так далее. К примерам процессов относятся обработка заказа в отделе продаж, история болезни в больнице и тому подобное. Объекты группируются в типы. Каждый объект имеет свой уникальный идентификационный номер ID (unique ID), текущее состояние (current state) и историю (history):
  Уникальный ID, ObjId, - это строка или число, уникальное для каждого объекта данного типа.
  Текущее состояние объекта описывается набором атрибутов, как, например, имя, номер телефона, адрес, возраст и так далее. Каждый тип объекта, как, например, СУБЪЕКТ, КОМПАНИЯ, ИСТОРИЯ БОЛЕЗНИ, имеет свой собственный набор атрибутов. Однако, для каждого отдельного объекта некоторые значения атрибутов могут быть неизвестны.
  История объекта - это последовательность состояний, в которых в прошлом находился объект. Каждое состояние, включая текущее, снабжается временным признаком, который показывает, когда объект перешел в это состояние.

• ОВФ часто описывает конкретные объекты или процессы. Например, ОВФ Продажа касается некого продукта (объекта), продаваемого некоторому клиенту (объекту). Это событие также происходит в рамках некоторого процесса заказа (объекта), который может охватывать несколько других событий Продажи, которые затрагивают другие продукты, проданные этому же клиенту. Предикат Госпитализация относится к субъекту (объекту), которого помещают в больницу (объект), например для выполнения общего медицинского осмотра (объект процесса - история болезни).
  Сноска на объект - это указатель на объект, который описывается данным ОВФ. Каждая сноска располагает именем и типом, последний показывает, на какой тип объектов сноска может указывать (субъект, больница, история болезни и так далее). Все основанные на времени факты с одним и тем же предикатом разделяют одинаковый набор сносок на объект (точнее, имена сносок на объект). Однако, не все из могут быть известны для отдельного ОВФ.
  Поскольку объект является динамической сущностью, описываемой своей историей, сноска должна указывать не только на объект, но и на состояние объекта (в истории объекта), в котором он находился, когда данный ОВФ был истинным в реальном мире.
• Мера - это параметр, который численно характеризует основанные на времени факты. В качестве примера можно привести величину денег, полученных при событии Продажа, величину денег, инвестированных при событии Решение, и так далее. Каждая мера определяется именем параметра и диапазоном возможных значений. Все основанные на времени факты с одним и тем же предикатом разделяют одинаковый набор мер. Однако, не все из них могут быть известны для отдельного ОВФ.
  Атрибуты и меры концептуально не отличаются друг от друга. Они оба отражают некоторые характеристики основанных на времени фактов. Различие заключается в том, как они используются в отдельном приложении. Меры применяются для оценки комплексных параметров динамического мира, например, средней величины планируемых в месяц инвестиций, общей суммы продаж в месяц для определенной группы товаров и так далее. Атрибуты используются для группировки основанных на времени фактов во время процесса агрегирования, например, решения по всем инвестициям (величина атрибута), принятые в этом месяце, все пациенты, госпитализированные в отделение интенсивной терапии (величина атрибута), и так далее.

Замечание. Иногда один и тот же параметр может использоваться и как мера, и как атрибут. Допустим, например, что мы хотим сгруппировать все инвестиционные решения в соответствии с величиной инвестиций: незначительные инвестиции (до 10 тысяч долларов), средние (от 10 до 100 тысяч долларов) и так далее. Предположим также, мы желаем знать общую величину планируемых инвестиций в каждой группе. Чтобы описать эту ситуацию, характерный размер инвестиций должен быть включен в основанные на времени факты и как атрибут, и как мера. Точность атрибута и измерения, опирающихся на одинаковую характеристику, может быть различной. Обычно атрибут не требует такой же точности, как мера.

В более сложном случае может возникнуть необходимость включать в качестве мер в отдельный ОВФ характеристики объектов, на которые ссылаются основанные на времени факты. Например, если нас интересует средний возраст пациентов, которым была сделана какая-то операция, возраст субъекта должен быть включен в ОВФ в качестве меры, несмотря на то, что он продолжает выполнять функции атрибута при описании состояния объекта.

4. Преобразование пространства

4.1 Простые измерения

Пусть P(t, m₁, m₂, ..., _mi, a₁, a₂,..., a_j, r₁,..., r_k) - ОВФ,

где P - предикат,

t - временной признак,

m₁, m₂, ..., m_i - меры,

a₁, a₂,..., a_j - атрибуты,

r₁,... ,r_k - сноски на объект.

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

Что же касается атрибутов, то для некоторых из них значения имеют естественный порядок, для других он отсутствует. Тем не менее, мы всегда можем внести некоторую искусственную упорядоченность в значения атрибута. Будем называть атрибут, значения которого упорядочены, измерением (dimension) атрибута. Этот же фокус может быть проделан и с сносками. Обычно объекты, на которые может указывать сноска отдельного ОВФ, неупорядочены, но мы можем внести некоторый произвольный порядок и для них. Назовем предикатную сноску, которая указывает на упорядоченные объекты, измерением сноски.

После того, как мы ввели понятие размерности, мы можем воспользоваться различными способами построения многомерного пространства.

Первый способ - построение (i+j+k+1)-мерного пространства из временного измерения (временного признака t), i-мерных мер (m₁, m₂, ..., m_i), j-мерных атрибутов (a₁, a₂,..., a_j ) и k-мерных сносок (r₁,..., r_k). Это - стандартный способ, описываемый в литературе по OLAP. Однако, в этом пространстве могут быть нежелательные зависимости между измерениями, возникающие в тех случаях, когда некоторые измерения и некоторые атрибуты представляют одинаковые характеристики реального мира.

Другой способ создания многомерного пространства - формирование его из временного измерения (временного признака t), j-мерных атрибутов (a₁, a₂,..., a_j) и k-мерных сносок (r₁,..., r_k); результирующее пространство будет иметь размерность (j+k+1). Эта концепция дает нам "более ортогональное" пространство по сравнению с предыдущим, и мы будем использовать его для определения многомерного пространства, описывающего основанные на времени факты заданного типа (например, с определенным предикатом). При условии, что временной признак, атрибуты и сноски абсолютно разграничивают одну ОВФ от другой, меры могут трактоваться как значения (например, веса), которые приписаны к некоторым точкам описанного таким способом пространства.

4.2. Расширение и упрощение

Пусть r_c, 1 >= c <= k - сноска на объект из ОВФ P(t, m₁, m₂, ..., m_i, a₁, a₂,..., a_j, r₁,..., r_k), а состояние объекта, на который указывает эта сноска, определяется набором атрибутов: 1, ..., b_n. Предположим, что мы описали измерение по каждому атрибуту объектов, на которые сноска c может указывать. Теперь мы можем рассматривать любую ОВФ с предикатом P, как точку в (j+k+n+1)-мерном пространстве, построенном из временного измерения (временного признака t), j-мерных атрибутов (a₁, a₂,..., a_j), k-мерных сносок (r₁,..., r_k) и n-мерных атрибутов объекта. Операция преобразования пространства, при которой измерение сноски дополняется измерениями атрибутов объекта, называется расширением (extension) исходного пространства по сноске rc.

Другая полезная операция по преобразованию пространства - удаление одного из измерений, которые принадлежат исходному пространству (атрибут, сноска или измерение атрибута объекта). Это преобразование называется упрощение (reduction) по определенному измерению. Координаты ОВФ в упрощенном пространстве такие же, как и в исходном для всех осей за исключением той, которой была удалена.

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

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

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

Замечание. Если упрощение касается атрибута объекта (например, категорию объекта), а сноска на объект не является частью исключаемых измерений, агрегации по устраняемому измерению не происходит.

4.3. Иерархические измерения

В предыдущем разделе мы рассмотрели, как простое измерение атрибута устанавливается введением жесткой упорядоченности в значениях атрибута. Чтобы было можно определять атрибут с меньшей точностью по сравнению с точным значением, иерархическое измерение (hierarchical dimension) определяет несколько уровней значений атрибута. В основном, иерархическое измерение, определенное по атрибуту, называет:

• Ряд уровней, больших 1, которые пронумерованы от 0 и выше. Каждый уровень составляет новый масштаб значений атрибута, который описывает этот атрибут с меньшей точностью по сравнению с исходными значениями атрибута.
• Жестко упорядоченный набор элементов (единиц измерения [units]) на каждом уровне. Единицы измерения на уровне 0 равны исходным значениям атрибута. Число единиц измерения на уровне, большем 0, всегда меньше числа единиц измерений на предыдущем уровне.
• Отображение между согласованными единицами измерения уровня. Каждая единица измерения данного уровня должна включать одну или несколько единиц измерения предыдущего уровня. Наборы единиц измерения более низкого уровня, отображенные в две различные единицы измерения текущего уровня, не должны перекрываться. Все единицы более низкого уровня должны быть охвачены (включены в некоторую единицу измерения более высокого уровня). Порядок единиц измерения более высокого уровня не должен противоречить порядку, наложенному на отображенные единицы измерения более низкого уровня.

Давайте также предположим, что каждое иерархическое измерения включает так называемый корневой (root) уровень. Корневой уровень - это высочайший уровень в иерархии, и он имеет только один элемент (единицу измерения), обозначаемую как все. Согласно приведенному выше определению иерархического измерения, все охватывает все единицы измерения предыдущего уровня. В соответствии с концепцией корневого уровня, каждое простое измерение может трактоваться как иерархическое измерение с двумя уровнями: нуль и один, где уровень один - корневой.

Замечание. Наше определение иерархического измерения сформулировано в форме, отличной от принятой в литературе по OLAP.

4.4. Сжатие

Предположим, что мы определили многомерное пространство, которое включает иерархическое измерение x. Тогда замещение первоначальных значений вдоль оси x единицами измерения более высокого уровня приведет к появлению нового пространства, которое устанавливает величины x с меньшей точностью. Мы будем называть этот преобразования сжатием (shrinking) вдоль оси x до уровня n. И опять-таки, при использовании этого вида преобразования несколько основанных на времени фактов, которые занимают различные точки в исходном пространстве, могут быть отображены в те же самые точки в "сжатом" пространстве.

Если мы трактуем все измерения как иерархические, то операция упрощения, описанная выше, может считаться частным случаем сжатия, то есть сжатия до корневого уровня. Это определение может быть расширено и на измерения сносок. Теперь мы можем описать сложную операцию упрощения/сжатия, устанавливая уровень "сжатия" для каждого задействованного измерения.

4.5. Агрегация

Когда над многомерным пространством выполняется операция сжатия/упрощения, ряд точек из исходного пространства с приписанными к ним мерами могут быть спроектированы в те же точки упрощенного пространства. Эта процедура называется агрегацией, и для того, чтобы агрегированным точкам в этом новом пространстве приписать новые определяемые значения, требуются некоторые вычисления. Новые меры устанавливаются "интегрированием" величин, первоначально приписанным к агрегируемым точкам.

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

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

Пусть m₁, m₂, ..., m_i - меры, определенные для основанных на времени фактов, которые агрегируются. Добавим к ним i+1 дополнительную меру c, c₁, …, c_i. Определим процедуру интегрирования, которая следующим образом назначает значения мерам m₁, m₂, ..., m_i, c, c₁, …, c_i:

• c получает число всех агрегируемых точек.
• c_k получает число всех точек, мера m_k которых определена, k = 1,…, i (напомним, что не для всех основанных на времени фактов необходимо, чтобы все измерения были назначены).
• И в конце, m_k получает среднее значения m_k по всем агрегируемым точкам, k-ая мера которых определена, k = 1,…,i.

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

Стандартная процедура интегрирования располагает всеми данными для вычисления некоторых других типов величин, то есть итогов по всем агрегированным точкам. Итог по p-ой измеренной величине получается из c_p и m_p согласно формуле c_p * m_p.

В некоторых случаях интегрированные величины могут трактоваться не как меры, а как атрибуты в преобразованном пространстве (иногда нам нужны и те и другие). Благодаря этому мы можем определить новое иерархическое измерение, например на средних значениях, и выполнить операции сжатия (или сокращения, см. ниже) над этим измерением.

4.6. Сокращение и смещение

Иногда для текущего анализа интересна только часть значений измерения атрибута.

Пусть s - подмножество всех возможных значений измерения атрибута x. Тогда новое пространство может быть создано из исходного путем удаления всех точек, для которых значения координаты x не принадлежит s. Такая операция преобразования пространства называется сокращением (restriction) измерения x на множестве s. Способ определения подмножества значений, подлежащих удалению, выбирается исходя из практических соображений. Это множество может быть определено путем:

1. перечисления всех величин, которые учитываются;
2. установления границ диапазона (минимума и максимума);
3. перечислением нескольких диапазонов;
4. перечислением диапазонов и не входящих в них величин;
5. указанием величин, которые не должны входить в это множество.

В отличие от операции сжатия/упрощения сокращение не приводит к агрегации, оно просто удаляет ненужные части пространства.

По выполнении сокращения первоначальный диапазон значений от 0 до некоторого предела может быть освобожден от точек с мерами. Операция смещения (shift) перемещает точку 0 в измерении направо. Эта операция характеризуется величиной смещения. Например, если нас интересуют основанные на времени факты для 1997 года, мы можем выполнить сокращение по этому году и сместить начальную точку временной оси на начало 1997 года.

Сокращение с последующим смещением допускает сравнительный анализ мер, которые принадлежат двум разным временным интервалам, например 1996 и 1997 годам. Если мы выполним два отдельных сокращения по двум годам, а затем осуществим смешение в каждом из результирующих пространств, временные оси в обоих пространствах будут согласовываться, то есть они получат одинаковое множество значений. Операция соединения (join), описанная ниже, предназначена для создания нового пространства для сравнения значений за разные годы.

4.7. Соединения

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

Существуют иные способы определения производных основанных на времени фактов. Предположим, что у нас есть база данных больницы, которая для каждого пациента хранит ОВФ, регистрирующий событие при приеме пациента в больницу, и ОВФ, регистрирующее событие при его выписке. Эти основанные на времени факты связаны с одинаковым объектом - субъектом (физическим лицом) - и с одинаковой больничной картой (объект процесса), кроме того, существует правило, согласно которому карта может иметь только одно событие Принят и Выписан. Несмотря на то, что исходная база данных может не включать основанные на времени факты, которые показывают, кто лежал в больнице в определенный день, такую информацию можно получить. Для этого необходимо для каждой даты:

• найти все события типа Принят с временным признаком, меньшим или равным заданной даты;
• и исключить из них все события, которые относятся к картам, для которых событие Выписан было зарегистрировано с временным признаком, меньшим заданной даты.

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

Рассмотрим два многомерных пространства: M1 и M2 - каждое размерности n, но с абсолютно разными множествами мер. Пусть каждое i-ое измерение из M1 совместимо с i-ым измерением из M2, то есть они имеют одно и то же множество величин, упорядоченных одинаковым образом. Затем мы соединяем M1 с M2 по общим осям и получаем новое пространство M3. Для этого нам необходимо назначить меры для каждой точки в M3. Это возможно только в том случае, если соответствующие точки в M1 или/и M2 имеют одинаковые приписанные меры. Хотя существуют различные способы назначения мер для точек в новом пространстве, мы можем описать, по крайней мере, один стандартный метод:

• меры, приписываемые точкам в M3, состоят из всех мер, приписанных соответствующим точкам в M1 плюс все меры, приписанные соответствующим точкам в M2.

Для создания пространства, которое сравнивает меры по времени для двух различных временных интервалов, например, для 1996 и 1997 годов, можно вернуться к примеру, рассмотренному выше, и воспользоваться операцией соединения.

5. Поиск по пространству и его представление

5.1. Что такое запрос

Запрос конечного пользователя в OLAP-системе - это требование представить основанные на времени факты в форме одного или нескольких многомерных пространств. Запрос состоит из двух частей: какое пространство(-а) должно быть представлено и в какой форме, например, в виде списка (отчета), графика, трехмерной диаграммы и так далее.

В случае, если должно быть представлено более чем одно пространство, между пространствами должно присутствовать некоторое подобие, например, они должны делить, по крайней мере, одно измерение. В данном случае, в отличие от операции соединения, это не означает, что измерения должны быть абсолютно совместимы. Допускается слабая совместимость, то есть действительные оси, используемые в обоих пространствах, относятся к одному и тому же иерархическому измерению, но в каждом из этих пространств используются различные уровни единиц измерения. Типичный пример представления нескольких пространств вместе - отчет с итогами и промежуточными итогами для различных временных диапазонов (неделя, месяц и год), категории проданных товаров и так далее. Для этих отчетов объединенные пространства могут быть получены поэтапным сжатием/упрощением исходного пространства по различным осям (время, продукт и так далее).

5.2. Декомпозиция запросов

После того, как решено, какое пространство представлять, необходимо ответить на следующий вопрос: хранится ли это пространство в базе данных, или же его необходимо каким-то образом из нее получать. Во втором случае нам потребуется понять, может ли производное пространство быть получено с помощью стандартных операций преобразования пространства (расширение, сжатие/упрощение, сокращение, объединение [union]) или же потребуется прибегнуть к нестандартным операциям.

Обычно искомое пространство должно быть представлено как последовательность операций (стандартных или нестандартных) над одним или несколькими исходными пространствами. Каждая операция, которая может привести к агрегации, должна сопровождаться формулой для вычисления мер. Формула может быть добавлена также и к операциям, не связанным с агрегацией, например, если для запроса нужны меры, которые могут быть вычислены, а не те, которые хранятся в базе данных. Более того, формула для вычисления может потребоваться даже тогда, когда нет необходимости в преобразовании пространства, то есть когда база данных уже содержит пространство, запрашиваемое в запросе, но с иным множеством измерений, отличных от запрашиваемых.

Часто существует несколько способов определения порядка операций, которые ведут к заданному искомому пространству. Новый порядок может быть получен, если, например, поменять местами две стандартные операций в уже установленном порядке. Это возможно только в том случае, если формула для вычислений инвариантна к таким изменениям порядка операций. Это справедливо, например, для стандартной формулы интегрирования, рассмотренной в разделе 4.5. Если порядок операций можно изменить, полезно придерживаться следующих правил:

1. Смена сжатия и сокращения. Если сокращение следует за сжатием над одним и тем же измерением, возможно, более разумно сменить порядок этих операций. Поскольку при сокращении некоторые точки удаляются без интегрирования, при вызове сжатия меньшее число точек будет интегрироваться. Однако, потребуется решить одну проблему, а именно: если сокращение определено после сжатия в том же измерении, описание сокращения будет опираться на единицы измерения более высокого порядка иерархии по сравнению с единицами измерения несжатого пространства. Чтобы поменять местами сжатие и сокращение, описание сокращения должно быть переведено в единицы измерения более низкого уровня. Это выполняется на основе описания иерархического измерения.
2. Если две операции сжатия определятся в одном и том же измерении, сначала попытайтесь изменить порядок операций, так чтобы они следовали одна за другой (например, используя правило 1, приведенное выше). После этого они могут быть объединены в одно сжатие, которое покрывает несколько уровней. Это весьма эффективно, когда второе сжатие выполняется до корневого уровня (то есть это измерение опускается после всех).
3. Если измерение, подлежащее сжатию, имеет индекс в базе данных, разумно выполнить сжатие в этом измерении после сжатия в других измерениях. Если же имеется более одного индекса измерения, измерение, которое приводит к меньшему числу агрегированных точек (маленьких ячеек [small cells]) следует рассматривать как последнее для сжатия. Если же существует сложный индекс, который простирается на несколько измерений, необходимо сменить порядок сжатия на обратный по отношению к порядку атрибутов, определенных в этом индексе.

5.3. Поиск

Поиск (scanning) - это процесс прохождения по многомерному пространству и сбора всех точек, которые имеют некоторые измерения. Результатом поиска является поток взвешенных точек, каждая из которых описывается своими координатами в пространстве и мерами. Поиск необходим для:

• представления информации конечному пользователю;
• агрегации и интегрирования при выполнении сжатия/упрощения пространства.

Во время поиска каждая точка должна просматриваться только один раз. На практике этого требования недостаточно с учетом задач презентации и интегрирования, и может потребоваться более строгий порядок обхода.

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

Предположим, что мы просматриваем n-мерное пространство в порядке D₁, .., D_n. Тогда можно считать, что результирующий поток состоит из ряда последовательностей, определяемых следующим образом:

• Каждая последовательность включает все точки с одинаковой координатой в измерении D₁. Точка, которая начинает новую последовательность, называется разрывом (break) уровня 0 в измерении D₁.
• В качестве альтернативы каждая последовательность включает точки с одинаковыми координатами в измерении D₁ и D₂. Точка, которая начинает новую последовательность, называется разрывом уровня 0 в измерениях <D₁, D₂>. Естественно, разрывы в D₁, D₂ будут происходить более часто по сравнению с D₁. Все разрывы в D₁ также являются разрывами в <D₁, D₂>.
• Или же каждая последовательность включает точки с одинаковыми координатами в измерении D₁, ..., D_k, где k <= n. Точка, которая начинает новую последовательность, называется разрывом уровня 0 в измерениях <D₁, ..., D_k>.
  Если измерение D_k является иерархическим измерением с h уровнями, а f - ненулевой уровень (f <=h), можно считать, что рассмотренный поток состоит из ряда следующих последовательностей:
• Каждая последовательность включает точки с одинаковыми координатами в измерении D₁, ..., D_k--1, и D_k, но для измерения D_k координаты точно такие только с точностью единиц измерения уровня f. Точка, которая начинает новую последовательность, называется разрывом уровня f в измерениях <D₁, ..., D_k>.

5.4. Потоковая обработка и объединение

Поиск можно использовать как способ преобразования пространства "на лету". Применяя правила специальной обработки к просмотренному потоку, мы можем получить поток, который мог бы быть получен в результате поиска по пространству, отличному от исходного. Естественно, это другое пространство может быть определено как преобразование исходного пространства.

Пусть пространство M2 может быть получено из n-мерного пространства M1 = D₁ x ...x D_n путем операции сжатия вдоль измерения D_k до уровня f. Предположим также, что определена некоторая формула интегрирования для назначения мер для агрегированных точек. Рассмотрим M1 в порядке, определенном как D₁, ..., D_k-1, D_k+1, ..., D_n, D_k. Будем считать, что результирующий поток - это ряд последовательностей, каждая из которых лежит между двумя разрывами уровня f в измерениях <D₁, ..., D_k-1, D_k+1, ..., D_n, D_k> (крайний правый разрыв включен в эту последовательность). Применяя формулу интегрирования ко всем точкам в каждой последовательности и заменяя величину Dk точности 0 величиной точности f, мы получим поток, который был бы результатом просмотра пространства M2. Эту процедуру можно обобщить, чтобы она включала случаи, когда несколько операций сжатия применяются одна после другой.

Помимо преобразования пространства разрывы могут также использоваться для объединения (merging) двух или более пространств, которые должны быть вместе представлены конечному пользователю. Точнее, разрывы уровня l, большего 0, могут использоваться для объединения двух потоков, где второй определяет некоторые интегрированные величины, как, например, промежуточный итог, среднее и так далее, для единиц измерения уровня l. В этом случае следующая точка из второго потока помещается непосредственно перед следующим разрывом в первом потоке (чтобы суммировать предыдущую последовательность). Более того, вместо объединения двух независимых потоков, правила обработки потока, описанные выше, могут применяться к текущему потоку во время просмотра исходного пространства, чтобы получить второй поток.

5.5. Визуализация

Визуализация - это способ представления конечному пользователю потока точек. Существует несколько разновидностей визуализации, например, список (отчет), графическая диаграмма (пирог, столбцы), график, двумерная матрица и так далее.

Автор: Илиа Бидер (Ilia Bider)