Lorenzo Alberton, profile picture
Uploaded byLorenzo Alberton
146,058 views

Trees In The Database - Advanced data structures

The document discusses advanced data structures, particularly focusing on tree representations in databases using models like adjacency lists, path enumeration, and nested sets. It covers how to create these models, manage anomalies, and perform common operations such as finding root nodes, leaf nodes, and subtrees. The information highlights SQL queries and procedural code necessary for navigating and manipulating these tree structures effectively.

Technology◦Business◦
In this document
Powered by AI

Introduction to the topic by Lorenzo Alberton, focusing on trees in databases as an advanced data structure.

Definition of trees as connected, undirected, acyclic graphs with corresponding representation.

Introduction to the Adjacency List model, detailing its structure and how to find root and leaf nodes.

Discussion on update and delete anomalies within the Adjacency List model and their implications.

Improvements to the Adjacency List model, establishing constraints like root node checks and preventing cycles.

Techniques for navigating the Adjacency List model through loops and self-joins, demonstrating deletion operations.

Introduction of Path Enumeration Model (Materialized Path), defining structures and depth calculations for nodes.

Operations for searching subordinates/superiors, deleting and inserting nodes in the Path Enumeration model.

Details on the Nested Set model, its definition, structure, and how to find nodes, levels, and relations.

Operations in the Nested Set model, including deleting subtrees and single nodes.

Discussion on managing frequent insertions and datatype considerations relevant to Nested Set structures.

Hybrid models combining Adjacency List and Nested Sets, as well as introducing Nested Intervals for data management.

Detailed description of logical operations and functions used with the Nested Intervals model.

Techniques for encoding using Nested Intervals along with methods to manage operations and fractions.

Oracle-specific tree traversing techniques using CONNECT BY PRIOR for managing hierarchical data.Explanation of Common Table Expressions in SQL to manage hierarchical queries recursively.

Wrap-up, resources for further reading, contact information for the presenter, and open floor for questions.

