Re: Nearest Common Ancestor Report (XDb1's $1000 Challenge)

From: --CELKO-- <jcelko212_at_earthlink.net>
Date: 17 May 2004 10:35:58 -0700
Message-ID: <18c7b3c2.0405170935.1259f2c9@posting.google.com>

>> $1000 to the first person who replicates the equivalent of
www.xdb1.com/Example/Ex076.asp using the relational model. To claim the prize, one needs to produce the equivalent Nearest Common Ancestor Report from normalized and NULL-less data and the solution must be as generic, meaning allow the user to create any hierarchy, consisting of different types of things (each type to allow different attributes) and each thing in the hierarchy to have any number of parents. Report generation must not be more than 2X slower than XDb1 on equivalent hardware. <<

Here is the link on Amazon.com for my new book on "Trees & Hierarchies in SQL"

http://www.amazon.com/exec/obidos/tg/detail/-/1558609202/qid=1080772873/sr=1-1/ref=sr_1_1/102-7683601-6345721?v=glance&s=books#product-details.

Another way of representing trees is to show them as nested sets. Since SQL is a set oriented language, this is a better model than the usual adjacency list approach you see in most text books. Let us define a simple OrgChart table like this.

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

I can add some more constraints to handle overlap, etc. in full SQL-92, but let me skip those for this newsgroup posting.

The organizational chart would look like this as a directed graph:

            Albert (1,12)
            /        \
           /          \
    Bert (2,3)    Chuck (4,11)
                   /    |   \
                 /      |     \
               /        |       \
             /          |         \
        Donna (5,6) Eddie (7,8) Fred (9,10)

OrgChart 
emp         lft rgt 
======================
'Albert'      1   12 
'Bert'        2    3 
'Chuck'       4   11 
'Donna'       5    6 
'Eddie'       7    8 
'Fred'        9   10

The nodes will be in a separate table, referenced from the tree structure by a FOREIGN KEY having the DRI actions needed for the particular business rules.

This model has some predictable results that we can use for building queries. The root is always (left = 1, right = 2 * (SELECT COUNT(*) FROM TreeTable)); leaf nodes always have (left + 1 = right); subtrees are defined by the BETWEEN predicate; etc. Here are two common queries which can be used to build others:

An employee and all their Supervisors, no matter how deep the tree.

SELECT O2.*
FROM OrgChart AS O1, OrgChart AS O2
WHERE O1.lft BETWEEN O2.lft AND O2.rgt AND O1.emp = :myemployee;

2. The employee and all subordinates. There is a nice symmetry here.

SELECT O1.*
FROM OrgChart AS O1, OrgChart AS O2
WHERE O1.lft BETWEEN O2.lft AND O2.rgt AND O2.emp = :myemployee;

3. Add a GROUP BY and aggregate functions to these basic queries and you have hierarchical reports. For example, the total salaries which each employee controls:

SELECT O2.emp, SUM(S1.salary)

FROM OrgChart AS O1, OrgChart AS O2,

        Salaries AS S1
  WHERE O1.lft BETWEEN O2.lft AND O2.rgt     AND O1.emp = S1.emp
  GROUP BY O2.emp;

4. To find the level of each emp, so you can print the tree as an indented listing. Technically, you should declare a cursor to go with the ORDER BY clause.

SELECT COUNT(O2.emp) AS indentation, O1.emp    FROM OrgChart AS O1, OrgChart AS O2
  WHERE O1.lft BETWEEN O2.lft AND O2.rgt   GROUP BY O1.lft, O1.emp
  ORDER BY O1.lft;

5. To convert a nested sets model into an adjacency list model:

SELECT B.emp AS boss, E.emp
FROM OrgChart AS E

       LEFT OUTER JOIN
       OrgChart AS B
       ON B.lft
          = (SELECT MAX(lft)
               FROM OrgChart AS S
              WHERE E.lft > S.lft
                AND E.lft < S.rgt);

6. Given two employees, find all their common supervisors:

SELECT DISTINCT S1.emp
FROM OrgChart AS E1,

       OrgChart AS E2,
       OrgChart AS S1
WHERE E1.emp = :my_emp_1
  AND E2.emp = :my_emp_2

AND E1.lft BETWEEN S1.lft AND S1.rgt
AND E2.lft BETWEEN S1.lft AND S1.rgt;

This is just a version of the usual nesting predicates (1) and (2).

7. Given two employees, find their nearest common supervisor,

WITH (SELECT S1.emp, (S1.rgt - S1.lft)

        FROM OrgChart AS E1, 
             OrgChart AS E2,
             OrgChart AS S1
      WHERE E1.emp = :my_emp_1
        AND E2.emp = :my_emp_2
        AND E1.lft BETWEEN S1.lft AND S1.rgt
        AND E2.lft BETWEEN S1.lft AND S1.rgt)
       AS S0 (emp, gap)

SELECT S0.emp
FROM S0
WHERE S0.gap

(SELECT MIN(gap) FROM S0);

The WITH clause is part of SQL-99 which you could replace with a VIEW or derived tables. The gap is the "diameter" of the containing set, and we are looking for the smallest such set. Here is the solution in pure SQL-92
SELECT S0.emp
FROM (SELECT S1.emp, (S1.rgt - S1.lft)

        FROM OrgChart AS E1, 
             OrgChart AS E2,
             OrgChart AS S1
      WHERE E1.emp = @my_emp_1
        AND E2.emp = @my_emp_2
        AND E1.lft BETWEEN S1.lft AND S1.rgt
        AND E2.lft BETWEEN S1.lft AND S1.rgt) AS S0(emp, gap)
 WHERE S0.gap 
       =(SELECT MIN (S1.rgt - S1.lft) 
        FROM OrgChart AS E1, 
             OrgChart AS E2,
             OrgChart AS S1
      WHERE E1.emp = @my_emp_1
        AND E2.emp = @my_emp_2
        AND E1.lft BETWEEN S1.lft AND S1.rgt
        AND E2.lft BETWEEN S1.lft AND S1.rgt);

What was not given in the specs is how to handle two identical employees; my solution is to say that they are their own nearest supervisor. Received on Mon May 17 2004 - 12:35:58 CDT