The Cusp of Helix

Fertile Forest Model
[C.1: Hierarchical Data in a RDB]

Focus of Problem

Reuse the two roles of model to store hierarchical data in RDB.

  1. To store the hierarchical data in RDB table.
  2. To write the query to find the relevant nodes efficiently for any nodes.

If the reason for unwieldy a hierarchical data in RDB is only "To store the hierarchical data in RDB table", does not exist problems that plague the database engineers around the world. Because. "Adjacency List Model" was demonstrated that it can not be described efficient query to find subtree. However, Adjacency List Model can store hierarchical data in RDB.

There are several reasons why it is difficult to write an efficient find query.

  1. For being searchable, it is necessary to store all the ancestor nodes of each node.
  2. The number of nodes relationship to store, is increased according exponentially to the depth of the tree.
  3. The depth of hierarchy is not fixed with depending on contents of data.
  4. It is difficult to impart index to hierarchical data in a database. Because tree structure having the two-dimensional spread, but index is one-dimensional structure.
  5. etc.

Consider to find a set of descendant nodes from specified node. It is a simple story If can determine for each node by tracing branch lines to ancestor direction. However, SQL is a "declarative programming". Therefore, can not implement for determining relationship for each node, like imperative programming in a separate process.

In declarative programming, how can we express the relationship of the subtree and ancestor nodes in the search queries?

This is the essence of a challenge that all database engineers around the world given. The problem of hierarchical data in RDB attaches at one point that "describes the search queries to efficiently retrieve related node from any node".