Reputation: 303

How to convert graph table into adjacency list using Oracle SQL only

Please help me to figure out how to convert data stored as a graph into adjacency table. I am running on Oracle 11g R2

I have the following table:

CREATE TABLE "GRAPH_TBL"
("PARENT_NAME" VARCHAR2(80 CHAR), 
"CHILD_NAME" VARCHAR2(80 CHAR), 
"PARENT_ID" VARCHAR2(18 CHAR), 
"CHILD_ID" VARCHAR2(18 CHAR), 
"RELATIVE_LEVEL" NUMBER(18,0)
);

with this sample data:

Insert into GRAPH_TBL PARENT_NAME,CHILD_NAME,PARENT_ID,CHILD_ID,RELATIVE_LEVEL) values ('Components','Components','a044100000171bXAAQ','a044100000171bXAAQ',0);
Insert into GRAPH_TBL (PARENT_NAME,CHILD_NAME,PARENT_ID,CHILD_ID,RELATIVE_LEVEL) values ('Processors','Processors','a044100000171bYAAQ','a044100000171bYAAQ',0);
Insert into GRAPH_TBL (PARENT_NAME,CHILD_NAME,PARENT_ID,CHILD_ID,RELATIVE_LEVEL) values ('Intel','Intel','a044100000171bZAAQ','a044100000171bZAAQ',0);
Insert into GRAPH_TBL (PARENT_NAME,CHILD_NAME,PARENT_ID,CHILD_ID,RELATIVE_LEVEL) values ('Xeon 5600','Xeon 5600','a044100000171bdAAA','a044100000171bdAAA',0);
Insert into GRAPH_TBL (PARENT_NAME,CHILD_NAME,PARENT_ID,CHILD_ID,RELATIVE_LEVEL) values ('Intel','Xeon 5600','a044100000171bZAAQ','a044100000171bdAAA',1);
Insert into GRAPH_TBL (PARENT_NAME,CHILD_NAME,PARENT_ID,CHILD_ID,RELATIVE_LEVEL) values ('Processors','Intel','a044100000171bYAAQ','a044100000171bZAAQ',1);
Insert into GRAPH_TBL (PARENT_NAME,CHILD_NAME,PARENT_ID,CHILD_ID,RELATIVE_LEVEL) values ('Processors','Xeon 5600','a044100000171bYAAQ','a044100000171bdAAA',2);
Insert into GRAPH_TBL (PARENT_NAME,CHILD_NAME,PARENT_ID,CHILD_ID,RELATIVE_LEVEL) values ('Xeon 5600','Intel Xeon E5645 2.4Ghz, 12M Cache,Turbo, HT, 1333MHz Max Mem','a044100000171bdAAA','a044100000171grAAA',1);
Insert into GRAPH_TBL (PARENT_NAME,CHILD_NAME,PARENT_ID,CHILD_ID,RELATIVE_LEVEL) values ('Components','Processors','a044100000171bXAAQ','a044100000171bYAAQ',1);
Insert into GRAPH_TBL (PARENT_NAME,CHILD_NAME,PARENT_ID,CHILD_ID,RELATIVE_LEVEL) values ('Eclipse Products and Services','Eclipse Products and Services','a044100000171aQAAQ','a044100000171aQAAQ',0);
Insert into GRAPH_TBL (PARENT_NAME,CHILD_NAME,PARENT_ID,CHILD_ID,RELATIVE_LEVEL) values ('Components','Intel','a044100000171bXAAQ','a044100000171bZAAQ',2);
Insert into GRAPH_TBL (PARENT_NAME,CHILD_NAME,PARENT_ID,CHILD_ID,RELATIVE_LEVEL) values ('Components','Xeon 5600','a044100000171bXAAQ','a044100000171bdAAA',3);
Insert into GRAPH_TBL (PARENT_NAME,CHILD_NAME,PARENT_ID,CHILD_ID,RELATIVE_LEVEL) values ('Eclipse Products and Services','Processors','a044100000171aQAAQ','a044100000171bYAAQ',2);
Insert into GRAPH_TBL (PARENT_NAME,CHILD_NAME,PARENT_ID,CHILD_ID,RELATIVE_LEVEL) values ('Eclipse Products and Services','Intel','a044100000171aQAAQ','a044100000171bZAAQ',3);
Insert into GRAPH_TBL (PARENT_NAME,CHILD_NAME,PARENT_ID,CHILD_ID,RELATIVE_LEVEL) values ('Eclipse Products and Services','Xeon 5600','a044100000171aQAAQ','a044100000171bdAAA',4);
Insert into GRAPH_TBL (PARENT_NAME,CHILD_NAME,PARENT_ID,CHILD_ID,RELATIVE_LEVEL) values ('Eclipse Products and Services','Components','a044100000171aQAAQ','a044100000171bXAAQ',1);
Insert into GRAPH_TBL (PARENT_NAME,CHILD_NAME,PARENT_ID,CHILD_ID,RELATIVE_LEVEL) values ('Intel Xeon E5645 2.4Ghz, 12M Cache,Turbo, HT, 1333MHz Max Mem','Intel Xeon E5645 2.4Ghz, 12M Cache,Turbo, HT, 1333MHz Max Mem','a044100000171grAAA','a044100000171grAAA',0);
commit;

