A tree is a special kind of directional graph. Graphs are data structures consisting of nodes connected by arcs. Each arc shows unidirectional communication between two nodes. In an organization chart, nodes are employees, and each arc describes subordinations. In the list of materials, the nodes are modules (ultimately shown down to individual parts), and arcs describe the relationship "made of".
The top of the tree is called the root. In the organization chart, this is the biggest boss; in the list of materials, this is the assembled part. A binary tree is a tree in which a node can have no more than two descendants; In general, an n-dimensional tree is one in which a node can have no more than n nodes of descendants.
Tree nodes that do not have subtrees are called leaves. In the list of materials, these are the minimum parts into which the part can be disassembled. The descendants, or children, of the parent node are all nodes in the subtree that has the parent node rooted.
Trees are often depicted as diagrams. (See Figure 1) Another way to represent trees is to show them as nested sets (see Figure 2); This is the basis for my SQL representation of trees as nested sets.
In SQL, any relationship is explicitly described by the data. A typical way to represent trees is to place an adjacency matrix in a table. That is, one column is the parent node, and the other column in the same row is the child node (the pair is an arc in the graph). For example, consider an organizational chart of a company with six employees:
CREATE TABLE Personnel( emp CHAR(20) PRIMARY KEY, boss CHAR(20) REFERENCES Personnel(emp), salary DECIMAL(6,2) NOT NULL ); Personnel: emp boss salary ========================== 'Jerry' NULL 1000.00 'Bert' 'Jerry' 900.00 'Chuck' 'Jerry' 900.00 'Donna' 'Chuck' 800.00 'Eddie' 'Chuck' 700.00 'Fred' 'Chuck' 600.00
This model has advantages and disadvantages. The PRIMARY KEY is emp, but the boss column is functionally dependent on it, hence we have problems with normalization. REFERENCES will not give you the opportunity to indicate to the boss who is not an employee. However, what happens when 'Jerry' changes the name to 'Geraldo' to get a TV talk show? You should also make cascading changes to the 'Bert' and 'Chuck' lines.
Another disadvantage of this model is that it is difficult to deduce the path. To find the boss name for each employee, use a self-connecting query, such as:
SELECT B1.emp, 'bosses', E1.emp FROM Personnel AS B1, Personnel AS E1 WHERE B1.emp = E1.boss;
But something is missing here. This request only gives you immediate supervisors. Your boss's boss also has power over you, and so on up the tree. To display two levels in the tree, you need to write a more complex self-association query, such as:
SELECT B1.emp, 'bosses', E2.emp FROM Personnel AS B1, Personnel AS E1, Personnel AS E2 WHERE B1.emp = E1.boss AND E1.emp = E2.boss;
To go more than two levels deeper in the tree, simply expand the sample:
SELECT B1.emp, 'bosses', E3.emp FROM Personnel AS B1, Personnel AS E1, Personnel AS E2, Personnel AS E3 WHERE B1.emp = E1.boss AND E1.emp = E2.boss AND E2.emp = E3.boss;
Unfortunately, you have no idea how deep the tree is, so you should keep expanding this query until you end up with an empty set.
The leaves have no descendants. In this model, they are fairly easy to find: These are employees who are not the boss of anyone else in the company:
SELECT * FROM Personnel AS E1 WHERE NOT EXISTS( SELECT * FROM Personnel AS E2 WHERE E1.emp = E2.boss);
At the root of the boss tree is NULL:
SELECT * FROM Personnel WHERE boss IS NULL;
Real problems arise when you try to calculate values up and down the tree. As an exercise, write a query summarizing the salary of each employee and his/her subordinates; result:
Total Salaries emp boss salary ========================== 'Jerry' NULL 4900.00 'Bert' 'Jerry' 900.00 'Chuck' 'Jerry' 3000.00 'Donna' 'Chuck' 800.00 'Eddie' 'Chuck' 700.00 'Fred' 'Chuck' 600.00
Multiple tree model.
Another way to represent trees is to show them as nested sets. This is a more suitable model, because .SQL is a language focused on sets. The root of a tree is a set containing all other sets, and the ancestor-child relationship is described by the belonging of the set of descendants to the set of ancestors.
There are several ways to convert an organization chart to nested sets. One way is to imagine that you are moving subordinate "ovals" inside their parents, using the edge lines as ropes. The root is the largest oval and contains all the other nodes. The leaves are the innermost ovals, containing nothing inside, and the nesting corresponds to hierarchical relationships. This is a natural representation of the "list of materials" model, because the final block is made physically from nested components, and is disassembled into separate parts.
Another approach is to imagine a small worm crawling along the "nodes and arcs" of a tree. The worm starts from above, with the root, and makes a complete trip around the tree.
But now let's imagine a stronger worm with a counter that starts with one. When the worm arrives at the node, it places a number in the cell on the side it visited and increments the counter. Each node will receive two numbers, one for the right side and one for the left side.
This produces predictable results that you can use to generate queries. The Personnel table looks like this, with left and right numbers in the form:
CREATE TABLE Personnel( emp CHAR(10) PRIMARY KEY, salary DECIMAL(6,2) NOT NULL, left INTEGER NOT NULL, right INTEGER NOT NULL); Personnel emp salary left right ============================== 'Jerry' 1000.00 1 12 'Bert' 900.00 2 3 'Chuck' 900.00 4 11 'Donna' 800.00 5 6 'Eddie' 700.00 7 8 'Fred' 600.00 9 10
The root always has 1 in the left column and twice the number of nodes (2*n) in the right column. It's easy to understand: the worm must visit each node twice, once on the left side and once on the right side, so the final number must be twice the number of nodes in the entire tree.
In the nested sets model, the difference between left and right leaf values is always 1. Imagine a worm turning around a leaf as it crawls across the tree. Therefore, you can find all the leaves by the following simple query:
SELECT * FROM Personnel WHERE (right - left) = 1;
You can use this trick to speed up queries: build a unique index on the left column, then rewrite the query to take advantage of the index:
SELECT * FROM Personnel WHERE left = (right - 1);
The reason for the performance gain is that SQL can use the index on the left column when it is not corrupted in the expression. Do not use (left - right) = 1, because it allows you to take advantage of the index.
In the nested-multiplier model, paths are shown as nested sets, which are represented by nested set numbers and BETWEEN predicates. For example, to identify all the bosses of a particular employee, you need to write:
SELECT :myworker, B1.emp, (right - left) AS height FROM Personnel AS B1, Personnel AS E1 WHERE E1.left BETWEEN B1.left AND B1.right AND E1.right BETWEEN B1.left AND B1.right AND E1.emp = :myworker;
The higher the height, the further down the hierarchy the boss is from the employee. The nested sets model uses the fact that each containing other sets is larger in size (where size = (right - left)) than the sets it contains. Obviously, the root will always have the largest size.
The level, the number of arcs between two given nodes, is fairly simple to calculate. For example, to find the levels between a given worker and a manager, you could use:
SELECT E1.emp, B1.emp, COUNT(*) - 1 AS levels FROM Personnel AS B1, Personnel AS E1 WHERE E1.left BETWEEN B1.left AND B1.right AND E1.right BETWEEN B1.left AND B1.right AND E1.node = :myworker AND B1.node = :mymanager;
(COUNT(*) - 1) is used to remove a node's double index directly as being at another level, because a node is zero levels removed from itself.
You can build other queries from this template. For example, to find the common bosses of two employees, combine paths and find nodes that have (COUNT(*) > 1). To find the closest common ancestors of the two nodes, combine paths, find nodes that have (COUNT(*) > 1), and select with the lowest depth.
|The top of the tree is called the root. Tree nodes that do not have subtrees are called leaves. The descendants of the parent node are the nodes in the subdents that have the root parent node.|
|Another way to represent trees is to show them as nested sets. This is a more suitable model, because .SQL is a language focused on sets. The root of a tree is a set containing all other sets, and the ancestor-child relationship is described by the belonging of the set of descendants to the set of ancestors.|
I assume you have a March 1996 article in front of you, so I won't repeat myself. The multiple tree model has some properties that I didn't mention last month. But first, let's create a table (see Listing 1) to store personnel information. I will refer to this table everywhere in the rest of this article.
The tree in Figure 1 is represented as A) a graph and B) nested sets. The direction is shown by attachment, that is, you know that someone is a subordinate of someone else in the hierarchy of the company, if that left and right numbers of the set of this person - between those of their bosses.
Another property that I didn't mention last time is that descendants are ordered, i.e. you can use the numbers of the elements of the set to arrange the descendants. This property is absent in the model of the adjacency matrix, which has no ordering among descendants. You can use this fact when inserting, updating, or deleting nodes in the tree.
One of the properties of a tree is that it is a graph without loops. That is, no path closes to catch you in an endless loop when you follow them in a tree. Another property is that there is always a path from the root to any other node in the tree. In the nested sets model, paths are shown as nested sets, which are represented by set numbers and BETWEEN predicates. For example, to find out all the managers to whom the worker should report, you can write:
SELECT 'Mary', P1.emp, (P1.rgt - P1.lft) AS size FROM Personnel AS P1, Personnel AS P2 WHERE P2.emp = 'Mary' AND P2.lft BETWEEN P1.lft AND P1.rgt; Mary emp size ==== === ==== Mary Albert 27 Mary Charles 13 Mary Fred 9 Mary Jim 5 Mary Mary 1
Note that when size = 1, you are dealing with Mary as her own boss. You can rule out this case.
The nested set model uses the fact that each set has a larger size (size = right - left) than the sets it contains. Obviously, the root will always have the largest size. JOIN and ORDER BY are not needed in nested sets models like adjacency graph models. Plus, the results do not depend on the order in which the rows are displayed.
Node level - The number of arcs between the node and the root. You can calculate the node level with the following query:
SELECT P2.emp, COUNT(*) AS level FROM Personnel AS P1, Personnel AS P2 WHERE P2.lft BETWEEN P1.lft AS P2 GROUP BY P2.emp;
This query finds levels among managers, as follows:
emp level === ===== Albert 1 Bert 2 Charles 2 Diane 2 Edward 3 Fred 3 George 3 Heidi 3 Igor 4 Jim 4 Kathy 4 Larry 4 Mary 5 Ned 5
In some books on graph theory, the root has a zero level instead of the first. If you like this agreement, use the expression "(COUNT(*)-1)".
Self-association in combination with the predicate BETWEEN is the main template for other queries.
Aggregate functions in trees.
Getting a simple amount of salary to the manager's subordinates works on the same principle. Note that this total amount will also include the boss's salary:
SELECT P1.emp, SUM(P2.salary) AS payroll FROM Personnel AS P1, Personnel AS P2 WHERE P2.lft BETWEEN P1.lft AND P1.rgt GROUP BY P1.emp; emp payroll === ======= Albert 7800.00 Bert 1650.00 Charles 3250.00 Diane 1900.00 Edward 750.00 Fred 1600.00 George 750.00 Heidi 1000.00 Igor 500.00 Jim 300.00 Kathy 100.00 Larry 100.00 Mary 100.00 Ned 100.00
The next request will take a fired employee as a parameter and delete the subtree below him/her. The catch in this query is that you are using a key, but you have to make the left and right values work. The answer is a set of scalar subqueries:
DELETE FROM Personnel WHERE lft BETWEEN (SELECT lft FROM Personnel WHERE emp = :downsized) AND (SELECT rgt FROM Personnel WHERE emp = :downsized);
The problem is that after this query, there are gaps in the sequence of numbers of sets. This does not prevent most tree queries from being made because the attachment property is preserved. This means that you can use the BETWEEN predicate in your queries, but other operations that depend on the density of numbers will not work in the tree at intervals. For example, you will not be able to find leaves using the predicate (right-left=1), and you will not be able to find the number of nodes in a subtree using the left and right values of its root.
Unfortunately, you have lost information that will be very useful in closing those gaps - namely the correct and left numbers of the root of the subtree. Therefore, forget the request, and write instead the procedure:
CREATE PROCEDURE DropTree (downsized IN CHAR(10) NOT NULL) BEGIN ATOMIC DECLARE dropemp CHAR(10) NOT NULL; DECLARE droplft INTEGER NOT NULL; DECLARE droprgt INTEGER NOT NULL; SELECT emp, lft, rgt INTO dropemp, droplft, droprgt FROM Personnel WHERE emp = downsized; DELETE FROM Personnel WHERE lft BETWEEN droplft and droprgt; UPDATE Personnel SET lft = CASE WHEN lft > droplf THEN lft - (droprgt - droplft + 1) ELSE lft END, rgt = CASE WHEN rgt > droplft THEN rgt - (droprgt - droplft + 1) ELSE rgt END;END;
The actual procedure should have error handling, but I leave it as an exercise for the reader.
Delete p a single node
Removing a single node in the middle of a tree is harder than removing full subtrees. When you remove a node in the middle of a tree, you have to decide how to fill the hole. There are two ways. The first method k elevates one of the children to the position of the original node (suppose the father dies and the eldest son takes over the business, as shown in Figure 2). The oldest child is always shown as the leftmost child node under the parent. However, there is a problem with this operation. If the older child has children of his own, you have to decide how to handle them, and so on down the tree until you get to the leaf.
The second method for removing a single node in the middle of the tree is to connect the descendants to the ancestor of the original node (you can say that the mom dies and the children are accepted by the grandmother), as shown in Figure 3. This is obtained automatically in the nested sets model, you just delete the node and its children are already contained in the nodes of its ancestor. However, you have to be careful when closing the gap left by erasing. There is a difference in changing the numbering of the descendants of the remote node and changing the numbering of the nodes on the right. Below is a procedure that does this:
CREATE PROCEDURE DropNode (downsized IN CHAR(10) NOT NULL) BEGIN ATOMIC DECLARE dropemp CHAR(10) NOT NULL; DECLARE droplft INTEGER NOT NULL; DECLARE droprgt INTEGER NOT NULL; SELECT emp, lft, rgt INTO dropemp, droplft, droprgt FROM Personnel WHERE emp = downsized; DELETE FROM Personnel WHERE emp = downsized; UPDATE Personnel SET lft = CASE WHEN lft BETWEEN droplft AND droprgt THEN lft - 1 WHEN lft > droprgt THEN lft - 2 ELSE lft END rgt = CASE WHEN rgt BETWEEN droplft AND droprgt THEN rgt - 1 WHEN rgt > droprgt THEN rgt -2 ELSE rgt END; WHERE lft > droplft; END;
Листинг 1 CREATE TABLE Personnel (emp CHAR(10) PRIMARY KEY, salary DECIMAL(8,2) NOT NULL CHECK(salary > = 0.00), lft INTEGER NOT NULL, rgt INTEGER NOT NULL, CHECK(lft < rgt)); INSERT INTO Personnel VALUES ('Albert', 1000.00, 1, 28); INSERT INTO Personnel VALUES ('Bert', 900.00, 2, 5); INSERT INTO Personnel VALUES ('Charles', 900.00, 6, 19); INSERT INTO Personnel VALUES ('Diane', 900.00, 20, 27); INSERT INTO Personnel VALUES ('Edward', 750.00, 3, 4); INSERT INTO Personnel VALUES ('Fred', 800.00, 7, 16); INSERT INTO Personnel VALUES ('George', 750.00, 17, 18); INSERT INTO Personnel VALUES ('Heidi', 800.00, 21, 26); INSERT INTO Personnel VALUES ('Igor', 500.00, 8, 9); INSERT INTO Personnel VALUES ('Jim', 100.00, 10, 15); INSERT INTO Personnel VALUES ('Kathy', 100.00, 22, 23); INSERT INTO Personnel VALUES ('Larry', 100.00, 24, 25); INSERT INTO Personnel VALUES ('Mary', 100.00, 11, 12); INSERT INTO Personnel VALUES ('Ned', 100.00, 13, 14);
Removing a single node in the middle of a tree is harder than removing full subtrees. When you remove a node in the middle of a tree, you have to decide how to fill the hole. There are two ways. The first method k raises one of the children to the position of the original node (suppose the father dies and the oldest son takes over the business. The oldest descendant is always shown as the far-left child node under the parent.
The second method for removing a single node in the middle of the tree is to connect the offspring to the ancestor of the original node (you can say that mommy dies and the children are accepted by the grandmother).
People ask me why I don't show more procedural code in the examples. Right now, ANSI and ISO are trying to negotiate a standard procedural language for triggers and stored procedures called SQL/PSM. However, this standard has not yet been approved, which means that I have to use either my own pseudo-code or choose one manufacturer. I've decided to use English comments for now, but I'll start using SQL/PSM when it's complete.
The trickiest part of tree processing in SQL is finding a way to convert the adjacency matrix model into a nested set model within a pure SQL structure. It would be fairly simple to load the adjacency matrix table into the program, and then use the recursive tree transformation program from the college textbook to build a model of nested sets.
Honestly, such a tree transform could be faster than what I'm going to show you. But I want to do it in pure SQL to prove the following: You can do in a declarative language what you can do in a procedural language. Since this is an instructional exercise, I will explain in painful detail.
The classic approach to solving a problem is to take the simplest case of the problem, and see if you can apply it to more complex cases. If the tree has no nodes, then the transformation is simple - do nothing. If the tree has one node, then the conversion is simple - set the left value to 1 and the right value to 2. The nature of the adjacency matrix is such that you can only move one level at a time, so let's look at a tree with two levels – the root and immediate descendants. The adjacency model table would resemble the following:
CREATE TABLE Personnel (emp CHAR(10) NOT NULL PRIMARY KEY, boss CHAR(10)); Personnel emp boss ================= 'Albert' NULL 'Bert' 'Albert' 'Charles' 'Albert' 'Diane' 'Albert'
Let's put the nested set model in its own worksheet:
CREATE TABLE WorkingTree( emp CHAR (10), boss CHAR(10), lft INTEGER NOT NULL DEFAULT 0, rgt INTEGER NOT NULL DEFAULT 0);
From the previous paragraphs of this article, you know that the root of the tree has a left value of 1, and that the right value is twice the number of nodes in the tree. In a worksheet, let the boss column always contain the root key value of the original tree. In reality, this will be the name of the nested set:
INSERT INTO WorkingTree --convert the root node SELECT P0.boss, P0.boss, 1, 2 * (SELECT COUNT(*) + 1 FROM Personnel AS P1 WHERE P0.boss = P1.boss) FROM Personnel AS P0;
Now, you have to add descendants to the nested sets table. The original boss will remain the same. The order of descendants is the natural order of the key; in this case, emp char(10):
INSERT INTO WorkingTree --convert the children SELECT DISTINCT P0.emp, P0.boss, 2 * (SELECT COUNT(DISTINCT emp) FROM Personnel AS P1 WHERE P1.emp < P0.emp AND P0.boss IN (P1.emp, P1.boss)), 2 * (SELECT COUNT(DISTINCT emp) FROM Personnel AS P1 WHERE P1.emp < P0.emp AND P0.boss IN (P1.boss, P1.emp)) + 1 FROM Personnel AS P0;
In fact, you can use this procedure to convert an adjacency matrix model into a forest of trees, each of which is a nested set model identified by its root value. Thus, the Albert family tree is a set of rows that have Albert as an ancestor, a Bert family tree is a set of rows that have Bert as an ancestor, and so on. (This concept is illustrated in Figures 1 and 2.
Because the original adjacency matrix table replicates leaf nodes, non-root nodes, in the emp and boss columns, the WorkingTree table duplicates nodes as the root in one tree and as a child in another. The query will also behave strangely with a null value in the boss column of the original table of the adjacency matrix, so you will have to clear the WorkingTree table with the following query:
DELETE FROM WorkingTree WHERE boss IS NULL OR emp IS NULL;
To make these trees merge into one final tree, you need a way to attach the subordinate tree to its ancestor. In procedural language, you could accomplish this with a program that would do the following steps:
- Find the size of the slave tree.
- Find the place where the subordinate tree is inserted into the ancestor tree.
- Push the ancestor tree apart at the insertion point.
- Insert the slave tree at the insertion point.
In non-procedural language, you would perform these steps together, using the logic of all the points listed. You begin this process by asking questions and noting the facts:
Q)How do you choose an ancestor tree and its subordinate tree in the forest?
A) Looking for a single key value that is a descendant in the ancestor tree and the root of the subordinate tree;
Q)How to determine how much to expand the ancestor tree?
A)This is the size of the slave tree equal to (2 * (select count(*) from Subordinate)).
Q)How do I determine the insertion point?
A)This is a row in the ancestor table where the emp value is equal to the boss value in the slave table. You want to place the slave tree to the left left of that shared node. Small algebraic calculations give you a number appended to all left and right values to the right of the insertion point.
The easiest way to explain this is with the help of the table of relations shown in Table 1.
TRANSLATOR'S NOTE: I don't know what he meant about the simplest way of explanation, but I didn't understand a damn thing in this table :)))) If you understand everything, then explain to me, pls, by letter :)))
You're ready to write a procedure that combines two trees:
CREATE PROCEDURE TreeMerge(superior NOT NULL, subordinate NOT NULL) BEGIN DECLARE size INTEGER NOT NULL; DECLARE insert_point INTEGER NOT NULL; SET size = 2 * (SELECT COUNT(*) FROM WorkingTree WHERE emp = subordinate); SET insert_point = ( SELECT MIN(lft) FROM WorkingTree WHERE emp = subordinate AND boss = superior) - 1; UPDATE WorkingTree SET boss = CASE WHEN boss = subordinate THEN CASE WHEN emp = subordinate THEN NULL ELSE superior END ELSE boss END, lft = CASE WHEN (boss = superior AND lft > size) THEN lft + size ELSE CASE WHEN boss = subordinate AND emp <> subordinate THEN lft + insert_point ELSE lft END END, rgt = CASE WHEN (boss = superior AND rgt > size) THEN rgt + size ELSE CASE WHEN boss = subordinate AND emp <> subordinate THEN rgt + insert_point ELSE rgt END END WHERE boss IN (superior, subordinate);
--Remove redundant copies of the child tree root
DELETE FROM WorkingTree WHERE boss IS NULL OR emp IS NULL; END;
It is very easy to detect pairs of external and subordinate trees in a WorkingTree table. The following query becomes empty when all bosses are set to the same value:
CREATE VIEW AllPairs (superior, subordinate) AS SELECT W1.boss, W1.emp FROM WorkingTree AS W1 WHERE EXISTS( SELECT * FROM WorkingTree AS W2 WHERE W2.boss = W1.emp) AND W1.boss <> W1.emp;
But you would like to get only one pair that you will transfer to the newly developed procedure. To move one pair, take the leftmost pair from the previous query:
CREATE VIEW LeftmostPairs(superior, subordinate) AS SELECT DISTINCT superior, (SELECT MIN(subordinate) FROM AllPairs AS A2 WHERE A1.superior = A2.superior) FROM AllPairs AS A1 WHERE superior = (SELECT MIN(superior) FROM AllPairs);
Now all you have to do is put this request into a previously developed procedure – and you will have a procedure that will merge together a forest of trees from left to right. Using a WHILE loop that monitors the presence of values in LeftmostPairs, make procedure calls. This is the only procedural structure in the entire stored procedure.
Table 1 Resource requirements by component
|C1||row in superior||y||y||y||y||n||y||n|
|C2||row in subord||n||n||n||n||y||y||n|
|C3||lft > cut||n||n||y||y||-||-||-|
|C4||rgt > cut||n||y||n||y||-||-||-|
|A2||lft := lft + size||1|
|A3||rgt := rgt + size||1||2|
|A4||lft := lft||1||2||1|
|A5||rgt := rgt||2||2|
|A6||lft := lft + cut||1|
|A7||rgt := rgt + cut||2|