COVID-19 Update: We are currently shipping orders daily. However, due to transit disruptions in some geographies, deliveries may be delayed. To provide all customers with timely access to content, we are offering 50% off Science and Technology Print & eBook bundle options. Terms & conditions.
Joe Celko's Trees and Hierarchies in SQL for Smarties - 2nd Edition - ISBN: 9780123877338, 9780123877567

Joe Celko's Trees and Hierarchies in SQL for Smarties

2nd Edition

Author: Joe Celko
eBook ISBN: 9780123877567
Paperback ISBN: 9780123877338
Imprint: Morgan Kaufmann
Published Date: 20th January 2012
Page Count: 296
Sales tax will be calculated at check-out Price includes VAT/GST
Price includes VAT/GST

Institutional Subscription

Secure Checkout

Personal information is secured with SSL technology.

Free Shipping

Free global shipping
No minimum order.

Table of Contents

Chapter 1 Graphs, Trees and Hierarchies

1.1 Basic Graph Theory

1.1.1 Terminology

1.1.2 Edges versus Nodes

1.1.3 Directed versus Undirected Graphs

1.2 Tree versus Hierarchies

1.2.1 Trees

1.2.2 Types of Trees

1.2.3 Hierarchies

1.2.4 Types of Hierarchies

Chapter 2 Adjacency List Model

2.1 The Simple Adjacency List Model

2.2 The Simple Adjacency List Model is not normalized.

2.2.1 UPDATE Anomalies

2.2.2 INSERT Anomalies

2.2.3 DELETE Anomalies

2.2.4 Structural Anomalies

2.3 Fixing the Adjacency List Model

2.3.1 Concerning the Use of NULLs

2.4 Navigation in Adjacency List Model

2.4.1 Cursors and Procedural Code

2.4.2 Self-joins

2.4. 3 Recursive CTEs

2.5 Inserting Nodes in the Adjacency List Model

2.6 Deleting Nodes in the Adjacency List Model

2.6.1 Deleting an Entire Subtree

2.6.2 Promoting a Subordinate after Deletion

2.6.3 Promoting an Entire Subtree after Deletion

2.7 Levels in an Adjacency List Model

2.7.1 Numbering the Levels

2.7.2 Aggregation in the Adjacency List Model

Chapter 3 Path Enumeration Models

3.1 Finding the Depth of the Tree

3.2 Searching for Subordinates

3.3 Searching for Superiors

3.4 Deleting a Subtree

3.5 Deleting a Single Node

3.6 Inserting a New Node

3.7 Splitting up a Path String

3.8 The Edge Enumeration Model

3.9 Transitive Closure Model

3.10 Converting Path Enumeration Model to Adjacency List

3.11 Converting Path Enumeration Model to Nested Sets Model

Chapter 4 Nested Set Model of Hierarchies

4.1 Finding Root and Leaf Nodes

4.2 Finding Subtrees

4.3 Finding Levels and Paths in a Tree

4.3.1 Finding the Height of a Tree

4.3.2 Finding Levels of Subordinates

4.3.3 Finding Oldest and Youngest Subordinates

4.3.4 Finding a Path

4.3.5 Finding Relative Position

4.4 Functions in the Nested Sets Model

4.5 Deleting Nodes and Subtrees

4.5.1 Deleting Subtrees

4.5.2 Deleting a Single Node

4.5.3 Pruning a Set of Nodes from a Tree

4.6. Closing Gaps in the Tree

4.7. Summary Functions on Trees

4.7.1 Iterative Parts Update

4.7.2 Recursive Parts Update

4.8 Inserting and Updating Trees

4.8.1 Moving a Subtree within a Tree

4.8.2 MoveSubtree () Second Version

4.8.3 Subtree Duplication

4.8.4 Swapping Siblings

4.8.5 Inserting New Subordinates

4.9 Converting Nested Sets Model to Adjacency List

4.10 Converting Adjacency List to Nested Sets Model

4.11 Separation of Edges and Nodes

4.11.1 Multiple Structures

4.11.2 Multiple Nodes

4.12 Comparing Nodes and Structure

Chapter 5 Frequent Insertion Trees

5.1 The Data Typeof (lft, rgt)

5.1.1 Exploiting the Full Range of Integers


5.1.3 NUMERIC(p,s) or DECIMAL(p,s) Numbers

5.2 Computing the Spread to Use

5.2.1 Varying the Spread

5.2.2 Divisor Parameter

5.2.3 Divisor via Formula

5.2.4 Divisor via Table Lookup

5.2.5 Partial Reorganization

5.2.6 Rightward Spread Growth

5.3 Total Reorganization

5.3.1 Reorganization with Lookup Table

5.3.2 Reorganization with Recursion

5.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 Number

5.4.4 Calculating the Enumerated Path and Distance between Nodes

5.4.5 Building a Hierarchy

5.4.6 Depth-first Enumeration by Left Interval Boundary

5.4.7 Depth-first enumeration by Right Interval boundary

5.4.8 All Descendants of a Node

Chapter 6 The Linear Version of the Nested Sets model

6.1 Insertion and Deletion

