01.00. Graphs, Trees and Hierarchies

-- You can actually represent a two dimensional array, say
-- A[0:5, 0:5], with a table like this:

CREATE TABLE Array_A
(edge CHAR(10) NOT NULL, 
 i INTEGER NOT NULL UNIQUE
   CHECK (i BETWEEN 0 AND 5), 
 j INTEGER NOT NULL UNIQUE
   CHECK (j BETWEEN 0 AND 5), 
 PRIMARY KEY (i, j));

CREATE TABLE Graph
(source CHAR(2) NOT NULL, 
 destination CHAR(2) NOT NULL, 
 cost INTEGER NOT NULL, 
 PRIMARY KEY (source, destination));

INSERT INTO Graph 
VALUES ('s', 's', 0), 
       ('s', 'u', 3), 
       ('s', 'x', 5), 
       ('u', 'u', 0), 
       ('u', 'v', 6), 
       ('u', 'x', 2), 
       ('v', 'v', 0), 
       ('v', 'y', 2), 
       ('x', 'u', 1), 
       ('x', 'v', 4), 
       ('x', 'x', 0), 
       ('x', 'y', 6), 
       ('y', 's', 3), 
       ('y', 'v', 7), 
       ('y', 'y', 0);


CREATE TABLE Paths
(step_1 CHAR(2) NOT NULL, 
 step_2 CHAR(2) NOT NULL, 
 step_3 CHAR(2) NOT NULL, 
 step_4 CHAR(2) NOT NULL, 
 step_5 CHAR(2) NOT NULL, 
 total_cost INTEGER NOT NULL, 
 path_length INTEGER NOT NULL, 
PRIMARY KEY (step_1, step_2, step_3, step_4, step_5));

INSERT INTO Paths
SELECT  G1.source, -- it is 's' in this example
        G2.source, 
        G3.source, 
        G4.source, 
        G4.destination, -- it is 'y' in this example
       (G1.cost + G2.cost + G3.cost + G4.cost), 
       (CASE WHEN G1.source 
                  NOT IN (G2.source, G3.source, G4.source)
             THEN 1 ELSE 0 END
      + CASE WHEN G2.source 
                  NOT IN (G1.source, G3.source, G4.source)
             THEN 1 ELSE 0 END
      + CASE WHEN G3.source 
                  NOT IN (G1.source, G2.source, G4.source)
             THEN 1 ELSE 0 END
      + CASE WHEN G4.source 
                  NOT IN (G1.source, G2.source, G3.source)
             THEN 1 ELSE 0 END)
  FROM Graph AS G1, Graph AS G2, Graph AS G3, Graph AS G4 
 WHERE G1.source = 's'
   AND G1.destination = G2.source
   AND G2.destination = G3.source
   AND G3.destination = G4.source
   AND G4.destination = 'y';

DELETE FROM Paths
 WHERE total_cost
     > (SELECT MIN(total_cost)
          FROM Paths);

DELETE FROM Paths 
 WHERE path_length
       > (SELECT MIN(path_length)FROM Paths); 


CREATE TABLE Personnel_OrgChart
(emp VARCHAR(10) NOT NULL PRIMARY KEY,
 boss VARCHAR(10), -- null means root
 salary DECIMAL(6,2) NOT NULL);

INSERT INTO Personnel_OrgChart(emp, boss, salary)
VALUES ('Albert', NULL, 1000.00),
'Bert', 'Albert', 900.00),
'Chuck', 'Albert', 900.00),
'Donna', 'Chuck ', 800.00),
'Eddie', 'Chuck', 700.00),
'Fred ', 'Chuck', 600.00);

UPDATE Personnel_OrgChart
   SET emp = 'Charles'
 WHERE emp = 'Chuck';

BEGIN ATOMIC 
UPDATE Personnel_OrgChart
   SET emp = 'Charles'
 WHERE emp = 'Chuck';
UPDATE Personnel_OrgChart
   SET boss = 'Charles'
 WHERE boss = 'Chuck';
END;

UPDATE Personnel_OrgChart
   SET emp = CASE WHEN emp = 'Chuck'
                  THEN 'Charles',
                  ELSE emp END,
       boss = CASE WHEN boss = 'Chuck'
                   THEN 'Charles',
                   ELSE boss END
 WHERE 'Chuck' IN (boss, emp);


 DELETE FROM Personnel_OrgChart WHERE emp = 'Chuck';

Suddenly 'Donna', 'Eddie' and 'Fred' find themselves disconnected from the organization and no longer reporting indirectly to 'Albert' anymore.  In fact, they are still reporting to 'Chuck', who does not exist any more!  Using an ON DELETE CASCADE referential action or a TRIGGER could cause the entire subtree to disappear -- probably a bad surprise for Chuck's former subordinates.   

-- self-reference
INSERT INTO Personnel_OrgChart (boss, emp) VALUES (a, a);

-- simple cycle
INSERT INTO Personnel_OrgChart (boss, emp) VALUES (c, b);
INSERT INTO Personnel_OrgChart (boss, emp) VALUES (b, c);

-- 02.03. Fixing the Adjacency List Model

CREATE TABLE Personnel
(emp_nbr INTEGER DEFAULT 0 NOT NULL PRIMARY KEY,
 emp_name VARCHAR(10) DEFAULT '{{vacant}}' NOT NULL,
 address VARCHAR(35) NOT NULL,
 birth_date DATE NOT NULL);

CREATE TABLE OrgChart
(job_title VARCHAR(30) NOT NULL PRIMARY KEY,
 emp_nbr INTEGER DEFAULT 0 -- zero is vacant position
         NOT NULL
         REFERENCES Personnel(emp_nbr)
         ON DELETE SET DEFAULT
         ON UPDATE CASCADE,
 boss_emp_nbr INTEGER  -- null means root node
              REFERENCES Personnel(emp_nbr),
 UNIQUE (emp_nbr, boss_emp_nbr), 
 salary DECIMAL (12,4) NOT NULL CHECK (salary >= 0.00),
 CHECK (boss_emp_nbr <> emp_nbr) -– cannot be your own boss!
 CHECK ((boss_emp_nbr <> emp_nbr) OR (boss_emp_nbr = 0 AND emp_nbr = 0))
 CHECK ((SELECT COUNT(*) FROM OrgChart) -1  -- edges
        = (SELECT COUNT(boss_emp_nbr) FROM OrgChart)) -- nodes
 CHECK (SELECT COUNT(*) FROM OrgChart WHERE boss_emp_nbr IS NULL) = 1)
);

CREATE FUNCTION TreeTest() RETURNS CHAR(6)
LANGUAGE SQL 
DETERMINISTIC
BEGIN ATOMIC
-- put a copy in a temporary table
INSERT INTO Tree SELECT emp, boss FROM Personnel_OrgChart;
-- prune the leaves
WHILE (SELECT COUNT(*) FROM Tree) -1  
       = (SELECT COUNT(boss) FROM Tree) 
DO DELETE FROM Tree
    WHERE Tree.emp 
        NOT IN (SELECT T2.boss 
                  FROM Tree AS T2 
                 WHERE T2.boss IS NOT NULL);
    IF NOT EXISTS (SELECT * FROM Tree)
    THEN RETURN ('Tree  ');
    ELSE RETURN ('Cycles'); 
    END IF;
END WHILE;
END;

CREATE VIEW Personnel_OrgChart (emp_nbr, emp, boss_emp_nbr, boss)
AS SELECT E1.emp_nbr, E1.emp_name, E1.boss_emp_nbr, B1.emp_name
     FROM Personnel AS E1, Personnel AS B1, OrgChart AS O1
    WHERE B1.emp_nbr = P1.boss_emp_nbr
      AND E1.emp_nbr = P1.emp_nbr; 

CREATE PROCEDURE UpTreeTraversal (IN current_emp_nbr INTEGER)
LANGUAGE SQL
DETERMINISTIC
WHILE EXISTS 
      (SELECT * 	
         FROM OrgChart AS T1
        WHERE current_emp_nbr = T1.emp_nbr)
   DO BEGIN 
      -- take some action on the current node of the traversal
      CALL SomeProc (current_emp_nbr);
      -- go up the tree toward the root
      SET current_emp_nbr
          = (SELECT T1.boss_emp_nbr 
               FROM OrgChart AS T1
              WHERE current_emp_nbr = T1.emp_nbr);
      END;
END WHILE;

SELECT O1.emp AS e1, O2.emp AS e2, O3.emp AS e3
   FROM Personnel_OrgChart AS O1, Personnel_OrgChart AS O2, 
        Personnel_OrgChart AS O3
  WHERE O1.emp = O2.boss 
    AND O2.emp = O3.boss 
    AND O1.emp = 'Albert';

SELECT O1.emp AS e1, O2.emp AS e2, O3.emp AS e3, O4.emp AS e4
   FROM Personnel_OrgChart AS O1
        LEFT OUTER JOIN
        Personnel_OrgChart AS O2
        ON O1.emp = O2.boss
          LEFT OUTER JOIN
          Personnel_OrgChart AS O3
          ON O2.emp = O3.boss
            LEFT OUTER JOIN
            Personnel_OrgChart AS O4
            ON O3.emp = O4.boss
  WHERE O1.emp = 'Albert';


 SELECT MAX(CASE
             WHEN seq = 1 THEN e1
             WHEN seq = 2 THEN e2
             WHEN seq = 3 THEN e3
             WHEN seq = 4 THEN e4
             ELSE NULL END)
   FROM (Sequence AS S1
         CROSS JOIN
         << Personnel_OrgChart query as above>>
        ) AS X(e1, e2, e3, e4)
  WHERE seq BETWEEN 1 AND 4;

CREATE LOCAL TEMPORARY TABLE Workingtable 
(boss_emp_nbr INTEGER, 
 emp_nbr INTEGER NOT NULL)
ON COMMIT DELETE ROWS;

CREATE PROCEDURE DeleteSubtree (IN dead_guy INTEGER)
LANGUAGE SQL
DETERMINISTIC
BEGIN ATOMIC
SET CONSTRAINTS <<constriant list>> DEFFERED;
-- mark root of subtree and immediate subordinates
UPDATE OrgChart
   SET emp_nbr = CASE WHEN emp_nbr = dead_guy
                      THEN -99999 ELSE emp_nbr END,
       boss_emp_nbr = CASE WHEN boss_emp_nbr = dead_guy
                       THEN -99999 ELSE boss_emp_nbr END
 WHERE dead_guy IN (emp_nbr, boss_emp_nbr);

WHILE EXISTS -- mark leaf nodes
      (SELECT *
         FROM OrgChart
        WHERE boss_emp_nbr = -99999 
          AND emp_nbr > -99999)
  DO -- get list of next level subordinates
  DELETE FROM WorkingTable;

  INSERT INTO WorkingTable
  SELECT emp_nbr FROM OrgChart WHERE boss_emp_nbr = -99999;

-- mark next level of subordinates
  UPDATE OrgChart
     SET emp_nbr = -99999 
  WHERE boss_emp_nbr IN (SELECT emp_nbr FROM WorkingTable);
END WHILE;

-- delete all marked nodes
DELETE FROM OrgChart
 WHERE emp_nbr = -99999;

SET CONSTRAINTS ALL IMMEDIATE;
END;

CREATE PROCEDURE DeleteAndPromoteSubtree (IN dead_guy INTEGER)
LANGUAGE SQL
DETERMINISTIC 
SET CONSTRAINTS <<list of constraints>> DEFFERED;
BEGIN ATOMIC
DECLARE my_emp_nbr INTEGER;
DECLARE my_boss_emp_nbr INTEGER;

INSERT INTO Workingtable (emp_nbr, boss_emp_nbr)
SELECT T1.emp_nbr, T2.boss_emp_nbr
   FROM OrgChart AS O1, OrgChart AS O2
  WHERE dead_guy IN (O1.boss_emp_nbr, O2.emp_nbr)
    AND dead_guy 
* (SELECT emp FROM OrgChart WHERE boss_emp_nbr IS
NULL);

