From: JH
To: Editor
Date: 04 Oct 2004
Joe Celko has often hyped using nested sets to represent
trees in a SQL DBMS. My introduction to Celko and nested sets was his post to a
mailing list on this subject in 2001, and the idea intrigued me. There was just one problem. His examples did not work!
On the chance that I could have been using a worse-than-usual
SQL implementation, I tried everything I could get my hands on, yet the results
were the same. Celko goofed! Somebody that was an alleged expert had
published something that was completely wrong.
Not just a single post, but every single article on this subject for at
least six years. Duplicated in
everything from magazines to his book, SQL FOR SMARTIES.
I set out trying to understand how nested sets work. It took some time, but I eventually figured
it out and sent him the message included below.
I've been playing around with the nested set model for a
little while, thanks to your articles. However, I think I've found an error that has been duplicated in all instances of the article and the message(s) posted to the Postgres mailing list.
1. An employee and all their Supervisors, no matter how deep
the tree.
SELECT P2.*
FROM Personnel AS P1, Personnel AS P2
WHERE P1.lft BETWEEN P2.lft AND P2.rgt
AND P1.emp = :myemployee;
2. The employee and all subordinates. There is a nice
symmetry here.
SELECT P2.*
FROM Personnel AS P1, Personnel AS P2
WHERE P1.lft BETWEEN P2.lft AND P2.rgt
AND P2.emp = :myemployee;
I've tried this on Postgres, Oracle 9i, and mySQL, and get
the same results for the second query:
trees=# SELECT p2.* from personnel as p1, personnel as p2 where
p1.lft
between p2.lft and p2.rgt and p2.emp = 'Albert';
emp | lft | rgt
------------+-----+-----
Albert |
1 | 12
Albert |
1 | 12
Albert |
1 | 12
Albert |
1 | 12
Albert |
1 | 12
Albert |
1 | 12
It should be a select from p1.* and not p2.*, which is also a
bit more symmetrical. The results for selecting from p1 instead of p2:
trees=# SELECT p1.* from personnel as p1, personnel as p2 where
p1.lft
between p2.lft and p2.rgt and p2.emp = 'Albert';
emp | lft | rgt
------------+-----+-----
Albert |
1 | 12
Bert |
2 | 3
Chuck |
4 | 11
Donna |
5 | 6
Eddie |
7 | 8
Fred |
9 | 10
His response was brief.
"Shit. You're right."
From: Fabian Pascal
To: JH
Too bad you did not check with me first. There is absolutely
nothing that will persuade me to consider anything that has to do with
Celko. 100% waste of time.
Posted: 11/05/04
