Хранилища строятся на основе многомерной модели данных, подразумевающей выделение отдельных измерений (время, география, клиент, счет) и фактов (объем продаж, доход, количество товара) с их анализом по выбранным измерениям. Многомерная модель данных физически может быть реализована как в многомерных, так и в реляционных СУБД. В последнем случае она выполняется по схеме «звезда» или «снежинка». Данные схемы предполагают выделение таблиц фактов и таблиц измерений. Каждая таблица фактов содержит детальные данные и внешние ключи на таблицы измерений.
Теория построения многомерной модели данных и ее воплощение в реляционной структуре известна [3, 10, 12], однако информации по проблеме представления иерархий очень мало. В качестве примера измерения, широко применяющегося при анализе деятельности предприятия и имеющего иерархическую структуру, можно привести справочник статей затрат (рис 2).
![]() | |
Рис. 2. Модель иерархического справочника. |
![]() | |
Таблица 1. Представление иерархий с помощью рекурсивной связи |
Метод, предложенный Джо Селко [4], основан на теории множеств — все узлы дерева проходятся в прямом порядке [5] и для каждого узла заполняются два значения (cм. нумерацию узлов на рис. 3).
![]() | |
Рис. 3. Нумерация левой и правой границ узлов дерева |
Сначала заполняется левая граница и лишь затем правая — при движении обратно от потомков к родителям. При такой нумерации узлов каждый родитель содержит потомков, левая и правая граница которых лежит в интервале между левой и правой границей родителя. Аналогично все родители потомка имеют левую границу, которая меньше левой границы потомка и правую, большую правой границы потомка.