UPDATE Personnel_OrgChart 
   SET boss = CASE WHEN OrgChart.boss_emp_nbr = dead_guy
                   THEN WorkingTable.emp_nbr 
                   ELSE OrgChart.boss_emp_nbr END,
        emp = CASE WHEN OrgChart.emp_nbr = dead_guy
                   THEN WorkingTable.boss_emp_nbr 
                   ELSE OrgChart.emp_nbr END
 WHERE dead_guy IN (emp_nbr, boss_emp_nbr)
   AND dead_guy <> (SELECT emp_nbr 
                      FROM OrgChart 
                     WHERE boss_emp_nbr IS NULL);

DELETE FROM OrgChart 
 WHERE boss_emp_nbr = emp_nbr;
END;

SET CONSTRAINTS ALL IMMEDIATE;

-- 02.07. Leveled Adjacency List Model

CREATE TABLE Tree
(boss CHAR(1), -- null means root
 emp CHAR(1) NOT NULL,
 lvl INTEGER DEFAULT 0 NOT NULL);

INSETR INTO Tree (boss, emp, lvl)
VALUES (NULL, 'a', 1),
('a', 'b', 2),
('a', 'c', 2),
('b', 'd', 3),
('b', 'e', 3),
('b', 'f', 3),
('e', 'g', 4),
('e', 'h', 4),
('f', 'i', 4),
('g', 'j', 5),
('i', 'k', 5),
('i', 'l', 5);

CREATE PROCEDURE RenumberLevels()
LANGUAGE SQL
DETERMINISTIC 
BEGIN ATOMIC

DECLARE lvl_counter INTEGER;
SET lvl_counter = 1;

-- set root to 1, others to zero
UPDATE Tree
   SET lvl 
       = CASE WHEN boss IS NULL THEN 1 ELSE 0 END;

-- loop thru lvls of the tree
WHILE EXISTS (SELECT * FROM Tree WHERE lvl = 0)
DO
UPDATE Tree
   SET lvl = lvl_counter + 1
 WHERE (SELECT T2.lvl
          FROM Tree AS T2
         WHERE T2.emp = Tree.boss) > 0
   AND lvl = 0;

SET lvl = lvl_counter + 1;
END WHILE;
END;

-- 02.07.02. Aggregation in the Hierarchy

CREATE TABLE PartsExpolsion
(assembly CHAR(1), -- null means root
 subassembly CHAR(1) NOT NULL,
 weight INTEGER DEFAULT 0 NOT NULL,
 lvl INTEGER DEFAULT 0 NOT NULL);

CREATE LOCAL TEMPORARY TABLE Summary
(node CHAR(1) NOT NULL PRIMARY KEY,
 weight INTEGER DEFAULT 0 NOT NULL
) ON COMMIT DELETE ROWS;

CREATE PROCEDURE SummarizeWeights()
LANGUAGE SQL
DETERMINISTIC 
BEGIN ATOMIC
DECLARE max_lvl INTEGER;
SET max_lvl = (SELECT MAX(lvl) FROM PartsExpolsion);

--start with leaf nodes
INSERT INTO Summary (node, total)
SELECT emp, weight
  FROM PartsExpolsion
 WHERE emp NOT IN (SELECT assembly FROM PartsExpolsion);

-- loop up the tree, accumulating totals
WHILE max_lvl > 1
DO INSERT INTO Summary (node, total)
    SELECT T1.assembly, SUM(S1.weight)
      FROM PartsExpolsion AS T1, Summary AS S1
     WHERE T1.assembly = S1.node
       AND T1.lvl = max_lvl
     GROUP BY T1.assembly;
    SET max_lvl = max_lvl - 1;
END WHILE;

--transfer calculations to PartsExpolsion table
UPDATE PartsExpolsion
   SET weight
      = (SELECT weight
           FROM Summary AS S1 
          WHERE S1.node = PartsExpolsion.emp)
 WHERE subassembly IN (SELECT assembly FROM PartsExpolsion);
END; 

-- 03.00. Path Enumeration Models

-- path is a reserved word in SQL-99
-- CHECK() constraint prevents separator in the column.)  

CREATE TABLE Personnel_OrgChart
(emp_name CHAR(10) NOT NULL,
 emp_id CHAR(1) NOT NULL PRIMARY KEY
        CHECK(REPLACE (emp_id, '/', '') = emp_id)),
 path_string VARCHAR(500) NOT NULL);

INDSET INTO Personnel_OrgChart (emp_name, emp_id, path_string)
VALUES ('Albert', 'A', 'A'),
('Bert', 'B', 'AB'),
('Chuck', 'C', 'AC'),
('Donna', 'D', 'ACD'),
('Eddie', 'E', 'ACE'),
('Fred', 'F', 'ACF');

Note that I have not broken the sample table into Personnel (emp_id, path_string) and OrgChart (emp_id, emp_name) tables.  This would be a better design, but allow me this bit of sloppiness to make the code simpler to read. REPLACE (<str_exp_1>, <str_exp_2>, <str_exp_3>) is a common vendor string function.  The first string expression is searched for all occurrences of the second string expression, and if it is found, the second string expression is replaced by the third string expression.  The third string expression can be the empty string as in CHECK () constraint just given.  

/*Another problem is how to prevent cycles in the graph.  A cycle would be represented as a path string in which at least one emp_id string appears twice, such as 'ABCA' in my sample table.  This can be done with a constraint that uses a subquery, thus. */

 CHECK (NOT EXISTS
        (SELECT *
           FROM Personnel_OrgChart AS D1,
                Personnel_OrgChart AS P1
          WHERE CHAR_LENGTH (REPLACE (D1.emp_id, P1.path_string, ''))
                < (CHAR_LENGTH(P1.path_string)
                   - 1) -- size of one emp_id string
        ))

/* Another fact about such a tree is that no path can be longer than the number of nodes in the tree. */

 CHECK ((SELECT MAX(CHAR_LENGTH(path_string))
           FROM Personnel_OrgChart AS P1)
         <= (SELECT COUNT(emp_id) * CHAR_LENGTH(emp_id)
               FROM Personnel_OrgChart AS P2))


-- 03.02. Searching for Subordinates

SELECT *
   FROM Personnel_OrgChart
  WHERE path_string LIKE '%' || :parent_emp_id || '%';


 SELECT *
   FROM Personnel_OrgChart
  WHERE path_string LIKE (SELECT path_string FROM Personnel_OrgChart
                    WHERE emp_id = :parent_emp_id) || '%';

 SELECT *
   FROM Personnel_OrgChart
  WHERE path_string LIKE (SELECT path_string FROM Personnel_OrgChart
                    WHERE emp_id = :parent_emp_id) ||'_';

 SELECT *
   FROM Personnel_OrgChart
  WHERE path_string LIKE (SELECT path_string FROM Personnel_OrgChart
                    WHERE emp_id = :parent_emp_id)
                  || REPLICATE ('_', :n);

SELECT * 
  FROM Personnel_OrgChart
 WHERE path_string LIKE '01.02.01.%'
   AND path_string NOT LIKE '01.02.01.%.%';

-- 03.03. Searching for Superiors

SELECT SUBSTRING (P1.path_string 
            FROM (seq * CHAR_LENGTH(P1.emp_id)) 
             FOR CHAR_LENGTH(P1.emp_id)) AS emp_id
   FROM Personnel_OrgChart AS P1,
        Sequence AS S1  
  WHERE P1.emp_id = :search_emp_id
    AND S1.seq <= CHAR_LENGTH(path_string)/CHAR_LENGTH(emp_id);

The problem is that this does not tell you the relationships among the superiors, only who they are.  Those relationships are actually easier to report.

 SELECT P2.*
   FROM Personnel_OrgChart AS P1,
        Personnel_OrgChart AS P2
  WHERE P1.emp_id = :search_emp_id
    AND POSITION (P2.path_string IN P1.path_string) = 1; 

-- 03.04. Deleting a Subtree

DELETE FROM Personnel_OrgChart
 WHERE path_string LIKE (SELECT path_string FROM Personnel_OrgChart
                   WHERE emp_id = :dead_guy) || '%';

-- 03.05. Deleting a Single Node

BEGIN ATOMIC
DELETE FROM Personnel_OrgChart
 WHERE emp_id = :dead_guy;
UPDATE Personnel_OrgChart
   SET path_string = REPLACE (path_string, :dead_guy, '');
END;

-- 03.06. Inserting a New Node

INSERT INTO Personnel_OrgChart
VALUES (:new_guy, :new_emp_id,
        (SELECT path_string 
           FROM Personnel_OrgChart 
          WHERE emp_id = :new_guy_boss)
         || :new_emp_id);

This basic statement design can be modified to work for insertion of a subtree, thus.

INSERT INTO Personnel_OrgChart
SELECT N1.emp, N1.emp_id,
        (SELECT path_string FROM Personnel_OrgChart WHERE emp_id = :new_tree_boss)
         || N1.emp_id
  FROM NewTree AS N1;

03.07. Splitting up a Path String

/* CharIndex(<search string>, <target string>, <starting position>) is a vendor version of the Standard SQL function POSITION(<search string> IN <target string>).  It begins the search at a position in the target string, thus when the <starting position> = 1, the two are equivalent.  It can defined as */

CREATE FUNCTION CharIndex (IN search_str VARCHAR(1000), IN target VARCHAR(1000), IN start_point INTEGER) RETURNS INTEGER 
RETURN
   (POSITION (search_str 
              IN SUBSTRING (target FROM start_point)) + start_point -1);

-- Version one:

SELECT CASE WHEN SUBSTRING('/' || P1.path_string || '/' FROM S1.seq FOR 1) = '/'
             THEN SUBSTRING('/' || P1.path_string || '/' FROM (S1.seq +1) 
                             FOR CharIndex('/', '/' || P1.path_string || '/', S1.seq +1) 
                                 - S1.seq - 1)
             ELSE NULL END AS emp_id
   FROM Sequence AS S1, Personnel_OrgChart AS P1
  WHERE S1.seq BETWEEN 1 AND CHAR_LENGTH('/' || P1.path_string || '/') - 1
    AND SUBSTRING('/' || P1.path_string || '/' FROM S1.seq FOR 1) = '/' 

-- Version two: 
CREATE VIEW Breakdown (emp_id, step_nbr, subordinate_emp_id)
AS
SELECT emp_id, 
       COUNT(S2.seq),
       SUBSTRING ('/' || P1.path_string || '/', MAX(S1.seq || 1)
                   FROM (S2.seq - MAX(S1.seq || 1))
  FROM Personnel_OrgChart AS P1, Sequence AS S1, Sequence AS S2
 WHERE SUBSTRING ('/' || P1.path_string || '/', S1.seq, 1) = '/'
   AND SUBSTRING ('/' || P1.path_string || '/', S2.seq, 1) = '/'
   AND S1.seq < S2.seq
   AND S2.seq <= CHAR_LENGTH(P1.path_string) +1
 GROUP BY P1.emp_id, P1.path_string, S2.seq;
-- Version Three: Same as above

 SELECT SUBSTRING('/' || P1.path_string || '/' 
                  FROM S1.seq +1
                   FOR CharIndex('/', 
                                 '/' || P1.path_string || '/', 
                                 S1.seq +1)- S1.seq - 1) AS node
   FROM Sequence AS S1, Personnel_OrgChart AS P1
  WHERE SUBSTRING('/' || P1.path_string || '/'
                   FROM S1.seq FOR 1) = '/'
    AND seq < CHAR_LENGTH('/' || P1.path_string || '/');

-- Version four: another way using the LIKE predicate: 

SELECT SUBSTRING(P1.path_string 
                  FROM seq +1 
                   FOR CharIndex('/', P1.path_string, S1.seq +1) - (S1.seq +1))
   FROM Sequence AS S1
        INNER JOIN 
        (SELECT '/' || path_string || '/' 
           FROM Personnel_OrgChart) AS P1.(path_string)
        ON S1.seq <= CHAR_LENGTH(P1.path_string)
           AND SUBSTRING(P1.path_string 
                         FROM S1.seq 
                          FOR CHAR_LENGTH(P1.path_string)) 
               LIKE '/_%';

-- 04.00. Nested Set Model of Hierarchies 
CREATE TABLE OrgChart
(member CHAR(10) NOT NULL PRIMARY KEY, 
 lft INTEGER NOT NULL, 
 rgt INTEGER NOT NULL);

INSERT INTO OrgChart (member, lft, rgt)
VALUES ('Albert', 1, 12)
'Bert', 2, 3)
'Chuck', 4, 11)
'Donna', 5, 6)
'Eddie', 7, 8),
'Fred', 9, 10);

