Archive

Archive for October, 2016

How To : Convert Path Enumeration to Adjency List

October 4, 2016 Leave a comment

An Adjency List is a way to describe a finite graph structure by associating each vertex of the graph to each of its neighbours.
For a simple oriented tree, a possible implemention of the Adjency List model is to store a node along with its parent node reference.
In a RDBMS, this is indeed a very common way of storing hierarchical data, such as the Employee-Manager relationship :

SQL> select empno, ename, mgr
  2  from scott.emp;
 
EMPNO ENAME        MGR
----- ---------- -----
 7369 SMITH       7902
 7499 ALLEN       7698
 7521 WARD        7698
 7566 JONES       7839
 7654 MARTIN      7698
 7698 BLAKE       7839
 7782 CLARK       7839
 7788 SCOTT       7566
 7839 KING       
 7844 TURNER      7698
 7876 ADAMS       7788
 7900 JAMES       7698
 7902 FORD        7566
 7934 MILLER      7782

Such a structure can be easily traversed using a CONNECT-BY query, or Recursive Subquery Factoring :

SQL> select ename, ltrim(sys_connect_by_path(ename, '/'), '/') as path
  2  from scott.emp
  3  connect by prior empno = mgr
  4  start with mgr is null
  5  order siblings by empno;
 
ENAME      PATH
---------- -----------------------------------------------------------
KING       KING
JONES      KING/JONES
SCOTT      KING/JONES/SCOTT
ADAMS      KING/JONES/SCOTT/ADAMS
FORD       KING/JONES/FORD
SMITH      KING/JONES/FORD/SMITH
BLAKE      KING/BLAKE
ALLEN      KING/BLAKE/ALLEN
WARD       KING/BLAKE/WARD
MARTIN     KING/BLAKE/MARTIN
TURNER     KING/BLAKE/TURNER
JAMES      KING/BLAKE/JAMES
CLARK      KING/CLARK
MILLER     KING/CLARK/MILLER
 
SQL> with tree_walker (empno, ename, path) as (
  2    select empno, ename, ename
  3    from scott.emp
  4    where mgr is null
  5    union all
  6    select e.empno, e.ename, w.path || '/' || e.ename
  7    from tree_walker w
  8         join scott.emp e on e.mgr = w.empno
  9  )
 10  search depth first by empno set emp_order
 11  select ename, path
 12  from tree_walker;
 
ENAME      PATH
---------- ---------------------------------------------
KING       KING
JONES      KING/JONES
SCOTT      KING/JONES/SCOTT
ADAMS      KING/JONES/SCOTT/ADAMS
FORD       KING/JONES/FORD
SMITH      KING/JONES/FORD/SMITH
BLAKE      KING/BLAKE
ALLEN      KING/BLAKE/ALLEN
WARD       KING/BLAKE/WARD
MARTIN     KING/BLAKE/MARTIN
TURNER     KING/BLAKE/TURNER
JAMES      KING/BLAKE/JAMES
CLARK      KING/CLARK
MILLER     KING/CLARK/MILLER
 

Now, what if we want to – given only a list of paths – generate back an adjency data set?

For example, from this list of leaf paths :

KING/BLAKE/ALLEN
KING/BLAKE/JAMES
KING/BLAKE/MARTIN
KING/BLAKE/TURNER
KING/BLAKE/WARD
KING/CLARK/MILLER
KING/JONES/FORD/SMITH
KING/JONES/SCOTT/ADAMS

to :

  ID NAME     PARENT_ID
---- -------- ---------
   1 KING     
   2 JONES            1
   3 SCOTT            2
   4 ADAMS            3
   5 FORD             2
   6 SMITH            5
   7 BLAKE            1
   8 ALLEN            7
   9 WARD             7
  10 MARTIN           7
  11 TURNER           7
  12 JAMES            7
  13 CLARK            1
  14 MILLER          13

This post presents a way to achieve that result, using a pipelined table function.

 
Read more…