Dataphor - Exploding hierarchical data

This article show examples of using the D4 explode operator.
This operator is used for expressing hierarchical data. It is
not a 'recursive' operator like the recursive sql CTE but more
like the Oracle Connect By construct.

The examples follow the ones used by Itzik Ben-Gan to illustrate
the recursive CTE query in Sql Server 2005, specifically the
'Single-Parent Environment: Employees Organizational Chart'
which can be found at:
http://msdn2.microsoft.com/en-us/library/ms345144.aspx#docum_topic4

The explode examples are based on the Employees table used in the
sql example. The table is stored in an Sql Server 2005 database.
Several of the examples use the concept of a dense rank.

As with most of my articles, the code is not necessarily 'clever' but
straightforward, not necessarily the best 'performant' but intended
to express the many different concepts and constructs in D4.

select Employees

empid mgrid empname  salary    
----- ----- -------- ----------
1     0     Nancy    $10,000.00
2     1     Andrew   $5,000.00 
3     1     Janet    $5,000.00 
4     1     Margaret $5,000.00 
5     2     Steven   $2,500.00 
6     2     Michael  $2,500.00 
7     3     Robert   $2,500.00 
8     3     Laura    $2,500.00 
9     3     Ann      $2,500.00 
10    4     Ina      $2,500.00 
11    7     David    $2,000.00 
12    7     Ron      $2,000.00 
13    7     Dan      $2,000.00 
14    11    James    $1,500.00 


Get a tree for a specific manager.

select
 (
  Employees
    explode
   by mgrid = parent empid
   where  mgrid=0
     order by {empid}
       include level
   with {IgnoreUnsupported = 'true'}
  )
// Do a little string insert to format the tree.  
    add {'' Temp, level-1 Totalspace}
     add {
          (
           empname.Insert(0,Temp.PadLeft(Totalspace,'|'))
          ).Replace('|',' | ')
          Tree
         }
        {Tree,mgrid,empid,empname,sequence,level};
       
Tree              mgrid empid empname  sequence level
----------------- ----- ----- -------- -------- -----
Nancy             0     1     Nancy    1        1    
 | Andrew         1     2     Andrew   2        2    
 |  | Steven      2     5     Steven   3        3    
 |  | Michael     2     6     Michael  4        3    
 | Janet          1     3     Janet    5        2    
 |  | Robert      3     7     Robert   6        3    
 |  |  | David    7     11    David    7        4    
 |  |  |  | James 11    14    James    8        5    
 |  |  | Ron      7     12    Ron      9        4    
 |  |  | Dan      7     13    Dan      10       4    
 |  | Laura       3     8     Laura    11       3    
 |  | Ann         3     9     Ann      12       3    
 | Margaret       1     4     Margaret 13       2    
 |  | Ina         4     10    Ina      14       3    

Treat each employee as if they are a manager. This will return the
subordinates of each employee regardless of whether or not
they are a manager.

select
 (
  Employees
    explode
   by mgrid = parent empid
   where  mgrid>=0         //Changing where to include all employees.
     order by {empid}
       include level
   with {IgnoreUnsupported = 'true'}
  )
     add {'' Temp, level-1 Totalspace}
     add {
          (
           empname.Insert(0,Temp.PadLeft(Totalspace,'|'))
          ).Replace('|',' | ')
          Tree
         }
        {Tree,mgrid,empid,empname,sequence,level} ;
       
Tree              mgrid empid empname  sequence level
----------------- ----- ----- -------- -------- -----
Nancy             0     1     Nancy    1        1    
 | Andrew         1     2     Andrew   2        2    
 |  | Steven      2     5     Steven   3        3    
 |  | Michael     2     6     Michael  4        3    
 | Janet          1     3     Janet    5        2    
 |  | Robert      3     7     Robert   6        3    
 |  |  | David    7     11    David    7        4    
 |  |  |  | James 11    14    James    8        5    
 |  |  | Ron      7     12    Ron      9        4    
 |  |  | Dan      7     13    Dan      10       4    
 |  | Laura       3     8     Laura    11       3    
 |  | Ann         3     9     Ann      12       3    
 | Margaret       1     4     Margaret 13       2    
 |  | Ina         4     10    Ina      14       3    
Andrew            1     2     Andrew   15       1    
 | Steven         2     5     Steven   16       2    
 | Michael        2     6     Michael  17       2    
Janet             1     3     Janet    18       1    
 | Robert         3     7     Robert   19       2    
 |  | David       7     11    David    20       3    
 |  |  | James    11    14    James    21       4    
 |  | Ron         7     12    Ron      22       3    
 |  | Dan         7     13    Dan      23       3    
 | Laura          3     8     Laura    24       2    
 | Ann            3     9     Ann      25       2    
