JOE CELKO'S TREES AND HIERARCHIES IN SQL FOR SMARTIES
To order this title, and for more information, click here
By Joe Celko, Independent Consultant & Columnist for Intelligent Enterprise, USA
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.
Audience
database application developers (from enterprise-level application builders to small business developers)
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
Books and book related electronic products are priced in US dollars (USD), euro (EUR), and Great Britain Pounds (GBP). USD prices apply to the Americas and Asia Pacific. EUR prices apply in Europe and the Middle East. GBP prices apply to the UK and all other countries.
Home | Elsevier Sites | Privacy Policy | Terms and Conditions | Feedback | Site Map | A Reed Elsevier Company