You are previewing Joe Celko’s Trees and Hierarchies in SQL for Smarties.
O'Reilly logo
Joe Celko’s Trees and Hierarchies in SQL for Smarties

Book Description

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.

Table of Contents

  1. Cover
  2. Title Page
  3. Dediction
  4. Copyright
  5. Contents
  6. Introduction
  7. Chapter 1: Graphs, Trees, and Hierarchies
    1. 1.1 Modeling a Graph in a Program
      1. 1.1.1 Adjacency Lists for Graphs
      2. 1.1.2 Adjacency Arrays for Graphs
      3. 1.1.3 Finding a Path in General Graphs in SQL
    2. 1.2 Defining Trees and Hierarchies
      1. 1.2.1 Trees
      2. 1.2.2 Properties of Hierarchies
      3. 1.2.3 Types of Hierarchies
    3. 1.3 Note on Recursion
  8. Chapter 2: Adjacency List Model
    1. 2.1 The Simple Adjacency List Model
    2. 2.2 The Simple Adjacency List Model Is Not Normalized
      1. 2.2.1 UPDATE Anomalies
      2. 2.2.2 INSERT Anomalies
      3. 2.2.3 DELETE Anomalies
      4. 2.2.4 Structural Anomalies
    3. 2.3 Fixing the Adjacency List Model
      1. 2.3.1 Concerning the Use of NULLs
    4. 2.4 Navigation in Adjacency List Model
      1. 2.4.1 Cursors and Procedural Code
      2. 2.4.2 Self-joins
    5. 2.5 Inserting Nodes in the Adjacency List Model
    6. 2.6 Deleting Nodes in the Adjacency List Model
      1. 2.6.1 Deleting an Entire Subtree
      2. 2.6.2 Promoting a Subordinate after Deletion
      3. 2.6.3 Promoting an Entire Subtree after Deletion
    7. 2.7 Leveled Adjacency List Model
      1. 2.7.1 Numbering the Levels
      2. 2.7.2 Aggregation in the Hierarchy
  9. Chapter 3: Path Enumeration Models
    1. 3.1 Finding the Depth of the Tree
    2. 3.2 Searching for Subordinates
    3. 3.3 Searching for Superiors
    4. 3.4 Deleting a Subtree
    5. 3.5 Deleting a Single Node
    6. 3.6 Inserting a New Node
    7. 3.7 Splitting up a Path String
    8. 3.8 The Edge Enumeration Model
    9. 3.9 XPath and XML
  10. Chapter 4: Nested Set Model of Hierarchies
    1. 4.1 Finding Root and Leaf Nodes
    2. 4.2 Finding Subtrees
    3. 4.3 Finding Levels and Paths in a Tree
      1. 4.3.1 Finding the Height of a Tree
      2. 4.3.2 Finding Levels of Subordinates
      3. 4.3.3 Finding Oldest and Youngest Subordinates
      4. 4.3.4 Finding a Path
      5. 4.3.5 Finding Relative Position
    4. 4.4 Functions in the Nested Sets Model
    5. 4.5 Deleting Nodes and Subtrees
      1. 4.5.1 Deleting Subtrees
      2. 4.5.2 Deleting a Single Node
      3. 4.5.3 Pruning a Set of Nodes from a Tree
    6. 4.6 Closing Gaps in the Tree
    7. 4.7 Summary Functions on Trees
      1. 4.7.1 Iterative Parts Update
      2. 4.7.2 Recursive Parts Update
    8. 4.8 Inserting and Updating Trees
      1. 4.8.1 Moving a Subtree within a Tree
      2. 4.8.2 MoveSubtree, Second Version
      3. 4.8.3 Subtree Duplication
      4. 4.8.4 Swapping Siblings
    9. 4.9 Converting Nested Sets Model to Adjacency List
    10. 4.10 Converting Adjacency List to Nested Sets Model
    11. 4.11 Separation of Edges and Nodes
      1. 4.11.1 Multiple Structures
      2. 4.11.2 Multiple Nodes
    12. 4.12 Comparing Nodes and Structure
    13. 4.13 Nested Sets Code in Other Languages
  11. Chapter 5: Frequent Insertion Trees
    1. 5.1 The Datatype of (lft, rgt)
      1. 5.1.1 Exploiting the Full Range of Integers
      2. 5.1.2 FLOAT, REAL, or DOUBLE PRECISION Numbers
      3. 5.1.3 NUMERIC(p,s) or DECIMAL(p,s) Numbers
    2. 5.2 Computing the Spread to Use
      1. 5.2.1 Varying the Spread
      2. 5.2.2 Divisor Parameter
      3. 5.2.3 Divisor via Formula
      4. 5.2.4 Divisor via Table Lookup
      5. 5.2.5 Partial Reorganization
      6. 5.2.6 Rightward Spread Growth
    3. 5.3 Total Reorganization
      1. 5.3.1 Reorganization with Lookup Table
      2. 5.3.2 Reorganization with Recursion
    4. 5.4 Rational Numbers and Nested Intervals Model
      1. 5.4.1 Partial Order Mappings
      2. 5.4.2 Summation of Coordinates
      3. 5.4.3 Finding Parent Encoding and Sibling Number
      4. 5.4.4 Calculating the Enumerated Path and Distance between Nodes
      5. 5.4.5 Building a Hierarchy
      6. 5.4.6 Depth-first Enumeration by Left Interval Boundary
      7. 5.4.7 Depth-first Enumeration by Right Interval Boundary
      8. 5.4.8 All Descendants of a Node
  12. Chapter 6: The Linear Version of the Nested Sets Model
    1. 6.1 Insertion and Deletion
    2. 6.2 Finding Paths
    3. 6.3 Finding Levels
    4. 6.4 Summary
  13. Chapter 7: Binary Trees
    1. 7.1 Binary Tree Traversals
    2. 7.2 Binary Tree Queries
    3. 7.2.1 Find Parent of a Node
    4. 7.2.2 Find Subtree at a Node
    5. 7.3 Deletion from a Binary Tree
    6. 7.4 Insertion into a Binary Tree
    7. 7.5 Heaps
    8. 7.6 Binary Tree Representation of Multiway Trees
    9. 7.7 The Stern-Brocot Numbers
  14. Chapter 8: Other Models for Trees
    1. 8.1 Adjacency List with Self-references
    2. 8.2 Subordinate Adjacency List
    3. 8.3 Hybrid Models
      1. 8.3.1 Adjacency and Nested Sets Model
      2. 8.3.2 Nested Set with Depth Model
      3. 8.3.3 Adjacency and Depth Model
      4. 8.3.4 Computed Hybrid Models
    4. 8.4 General Graphs
      1. 8.4.1 Detecting Paths in a Convergent Graph
      2. 8.4.2 Detecting Directed Cycles
  15. Chapter 9: Proprietary Extensions for Trees
    1. 9.1 Oracle Tree Extensions
    2. 9.2 XDB Tree Extension
    3. 9.3 DB2 and the WITH Operator
    4. 9.4 Date's EXPLODE Operator
    5. 9.5 Tillquist and Kuo's Proposals
    6. 9.6 Microsoft Extensions
    7. 9.7 Other Methods
  16. Chapter 10: Hierarchies in Data Modeling
    1. 10.1 Types of Hierarchies
    2. 10.2 DDL Constraints
      1. 10.2.1 Uniqueness Constraints
      2. 10.2.2 Disjoint Hierarchies
      3. 10.2.3 Representing 1:1, 1:m, and n:m Relationships
  17. Chapter 11: Hierarchical Encoding Schemes
    1. 11.1 ZIP codes
    2. 11.2 Dewey Decimal Classification
    3. 11.3 Strength and Weaknesses
    4. 11.4 Shop Categories
    5. 11.5 Statistical Tools for Decision Trees
  18. Chapter 12: Hierarchical Database Systems (IMS)
    1. 12.1 Types of Databases
    2. 12.2 Database History
      1. 12.2.1 DL/I
      2. 12.2.2 Control Blocks
      3. 12.2.3 Data Communications
      4. 12.2.4 Application Programs
      5. 12.2.5 Hierarchical Databases
      6. 12.2.6 Strengths and Weaknesses
    3. 12.3 Sample Hierarchical Database
      1. 12.3.1 Departmental Database
      2. 12.3.2 Student Database
      3. 12.3.3 Design Considerations
      4. 12.3.4 Example Database Expanded
      5. 12.3.5 Data Relationships
      6. 12.3.6 Hierarchical Sequence
      7. 12.3.7 Hierarchical Data Paths
      8. 12.3.8 Database Records
      9. 12.3.9 Segment Format
      10. 12.3.10 Segment Definitions
    4. 12.4 Summary
  19. Appendix: Readings and Resources
  20. Index
  21. About the Author
  22. Instructions for online access