1 / 128
2 / 128
3 / 128
4 / 128
5 / 128
6 / 128
7 / 128
8 / 128
9 / 128
10 / 128
11 / 128
12 / 128
13 / 128
14 / 128
15 / 128
16 / 128
17 / 128
18 / 128
19 / 128
20 / 128
21 / 128
22 / 128
23 / 128
24 / 128
25 / 128
26 / 128
27 / 128
28 / 128
29 / 128
30 / 128
31 / 128
32 / 128
33 / 128
34 / 128
35 / 128
36 / 128
37 / 128
38 / 128
39 / 128
40 / 128
41 / 128
42 / 128
43 / 128
44 / 128
45 / 128
46 / 128
47 / 128
48 / 128
49 / 128
50 / 128
51 / 128
52 / 128
53 / 128
54 / 128
55 / 128
56 / 128
57 / 128
Most read
58 / 128
59 / 128
60 / 128
61 / 128
62 / 128
63 / 128
64 / 128
65 / 128
66 / 128
67 / 128
68 / 128
69 / 128
70 / 128
71 / 128
72 / 128
73 / 128
74 / 128
75 / 128
76 / 128
77 / 128
78 / 128
79 / 128
80 / 128
81 / 128
82 / 128
83 / 128
84 / 128
85 / 128
86 / 128
87 / 128
88 / 128
89 / 128
90 / 128
91 / 128
92 / 128
93 / 128
94 / 128
95 / 128
96 / 128
97 / 128
98 / 128
99 / 128
100 / 128
101 / 128
102 / 128
103 / 128
104 / 128
105 / 128
106 / 128
107 / 128
108 / 128
109 / 128
110 / 128
111 / 128
112 / 128
113 / 128
Most read
114 / 128
115 / 128
116 / 128
117 / 128
118 / 128
119 / 128
120 / 128
121 / 128
122 / 128
123 / 128
124 / 128
125 / 128
Most read
126 / 128
127 / 128
128 / 128
Trees in the Database Advanced Data Structures Lorenzo Alberton lorenzo@ibuildings.com DPC09, Amsterdam, 13 June 2009
Lorenzo Alberton 2
Lorenzo Alberton MDB2 Calendar Pager Translation2 Mail_Queue DB_QueryTool 2
Lorenzo Alberton MDB2 Calendar Pager Translation2 Mail_Queue DB_QueryTool 2
Tree Connected, undirected, acyclic graph A B C G D E F 3
Tree Connected, undirected, acyclic graph A B C D E F 3
Tree Connected, undirected, acyclic graph A B C D E F 3
Tree Connected, undirected, acyclic graph A B C D E F 3
Tree Connected, undirected, acyclic graph A B C D E F 3
Adjacency List Model AKA “parent-child” model 4
Adjacency List Model CREATE TABLE emp_orgchart ( emp VARCHAR(10) NOT NULL PRIMARY KEY, boss VARCHAR(10), salary DECIMAL(6,2) NOT NULL ); A emp boss salary A NULL 1000.00 B C B A 900.00 C A 900.00 D C 800.00 D E F E C 700.00 F C 600.00 5
Adjacency List Model Finding the root node SELECT * FROM emp_orgchart WHERE boss IS NULL; Finding the leaf nodes SELECT e1.* FROM emp_orgchart AS e1 LEFT JOIN emp_orgchart AS e2 ON e1.emp = e2.boss WHERE e2.emp IS NULL; 6
Adjacency List Model Anomalies UPDATE anomalies START TRANSACTION; emp boss salary UPDATE emp_orgchart A NULL 1000.00 SET emp = ‘C1’ B A 900.00 WHERE emp = ‘C’; C1 A 900.00 D C 800.00 UPDATE emp_orgchart E C 700.00 SET boss = ‘C1’ F C 600.00 WHERE boss = ‘C’; COMMIT; 7
Adjacency List Model Anomalies UPDATE anomalies START TRANSACTION; emp boss salary UPDATE emp_orgchart A NULL 1000.00 SET emp = ‘C1’ B A 900.00 WHERE emp = ‘C’; C1 A 900.00 D C 800.00 UPDATE emp_orgchart E C 700.00 SET boss = ‘C1’ F C 600.00 WHERE boss = ‘C’; COMMIT; 7
Adjacency List Model Anomalies UPDATE anomalies START TRANSACTION; UPDATE emp_orgchart SET emp = CASE emp UPDATE emp_orgchart WHEN ‘C’ THEN ‘C1’ SET emp = ‘C1’ ELSE emp END, WHERE emp = ‘C’; boss = CASE boss WHEN ‘C’ THEN ‘C1’ UPDATE emp_orgchart ELSE boss END SET boss = ‘C1’ WHERE ‘C’ IN (emp, boss); WHERE boss = ‘C’; COMMIT; 7
Adjacency List Model Anomalies INSERT anomalies 8
Adjacency List Model Anomalies INSERT anomalies INSERT INTO emp_orgchart (emp, boss) VALUES (‘G’, ‘H’), (‘H’, ‘G’); G H 8
Adjacency List Model Anomalies INSERT anomalies INSERT INTO emp_orgchart (emp, boss) VALUES (‘G’, ‘H’), (‘H’, ‘G’); G H INSERT INTO emp_orgchart VALUES (‘M’, ‘M’); M 8
Adjacency List Model Anomalies DELETE anomalies DELETE FROM emp_orgchart WHERE emp = ‘C’; A B C D E F 9
Adjacency List Model Anomalies DELETE anomalies DELETE FROM emp_orgchart WHERE emp = ‘C’; A B C D E F 9
Fixing the Adjacency List Model CREATE TABLE emp ( id INTEGER DEFAULT 0 PRIMARY KEY, name VARCHAR(10) NOT NULL, salary DECIMAL (6,2) NOT NULL CHECK (salary >= 0.00), ... ); CREATE TABLE orgchart ( emp_id INTEGER NOT NULL DEFAULT 0 -- vacant REFERENCES emp(id) ON DELETE SET DEFAULT ON UPDATE CASCADE, boss_id INTEGER -- NULL means root node REFERENCES emp(id), ... ); 10
Fixing the Adjacency List Model -- cannot be your own boss CHECK ((boss_id <> emp_id) OR (boss_id = 0 AND emp_id = 0)), 11
Fixing the Adjacency List Model -- cannot be your own boss CHECK ((boss_id <> emp_id) OR (boss_id = 0 AND emp_id = 0)), -- prevent longer cycles UNIQUE (emp_id, boss_id), 11
Fixing the Adjacency List Model -- cannot be your own boss CHECK ((boss_id <> emp_id) OR (boss_id = 0 AND emp_id = 0)), -- prevent longer cycles UNIQUE (emp_id, boss_id), -- connected graph (edges = nodes - 1) CHECK ((SELECT COUNT(*) FROM orgchart) - 1 = (SELECT COUNT(boss_id) FROM orgchart)), 11
Fixing the Adjacency List Model -- cannot be your own boss CHECK ((boss_id <> emp_id) OR (boss_id = 0 AND emp_id = 0)), -- prevent longer cycles UNIQUE (emp_id, boss_id), -- connected graph (edges = nodes - 1) CHECK ((SELECT COUNT(*) FROM orgchart) - 1 = (SELECT COUNT(boss_id) FROM orgchart)), -- one root only CHECK ((SELECT COUNT(*) FROM orgchart WHERE boss_id IS NULL) = 1), 11
Adjacency List Model - Navigation Loops / Self-Joins procedural code SELECT o1.emp AS e1, o2.emp AS e2, CREATE PROCEDURE o3.emp AS e3 TreeTraversal (IN FROM emp_orgchart AS o1 current_emp_id INT) LEFT OUTER JOIN BEGIN emp_orgchart AS o2 ... ON o1.emp = o2.boss LEFT OUTER JOIN emp_orgchart AS o3 ON o2.emp = o3.boss WHERE o1.emp = ‘A’; 12
Adjacency List Model - Deletion 13
Adjacency List Model - Deletion A B C D E F 13
Adjacency List Model - Deletion A B C D x E F 13
Adjacency List Model - Deletion A A B C B C D x E F D E F 13
Adjacency List Model - Deletion A A A B C B C D x E F B D D E E F F 13
Adjacency List Model - Deletion A A A A B C B C B C D x E F B D D E E F F D E F 13
Adjacency List Model - Deletion A A A A B C B C B D C D x E F B D D E E F F D E F 13
Adjacency List Model - Deletion A A A A B C B C B D C D x E F B D D E E F F D E F Requires traversal (deferred constraints) 13
Path Enumeration Model aka Materialized Path 14
Path Enumeration Model CREATE TABLE emp_orgchart ( emp_id CHAR(1) NOT NULL PRIMARY KEY -- if using a separator, don’t use it in the ID CHECK (REPLACE(emp_id, ‘/’, ‘’) = emp_id), emp_name VARCHAR(10) NOT NULL, path_string VARCHAR(512) NOT NULL ); emp_id emp_name path_string A A Anthony A B Beryl AB B C C Charles AC D Denise ACD E Ellen ACE D E F F Frank ACF 15
Path Enumeration Model -- prevent cycles (nodes appearing twice: ‘ABCA’) CHECK (NOT EXISTS( SELECT * FROM emp_orgchart AS D1, emp_orgchart AS P1 WHERE LENGTH(REPLACE(P1.path_string, D1.emp_id, ‘’)) < LENGTH(P1.path_string) - LENGTH(D1.emp_id)) )) -- No path can be longer than the number of nodes CHECK((SELECT MAX(LENGTH(path_string)) FROM emp_orgchart AS E1) <= (SELECT COUNT(emp_id) * LENGTH(emp_id) FROM emp_orgchart AS E2)) 16
Path Enumeration Model 17
Path Enumeration Model Depth of the node 17
Path Enumeration Model Depth of the node • LENGTH(path_string) / LENGTH(emp_id) 17
Path Enumeration Model Depth of the node • LENGTH(path_string) / LENGTH(emp_id) • LENGTH(path_string) - LENGTH(REPLACE(path_string, ‘/’, ‘’)) + 1 17
Path Enumeration Model Depth of the node • LENGTH(path_string) / LENGTH(emp_id) • LENGTH(path_string) - LENGTH(REPLACE(path_string, ‘/’, ‘’)) + 1 17
Path Enumeration Model Depth of the node • LENGTH(path_string) / LENGTH(emp_id) • LENGTH(path_string) - LENGTH(REPLACE(path_string, ‘/’, ‘’)) + 1 Searching for subordinates 17
Path Enumeration Model Depth of the node • LENGTH(path_string) / LENGTH(emp_id) • LENGTH(path_string) - LENGTH(REPLACE(path_string, ‘/’, ‘’)) + 1 Searching for subordinates • SELECT * FROM emp_orgchart WHERE path_string LIKE ‘%’ || :parent_emp_id || ‘%’; 17
Path Enumeration Model Depth of the node • LENGTH(path_string) / LENGTH(emp_id) • LENGTH(path_string) - LENGTH(REPLACE(path_string, ‘/’, ‘’)) + 1 Searching for subordinates • SELECT * FROM emp_orgchart WHERE path_string LIKE ‘%’ || :parent_emp_id || ‘%’; • SELECT * FROM emp_orgchart WHERE path_string LIKE (SELECT path_string FROM emp_orgchart WHERE emp_id = :parent_emp_id) || ‘%’; 17
Path Enumeration Model Searching for superiors SELECT SUBSTRING(P1.path_string FROM seq * LENGTH(P1.emp_id) FOR LENGTH(P1.emp_id)) AS emp_id FROM emp_orgchart AS P1, sequence AS S1 WHERE P1.emp_id = :search_emp_id AND S1.seq <= LENGTH(path_string)/ LENGTH(emp_id); 18
Path Enumeration Model Deleting a subtree: DELETE FROM emp_orgchart WHERE path_string LIKE ( SELECT path_string FROM emp_orgchart WHERE emp_id = :deleted_node) || ‘%’; Deleting a single node: START TRANSACTION; DELETE FROM emp_orgchart WHERE emp_id = :deleted_node; UPDATE emp_orgchart SET path_string = REPLACE(path_string, :deleted_node, ‘’); COMMIT; 19
Path Enumeration Model Insertion of a new node INSERT INTO emp_orgchart VALUES ( :new_emp_id, -- ‘M’ :new_name, -- ‘Maggie’ (SELECT path_string FROM emp_orgchart WHERE emp_id = :boss_of_new_emp) -- ‘D’ || :new_emp_id -- ‘M’ ); emp_id emp_name path_string D Denise ACD M Maggie ACDM 20
Path Enumeration Model Insertion of a new node INSERT INTO emp_orgchart VALUES ( :new_emp_id, -- ‘M’ :new_name, -- ‘Maggie’ (SELECT path_string FROM emp_orgchart WHERE emp_id = :boss_of_new_emp) -- ‘D’ || :new_emp_id -- ‘M’ ); emp_id emp_name path_string D Denise ACD M Maggie ACDM 20
Path Enumeration Model Insertion of a new node INSERT INTO emp_orgchart VALUES ( :new_emp_id, -- ‘M’ :new_name, -- ‘Maggie’ (SELECT path_string FROM emp_orgchart WHERE emp_id = :boss_of_new_emp) -- ‘D’ || :new_emp_id -- ‘M’ ); emp_id emp_name path_string D Denise ACD M Maggie ACDM 20
Path Enumeration Model Splitting the path string into nodes 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, emp_orgchart AS P1 WHERE S1.seq BETWEEN 1 AND LENGTH(P1.path_string) + 1 AND SUBSTRING(‘/’ || P1.path_string || ‘/’ FROM S1.seq FOR 1) = ‘/’ 21
Path Enumeration Model emp_name edge_path Edge Anthony 1. Beryl 1.1. Enumeration Charles 1.2. Model Denise 1.2.1. Ellen 1.2.2. Frank 1.2.3. Anthony Beryl Charles Denise Ellen Frank 22
Nested Set Model aka Modified Preorder Tree Traversal (MPTT) 23
Nested Set Model A C B D E F 24
Nested Set Model A C B D E F A 1 12 B C 2 3 4 11 D E F 5 6 7 8 9 10 24
Nested Set Model CREATE TABLE orgchart ( emp VARCHAR(10) NOT NULL PRIMARY KEY, lft INTEGER NOT NULL, rgt INTEGER NOT NULL ); A 1 12 B C 2 3 4 11 D E F 5 6 7 8 9 10 25
Nested Set Model CREATE TABLE orgchart ( emp VARCHAR(10) NOT NULL PRIMARY KEY, lft INTEGER NOT NULL, rgt INTEGER NOT NULL ); A 1 12 B C 1 A 12 2 3 4 11 D E F 5 6 7 8 9 10 2 B 3 4 C 11 D E F 5 6 7 8 9 10 25
Nested Set Model Finding root node 1 A 12 2 B 3 4 C 11 D E F 5 6 7 8 9 10 26
Nested Set Model Finding root node SELECT * FROM orgchart WHERE lft = 1; 1 A 12 2 B 3 4 C 11 D E F 5 6 7 8 9 10 26
Nested Set Model Finding root node SELECT * FROM orgchart WHERE lft = 1; 1 A 12 Finding leaf nodes 2 B 3 4 C 11 D E F 5 6 7 8 9 10 26
Nested Set Model Finding root node SELECT * FROM orgchart WHERE lft = 1; 1 A 12 Finding leaf nodes SELECT * 2 B 3 4 C 11 FROM orgchart WHERE lft = (rgt - 1); D E F 5 6 7 8 9 10 26
Nested Set Model Finding root node SELECT * FROM orgchart WHERE lft = 1; 1 A 12 Finding leaf nodes SELECT * 2 B 3 4 C 11 FROM orgchart WHERE lft = (rgt - 1); D E F Finding subtrees 5 6 7 8 9 10 26
Nested Set Model Finding root node SELECT * FROM orgchart WHERE lft = 1; 1 A 12 Finding leaf nodes SELECT * 2 B 3 4 C 11 FROM orgchart WHERE lft = (rgt - 1); D E F Finding subtrees 5 6 7 8 9 10 SELECT Mgrs.emp AS boss Workers.emp AS worker FROM orgchart AS Mgrs, orgchart AS Workers WHERE Workers.lft > Mgrs.lft AND Workers.lft < Mgrs.rgt 26
Nested Set Model Finding root node SELECT * FROM orgchart WHERE lft = 1; 1 A 12 Finding leaf nodes SELECT * 2 B 3 4 C 11 FROM orgchart WHERE lft = (rgt - 1); D E F Finding subtrees 5 6 7 8 9 10 SELECT Mgrs.emp AS boss Workers.emp AS worker FROM orgchart AS Mgrs, orgchart AS Workers WHERE Workers.lft > Mgrs.lft BETWEEN Mgrs.lft AND Mgrs.rgt AND Workers.lft < Mgrs.rgt 26
Nested Set Model Finding the level of a node 27
Nested Set Model Finding the level of a node SELECT o2.emp, COUNT(o1.emp) AS lvl FROM orgchart AS o1, orgchart AS o2 WHERE o2.lft BETWEEN o1.lft AND o1.rgt GROUP BY o2.emp; 27
Nested Set Model Finding the level of a node SELECT o2.emp, COUNT(o1.emp) AS lvl FROM orgchart AS o1, orgchart AS o2 WHERE o2.lft BETWEEN o1.lft AND o1.rgt GROUP BY o2.emp; Finding the height of the tree 27
Nested Set Model Finding the level of a node SELECT o2.emp, COUNT(o1.emp) AS lvl FROM orgchart AS o1, orgchart AS o2 WHERE o2.lft BETWEEN o1.lft AND o1.rgt GROUP BY o2.emp; Finding the height of the tree SELECT MAX(lvl) AS height FROM ( SELECT o2.emp, COUNT(o1.emp) - 1 FROM orgchart AS o1, orgchart AS o2 WHERE o2.lft BETWEEN o1.lft AND o1.rgt GROUP BY o2.emp) AS L1(emp, lvl); 27
Nested Set Model Finding relative position SELECT CASE WHEN :emp1 = :emp2 THEN :emp1 || ‘ is ’ || :emp2 WHEN o1.lft BETWEEN o2.lft AND o2.rgt THEN :emp1 || ‘ subordinate to ’ || :emp2 WHEN o2.lft BETWEEN o1.lft AND o1.rgt THEN :emp2 || ‘ subordinate to ’ || :emp1 ELSE :emp1 || ‘ no relation to ’ || :emp2 END FROM orgchart AS o1, orgchart AS o2 WHERE o1.emp = :emp1 AND o2.emp = :emp2; 28
Nested Set Model Deleting subtrees DELETE FROM orgchart WHERE lft BETWEEN (SELECT lft FROM orgchart WHERE emp = :start_node) AND (SELECT rgt FROM orgchart Filling gaps WHERE emp = :start_node); CREATE VIEW LftRgt (seq) AS SELECT lft FROM orgchart UNION ALL SELECT rgt FROM orgchart; UPDATE orgchart SET lft = (SELECT COUNT(*) FROM LftRgt WHERE seq <= lft), rgt = (SELECT COUNT(*) FROM LftRgt WHERE seq <= rgt) 29
Nested Set Model Deleting a single node DELETE FROM orgchart WHERE emp = ‘C’; A C B D E F 30
Nested Set Model Deleting a single node DELETE FROM orgchart WHERE emp = ‘C’; A B D E F 30
Nested Set Model Deleting a single node CREATE PROCEDURE downsize(IN removed VARCHAR(10)) LANGUAGE SQL DETERMINISTIC UPDATE orgchart SET emp = CASE WHEN orgchart.emp = removed AND orgchart.lft + 1 = orgchart.rgt --leaf THEN ‘{vacant}’ WHEN orgchart.emp = removed AND orgchart.lft + 1 <> orgchart.rgt -- promote subordinate and vacate THEN (SELECT o1.emp FROM orgchart AS o1 WHERE orgchart.lft + 1 = o1.lft) WHEN orgchart.emp = (SELECT o1.emp FROM orgchart AS o1 WHERE orgchart.lft + 1 = o1.lft) THEN ‘{vacant}’ ELSE emp END; 31
Nested Set Model Deleting a single node CREATE PROCEDURE downsize(IN removed VARCHAR(10)) LANGUAGE SQL DETERMINISTIC UPDATE orgchart SET emp = CASE WHEN orgchart.emp = removed AND orgchart.lft + 1 = orgchart.rgt --leaf THEN ‘{vacant}’ WHEN orgchart.emp = removed AND orgchart.lft + 1 <> orgchart.rgt -- promote subordinate and vacate THEN (SELECT o1.emp FROM orgchart AS o1 WHERE orgchart.lft + 1 = o1.lft) WHEN orgchart.emp = (SELECT o1.emp FROM orgchart AS o1 WHERE orgchart.lft + 1 = o1.lft) THEN ‘{vacant}’ ELSE emp END; 31
Nested Set to Adjacency List SELECT B.id AS boss, P.emp, P.lft, P.rgt FROM orgchart as P LEFT OUTER JOIN emp AS B ON B.lft = (SELECT MAX(S.lft) FROM orgchart AS S WHERE P.lft > S.lft AND P.lft < S.rgt); boss emp lft rgt NULL Anthony 1 12 Anthony Beryl 2 3 Anthony Charles 4 11 Charles Denise 5 6 Charles Ellen 7 8 Charles Frank 9 10 32
Frequent Insertion Trees Avoid overhead (locking + updating) with larger spreads and bigger gaps emp lft rgt Anthony 100 1200 Beryl 200 300 Charles 400 1100 Denise 500 600 Ellen 700 800 Frank 900 1000 33
Frequent Insertion Trees Avoid overhead (locking + updating) with larger spreads and bigger gaps emp lft rgt Anthony 100 1200 Beryl 200 300 Charles 400 1100 Denise 500 600 Ellen 700 800 Frank 900 1000 Datatype of (lft, rgt)? - INTEGER (full range) - FLOAT / REAL / DOUBLE - NUMERIC(p,s) / DECIMAL(p,s) 33
Frequent Insertion Trees Avoid overhead (locking + updating) with larger spreads and bigger gaps emp lft rgt Anthony 100 1200 Beryl 200 300 Charles 400 1100 Denise 500 600 Ellen 700 800 Frank 900 1000 Datatype of (lft, rgt)? - INTEGER (full range) - FLOAT / REAL / DOUBLE - NUMERIC(p,s) / DECIMAL(p,s) 33
Frequent Insertion Trees Avoid overhead (locking + updating) with larger spreads and bigger gaps emp lft rgt Anthony 100 1200 Beryl 200 300 Charles 400 1100 Denise 500 600 Ellen 700 800 Frank 900 1000 Datatype of (lft, rgt)? - INTEGER (full range) - FLOAT / REAL / DOUBLE - NUMERIC(p,s) / DECIMAL(p,s) 33
Frequent Insertion Trees Avoid overhead (locking + updating) with larger spreads and bigger gaps emp lft rgt Anthony 100 1200 Beryl 200 300 Charles 400 1100 Denise 500 600 Ellen 700 800 Frank 900 1000 Datatype of (lft, rgt)? - INTEGER (full range) - FLOAT / REAL / DOUBLE - NUMERIC(p,s) / DECIMAL(p,s) 33
Hybrid Models Adjacency List with Nested Sets (node, parent, lft, rgt) Nested Sets with depth Adjacency List with depth ... Denormalisation to save subselects or joins 34
Nested Intervals Rational Number Encodings 35
Nested Intervals Model Rational numbers (a/b, with a and b integers) ((p.lft <= c.lft) AND (c.rgt <= p.rgt)) 0/5 A 5/5 1/5 B 2/5 3/5 C 4/5 36
Nested Intervals Model a b 37
Nested Intervals Model a b a+(b-a)/3 a+2(b-a)/3 37
Nested Intervals Model Finding GCD (greatest common divisor) 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; 38
Nested Intervals Model Binary Node (x, y) Fractions 39
Nested Intervals Model Binary Node (x, y) Fractions First node (1, 1/2) 39
Nested Intervals Model Binary Node (x, y) Fractions First node (1, 1/2) depth-first convergence point 39
Nested Intervals Model Binary Node (x, y) Fractions First child of first node (1, 3/4) First node (1, 1/2) depth-first convergence point 39
Nested Intervals Model Binary Node (x, y) Fractions First child of first node (1, 3/4) First node (1, 1/2) depth-first convergence point breadth-first convergence point 39
Nested Intervals Model Binary Node (x, y) Fractions First child of first node (1, 3/4) First node (1, 1/2) depth-first convergence point breadth-first convergence point 39
Nested Intervals Model Binary Node (x, y) Fractions First child of first node (1, 3/4) First node (1, 1/2) depth-first convergence point breadth-first convergence point 39
Nested Intervals Model 40
Nested Intervals Model CREATE FUNCTION x_numer( IN numer INT, IN denom INT ) 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 red_den = ret_den/2; END WHILE; RETURN ret_num; -- ret_den -- for x_denom() END; 40
Nested Intervals Model 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 red_den = ret_den/2; END WHILE; RETURN ret_num; -- ret_den for parent_denom() END; 41
Nested Intervals Model Similar functions for: sibling_numer(), sibling_denom() child_numer(), child_denom() enumerated_path(), distance() path_numer(), path_denom() 42
Nested Intervals Model Similar functions for: sibling_numer(), sibling_denom() child_numer(), child_denom() enumerated_path(), distance() path_numer(), path_denom() INSERT INTO orgchart (name, numer, denom) VALUES (‘Anthony’, path_numer(‘1’), path_denom(‘1’)), (‘Beryl’, path_numer(‘1.1’), path_denom(‘1.1’)), (‘Charles’, path_numer(‘1.2’), path_denom(‘1.2’)), (‘Denise’, path_numer(‘1.2.1’), path_denom(‘1.2.1’)); 42
Nested Intervals Encodings Interval Halving average: (lft + rgt) / 2 43
Nested Intervals Encodings Interval Halving average: (lft + rgt) / 2 Farey Fractions a/b and c/d neighbours => bc -ad = 1 mediant: (lft_num + rgt_num) (lft_den + rgt_den) 43
Nested Intervals Encodings Continued Fractions 1.1.2.1 Reverse (or additive) Continued Fractions 44
Proprietary Solutions Oracle 45
Oracle: CONNECT BY PRIOR Traversing the tree SELECT emp, boss FROM emp_orgchart START WITH boss IS NULL CONNECT BY [NOCYCLE] PRIOR emp = boss; emp boss A NULL B A G B C A D C E C F C 46
Oracle: CONNECT BY PRIOR Traversing the tree SELECT emp, boss FROM emp_orgchart START WITH boss = ‘C’ IS NULL CONNECT BY [NOCYCLE] PRIOR emp = boss; emp boss D C E C F C 46
Oracle: CONNECT BY PRIOR Traversing the tree SELECT emp, boss, salary, LEVEL AS lvl, LPAD(' ', 2*(LEVEL-1)) || emp AS tree, CONNECT_BY_IS_LEAF AS is_leaf FROM emp_orgchart CONNECT BY PRIOR emp = boss START WITH boss IS NULL ORDER SIBLINGS BY salary DESC; emp boss salary lvl tree is_leaf A NULL 1000.00 1 A 0 B A 900.00 2 B 0 G B 800.00 3 G 1 C A 900.00 2 C 0 D C 800.00 3 D 1 E C 700.00 3 E 1 F C 600.00 3 F 1 47
Oracle: CONNECT BY PRIOR Determining the relationship between two nodes SELECT COUNT(*) AS ‘is_subordinate’ FROM emp_orgchart WHERE emp = :subordinate AND LEVEL > 1 START WITH emp = :superior CONNECT BY PRIOR emp = boss; 48
Oracle: CONNECT BY PRIOR Determining the relationship between two nodes SELECT COUNT(*) AS ‘is_subordinate’ FROM emp_orgchart WHERE emp = :subordinate AND LEVEL > 1 START WITH emp = :superior CONNECT BY PRIOR emp = boss; A subordinate of C? 0 F subordinate of A? 1 48
Oracle: CONNECT_BY_ROOT Determining the ancestor of a node SELECT emp_id, CONNECT_BY_ROOT emp_id AS root FROM orgchart START WITH boss = ‘A’ CONNECT BY PRIOR emp_id = boss; emp_id root B B G B C C D C E C F C 49
Oracle: SYS_CONNECT_BY_PATH Materialized Path View SELECT emp_id, SYS_CONNECT_BY_PATH (emp_id,'.') AS path_string FROM orgchart START WITH boss IS NULL CONNECT BY PRIOR emp_id = boss ORDER BY 2; emp_id path_string A .A B .A.B C .A.C D .A.C.D E .A.C.E F .A.C.F 50
Common Table Expressions SQL-99 Standard 51
Common Table Expressions CREATE TABLE emp_orgchart ( emp VARCHAR(10) PRIMARY KEY, boss VARCHAR(10) REFERENCES emp_orgchart(emp_id), salary TEXT ); INSERT INTO emp_orgchart (emp, boss, salary) VALUES (‘A’, NULL, 1000.00), (‘B’, ‘A’, 900.00), (‘C’, ‘A’, 900.00), A (‘D’, ‘C’, 800.00), (‘E’, ‘C’, 700.00), (‘F’, ‘C’, 600.00), B C (‘G’, ‘B’, 800.00); G D E F 52
Common Table Expressions WITH RECURSIVE hierarchy AS ( -- non recursive term SELECT * FROM emp_orgchart WHERE boss IS NULL UNION ALL -- recursive term SELECT E1.* FROM emp_orgchart AS E1 JOIN hierarchy AS E2 ON E1.boss = E2.emp ) SELECT * FROM hierarchy ORDER BY emp; 53
Common Table Expressions WITH RECURSIVE hierarchy AS ( -- non recursive term SELECT * FROM emp_orgchart WHERE boss IS NULL UNION ALL -- recursive term SELECT E1.* FROM emp_orgchart AS E1 JOIN hierarchy AS E2 ON E1.boss = E2.emp ) SELECT * FROM hierarchy ORDER BY emp; 53
Common Table Expressions WITH RECURSIVE hierarchy AS ( -- non recursive term SELECT * FROM emp_orgchart WHERE boss IS NULL UNION ALL -- recursive term SELECT E1.* FROM emp_orgchart AS E1 JOIN hierarchy AS E2 ON E1.boss = E2.emp ) SELECT * FROM hierarchy ORDER BY emp; 53
Common Table Expressions WITH RECURSIVE hierarchy AS ( -- non recursive term SELECT * FROM emp_orgchart WHERE boss IS NULL emp boss salary UNION ALL A NULL 1000.00 -- recursive term B A 900.00 SELECT E1.* C A 900.00 FROM emp_orgchart AS E1 D C 800.00 JOIN hierarchy AS E2 E C 700.00 ON E1.boss = E2.emp F C 600.00 ) SELECT * G B 800.00 FROM hierarchy ORDER BY emp; 53
Common Table Expressions WITH RECURSIVE hierarchy AS ( SELECT *, 1 AS lvl, CAST(emp AS TEXT) AS tree, emp || ‘.’ AS path FROM emp_orgchart WHERE boss IS NULL UNION ALL SELECT E1.*, E2.lvl + 1 AS lvl, LPAD(E1.emp, lvl * 2, ‘ ’) AS tree, E2.path || E1.emp || ‘.’ AS path FROM emp_orgchart JOIN hierarchy AS E2 ON E1.boss = E2.emp ) SELECT * FROM hierarchy ORDER BY path; 54
Common Table Expressions WITH RECURSIVE hierarchy AS ( SELECT *, 1 AS lvl, CAST(emp AS TEXT) AS tree, emp || ‘.’ AS path FROM emp_orgchart WHERE boss IS NULL UNION ALL SELECT E1.*, E2.lvl + 1 AS lvl, LPAD(E1.emp, lvl * 2, ‘ ’) AS tree, E2.path || E1.emp || ‘.’ AS path FROM emp_orgchart JOIN hierarchy AS E2 ON E1.boss = E2.emp ) SELECT * FROM hierarchy ORDER BY path; 54
Common Table Expressions WITH RECURSIVE hierarchy AS ( SELECT *, 1 AS lvl, CAST(emp AS TEXT) AS tree, emp || ‘.’ AS path FROM emp_orgchart WHERE boss IS NULL UNION ALL SELECT E1.*, E2.lvl + 1 AS lvl, LPAD(E1.emp, lvl * 2, ‘ ’) AS tree, E2.path || E1.emp || ‘.’ AS path FROM emp_orgchart JOIN hierarchy AS E2 ON E1.boss = E2.emp ) SELECT * FROM hierarchy ORDER BY path; 54
Common Table Expressions WITH RECURSIVE hierarchy AS ( SELECT *, 1 AS lvl, CAST(emp AS TEXT) AS tree, emp || ‘.’ AS path FROM emp_orgchart WHERE boss IS NULL UNION ALL SELECT E1.*, E2.lvl + 1 AS lvl, LPAD(E1.emp, lvl * 2, ‘ ’) AS tree, E2.path || E1.emp || ‘.’ AS path FROM emp_orgchart JOIN hierarchy AS E2 ON E1.boss = E2.emp ) SELECT * FROM hierarchy ORDER BY path; 54
Common Table Expressions WITH RECURSIVE hierarchy AS ( SELECT *, 1 AS lvl, CAST(emp AS TEXT) AS tree, emp || ‘.’ AS path FROM emp_orgchart WHERE boss IS NULL UNION ALL SELECT E1.*, E2.lvl + 1 AS lvl, LPAD(E1.emp, lvl * 2, ‘ ’) AS tree, E2.path || E1.emp || ‘.’ AS path FROM emp_orgchart JOIN hierarchy AS E2 ON E1.boss = E2.emp ) SELECT * FROM hierarchy ORDER BY path; 54
Common Table Expressions WITH RECURSIVE hierarchy AS ( SELECT *, 1 AS lvl, emp CAST(emp salary boss AS TEXT) AS tree, tree lvl path emp || ‘.’ AS path A NULL 1000.00 1 A A. FROM emp_orgchart WHERE boss IS NULL B A 900.00 2 B A.B. UNION ALL SELECT E1.*, G B 800.00 3 G A.B.G. E2.lvl + 1 AS lvl, C LPAD(E1.emp, lvl * 2, ‘ ’)CAS tree, A 900.00 2 A.C. E2.path || E1.emp || ‘.’ AS path D C 800.00 FROM emp_orgchart 3 D A.C.D. JOIN hierarchy AS E2 E C 700.00 3 E A.C.E. ON E1.boss = E2.emp ) F C 600.00 3 F A.C.F. SELECT * FROM hierarchy ORDER BY path; 54
Common Table Expressions WITH RECURSIVE hierarchy AS ( SELECT *, 1 AS lvl, CAST(emp AS TEXT) AS tree FROM emp_orgchart WHERE boss = ‘A’ UNION ALL SELECT E1.*, E2.lvl + 1 AS lvl, LPAD(E1.emp, depth * 2, ‘ ’) AS tree FROM emp_orgchart JOIN hierarchy AS E2 ON E1.boss = E2.emp WHERE E2.lvl < 3 -- termination condition ) SELECT * FROM hierarchy ORDER BY path; 55
Common Table Expressions WITH RECURSIVE hierarchy AS ( SELECT *, 1 AS lvl, CAST(emp AS TEXT) AS tree FROM emp_orgchart WHERE boss = ‘A’ UNION ALL SELECT E1.*, E2.lvl + 1 AS lvl, LPAD(E1.emp, depth * 2, ‘ ’) AS tree FROM emp_orgchart JOIN hierarchy AS E2 ON E1.boss = E2.emp ) SELECT *, COALESCE((SELECT 0 FROM emp_orgchart E3 WHERE hierarchy.emp = E3.boss FETCH FIRST ROW ONLY), 1) AS is_leaf FROM hierarchy; 56
And the winner is... 57
And the winner is... 57
Questions ? 58
Resources Joe Celko, “Trees and Hierarchies in SQL for Smarties”, Morgan Kaufmann: http://www.amazon.com/dp/1558609202/ Vadim Tropashko, various articles and papers: http://www.dbazine.com/top-auth/top-auth-trop/ http://www.sigmod.org/sigmod/record/issues/ 0506/p47-article-tropashko.pdf http://arxiv.org/pdf/cs/0402051 59
Thank you! Contact details: Lorenzo Alberton lorenzo@ibuildings.com http://www.alberton.info http://joind.in/talk/view/585

