Hierarchical Data - Storage and Queries

Storing Hierarchical Data
Bill Karwin - Models for Hierarchical Data
Hierarchical as relational
StackOverflow - Options for Hierarchical in RDBMS
StackOverflow - Store and navigate hierarchies
Implementing a Closure Table
Querying Hierarchical Data
START WITH...CONNECT BY documentation
AMIS Blog on Recursive Subquery Refactoring replacement for CONNECT BY
Detecting Cycles in Hierarchical Data

-- Simple 3 node tree with no cycle
CREATE TABLE EMPLOYEE_CYCLE (ENAME VARCHAR2(20), MGR VARCHAR2(20));
insert into employee_cycle values ('EMP1',NULL);
insert into employee_cycle values ('EMP2','EMP1');
insert into employee_cycle values ('EMP3','EMP2');
commit;

-- This query shows entries involved in a cycle
-- In this case it will return Zero Records
SELECT
   SYS_CONNECT_BY_PATH (ENAME,'/') as EMPLOYEE_NAME, 
   MGR, 
   CONNECT_BY_ISCYCLE 
FROM
   employee_cycle
WHERE CONNECT_BY_ISCYCLE  = 1
CONNECT BY NOCYCLE PRIOR ENAME = MGR;

-- Introduce a cycle into the tree, change EMP1's manager to EMP3
UPDATE employee_cycle set MGR='EMP3' WHERE ENAME='EMP1';
COMMIT;

-- This query shows entries involved in a cycle
-- In this case it will return 1 record for each entry involved in a cycle. 
SELECT
   SYS_CONNECT_BY_PATH (ENAME,'/') as EMPLOYEE_NAME, 
   MGR, 
   CONNECT_BY_ISCYCLE 
FROM
   employee_cycle
WHERE CONNECT_BY_ISCYCLE  = 1
CONNECT BY NOCYCLE PRIOR ENAME = MGR;

The 2nd query detects and returns all entries involved in a cycle:

EMPLOYEE_NAME        MGR     CONNECT_BY_ISCYCLE
-------------------- ------- ------------------
/EMP2/EMP3/EMP1      EMP3                     1 
/EMP3/EMP1/EMP2      EMP1                     1 
/EMP1/EMP2/EMP3      EMP2                     1 

Cycle Detection with Recursive Subquery Refactoring

Closure Table Demo

-- Closure Table Demo

-- I have seen lots of demos of closure table but most just hit the trivial 
-- cases - one tree stored in a table. Here is some exploration of 
-- multiple trees living in the same table. 

--             1                               10
--           / |  \                           /  \
--          2  3   6                        11   12
--             |     \
--             4      7
--             |
--             5

CREATE TABLE REL (ANCESTOR NUMBER, DESCENDANT NUMBER);

-- Data for Table 1
INSERT INTO REL VALUES (1,1);
INSERT INTO REL VALUES (1,2);
INSERT INTO REL VALUES (1,3);
INSERT INTO REL VALUES (1,4);
INSERT INTO REL VALUES (1,5);
INSERT INTO REL VALUES (1,6);
INSERT INTO REL VALUES (1,7);

INSERT INTO REL VALUES (2,2);

INSERT INTO REL VALUES (3,3);
INSERT INTO REL VALUES (3,4);
INSERT INTO REL VALUES (3,5);

INSERT INTO REL VALUES (4,4);
INSERT INTO REL VALUES (4,5);

INSERT INTO REL VALUES (5,5);

INSERT INTO REL VALUES (6,6);
INSERT INTO REL VALUES (6,7);

INSERT INTO REL VALUES (7,7);

-- Data for Table 2
INSERT INTO REL VALUES (10,10);
INSERT INTO REL VALUES (10,11);
INSERT INTO REL VALUES (10,12);

INSERT INTO REL VALUES (11,11);

INSERT INTO REL VALUES (12,12);

COMMIT;

-- What are the root nodes? 
SELECT DISTINCT ANCESTOR
FROM REL
WHERE DESCENDANT NOT IN
  ( SELECT DESCENDANT FROM REL WHERE ANCESTOR<>DESCENDANT );

-- What are the children of 3 exclusive?
SELECT DESCENDANT FROM REL WHERE ANCESTOR=3 AND DESCENDANT<>ANCESTOR;

DESCENDANT
----------
         4 
         5 

-- What are the parents of 3?
SELECT ANCESTOR FROM REL WHERE DESCENDANT=3 AND DESCENDANT<>ANCESTOR;

ANCESTOR
--------
       1