views:

106

answers:

2

I know there's an easy way of doing this, but my recursion abilities are out of practice. Given a database table that has three fields:

id
label
child_id

I should be able to put together a recursive function that will give output like this:

child (input of program)
  parent1
  parent2
    grandparent1
      great-grandparent1
    grandparent2
    grandparent3
  parent3
    grandparent4
    grandparent5

I know it should be easy, but I can't get my mind to go through the mental gymnastics to make it work. Also, is this a good thing to do? Seems like I might end up leaving open quite a few database connections.

I think this is the part making it difficult for me. I'm starting with a child_id, and working my way up. And a child can have many parents. So, the output would be the child id at the 'root' of the tree and then it's parents and grandparents for each branch. The more I think about it, it's just the traditional 'one parent, many grandparents' formula, except for semantics. I could just be over thinking it.

The table would look something like this:

table parents

id    child_id    label
 1     NULL       child
 2     1          parent1
 3     1          parent2
 4     1          parent3
 5     3          grandparent1
 6     3          grandparent2
 7     3          grandparent3
 8     5          great-grandparent1
 9     4          grandparent4
10     4          grandparent5
+4  A: 

You could try this way

sub getChildren {
  my $id = shift;
  my $depth = shift;
  my $sql = qq/SELECT id,label,child_id FROM table WHERE id=?/;
  my $sth = $db->prepare($sql);
  my $sth->execute($id);
  while(my ($id,$label,$child_id)=$sth->fetchrow_array) {
    print " "x$depth,$label;
    getChildren($child_id,$depth++);
 }
}
getChildren($id);
M42
Awesome. That's about what I was trying to do, but I was trying to use a global $depth for some reason. If you read my note above, I'm actually starting with the children, but I think the same concept will work.
coding_hero
You only need to prepare the statement once. Or use prepare_cached().
runrig
The $depth counter keeps counting, even when it should reset, for some reason. I think a prefix is more appropriate here (++$depth), but it still has the same issue either way.
coding_hero
Never mind, figured it out. The $depth++ incrementor needs to be located outside of the while loop.
coding_hero
Yes, you're right
M42
A: 

I actually explained a quite similar problem in my blog, Implementing a depth first search in a PostgreSQL stored procedure, and my way of solving this using perl.

If your database doesn't support stored procedures you can do the same thing client-side, but you need to fetch the entire table first and do it in memory.

You could of course do it recursively and fetch each entry as you go along, but it will not scale because of the SQL statement overhead (except maybe on SQLite). If performance is not a problem this must be by far the easiest solution.

Robin Smidsrød