Совет №17
Наполняем вспомогательные таблицы иерархий

Материал опубликован с разрешения компании Ralph Kimball Associates
Автор оригинала: Lawrence Corr (все статьи)
Перевод на русский язык: Константин Лисянский
Оригинальный документ располагается здесь.

Совет этого месяца является продолжением статьи Ральфа, опубликованной в сентябре 1988 года под названием "Help for Hierarchies" (http://www.dbsmag.com/9809d05.html), которая посвящена иерархическим структурам переменной глубины, которые наиболее часто представляются в реляционных базах данных рекурсивными отношениями, известными иногда под названиями "свиные уши" или "рыболовные крючки".
Ниже следует определение измерения "компания", которое содержит рекурсивное отношение между внешним ключом PARENT_KEY и первичным ключом COMPANY_KEY

Create table COMPANY (
COMPANY_KEY INTEGER NOT NULL,
COMPANY_NAME VARCHAR2(50),
PARENT_KEY INTEGER);

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

Create table COMPANY_STRUCTURE (
PARENT_KEY INTEGER NOT NULL,
SUBSIDIARY_KEY INTEGER NOT NULL,
SUBSIDIARY_LEVEL INTEGER NOT NULL,
SEQUENCE_NUMBER INTEGER NOT NULL,
LOWEST_FLAG CHAR(1),
LOWEST_FLAG CHAR(1),
HIGHEST_FLAG VARCHAR2(50),
SUBSIDIARY_COMPANY VARCHAR2(50));

Последние два столбца в этом примере, которые денормализуют названия компаний в эту таблицу, строго говоря, не являются необходимыми, однако добавлены с тем, чтобы облегчить понимание того, что будет происходить дальше. Следующая хранимая процедура на PL/SQL демонстрирует возможный способ наполнения этой таблицы "иерархического взрыва" из таблицы COMPANY, хранящейся в СУБД Oracle:

CREATE or Replace procedure COMPANY_EXPLOSION_SP as
CURSOR Get_Roots is
select COMPANY_KEY ROOT_KEY,
decode(PARENT_KEY,NULL,'Y ','N ')HIGHEST_FLAG,
COMPANY_NAME ROOT_COMPANY
from COMPANY;
BEGIN
For Roots in Get_Roots
LOOP
insert into COMPANY_STRUCTURE
(PARENT_KEY,
SUBSIDIARY_KEY,
SUBSIDIARY_LEVEL,
SEQUENCE_NUMBER,
LOWEST_FLAG,
HIGHEST_FLAG,
PARENT_COMPANY,
SUBSIDIARY_COMPANY)
select
roots.ROOT_KEY,
COMPANY_KEY,
LEVEL -1,
ROWNUM,
'N ',
roots.HIGHEST_FLAG,
roots.ROOT_COMPANY,
COMPANY_NAME
from COMPANY
Start with COMPANY_KEY =roots.ROOT_KEY
connect by prior COMPANY_KEY =PARENT_KEY;
END LOOP;
update COMPANY_STRUCTURE
SET LOWEST_FLAG ='Y '
where not exists (select *from COMPANY
where PARENT_KEY =COMPANY_STRUCTURE.SUBSIDIARY_KEY);
COMMIT;
END;/*of procedure */

Это решение использует преимущество расширения CONNECT BY СУБД Oracle для прохода по каждому из деревьев в данных. В то время как конструкция CONNECT BY очень полезна в этой процедуре, она не может быть использована инструментом генерации запросов. Если инструмент был бы способен сгенерировать такой оператор для исследования рекурсивных отношений, он не сможет в том же самом операторе выполнить соединение с таблицей фактов. Если бы даже Oracle снял это немного деспотичное ограничение, производительность при выполнении запроса была бы далеко не самой хорошей.
Следующие данные о фиктивной компании помогут вам понять таблицу COMPANY_STRUCTURE и процедуру COMPANY_EXPLOSION_SP:

/*column order is Company_key,Company_name,Parent_key */
insert into company values (100,'Microsoft ',NULL);
insert into company values (101,'Software ',100);
insert into company values (102,'Consulting ',101);
insert into company values (103,'Products ',101);
insert into company values (104,'Of .ce ',103);
insert into company values (105,'Visio ',104);
insert into company values (106,'Visio Europe ',105);
insert into company values (107,'Back Of .ce ',103);
insert into company values (108,'SQL Server ',107);
insert into company values (109,'OLAP Services ',108);
insert into company values (110,'DTS ',108);
insert into company values (111,'Repository ',108);
insert into company values (112,'Developer Tools ',103);
insert into company values (113,'Windows ',103);
insert into company values (114,'Entertainment ',103);
insert into company values (115,'Games ',114);
insert into company values (116,'Multimedia ',114);
insert into company values (117,'Education ',101);
insert into company values (118,'Online Services ',100);
insert into company values (119,'WebTV ',118);
insert into company values (120,'MSN ',118);
insert into company values (121,'MSN.co.uk ',120);
insert into company values (122,'Hotmail.com ',120);
insert into company values (123,'MSNBC ',120);
insert into company values (124,'MSNBC Online ',123);
insert into company values (125,'Expedia ',120);
insert into company values (126,'Expedia.co.uk ',125);
/*End example data */

Процедура возьмёт 27 записей из таблицы COMPANY и создаст 110 записей в таблице COMPANY_STRUCTURE, представляющих одно большое дерево (Microsoft) с 27 узлами и 26 более мелкими деревьями. Вы можете обнаружить, что в случае больших наборов данных производительность можно поднять путём создания пары конкатенированных индексов по столбцам, по которым происходит соединение. В данном примере по столбцам COMPANY_KEY, PARENT_KEY и PARENT_KEY, COMPANY_KEY.
Если вы хотите визуализировать древовидную структуру в текстовом виде, следующий запрос отображает список подчинённых организаций Microsoft с отступами:

select LPAD(' ',3*(SUBSIDIARY_LEVEL))||SUBSIDIARY_COMPANY from
COMPANY_STRUCTURE order by SEQUENCE_NUMBER where parent_key =100

Поле SEQUENCE_NUMBER было добавлено ещё в оригинальной статье, оно нумерует узлы снизу вверх и справа налево. Оно позволяет хранить корректные узлы уровня 2 под соответствующими им узлами уровня 1.
Для создания графической версии дерева организационной структуры обратите внимание на продукт VISIO 2000 Enterprise Edition, в котором имеется мастер создания схем организационных структур на основе данных из базы данных или текстовых файлов. С помощью программы на VBA, представления над таблицей COMPANY STRUCTURE и таблицы фактов он может автоматизировать генерацию той страницы HTML, которая вам нужна.

Я была бы признательна, если бы кто-нибудь мог прислать мне процедуры для DB2 UDB и Microsoft SQL Server, которые давали бы те же самые результаты. Более эффективные реализации для Oracle также представляют интерес. Лучшие примеры получат оценку и будут включены в будущую колонку журнала Intelligent Enterprise.

• Следующий совет
• Предыдущий совет
• Другие советы

По этой теме можно также почитать:

• Статьи из раздела Проектирование многомерных моделей (схема "звезда")
  

Для удобства отслеживания новых публикаций на сайте рекомендую подписаться на рассылку или подписаться на канал RSS.

Если вы нашли в сети интересные ссылки на ресурсы по технологиям хранилищ данных, OLAP, CRM или data mining, и хотите поделиться ими с другими, присылайте их. Я с удовольствием размещу их на этом сайте.

[AD]