Breadcrumb help

[HardCoded]

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.

[r937]

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)

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)

[HardCoded]

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

[HardCoded]

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.

[r937]

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!!!!

[HardCoded]

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?

[r937]

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?

[HardCoded]

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.

[r937]

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

[HardCoded]

Thanks, one more thing for now: Why am I doing a left outer join rather than a left join?

[r937]

a left outer join is a left join

the OUTER keyword is optional

[HardCoded]

Sweet:
Showing rows 0 - 0 (1 total, Query took 0.0006 sec)

You rock dude.