Get child parent pairs from nested sets

user_7361329 0
Viewed 65

I have the following nested table:

CREATE TABLE personal2 (
    emp VARCHAR(20) PRIMARY KEY,
    salary DECIMAL(6,2) NOT NULL,
    lft INTEGER NOT NULL UNIQUE CHECK (lft > 0),
    rgt INTEGER NOT NULL UNIQUE CHECK (rgt > 1)
    );
    
    ALTER TABLE personal2 ADD CONSTRAINT orderOKAY
    CHECK (lft < rgt);
    
    INSERT INTO personal2 VALUES('Albert', 1000, 1, 16);
    INSERT INTO personal2 VALUES('Bert', 900, 2, 3);
    INSERT INTO personal2 VALUES('Chuck', 900, 6, 15);
    INSERT INTO personal2 VALUES('Donna', 800, 9, 10);
    INSERT INTO personal2 VALUES('Eddie', 700, 11, 12);
    INSERT INTO personal2 VALUES('Fred', 600, 13, 14);
    INSERT INTO personal2 VALUES('Gilbert', 900, 4, 5);
    INSERT INTO personal2 VALUES('Hans', 850, 7, 8);

Now I am supposed to get the pairs of child and their parents, which apparently should work like this and indeed gives the correct result:

SELECT a.emp, b.emp
FROM personal2 a, personal2 b
WHERE (SELECT COUNT(*)
FROM personal2 c WHERE a.lft BETWEEN c.lft and c.rgt
AND c.lft Between b.lft AND b.rgt) = 2;

I am not able to understand this query completely and I also don't get why this works. So apparently I am creating the cartesian product of the table in the beginning. And now I am selecting specific rows from it, which are defined in the subquery. But I don't understand what happens there and why this makes me leaving with child-parent pairs. Can somebody explain this to me?

oracle sql
2 Answers

As you say, this is an example of a "nested set" ( see https://en.wikipedia.org/wiki/Nested_set_model ), however there is one error: for Donna lft should be 9, not 8, since for Hans rgt = 8.

In this model the child's range should be completely included in the ranges of all his ancestors. For example, Albert contains Chuck who contains Hans and three others.

You are accessing the same rows three times as A, B and C.

  • WHERE a.lft BETWEEN c.lft and c.rgt is looking for rows where A is contained by C (including when the A row is the same as the C row);
  • AND c.lft Between b.lft AND b.rgt is looking for rows where C is contained in B (including when B and C are the same);
  • So the result is the number of rows than contain A and are contained by B, including A and B. This number will be 2 if A is an immediate child of B, and it will be greater if there is an intermediate row between A and B in the hierarchy.
user_63307970

Stew Ashton already explained how the query works. In effect, each entity (person) is associated with a closed interval on the number line - a subset of the integers (or of the real numbers), and a person A is an ancestor of another person B if the set associated with A contains the set associated with B.

In this arrangement, the provider of the data must make sure that the sets satisfy some constraints (which do not automatically follow from the obvious constraint you already included for your table). Namely, for two distinct persons A and B, it must always be the case that either their sets (their intervals) are disjoint, or that one of the sets strictly contains the other "at both ends" (meaning that both endpoints of the smaller interval are strictly inside the larger interval).

As Stew explained, the query checks that one interval is contained in the other, and - for a fixed pair of intervals - it counts how many are between the two. If the answer is zero, then neither person is an ancestor to the other. If the answer is exactly 1, then the two persons are the same. If it's exactly 2, then one person is the immediate ancestor ("parent") of the other.

One point of clarification: person A is an ancestor to person B if A.lft < B.lft and A.rgt > B.rgt. The query you have only checks that A.lft between B.lft and B.rgt. Why is that enough? Answer: because we assume that the input data is "correct" - any two intervals are either disjoint, or one contains the other. If we didn't know that ahead of time, the conditions in the query wouldn't suffice.

So - that's what the query does. Let me point out, however, that the query is quite inefficient - it does too much work. The standard way to convert from nested sets to adjacency list (the "child, parent" representation of the hierarchy) is as I show below. Note also that the output contains a row for the "root" (the query you have doesn't); it is generally an important "best practice" to include a root row in a hierarchy.

select t1.emp as child, 
       min(t2.emp) keep (dense_rank first order by t2.rgt) as parent
from   personal2 t1 left outer join personal2 t2 
                    on t1.lft > t2.lft and t1.rgt < t2.rgt
group  by t1.emp
;

CHILD                PARENT              
-------------------- --------------------
Albert                                   
Bert                 Albert              
Chuck                Albert              
Donna                Chuck               
Eddie                Chuck               
Fred                 Chuck               
Gilbert              Albert              
Hans                 Chuck

I used your inputs, except lft for Donna is 9 (Stew explained why in his answer).

In this very small example, the optimizer estimates a cost of 9 for this query, vs. 17 for the one you posted. I believe for larger datasets the difference will be significantly bigger.

Admin1
Related