Joe Celko's Trees and Hierarchies in SQL for Smarties


  • Joe Celko, Independent Consultant, Austin, Texas
  • Joe Celko, Independent Consultant, Austin, Texas

Joe Celko's Trees and Hierarchies in SQL is an intermediate to advanced-level practitioner’s guide to mastering the two most challenging aspects of developing database applications in SQL. In this book, Celko illustrates several major approaches to representing trees and hierarchies and related topics that should be of interest to the working database programmer. These topics include hierarchical encoding schemes, graphs, IMS, binary trees, and more. This book covers SQL-92 and SQL:1999.
View full description


database application developers (from enterprise-level application builders to small business developers)


Book information

  • Published: May 2004
  • ISBN: 978-1-55860-920-4


"I want to say clearly that I think the subject of this proposed book is one for which there will be considerable demand...the topic is poorly understood in general and a good book on the subject will be helpful to the SQL community at large. This book should be of great interest to real-world application programmers...I think that this book would be used on a day-to-day basis (rather than languish on a shelf until some special problem arose)." -Jim Melton, author of SQL:1999.

Table of Contents

1 Graphs, Trees and Hierarchies1.1 Modeling a Graph in a Program1.1.1 Adjacency Lists for Graphs1.1.2 Adjacency Arrays for Graphs1.1.3 Finding a path in a General Graphs in SQL1.2 Defining Tree and Hierarchies1.2.1 Trees1.2.2 Properties of Hierarchies1.2.3 Types of Hierarchies1.3 Note on Recursion2 Adjacency List Model2.1 The Simple Adjacency List Model2.2 The Simple Adjacency List Model is not normalized. 2.2.1 UPDATE Anomalies2.2.2 INSERT Anomalies2.2.3 DELETE Anomalies2.2.4 Structural Anomalies2.3 Fixing the Adjacency List Model2.3.1 Concerning the Use of NULLs2.4 Navigation in Adjacency List Model 2.4.1 Cursors and Procedural Code2.4.2 Self-joins2.5 Inserting Nodes in the Adjacency List Model2.6 Deleting Nodes in the Adjacency List Model2.6.1 Deleting an Entire Subtree2.6.2 Promoting a Subordinate after Deletion 2.6.3 Promoting an Entire Subtree after Deletion 2.7 Leveled Adjacency List Model2.7.1 Numbering the levels2.7.2 Aggregation in the Hierarchy3 Path Enumeration Models3.1 Finding the Depth of the Tree3.2 Searching for Subordinates3.3 Searching for Superiors3.4 Deleting a Subtree3.5 Deleting a Single Node3.6 Inserting a New Node3.7 Splitting up a Path String3.8 The Edge Enumeration Model3.9 XPath and XML 4 Nested Set Model of Hierarchies4.1 Finding Root and Leaf Nodes4.2 Finding Subtrees4.3 Finding Levels and Paths in a Tree4.3.1 Finding the Height of a Tree4.3.2 Finding Levels of Subordinates4.3.3 Finding Oldest and Youngest Subordinates4.3.4 Finding a Path4.3.5 Finding Relative Position 4.4 Functions in the Nested Sets Model4.5 Deleting Nodes and Subtrees4.5.1 Deleting Subtrees4.5.2 Deleting a Single Node4.5.3 Pruning a Set of Nodes from a Tree4.6. Closing Gaps in the Tree4.7. Summary Functions on Trees4.7.1 Iterative Parts Update4.7.2 Recursive Parts Update4.8 Inserting and Updating Trees4.8.1 Moving a Subtree within a Tree4.8.2 MoveSubtree Second Version4.8.3 Subtree Duplication4.8.4 Swapping Siblings4.9 Converting Nested Sets Model to Adjacency List4.10 Converting Adjacency List to Nested Sets Model 4.11 Separation of Edges and Nodes4.11.1 Multiple Structures4.11.2 Multiple Nodes4.12 Comparing Nodes and Structure5 Frequent Insertion Trees5.1 The Datatype of (lft, rgt)5.1.1 Exploiting the Full Range of Integers5.1.2 FLOAT, REAL or DOUBLE PRECISION Numbers5.1.3 NUMERIC(p,s) or DECIMAL(p,s) Numbers5.2 Computing the Spread to Use5.2.1 Varying the Spread5.2.2 Divisor Parameter5.2.3 Divisor via Formula5.2.4 Divisor via Table Lookup5.2.5 Partial Reorganization 5.2.6 Rightward Spread Growth5.3 Total Reorganization5.3.1 Reorganization with Lookup Table5.3.2 Reorganization with Recursion5.4 Rational Numbers and Nested Intervals model 5.4.1 Partial Order mappings 5.4.2 Summation of Coordinates 5.4.3 Finding Parent Encoding and Sibling Number5.4.4 Calculating the Enumerated Path and Distance between Nodes5.4.5 Building a Hierarchy 5.4.6 Depth-first Enumeration by Left Interval Boundary5.4.7 Depth-first enumeration by Right Interval boundary5.4.8 All Descendants of a Node6 The Linear Version of the Nested Sets model6.1 Insertion and Deletion6.2 Finding Paths6.3 Finding Levels6.4 Summary7 Binary Trees7.1 Binary Tree Traversals 7.2 Binary Tree Queries7.2.1 Find Parent of a Node7.2.2 Find Subtree at a Node7.3 Deletion from a Binary Tree 7.4 Insertion into a Binary Tree 7.5 Heaps 7.6 Binary Tree Representation of Multiway Trees7.7 The Stern-Brocot Numbers8 Other Models for Trees8.1 Adjacency List with Self-References8.2 Subordinate Adjacency List 8.3 Hybrid Models8.3.1. Adjacency and Nested Set Model8.3.2. Nested Set with Depth Model8.3.3. Adjacency and Depth Model8.3.4. Computed Hybrid Models8.4 General Graphs8.4.1 Detecting Paths in a Convergent Graph 8.4.2 Detecting Directed Cycles 9 Proprietary Extensions for Trees9.1 Oracle Tree Extensions9.2 XDB Tree Extension9.3 DB2 and the WITH Operator9.4 Date's EXPLODE Operator9.5 Tillquist and Kuo's Proposals9.6 Microsoft Extensions9.7 Other Methods10 Hierarchies in Data Modeling10.1 Types of Hierarchies10.2 DDL Constraints10.2.1 Uniqueness Constraints10.2.2 Disjoint Hierarchies10.2.3 Representing 1:1, 1:m, and n:m Relationships11 Hierarchical Encoding Schemes11.1 ZIP codes11.2 Dewey Decimal Classification11.3 Strength and Weaknesses11.4 Shop Categories11.5 Statistical Tools for Decision Trees12 Hierarchical Database Systems (IMS)12.1 Types of Databases12.2 Database History12.2.1. DL/I12.2.2 Control Blocks12.2.3 Data Communications12.2.4 Application Programs12.2.5 Hierarchical Databases12.2.6 Strengths and Weaknesses12.3 Sample Hierarchical Database12.3.1 Department Database12.3.2 Student Database12.3.3 Design Considerations12.3.4 Example Database Expanded12.3.5 Data Relationships12.3.6 Hierarchical Sequence12.3.7 Hierarchical Data Paths12.3.8 Database Records12.3.9 Segment Format12.3.10 Segment Definitions12.4 Summary