More Related Content

PDF
Sql Antipatterns Strike Back
byKarwin Software Solutions LLC
 
PDF
Trees and Hierarchies in SQL
byEduard Hildebrandt
 
PDF
Practical Object Oriented Models In Sql
byKarwin Software Solutions LLC
 
PDF
Models for hierarchical data
byKarwin Software Solutions LLC
 
PDF
Extensible Data Modeling
byKarwin Software Solutions LLC
 
PDF
How to Use JSON in MySQL Wrong
byKarwin Software Solutions LLC
 
PDF
Sql query patterns, optimized
byKarwin Software Solutions LLC
 
PPTX
Data storage and indexing
bypradeepa velmurugan
 
Sql Antipatterns Strike Back
byKarwin Software Solutions LLC
 
Trees and Hierarchies in SQL
byEduard Hildebrandt
 
Practical Object Oriented Models In Sql
byKarwin Software Solutions LLC
 
Models for hierarchical data
byKarwin Software Solutions LLC
 
Extensible Data Modeling
byKarwin Software Solutions LLC
 
How to Use JSON in MySQL Wrong
byKarwin Software Solutions LLC
 
Sql query patterns, optimized
byKarwin Software Solutions LLC
 
Data storage and indexing
bypradeepa velmurugan
 

What's hot

