Joe Celko's Trees and Hierarchies in SQL for Smarties

Joe Celko's Trees and Hierarchies in SQL for Smarties

The Morgan Kaufmann Series in Data Management Systems
2004, Pages 3-15
Joe Celko's Trees and Hierarchies in SQL for Smarties

Chapter 1 - Graphs, Trees, and Hierarchies rights and content

Publisher Summary

Graph theory is a branch of mathematics that deals with abstract structures, known as graphs. A graph is a diagram of dots called nodes or vertices and lines called edges that model some kind of flow or relationship. The edges can be undirected or directed. Before the development of SQL, programmers represented graphs in the programming language that they had. People used pointer chains in an assembly language or system development languages, such as C, to build direct representations of graphs with machine language instructions. However, unlike low-level system development languages, higher-level languages, such as Pascal, LISP, and PL/I, did not expose the hardware to the programmer. Most of these application development languages do not have pointers but often have arrays. Once the array techniques for graphs were developed, they became part of the computer programming and were implemented in other languages. The chapter uses pseudocode to explain these techniques. Trees are a special case of graphs, whereas hierarchies are a special case of trees. A tree is a connected graph that has no cycles. A connected graph is the one in which there is a path between any two nodes and has one less edge than it has nodes. No node sits by itself, disconnected from the rest of the graph. Every node in a tree is the root of a subtree. A hierarchy is a directed tree with extra properties, such as subordination and inheritance. The chapter also explains recursion, because trees are a recursive data structure and can be accessed using recursive algorithms.

References (0)

Cited by (0)

View full text