Hello and welcome to our community! Is this your first visit?
Register
Enjoy an ad free experience by logging in. Not a member yet? Register.
Results 1 to 6 of 6
  1. #1
    New Coder
    Join Date
    Apr 2011
    Posts
    59
    Thanks
    8
    Thanked 0 Times in 0 Posts

    How to pull a list....

    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

  • #2
    Super Moderator guelphdad's Avatar
    Join Date
    Mar 2006
    Location
    St. Catharines, Ontario Canada
    Posts
    2,633
    Thanks
    4
    Thanked 148 Times in 139 Posts
    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).

  • #3
    Supreme Master coder! Old Pedant's Avatar
    Join Date
    Feb 2009
    Posts
    25,111
    Thanks
    75
    Thanked 4,336 Times in 4,302 Posts
    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).
    An optimist sees the glass as half full.
    A pessimist sees the glass as half empty.
    A realist drinks it no matter how much there is.

  • #4
    New Coder
    Join Date
    Apr 2011
    Posts
    59
    Thanks
    8
    Thanked 0 Times in 0 Posts
    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?

  • #5
    Supreme Master coder! Old Pedant's Avatar
    Join Date
    Feb 2009
    Posts
    25,111
    Thanks
    75
    Thanked 4,336 Times in 4,302 Posts
    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.
    An optimist sees the glass as half full.
    A pessimist sees the glass as half empty.
    A realist drinks it no matter how much there is.

  • #6
    New Coder
    Join Date
    Apr 2011
    Posts
    59
    Thanks
    8
    Thanked 0 Times in 0 Posts
    That's what makes it so tricky. :c Would nested still work though? This is really stumping me.


  •  

    Posting Permissions

    • You may not post new threads
    • You may not post replies
    • You may not post attachments
    • You may not edit your posts
    •