Joe Celko's Trees and Hierarchies in SQL for Smarties (eBook)

Front Cover 1
Joe Celko’s Trees and Hierarchies in SQL for Smarties 4
Copyright Page 5
Contents 8
Introduction 14
Chapter 1. Graphs, Trees, and Hierarchies 16
1.1 Modeling a Graph in a Program 17
1.2 Defining Trees and Hierarchies 24
1.3 Note on Recursion 26
Chapter 2. Adjacency List Model 30
2.1 The Simple Adjacency List Model 30
2.2 The Simple Adjacency List Model Is Not Normalized 32
2.3 Fixing the Adjacency List Model 35
2.4 Navigation in Adjacency List Model 38
2.5 Inserting Nodes in the Adjacency List Model 41
2.6 Deleting Nodes in the Adjacency List Model 41
2.7 Leveled Adjacency List Model 44
Chapter 3. Path Enumeration Models 48
3.1 Finding the Depth of the Tree 50
3.2 Searching for Subordinates 50
3.3 Searching for Superiors 51
3.4 Deleting a Subtree 52
3.5 Deleting a Single Node 52
3.6 Inserting a New Node 53
3.7 Splitting up a Path String 53
3.8 The Edge Enumeration Model 55
3.9 XPath and XML 56
Chapter 4. Nested Set Model of Hierarchies 58
4.1 Finding Root and Leaf Nodes 61
4.2 Finding Subtrees 62
4.3 Finding Levels and Paths in a Tree 63
4.4 Functions in the Nested Sets Model 72
4.5 Deleting Nodes and Subtrees 73
4.6 Closing Gaps in the Tree 79
4.7 Summary Functions on Trees 82
4.8 Inserting and Updating Trees 90
4.9 Converting Nested Sets Model to Adjacency List 102
4.10 Converting Adjacency List to Nested Sets Model 103
4.11 Separation of Edges and Nodes 105
4.12 Comparing Nodes and Structure 107
4.13 Nested Sets Code in Other Languages 111
Chapter 5. Frequent Insertion Trees 114
5.1 The Datatype of (lft, rgt) 116
5.2 Computing the Spread to Use 117
5.3 Total Reorganization 126
5.4 Rational Numbers and Nested Intervals Model 132
Chapter 6. The Linear Version of the Nested Sets Model 150
6.1 Insertion and Deletion 151
6.2 Finding Paths 153
6.3 Finding Levels 153
6.4 Summary 154
Chapter 7. Binary Trees 156
7.1 Binary Tree Traversals 158
7.2 Binary Tree Queries 160
7.3 Deletion from a Binary Tree 163
7.4 Insertion into a Binary Tree 163
7.5 Heaps 163
7.6 Binary Tree Representation of Multiway Trees 167
7.7 The Stern-Brocot Numbers 168
Chapter 8. Other Models for Trees 170
8.1 Adjacency List with Self-references 170
8.2 Subordinate Adjacency List 171
8.3 Hybrid Models 172
8.4 General Graphs 177
Chapter 9. Proprietary Extensions for Trees 182
9.1 Oracle Tree Extensions 182
9.2 XDB Tree Extension 184
9.3 DB2 and the WITH Operator 185
9.4 Date’s EXPLODE Operator 186
9.5 Tillquist and Kuo’s Proposals 186
9.6 Microsoft Extensions 187
9.7 Other Methods 187
Chapter 10. Hierarchies in Data Modeling 188
10.1 Types of Hierarchies 192
10.2 DDL Constraints 193
Chapter 11. Hierarchical Encoding Schemes 204
11.1 ZIP codes 204
11.2 Dewey Decimal Classification 205
11.3 Strength and Weaknesses 206
11.4 Shop Categories 207
11.5 Statistical Tools for Decision Trees 210
Chapter 12. Hierarchical Database Systems (IMS) 212
12.1 Types of Databases 212
12.2 Database History 213
12.3 Sample Hierarchical Database 217
12.4 Summary 226
Appendix: Readings and Resources 228
Index 230