Trees and Hierarchies in SQL for Smarties

Team DDU......Page 1
Contents......Page 8
Introduction......Page 14
1 Graphs, Trees, and Hierarchies......Page 16
1.1 Modeling a Graph in a Program......Page 17
1.1.2 Adjacency Arrays for Graphs......Page 19
1.1.3 Finding a Path in General Graphs in SQL......Page 20
1.2.2 Properties of Hierarchies......Page 24
1.2.3 Types of Hierarchies......Page 25
1.3 Note on Recursion......Page 26
2.1 The Simple Adjacency List Model......Page 30
2.2.1 UPDATE Anomalies......Page 32
2.2.2 INSERT Anomalies......Page 33
2.2.3 DELETE Anomalies......Page 34
2.3 Fixing the Adjacency List Model......Page 35
2.4.1 Cursors and Procedural Code......Page 38
2.4.2 Self-joins......Page 39
2.6.1 Deleting an Entire Subtree......Page 41
2.6.3 Promoting an Entire Subtree after Deletion......Page 43
2.7 Leveled Adjacency List Model......Page 44
2.7.1 Numbering the Levels......Page 45
2.7.2 Aggregation in the Hierarchy......Page 46
3 Path Enumeration Models......Page 48
3.2 Searching for Subordinates......Page 50
3.3 Searching for Superiors......Page 51
3.5 Deleting a Single Node......Page 52
3.7 Splitting up a Path String......Page 53
3.8 The Edge Enumeration Model......Page 55
3.9 XPath and XML......Page 56
4 Nested Set Model of Hierarchies......Page 58
4.1 Finding Root and Leaf Nodes......Page 61
4.2 Finding Subtrees......Page 62
4.3.2 Finding Levels of Subordinates......Page 63
4.3.3 Finding Oldest and Youngest Subordinates......Page 69
4.3.5 Finding Relative Position......Page 71
4.4 Functions in the Nested Sets Model......Page 72
4.5 Deleting Nodes and Subtrees......Page 73
4.5.1 Deleting Subtrees......Page 74
4.5.2 Deleting a Single Node......Page 76
4.5.3 Pruning a Set of Nodes from a Tree......Page 78
4.6 Closing Gaps in the Tree......Page 79
4.7 Summary Functions on Trees......Page 82
4.7.1 Iterative Parts Update......Page 83
4.7.2 Recursive Parts Update......Page 87
4.8 Inserting and Updating Trees......Page 90
4.8.1 Moving a Subtree within a Tree......Page 93
4.8.2 MoveSubtree, Second Version......Page 97
4.8.3 Subtree Duplication......Page 98
4.8.4 Swapping Siblings......Page 101
4.9 Converting Nested Sets Model to Adjacency List......Page 102
4.10 Converting Adjacency List to Nested Sets Model......Page 103
4.11.1 Multiple Structures......Page 105
4.11.2 Multiple Nodes......Page 106
4.12 Comparing Nodes and Structure......Page 107
4.13 Nested Sets Code in Other Languages......Page 111
5 Frequent Insertion Trees......Page 114
5.1.2 FLOAT, REAL, or DOUBLE PRECISION Numbers......Page 116
5.2 Computing the Spread to Use......Page 117
5.2.1 Varying the Spread......Page 120
5.2.3 Divisor via Formula......Page 121
5.2.5 Partial Reorganization......Page 122
5.2.6 Rightward Spread Growth......Page 124
5.3.1 Reorganization with Lookup Table......Page 126
5.3.2 Reorganization with Recursion......Page 130
5.4 Rational Numbers and Nested Intervals Model......Page 132
5.4.1 Partial Order Mappings......Page 133
5.4.2 Summation of Coordinates......Page 136
5.4.3 Finding Parent Encoding and Sibling Number......Page 139
5.4.4 Calculating the Enumerated Path and Distance between Nodes......Page 141
5.4.5 Building a Hierarchy......Page 145
5.4.6 Depth-first Enumeration by Left Interval Boundary......Page 146
5.4.8 All Descendants of a Node......Page 147
6 The Linear Version of the Nested Sets Model......Page 150
6.1 Insertion and Deletion......Page 151
6.3 Finding Levels......Page 153
6.4 Summary......Page 154
7 Binary Trees......Page 156
7.1 Binary Tree Traversals......Page 158
7.2 Binary Tree Queries......Page 160
7.2.1 Find Parent of a Node......Page 161
7.2.2 Find Subtree at a Node......Page 162
7.5 Heaps......Page 163
7.6 Binary Tree Representation of Multiway Trees......Page 167
7.7 The Stern-Brocot Numbers......Page 168
8.1 Adjacency List with Self-references......Page 170
8.2 Subordinate Adjacency List......Page 171
8.3.1 Adjacency and Nested Sets Model......Page 172
8.3.3 Adjacency and Depth Model......Page 173
8.3.4 Computed Hybrid Models......Page 174
8.4.1 Detecting Paths in a Convergent Graph......Page 177
8.4.2 Detecting Directed Cycles......Page 180
9.1 Oracle Tree Extensions......Page 182
9.2 XDB Tree Extension......Page 184
9.3 DB2 and the WITH Operator......Page 185
9.5 Tillquist and Kuo\'s Proposals......Page 186
9.7 Other Methods......Page 187
10 Hierarchies in Data Modeling......Page 188
10.1 Types of Hierarchies......Page 192
10.2.1 Uniqueness Constraints......Page 193
10.2.2 Disjoint Hierarchies......Page 196
10.2.3 Representing 1:1, 1:m, and n:m Relationships......Page 199
11.1 ZIP codes......Page 204
11.2 Dewey Decimal Classification......Page 205
11.3 Strength and Weaknesses......Page 206
11.4 Shop Categories......Page 207
11.5 Statistical Tools for Decision Trees......Page 210
12.1 Types of Databases......Page 212
12.2 Database History......Page 213
12.2.3 Data Communications......Page 215
12.2.6 Strengths and Weaknesses......Page 216
12.3 Sample Hierarchical Database......Page 217
12.3.4 Example Database Expanded......Page 219
12.3.5 Data Relationships......Page 221
12.3.7 Hierarchical Data Paths......Page 222
12.3.8 Database Records......Page 223
12.3.9 Segment Format......Page 224
12.3.10 Segment Definitions......Page 225
12.4 Summary......Page 226
Appendix: Readings and Resources......Page 228
Index......Page 230