--The root of the tree 
SELECT member, lft, rgt 
  FROM Orgchart
 WHERE lft = 1;

--leaf nodes
SELECT member, lft, rgt 
  FROM Orgchart
 WHERE (rgt - lft) = 1;

SELECT member, lft, rgt 
  FROM Orgchart
 WHERE lft = (rgt - 1);

--  04.02. Finding Subtrees

SELECT Mgrs.member AS boss, Workers.member AS worker
  FROM Orgchart AS Mgrs, Orgchart AS Workers
 WHERE Workers.lft BETWEEN Mgrs.lft AND Mgrs.rgt
   AND Workers.rgt BETWEEN Mgrs.lft AND Mgrs.rgt;

SELECT Mgrs.member AS boss, Workers.member AS worker
  FROM Orgchart AS Mgrs, Orgchart AS Workers
 WHERE Workers.lft BETWEEN Mgrs.lft AND Mgrs.rgt;


-- 04.03. Finding Levels and Paths in a Tree

SELECT O2.member, COUNT(O1.member) AS level
  FROM OrgChart AS O1, OrgChart AS O2
 WHERE O2.lft BETWEEN O1.lft AND O1.rgt
 GROUP BY O2.member;

-- 04.03.01. Finding the Height of a Tree
SELECT MAX(level) AS height
  FROM (SELECT O2.member, (COUNT(O1.member) - 1)
          FROM OrgChart AS O1, OrgChart AS O2
         WHERE O2.lft BETWEEN O1.lft AND O1.rgt
         GROUP BY O2.member) AS L1(member, level);

-- 04.03.02. Finding Levels of Subordinates
CREATE VIEW Immediate_Subordinates (boss, worker, lft, rgt)
AS SELECT Mgrs.member, Workers.member, Workers.lft, Workers.rgt
     FROM OrgChart AS Mgrs, OrgChart AS Workers
    WHERE Workers.lft BETWEEN Mgrs.lft AND Mgrs.rgt
     AND NOT EXISTS -- no middle manager between the boss and us!
          (SELECT *
             FROM OrgChart AS MidMgr
            WHERE MidMgr.lft BETWEEN Mgrs.lft AND Mgrs.rgt
              AND Workers.lft BETWEEN MidMgr.lft AND MidMgr.rgt
              AND MidMgr.member NOT IN (Workers.member, Mgrs.member));

-- The (lft, rgt) numbers for the parent of each node can be reconstructed by
 SELECT boss, MIN(lft) - 1, MAX(rgt) + 1
   FROM Immediate_Subordinates 
  GROUP BY boss;

-- This query can be generalized to any distance (:n) in the hierarchy, thus:
SELECT Workers.member, ' is ', :n, ' levels down from ', :my_member
  FROM OrgChart AS Mgrs, OrgChart AS Workers
 WHERE Mgrs.member = :my_member
   AND Workers.lft BETWEEN Mgrs.lft
                       AND Mgrs.rgt
   AND :n = (SELECT COUNT(MidMgr.member) + 1
               FROM OrgChart AS MidMgr
              WHERE MidMgr.lft BETWEEN Mgrs.lft
                                   AND Mgrs.rgt
                AND Workers.lft BETWEEN MidMgr.lft
                                    AND MidMgr.rgt
                AND MidMgr.member
                    NOT IN (Workers.member, Mgrs.member));

SELECT Workers.member, ' is ', :n, ' levels down from ', :my_member
  FROM OrgChart AS Mgrs, OrgChart AS Workers, 
       OrgChart AS MidMgr
 WHERE Mgrs.member = :my_member
   AND Workers.lft BETWEEN Mgrs.lft AND Mgrs.rgt
   AND MidMgr.lft BETWEEN Mgrs.lft AND Mgrs.rgt
   AND Workers.lft BETWEEN MidMgr.lft AND MidMgr.rgt
   AND MidMgr.member NOT IN (Workers.member, Mgrs.member)
 GROUP BY Workers.member 
HAVING :n = COUNT(MidMgr.member);

CREATE TABLE Assemblies
(part CHAR(2) NOT NULL
      REFERENCES Inventory(part) -- assume an inventory
      ON UPDATE CASCADE, 
lft INTEGER NOT NULL,
rgt INTEGER NOT NULL);

INSERT INTO Assemblies (part, lft, rgt)
VALUES ('A', 1, 28), 
       ('B', 2, 5), 
       ('C', 6, 19), 
       ('D', 20, 27), 
       ('E', 3, 4), 
       ('F', 7, 16), 
       ('G', 17, 18), 
       ('H', 21, 26), 
       ('I', 8, 9), 
       ('J', 10, 15), 
       ('K', 22, 23), 
       ('L', 24, 25), 
       ('M', 11, 12), 
       ('N', 13, 14);

CREATE VIEW Flat_Parts(part, level_0, level_1, level_2, level_3)
AS
SELECT A1.part, 
       CASE WHEN COUNT(A3.part) = 2
            THEN A2.node 
            ELSE NULL END AS level_0, 
       CASE WHEN COUNT(A3.part) = 3
            THEN A2.node
            ELSE NULL END AS level_1, 
       CASE WHEN COUNT(A3.part) = 4
            THEN A2.part
            ELSE NULL END AS level_2, 
       CASE WHEN COUNT(A3.part) = 5
            THEN A2.part
            ELSE NULL END AS level_3
  FROM Assemblies AS A1, -- subordinates
       Assemblies AS A2, -- superiors
       Assemblies AS A3  -- items in between them
 WHERE A1.lft BETWEEN A2.lft AND A2.rgt
   AND A3.lft BETWEEN A2.lft AND A2.rgt
   AND A1.lft BETWEEN A3.lft AND A3.rgt
 GROUP BY A1.part, A2.part;

-- show to the path from a node to the root of the tree horizontally.

SELECT part, MAX(level_0), MAX(level_1), 
             MAX(level_2), MAX(level_3)
  FROM Flat_Parts
 GROUP BY part;

SELECT A1.part, 
       (SELECT part
          FROM Assemblies
         WHERE lft = MAX(A2.lft)) AS level_0, 
       (SELECT part
          FROM Assemblies
         WHERE lft = MAX(A3.lft)) AS level_1, 
       (SELECT part
          FROM Assemblies
         WHERE lft = MAX(A4.lft)) AS level_2, 
       (SELECT part
          FROM Assemblies
         WHERE lft = MAX(A5.lft)) AS level_3
  FROM Assemblies AS A1
       LEFT OUTER JOIN
       Assemblies AS A2
       ON A1.lft > A2.lft AND A1.rgt < A2.rgt
          LEFT OUTER JOIN
          Assemblies AS A3
          ON A2.lft > A3.lft AND A2.rgt < A3.rgt
             LEFT OUTER JOIN
             Assemblies AS A4
             ON A3.lft > A4.lft AND A3.rgt < A4.rgt
                LEFT OUTER JOIN
                Assemblies AS A5
                ON A4.lft > A5.lft AND A4.rgt < A5.rgt
 GROUP BY A1.part;

-- 04.03.03. Finding Oldest and Youngest Subordinates

--  Most senior subordinate is found by this query:
SELECT Workers.member, ' is the most senior subordinate of ', :my_member
  FROM OrgChart AS Mgrs, OrgChart AS Workers
 WHERE Mgrs.member = :my_member
   AND Workers.lft = Mgrs.lft + 1; -- leftmost child

-- Most junior subordinate:
SELECT Workers.member, ' is the least senior subordinate of ', :my_member
  FROM OrgChart AS Mgrs, OrgChart AS Workers
 WHERE Mgrs.member = :my_member
   AND Workers.rgt = Mgrs.rgt - 1; -- rightmost child

-- find the n-th sibling of a parent 
SELECT S1.worker, ' is the ', :n, '-th subordinate of ', S1.boss
  FROM Immediate_Subordinates AS S1 
 WHERE S1.boss = :my_member 
   AND :n = (SELECT COUNT(S2.lft) - 1
               FROM Immediate_Subordinates AS S2
              WHERE S2.boss = S1.boss
                AND S2.boss <> S1.worker
                AND S2.lft BETWEEN 1 AND S1.lft);

SELECT O1.member AS boss, S1.worker, 
       COUNT(S2.lft) AS sibling_order
  FROM Immediate_Subordinates AS S1, 
       Immediate_Subordinates AS S2, 
       OrgChart AS O1
 WHERE S1.boss = O1.member
   AND S2.boss = S1.boss
   AND S1.worker <> S2.worker 
   AND S2.lft <= S1.lft
 GROUP BY O1.member, S1.worker;

/* siblings of a given node can be found by looking for a common parent and rows on the same level.  */
CREATE VIEW Siblings (lvl, part, lft, rgt)
AS SELECT COUNT(A2.lft), A1.part, A1.lft, A1.rgt
     FROM Assemblies AS A1, Assemblies AS A2
    WHERE A1.lft BETWEEN A2.lft AND A2.rgt
   GROUP BY A1.part, A1.lft, A1.rgt;

-- This VIEW can then be used for
SELECT DISTINCT S2.part
  FROM Siblings AS S1, Siblings AS S2 
 WHERE S1.part = :my_sibling_part
   AND EXISTS
       (SELECT *
          FROM Siblings AS S0
         WHERE S1.lft BETWEEN S0.lft AND S0.rgt
           AND S2.lft BETWEEN S0.lft AND S0.rgt
           AND S0.lvl = S1.lvl - 1
           AND A1.lvl = A2.lvl);

-- 04.03.04. Finding a Path

SELECT A2.part, 
        (SELECT COUNT(*)
           FROM Assemblies AS A4
          WHERE A4.lft BETWEEN A1.lft AND A1.rgt
            AND A2.lft BETWEEN A4.lft AND A4.rgt) AS path_nbr
    FROM Assemblies AS A1, Assemblies AS A2, Assemblies AS A3
   WHERE A1.part = :start_node
     AND A3.part = :finish_node
     AND A2.lft BETWEEN A1.lft AND A1.rgt
     AND A3.lft BETWEEN A2.lft AND A2.rgt;

-- 04.03.05. Finding Relative Position 

SELECT CASE WHEN :first_member = :second_member
            THEN :first_member || ' is ' || :second_member
            WHEN O1.lft BETWEEN O2.lft AND O2.rgt
            THEN :first_member || ' subordinate to ' || :second_member
            WHEN O2.lft BETWEEN O1.lft AND O1.rgt
            THEN :second_member || ' subordinate to ' || :first_member 
            ELSE :first_member || 'no relation to '  || :second_member
        END
  FROM OrgChart AS O1, OrgChart AS O2 
 WHERE O1.member = :first_member
   AND O2.member = :second_member;

-- 04.04. Functions in the Nested Sets Model

SELECT :my_member, COUNT(Mgrs.member) AS level
  FROM OrgChart AS Mgrs, OrgChart AS Workers
 WHERE Workers.lft BETWEEN Mgrs.lft AND Mgrs.rgt
   AND Workers.member = :my_member;

CREATE TABLE Sales
(member CHAR(10) NOT NULL PRIMARY KEY, 
 sale_amt DECIMAL(12,4) NOT NULL);

SELECT :my_member, SUM(S1.sale_amt) AS total_sales
  FROM OrgChart AS Mgrs, OrgChart AS Workers,
       Sales AS S1
 WHERE Workers.lft BETWEEN Mgrs.lft AND Mgrs.rgt
   AND P1.job_title = Workers.job_title
   AND Mgrs.member = :my_member;