KEY
Graphs in the Database: Rdbms In The Social Networks Age
byLorenzo Alberton
 
PDF
Recursive Query Throwdown
byKarwin Software Solutions LLC
 
PDF
Database Anti Patterns
byRobert Treat
 
PPTX
Introduction to SQL Antipatterns
byKrishnakumar S
 
PDF
MySQL Index Cookbook
byMYXPLAIN
 
PDF
BigData_TP4 : Cassandra
byLilia Sfaxi
 
PDF
BigData_Chp2: Hadoop & Map-Reduce
byLilia Sfaxi
 
PPTX
Introduction to Apache ZooKeeper
bySaurav Haloi
 
PPT
Les Contraintes | SQL Oracle
bywebreaker
 
PDF
TP1 Big Data - MapReduce
byAmal Abid
 
PDF
BigData_TP5 : Neo4J
byLilia Sfaxi
 
PDF
ClickHouse tips and tricks. Webinar slides. By Robert Hodges, Altinity CEO
byAltinity Ltd
 
PDF
Etsy Activity Feeds Architecture
byDan McKinley
 
PDF
Introduction to Redis
byDvir Volk
 
PDF
Cassandra Introduction & Features
byDataStax Academy
 
KEY
Big Data in Real-Time at Twitter
bynkallen
 
PPTX
Introduction to Storm
byChandler Huang
 
PDF
SEH overwrite and its exploitability
byFFRI, Inc.
 
PDF
Dynamic Allocation in Spark
byDatabricks
 
PDF
SQL Outer Joins for Fun and Profit
byKarwin Software Solutions LLC
 
Graphs in the Database: Rdbms In The Social Networks Age
byLorenzo Alberton
 
Recursive Query Throwdown
byKarwin Software Solutions LLC
 
Database Anti Patterns
byRobert Treat
 
Introduction to SQL Antipatterns
byKrishnakumar S
 
MySQL Index Cookbook
byMYXPLAIN
 
BigData_TP4 : Cassandra
byLilia Sfaxi
 
BigData_Chp2: Hadoop & Map-Reduce
byLilia Sfaxi
 
Introduction to Apache ZooKeeper
bySaurav Haloi
 
Les Contraintes | SQL Oracle
bywebreaker
 
TP1 Big Data - MapReduce
byAmal Abid
 
BigData_TP5 : Neo4J
byLilia Sfaxi
 
ClickHouse tips and tricks. Webinar slides. By Robert Hodges, Altinity CEO
byAltinity Ltd
 
Etsy Activity Feeds Architecture
byDan McKinley
 
Introduction to Redis
byDvir Volk
 
Cassandra Introduction & Features
byDataStax Academy
 
Big Data in Real-Time at Twitter
bynkallen
 
Introduction to Storm
byChandler Huang
 
SEH overwrite and its exploitability
byFFRI, Inc.
 
Dynamic Allocation in Spark
byDatabricks
 
SQL Outer Joins for Fun and Profit
byKarwin Software Solutions LLC
 

Viewers also liked

PPTX
Network Intent Composition in OpenDaylight
byOpenDaylight
 
PDF
Hadoop-DS: Which SQL-on-Hadoop Rules the Herd
byIBM Analytics
 
PDF
HBaseCon2017 Transactions in HBase
byHBaseCon
 
KEY
Scaling Teams, Processes and Architectures
byLorenzo Alberton
 
KEY
Scalable Architectures - Taming the Twitter Firehose
byLorenzo Alberton
 
KEY
Modern Algorithms and Data Structures - 1. Bloom Filters, Merkle Trees
byLorenzo Alberton
 
KEY
The Art of Scalability - Managing growth
byLorenzo Alberton
 
PDF
Monitoring at scale - Intuitive dashboard design
byLorenzo Alberton
 
KEY
NoSQL Databases: Why, what and when
byLorenzo Alberton
 
PDF
MySQL Group Replication
byKenny Gryp
 
PDF
Inno db internals innodb file formats and source code structure
byzhaolinjnu
 
PDF
MySQL InnoDB Cluster - Group Replication
byFrederic Descamps
 
PDF
Percona XtraDB Cluster vs Galera Cluster vs MySQL Group Replication
byKenny Gryp
 
PDF
MySQL Best Practices - OTN LAD Tour
byRonald Bradford
 
PDF
MySQL 5.7: Focus on InnoDB
byMario Beck
 
PPTX
Mysql参数-GDB
byzhaolinjnu
 
PDF
MySQL Group Replication
byManish Kumar
 
PDF
Using Apache Spark and MySQL for Data Analysis
bySveta Smirnova
 
PDF
MySQL High-Availability and Scale-Out architectures
byFromDual GmbH
 
PDF
MySQL InnoDB Cluster and MySQL Group Replication @HKOSC 2017
byIvan Ma
 
Network Intent Composition in OpenDaylight
byOpenDaylight
 
Hadoop-DS: Which SQL-on-Hadoop Rules the Herd
byIBM Analytics
 
