Joe Celko

Joe Celko's Trees and Hierarchies in SQL for Smarties

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.

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

Paperback, 296 Pages

Published: January 2012

Imprint: Morgan Kaufmann

ISBN: 978-0-12-387733-8

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

    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

Advertisement

advert image