Showing all of the children of each parent

Question

I have a table People. I want to display an HTML table consisting of every parent, with all of their children directly underneath of them.

 _________
|People   |_____________________________________________
|-------------------------------------------------------|
| id     | parent | firstname     | lastname            |
|-------------------------------------------------------|
| 1        0        James           Donovan             |
| 2        0        Jeffrey         Williams            |
| 3        0        Emmit           Herring             |
| 4        2        Carol           Williams            |
| 5        2        Sarah           Williams            |
| 6        1        Nikolai         Donovan             | 
|_______________________________________________________|

Expected output:

 ________________________________________________
|Jeffrey Williams                                |
|------------------------------------------------|
|  - Carol Williams                              |
|  - Sarah Williams                              |
|________________________________________________|
|James Donovan                                   |
|------------------------------------------------|
|  - Nikolai Donovan                             |
|________________________________________________|
|Emmit Herring                                   |
|------------------------------------------------|
|________________________________________________|

How do I build an associative array containing the right result set to iterate over? I'm confused about the right SQL and the right PHP to build the final array.

Specifically, I am unsure how to display a hierarchical relationship between two MySQL tables. SQL result sets are not multidimensional as far as I know. Putting a SQL query in a for loop is terrible for performance. So what do you do?

I guess I'm looking for an adjacency list implementation in MySQL.

This question should be easy if I could split everything out into two tables, but unfortunately I have to stick with this un-normal table structure.

Answer 1

There are several ways to do it:

1. The obvious one is to first fetch a list of all parents, and then run a separate query for the children of each parent in a loop. You say that this is "terrible for performance", but it really shouldn't be, assuming that you have an index on the parent column and that your MySQL server isn't located on the other side of the planet.

---

2. If you really want to do this is in a single query, you can use a LEFT JOIN on the table against itself:

SELECT
  p.id AS parent_id,
  p.firstname AS parent_firstname,
  p.lastname  AS parent_lastname,
  c.id AS child_id,
  c.firstname AS child_firstname,
  c.lastname  AS child_lastname
FROM
  People AS p
  LEFT JOIN People AS c ON c.parent = p.id
WHERE p.parent = 0
ORDER BY p.id

Again, you really, really need an index on the parent column. The ORDER BY clause is there to ensure that the children of each parent are sorted together; you can change it e.g. to something like p.lastname, p.firstname, p.id, c.lastname, c.firstname, c.id if you want the names sorted in alphabetical order. In PHP, you then need to loop over the results and print a new header whenever the parent ID changes (and remember to handle the case where the child_* columns are NULL), something like:

$res = mysql_query( $sql );
$last_parent_id = 0;
while ( $row = mysql_fetch_object( $res ) ) {
    if ( $row->parent_id != $last_parent_id ) {
        // print parent header
        $last_parent_id = $row->parent_id;
    }
    if ( $row->child_id ) {
        // print child row
    }
}

---

3. The third option is to just fetch all the rows with a simple SELECT * FROM People query and build the tree in PHP:

$res = mysql_query( "SELECT * FROM People" );  // add WHERE clauses if needed
$names = array();
$parents = array();
$children = array();

while ( $row = mysql_fetch_object( $res ) ) {
    $names[ $row->id ] = array( $row->firstname, $row->lastname );
    if ( $row->parent == 0 ) {
        $parents[] = $row->id;
    } else {
        if ( !array_key_exists( $row->parent, $children ) )
            $children[ $row->parent ] = array();
        $children[ $row->parent ][] = $row->id;
    }
}

foreach ( $parents as $parent_id ) {
    // print parent header
    if ( array_key_exists( $parent_id, $children ) ) {
        foreach ( $children[ $parent_id ] as $child_id ) {
            // print child row
        }
    }
}

Ps. If you don't actually want to show all the parents and children in the table, but just, say, those belonging to a single family, then you should still try to do the filtering in SQL to avoid fetching too many records.

Answer 2

According to a traditional approach, I think starting with SQL, joining tables (even if left table and right table in this case would be the same), could be a good starting point.

This is mainly because using a RDBMS you must always deal with tabular structures, and joining tables that way you're guaranteed about data consistency.

So, start with something like:

SELECT 
       a.id parent_id, a.firstname parent_name, a.lastname parent_lastname, 
       b.id child_id, b.firstname child_firstname, b.lastname child_lastname
FROM 
       People a LEFT OUTER JOIN People b ON a.id = b.parent
WHERE  
       a.parent = 0;

Second, you should prefer using a "fetch_all" strategy (with mysqli php extension, for example, but it is available with PDO also), which will give you the ability with one single operation to have the whole result set fetched in a bi-dimensional associative array.

At this point you can choose your path.

All-PHP: you could walk the array with PHP and directly build the presentation markup to display the data organized as you need, echoing the html string towards the browser.

AJAX: if - for instance - your PHP script has been rather called via AJAX you could walk the query result array as well, but this time interpreting it to build a JSON structure with which you would respond to the call, just like that:

{
    "1": {
        "id": 1,
        "firstname": "James",
        "lastname": "Donovan",
        "children": {
            "6": {
                "id": 6,
                "firstname": "Nikolai",
                "lastname": "Donovan"   
            }
        }
    },
    "2": {
        "id": 2,
        "firstname": "Jeffrey",
        "lastname": "Williams",
        "children": {
            "4": {
                "id": 4,
                "firstname": "Carol",
                "lastname": "Williams"  
            },
            "5": {
                "id": 5,
                "firstname": "Sarah",
                "lastname": "Williams"  
            }
        }
    },
    "3": {
        "id": 3,
        "firstname": "Emmit",
        "lastname": "Herring",
        "children": { }
    }
}

Such representation would be better for data interchange, because your client-side javascript could seamlessly recognize it and walk it to populate a pre-existing empty table skeleton. Sure you could have PHP to json_encode() the results array directly instead of restructuring it into something else like this, but you'd find yourself with something that wouldn't go much farther than the solid recordset-like array representation you already have.

Finally, the all-mysql solution would be to prepare a stored procedure that purposefully constructs the data structure you're looking for, e.g. 1 row per family, having the parent's full name as the first column and children's full names as subsequent columns (empty fields if the person does not have children, like Emmit Herring).

You could again "fetch_all" the result set with PHP, walk the array and you'd be done.

So if performance is a concern, this last approach should guarantee you with best results, even if it must be said that a price is paid by the server in terms of computational load and memory occupation, if you're going to deal with huge amounts of data.