Margaret          1     4     Margaret 26       1    
 | Ina            4     10    Ina      27       2    
Steven            2     5     Steven   28       1    
Michael           2     6     Michael  29       1    
Robert            3     7     Robert   30       1    
 | David          7     11    David    31       2    
 |  | James       11    14    James    32       3    
 | Ron            7     12    Ron      33       2    
 | Dan            7     13    Dan      34       2    
Laura             3     8     Laura    35       1    
Ann               3     9     Ann      36       1    
Ina               4     10    Ina      37       1    
David             7     11    David    38       1    
 | James          11    14    James    39       2    
Ron               7     12    Ron      40       1    
Dan               7     13    Dan      41       1    
James             11    14    James    42       1            

If we reverse 'by mgrid = parent empid' to 'by empid = parent mgrid' we
get the tree of a particular employee to their top level manager.

select
 (
  Employees
    explode
      by empid = parent mgrid
         where  empid=13
   order by {empid}
       include level
   with {IgnoreUnsupported = 'true'}
  )
     add {'' Temp, level-1 Totalspace}
     add {
          (
           empname.Insert(0,Temp.PadLeft(Totalspace,'|'))
          ).Replace('|',' | ')
          Tree
         }
        {Tree,mgrid,empid,empname,sequence,level};
       
Tree           mgrid empid empname sequence level
-------------- ----- ----- ------- -------- -----
Dan            7     13    Dan     1        1    
 | Robert      3     7     Robert  2        2    
 |  | Janet    1     3     Janet   3        3    
 |  |  | Nancy 0     1     Nancy   4        4    
       
By changing the where predicate to >=1 we can get a report on all
employees (note where empid>=3 eliminates the graph of the 1st 2
employees (Nancy and Andrew) but doesn't eliminate them from graphs
of other employees who report to them).


Here we create an operator that will give a graph in either direction
of a specific employee and their top level manager. In other words,
we can either start with the employee and go down to their top level
manager or start with the employees top level manager and go down
to the employee. The concept of the dense rank is used for binding
all rows of each employee together. By getting the empname and empid
for each dense rank we can target any employee by name or number.   
(Note we could, of course, use a view or any number of other constructs.
I just felt in the mood to use an operator ☺ ).

The operator takes two arguments. The first, aTreeTable, is a table
of type Employees. The second, Start_At, is a string and indicates
the direction of the graph. Using 'M' for manager starts with the
manager. Using 'E' starts with the employee.

create operator EmpTree(aTreeTable:typeof(Employees),Start_At:String):
//The operator returns a virtual table with columns and their data types
//defined by the typeof expression.
typeof(
       Employees
       add{1 level,'S' empnamerank,1 empidrank, 'T' Tree_Graph, 1 Rank, 1 TreeOrder}
       )
begin
result:=table of typeof(result){};
//Starting at top level mgr for each employee is a desc sort (default).
//Starting at each employee to the top level mgr. is an asc sort.    
//Start_At=M(gr) is desc sort (default)
//Start_At='E(mp) is asc sort.
var LSort:='D'; //Default.
if ( ((Start_At.Trim())[0]).Upper() ) = 'E'
   then LSort:='A' ;
var T:=
aTreeTable
explode  
by empid = parent mgrid
    where  empid>=1
      order by {empid}
       include level
   with {IgnoreUnsupported = 'true'};
//Get a dense rank. This rank binds all rows for each employee
//together. The idea is to increment a count for every level 1 since
//a level 1 indicates the start of a new employee.
var TR:=
       T add{case when level=1 then empname else nil end NameEmp}
        add
           {
            Count(
                  T rename {sequence sequenceX}
                   where  (sequenceX<=sequence) and (level=1)
                  ) 
             Rank
            };
var SR:=
     TR               
      join
       (
        TR group by {Rank}
        //We want the emp name, number (empid) and reverse level for each
        //dense rank (empname). We want the reverse level so we can get
        //the tree representative from the employee to top level manager
        //AND the top level manager to the employee.
                add{Max(empid) NumEmpid,Max(NameEmp) Emp_Name,Max(level) Maxlevel}
        )                        
 add {
    (empname.Insert(0,''.PadLeft( (if LSort='A' then (level-1) else (Maxlevel-level)),
                                                         '|'))).Replace('|',' | ')
        Tree_Graph
     }
     rename {sequence seq};
