How do I extract and display hierarchical data from my database?

Question

I have two tables.

The chapters table has the columns id and name.

The chapters_chapter table has columns id, master_id, and slave_id.

Lets say that the chapters table has 7 records:

id     name
1      test01
2      test02
3      test03
4      test04
5      test05
6      test06
7      test07

And in the chapters_chapters table I have these records:

id    master_id    slave_id
1     1            5
2     1            6
3     6            7
4     7            2

Given that data, how can I extract the hierarchy of that data so that it looks like this?

test01
  test05
  test06
    test07
      test02
test03
test04

Answer 1

So this was kind of a pain because of the fact that we had to have the hierarchy stored in the DB. Because of this, each item can have multiple children, and each child can have multiple parents.

This second part means we cannot simply loop through the list once and be done with it. We might have to insert an item in multiple places in the hierarchy. While you probably won't actually structure your data that way, the database schema you've described supports this scenario, so the code must support it too.

Here's a high-level version of the algorithm:

1. Query both tables
2. Create a map (array) of a parent (number) to its children (another array)
3. Create a set of items that are children (array of numbers)
4. Create a function that displays a single item, indenting it to the desired depth.
   If that item has children, this function increases the depth by one, and calls itself recursively
5. Loop through all items that aren't children (root items).
   Call the function for each of those items, with a desired depth of 0 (no indent).

Here's two hours work. Enjoy :)

Note that I stuck it within a <pre> block, so you might have to mess with how the indentation is done (output something other than two spaces, mess with the style of the divs, etc).

<?php
  $con = mysql_connect("localhost", "test_user", "your_password");
  if(!$con)
  {
    die("could not connect to DB: " . mysql_error());
  }
  mysql_select_db("your_db", $con);

  // get chapters
  $chapters = array();

  $result = mysql_query("SELECT * FROM chapters");
  while($row = mysql_fetch_array($result))
  {
    $id = $row["id"];
    $name = $row["name"];
    $chapters[$id] = $name;
  }

  // get chapters_chapters - We'll call it "parent/child" instead of "master/slave"
  $parent_child_map = array();
  $is_child = array();

  $result = mysql_query("SELECT master_id, slave_id FROM chapters_chapters");
  while($row = mysql_fetch_array($result))
  {
    $parent_id = $row["master_id"];
    $child_id = $row["slave_id"];

    $children = $parent_child_map[$parent_id];
    if($children == null)
    {
      $children = array();
    }

    $children[] = $child_id;
    $parent_child_map[$parent_id] = $children;

    $is_child[$child_id] = true;
  }

  // display item hierarchically
  $display_item_and_children = function($id, $name, $depth)
    use ($chapters, $parent_child_map, &$display_item_and_children)
  {
    echo "<div><pre>";

    // indent up to depth
    for($i = 0; $i < $depth; $i++)
    {
      echo "  ";
    }

    echo "id: " . $id
      . " name: " . $name
      . "</pre></div>";

    // if there are children, display them recursively
    $children = $parent_child_map[$id];
    if($children != null)
    {
      foreach($children as $child_id)
      {
        $child_name = $chapters[$child_id];
        $display_item_and_children($child_id, $child_name, $depth + 1);
      }
    }
  };

  // display all top-level items hierarchically
  foreach($chapters as $id => $name)
  {
    // if it is a top-level item, display it
    if($is_child[$id] != true)
    {
      $display_item_and_children($id, $name, 0);
    }
  }

  mysql_close($con);
?>

And here's a screenshot:

Answer 2

The question becomes how complex you want your solution to be. I'd do it with the following pseudo code.

• SELECT all the chapters
• SELECT all the *chapters_chapters*
• loop over the chapters to create an array chapter objects
• loop over the `chapters_chapters* and create the relationships using the chapter objects

Essentially you're creating a link-list.