-- quantity columns in the nodes to compute an accumulated total.  
SELECT :this_part, SUM(Subassem.qty * Subassem.price) AS totalcost
  FROM Blueprint AS Assembly, Blueprint AS Subassem
 WHERE Subassem.lft
       BETWEEN Assembly.lft AND Assembly.rgt
   AND Assembly.part = :this_part;

-- 04.05. Deleting Nodes and Subtrees

-- 04.05.01. Deleting Subtrees

DELETE FROM OrgChart
 WHERE lft BETWEEN
   (SELECT lft FROM OrgChart WHERE member = :downsized_guy)
    AND 
   (SELECT rgt FROM OrgChart WHERE member = :downsized_guy);

CREATE PROCEDURE DropTree (IN downsized CHAR(10))
LANGUAGE SQL
DETERMINISTIC
BEGIN ATOMIC
DECLARE drop_member CHAR(10);
DECLARE drop_lft INTEGER;
DECLARE drop_rgt INTEGER;

-- save the dropped subtree data with a singleton SELECT
SELECT member, lft, rgt
  INTO drop_member, drop_lft, drop_rgt
  FROM OrgChart
 WHERE member = downsized;

-- subtree deletion is easy
DELETE FROM OrgChart
 WHERE lft BETWEEN drop_lft and drop_rgt;

-- close up the gap left by the subtree
UPDATE OrgChart
   SET lft = CASE
             WHEN lft > drop_lft
             THEN lft - (drop_rgt - drop_lft + 1)
             ELSE lft END, 
       rgt = CASE
             WHEN rgt > drop_lft
             THEN rgt - (drop_rgt - drop_lft + 1)
             ELSE rgt END
 WHERE lft > drop_lft
    OR rgt > drop_lft;
END; 

UPDATE OrgChart
   SET lft = (SELECT COUNT(*)
                FROM (SELECT lft FROM OrgChart
                       UNION ALL
                      SELECT rgt FROM OrgChart) AS LftRgt (seq)
                WHERE seq <= lft), 
       rgt = (SELECT COUNT(*)
                FROM (SELECT lft FROM OrgChart
                       UNION ALL
                      SELECT rgt FROM OrgChart) AS LftRgt (seq)
               WHERE seq <= rgt);

-- 04.05.02. Deleting a Single Node
CREATE PROCEDURE Downsize(IN downsized_guy CHAR(10))
LANGUAGE SQL
DETERMINISTIC
UPDATE OrgChart
   SET member
       = CASE WHEN OrgChart.member = downsized_guy
                   AND OrgChart.lft +1 = OrgChart.rgt -- leaf node
              THEN '{vacant}'
              WHEN OrgChart.member = downsized_guy
                   AND OrgChart.lft +1 <> OrgChart.rgt -- promote subordinate 
              THEN (SELECT O1.member
                      FROM OrgChart AS O1
                     WHERE OrgChart.lft + 1 = O1.lft)
              WHEN OrgChart.member -- vacate subordinate position
                   = (SELECT O1.member
                      FROM OrgChart AS O1
                     WHERE OrgChart.lft + 1 = O1.lft)
              THEN '{vacant}'
              ELSE member END;

/* This leads to cases:

1) A leaf node has no subordinates to promote, so leave the node vacant.
2) If there is a subordinate, then we have two steps: a) promote subordinate and b) vacate the subordinate's current position.  */

-- 04.05.03. Pruning a Set of Nodes from a Tree

CREATE TABLE Cuts (node CHAR(5) NOT NULL PRIMARY KEY);
-- Next, use a VIEW to drop the subtrees rooted at the cut nodes:

CREATE VIEW PrunedTree (node, lft, rgt)
AS SELECT T1.T1.part, T1.lft, T1.rgt
     FROM Tree AS T1, Tree AS T2, Cuts AS C1
    WHERE T1.lft
          NOT BETWEEN T2.lft +1
                  AND T2.rgt -1
      AND C1.part = T2.part
    GROUP BY T1.part, T1.lft, T1.rgt
   HAVING COUNT(*) = (SELECT COUNT(*) FROM Cuts);

-- 04.06. Closing Gaps in the Tree

CREATE TABLE Assemblies
(part CHAR(2) PRIMARY KEY,
 lft INTEGER NOT NULL UNIQUE,
 rgt INTEGER NOT NULL UNIQUE,
 CONSTRAINT valid_lft CHECK (lft > 0), 
 CONSTRAINT valid_rgt CHECK (rgt > 1), 
 CONSTRAINT valid_range_pair CHECK (lft < rgt));

INSERT INTO Assemblies
VALUES ('A', 1, 28),
       ('B', 2, 5),
       ('C', 6, 19),
       ('D', 20, 27),
       ('E', 3, 4),
       ('F', 7, 16),
       ('G', 17, 18),
       ('H', 21, 26),
       ('I', 8, 9),
       ('J', 10, 15),
       ('K', 22, 23),
       ('L', 24, 25),
       ('M', 11, 12),
       ('N', 13, 14);

-- view with all the (lft, rgt) numbers in a single column.  

CREATE VIEW LftRgt (visit)
AS SELECT lft FROM Assemblies
   UNION
   SELECT rgt FROM Assemblies;

-- This VIEW finds the left numbers in gaps instead of in the tree.  
CREATE VIEW Firstvisit (visit)
AS SELECT (visit + 1)
     FROM LftRgt
    WHERE (visit + 1) NOT IN (SELECT visit FROM LftRgt)
      AND (visit + 1) > 0;

CREATE VIEW LastVisit (visit)
AS SELECT (visit - 1)
     FROM LftRgt
    WHERE (visit - 1) NOT IN (SELECT visit FROM LftRgt)
      AND (visit - 1) < 2 * (SELECT COUNT(*) FROM LftRgt);

CREATE VIEW Gaps (commence, finish, spread)
AS SELECT A1.visit, L1.visit, ((L1.visit - A1.visit) + 1)
     FROM Firstvisit AS A1, LastVisit AS L1
    WHERE L1.visit = (SELECT MIN(L2.visit)
                        FROM LastVisit AS L2
                       WHERE A1.visit <= L2.visit);

CREATE PROCEDURE X1()
LANGUAGE SQL
DETERMINISTIC

WHILE EXISTS (SELECT * FROM Gaps) 
   DO UPDATE Assemblies
         SET rgt = CASE
                   WHEN rgt > (SELECT MIN(commence) FROM Gaps)
                   THEN rgt - 1 ELSE rgt END, 
             lft = CASE
                   WHEN lft > (SELECT MIN(commence) FROM Gaps)
                   THEN lft - 1 ELSE lft END;
END WHILE;

-- start and finish nested sets numbers of the gaps, as well as their spread.  
CREATE VIEW Gaps (commence, finish, spread)
AS SELECT A1.visit, L1.visit, ((L1.visit - A1.visit) + 1)
     FROM Firstvisit AS A1, LastVisit AS L1
    WHERE L1.visit = (SELECT MIN(L2.visit)
                        FROM LastVisit AS L2
                        WHERE A1.visit <= L2.visit);

CREATE PROCEDURE X2()
LANGUAGE SQL
DETERMINISTIC
-- This will have to be repeated until gaps disappear
WHILE EXISTS (SELECT * FROM Gaps)
DO UPDATE Assemblies
        SET rgt = CASE
                  WHEN rgt > (SELECT MIN(commence) FROM Gaps)
                  THEN rgt - 1 ELSE rgt END, 
            lft = CASE
                  WHEN lft > (SELECT MIN(commence) FROM Gaps)
                  THEN lft - 1 ELSE lft END;
END WHILE;

-- 04.07. Summary Functions on Trees

SELECT O2.member, SUM(O1.salary) AS total_salary_budget
  FROM OrgChart AS O1, Personnel AS O2
 WHERE O1.lft BETWEEN O2.lft AND O2.rgt
 GROUP BY O2.member;

-- 04.07.01. Iterative Parts Update

CREATE TABLE Frammis
(part CHAR(2) PRIMARY KEY,
 qty INTEGER NOT NULL
      CONSTRAINT positive_qty CHECK (qty > 0),
 wgt INTEGER DEFAULT 0 NOT NULL,
 CONSTRAINT non_negative_wgt 
     CHECK ((wgt = 0 AND rgt-lft > 1) OR (wgt > 0 AND rgt-lft = 1)),
 lft INTEGER NOT NULL UNIQUE
     CONSTRAINT valid_lft CHECK (lft > 0),
 rgt INTEGER NOT NULL UNIQUE
     CONSTRAINT valid_rgt CHECK (rgt > 1),
 CONSTRAINT valid_range_pair CHECK (lft < rgt));

INSERT INTO Frammis (part, qty, wgt, lft, rgt)
VALUES ('A', 1, 0, 1, 28),
('B', 1, 0, 2, 5),
('C', 2, 0, 6, 19),
('D', 2, 0, 20, 27),
('E', 2, 12, 3, 4),
('F', 5, 0, 7, 16),
('G', 2, 6, 17, 18),
'H', 3, 0, 21, 26),
('I', 4, 8, 8, 9),
('J', 1, 0, 10, 15),
('K', 5, 3, 22, 23),
('L', 1, 4, 24, 25),
('M', 2, 7, 11, 12),
('N', 3, 2, 13, 14);

CREATE TABLE Parts
(part_id CHAR(2) NOT NULL PRIMARY KEY, 
 part_name VARCHAR(15) NOT NULL,
 wgt INTEGER NOT NULL
     CHECK (wgt >= 0),
 supplier_nbr INTEGER NOT NULL
           REFERENCES Suppliers (supplier_nbr));

CREATE PROCEDURE WgtCalc_1 ()
LANGUAGE SQL
DETERMINISTIC
BEGIN 
UPDATE Frammis -- clear out the weights
   SET wgt = 0
 WHERE lft < (rgt - 1);
WHILE EXISTS (SELECT * FROM Frammis WHERE wgt = 0)
DO UPDATE Frammis 
      SET wgt = 
             CASE -- all the children have a weight computed
             WHEN 0 < ALL (SELECT C.wgt 
                              FROM Frammis AS C
                                   LEFT OUTER JOIN
                                   Frammis AS B
                                    ON B.lft
                                       = (SELECT MAX(S.lft)
                                            FROM Frammis AS S
                                           WHERE C.lft > S.lft
                                             AND C.lft < S.rgt)
                           WHERE B.part = Frammis.part)
             THEN (SELECT COALESCE (SUM(C.wgt * C.qty), Frammis.wgt) 
                              FROM Frammis AS C
                                   LEFT OUTER JOIN
                                   Frammis AS B
                                    ON B.lft
                                       = (SELECT MAX(S.lft) 
                                            FROM Frammis AS S
                                           WHERE C.lft > S.lft
                                             AND C.lft < S.rgt)
                           WHERE B.part = Frammis.part)
             ELSE Frammis.wgt END;
END WHILE;
END;

-- 04.07.02. Recursive Parts Update

CREATE FUNCTION WgtCalc2 (IN my_part CHAR(2))
RETURNS INTEGER
LANGUAGE SQL
DETERMINISTIC
-- recursive function
RETURN
(SELECT COALESCE(SUM(Subassemblies.qty
              * CASE WHEN Subassemblies.lft + 1 = Subassemblies.rgt
                     THEN Subassemblies.wgt
                     ELSE WgtCalc (Subassemblies.part)
                     END), MAX(Assemblies.wgt))
  FROM Frammis AS Assemblies
       LEFT OUTER JOIN
       Frammis AS Subassemblies
       ON Assemblies.lft < Subassemblies.lft
          AND Assemblies.rgt > Subassemblies.rgt 
          AND NOT EXISTS
              (SELECT *
                 FROM Frammis
                WHERE lft < Subassemblies.lft
                  AND lft > Assemblies.lft
                  AND rgt > Subassemblies.rgt
                  AND rgt < Assemblies.rgt)

 WHERE Assemblies.part = my_part);

-- We can use the function in a VIEW to get the total weight.
CREATE VIEW TotalWeight (part, qty, wgt, lft, rgt)
AS
SELECT part, qty, WgtCalc(part, lft, rgt)
  FROM Frammis;

