#1
  1. No Profile Picture
    Contributing User
    Devshed Newbie (0 - 499 posts)

    Join Date
    May 2004
    Location
    Boston, MA USA
    Posts
    388
    Rep Power
    47

    Hierarchical Relationships


    Hi:

    I have a database of records and I want to build a hierarchical relationship (tree) of them.

    The items table has fields such as:
    item_id, item_name, item description, etc

    Then there is a "parent" table that assigns one record as a "parent" of another. This table simply has

    index, item_id, parent_id

    where "item_id" is a record from the items table and "parent_id" is an "item_id" of another record in the items table.

    The hierarchy can have many levels, and any item can have multiple parents.

    I'm having trouble with an efficient MySQL query which will take all items in the "items" table, and using the "parents" table find all parents and "grandparents" and "great-grandparents", etc. especially where somewhere along the branch there bay be multiple parents.

    i.e. what I would like to display is, for an item named "item1":

    Top-of-tree > ggp1 > gp1 > p1 > item1

    Top-of tree > p2 > item1
    In this case, item1 has two parents, "p1" and "p2"
    "p1" is a child of "gp1" which is a child of "ggp1" which is a child of the top
    "p2" is a direct child of the top.

    How can I display these relationships without explicitly nesting many many SELECTs
  2. #2
  3. SQL Consultant
    Devshed Supreme Being (6500+ posts)

    Join Date
    Feb 2003
    Location
    Toronto Canada
    Posts
    27,203
    Rep Power
    4279
    Originally Posted by SeanF
    How can I display these relationships without explicitly nesting many many SELECTs
    1. many many LEFT OUTER JOINs

    2. change your data model to the nested set model (google that for more info)
    rudy.ca | @rudydotca
    Buy my SitePoint book: Simply SQL
  4. #3
  5. No Profile Picture
    Contributing User
    Devshed Newbie (0 - 499 posts)

    Join Date
    May 2004
    Location
    Boston, MA USA
    Posts
    388
    Rep Power
    47
    Originally Posted by r937
    1. many many LEFT OUTER JOINs

    2. change your data model to the nested set model (google that for more info)
    Thanks for the response...

    Yes, I did it with many outer joins to the same table. I also joined to a separate table for the item names.

    Here's the query:

    select base. destination_id as dest_id
    , base.parent_id as base_parent_id
    , d1.name as name1
    , up1.parent_id as up1_id
    , d2.name as name2
    , up2.parent_id as up2_id
    , d3.name as name3
    , up3.parent_id as up3_id
    , d4.name as name4
    , up4.parent_id as up4_id
    , d5.name as name5
    , up5.parent_id as up5_id
    , d6.name as name6
    , up6.parent_id as up6_id
    , d7.name as name7
    , up7.parent_id as up7_id
    , d8.name as name8
    from destinations_parents as base
    left join destinations as d1 on d1.id = base.parent_id
    left outer join destinations_parents as up1
    on up1.destination_id = base.parent_id
    left join destinations as d2 on d2.id = up1.destination_id
    left outer join destinations_parents as up2
    on up2.destination_id = up1.parent_id
    left join destinations as d3 on d3.id = up2.destination_id
    left outer join destinations_parents as up3
    on up3.destination_id = up2.parent_id
    left join destinations as d4 on d4.id = up3.destination_id
    left outer join destinations_parents as up4
    on up4.destination_id = up3.parent_id
    left join destinations as d5 on d5.id = up4.destination_id
    left outer join destinations_parents as up5
    on up5.destination_id = up4.parent_id
    left join destinations as d6 on d6.id = up5.destination_id
    left outer join destinations_parents as up6
    on up6.destination_id = up5.parent_id
    left join destinations as d7 on d7.id = up6.destination_id
    left outer join destinations_parents as up7
    on up7.destination_id = up6.parent_id
    left join destinations as d8 on d8.id = up7.destination_id
    where base.destination_id = $destination_id
    order
    by d1.name
    , d2.name
    , d3.name
    , d4.name
    , d5.name
    , d6.name
    , d7.name
    This assumes the hierarchy will never be more than 7 levels deep.

    Can anyone think of a way to streamline this?
  6. #4
  7. No Profile Picture
    Lost in code
    Devshed Supreme Being (6500+ posts)

    Join Date
    Dec 2004
    Posts
    8,317
    Rep Power
    7170
    No. Unless you switch to the nested set model as r937 suggested.
    PHP FAQ

    Originally Posted by Spad
    Ah USB, the only rectangular connector where you have to make 3 attempts before you get it the right way around
  8. #5
  9. No Profile Picture
    Contributing User
    Devshed Intermediate (1500 - 1999 posts)

    Join Date
    Mar 2008
    Posts
    1,928
    Rep Power
    378
    Can a 'parent' have more than one child?

    If not, suggest you reverse your hierarchy!
  10. #6
  11. SQL Consultant
    Devshed Supreme Being (6500+ posts)

    Join Date
    Feb 2003
    Location
    Toronto Canada
    Posts
    27,203
    Rep Power
    4279
    Originally Posted by SeanF
    Yes, I did it with many outer joins to the same table. I also joined to a separate table for the item names.
    well done

    i notice you used "upn" as table aliases, did you by any chance use Categories and Subcategories as a guide?

    'cause i wrote that article

    rudy.ca | @rudydotca
    Buy my SitePoint book: Simply SQL
  12. #7
  13. No Profile Picture
    Contributing User
    Devshed Newbie (0 - 499 posts)

    Join Date
    May 2004
    Location
    Boston, MA USA
    Posts
    388
    Rep Power
    47
    Originally Posted by cafelatte
    Can a 'parent' have more than one child?

    If not, suggest you reverse your hierarchy!
    Yes, a parent can have more than one child an a child can have multiple parents as well.

    The intent is to allow multiple methods of navigating down the tree, depending on each user's point of view or intuition.

    For example, if this were a hierarch of destinations, and the user was trying to get to Cannes, France:

    One user might logically think:
    World > Europe > France > French Riviera > Cannes

    Another might think:
    World > Mediterranean > French Riviera > Cannes

    So:
    Cannes is a child of the French Riviera
    but
    The French Riviera is a child of both The Mediterranean and France.

    The French Riviera has multiple children so the same "double" path applies to all children of the French Riviera, without having to explicitly define it. (the path is inherited from the parent)
    Last edited by SeanF; December 1st, 2012 at 09:41 PM.
  14. #8
  15. No Profile Picture
    Contributing User
    Devshed Newbie (0 - 499 posts)

    Join Date
    May 2004
    Location
    Boston, MA USA
    Posts
    388
    Rep Power
    47
    Originally Posted by r937
    well done

    i notice you used "upn" as table aliases, did you by any chance use Categories and Subcategories as a guide?

    'cause i wrote that article

    Ha ha ha... Yes, I did! Well Done to you!

    Do I owe you a royalty??
  16. #9
  17. SQL Consultant
    Devshed Supreme Being (6500+ posts)

    Join Date
    Feb 2003
    Location
    Toronto Canada
    Posts
    27,203
    Rep Power
    4279
    Originally Posted by SeanF
    Do I owe you a royalty??
    nope, it's out there on da free interwebs

    rudy.ca | @rudydotca
    Buy my SitePoint book: Simply SQL

IMN logo majestic logo threadwatch logo seochat tools logo