Hierarchical Database Structures

Hierarchical Database Structures (SQL)

Let's look at a visual diagram of the following data structure and explore some alternative options.

Option 1: Relational Database - Single Table

- Let's take a look at how we could structure this data in a relational database in a single table.

CREATE TABLE tree( parent INTEGER, child INTEGER );

INSERT INTO tree VALUES(NULL, 2);

INSERT INTO tree VALUES(2, 4);

INSERT INTO tree VALUES(2, 5);

Ect... Until we have the following table. 

table_name = tree

Parent | Child

  Null   |     2

  2        |      4

  2        |      5

  4        |      7

  4        |      8

  5        |      9

  5        |      1

Question: How can we return the second level of data for this tree? 

ANSWER 1: Since the table was set up correctly, we know that the child who has a parent of NULL is the head of the table and then we want to move down a level from there. 

   SELECT child FROM tree WHERE parent = 

     ( SELECT child FROM tree WHERE parent IS NULL );          

Answer 2: What do we do if the developer decides to not clue us into the fact the a child of 2 doesn't have a head?  

Parent | Child                  Parent | Child

  Null   |     2                        2        |      4

  2        |      4                       2        |      5

  2        |      5          =>        4        |      7

  4        |      7                       4        |      8

  4        |      8                       5        |      9

  5        |      9                       5        |      1

  5        |      1                                          

- We no longer have an easy path to the head of the table. 

- Let's use SQL to make this Table Join itself. I know this sounds crazy. Let's take it in steps.

  Step 1 - Make the JOIN, User Inner

  SELECT * FROM tree JOIN tree AS tree_clone WHERE tree.parent = tree_clone.child;

Results (All of the possible paths through the maze). Notice has two repeats. 

4|7|2|4

4|8|2|4

5|9|2|5

5|1|2|5

Looks like I didn't get everything I wanted. However, if we perform an OUTER JOIN we will get the additional information in return. 

  Step 3 - Try an Outer Join for more results

SELECT tree.parent FROM tree AS tree_clone LEFT OUTER JOIN tree ON tree.child = tree_clone.parent;

Results (Notice that we received two additional columns that don't match any values. Pretty Cool).

2|4| |

2|5| |

4|7|2|4

4|8|2|4

5|9|2|5

5|1|2|5

Conclusion

- We can use SQL to Join to table onto itself in order to traverse all of the different path through the hierarchy. In order to move down a row we need to gather additional information.