HBaseCon2017 Transactions in HBase
byHBaseCon
 
Scaling Teams, Processes and Architectures
byLorenzo Alberton
 
Scalable Architectures - Taming the Twitter Firehose
byLorenzo Alberton
 
Modern Algorithms and Data Structures - 1. Bloom Filters, Merkle Trees
byLorenzo Alberton
 
The Art of Scalability - Managing growth
byLorenzo Alberton
 
Monitoring at scale - Intuitive dashboard design
byLorenzo Alberton
 
NoSQL Databases: Why, what and when
byLorenzo Alberton
 
MySQL Group Replication
byKenny Gryp
 
Inno db internals innodb file formats and source code structure
byzhaolinjnu
 
MySQL InnoDB Cluster - Group Replication
byFrederic Descamps
 
Percona XtraDB Cluster vs Galera Cluster vs MySQL Group Replication
byKenny Gryp
 
MySQL Best Practices - OTN LAD Tour
byRonald Bradford
 
MySQL 5.7: Focus on InnoDB
byMario Beck
 
Mysql参数-GDB
byzhaolinjnu
 
MySQL Group Replication
byManish Kumar
 
Using Apache Spark and MySQL for Data Analysis
bySveta Smirnova
 
MySQL High-Availability and Scale-Out architectures
byFromDual GmbH
 
MySQL InnoDB Cluster and MySQL Group Replication @HKOSC 2017
byIvan Ma
 

Similar to Trees In The Database - Advanced data structures

PDF
ANSI SQL Transparent Multipath Hierarchical Structured Data Processing for Re...
byMichael M David
 
KEY
ZendCon 2011 Learning CouchDB
byBradley Holt
 
PPT
Multidimensional Indexing
byDigvijay Singh
 
PDF
Invisible loading
byDaniel Abadi
 
PPT
Unit 05 dbms
byanuragmbst
 
PPSX
Dbms presentation
byBhaskar D Garg
 
PPTX
entityrelationshipdiagrams & SQL Practice Exercises.pptx
byMustafaHyderPublicAd
 
PDF
Index management in depth
byAndrea Giuliano
 
PPT
Normalization
bymomo2187
 
PDF
Welcome to International Journal of Engineering Research and Development (IJERD)
byIJERD Editor
 
PDF
Relational Cloud
byAntonio Severien
 
PPT
Computernotes datastructures-22-111227202516-phpapp02
byqueenmarry
 
PPTX
Using SQL to process hierarchies
byConnor McDonald
 
PDF
A relational model of data for large shared data banks
bySammy Alvarez
 
PDF
Normalization form tutorial
byNikhildas P C
 
PPTX
Slide4 er-stu
bymarisa kuntasup
 
PDF
Tutorial de forms 10g
bymiguel
 
PPTX
Erd examples
byJennifer Polack
 
PDF
Bi
byjeff kit
 
PDF
Duplicaterows
byoracle documents
 
ANSI SQL Transparent Multipath Hierarchical Structured Data Processing for Re...
byMichael M David
 
ZendCon 2011 Learning CouchDB
byBradley Holt
 
Multidimensional Indexing
byDigvijay Singh
 
Invisible loading
byDaniel Abadi
 
Unit 05 dbms
byanuragmbst
 
Dbms presentation
byBhaskar D Garg
 
entityrelationshipdiagrams & SQL Practice Exercises.pptx
byMustafaHyderPublicAd
 
Index management in depth
byAndrea Giuliano
 
Normalization
bymomo2187
 
Welcome to International Journal of Engineering Research and Development (IJERD)
byIJERD Editor
 
Relational Cloud
byAntonio Severien
 
Computernotes datastructures-22-111227202516-phpapp02
byqueenmarry
 
Using SQL to process hierarchies
byConnor McDonald
 
A relational model of data for large shared data banks
bySammy Alvarez
 
Normalization form tutorial
byNikhildas P C
 
Slide4 er-stu
bymarisa kuntasup
 
Tutorial de forms 10g
bymiguel
 
Erd examples
byJennifer Polack
 
Bi
byjeff kit
 
Duplicaterows
byoracle documents
 

Recently uploaded