result:=
 ToTable(
  ToList(
 cursor(SR
 order by
     {
      Rank,
      seq
      sort ((1 - (2*ToInteger((LSort = 'D'))))*(.left.value ?= .right.value)) asc
     }
    
       )//cursor
       )//ToList
      )  //ToTable
        {empid,mgrid,empname,salary,level,Emp_Name empnamerank,
          NumEmpid empidrank,Tree_Graph,Rank,sequence+1 TreeOrder};
end;         


Here we show the first five employees by using Rank in a where statement.
The value of the Rank corresponds to the ascending order of empid.
Because empid starts at 1 Rank happens to be equal to the empid.

select EmpTree(Employees,'Mgr') //We use the operator as if it were a table.
  where Rank<=5
      order by {TreeOrder};     

empid mgrid empname  salary     level empnamerank empidrank Tree_Graph   Rank TreeOrder
----- ----- -------- ---------- ----- ----------- --------- ------------ ---- ---------
1     0     Nancy    $10,000.00 1     Nancy       1         Nancy        1    1        
1     0     Nancy    $10,000.00 2     Andrew      2         Nancy        2    2        
2     1     Andrew   $5,000.00  1     Andrew      2          | Andrew    2    3        
1     0     Nancy    $10,000.00 2     Janet       3         Nancy        3    4        
3     1     Janet    $5,000.00  1     Janet       3          | Janet     3    5        
1     0     Nancy    $10,000.00 2     Margaret    4         Nancy        4    6        
4     1     Margaret $5,000.00  1     Margaret    4          | Margaret  4    7        
1     0     Nancy    $10,000.00 3     Steven      5         Nancy        5    8        
2     1     Andrew   $5,000.00  2     Steven      5          | Andrew    5    9        
5     2     Steven   $2,500.00  1     Steven      5          |  | Steven 5    10     


We can overload the EmpTree operator so as to provide a default value
for the Start_At parameter, ie. the direction of the graph. We make
the default 'M' so the graph starts with the top level manager of the
employee.

We simply supply the literal 'Mgr' for the sort direction for the
same operator whose signiture includes the Start_At parameter.

create operator EmpTree(aTreeTable:typeof(Employees)):
typeof(
       Employees
       add{1 level,'S' empnamerank,1 empidrank, 'T' Tree_Graph, 1 Rank, 1 TreeOrder}
       )
begin
result:= EmpTree(aTreeTable,'Mgr');
end;

     
Here get the tree of employee 'James' starting at the highest level manager
by using the overload signature of the EmpTree operator.

select EmpTree(Employees)
  where empnamerank='James'
  {Tree_Graph,TreeOrder}
      order by {TreeOrder};
     
Tree_Graph        TreeOrder
----------------- ---------
Nancy             38       
 | Janet          39       
 |  | Robert      40       
 |  |  | David    41       
 |  |  |  | James 42       


Here we start with employee 'James' up to his highest level manager.

select EmpTree(Employees,' Emp ')
  where empnamerank='James'
  {Tree_Graph,TreeOrder}
      order by {TreeOrder};
     
Tree_Graph        TreeOrder
----------------- ---------
James             38       
 | David          39       
 |  | Robert      40       
 |  |  | Janet    41       
 |  |  |  | Nancy 42        


Here we use the EmpTree operator to get the enumerated paths in both
directions using the Concat (concatenation) operator. (More info here).

select
 (EmpTree(Employees) add{'.' Del} adorn{key{empidrank,TreeOrder}})
   group by {empidrank}
    add 
          {
            Max(empnamerank) empname,
            Concat(empname,Del order by {empidrank,TreeOrder}) PathMgrtoEmp,
            Concat(empname,Del order by {empidrank,TreeOrder desc}) PathEmptoMgr
          }
     rename {empidrank empid}
      order by {empid};
     
empid empname  PathMgrtoEmp                   PathEmptoMgr                  
----- -------- ------------------------------ ------------------------------
1     Nancy    Nancy                          Nancy                         
2     Andrew   Nancy.Andrew                   Andrew.Nancy                  
3     Janet    Nancy.Janet                    Janet.Nancy                   
4     Margaret Nancy.Margaret                 Margaret.Nancy                
5     Steven   Nancy.Andrew.Steven            Steven.Andrew.Nancy           
6     Michael  Nancy.Andrew.Michael           Michael.Andrew.Nancy          
7     Robert   Nancy.Janet.Robert             Robert.Janet.Nancy            
8     Laura    Nancy.Janet.Laura              Laura.Janet.Nancy             
9     Ann      Nancy.Janet.Ann                Ann.Janet.Nancy               
10    Ina      Nancy.Margaret.Ina             Ina.Margaret.Nancy            
11    David    Nancy.Janet.Robert.David       David.Robert.Janet.Nancy      
12    Ron      Nancy.Janet.Robert.Ron         Ron.Robert.Janet.Nancy        
13    Dan      Nancy.Janet.Robert.Dan         Dan.Robert.Janet.Nancy        
14    James    Nancy.Janet.Robert.David.James James.David.Robert.Janet.Nancy
    

