Joe Celko's Trees and Hierarchies in SQL for Smarties

Joe Celko's Trees and Hierarchies in SQL for Smarties

1st Edition - May 7, 2004

Write a review

  • Authors: Joe Celko, Joe Celko
  • eBook ISBN: 9780080491691

Purchase options

Purchase options
DRM-free (Mobi, EPub, PDF)
Sales tax will be calculated at check-out

Institutional Subscription

Free Global Shipping
No minimum order

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.

Key Features

· Includes graph theory and programming techniques.
· Running examples throughout the book help illustrate and tie concepts together.
· Loads of code, available for download from www.mkp.com.

Readership

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

Table of Contents

  • 1 Graphs, Trees and Hierarchies
    1.1 Modeling a Graph in a Program
    1.1.1 Adjacency Lists for Graphs
    1.1.2 Adjacency Arrays for Graphs
    1.1.3 Finding a path in a General Graphs in SQL
    1.2 Defining Tree and Hierarchies
    1.2.1 Trees
    1.2.2 Properties of Hierarchies
    1.2.3 Types of Hierarchies
    1.3 Note on Recursion

    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.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 Leveled Adjacency List Model
    2.7.1 Numbering the levels
    2.7.2 Aggregation in the Hierarchy

    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 XPath and XML

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

    5 Frequent Insertion Trees
    5.1 The Datatype of (lft, rgt)
    5.1.1 Exploiting the Full Range of Integers
    5.1.2 FLOAT, REAL or DOUBLE PRECISION Numbers
    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

    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

    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

    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
    8.4 General Graphs
    8.4.1 Detecting Paths in a Convergent Graph
    8.4.2 Detecting Directed Cycles

    9 Proprietary Extensions for Trees
    9.1 Oracle Tree Extensions
    9.2 XDB Tree Extension
    9.3 DB2 and the WITH Operator
    9.4 Date's EXPLODE Operator
    9.5 Tillquist and Kuo's Proposals
    9.6 Microsoft Extensions
    9.7 Other Methods

    10 Hierarchies in Data Modeling
    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

    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


    12 Hierarchical Database Systems (IMS)
    12.1 Types of Databases
    12.2 Database History
    12.2.1. DL/I
    12.2.2 Control Blocks
    12.2.3 Data Communications
    12.2.4 Application Programs
    12.2.5 Hierarchical Databases
    12.2.6 Strengths and Weaknesses
    12.3 Sample Hierarchical Database
    12.3.1 Department Database
    12.3.2 Student Database
    12.3.3 Design Considerations
    12.3.4 Example Database Expanded
    12.3.5 Data Relationships
    12.3.6 Hierarchical Sequence
    12.3.7 Hierarchical Data Paths
    12.3.8 Database Records
    12.3.9 Segment Format
    12.3.10 Segment Definitions
    12.4 Summary

Product details

  • No. of pages: 240
  • Language: English
  • Copyright: © Morgan Kaufmann 2004
  • Published: May 7, 2004
  • Imprint: Morgan Kaufmann
  • eBook ISBN: 9780080491691

About the Authors

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

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

Ratings and Reviews

Write a review

There are currently no reviews for "Joe Celko's Trees and Hierarchies in SQL for Smarties"