How to pull a list....

Kurisvo · 08-21-2012, 04:05 PM

Hey everyone!

I've got a question for you that's been stumping me for a while...

I have a table of relationships like this:

Code:

id | parent_a |parent_b
____________________
1  |      0      | 0
2  |      0      | 0
3  |      0      | 0
4  |      0      | 0
5  |      1      | 2
6  |      3      | 4
7  |      5      | 6
8  |      7      | 5

How it works is the parent_a and parent_b correspond to the id from which they originate.

The easiest way to think of it is say I'm breeding some birds and I want to keep track of it. id is the bird. So let's say bird 5 has the parents of 1 and 2. 6 has the parents of 3 and 4. The parent of 0 means we don't know and don't need to go back any farther.

My question is, how do I query this to generate a list so I can display a "lineage" of relationships? Ideally I'd like to display this info in a table with the bird on top, and it's mother and father in the next row. That's easy enough but then I want to get the mother's mother and it's lineage and the same with the father's father. I want to go all the way back to the beginning.

I know it's possible cause I've seen it done, I'm just wondering if there is a way to query for it without using endless loops.

Hopefully I was clear, if you want me to explain a bit more let me know.

EDIT:

Here is an awesome example from a game I play: http://dragcave.net/lineage/gmpkY

guelphdad · 08-21-2012, 07:16 PM

Look up TREE TRAVERSAL and NESTED SETS. There are a few resources out there from JOE CELKO to search among others. You'll need NESTED sets because you can have two parents rather than a single parentid (which is more suited to adjacency lists).

Old Pedant · 08-21-2012, 07:49 PM

If you know the total number of generations that you want to be able to go back, it's possible in a fairly straight way in a single (albeit lengthy) query.

If you want to go back an indeterminate number of generations, then one answer is to build the generational "paths" into your data. It's much much more efficient (and flexible) than nested sets, but it does mean putting more work into building the data (it pays off in the long run in vastly improved performance in "find the ancestors" or "find the descendants" queries).

Kurisvo · 08-21-2012, 08:08 PM

I think that second way would be best. I'm at a point in coding it where I can change stuff around.

Could you teach me or link me to an example on how to do that?

Old Pedant · 08-21-2012, 08:23 PM

OOPS!!! Can't do it with your example!

Your id 8 has 5 for "father" and 7 for "mother", but then 7 has 5 for "father"! So you have crossed generational boundaries. Sorry...my solution isn't suitable for more complex relations, such as this one. Apologies.

Kurisvo · 08-21-2012, 08:38 PM

That's what makes it so tricky. :c Would nested still work though? This is really stumping me.