-- UPDATE is now trivial
UPDATE Frammis SET wgt = WgtCalc(part);

-- 04.08. Inserting and Updating Trees
CREATE PROCEDURE InsertNewNode
(IN new_part CHAR(2), IN parent_part CHAR(2),
IN new_qty INTEGER, IN new_wgt INTEGER)
LANGUAGE SQL
DETERMINISTICBEGIN ATOMIC
DECLARE parent INTEGER;
SET parent = (SELECT rgt
                FROM Frammis
               WHERE part = parent_part);
UPDATE Frammis
   SET lft = CASE WHEN lft > parent
                  THEN lft + 2
                  ELSE lft END, 
       rgt = CASE WHEN rgt >= parent
                  THEN rgt + 2
                  ELSE rgt END
 WHERE rgt >= parent;
INSERT INTO Frammis (part, qty, wgt, lft, rgt)
VALUES (new_part, new_qty, new_wgt, parent, (parent + 1));
END; 

CREATE PROCEDURE InsertNewNode
(IN new_part CHAR(2), IN lft_sibling_part CHAR(2),
IN new_qty INTEGER, IN new_wgt INTEGER)
LANGUAGE SQL
DETERMINISTIC
BEGIN ATOMIC 
IF (SELECT lft     -- the root has no siblings
      FROM Frammis
     WHERE part = lft_sibling_part) = 1
THEN LEAVE insert_on_lft;
ELSE BEGIN 
     DECLARE lft_sibling INTEGER;
     SET lft_sibling
           = (SELECT rgt

                FROM Frammis
                WHERE part = lft_sibling_part);
     UPDATE Frammis
        SET lft = CASE WHEN lft < lft_sibling
                       THEN lft ELSE lft + 2 END, 
            rgt = CASE WHEN rgt < lft_sibling
                         THEN rgt ELSE rgt + 2 END
      WHERE rgt > lft_sibling;
     INSERT INTO Frammis
     VALUES (new_part, new_qty, new_wgt, (lft_sibling + 1), (lft_sibling + 2));
     END;
END IF;
END;

-- 04.08.01. Moving a Subtree within a Tree

CREATE VIEW LftRgt (i)
AS SELECT lft FROM Tree
   UNION ALL
   SELECT rgt FROM Tree; 

CREATE LOCAL TEMPORARY TABLE WorkingTree
(root CHAR(2) NOT NULL, 
 node CHAR(2) NOT NULL, 
 lft INTEGER NOT NULL, 
 rgt INTEGER NOT NULL, 
 PRIMARY KEY (root, node))
ON COMMIT DELETE ROWS;

CREATE PROCEDURE MoveSubtree
                 (IN my_root CHAR(2), 
                  IN new_parent CHAR(2))
LANGUAGE SQL
DETERMINISTIC
BEGIN ATOMIC
DECLARE right_most_sibling INTEGER; 
DECLARE subtree_size INTEGER;

-- Cannot move a subtree under itself
      DECLARE Self_reference CONDITION;
-- No such subtree root node
      DECLARE No_such_subtree CONDITION;
-- No such parent node in the tree
      DECLARE No_such_parent_node CONDITION;

body_of_proc:
BEGIN
IF my_root = new_parent
   OR new_parent
    IN (SELECT T1.node
          FROM Tree AS T1, Tree AS T2
         WHERE T2.node = my_root
           AND T1.lft BETWEEN T2.lft AND T2.rgt)
THEN SIGNAL Self_reference; -- error handler invoked here
     LEAVE body_of_proc; -- or leave the block
END IF;

IF NOT EXISTS
   (SELECT *
      FROM Tree
     WHERE node = my_root)
THEN SIGNAL No_such_subtree; -- error handler invoked here
     LEAVE body_of_proc; -- or leave the block 
END IF;

IF NOT EXISTS
   (SELECT *
      FROM Tree
     WHERE node = new_parent)
THEN SIGNAL No_such_parent_node; -- error handler invoked here
     LEAVE body_of_proc; -- or leave the block 
END IF;

-- put subtree into working table
INSERT INTO WorkingTree (root, node, lft, rgt)
SELECT my_root, T1.node, 
       T1.lft - (SELECT MIN(lft)
                   FROM Tree
                  WHERE node = my_root), 
       T1.rgt - (SELECT MIN(lft)
                   FROM Tree
                  WHERE node = my_root)
  FROM Tree AS T1, Tree AS T2
 WHERE T1.lft BETWEEN T2.lft AND T2.rgt
   AND T2.node = my_root;

-- remove the subtree from original tree
DELETE FROM Tree
 WHERE node IN (SELECT node FROM WorkingTree);

-- get the spread and location for inserting working tree into tree
SET right_most_sibling
    = (SELECT rgt
         FROM Tree
        WHERE node = new_parent);

SET subtree_size = (SELECT (MAX(rgt) +1) FROM WorkingTree);

-- make a gap in the tree
UPDATE Tree
   SET lft = CASE WHEN lft > right_most_sibling
                  THEN lft + subtree_size
                  ELSE lft END, 
       rgt = CASE WHEN rgt >= right_most_sibling
                  THEN rgt + subtree_size
                  ELSE rgt END
 WHERE rgt >= right_most_sibling;

-- insert the subtree and renumber its rows
INSERT INTO Tree (node, lft, rgt)
SELECT node, 
       lft + right_most_sibling, 
       rgt + right_most_sibling
  FROM WorkingTree;

-- close gaps in tree
UPDATE Tree
   SET lft = (SELECT COUNT(*)
                FROM LftRgt
               WHERE LftRgt.i <= Tree.lft), 
       rgt = (SELECT COUNT(*)
                FROM LftRgt
               WHERE LftRgt.i <= Tree.rgt);

-- clean out working tree table
DELETE FROM WorkingTree;
END body_of_proc;

END; -- of MoveSubtree

-- 04.08.02. MoveSubtree Second Version

CREATE PROCEDURE MoveSubtree
            (IN my_root CHAR(2), IN new_parent CHAR(2))
LANGUAGE SQL
DETERMINISTIC
BEGIN ATOMIC
DECLARE origin_lft INTEGER;
DECLARE origin_rgt INTEGER;
DECLARE new_parent_rgt INTEGER;

SELECT lft, rgt
  INTO origin_lft, origin_rgt
  FROM Tree
 WHERE node = my_root;

SET new_parent_rgt
    = (SELECT rgt
         FROM Tree
        WHERE node = new_parent);

UPDATE Tree
   SET lft
       = lft
         + CASE
           WHEN new_parent_rgt < origin_lft
           THEN CASE

                WHEN lft BETWEEN origin_lft AND origin_rgt
                THEN new_parent_rgt - origin_lft
                WHEN lft BETWEEN new_parent_rgt
                             AND origin_lft -1
                THEN origin_rgt - origin_lft + 1
                ELSE 0 END
           WHEN new_parent_rgt > origin_rgt
           THEN CASE
                WHEN lft BETWEEN origin_lft
                             AND origin_rgt
                THEN new_parent_rgt - origin_rgt -1
                WHEN lft BETWEEN origin_rgt + 1
                             AND new_parent_rgt -1
                THEN origin_lft - origin_rgt -1
                ELSE 0 END          ELSE 0 END, 
       rgt
       = rgt
         + CASE
           WHEN new_parent_rgt < origin_lft
           THEN CASE

                WHEN rgt BETWEEN origin_lft
                             AND origin_rgt
                THEN new_parent_rgt - origin_lft
                WHEN rgt BETWEEN new_parent_rgt AND origin_lft -1
                THEN origin_rgt - origin_lft + 1
                ELSE 0 END
           WHEN new_parent_rgt > origin_rgt
           THEN CASE
                WHEN rgt BETWEEN origin_lft
                             AND origin_rgt
                THEN new_parent_rgt - origin_rgt -1
                WHEN rgt BETWEEN origin_rgt + 1
                             AND new_parent_rgt -1
                THEN origin_lft - origin_rgt -1
                ELSE 0 END
           ELSE 0 END;
END; -- Movesubtree

-- 04.08.03. Subtree Duplication
CREATE TABLE Tree
(node VARCHAR(5) NOT NULL, 
 lft INTEGER NOT NULL, 
 rgt INTEGER NOT NULL, 
 PRIMARY KEY (lft, rgt));

CREATE PROCEDURE CopyTree 
       (IN new_parent VARCHAR(5), 
        IN subtree_root VARCHAR(5))
LANGUAGE SQL
DETERMINISTIC
BEGIN ATOMIC
-- create the gap
UPDATE Tree
   SET lft = CASE WHEN lft > (SELECT rgt
                                FROM Tree
                               WHERE node = new_parent)
                  THEN lft + (SELECT (rgt - lft + 1)
                                FROM Tree
                               WHERE node = subtree_root)
                  ELSE lft END, 
       rgt = CASE WHEN rgt >= (SELECT rgt
                                 FROM Tree
                                 WHERE node = new_parent)
                  THEN rgt + (SELECT (rgt - lft + 1)

                                FROM Tree
                               WHERE node = subtree_root)
                  ELSE rgt END
 WHERE rgt >= (SELECT rgt
                 FROM Tree
                WHERE node = new_parent); 

-- insert the copy
INSERT INTO Tree (node, lft, rgt)
SELECT T1.node || '2', 
       T1.lft
       + (SELECT rgt - lft + 2
            FROM Tree
           WHERE node = subtree_root), 
       T1.rgt
       + (SELECT rgt - lft + 2
            FROM Tree
           WHERE node = subtree_root)
  FROM Tree AS T1, Tree AS T2
 WHERE T2.node = subtree_root
   AND T1.lft BETWEEN T2.lft AND T2.rgt;

END;

-- predicate to prevent copying a subtree under itself and getting endless recursion 
CONSTRAINT new_parent
NOT BETWEEN (SELECT lft FROM Tree WERE node = subtree_root)
        AND (SELECT rgt FROM Tree WERE node = subtree_root)

-- 04.08.04. Swapping Siblings

CREATE PROCEDURE SwapSiblings
       (IN lft_sibling CHAR(2), IN rgt_sibling CHAR(2))
LANGUAGE SQL
DETERMINISTIC

BEGIN ATOMIC
DECLARE i0 INTEGER;
DECLARE i1 INTEGER;
DECLARE i2 INTEGER;
DECLARE i3 INTEGER;
SET i0 = (SELECT lft FROM Tree WHERE node = lft_sibling);
SET i1 = (SELECT rgt FROM Tree WHERE node = lft_sibling);
SET i2 = (SELECT lft FROM Tree WHERE node = rgt_sibling);
SET i3 = (SELECT rgt FROM Tree WHERE node = rgt_sibling); 

UPDATE Tree
   SET lft = CASE WHEN lft BETWEEN i0 AND i1
                  THEN i3 + lft - i1
                  WHEN lft BETWEEN i2 AND i3
                  THEN i0 + lft - i2
                  ELSE i0 + i3 + lft - i1 - i2 END, 
       rgt = CASE WHEN rgt BETWEEN i0 AND i1
                  THEN i3 + rgt - i1
                  WHEN rgt BETWEEN i2 AND i3
                  THEN i0 + rgt - i2
                  ELSE i0 + i3 + rgt - i1 - i2 END
 WHERE lft BETWEEN i0 AND i3
   AND i0 < i1
   AND i1 < i2
   AND i2 < i3;
END;

-- 04.09. Converting Nested Sets Model to Adjacency List

SELECT B.member AS boss, P.member
 FROM OrgChart AS P
       LEFT OUTER JOIN
       Personnel AS B
       ON B.lft = (SELECT MAX(S.lft)
                     FROM OrgChart AS S
                    WHERE P.lft > S.lft
                      AND P.lft < S.rgt);

SELECT B.member AS boss, P.member  
  FROM OrgChart AS B, Personnel AS P
 WHERE P.lft BETWEEN B.lft AND B.rgt
   AND B.member
       = (SELECT MAX(S.member)
            FROM OrgChart AS S
           WHERE S.lft < P.lft
             AND S.rgt > P.rgt);

-- 04.10. Converting Adjacency List to Nested Sets Model 