6.2 Finding Paths

6.3 Finding Levels

6.4 Summary

Chapter 7 Binary Trees

7.1 Binary Tree Traversals

7.2 Binary Tree Queries

7.2.1 Find Parent of a Node

7.2.2 Find Subtree at a Node

7.3 Deletion from a Binary Tree

7.4 Insertion into a Binary Tree

7.5 Heaps

7.6 Binary Tree Representation of Multiway Trees

7.7 The Stern-Brocot Numbers

Chapter 8 Other Models for Trees

8.1 Adjacency List with Self-References

8.2 Subordinate Adjacency List

8.3 Hybrid Models

8.3.1. Adjacency and Nested Set Model

8.3.2. Nested Set with Depth Model

8.3.3. Adjacency and Depth Model

8.3.4. Computed Hybrid Models

Chapter 9 Proprietary Extensions for Trees

9.1 Oracle Tree Extensions

9.2 DB2 and the WITH Operator

9.3 Date's EXPLODE Operator

9.4 Tillquist and Kuo's Proposals

9.5 Microsoft Extensions

9.6 Other Methods

Chapter 10 Hierarchies in Data Modelling

10.1 Types of Hierarchies

10.2 DDL Constraints

10.2.1 Uniqueness Constraints

10.2.2 Disjoint Hierarchies

10.2.3 Representing 1:1, 1:m, and n:m Relationships

Chapter 11 Hierarchical Encoding Schemes

11.1 ZIP codes

11.2 Dewey Decimal Classification

11.3 Strength and Weaknesses

11.4 Shop Categories

11.5 Statistical Tools for Decision Trees

Chapter 12. General Graphs (NEW)

12.1 Types of Graphs

12.1.1. Complete Graph

12.1.2. Sparse and Dense Graphs

12.1.3. Complete Graph

12.1.4. Wheel Graph

12.1.5. Interval Graph

12.1.6. Cycle Graph

12.1.7. Planar Graph

12.2. Detecting paths in a convergent Graph

12.3. Detecting directed cycles

12.4. Find the Shortest Route

12.4.1. Stepwise Procedures - Dijkstra's algorithm 12.4.2. Set-based Procedures

12.5. Transport Networks

12.5.1. Maximum and Minimum Flow

12.5.2. Edges with Values

12.6. Hamiltonian Paths and Circuits

12.7. Matching problems: Ramsey Numbers

12.8. Planar Graphs and coloring

12.8.1. Three Houses and Three Utilities Problem

Chapter 13. Petri Nets (NEW)

13.1. History and uses

13.2. A bit of Theory

13.3. Traffic Light Problem

Chapter 14 State Transition Graphs (NEW)

14.1. Constraints for Valid Transitions

14.2. Table of Valid Transitions

14.3. Temporal Delays and Sequence in Transitions

14.4. PERT and the Critical Path Method (CPM)

14.7.1. History

14.7.2. Software

Chapter 15.Hierarchical Database Systems (IMS)

15.1 Types of Databases

15.2 Database History

15.2.1. DL/I

15.2.2 Control Blocks

15.2.3 Data Communications

15.2.4 Application Programs

15.2.5 Hierarchical Databases

15.2.6 Strengths and Weaknesses

15.3 Sample Hierarchical Database

15.3.1 Department Database

15.3.2 Student Database

15.3.3 Design Considerations

15.3.4 Example Database Expanded

15.3.5 Data Relationships

15.3.6 Hierarchical Sequence

15.3.7 Hierarchical Data Paths

15.3.8 Database Records

15.3.9 Segment Format

15.3.10 Segment Definitions

15.4 Summary


The demand for SQL information and training continues to grow with the need for a database behind every website capable of offering web-based information queries. SQL is the de facto standard for database retrieval, and if you need to access, update, or utilize data in a modern database management system, you will need SQL to do it. The Second Edition of Joe Celko's Trees and Hierarchies in SQL for Smarties covers two new sets of extensions over three entirely new chapters and expounds upon the changes that have occurred in SQL standards since the previous edition's publication. Benefit from mastering the challenging aspects of these database applications in SQL as taught by Joe Celko, one of the most-read SQL authors in the world.

Key Features

  • Expert advice from a noted SQL authority and award-winning columnist who has given 10 years of service to the ANSI SQL standards committee
  • Teaches scores of advanced techniques that can be used with any product, in any SQL environment
  • Offers graph theory and programming techniques for working around deficiencies and gives insight into real-world challenges


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


No. of pages:
© Morgan Kaufmann 2012
20th January 2012
Morgan Kaufmann
eBook ISBN:
Paperback ISBN:

Ratings and Reviews

About the Author

Joe Celko

Joe Celko

Joe Celko served 10 years on ANSI/ISO SQL Standards Committee and contributed to the SQL-89 and SQL-92 Standards.

Mr. Celko is author a series of books on SQL and RDBMS for Elsevier/MKP. He is an independent consultant based in Austin, Texas.

He has written over 1200 columns in the computer trade and academic press, mostly dealing with data and databases.

Affiliations and Expertise

Independent Consultant, Austin, Texas