Michael Gilfix Online

I recently found myself posed with a design problem that necessitated storing a hierarchical structure in a relational database (no, a directory such as LDAP wasn't an option). A desirable solution would be implemented entirely in SQL, without dipping into stored procedure specifics. A bit of research turned up three techniques:

• Adjacency lists: Effectively each node (row) gets a parent column that refers to its parent. The tree is constructed by traversing through parent links. Here's a good tutorial: http://www.sqlsummit.com/AdjacencyList.htm.
  
• Nested sets: An excellent and clever approach that has yielded much fame for Mr. Joe Celko. Each node in the hierarchy has an interval that represents the range of its children, with smaller numbers in a level being to the left and larger numbers moving to the right. http://www.intelligententerprise.com/001020/celko.jhtml?_requestid=235427.
  
• Right child index: Each node gets a positive integer index and each node contains a column that references its rightmost child. In each level, nodes are organized from smallest index to largest. http://www.codeproject.com/cs/database/persisting_trees.asp#af.

I just read two interesting papers (sharing the same core set of authors) that argue that the database industry is on the cusp of a shift to evolve beyond the "one-size-fits-all" motto that has been the relational database industry for quite some time. Here is a link to the two papers:

1. "One Size Fits All": An Idea Whose Time Has Come and Gone: http://www.cs.brown.edu/~ugur/fits_all.pdf
2. "One Size Fits All? - Part 2: Benchmarking Results: http://nms.csail.mit.edu/~stavros/pubs/osfa.pdf

The crux of the argument is that the market has begun shifting towards applications where the performance benefits of domain-specific database engines cannot be ignored. Together, the papers cover a wide variety of ground: (a) column-centric storage rather than row-centric storage, (b) stream processing, (c) text searching, (d) XML databases, and (e) array-centric processing of large data-sets.

Approach (a) has benefits for applications like large data warehousing, which are optimized for ad-hoc, read-centric querying. Data is scraped off operational systems in an offline basis, mitigating the need for write performance. In addition, data sets with a large number of columns (increasingly common) benefit performance-wise from column-centric storage. Queries with several predicates need only read the columns addressed by the query, filtering large amounts of data before returning the candidate row set -as opposed to row-centric storage used by most RDBMS, where each row's data must be processed during the query, requiring sifting through large amounts of data. Approach (e) is clearly problematic for a straightforward relational system, as it requires introspective abilities within text data types containing XML, which should have ideally been stored or indexed differently in the first place. However, support for two of these domains has infiltrated the existing database market with built-in data warehousing support, and support for XML storage and query.