.



   

 Каталог

Корпоративные порталы
Информационные порталы
Экспертные порталы
Порталы приложений
Порталы совместной работы
Порталы управления знаниями
Порталы интеграции корпоративных систем

Методологии
Системы поддержки принятия решений (Decision Support Systems — DSS)
Data Warehouse - хранилища данных
Data Mart - Витрины данных
OLAP (On-Line Analytical Processing) - интерактивная аналитическая обработка
Business Intelligence (BI) - бизнес-интеллект
Интеллектуальный анализ данных (Data Mining)
Управление знаниями (Knowledge Management)

Корпоративные сети
Экстранет (Extranet , Экстрасеть)
Защита корпоративных сетей
Интернет (Internet)
Интранет (Intranet)

О проекте

             

Портал о Корпоративных порталах
Консалтинг, создание, внедрение и поддержка

УслугиЭнциклопедияСтатьиРесурсыИсторияНовости
Главная > Статьи > Методологии > OLAP (On-Line Analytical Processing) - интерактивная аналитическая обработка

Ядро OLAP системы. Часть 2 -- внутри гиперкуба

В предыдущей статье была рассмотрена архитектура и взаимодействие компонентов, которые могут быть использованы для построения OLAP машины. Теперь рассмотрим подробнее внутреннее устройство компонентов.

Загрузка данных в гиперкуб

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

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

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

Для хранения гиперкуба проще всего использовать базу данных своего внутреннего формата. Схематически преобразования можно представить следующим образом:

Преобразование данных плоской таблицы к внутреннему представлению

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

Проиндексированные данные измерений и фактов

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

Внутреннее представление гиперкуба

Такое будет у нас внутреннее представление гиперкуба. Так как мы делаем его не для реляционной базы данных, то в качестве полей связи значений измерений используются просто поля переменной длины (в РБД такое сделать мы бы не смогли, так как там количество колонок таблицы определено заранее).

Реализация гиперкуба

Можно было бы попытаться использовать для реализации гиперкуба набор временных таблиц, но этот метод обеспечит слишком низкое быстродействие (пример – набор компонент Decision Cube), поэтому будем использовать свои структуры хранения данных.

Для реализации гиперкуба нам необходимо использовать структуры данных, которые обеспечат максимальное быстродействие и минимальные расходы оперативной памяти. Очевидно, что основными у нас будут структуры для хранения словарей и таблицы фактов. Рассмотрим задачи, которые должен выполнять словарь с максимальной скоростью:

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

 

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

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

    • добавление нового значения;
    • определение координаты по значению измерения;
    • определение значения по координате.

     

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

      PFactLink = ^TFactLink;

      TFactLink = record
          FactNo: integer; // индекс факта в таблице
          Next: PFactLink; // ссылка на следующий элемент
      End;

      TDimensionRecord = record

          Value: string; // значение измерения
          Index: integer; // значение координаты
          FactLink: PFactLink; // указатель на начало списка элементов таблицы фактов
      End;

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

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

      Дополнительно см.

      Ядро OLAP системы. Часть 3 – построение срезов куба

      Алексей Стариков
      BaseGroup Labs.
      Источник


      16.04.2007



      Кроме этой статьи Вы можете посмотреть по тематеке текущего раздела:
      1 статью в разделе "Энциклопедия"
      7 статей в разделе "Статьи".
      2 статей в разделе "История".
      __________________
      Версия для печати

       


       
       

              Поиск

         
              Расширенный поиск

      Статьи

      Оперативная аналитическая обработка данных: концепции и технологии

      Основы OLAP

      OLAP - чудесное превращение данных в информацию

      Ядро OLAP системы. Часть 3 -- построение срезов куба

      Ядро OLAP системы. Часть 1 -- принципы построения

      Применение OLAP технологий при извлечении данных

      Что следует понимать под термином OLAP?

      История

      Истоки сегодняшних продуктов OLAP

      История OLAP (On-Line Analytical Processing)

      Энциклопедия

      OLAP - Оперативная аналитическая обработка (данных)

      Ресурсы

      OLAP: Панацея для систем управления информацией?

      Мобильный OLAP

      Оперативная аналитическая обработка данных OLAP. Интеллектуальные информационные системы.

      OLAP. Часть 1. Старо как мир компьютерный

      OLAP что в имени твоем?

      Клад, который лежит под ногами

      CorPortal.ru Все права защищены. Инспро

      Рейтинг@Mail.ru
      !