This data set represents just one single path from a product to a top level category. It looks like this:

Eclipse Products and Services (this is my root category)
 Components (some category)
  Processors (some category)
   Intel (some category)
    Xeon 5600 (some category)
     Intel Xeon E5645 2.4Ghz, 12M Cache,Turbo, HT, 1333MHz Max Mem (this is my leaf node, product)

In real table there are thousands of products with various number of categories. A leaf node (actual product) can be in more than one category but it is a separate path within a tree. Root level node is a single node within my tree, that is all paths lead up only to it, there are no other roots.

relative level indicates edges of the graph for categories:
0 - node itself, self relationship 1 - next direct immediate node (direct parent - child relationship)
2 - one hop over
3 - two hops over
4 - three hops over

Edges for hops >=2 are defined only for first immediate category my leaf product belongs to. In my sample data it starts with Xeon 5600. There is no edge for leaf node.

The output I need to produce is below:

NAME                                                            ID                  PARENT_ID
Eclipse Products and Services                                   a044100000171aQAAQ  a044100000171aQAAQ
Components                                                      a044100000171bXAAQ  a044100000171aQAAQ
Processors                                                      a044100000171bYAAQ  a044100000171bXAAQ
Intel                                                           a044100000171bZAAQ  a044100000171bYAAQ
Xeon 5600                                                       a044100000171bdAAA  a044100000171bZAAQ
Intel Xeon E5645 2.4Ghz, 12M Cache,Turbo, HT, 1333MHz Max Mem   a044100000171grAAA  a044100000171bdAAA

Thank you for your time and help!

Here is what I tried with some variations so far, unfortunately it does not produce what I expect:

select t1.child_name as L1, t2.child_name as L2, t3.child_name as L3,     t4.child_name as L4, t5.child_name as L5, t6.child_name as L6, t7.child_name as L7
from GRAPH_TBL t1
join GRAPH_TBL t2 on t1.parent_id = t2.child_id
join GRAPH_TBL t3 on t2.parent_id = t3.child_id
join GRAPH_TBL t4 on t3.parent_id = t4.child_id
join GRAPH_TBL t5 on t4.parent_id = t5.child_id
join GRAPH_TBL t6 on t5.parent_id = t6.child_id
join GRAPH_TBL t7 on t6.parent_id = t7.child_id

;

Upvotes: 1

Answers (3)

Mike

Reputation: 2005