-- Tree holds the adjacency model
CREATE TABLE Tree
(node CHAR(10) NOT NULL,
 parent CHAR(10));

-- Stack starts empty, will holds the nested set model
CREATE TABLE Stack
(stack_top INTEGER NOT NULL,
 node CHAR(10) NOT NULL,
 lft INTEGER,
 rgt INTEGER);

CREATE PROCEDURE AdjToNested()
LANGUAGE SQL
DETERMINISTIC 
BEGIN ATOMIC

DECLARE lft_rgt INTEGER;
DECLARE max_lft_rgt INTEGER;
DECLARE current_top INTEGER;

SET lft_rgt = 2;
SET max_lft_rgt = 2 * (SELECT COUNT(*) FROM Tree);
SET current_top = 1;

--clear the stack
DELETE FROM Stack;

-- push the root
INSERT INTO Stack
SELECT 1, node, 1, max_lft_rgt
  FROM Tree
 WHERE parent IS NULL;

-- delete rows from tree as they are used
DELETE FROM Tree WHERE parent IS NULL;

WHILE lft_rgt <= max_lft_rgt - 1
DO IF EXISTS (SELECT *
              FROM Stack AS S1, Tree AS T1
             WHERE S1.node = T1.parent
               AND S1.stack_top = current_top)
      THEN BEGIN -- push when top has subordinates and set lft value
       INSERT INTO Stack
       SELECT (current_top + 1), MIN(T1.node), lft_rgt, NULL         FROM Stack AS S1, Tree AS T1
        WHERE S1.node = T1.parent
          AND S1.stack_top = current_top;

        -- delete rows from tree as they are used
        DELETE FROM Tree
         WHERE node = (SELECT node
                        FROM Stack
                       WHERE stack_top = current_top + 1);
        -- housekeeping of stack pointers and lft_rgt
        SET lft_rgt = lft_rgt + 1;
        SET current_top = current_top + 1;
     END;
     ELSE
     BEGIN -- pop the stack and set rgt value
       UPDATE Stack
          SET rgt = lft_rgt,
              stack_top = -stack_top -- pops the stack
        WHERE stack_top = current_top;
       SET lft_rgt = lft_rgt + 1;
       SET current_top = current_top - 1;
     END;  END IF;
END WHILE;
 -- stack top is not needed in final answer

IF EXISTS (SELECT * FROM Tree)
THEN << error handling for orphans in original tree >> 
END IF;
END;

-- 04.11.02. Multiple Nodes

CREATE TABLE Tree
(node INTEGER NOT NULL PRIMARY KEY, 
 lft INTEGER NOT NULL UNIQUE,
 rgt INTEGER NOT NULL UNIQUE, 
  );

-- Now attach various attributes to each node.
CREATE TABLE NodeProperty_1 
(node INTEGER NOT NULL
         REFERENCES Tree (node)
         ON DELETE CASCADE
         ON UPDATE CASCADE, 
 value CHAR(15) NOT NULL);

CREATE TABLE NodeProperty_2
(node INTEGER NOT NULL
         REFERENCES Tree (node)
         ON DELETE CASCADE
         ON UPDATE CASCADE, 
 value CHAR(15) NOT NULL);

-- 04.12. Comparing Nodes and Structure

CREATE TABLE OrgChart_2
 (member CHAR(10) NOT NULL PRIMARY KEY, 
  lft INTEGER NOT NULL UNIQUE CHECK (lft > 0), 
  rgt INTEGER NOT NULL UNIQUE CHECK (rgt > 1), 
  CONSTRAINT order_okay CHECK (lft < rgt));

INSERT INTO OrgChart_2 (member, lft, rgt)
VALUES ('Albert', 1, 12),
('Bert', 2, 3),
 ('Chuck', 4, 5),
('Donna', 6, 7),
 ('Eddie', 8, 9),
('Fred', 10, 11);

-- Do we have the same nodes, but in a different structure?  
SELECT DISTINCT 'They have different sets of nodes'
   FROM (SELECT * FROM OrgChart
         UNION ALL
         SELECT * FROM OrgChart_2) AS P0 (member, lft, rgt)
  GROUP BY P0.member
 HAVING COUNT(*) <> 2;

SELECT DISTINCT 'They have different multi-sets of nodes'
   FROM (SELECT DISTINCT *
           FROM OrgChart)
         UNION ALL
        (SELECT DISTINCT *
           FROM OrgChart_2) AS P0 (member, lft, rgt)
  GROUP BY P0.member
 HAVING COUNT(*) <> 2;

-- Do they have the same structure, but with different nodes? 
CREATE TABLE OrgChart_3
 (member CHAR(10) NOT NULL PRIMARY KEY, 
  lft INTEGER NOT NULL UNIQUE CHECK (lft > 0), 
  rgt INTEGER NOT NULL UNIQUE CHECK (rgt > 1), 
  CONSTRAINT order_okay CHECK (lft < rgt));

INSERT INTO OrgChart_3(member, lft, rgt)
VALUES ('Amber', 1, 12),
( 'Bobby', 2, 3),
 ('Charles', 4, 11),
 ('Donald', 5, 6),
 ('Edward', 7, 8),
 ('Frank', 9, 10);

SELECT DISTINCT 'They have different structures'
   FROM (SELECT * FROM OrgChart)
         UNION ALL
        (SELECT * FROM OrgChart_3) AS P0 (member, lft, rgt)
  GROUP BY P0.lft, P0.rgt
 HAVING COUNT(*) <> 2;

-- are the trees identical?  
SELECT DISTINCT 'They are not identical'
   FROM (SELECT * FROM OrgChart)
         UNION ALL
        (SELECT * FROM OrgChart_3) AS P0 (member, lft, rgt)
  GROUP BY P0.lft, P0.rgt, P0.member
 HAVING COUNT(*) <> 2;

-- comparing subtrees within the same tree
 (SELECT O1.member, 
         O1.lft - (SELECT MIN(lft)
                     FROM OrgChart
                    WHERE member = :my_member_1) + 1,
         O1.rgt - (SELECT MIN(lft)
                     FROM OrgChart
                    WHERE member = :my_member_1) +1 
    FROM OrgChart AS O1, OrgChart AS O2
   WHERE O1.lft BETWEEN O2.lft AND O2.rgt
     AND O2.member = :my_member_1) AS P0 (member, lft, rgt);

05.00. Frequent Insertion Trees

CREATE TABLE OrgChart
(emp CHAR(10) NOT NULL PRIMARY KEY,
 lft INTEGER NOT NULL UNIQUE CHECK (lft > 0),
 rgt INTEGER NOT,
 CONSTRAINT order_okay CHECK (lft < rgt));

OrgChart
emp         lft  rgt
======================
'Albert'   100   1200
'Bert'     200    300
'Chuck'    400   1100
'Donna'    500    600
'Eddie'    700    800
'Fred'     900   1000

INSERT INTO OrgChart VALUES ('Betty', 201, 210); -- spread of 9
INSERT INTO OrgChart VALUES ('Bobby', 202, 203); --spread of 1

CREATE VIEW Spreads (emp, commence, finish)
AS
SELECT O1.emp, MAX(O2.rgt), (O1.rgt-1)
  FROM OrgChart AS O1, OrgChart AS O2
 WHERE O2.lft BETWEEN O1.lft AND O1.rgt
   AND O1.emp <> O2.emp
 GROUP BY O1.emp, O1.rgt
UNION ALL
SELECT O1.emp, (O1.lft +1), (O1.rgt-1)
  FROM OrgChart AS O1
 WHERE NOT EXISTS
       (SELECT *
          FROM OrgChart AS O2
         WHERE O2.lft BETWEEN O1.lft AND O1.rgt
           AND O1.emp <> O2.emp)

CREATE PROCEDURE InsertNewGuy (IN parent CHAR(10), IN new_guy CHAR(10))
BEGIN ATOMIC
DECLARE commence INTEGER; 
DECLARE finish INTEGER;
SET commence = (SELECT commence + 1 FROM Spreads WHERE emp = parent); 
SET finish = (SELECT finish - 1 FROM Spreads WHERE emp = parent);
IF (finish - commence) <= 0 THEN LEAVE; -- error handling needed 

-- give the new guy 1/10 of the remaining spread
INSERT INTO OrgChart
VALUES (new_guy, commence,
        commence + CAST (((finish - commence)/ 10.0) AS INTEGER));
END;

-- 05.02.02. Divisor Parameter
CREATE PROCEDURE InsertNewGuy
       (IN parent CHAR(10), IN new_guy CHAR(10),
        IN divisor INTEGER)
LANGUAGE SQL
DETERMINISTIC
BEGIN
DECLARE commence INTEGER;
DECLARE finish INTEGER;
DECLARE divisor INTEGER;
SET commence
    = (SELECT commence FROM Spreads WHERE emp = parent);
SET finish
    = (SELECT finish FROM Spreads WHERE emp = parent);
INSERT INTO OrgChart
VALUES (new_guy, commence,
        commence + ((finish - commence)/ divisor));
END;

-- 05.02.05. Partial Reorganization 

UPDATE OrgChart
   SET lft = (SELECT COUNT(*)
                FROM LftRgt AS LR
               WHERE LR.seq <= lft),
       rgt = (SELECT COUNT(*)
               FROM LftRgt AS LR
              WHERE LR.seq <= rgt);


-- 05.02.06. Rightward Spread Growth

UPDATE OrgChart
   SET lft = lft + 100,
       rgt = rgt + 100
 WHERE lft > (SELECT rgt
                FROM OrgChart
               WHERE emp = :failure_emp)
    OR rgt >= (SELECT rgt
                 FROM OrgChart
                WHERE emp = :failure_emp);

CREATE PROCEDURE ShiftLeft()
LANGUAGE SQL
DETERMINISTIC
BEGIN ATOMIC
DECLARE squeeze INTEGER;
SET squeeze
    = (SELECT CASE WHEN MIN(O2.lft - O1.rgt) - 1 > 1
                   THEN MIN(O2.lft - O1.rgt) - 1

                   ELSE 1 END
         FROM OrgChart AS O1, OrgChart AS O2
        WHERE O1.rgt < O2.lft
          AND O1.emp <> O2.emp);
UPDATE OrgChart
   SET lft = (lft - squeeze),
       rgt = (rgt - squeeze)
 WHERE (lft - squeeze) > 0
   AND NOT EXISTS
      (SELECT *
         FROM OrgChart AS O1
        WHERE O1.emp <> OrgChart.emp
          AND (O1.lft
               BETWEEN (OrgChart.lft - squeeze)
                   AND (OrgChart.rgt - squeeze)
               OR O1.rgt
               BETWEEN (OrgChart.lft - squeeze)
                   AND (OrgChart.rgt - squeeze)));
END;

-- 05.03. Total Reorganization

UPDATE OrgChart
 SET shift = NULL,
     traversal_nbr = NULL;

-- The NULLs act as markers for the computations.
-- Calculate shift factor within a parent node.
-- Leftmost siblings are computed later.
UPDATE OrgChart
   SET shift
       = lft - 1
         - (SELECT MAX(Siblings.rgt)
              FROM OrgChart AS Siblings
              WHERE Siblings.rgt < OrgChart.lft)
 WHERE shift IS NULL
   AND EXISTS -- has sibling on left side
       (SELECT *
          FROM OrgChart AS Siblings
         WHERE Siblings.rgt < OrgChart.lft);

-- Now it is time to look at the parents and shift them and their family.
UPDATE OrgChart
   SET shift
       = lft - 1
         - (SELECT MAX(Parents.lft)
              FROM OrgChart AS Parents
             WHERE Parents.lft < OrgChart.lft
               AND Parents.rgt > OrgChart.rgt)
 WHERE shift IS NULL
    OR (lft - shift)
       < (SELECT MAX(Parents.lft)
            FROM OrgChart AS Parents
           WHERE Parents.lft < OrgChart.lft
             AND Parents.rgt > OrgChart.rgt);

--At this point, only the root is still NULL. 
UPDATE OrgChart
   SET shift = lft - 1
 WHERE shift IS NULL;

