SitePoint Sponsor

User Tag List

Results 1 to 12 of 12

Thread: Breadcrumb help

  1. #1
    SitePoint Guru
    Join Date
    Nov 2004
    Location
    Parry Sound, ON
    Posts
    725
    Mentioned
    0 Post(s)
    Tagged
    0 Thread(s)

    Breadcrumb help

    Hi,

    Here's the scenario. I have a table 'sections' with the following fields:
    primary int 'id'
    index int 'parent_id'
    index varchar 'title'

    parent_id is a 'foreign key' to the id in the same table. Every page has exactly one parent except the home page, which has none. Each page may have zero to many children. Nesting could be infinite, but in practice it will be about 20 levels deep. Imagine a 'tree of life', for example, or any other tree-like hierarchy.

    I'm wondering if it's possible to have a single query such that, for any given page you're on, you can get the breadcrumb all the way back to the root. Or will it be more efficient just to have a bunch of queries and a recursive function.

    Thanks for your advice.

  2. #2
    SQL Consultant gold trophysilver trophybronze trophy
    r937's Avatar
    Join Date
    Jul 2002
    Location
    Toronto, Canada
    Posts
    39,347
    Mentioned
    63 Post(s)
    Tagged
    3 Thread(s)
    yes, 20 joins is possible in one query, it will be a large query but it is certainly feasible

    it should also perform extremely well, since you're going up the tree rather than down, because it will only find 1 result row, not millions as it might going down the tree (see this thread)

    Code:
    select curr.title
         , up01.title
         , up02.title
         , up03.title
         , up04.title
         , up05.title
         , up06.title
         , up07.title
         , up08.title
         , up09.title
         , up10.title
         , up11.title
         , up12.title
         , up13.title
         , up14.title
         , up15.title
         , up16.title
         , up17.title
         , up18.title
         , up19.title
         , up20.title
      from sections as curr
    left outer
      join sections as up01
        on curr.parent_id = up01.id  
    left outer
      join sections as up02
        on up01.parent_id = up02.id  
    left outer
      join sections as up03
        on up02.parent_id = up03.id  
    left outer
      join sections as up04
        on up03.parent_id = up04.id  
    left outer
      join sections as up05
        on up04.parent_id = up05.id  
    left outer
      join sections as up06
        on up05.parent_id = up06.id  
    left outer
      join sections as up07
        on up06.parent_id = up07.id  
    left outer
      join sections as up08
        on up07.parent_id = up08.id  
    left outer
      join sections as up09
        on up08.parent_id = up09.id  
    left outer
      join sections as up10
        on up09.parent_id = up10.id  
    left outer
      join sections as up11
        on up10.parent_id = up11.id  
    left outer
      join sections as up12
        on up11.parent_id = up12.id  
    left outer
      join sections as up13
        on up12.parent_id = up13.id  
    left outer
      join sections as up14
        on up13.parent_id = up14.id  
    left outer
      join sections as up15
        on up14.parent_id = up15.id  
    left outer
      join sections as up16
        on up15.parent_id = up16.id  
    left outer
      join sections as up17
        on up16.parent_id = up17.id  
    left outer
      join sections as up18
        on up17.parent_id = up18.id  
    left outer
      join sections as up19
        on up18.parent_id = up19.id  
    left outer
      join sections as up20
        on up19.parent_id = up20.id
    note they have to be left outer joins because you could be sitting on, say, a node 4 levels down, then many of the resulting columns will be null

    you just assemble the breadcrumb by reading the titles from right to left in the result set, starting with the first non-null one (which will be the root)

    rudy.ca | @rudydotca
    Buy my SitePoint book: Simply SQL
    "giving out my real stuffs"

  3. #3
    SitePoint Guru
    Join Date
    Nov 2004
    Location
    Parry Sound, ON
    Posts
    725
    Mentioned
    0 Post(s)
    Tagged
    0 Thread(s)
    Thanks. Any thoughts on the efficiency of that? Does MySQL have to scan the table twenty times so you might as well have just done 20 queries? Does it stick twenty copies of the table in memory or something?

    Also, there is no guarantee that it will be twenty levels deep. Could be more. Any way to make sure it keeps going until it hits the top?

    Should have mentioned, I'm on recent MySQL 4.x

  4. #4
    SitePoint Guru
    Join Date
    Nov 2004
    Location
    Parry Sound, ON
    Posts
    725
    Mentioned
    0 Post(s)
    Tagged
    0 Thread(s)
    Ok, just read the link above in your post. Neat stuff. But no, on any given page I only need to find its immediate children. Thanks again.

  5. #5
    SQL Consultant gold trophysilver trophybronze trophy
    r937's Avatar
    Join Date
    Jul 2002
    Location
    Toronto, Canada
    Posts
    39,347
    Mentioned
    63 Post(s)
    Tagged
    3 Thread(s)
    Quote Originally Posted by HardCoded
    Also, there is no guarantee that it will be twenty levels deep. Could be more. Any way to make sure it keeps going until it hits the top?
    yes, there sure is

    again, this is because you're going up the tree from the current node

    if you don't get a NULL in at least up20.title, just issue the query again

    of course, you'll need to pull the ids along with the titles, because you'll need the id of the node you're starting the query on (which i forgot in the sample i showed you)

    make sense?

    issue the query twice, and you can go up 40 levels

    as far as the efficiency is concerned, remember, it's going to be blindingly fast, because you're going up a series of 1-to-many relationships, not down

    but quite frankly, i really really really really really do not want to navigate my way around a hierarchy on a web site using a breadcrumb that's even 10 levels deep, never mind 40!!!!
    rudy.ca | @rudydotca
    Buy my SitePoint book: Simply SQL
    "giving out my real stuffs"

  6. #6
    SitePoint Guru
    Join Date
    Nov 2004
    Location
    Parry Sound, ON
    Posts
    725
    Mentioned
    0 Post(s)
    Tagged
    0 Thread(s)
    Quote Originally Posted by r937
    but quite frankly, i really really really really really do not want to navigate my way around a hierarchy on a web site using a breadcrumb that's even 10 levels deep, never mind 40!!!!
    Sure, but neither do you want to navigate a site with 100,000 links on the front page The browse hierarchy is really just there for Google et al., I expect humans will just use the search function. But if they come in via Google, I wanted the breadcrumbs so people can locate themselves.

    Anyway, I thank you again.

    Hmm..just sat here and thought, maybe I could just go up 5 levels, and provide an ellipsis in place of the other possible entries. Probably just as useful and less irritating. Going OT now, but something like (suppose I'm on a level 9 page):

    Home >> ... >> Level 4 >> Level 5 >> Level 6 >> Level 7 >> Level 8 >>
    LEVEL 9

    Would you find that less irritating or just confusing?

  7. #7
    SQL Consultant gold trophysilver trophybronze trophy
    r937's Avatar
    Join Date
    Jul 2002
    Location
    Toronto, Canada
    Posts
    39,347
    Mentioned
    63 Post(s)
    Tagged
    3 Thread(s)
    that's an improvement, but i would wonder why the information architecture analysis resulted in so many levels

    what would happen if you set a design criterion that there be no more than 3 levels? can you organize the information to be "wide" rather than "deep"?

    and i don't think this is OT, after all, sitepoint is all about effective design for web sites, right?

    rudy.ca | @rudydotca
    Buy my SitePoint book: Simply SQL
    "giving out my real stuffs"

  8. #8
    SitePoint Guru
    Join Date
    Nov 2004
    Location
    Parry Sound, ON
    Posts
    725
    Mentioned
    0 Post(s)
    Tagged
    0 Thread(s)
    Quote Originally Posted by r937
    that's an improvement, but i would wonder why the information architecture analysis resulted in so many levels
    Because it actually is the tree of life.

    I'm doing the project in such a way that it can be used to model any kind of information that has a tree-like structure, but the phylogeny of living things is the current impetus. And I just can't think of a better way to organize the data than using the current best-accepted structure. There are actually only about 16 different levels from the root to species in the largest chains, and some are shorter. We thought that there might be some need to go deeper than species in some places, so therefore the 20 estimate.

  9. #9
    SQL Consultant gold trophysilver trophybronze trophy
    r937's Avatar
    Join Date
    Jul 2002
    Location
    Toronto, Canada
    Posts
    39,347
    Mentioned
    63 Post(s)
    Tagged
    3 Thread(s)
    aha, i see, i didn't know that's actually what the application is, i assumed it was breadcrumbs for site navigation

    well, sure, now a deep tree makes sense

    good luck, and feel free to post again if you have any query problems
    rudy.ca | @rudydotca
    Buy my SitePoint book: Simply SQL
    "giving out my real stuffs"

  10. #10
    SitePoint Guru
    Join Date
    Nov 2004
    Location
    Parry Sound, ON
    Posts
    725
    Mentioned
    0 Post(s)
    Tagged
    0 Thread(s)
    Thanks, one more thing for now: Why am I doing a left outer join rather than a left join?

  11. #11
    SQL Consultant gold trophysilver trophybronze trophy
    r937's Avatar
    Join Date
    Jul 2002
    Location
    Toronto, Canada
    Posts
    39,347
    Mentioned
    63 Post(s)
    Tagged
    3 Thread(s)
    a left outer join is a left join

    the OUTER keyword is optional

    rudy.ca | @rudydotca
    Buy my SitePoint book: Simply SQL
    "giving out my real stuffs"

  12. #12
    SitePoint Guru
    Join Date
    Nov 2004
    Location
    Parry Sound, ON
    Posts
    725
    Mentioned
    0 Post(s)
    Tagged
    0 Thread(s)
    Sweet:
    Showing rows 0 - 0 (1 total, Query took 0.0006 sec)

    You rock dude.


Bookmarks

Posting Permissions

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