Here we get the counts of employees directly or indirectly reporting to managers.

select
  Employees
    explode
      by empid = parent mgrid
         where  empid>=1
   order by {empid}
       include level
   with {IgnoreUnsupported = 'true'}
     group by {mgrid} add{Count() MgrCnt}
      where mgrid>0

 mgrid MgrCnt
 ----- ------
 1     13    
 2     2     
 3     7     
 4     1     
 7     4     
11     1    


Here are the employees who are the managers. For example there are 13 people
who report to Nancy. This is represented indirectly by people who report
to the three managers directly below her (Andrew, Janet, Margaret) and
directly by the same managers reporting to her. Dan, David and Ron report
to Robert. But there is an additional employee reporting to David (James)
so Robert (mgrid 7) has 4 employees reporting to him.

select
 (
  Employees
    explode
      by empid = parent mgrid
         where  empid>=1
   order by {empid}
       include level
   with {IgnoreUnsupported = 'true'}
     group by {mgrid} add{Count() MgrCnt}
  )
   join Employees
     where mgrid>0
      join  ( Employees {empid MgrEmpid,empname MgrName} )
        by mgrid=MgrEmpid
      {mgrid,MgrName,empname,MgrCnt};
     
mgrid MgrName  empname  MgrCnt
----- -------- -------- ------
1     Nancy    Andrew   13    
1     Nancy    Janet    13    
1     Nancy    Margaret 13    
2     Andrew   Michael  2     
2     Andrew   Steven   2     
3     Janet    Ann      7     
3     Janet    Laura    7     
3     Janet    Robert   7     
4     Margaret Ina      1     
7     Robert   Dan      4     
7     Robert   David    4     
7     Robert   Ron      4     
11    David    James    1           


Here we get salaries of subordinates under managers. Those employees
who are not managers are omitted.

var T:=
Employees
explode  
by mgrid = parent empid
     where  mgrid>=0
      order by {empid}
       include level
   with {IgnoreUnsupported = 'true'};
//Get a dense rank. This rank binds all rows for each employee
//together. The idea is to increment a count for every level 1 since
//a level 1 indicates the start of a new employee.
var TR:=
       T add{case when level=1 then empname else nil end NameEmp}
        add
           {
            Count(
                  T rename {sequence sequenceX}
                   where  (sequenceX<=sequence) and (level=1)
                  ) 
             Rank
            };
var SR:=
   (
     TR               
      join
       (
        TR group by {Rank}
        //We want the empid and name for each dense rank.
          add{Min(empid) NumEmpid,Max(NameEmp) Emp_Name}
        )                        
    )
    //We only want managers, those that have subordinates.
     where
     NumEmpid
              in
                ( Employees {mgrid} ) with {IgnoreUnsupported = 'true'}
      add {
         ( (empname+ case when level>1 then ' ('+ToString(salary)+')'
             else '' end).Insert(0,''.PadLeft((level-1),'|'))).Replace('|',' | ')
              Mgr_Sal_Tree
          };

select SR {Mgr_Sal_Tree,sequence} order by {sequence};   

Mgr_Sal_Tree                  sequence
----------------------------- --------
Nancy                         1       
 | Andrew ($5,000.00)         2       
 |  | Steven ($2,500.00)      3       
 |  | Michael ($2,500.00)     4       
 | Janet ($5,000.00)          5       
 |  | Robert ($2,500.00)      6       
 |  |  | David ($2,000.00)    7       
 |  |  |  | James ($1,500.00) 8       
 |  |  | Ron ($2,000.00)      9       
 |  |  | Dan ($2,000.00)      10      
 |  | Laura ($2,500.00)       11      
 |  | Ann ($2,500.00)         12      
 | Margaret ($5,000.00)       13      
 |  | Ina ($2,500.00)         14      
Andrew                        15      
 | Steven ($2,500.00)         16      
 | Michael ($2,500.00)        17      
