PHP: Recursing Relationships

In a well designed database, everything is related to everything else. Departments roll up to Companies. Work Stations spawn Service Requests. It's all relative. One of the major tasks in traversing any such a database is finding out exactly what those relationships are. Who entered that ticket? How many parts does the widget have? I've written a few simple functions to help work out the genealogy of it all, for a LAMP (PHP) environment.

For simplicity's sake, let's assume a very basic table structure. "tblFamily" has two fields: "child" and "parent". In use, it might look like this:

child   parent
1       0
2       1
3       1
4       2
5       2
6       4

So, in this example, every "child" has one and only one "parent". That's usually the way it works in everything but procreation, so work with me. On the obverse, a "parent" can any number of "children". This is a fairly standard configuration, such as in the relationship between companies and departments, or managers and employees.

In the LAMP environment, finding a single parent is pretty simple:

/*
        Given a child, return the parent
*/

function rtnParent ( $ child  )
{
        $sql = "SELECT parent from tblFamily where child = " . $child;
        $rs = sql_select($sql);
        return $rs[0]["parent"];
}

Note that, if this code looks a little unfamiliar, I'm using the database functions I built earlier. You can use the standard stuff if you want to – the concepts wont change – but the custom functions make it all a lot easier.

In the previous example, I build a SQL string asking for the parent of a child, then feeds it to the "sql_select" function. The function returns the result as an array (rows) of arrays (fields). Since there should be only one row (remember: one parent per child), we can return the "0" index row with the "parent" field value.

In use, it might work something like this:

$you = "2";
echo "Who's your daddy?";
$daddy =  rtnParent($you);
echo "I got your daddy right here:" . $daddy ;

But what if you wanted the daddy, the grand-daddy, the great-grand-daddy, and everyone else back to the down of time? In that case, you'd use something like this:

/*
        Given a child, returns all ancestors
*/

function rtnAncestors ( $ child  )
{
        $search = $child;
        $parentfound = true;
        // build an array of parents for this  child
        while($parentfound)
        {
         $sql = "SELECT parent from tblFamily where child = " . $search;
         $rs = sql_select($sql);
        if ($rs[0]["parent"] == 0) // ignore 0 space holders
        {
                $parentfound = false;
        } else {
                // add to areas array and search for next parent
                $search = $rs[0]["parent"];
                $parents[] = $search;
        }
        }
        return $parents;
}

Ok, this still isn't rocket science. What we're doing here with the "while" loop is essentially asking the same question as before. Only, this time, every time we get an answer, we ask it again, adding the results to an array and changing the child to the last parent. At the very end, when we reach the ultimate ancestor (with an ID of "0"), we set "$parentfound" to false, end the "while" loop, and return the "$parents" array.

In use, it would look like this:

$me = 34000;
$daddy = rtnParent($me );
$tree = rtnAncestors ( $daddy  )
echo "I am decended from " . $daddy;
foreach ( $tree as $granpa )
{
        echo " who is decendended from " .  $granpa;
}

But, Wait! There's more! What if you want to go the other way, looking for children, down all of the possible branches and dead-ends of the family tree? What if, say, you wanted to enter your great-grandfather, and pull back every uncle and cousin, no matter how many times removed? Then you need something like this:

/*
        Given a parent, return all decedents
*/

function rtnDescendants ($parent, $descendants)
{
 if( count($descendants) > 0 ){ $children = $descendants; }
 $sql = "SELECT child from tblFamily where parent = $parent";
 $rs = sql_select($sql);
 for ($i=0; $i < count($rs);$i++)
 {
        $children[] = $rs[$i]['child'];
        $children = rtnDescendants($rs[$i]['child'],$children);
 }
    sort($children);
    return $children;
}

Hold on tight, cause this one gets wacky. Let's start with the signature:

function rtnDescendants ($parent, $descendants)

One might ask, "Why are you required to provide the descendants if that's what you're looking for?" The reason is rooted in the recursive nature of this function. Because we'll have to keep running up the tree and back down every time we hit a dead end (a spinster uncle), we have to keep asking the same question, and having the function keep calling itself. Every time we find one, we add it to the array and pass the whole collection back into the grinder for another run through the cycle until we run out of descendants

 if( count($descendants) > 0 ){ $children = $descendants; }

This line checks to see if we've been through the process at least once. Of so, it sets the '$children" array to equal what we've found so far. Otherwise, it'll start it up fresh below.

 $sql = "SELECT child from tblFamily where parent = $parent";
 $rs = sql_select($sql);

This is the reverse of the same question we've been asking, but it's still similar in function. The only difference is that we have to be ready a multiple rows in the return set, since a parent can have any number of children.

 for ($i=0; $i < count($rs);$i++)
 {
        $children[] = $rs[$i]['child'];
        $children = rtnDescendants($rs[$i]['child'],$children);
 }

In this section, we loop through every row (child) in the return set. First, we add the child to the running array, and then we run that child through the function see if it has any children. If it does, it adds it to the array and check all descendants in the same manner. If not, it just exits and the process moves on.

sort($children);
return $children;

A little house keeping. Put all the kids in order and returns the array.

You might use it like this:

$gggf = 52;
echo "People who want a piece of Great-Great-Grandfather's fortune include ";
$children = rtnDescendants ($gggf);
foreach ( $children as $child )
{
  echo $child . " and ";
}

Now, if you can't keep your relationships straight with all of these functions, you'll probably need to seek family counseling.

Tags: