book

Joe Celko's Trees and Hierarchies in SQL for Smarties

Name: Joe Celko's Trees and Hierarchies in SQL for Smarties
Author: Joe Celko
ISBN: 9780080491691

by Joe Celko

June 2004

Intermediate to advanced

240 pages

4h 39m

English

Morgan Kaufmann

Read now

Unlock full access

Cover
Title Page
Dediction
Copyright
Contents
Introduction
Chapter 1: Graphs, Trees, and Hierarchies
1.1 Modeling a Graph in a Program1.1.1 Adjacency Lists for Graphs1.1.2 Adjacency Arrays for Graphs1.1.3 Finding a Path in General Graphs in SQL1.2 Defining Trees and Hierarchies1.2.1 Trees1.2.2 Properties of Hierarchies1.2.3 Types of Hierarchies1.3 Note on Recursion
Chapter 2: Adjacency List Model
2.1 The Simple Adjacency List Model2.2 The Simple Adjacency List Model Is Not Normalized2.2.1 UPDATE Anomalies2.2.2 INSERT Anomalies2.2.3 DELETE Anomalies2.2.4 Structural Anomalies2.3 Fixing the Adjacency List Model2.3.1 Concerning the Use of NULLs2.4 Navigation in Adjacency List Model2.4.1 Cursors and Procedural Code2.4.2 Self-joins2.5 Inserting Nodes in the Adjacency List Model2.6 Deleting Nodes in the Adjacency List Model2.6.1 Deleting an Entire Subtree2.6.2 Promoting a Subordinate after Deletion2.6.3 Promoting an Entire Subtree after Deletion2.7 Leveled Adjacency List Model2.7.1 Numbering the Levels2.7.2 Aggregation in the Hierarchy
Chapter 3: Path Enumeration Models
3.1 Finding the Depth of the Tree3.2 Searching for Subordinates3.3 Searching for Superiors3.4 Deleting a Subtree3.5 Deleting a Single Node3.6 Inserting a New Node3.7 Splitting up a Path String3.8 The Edge Enumeration Model3.9 XPath and XML
Chapter 4: Nested Set Model of Hierarchies
4.1 Finding Root and Leaf Nodes4.2 Finding Subtrees4.3 Finding Levels and Paths in a Tree4.3.1 Finding the Height of a Tree4.3.2 Finding Levels of Subordinates4.3.3 Finding Oldest and Youngest Subordinates4.3.4 Finding a Path4.3.5 Finding Relative Position4.4 Functions in the Nested Sets Model4.5 Deleting Nodes and Subtrees4.5.1 Deleting Subtrees4.5.2 Deleting a Single Node4.5.3 Pruning a Set of Nodes from a Tree4.6 Closing Gaps in the Tree4.7 Summary Functions on Trees4.7.1 Iterative Parts Update4.7.2 Recursive Parts Update4.8 Inserting and Updating Trees4.8.1 Moving a Subtree within a Tree4.8.2 MoveSubtree, Second Version4.8.3 Subtree Duplication4.8.4 Swapping Siblings4.9 Converting Nested Sets Model to Adjacency List4.10 Converting Adjacency List to Nested Sets Model4.11 Separation of Edges and Nodes4.11.1 Multiple Structures4.11.2 Multiple Nodes4.12 Comparing Nodes and Structure4.13 Nested Sets Code in Other Languages

Chapter 5: Frequent Insertion Trees
5.1 The Datatype of (lft, rgt)5.1.1 Exploiting the Full Range of Integers5.1.2 FLOAT, REAL, or DOUBLE PRECISION Numbers5.1.3 NUMERIC(p,s) or DECIMAL(p,s) Numbers5.2 Computing the Spread to Use5.2.1 Varying the Spread5.2.2 Divisor Parameter5.2.3 Divisor via Formula5.2.4 Divisor via Table Lookup5.2.5 Partial Reorganization5.2.6 Rightward Spread Growth5.3 Total Reorganization5.3.1 Reorganization with Lookup Table5.3.2 Reorganization with Recursion5.4 Rational Numbers and Nested Intervals Model5.4.1 Partial Order Mappings5.4.2 Summation of Coordinates5.4.3 Finding Parent Encoding and Sibling Number5.4.4 Calculating the Enumerated Path and Distance between Nodes5.4.5 Building a Hierarchy5.4.6 Depth-first Enumeration by Left Interval Boundary5.4.7 Depth-first Enumeration by Right Interval Boundary5.4.8 All Descendants of a Node
Chapter 6: The Linear Version of the Nested Sets Model
6.1 Insertion and Deletion6.2 Finding Paths6.3 Finding Levels6.4 Summary
Chapter 7: Binary Trees
7.1 Binary Tree Traversals7.2 Binary Tree Queries7.2.1 Find Parent of a Node7.2.2 Find Subtree at a Node7.3 Deletion from a Binary Tree7.4 Insertion into a Binary Tree7.5 Heaps7.6 Binary Tree Representation of Multiway Trees7.7 The Stern-Brocot Numbers
Chapter 8: Other Models for Trees
8.1 Adjacency List with Self-references8.2 Subordinate Adjacency List8.3 Hybrid Models8.3.1 Adjacency and Nested Sets Model8.3.2 Nested Set with Depth Model8.3.3 Adjacency and Depth Model8.3.4 Computed Hybrid Models8.4 General Graphs8.4.1 Detecting Paths in a Convergent Graph8.4.2 Detecting Directed Cycles
Chapter 9: Proprietary Extensions for Trees
9.1 Oracle Tree Extensions9.2 XDB Tree Extension9.3 DB2 and the WITH Operator9.4 Date's EXPLODE Operator9.5 Tillquist and Kuo's Proposals9.6 Microsoft Extensions9.7 Other Methods
Chapter 10: Hierarchies in Data Modeling
10.1 Types of Hierarchies10.2 DDL Constraints10.2.1 Uniqueness Constraints10.2.2 Disjoint Hierarchies10.2.3 Representing 1:1, 1:m, and n:m Relationships
Chapter 11: Hierarchical Encoding Schemes
11.1 ZIP codes11.2 Dewey Decimal Classification11.3 Strength and Weaknesses11.4 Shop Categories11.5 Statistical Tools for Decision Trees
Chapter 12: Hierarchical Database Systems (IMS)
12.1 Types of Databases12.2 Database History12.2.1 DL/I12.2.2 Control Blocks12.2.3 Data Communications12.2.4 Application Programs12.2.5 Hierarchical Databases12.2.6 Strengths and Weaknesses12.3 Sample Hierarchical Database12.3.1 Departmental Database12.3.2 Student Database12.3.3 Design Considerations12.3.4 Example Database Expanded12.3.5 Data Relationships12.3.6 Hierarchical Sequence12.3.7 Hierarchical Data Paths12.3.8 Database Records12.3.9 Segment Format12.3.10 Segment Definitions12.4 Summary
Appendix: Readings and Resources
Index
About the Author
Instructions for online access

Content preview from Joe Celko's Trees and Hierarchies in SQL for Smarties

CHAPTER 8 Other Models for Trees

THE MODELS FOR trees and hierarchies discussed so far are not the only ones. There are other models that use different approaches and properties of trees, some of which are hybrids of other models.

8.1 Adjacency List with Self-references

A slight modification of the usual adjacency list model is to include an edge that loops back to the same node.

Personnel_OrgChart

This makes the table longer, but it avoids a ...

Become an O’Reilly member and get unlimited access to this title plus top books and audiobooks from O’Reilly and nearly 200 top publishers, thousands of courses curated by job role, 150+ live events each month,
and much more.

Read now

Unlock full access

More than 5,000 organizations count on O’Reilly

O’Reilly covers everything we've got, with content to help us build a world-class technology community, upgrade the capabilities and competencies of our teams, and improve overall team performance as well as their engagement.

Julian F.

Head of Cybersecurity

I wanted to learn C and C++, but it didn't click for me until I picked up an O'Reilly book. When I went on the O’Reilly platform, I was astonished to find all the books there, plus live events and sandboxes so you could play around with the technology.

Addison B.

Field Engineer

I’ve been on the O’Reilly platform for more than eight years. I use a couple of learning platforms, but I'm on O'Reilly more than anybody else. When you're there, you start learning. I'm never disappointed.

Amir M.

Data Platform Tech Lead

I'm always learning. So when I got on to O'Reilly, I was like a kid in a candy store. There are playlists. There are answers. There's on-demand training. It's worth its weight in gold, in terms of what it allows me to do.

Mark W.

Embedded Software Engineer

Joe Celko's Trees and Hierarchies in SQL for Smarties, 2nd Edition

Publisher Resources

ISBN: 9781558609204

Cloud Computing

Data Engineering

Data Science

AI & ML

Programming Languages

Software Architecture

IT/Ops

Security

Design

Business

Soft Skills

Joe Celko's Trees and Hierarchies in SQL for Smarties

by Joe Celko