Janet                         18      
 | Robert ($2,500.00)         19      
 |  | David ($2,000.00)       20      
 |  |  | James ($1,500.00)    21      
 |  | Ron ($2,000.00)         22      
 |  | Dan ($2,000.00)         23      
 | Laura ($2,500.00)          24      
 | Ann ($2,500.00)            25      
Margaret                      26      
 | Ina ($2,500.00)            27      
Robert                        30      
 | David ($2,000.00)          31      
 |  | James ($1,500.00)       32      
 | Ron ($2,000.00)            33      
 | Dan ($2,000.00)            34      
David                         38      
 | James ($1,500.00)          39    

Here is the same tree as above (of salaries for subordinates) using a
table and a view created with a pass-thru query.

We can create a table based on the result of explode.

create table Emp_T
from
     (
       Employees
       explode  
       by mgrid = parent empid
       where  mgrid>=0
       order by {empid}
       include level
       with {IgnoreUnsupported = 'true'}
       add{case when level=1 then empname else nil end NameEmp}
        adorn  //We can include various meta-data about the columns of the table.
             {
              NameEmp nil static tags {Storage.Length = "10"},
              empname static tags {Storage.Length = "10"}
             }//end adorn.
     );  

Now we get the dense rank using a pass-thru query to Sql Server. The result
of the sql query could be set to var TR which means that TR is a table
variable in D4. The TR variable is therefore of the same nature
no matter how it (a table variable) was derived. Or we could create
a view based on the pass-thru query and use that.
var TR:= but we're using a view instead of setting the pass-thru to var TR.

create view TR
  SQLQuery("select A.*, 
      (select Count(*)
              from Emp_T as B
                 where (B.sequence<=A.sequence) and (B.level=1)) as Rank
          from Emp_T as A");

Use the TR view in a batch to get the salary tree.

var SR:=
   (
     TR               
      join
       (
        TR group by {Rank}
        //We want the empid and name for each dense rank.
                add{Min(empid) NumEmpid,Max(NameEmp) Emp_Name}
        )                        
    )
    //We only want managers, those that have subordinates.
     where
     NumEmpid
              in
                ( Employees {mgrid} ) with {IgnoreUnsupported = 'true'}
      add {
         ( (empname+ case when level>1 then ' ('+ToString(salary)+')'
             else '' end).Insert(0,''.PadLeft((level-1),'|'))).Replace('|',' | ')
              Mgr_Sal_Tree
          };
select SR {Mgr_Sal_Tree,sequence} order by {sequence};

Mgr_Sal_Tree             sequence
------------------------ --------
Nancy                    1       
 | Andrew (5000)         2       
 |  | Steven (2500)      3       
 |  | Michael (2500)     4       
 | Janet (5000)          5       
 |  | Robert (2500)      6       
 |  |  | David (2000)    7       
 |  |  |  | James (1500) 8       
 |  |  | Ron (2000)      9       
 |  |  | Dan (2000)      10      
 |  | Laura (2500)       11      
 |  | Ann (2500)         12      
 | Margaret (5000)       13      
 |  | Ina (2500)         14      
Andrew                   15      
 | Steven (2500)         16      
 | Michael (2500)        17      
Janet                    18      
 | Robert (2500)         19      
 |  | David (2000)       20      
 |  |  | James (1500)    21      
 |  | Ron (2000)         22      
 |  | Dan (2000)         23      
 | Laura (2500)          24      
 | Ann (2500)            25      
Margaret                 26      
 | Ina (2500)            27      
Robert                   30      
 | David (2000)          31      
 |  | James (1500)       32      
 | Ron (2000)            33      
 | Dan (2000)            34      
David                    38      
 | James (1500)          39


Here we get the sum of salaries for subordinates under managers using
the TR view. Eliminating level 1 in the query excludes the managers
salary in the sum. Again the dense rank idea makes this an easy query.

select
   (
    TR               
      join //This is a natural join based on Rank.
       (
        TR group by {Rank}
        //We want the empid and name for each dense rank.
            add{Min(empid) NumEmpid,Max(NameEmp) Emp_Name}
        )//->The relation of view TR being group by Rank.
    )//->The relation from TR joined to (TR grouped by Rank) 
          where level>1 //A 'where' applied to above relation. This relation
                        //is now grouped by NumEmpid to get subordinate salaries.
            group by{NumEmpid} add{Max(Emp_Name) Emp_Name,Sum(salary) SumSalary}
              order by {NumEmpid};

NumEmpid Emp_Name SumSalary 
-------- -------- ----------
1        Nancy    37500.0000
2        Andrew   5000.0000 
3        Janet    15000.0000
4        Margaret 2500.0000 
7        Robert   7500.0000 
11       David    1500.0000