1

I am aware of several models for describing hierarchical data in relational databases:

  • self-reference parent (each record has has a foreign key pointing to the primary key of the same table, not sure what this is called)
  • adjacency lists
  • nested sets

It occurred to me that there is another way to describe a hierarchy which has a different set of drawbacks to these models (a high degree of redundancy for one thing) - that is to maintain a shadow table where all the ancestors for each node in a tree and the number of generations apart the node is from its ancestor, e.g.

 node         ancestor          generations
 ----         --------          -----------
 leaf         parent            1
 leaf         grandparent       2
 leaf         great-grandparent 3
 leaf         root              4
 parent       grandparent       1
 parent       great-grandparent 2
 parent       root              3
 grandparent  great-grandparent 1
 grandparent  root              2
 great-grandparent  root        1

Describes the hierarchy....

 root
  |
  +- great-grandparent
      |
      +- grandparent
          |
          +- parent
              |
              +- leaf

I sincerely doubt that I have invented something new - but I'm struggling to find a description of this on the web due to the noise returned by search engines.

Does this have a name already?

symcbean
  • 47,736
  • 6
  • 59
  • 94
  • https://en.wikipedia.org/wiki/Hierarchical_database_model maybe this? – Alberto Sinigaglia Jan 06 '20 at 23:46
  • 2
    In [this presentation(page 46)](https://www.slideshare.net/billkarwin/models-for-hierarchical-data) , this model is called *closure tables*. [This question](https://stackoverflow.com/questions/49700342/closure-table-equivalent-for-graph-structures-in-sql) might also be relevant. – jrook Jan 07 '20 at 00:14
  • @AlbertoSinigaglia: No. – symcbean Jan 07 '20 at 02:08
  • @jrook Thanks - want to put this in an answer rather than a comment? – symcbean Jan 07 '20 at 02:12

1 Answers1

1

This presentation (starting page 40) by Bill Karwin calls a very similar structure to what you have described as closure table. The generations column in your structure is also introduced as length.

StackOverflow actually has a tag for this data structure. One of the top reference links in the tag info page refers to the presentation linked in this answer.

I am not sure if there is a specific technical reason for calling this pattern the closure table. Wikipedia article on transitive closures might shed some light:

In mathematics, the transitive closure of a binary relation R on a set X is the smallest relation on X that contains R and is transitive.

For example, if X is a set of airports and xRy means "there is a direct flight from airport x to airport y" (for x and y in X), then the transitive closure of R on X is the relation R+ such that x R+ y means "it is possible to fly from x to y in one or more flights". Informally, the transitive closure gives you the set of all places you can get to from any starting place.

jrook
  • 3,459
  • 1
  • 16
  • 33