PDF
🚀 Agentic Automation in Action 1/3 – From RPA to Agentic Automation (Arabic S...
byanabulhac
 
PDF
RaBitQ, JSON Index, Schema Evolution, What's New in Milvus 2.6
byZilliz
 
PPTX
Autonomous Convoy Routing via Drone Swarms and Multi-Modal Threat Detection
byIvan Ruchkin
 
PDF
Poster: Generalizable Image Repair for Robust Visual Control
byIvan Ruchkin
 
DOCX
Formula 3 - MACO using general limit.docx
byMarkus Janssen
 
DOCX
Formula 2 - APIC HBEL general calculation.docx
byMarkus Janssen
 
PPTX
xCapture v3: Efficient, Always-On Thread Level Observability with eBPF by Tan...
byScyllaDB
 
PDF
Energia Nowa and byteLAKE Partner to Develop Intelligent Services for Energy ...
bybyteLAKE
 
PDF
Morgenbooster: Navigating Ai Criticism with Systems Thinking
by1508 A/S
 
PDF
Keynote: X-rAI Specs, Submarines and Juice
byAll Things Open
 
PDF
Airtable Building Semantic Search with Milvus
byZilliz
 
PDF
ZGC: A Decade of Innovation by Stefan Johansson
byScyllaDB
 
PDF
Session 3 - UiPath Coded Agents & MCP Server in Action
byDianaGray10
 
PDF
The End of the Missed Call - How AI Recaptures Lost Leads and Secures ROI
byiovox
 
PPTX
Stop Worrying, Start Wiring: Azure Serverless for the AI Era
byMuralidharan Deenathayalan
 
PDF
"Building Interactive Async UI with React 19 and Ariakit", Aurora Scharff
byFwdays
 
PPTX
Session 5 - Specialized AI Associate Series: Build a Document Understanding ...
byDianaGray10
 
PDF
AI-Driven DevOps: How LLMs and Agents Are Changing Software Delivery
byAll Things Open
 
PPTX
Strategic Briefing - Supply-Chain and Autonomous AI Convergence - October-18-...
bySergio De Gregorio
 
PDF
AWS Community Day Indonesia 2025 - Attack the Cloud Before Attackers Do Build...
byMuhammad Yuga Nugraha
 
🚀 Agentic Automation in Action 1/3 – From RPA to Agentic Automation (Arabic S...
byanabulhac
 
RaBitQ, JSON Index, Schema Evolution, What's New in Milvus 2.6
byZilliz
 
Autonomous Convoy Routing via Drone Swarms and Multi-Modal Threat Detection
byIvan Ruchkin
 
Poster: Generalizable Image Repair for Robust Visual Control
byIvan Ruchkin
 
Formula 3 - MACO using general limit.docx
byMarkus Janssen
 
Formula 2 - APIC HBEL general calculation.docx
byMarkus Janssen
 
xCapture v3: Efficient, Always-On Thread Level Observability with eBPF by Tan...
byScyllaDB
 
Energia Nowa and byteLAKE Partner to Develop Intelligent Services for Energy ...
bybyteLAKE
 
Morgenbooster: Navigating Ai Criticism with Systems Thinking
by1508 A/S
 
Keynote: X-rAI Specs, Submarines and Juice
byAll Things Open
 
Airtable Building Semantic Search with Milvus
byZilliz
 
ZGC: A Decade of Innovation by Stefan Johansson
byScyllaDB
 
Session 3 - UiPath Coded Agents & MCP Server in Action
byDianaGray10
 
The End of the Missed Call - How AI Recaptures Lost Leads and Secures ROI
byiovox
 
Stop Worrying, Start Wiring: Azure Serverless for the AI Era
byMuralidharan Deenathayalan
 
"Building Interactive Async UI with React 19 and Ariakit", Aurora Scharff
byFwdays
 
Session 5 - Specialized AI Associate Series: Build a Document Understanding ...
byDianaGray10
 
AI-Driven DevOps: How LLMs and Agents Are Changing Software Delivery
byAll Things Open
 
Strategic Briefing - Supply-Chain and Autonomous AI Convergence - October-18-...
bySergio De Gregorio
 
AWS Community Day Indonesia 2025 - Attack the Cloud Before Attackers Do Build...
byMuhammad Yuga Nugraha
 

Trees In The Database - Advanced data structures

  • 1.
    Trees in theDatabase Advanced Data Structures Lorenzo Alberton lorenzo@ibuildings.com DPC09, Amsterdam, 13 June 2009
  • 2.
  • 3.
    Lorenzo Alberton MDB2 Calendar Pager Translation2 Mail_Queue DB_QueryTool 2
  • 4.
    Lorenzo Alberton MDB2 Calendar Pager Translation2 Mail_Queue DB_QueryTool 2
  • 5.
  • 6.
  • 7.
  • 8.
  • 9.
  • 10.
    Adjacency List Model AKA“parent-child” model 4
  • 11.
    Adjacency List Model CREATETABLE emp_orgchart ( emp VARCHAR(10) NOT NULL PRIMARY KEY, boss VARCHAR(10), salary DECIMAL(6,2) NOT NULL ); A emp boss salary A NULL 1000.00 B C B A 900.00 C A 900.00 D C 800.00 D E F E C 700.00 F C 600.00 5
  • 12.
    Adjacency List Model Finding the root node SELECT * FROM emp_orgchart WHERE boss IS NULL; Finding the leaf nodes SELECT e1.* FROM emp_orgchart AS e1 LEFT JOIN emp_orgchart AS e2 ON e1.emp = e2.boss WHERE e2.emp IS NULL; 6
  • 13.
    Adjacency List ModelAnomalies UPDATE anomalies START TRANSACTION; emp boss salary UPDATE emp_orgchart A NULL 1000.00 SET emp = ‘C1’ B A 900.00 WHERE emp = ‘C’; C1 A 900.00 D C 800.00 UPDATE emp_orgchart E C 700.00 SET boss = ‘C1’ F C 600.00 WHERE boss = ‘C’; COMMIT; 7
  • 14.
    Adjacency List ModelAnomalies UPDATE anomalies START TRANSACTION; emp boss salary UPDATE emp_orgchart A NULL 1000.00 SET emp = ‘C1’ B A 900.00 WHERE emp = ‘C’; C1 A 900.00 D C 800.00 UPDATE emp_orgchart E C 700.00 SET boss = ‘C1’ F C 600.00 WHERE boss = ‘C’; COMMIT; 7
  • 15.
    Adjacency List ModelAnomalies UPDATE anomalies START TRANSACTION; UPDATE emp_orgchart SET emp = CASE emp UPDATE emp_orgchart WHEN ‘C’ THEN ‘C1’ SET emp = ‘C1’ ELSE emp END, WHERE emp = ‘C’; boss = CASE boss WHEN ‘C’ THEN ‘C1’ UPDATE emp_orgchart ELSE boss END SET boss = ‘C1’ WHERE ‘C’ IN (emp, boss); WHERE boss = ‘C’; COMMIT; 7
  • 16.
    Adjacency List ModelAnomalies INSERT anomalies 8
  • 17.
    Adjacency List ModelAnomalies INSERT anomalies INSERT INTO emp_orgchart (emp, boss) VALUES (‘G’, ‘H’), (‘H’, ‘G’); G H 8
  • 18.
    Adjacency List ModelAnomalies INSERT anomalies INSERT INTO emp_orgchart (emp, boss) VALUES (‘G’, ‘H’), (‘H’, ‘G’); G H INSERT INTO emp_orgchart VALUES (‘M’, ‘M’); M 8
  • 19.
    Adjacency List ModelAnomalies DELETE anomalies DELETE FROM emp_orgchart WHERE emp = ‘C’; A B C D E F 9
  • 20.
    Adjacency List ModelAnomalies DELETE anomalies DELETE FROM emp_orgchart WHERE emp = ‘C’; A B C D E F 9
  • 21.
    Fixing the AdjacencyList Model CREATE TABLE emp ( id INTEGER DEFAULT 0 PRIMARY KEY, name VARCHAR(10) NOT NULL, salary DECIMAL (6,2) NOT NULL CHECK (salary >= 0.00), ... ); CREATE TABLE orgchart ( emp_id INTEGER NOT NULL DEFAULT 0 -- vacant REFERENCES emp(id) ON DELETE SET DEFAULT ON UPDATE CASCADE, boss_id INTEGER -- NULL means root node REFERENCES emp(id), ... ); 10
  • 22.
    Fixing the AdjacencyList Model -- cannot be your own boss CHECK ((boss_id <> emp_id) OR (boss_id = 0 AND emp_id = 0)), 11
  • 23.
    Fixing the AdjacencyList Model -- cannot be your own boss CHECK ((boss_id <> emp_id) OR (boss_id = 0 AND emp_id = 0)), -- prevent longer cycles UNIQUE (emp_id, boss_id), 11
  • 24.
    Fixing the AdjacencyList Model -- cannot be your own boss CHECK ((boss_id <> emp_id) OR (boss_id = 0 AND emp_id = 0)), -- prevent longer cycles UNIQUE (emp_id, boss_id), -- connected graph (edges = nodes - 1) CHECK ((SELECT COUNT(*) FROM orgchart) - 1 = (SELECT COUNT(boss_id) FROM orgchart)), 11
  • 25.
    Fixing the AdjacencyList Model -- cannot be your own boss CHECK ((boss_id <> emp_id) OR (boss_id = 0 AND emp_id = 0)), -- prevent longer cycles UNIQUE (emp_id, boss_id), -- connected graph (edges = nodes - 1) CHECK ((SELECT COUNT(*) FROM orgchart) - 1 = (SELECT COUNT(boss_id) FROM orgchart)), -- one root only CHECK ((SELECT COUNT(*) FROM orgchart WHERE boss_id IS NULL) = 1), 11
  • 26.
    Adjacency List Model- Navigation Loops / Self-Joins procedural code SELECT o1.emp AS e1, o2.emp AS e2, CREATE PROCEDURE o3.emp AS e3 TreeTraversal (IN FROM emp_orgchart AS o1 current_emp_id INT) LEFT OUTER JOIN BEGIN emp_orgchart AS o2 ... ON o1.emp = o2.boss LEFT OUTER JOIN emp_orgchart AS o3 ON o2.emp = o3.boss WHERE o1.emp = ‘A’; 12
  • 27.
    Adjacency List Model- Deletion 13
  • 28.
    Adjacency List Model- Deletion A B C D E F 13
  • 29.
    Adjacency List Model- Deletion A B C D x E F 13
  • 30.
    Adjacency List Model- Deletion A A B C B C D x E F D E F 13
  • 31.
    Adjacency List Model- Deletion A A A B C B C D x E F B D D E E F F 13
  • 32.
    Adjacency List Model- Deletion A A A A B C B C B C D x E F B D D E E F F D E F 13
  • 33.
    Adjacency List Model- Deletion A A A A B C B C B D C D x E F B D D E E F F D E F 13
  • 34.
    Adjacency List Model- Deletion A A A A B C B C B D C D x E F B D D E E F F D E F Requires traversal (deferred constraints) 13
  • 35.
    Path Enumeration Model akaMaterialized Path 14
  • 36.
    Path Enumeration Model CREATETABLE emp_orgchart ( emp_id CHAR(1) NOT NULL PRIMARY KEY -- if using a separator, don’t use it in the ID CHECK (REPLACE(emp_id, ‘/’, ‘’) = emp_id), emp_name VARCHAR(10) NOT NULL, path_string VARCHAR(512) NOT NULL ); emp_id emp_name path_string A A Anthony A B Beryl AB B C C Charles AC D Denise ACD E Ellen ACE D E F F Frank ACF 15
  • 37.
    Path Enumeration Model -- prevent cycles (nodes appearing twice: ‘ABCA’) CHECK (NOT EXISTS( SELECT * FROM emp_orgchart AS D1, emp_orgchart AS P1 WHERE LENGTH(REPLACE(P1.path_string, D1.emp_id, ‘’)) < LENGTH(P1.path_string) - LENGTH(D1.emp_id)) )) -- No path can be longer than the number of nodes CHECK((SELECT MAX(LENGTH(path_string)) FROM emp_orgchart AS E1) <= (SELECT COUNT(emp_id) * LENGTH(emp_id) FROM emp_orgchart AS E2)) 16
  • 38.
  • 39.
    Path Enumeration Model Depth of the node 17
  • 40.
    Path Enumeration Model Depth of the node • LENGTH(path_string) / LENGTH(emp_id) 17
  • 41.
    Path Enumeration Model Depth of the node • LENGTH(path_string) / LENGTH(emp_id) • LENGTH(path_string) - LENGTH(REPLACE(path_string, ‘/’, ‘’)) + 1 17
  • 42.
    Path Enumeration Model Depth of the node • LENGTH(path_string) / LENGTH(emp_id) • LENGTH(path_string) - LENGTH(REPLACE(path_string, ‘/’, ‘’)) + 1 17
  • 43.
    Path Enumeration Model Depth of the node • LENGTH(path_string) / LENGTH(emp_id) • LENGTH(path_string) - LENGTH(REPLACE(path_string, ‘/’, ‘’)) + 1 Searching for subordinates 17
  • 44.
    Path Enumeration Model Depth of the node • LENGTH(path_string) / LENGTH(emp_id) • LENGTH(path_string) - LENGTH(REPLACE(path_string, ‘/’, ‘’)) + 1 Searching for subordinates • SELECT * FROM emp_orgchart WHERE path_string LIKE ‘%’ || :parent_emp_id || ‘%’; 17
  • 45.
    Path Enumeration Model Depth of the node • LENGTH(path_string) / LENGTH(emp_id) • LENGTH(path_string) - LENGTH(REPLACE(path_string, ‘/’, ‘’)) + 1 Searching for subordinates • SELECT * FROM emp_orgchart WHERE path_string LIKE ‘%’ || :parent_emp_id || ‘%’; • SELECT * FROM emp_orgchart WHERE path_string LIKE (SELECT path_string FROM emp_orgchart WHERE emp_id = :parent_emp_id) || ‘%’; 17
  • 46.
    Path Enumeration Model Searching for superiors SELECT SUBSTRING(P1.path_string FROM seq * LENGTH(P1.emp_id) FOR LENGTH(P1.emp_id)) AS emp_id FROM emp_orgchart AS P1, sequence AS S1 WHERE P1.emp_id = :search_emp_id AND S1.seq <= LENGTH(path_string)/ LENGTH(emp_id); 18
  • 47.
    Path Enumeration Model Deleting a subtree: DELETE FROM emp_orgchart WHERE path_string LIKE ( SELECT path_string FROM emp_orgchart WHERE emp_id = :deleted_node) || ‘%’; Deleting a single node: START TRANSACTION; DELETE FROM emp_orgchart WHERE emp_id = :deleted_node; UPDATE emp_orgchart SET path_string = REPLACE(path_string, :deleted_node, ‘’); COMMIT; 19
  • 48.
    Path Enumeration Model Insertion of a new node INSERT INTO emp_orgchart VALUES ( :new_emp_id, -- ‘M’ :new_name, -- ‘Maggie’ (SELECT path_string FROM emp_orgchart WHERE emp_id = :boss_of_new_emp) -- ‘D’ || :new_emp_id -- ‘M’ ); emp_id emp_name path_string D Denise ACD M Maggie ACDM 20
  • 49.
    Path Enumeration Model Insertion of a new node INSERT INTO emp_orgchart VALUES ( :new_emp_id, -- ‘M’ :new_name, -- ‘Maggie’ (SELECT path_string FROM emp_orgchart WHERE emp_id = :boss_of_new_emp) -- ‘D’ || :new_emp_id -- ‘M’ ); emp_id emp_name path_string D Denise ACD M Maggie ACDM 20
  • 50.
    Path Enumeration Model Insertion of a new node INSERT INTO emp_orgchart VALUES ( :new_emp_id, -- ‘M’ :new_name, -- ‘Maggie’ (SELECT path_string FROM emp_orgchart WHERE emp_id = :boss_of_new_emp) -- ‘D’ || :new_emp_id -- ‘M’ ); emp_id emp_name path_string D Denise ACD M Maggie ACDM 20
  • 51.
    Path Enumeration Model Splitting the path string into nodes 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, emp_orgchart AS P1 WHERE S1.seq BETWEEN 1 AND LENGTH(P1.path_string) + 1 AND SUBSTRING(‘/’ || P1.path_string || ‘/’ FROM S1.seq FOR 1) = ‘/’ 21
  • 52.
    Path Enumeration Model emp_name edge_path Edge Anthony 1. Beryl 1.1. Enumeration Charles 1.2. Model Denise 1.2.1. Ellen 1.2.2. Frank 1.2.3. Anthony Beryl Charles Denise Ellen Frank 22
  • 53.
    Nested Set Model akaModified Preorder Tree Traversal (MPTT) 23
  • 54.
    Nested Set Model A C B D E F 24
  • 55.
    Nested Set Model A C B D E F A 1 12 B C 2 3 4 11 D E F 5 6 7 8 9 10 24
  • 56.
    Nested Set Model CREATETABLE orgchart ( emp VARCHAR(10) NOT NULL PRIMARY KEY, lft INTEGER NOT NULL, rgt INTEGER NOT NULL ); A 1 12 B C 2 3 4 11 D E F 5 6 7 8 9 10 25
  • 57.
    Nested Set Model CREATE TABLE orgchart ( emp VARCHAR(10) NOT NULL PRIMARY KEY, lft INTEGER NOT NULL, rgt INTEGER NOT NULL ); A 1 12 B C 1 A 12 2 3 4 11 D E F 5 6 7 8 9 10 2 B 3 4 C 11 D E F 5 6 7 8 9 10 25
  • 58.
    Nested Set Model Finding root node 1 A 12 2 B 3 4 C 11 D E F 5 6 7 8 9 10 26
  • 59.
    Nested Set Model Finding root node SELECT * FROM orgchart WHERE lft = 1; 1 A 12 2 B 3 4 C 11 D E F 5 6 7 8 9 10 26
  • 60.
    Nested Set Model Finding root node SELECT * FROM orgchart WHERE lft = 1; 1 A 12 Finding leaf nodes 2 B 3 4 C 11 D E F 5 6 7 8 9 10 26
  • 61.
    Nested Set Model Finding root node SELECT * FROM orgchart WHERE lft = 1; 1 A 12 Finding leaf nodes SELECT * 2 B 3 4 C 11 FROM orgchart WHERE lft = (rgt - 1); D E F 5 6 7 8 9 10 26
  • 62.
    Nested Set Model Finding root node SELECT * FROM orgchart WHERE lft = 1; 1 A 12 Finding leaf nodes SELECT * 2 B 3 4 C 11 FROM orgchart WHERE lft = (rgt - 1); D E F Finding subtrees 5 6 7 8 9 10 26
  • 63.
    Nested Set Model Finding root node SELECT * FROM orgchart WHERE lft = 1; 1 A 12 Finding leaf nodes SELECT * 2 B 3 4 C 11 FROM orgchart WHERE lft = (rgt - 1); D E F Finding subtrees 5 6 7 8 9 10 SELECT Mgrs.emp AS boss Workers.emp AS worker FROM orgchart AS Mgrs, orgchart AS Workers WHERE Workers.lft > Mgrs.lft AND Workers.lft < Mgrs.rgt 26
  • 64.
    Nested Set Model Finding root node SELECT * FROM orgchart WHERE lft = 1; 1 A 12 Finding leaf nodes SELECT * 2 B 3 4 C 11 FROM orgchart WHERE lft = (rgt - 1); D E F Finding subtrees 5 6 7 8 9 10 SELECT Mgrs.emp AS boss Workers.emp AS worker FROM orgchart AS Mgrs, orgchart AS Workers WHERE Workers.lft > Mgrs.lft BETWEEN Mgrs.lft AND Mgrs.rgt AND Workers.lft < Mgrs.rgt 26
  • 65.
    Nested Set Model Finding the level of a node 27
  • 66.
    Nested Set Model Finding the level of a node SELECT o2.emp, COUNT(o1.emp) AS lvl FROM orgchart AS o1, orgchart AS o2 WHERE o2.lft BETWEEN o1.lft AND o1.rgt GROUP BY o2.emp; 27
  • 67.
    Nested Set Model Finding the level of a node SELECT o2.emp, COUNT(o1.emp) AS lvl FROM orgchart AS o1, orgchart AS o2 WHERE o2.lft BETWEEN o1.lft AND o1.rgt GROUP BY o2.emp; Finding the height of the tree 27
  • 68.
    Nested Set Model Finding the level of a node SELECT o2.emp, COUNT(o1.emp) AS lvl FROM orgchart AS o1, orgchart AS o2 WHERE o2.lft BETWEEN o1.lft AND o1.rgt GROUP BY o2.emp; Finding the height of the tree SELECT MAX(lvl) AS height FROM ( SELECT o2.emp, COUNT(o1.emp) - 1 FROM orgchart AS o1, orgchart AS o2 WHERE o2.lft BETWEEN o1.lft AND o1.rgt GROUP BY o2.emp) AS L1(emp, lvl); 27
  • 69.
    Nested Set Model Finding relative position SELECT CASE WHEN :emp1 = :emp2 THEN :emp1 || ‘ is ’ || :emp2 WHEN o1.lft BETWEEN o2.lft AND o2.rgt THEN :emp1 || ‘ subordinate to ’ || :emp2 WHEN o2.lft BETWEEN o1.lft AND o1.rgt THEN :emp2 || ‘ subordinate to ’ || :emp1 ELSE :emp1 || ‘ no relation to ’ || :emp2 END FROM orgchart AS o1, orgchart AS o2 WHERE o1.emp = :emp1 AND o2.emp = :emp2; 28
  • 70.
    Nested Set Model Deleting subtrees DELETE FROM orgchart WHERE lft BETWEEN (SELECT lft FROM orgchart WHERE emp = :start_node) AND (SELECT rgt FROM orgchart Filling gaps WHERE emp = :start_node); CREATE VIEW LftRgt (seq) AS SELECT lft FROM orgchart UNION ALL SELECT rgt FROM orgchart; UPDATE orgchart SET lft = (SELECT COUNT(*) FROM LftRgt WHERE seq <= lft), rgt = (SELECT COUNT(*) FROM LftRgt WHERE seq <= rgt) 29
  • 71.
    Nested Set Model Deleting a single node DELETE FROM orgchart WHERE emp = ‘C’; A C B D E F 30
  • 72.
    Nested Set Model Deleting a single node DELETE FROM orgchart WHERE emp = ‘C’; A B D E F 30
  • 73.
    Nested Set Model Deleting a single node CREATE PROCEDURE downsize(IN removed VARCHAR(10)) LANGUAGE SQL DETERMINISTIC UPDATE orgchart SET emp = CASE WHEN orgchart.emp = removed AND orgchart.lft + 1 = orgchart.rgt --leaf THEN ‘{vacant}’ WHEN orgchart.emp = removed AND orgchart.lft + 1 <> orgchart.rgt -- promote subordinate and vacate THEN (SELECT o1.emp FROM orgchart AS o1 WHERE orgchart.lft + 1 = o1.lft) WHEN orgchart.emp = (SELECT o1.emp FROM orgchart AS o1 WHERE orgchart.lft + 1 = o1.lft) THEN ‘{vacant}’ ELSE emp END; 31
  • 74.
    Nested Set Model Deleting a single node CREATE PROCEDURE downsize(IN removed VARCHAR(10)) LANGUAGE SQL DETERMINISTIC UPDATE orgchart SET emp = CASE WHEN orgchart.emp = removed AND orgchart.lft + 1 = orgchart.rgt --leaf THEN ‘{vacant}’ WHEN orgchart.emp = removed AND orgchart.lft + 1 <> orgchart.rgt -- promote subordinate and vacate THEN (SELECT o1.emp FROM orgchart AS o1 WHERE orgchart.lft + 1 = o1.lft) WHEN orgchart.emp = (SELECT o1.emp FROM orgchart AS o1 WHERE orgchart.lft + 1 = o1.lft) THEN ‘{vacant}’ ELSE emp END; 31
  • 75.
    Nested Set toAdjacency List SELECT B.id AS boss, P.emp, P.lft, P.rgt FROM orgchart as P LEFT OUTER JOIN emp AS B ON B.lft = (SELECT MAX(S.lft) FROM orgchart AS S WHERE P.lft > S.lft AND P.lft < S.rgt); boss emp lft rgt NULL Anthony 1 12 Anthony Beryl 2 3 Anthony Charles 4 11 Charles Denise 5 6 Charles Ellen 7 8 Charles Frank 9 10 32
  • 76.
    Frequent Insertion Trees Avoidoverhead (locking + updating) with larger spreads and bigger gaps emp lft rgt Anthony 100 1200 Beryl 200 300 Charles 400 1100 Denise 500 600 Ellen 700 800 Frank 900 1000 33
  • 77.
    Frequent Insertion Trees Avoidoverhead (locking + updating) with larger spreads and bigger gaps emp lft rgt Anthony 100 1200 Beryl 200 300 Charles 400 1100 Denise 500 600 Ellen 700 800 Frank 900 1000 Datatype of (lft, rgt)? - INTEGER (full range) - FLOAT / REAL / DOUBLE - NUMERIC(p,s) / DECIMAL(p,s) 33
  • 78.
    Frequent Insertion Trees Avoidoverhead (locking + updating) with larger spreads and bigger gaps emp lft rgt Anthony 100 1200 Beryl 200 300 Charles 400 1100 Denise 500 600 Ellen 700 800 Frank 900 1000 Datatype of (lft, rgt)? - INTEGER (full range) - FLOAT / REAL / DOUBLE - NUMERIC(p,s) / DECIMAL(p,s) 33
  • 79.
    Frequent Insertion Trees Avoidoverhead (locking + updating) with larger spreads and bigger gaps emp lft rgt Anthony 100 1200 Beryl 200 300 Charles 400 1100 Denise 500 600 Ellen 700 800 Frank 900 1000 Datatype of (lft, rgt)? - INTEGER (full range) - FLOAT / REAL / DOUBLE - NUMERIC(p,s) / DECIMAL(p,s) 33
  • 80.
    Frequent Insertion Trees Avoidoverhead (locking + updating) with larger spreads and bigger gaps emp lft rgt Anthony 100 1200 Beryl 200 300 Charles 400 1100 Denise 500 600 Ellen 700 800 Frank 900 1000 Datatype of (lft, rgt)? - INTEGER (full range) - FLOAT / REAL / DOUBLE - NUMERIC(p,s) / DECIMAL(p,s) 33
  • 81.
    Hybrid Models Adjacency List with Nested Sets (node, parent, lft, rgt) Nested Sets with depth Adjacency List with depth ... Denormalisation to save subselects or joins 34
  • 82.
  • 83.
    Nested Intervals Model Rational numbers (a/b, with a and b integers) ((p.lft <= c.lft) AND (c.rgt <= p.rgt)) 0/5 A 5/5 1/5 B 2/5 3/5 C 4/5 36
  • 84.
  • 85.
    Nested Intervals Model a b a+(b-a)/3 a+2(b-a)/3 37
  • 86.
    Nested Intervals Model Finding GCD (greatest common divisor) 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; 38
  • 87.
    Nested Intervals Model Binary Node (x, y) Fractions 39
  • 88.
    Nested Intervals Model Binary Node (x, y) Fractions First node (1, 1/2) 39
  • 89.
    Nested Intervals Model Binary Node (x, y) Fractions First node (1, 1/2) depth-first convergence point 39
  • 90.
    Nested Intervals Model Binary Node (x, y) Fractions First child of first node (1, 3/4) First node (1, 1/2) depth-first convergence point 39
  • 91.
    Nested Intervals Model Binary Node (x, y) Fractions First child of first node (1, 3/4) First node (1, 1/2) depth-first convergence point breadth-first convergence point 39
  • 92.
    Nested Intervals Model Binary Node (x, y) Fractions First child of first node (1, 3/4) First node (1, 1/2) depth-first convergence point breadth-first convergence point 39
  • 93.
    Nested Intervals Model Binary Node (x, y) Fractions First child of first node (1, 3/4) First node (1, 1/2) depth-first convergence point breadth-first convergence point 39
  • 94.
  • 95.
    Nested Intervals Model CREATE FUNCTION x_numer( IN numer INT, IN denom INT ) 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 red_den = ret_den/2; END WHILE; RETURN ret_num; -- ret_den -- for x_denom() END; 40
  • 96.
    Nested Intervals Model CREATEFUNCTION 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 red_den = ret_den/2; END WHILE; RETURN ret_num; -- ret_den for parent_denom() END; 41
  • 97.
    Nested Intervals Model Similarfunctions for: sibling_numer(), sibling_denom() child_numer(), child_denom() enumerated_path(), distance() path_numer(), path_denom() 42
  • 98.
    Nested Intervals Model Similarfunctions for: sibling_numer(), sibling_denom() child_numer(), child_denom() enumerated_path(), distance() path_numer(), path_denom() INSERT INTO orgchart (name, numer, denom) VALUES (‘Anthony’, path_numer(‘1’), path_denom(‘1’)), (‘Beryl’, path_numer(‘1.1’), path_denom(‘1.1’)), (‘Charles’, path_numer(‘1.2’), path_denom(‘1.2’)), (‘Denise’, path_numer(‘1.2.1’), path_denom(‘1.2.1’)); 42
  • 99.
    Nested Intervals Encodings Interval Halving average: (lft + rgt) / 2 43
  • 100.
    Nested Intervals Encodings Interval Halving average: (lft + rgt) / 2 Farey Fractions a/b and c/d neighbours => bc -ad = 1 mediant: (lft_num + rgt_num) (lft_den + rgt_den) 43
  • 101.
    Nested Intervals Encodings Continued Fractions 1.1.2.1 Reverse (or additive) Continued Fractions 44
  • 102.
  • 103.
    Oracle: CONNECT BYPRIOR Traversing the tree SELECT emp, boss FROM emp_orgchart START WITH boss IS NULL CONNECT BY [NOCYCLE] PRIOR emp = boss; emp boss A NULL B A G B C A D C E C F C 46
  • 104.
    Oracle: CONNECT BYPRIOR Traversing the tree SELECT emp, boss FROM emp_orgchart START WITH boss = ‘C’ IS NULL CONNECT BY [NOCYCLE] PRIOR emp = boss; emp boss D C E C F C 46
  • 105.
    Oracle: CONNECT BYPRIOR Traversing the tree SELECT emp, boss, salary, LEVEL AS lvl, LPAD(' ', 2*(LEVEL-1)) || emp AS tree, CONNECT_BY_IS_LEAF AS is_leaf FROM emp_orgchart CONNECT BY PRIOR emp = boss START WITH boss IS NULL ORDER SIBLINGS BY salary DESC; emp boss salary lvl tree is_leaf A NULL 1000.00 1 A 0 B A 900.00 2 B 0 G B 800.00 3 G 1 C A 900.00 2 C 0 D C 800.00 3 D 1 E C 700.00 3 E 1 F C 600.00 3 F 1 47
  • 106.
    Oracle: CONNECT BYPRIOR Determining the relationship between two nodes SELECT COUNT(*) AS ‘is_subordinate’ FROM emp_orgchart WHERE emp = :subordinate AND LEVEL > 1 START WITH emp = :superior CONNECT BY PRIOR emp = boss; 48
  • 107.
    Oracle: CONNECT BYPRIOR Determining the relationship between two nodes SELECT COUNT(*) AS ‘is_subordinate’ FROM emp_orgchart WHERE emp = :subordinate AND LEVEL > 1 START WITH emp = :superior CONNECT BY PRIOR emp = boss; A subordinate of C? 0 F subordinate of A? 1 48
  • 108.
    Oracle: CONNECT_BY_ROOT Determiningthe ancestor of a node SELECT emp_id, CONNECT_BY_ROOT emp_id AS root FROM orgchart START WITH boss = ‘A’ CONNECT BY PRIOR emp_id = boss; emp_id root B B G B C C D C E C F C 49
  • 109.
    Oracle: SYS_CONNECT_BY_PATH MaterializedPath View SELECT emp_id, SYS_CONNECT_BY_PATH (emp_id,'.') AS path_string FROM orgchart START WITH boss IS NULL CONNECT BY PRIOR emp_id = boss ORDER BY 2; emp_id path_string A .A B .A.B C .A.C D .A.C.D E .A.C.E F .A.C.F 50
  • 110.
  • 111.
    Common Table Expressions CREATETABLE emp_orgchart ( emp VARCHAR(10) PRIMARY KEY, boss VARCHAR(10) REFERENCES emp_orgchart(emp_id), salary TEXT ); INSERT INTO emp_orgchart (emp, boss, salary) VALUES (‘A’, NULL, 1000.00), (‘B’, ‘A’, 900.00), (‘C’, ‘A’, 900.00), A (‘D’, ‘C’, 800.00), (‘E’, ‘C’, 700.00), (‘F’, ‘C’, 600.00), B C (‘G’, ‘B’, 800.00); G D E F 52
  • 112.
    Common Table Expressions WITHRECURSIVE hierarchy AS ( -- non recursive term SELECT * FROM emp_orgchart WHERE boss IS NULL UNION ALL -- recursive term SELECT E1.* FROM emp_orgchart AS E1 JOIN hierarchy AS E2 ON E1.boss = E2.emp ) SELECT * FROM hierarchy ORDER BY emp; 53
  • 113.
    Common Table Expressions WITHRECURSIVE hierarchy AS ( -- non recursive term SELECT * FROM emp_orgchart WHERE boss IS NULL UNION ALL -- recursive term SELECT E1.* FROM emp_orgchart AS E1 JOIN hierarchy AS E2 ON E1.boss = E2.emp ) SELECT * FROM hierarchy ORDER BY emp; 53
  • 114.
    Common Table Expressions WITHRECURSIVE hierarchy AS ( -- non recursive term SELECT * FROM emp_orgchart WHERE boss IS NULL UNION ALL -- recursive term SELECT E1.* FROM emp_orgchart AS E1 JOIN hierarchy AS E2 ON E1.boss = E2.emp ) SELECT * FROM hierarchy ORDER BY emp; 53
  • 115.
    Common Table Expressions WITHRECURSIVE hierarchy AS ( -- non recursive term SELECT * FROM emp_orgchart WHERE boss IS NULL emp boss salary UNION ALL A NULL 1000.00 -- recursive term B A 900.00 SELECT E1.* C A 900.00 FROM emp_orgchart AS E1 D C 800.00 JOIN hierarchy AS E2 E C 700.00 ON E1.boss = E2.emp F C 600.00 ) SELECT * G B 800.00 FROM hierarchy ORDER BY emp; 53
  • 116.
    Common Table Expressions WITHRECURSIVE hierarchy AS ( SELECT *, 1 AS lvl, CAST(emp AS TEXT) AS tree, emp || ‘.’ AS path FROM emp_orgchart WHERE boss IS NULL UNION ALL SELECT E1.*, E2.lvl + 1 AS lvl, LPAD(E1.emp, lvl * 2, ‘ ’) AS tree, E2.path || E1.emp || ‘.’ AS path FROM emp_orgchart JOIN hierarchy AS E2 ON E1.boss = E2.emp ) SELECT * FROM hierarchy ORDER BY path; 54
  • 117.
    Common Table Expressions WITHRECURSIVE hierarchy AS ( SELECT *, 1 AS lvl, CAST(emp AS TEXT) AS tree, emp || ‘.’ AS path FROM emp_orgchart WHERE boss IS NULL UNION ALL SELECT E1.*, E2.lvl + 1 AS lvl, LPAD(E1.emp, lvl * 2, ‘ ’) AS tree, E2.path || E1.emp || ‘.’ AS path FROM emp_orgchart JOIN hierarchy AS E2 ON E1.boss = E2.emp ) SELECT * FROM hierarchy ORDER BY path; 54
  • 118.
    Common Table Expressions WITHRECURSIVE hierarchy AS ( SELECT *, 1 AS lvl, CAST(emp AS TEXT) AS tree, emp || ‘.’ AS path FROM emp_orgchart WHERE boss IS NULL UNION ALL SELECT E1.*, E2.lvl + 1 AS lvl, LPAD(E1.emp, lvl * 2, ‘ ’) AS tree, E2.path || E1.emp || ‘.’ AS path FROM emp_orgchart JOIN hierarchy AS E2 ON E1.boss = E2.emp ) SELECT * FROM hierarchy ORDER BY path; 54
  • 119.
    Common Table Expressions WITHRECURSIVE hierarchy AS ( SELECT *, 1 AS lvl, CAST(emp AS TEXT) AS tree, emp || ‘.’ AS path FROM emp_orgchart WHERE boss IS NULL UNION ALL SELECT E1.*, E2.lvl + 1 AS lvl, LPAD(E1.emp, lvl * 2, ‘ ’) AS tree, E2.path || E1.emp || ‘.’ AS path FROM emp_orgchart JOIN hierarchy AS E2 ON E1.boss = E2.emp ) SELECT * FROM hierarchy ORDER BY path; 54
  • 120.
    Common Table Expressions WITHRECURSIVE hierarchy AS ( SELECT *, 1 AS lvl, CAST(emp AS TEXT) AS tree, emp || ‘.’ AS path FROM emp_orgchart WHERE boss IS NULL UNION ALL SELECT E1.*, E2.lvl + 1 AS lvl, LPAD(E1.emp, lvl * 2, ‘ ’) AS tree, E2.path || E1.emp || ‘.’ AS path FROM emp_orgchart JOIN hierarchy AS E2 ON E1.boss = E2.emp ) SELECT * FROM hierarchy ORDER BY path; 54
  • 121.
    Common Table Expressions WITHRECURSIVE hierarchy AS ( SELECT *, 1 AS lvl, emp CAST(emp salary boss AS TEXT) AS tree, tree lvl path emp || ‘.’ AS path A NULL 1000.00 1 A A. FROM emp_orgchart WHERE boss IS NULL B A 900.00 2 B A.B. UNION ALL SELECT E1.*, G B 800.00 3 G A.B.G. E2.lvl + 1 AS lvl, C LPAD(E1.emp, lvl * 2, ‘ ’)CAS tree, A 900.00 2 A.C. E2.path || E1.emp || ‘.’ AS path D C 800.00 FROM emp_orgchart 3 D A.C.D. JOIN hierarchy AS E2 E C 700.00 3 E A.C.E. ON E1.boss = E2.emp ) F C 600.00 3 F A.C.F. SELECT * FROM hierarchy ORDER BY path; 54
  • 122.
    Common Table Expressions WITHRECURSIVE hierarchy AS ( SELECT *, 1 AS lvl, CAST(emp AS TEXT) AS tree FROM emp_orgchart WHERE boss = ‘A’ UNION ALL SELECT E1.*, E2.lvl + 1 AS lvl, LPAD(E1.emp, depth * 2, ‘ ’) AS tree FROM emp_orgchart JOIN hierarchy AS E2 ON E1.boss = E2.emp WHERE E2.lvl < 3 -- termination condition ) SELECT * FROM hierarchy ORDER BY path; 55
  • 123.
    Common Table Expressions WITHRECURSIVE hierarchy AS ( SELECT *, 1 AS lvl, CAST(emp AS TEXT) AS tree FROM emp_orgchart WHERE boss = ‘A’ UNION ALL SELECT E1.*, E2.lvl + 1 AS lvl, LPAD(E1.emp, depth * 2, ‘ ’) AS tree FROM emp_orgchart JOIN hierarchy AS E2 ON E1.boss = E2.emp ) SELECT *, COALESCE((SELECT 0 FROM emp_orgchart E3 WHERE hierarchy.emp = E3.boss FETCH FIRST ROW ONLY), 1) AS is_leaf FROM hierarchy; 56
  • 124.
  • 125.
  • 126.
  • 127.
    Resources Joe Celko, “Treesand Hierarchies in SQL for Smarties”, Morgan Kaufmann: http://www.amazon.com/dp/1558609202/ Vadim Tropashko, various articles and papers: http://www.dbazine.com/top-auth/top-auth-trop/ http://www.sigmod.org/sigmod/record/issues/ 0506/p47-article-tropashko.pdf http://arxiv.org/pdf/cs/0402051 59
  • 128.
    Thank you! Contact details: Lorenzo Alberton lorenzo@ibuildings.com http://www.alberton.info http://joind.in/talk/view/585