UPDATE OrgChart
   SET traversal_nbr
       = (SELECT COUNT(*)
            FROM OrgChart AS Original_OrgChart
           WHERE Original_OrgChart.lft <= OrgChart.lft);

-- Now it is time to do the big shift.  
UPDATE OrgChart
 SET lft
     = lft
       - (SELECT SUM(shift)
            FROM OrgChart AS Original_OrgChart
           WHERE Original_OrgChart.traversal_nbr
                 <= OrgChart.traversal_nbr),
     rgt
     = rgt
       - (SELECT SUM(shift)
            FROM OrgChart AS Original_OrgChart
           WHERE Original_OrgChart.traversal_nbr
                 <= OrgChart.traversal_nbr);

-- re-set the shift and traversal_nbr columns to NULLs. 
UPDATE OrgChart
 SET shift = NULL,
     traversal_nbr = NULL;

05.03.02. Reorganization with Recursion

CREATE FUNCTION LeftShift (IN my_emp CHAR(10))
RETURNS INTEGER
LANGUAGE SQL
DETERMINISTIC
--recursive
RETURN
  (SELECT CASE WHEN MAX(Par.emp) IS NULL
               THEN 0
               ELSE LeftShift (MAX(Par.emp)) END
          + COALESCE (SUM(Sib.rgt - Sib.lft), 0)
          + COUNT(Sib.emp) + 1
     FROM OrgChart AS E1
          INNER JOIN
          OrgChart AS Par
          ON E1.lft > Par.lft
             AND E1.rgt < Par.rgt
               AND NOT EXISTS
                   (SELECT *
                      FROM OrgChart
                     WHERE lft < E1.lft
                       AND lft > Par.lft
                       AND rgt > E1.rgt
                       AND rgt < Par.rgt)
           LEFT OUTER JOIN
           OrgChart AS Sib
           ON Par.lft < Sib.lft
              AND Par.rgt > Sib.rgt
              AND Sib.lft < E1.lft
     WHERE E1.emp = my_emp);

-- 05.04. Rational Numbers and Nested Intervals model 
CREATE FUNCTION gcd(IN x INTEGER, IN y INTEGER) RETURNS INTEGER
LANGUAGE SQL
DETERMINISTIC
BEGIN 
WHILE x <> y
   DO IF x > y THEN SET x = x - y; END IF;
      IF y > x THEN SET y = y - x; END IF;
END WHILE;
RETURN (x);
END;

--05.04.01. Partial Order mappings 

-- 05.04.02. Summation of Coordinates 
CREATE FUNCTION Find_x_numer (IN numer INTEGER, IN denom INTEGER) 
RETURNS INTEGER 
BEGIN 
DECLARE ret_num INTEGER; 
DECLARE ret_den INTEGER; 
   SET ret_num = numer + 1;
   SET ret_den = 2 * denom; 
   WHILE FLOOR(ret_num/2) = ret_num/2
      DO SET ret_num = ret_num/2;
         SET ret_den = ret_den/2; 
   END WHILE; 
   RETURN ret_num; 
END;

CREATE FUNCTION Find_x_denom (IN numer INTEGER, IN denom INTEGER) 
RETURNS INTEGER 
BEGIN 
DECLARE ret_num INTEGER; 
DECLARE ret_den INTEGER; 
   SET ret_num = numer + 1;
   SET ret_den = 2 * denom; 
   WHILE FLOOR(ret_num/2) = ret_num/2
      DO SET ret_num = ret_num/2;
         SET ret_den = ret_den/2; 
   END WHILE; 
   RETURN ret_den; 
END; 

CREATE FUNCTION y_numer (IN numer INTEGER, IN denom INTEGER) 
RETURNS INTEGER 
LANGUAGE SQL
DETERMINISTIC
BEGIN 
DECLARE num INTEGER;
DECLARE den INTEGER; 
  SET num = x_numer(numer, denom);
  SET den = x_denom(numer, denom);
  WHILE den < denom 
    DO SET num = 2 * num;
       SET den = 2 * den; 
  END WHILE;
  SET num = numer - num; 
  WHILE FLOOR(num/2) = num/2 
     DO SET num = num/2;
        SET den = den/2; 
  END WHILE; 
  RETURN num; 
END;

CREATE FUNCTION y_denom(IN numer INTEGER, IN denom INTEGER) 
LANGUAGE SQL
DETERMINISTIC
BEGIN 
DECLARE num INTEGER;
DECLARE den INTEGER; 
  SET num = x_numer(numer, denom);
  SET den = x_denom(numer, denom);
  WHILE den < denom 
    DO SET num = 2 * num;
       SET den = 2 * den; 
  END WHILE;
  SET num = numer - num; 
  WHILE FLOOR(num/2) = num/2 
     DO SET num = num/2;
        SET den = den/2; 
  END WHILE; 

   RETURN (den); 
END;

-- 05.04.03. Finding Parent Encoding and Sibling Number
CREATE FUNCTION parent_numer (IN numer INTEGER, IN denom INTEGER) 
RETURNS INTEGER 
LANGUAGE SQL
DETERMINISTIC
BEGIN 
DECLARE ret_num INTEGER; 
DECLARE ret_den INTEGER; 
   IF numer = 3 
   THEN RETURN CAST(NULL AS INTEGER);
   END IF;
   SET ret_num = (numer-1)/2;
   SET ret_den = denom/2; 
   WHILE FLOOR((ret_num-1)/4) = (ret_num-1)/4 
      DO SET ret_num = (ret_num + 1)/2;
         SET ret_den = ret_den/2; 
   END WHILE; 
   RETURN ret_num; 
END;

CREATE FUNCTION parent_denom (IN numer INTEGER, IN denom INTEGER) 
LANGUAGE SQL
DETERMINISTIC
BEGIN 
DECLARE ret_num INTEGER; 
DECLARE ret_den INTEGER; 
   IF numer = 3 
   THEN RETURN CAST(NULL AS INTEGER);

   END IF;
   SET ret_num = (numer-1)/2;
   SET ret_den = denom/2; 
   WHILE FLOOR((ret_num-1)/4) = (ret_num-1)/4 
      DO SET ret_num = (ret_num + 1)/2;
         SET ret_den = ret_den/2; 
   END WHILE; 
   RETURN ret_den; 
END;

CREATE FUNCTION sibling_number (IN numer INTEGER, IN denom INTEGER) 
RETURNS INTEGER 
LANGUAGE SQL
DETERMINISTIC
BEGIN 
DECLARE ret_num INTEGER; 
DECLARE ret_den INTEGER; 
DECLARE ret INTEGER; 
   IF numer = 3 
   THEN RETURN CAST(NULL AS INTEGER);
   END IF;
   SET ret_num = (numer - 1)/2;
   SET ret_den = denom/2; 
   SET ret = 1; 
   WHILE FLOOR((ret_num-1)/4) = (ret_num-1)/4 
      DO IF ret_num = 1 
            AND ret_den = 1 
         THEN RETURN ret;
         END IF;
   SET ret_num = (ret_num + 1)/2;
   SET ret_den = ret_den/2; 
   SET ret = ret + 1; 
   END WHILE; 
   RETURN ret; 
END;

-- 05.04.04. Calculating the Enumerated Path and Distance between Nodes
CREATE FUNCTION Path (IN numer INTEGER, IN denom INTEGER) 
RETURNS VARCHAR (30)
LANGUAGE SQL
DETERMINISTIC
   IF numer IS NULL 
   THEN RETURN ('?');
   ELSE
   RETURN Path(parent_numer(numer, denom), 
               parent_denom(numer, denom)) 
     || '.' || sibling_number(numer, denom); 
   END IF;

CREATE FUNCTION Distance (IN num1 INTEGER, IN den1 INTEGER,
                          IN num2 INTEGER, IN den2 INTEGER) 
RETURNS INTEGER 
LANGUAGE SQL
DETERMINISTIC
RETURN CASE
       WHEN num1 = num2 AND den1 = den2 -- same node
       THEN 0
       WHEN num1 IS NULL -- missing data
       THEN CAST (NULL AS INTEGER)
       ELSE (1 + Distance(parent_numer(num1, den1), 
                          parent_denom(num1, den1), num2, den2))
       END;

CREATE FUNCTION Child_Numerator
(IN num INTEGER, IN den INTEGER, IN child INTEGER) 
RETURNS INTEGER 
LANGUAGE SQL
DETERMINISTIC 
RETURN (num * (child * child) + 3 - (child * child)); 

CREATE FUNCTION Child_Denominator
(IN num INTEGER, IN den INTEGER, IN child INTEGER) 
RETURNS INTEGER 
LANGUAGE SQL
DETERMINISTIC
RETURN den * (child * child); 

CREATE FUNCTION Path_Numer(path VARCHAR) 
RETURNS INTEGER 
LANGUAGE SQL
DETERMINISTIC
BEGIN 
DECLARE num INTEGER;
DECLARE den INTEGER; 
DECLARE postfix VARCHAR(1000);
DECLARE sibling VARCHAR(100);    SET num = 1;
   SET den = 1;
   SET postfix = '.' || path || '.';
   WHILE CHAR_LENGTH(postfix) > 1 
      DO SET sibling = SUBSTRING(postfix FROM 2 FOR INSTR(postfix, '.', 2)-2);
         SET postfix = SUBSTRING(postfix FROM INSTR(postfix, '.', 2) FOR CHAR_LENGTH(postfix) - INSTR(postfix, '.', 2) + 1);
         SET num = Child_Numer(num, den, CAST(sibling AS INTEGER)); 
         SET den = Child_Denom(num, den, CAST(sibling AS INTEGER)); 
END WHILE;
RETURN num; 
END;

CREATE FUNCTION Path_Denom(path VARCHAR) 
LANGUAGE SQL
DETERMINISTIC
BEGIN 
DECLARE num INTEGER;
DECLARE den INTEGER; 
DECLARE postfix VARCHAR(1000);
DECLARE sibling VARCHAR(100); 
   SET num = 1;
   SET den = 1;
   SET postfix = '.' || path || '.';
   WHILE CHAR_LENGTH(postfix) > 1 
      DO SET sibling = SUBSTRING(postfix FROM 2 FOR INSTR(postfix, '.', 2)-2);
         SET postfix = SUBSTRING(postfix FROM INSTR(postfix, '.', 2) FOR CHAR_LENGTH(postfix) - INSTR(postfix, '.', 2) + 1);
         SET num = Child_Numer(num, den, CAST(sibling AS INTEGER)); 
         SET den = Child_Denom(num, den, CAST(sibling AS INTEGER)); 
END WHILE; 
RETURN den; 
END;


-- 05.04.05. Building a Hierarchy 
CREATE TABLE OrgChart
(name VARCHAR(30) NOT NULL UNIQUE, 
 numer INTEGER NOT NULL, 
 denom INTEGER NOT NULL,
 UNIQUE (numer, denom));

INSERT INTO OrgChart 
VALUES ('King', Path_Numer('1'), Path_Denom('1')), 
      ('Jones', Path_Numer('1.1'), Path_Denom('1.1')), 
      ('Scott', Path_Numer('1.1.1'), Path_Denom('1.1.1')), 
      ('Adams', Path_Numer('1.1.1.1'), Path_Denom('1.1.1.1')), 
      ('Ford', Path_Numer('1.1.2'), Path_Denom('1.1.2')), 
      ('Smith', Path_Numer('1.1.2.1'), Path_Denom('1.1.2.1')), 
      ('Blake', Path_Numer('1.2'), Path_Denom('1.2')), 
      ('Allen', Path_Numer('1.2.1'), Path_Denom('1.2.1')), 
      ('Ward', Path_Numer('1.2.2'), Path_Denom('1.2.2')), 
      ('Martin', Path_Numer('1.2.3'), Path_Denom('1.2.3')), 
      ('Turner', Path_Numer('1.2.4'), Path_Denom('1.2.4')), 
      ('Clark', Path_Numer('1.3'), Path_Denom('1.3')), 
      ('Miller', Path_Numer('1.3.1'), Path_Denom('1.3.1'));