with Q as (
   select level as l, is_child,
          parent_name, child_name, parent_id, child_id
     from GRAPH_TBL T,
          (select 0 as is_child from dual union select 1 from dual)

    start with parent_name='Xeon 5600' and parent_id=child_id

  connect by nocycle
          (  (child_id=prior parent_id and is_child=0)
            or
             (parent_id=prior child_id and is_child=1)
          )
      and relative_level=1
      and is_child=prior is_child
)
select child_name, child_id as ID, parent_id, l, is_child
  from Q
 where parent_id<>child_id
union all
select parent_name, parent_id, parent_id, l+1, is_child
  from Q
 where l=(select max(l) from Q where is_child=0) and is_child=0
order by is_child, l desc

Result:

CHILD_NAME                  ID                  PARENT_ID           L   IS_CHILD
Eclipse Products and Servic a044100000171aQAAQ  a044100000171aQAAQ  6   0
Components                  a044100000171bXAAQ  a044100000171aQAAQ  5   0
Processors                  a044100000171bYAAQ  a044100000171bXAAQ  4   0
Intel                       a044100000171bZAAQ  a044100000171bYAAQ  3   0
Xeon 5600                   a044100000171bdAAA  a044100000171bZAAQ  2   0
Intel Xeon E5645 2.4Ghz,... a044100000171grAAA  a044100000171bdAAA  2   1

Upvotes: 1

Ponder Stibbons

Reputation: 14848

As @Mike mentioned in comments it`s not clear what output You want. But here is simple hierarchical query which may be useful in this case:

select lpad(' ', 4 * (level - 1))||child_name name
  from graph_tbl gt
  start with relative_level = 0 
  connect by relative_level <> 0 and parent_id = prior child_id

Also please check the level pseudocolumn, sys_connect_by_path and connect_by_root:

select gt.relative_level, parent_name, child_name,
       level, sys_connect_by_path(child_name, '  ->  ') path, 
       connect_by_root(child_name) root 
  from graph_tbl gt
  start with relative_level = 0 
  connect by relative_level <> 0 and parent_id = prior child_id

Partial output of the first query:

NAME
--------------------------------------------------------------------------------
Eclipse Products and Services
    Components
        Processors
            Intel
                Xeon 5600
                    Intel Xeon E5645 2.4Ghz, 12M Cache,Turbo, HT, 1333MHz Max Me
            Xeon 5600
                Intel Xeon E5645 2.4Ghz, 12M Cache,Turbo, HT, 1333MHz Max Mem
        Intel
            Xeon 5600
                Intel Xeon E5645 2.4Ghz, 12M Cache,Turbo, HT, 1333MHz Max Mem
        Xeon 5600
            Intel Xeon E5645 2.4Ghz, 12M Cache,Turbo, HT, 1333MHz Max Mem
...

Upvotes: 1

lescijus

Reputation: 76

select
  TOP_LEVEL.CHILD_NAME TOP,
  TOP_LEVEL.Relative_Level,
  level_one.child_name lvl_one,
  level_one.Relative_Level,
  level_two.child_name lvl_two,
  level_two.Relative_Level,
  level_three.child_name lvl_three,
  level_three.Relative_Level,
  level_four.child_name lvl_four,
  level_five.child_name lvl_five
from 
  graph_tbl TOP_LEVEL,
  GRAPH_TBL level_one,
  GRAPH_TBL level_two,
  GRAPH_TBL level_three,
  GRAPH_TBL level_four,
  GRAPH_TBL level_five
where
  TOP_LEVEL.Parent_Id = TOP_LEVEL.child_id and
  level_one.parent_id = top_level.child_id and
  level_one.relative_level = 1 and
  level_two.parent_id = level_one.child_id and
  level_two.relative_level = 1 and
  level_three.parent_id = level_two.child_id and
  level_three.relative_level = 1 and
  level_four.parent_id = level_three.child_id and
  level_four.relative_level = 1 and
  level_five.parent_id = level_four.child_id and
  level_five.relative_level = 1

Upvotes: 0

How to convert graph table into adjacency list using Oracle SQL only

Answers (3)

Related Questions