Joe Celko s SQL for Smarties - Advanced SQL Programming P67. In the SQL database community, Joe Celko is a well-known columnist and purveyor of valuable insights. In Joe Celko's SQL for Smarties: Advanced SQL Programming, he picks up where basic SQL training and experience leaves many database professionals and offers tips, techniques, and explanations that help readers extend their capabilities to top-tier SQL programming. Although Celko denies that the book is about database theory, he nevertheless alludes to theory often to buttress his practical points. This title is not for novices, as the author points out. Instead, its intended. | 632 CHAPTER 28 TREES AND HIERARCHIES IN SQL ---------- Figure ---------- Figure O Nested Set Model of Hierarchies 633 Computer science majors will recognize this as a modified preorder tree traversal algorithm. CREATE TABLE NestTree node CHAR 2 NOT NULL PRIMARY KEY 1ft INTEGER NOT NULL UNIQUE CHECK 1ft 0 rgt INTEGER NOT NULL UNIQUE CHECK rgt 1 CONSTRAINT order_okay CHECK 1ft rgt NestTree node lft rgt A 1 12 B 2 3 C 4 11 D 5 6 E 7 8 F 9 10 Another nice thing is that the name of each node appears once and only once in the table. The path enumeration and adjacency list models used lots of self-references to nodes which made updating more complex. The Counting Property The lft and rgt numbers have a definite meaning and carry information about the location and nature of each subtree. The root is always 1ft rgt 1 2 SELECT COUNT FROM TreeTable and leaf nodes always have 1ft 1 rgt . SELECT node AS root FROM NestTree WHERE 1ft 1 SELECT node AS leaf FROM NestTree WHERE 1ft rgt - 1 634 CHAPTER 28 TREES AND HIERARCHIES IN SQL Another very useful result of the counting property is that any node in the tree is the root of a subtree the leaf nodes are a degenerate case of size rgt - 1ft 1 2. The Containment Property In the nested set model table all the descendants of a node can be found by looking for the nodes with a rgt and lft number between the lft and rgt values of their parent node. For example to find out all the subordinates of each boss in the corporate hierarchy you would write SELECT is a boss of FROM NestTree AS Superiors NestTree AS Subordinates WHERE BETWEEN AND This would tell you that everyone is also his own boss so in some situations you would also add the predicate . AND This simple self-JOIN query is the basis for almost everything that follows in the nested set model. The containment property does not depend on the values