CREATE VIEW Hierarchy (name, numer, denom,
                       numer_lft, denom_lft,
                       numer_rgt, denom_rgt,
                        path, depth)
AS SELECT name, numer, denom, 
          y_numer(numer, denom), 
          y_denom(numer, denom), 
          x_numer(numer, denom), 
          x_denom(numer, denom), 
          path (numer, denom), 
          Distance(numer, denom, 3, 2)
    FROM OrgChart;

05.04.06. Depth-first Enumeration by Left Interval Boundary

SELECT depth, name, (numer_lft/denom_lft) AS indentation 
  FROM Hierarchy 
 ORDER BY indentation;

-- 05.04.07. Depth-first enumeration by Right Interval boundary
SELECT depth, name,
       (numer_rgt/denom_rgt) AS indentation 
  FROM Hierarchy 
 ORDER BY indentation DESC;

SELECT depth, name, path 
  FROM Hierarchy 
 ORDER BY path;

-- 05.04.08. All Descendants of a Node
SELECT H2.name 
  FROM Hierarchy AS H1, Hierarchy AS H2 
 WHERE H1.name = 'Ford' 
   AND Distance (H1.numer, H1.denom, H2.numer, H2.denom) > 0;

06.00. The Linear Version of the Nested Sets model

CREATE TABLE OrgChart
(emp CHAR(10) NOT NULL,
 seq INTEGER NOT NULL UNIQUE,
 CONSTRAINT natural_numbers
      CHECK(seq > 0),
 CONSTRAINT got_all_numbers
 CHECK ((SELECT COUNT(*) FROM OrgChart)
         = (SELECT MAX(seq) FROM OrgChart)),
 CONSTRAINT exactly_twice
 CHECK (NOT EXISTS
        (SELECT *
           FROM OrgChart
          GROUP BY emp
         HAVING COUNT(*) <> 2)),
 PRIMARY KEY (emp, seq));

INSERT INTO OrgChart(emp, seq)
VALUES( 'Albert', 1),
 ('Bert', 2),
 ('Bert', 3),
 ('Chuck', 4),
 ('Donna', 5),
 ('Donna', 6),
 ('Eddie', 7),
 ('Eddie', 8),
 ('Fred', 9),
 ('Fred', 10),
 ('Chuck', 11),
  ('Albert', 12);

CREATE VIEW OrgChart_NS (emp, lft, rgt)
AS SELECT emp, MIN(seq), MAX(seq)
     FROM OrgChart
    GROUP BY emp;	

-- 06.01. Insertion and Deletion
CREATE PROCEDURE RemoveSubtree (IN my_employee CHAR(10))
LANGUAGE SQL
DETERMINISTIC
BEGIN ATOMIC
 DECLARE leftmost INTEGER;
 DECLARE rightmost INTEGER;
 -- remember where the subtree root was
 SET leftmost = (SELECT MIN(seq)
                   FROM OrgChart
                  WHERE emp = my_employee);
 SET rightmost = (SELECT MAX(seq)
                    FROM OrgChart
                   WHERE emp = my_employee);
 -- remove the subtree
 DELETE FROM OrgChart
  WHERE seq BETWEEN leftmost AND rightmost;
 -- compute the size of the subtree & close the gap
 UPDATE OrgChart
    SET seq = seq - (rightmost - leftmost + 1) / 2
  WHERE seq > leftmost;
END;

CREATE PROCEDURE InsertSubtree (IN my_boss CHAR(10))
LANGUAGE SQL
DETERMINISTIC
BEGIN ATOMIC
-- assume that the new subtree is held in NewTree
-- and is in linear nested set format
 DECLARE tree_size INTEGER;
 DECLARE boss_right INTEGER;
 -- get size of the subtree
 SET tree_size = (SELECT COUNT(*) FROM NewTree);
 -- place new tree to right of siblings
 SET boss_right = (SELECT MAX(seq)
                     FROM OrgChart
                    WHERE emp = my_boss);
 -- move everyone over to the right
 UPDATE OrgChart
    SET seq = seq + tree_size
  WHERE seq >= boss_right;
 -- re-number the subtree and insert it
 INSERT INTO OrgChart
 SELECT emp, (seq + boss_right) FROM NewTree;
 -- clear out subtree table
 DELETE FROM Subtrees;
END;

-- 06.02. Finding Paths
SELECT P1.emp
   FROM OrgChart AS P1
  WHERE P1.seq <= (SELECT MIN(P2.seq)  -- left parentheses
                     FROM OrgChart AS P2
                    WHERE P2.emp = :my_guy)
 GROUP BY emp
HAVING COUNT(*) = 1;

-- 06.03. Finding Levels
SELECT :my_guy,
       2 * COUNT(DISTINCT P2.emp)
        - COUNT(DISTINCT P2.seq) AS lvl
  FROM OrgChart AS P1, OrgChart AS P2
 WHERE P1.emp = :my_guy
   AND P2.seq <= (SELECT MIN(seq)
                    FROM OrgChart
                   WHERE emp = :my_guy);

-- 07.00. Binary Trees
CREATE TABLE BinTree
(node CHAR(10) NOT NULL, 
 location INTEGER NOT NULL PRIMARY KEY);

INSERT INTO BinTree(node, location)
VALUES ('a', 1), ('B', 2), ('c', 3), ('d', 5), 
     ('e', 6), ('f', 7), ('g', 14), ('h', 15);

CREATE TABLE PowersOfTwo
(exponent INTEGER NOT NULL PRIMARY KEY
          CHECK(exponent >= 0), 
 pwr_two INTEGER NOT NULL UNIQUE
         CHECK(pwr_two >= 1)
 --, CHECK(2^exponent = pwr_two), but this is not standard SQL
);  

INSERT INTO PowersOfTwo 
VALUES (0, 1), (1, 2), (2, 4), (3, 8), (4, 16), 
       (5, 32), (6, 64), (7, 128), (8, 256); 

--07.02.01. Find Parent of a Node
SELECT BinTree.*, :my_child
 FROM BinTree
 WHERE location
 =(SELECT FLOOR(location/2) AS parent
        FROM BinTree T1
       WHERE T1.node = :my_child)

-- 07.02.02. Find Subtree at a Node
SELECT :my_root, T1.*
  FROM BinTree AS T1, BinTree AS T2
 WHERE T2.node = :my_root
   AND T1.location
        < (FLOOR(LOG2(T1.location/T2.location))^2)) * (n + 1);

-- 07.03. Deletion from a Binary Tree 
DELETE FROM BinTree 
 WHERE node = :my_root
   AND location
       IN (SELECT T1.location
             FROM BinTree AS T1 
            WHERE T1.location
                  < (FLOOR (LOG2(T1.location/BinTree.location))^2) *(n+1));

-- 07.04. Insertion into a Binary Tree 
CREATE TABLE Heap
(node CHAR(10) NOT NULL, 
 location INTEGER NOT NULL PRIMARY KEY);

INSERT INTO Heap 
VALUES ('A', 1), ('B', 2), ('C', 3), ('D', 4), 
('E', 5), ('F', 6), ('G', 7), ('H', 8);

CREATE TABLE PowersOfTwo
(exponent INTEGER NOT NULL PRIMARY KEY
          CHECK(exponent >= 0), 
 pwr_two INTEGER NOT NULL UNIQUE
         CHECK (pwr_two >= 1)
 --, CHECK (2^exponent = pwr_two), but this is not standard SQL
);  

--find all the ancestors of a node 
SELECT H1.node, H1.location
  FROM Heap AS H1
 WHERE H1.location 
   IN(SELECT @my_node/pwr_two 
     FROM PowersOfTwo
    WHERE pwr_two <= :my_location);

-- level of a node is easy
SELECT location, 
   CAST (FLOOR(LOG(location)/LOG(2.0)) AS INTEGER) AS lvl
  FROM Heap;

CREATE VIEW HeapDescendants
(node, location, descendant, dscnt_loc)
AS
SELECT H1.node, H1.location, 
       H2.node AS dscnt, 
       H2.location AS dscnt_loc
  FROM (SELECT FLOOR(LOG(MAX(location))/LOG(2.0)) + 1.0 
          FROM Heap) AS D(depth)
        CROSS JOIN
       (SELECT location, FLOOR(LOG(location)/LOG(2.0)) 
         FROM Heap) AS L(location, lvl)
       INNER JOIN
       Heap AS H1
       ON H1.location = L.location
       INNER JOIN
       PowersOfTwo AS T
       ON T.exponent >= 0 
          AND T.exponent < D.depth - L.lvl
      INNER JOIN
      Heap AS H2
      ON H2.location >= H1.location * pwr_two 
         AND H2.location < H1.location * pwr_two + pwr_two;

10.02.02. Disjoint Hierarchies

CREATE TABLE StudentTypes
(student_id INTEGER NOT NULL PRIMARY KEY
            REFERENCES Students (student_id)
            ON UPDATE CASCADE
            ON DELETE CASCADE,
 in_state INTEGER DEFAULT 0 NOT NULL
          CHECK (in_state IN (0, 1)),
 out_of_state INTEGER DEFAULT 0 NOT NULL
              CHECK (out_of_state IN (0, 1)),
 "foreign" INTEGER DEFAULT 0 NOT NULL
         CHECK ("foreign" IN (0,1)),
 CHECK ((in_state + out_of_state + "foreign") = 1));

-- attributes that belong to each subclass
CREATE TABLE OutOfStateStudents
(student_id INTEGER NOT NULL PRIMARY KEY
            REFERENCES StudentTypes (student_id)
            ON UPDATE CASCADE
            ON DELETE CASCADE,
 state CHAR(2) NOT NULL -- USPS standard codes
  );

CREATE TABLE ForeignStudents
(student_id INTEGER NOT NULL PRIMARY KEY
            REFERENCES StudentTypes (student_id)
            ON UPDATE CASCADE
            ON DELETE CASCADE,
 country_code CHAR(3) NOT NULL -- ISO standard codes
  );

CREATE TABLE InStateStudents
(student_id INTEGER NOT NULL PRIMARY KEY
            REFERENCES StudentTypes (student_id)
            ON UPDATE CASCADE
            ON DELETE CASCADE,
 county_code INTEGER NOT NULL, -- ANSI standard codes
 high_school_district INTEGER NOT NULL);

CREATE TABLE StudentTypes
(student_id INTEGER NOT NULL PRIMARY KEY
            REFERENCES Students (student_id)
            ON UPDATE CASCADE
            ON DELETE CASCADE,
 residence_type CHAR(3) DEFAULT 'ins' NOT NULL
          CHECK (residence_type IN ('ins', 'out', 'for'));

-- a table for each subclass 
CREATE TABLE OutOfStateStudents
(student_id INTEGER NOT NULL PRIMARY KEY
 residence_type CHAR(3) DEFAULT 'out' NOT NULL 
          CHECK (residence_type = 'out'),
 FOREIGN KEY (student_id, residence_type)
 REFERENCES StudentTypes (student_id, residence_type)
  ON UPDATE CASCADE
  ON DELETE CASCADE,
 state CHAR(2) NOT NULL, -- USPS standard codes
PRIMARY KEY (student_id, residence_type));

CREATE TABLE ForeignStudents
(student_id INTEGER NOT NULL
 residence_type CHAR(3) NOT NULL 
          CHECK (residence_type 'for'),
 FOREIGN KEY (student_id, residence_type)
 REFERENCES StudentTypes (student_id, residence_type)
  ON UPDATE CASCADE
  ON DELETE CASCADE,
country_code CHAR(3) NOT NULL, -- ISO standard codes
PRIMARY KEY (student_id, residence_type));

CREATE TABLE InStateStudents
(student_id INTEGER NOT NULL 
 residence_type CHAR(3) NOT NULL 
          CHECK (residence_type 'ins'),
 FOREIGN KEY (student_id, residence_type)
 REFERENCES StudentTypes (student_id, residence_type)
  ON UPDATE CASCADE
  ON DELETE CASCADE,
 county_code INTEGER NOT NULL, -- ANSI standard codes
 high_school_district INTEGER NOT NULL,
  PRIMARY KEY (student_id, residence_type));