How to create a SELECT statement for this case

[zealus]

Imagine you have an online store. The depth of subcategories isn't limited, so you may get some items pretty close to the top and some all the way at the bottom. You want to display breadcrumbs, something like:

Root->Category1->SubCategory2->SubCategory3->Item256
Root->Category4->SubCategory5->SubCategory6->SubCategory7->SubCategory8 ->Item789

You have a table that stores your items, something like:
tblItems(
itemID longint,
itemName varchar(100),
parentCategory longint)

You have table for categories:
tblCategories(
catID longint,
catName varchar(100),
catParent longint)

If catParent = 0 it's a root category.

Question is - what's the most efficient way to build a SELECT query (or stored procedure, or - whatever you think is good) to get a full breadcrumb path out of database.
The only restriction - it must be solved on the side of the database, not in some code.

Any ideas? My dev teammates already puzzled, so I am bringing this here

[r937]

google "nested set model"

[Zealus.com]

google "nested set model"

You're making it too easy, I still want to hear about cursors and recursions.

[longneck]

not from here you won't. we avoid them like plague, only worse.

[r937]

The depth of subcategories isn't limited...

perhaps it should be

any more than a few, and your users will flee

how does 15 levels sound?

see Categories and Subcategories

[zealus]

Found this: http://dev.mysql.com/tech-resources/...ical-data.html to be an excellent primer, printed out and gave away to every developer in my company who said anything about cursors and/or recursions.

Thanks everyone for participating

[zealus]

how does 15 levels sound

Well, the problem is formulated in such a way to make it easier to relate to. We can talk about database storing file and folder information - now depth of 15 isn't all that crazy anymore, is it?

The sole reason was to give the problem some reality kick and listen to all the ideas.

[wwb_99]

Why must this be solved in the DB rather than in code? Databases are awesome and fast when you are doing square, set-based data. But once things go triangular, you get alot more mileage out of object models IMHO.

To offer my solution: I would have a very nasty, recursive set of queries to populate an object graph of some sort. Then I would cache said object graph and pull breadcrumbs and other heirarchical bits from said object graph.

[Zealus.com]

I would have a very nasty, recursive set of queries to populate an object graph of some sort. Then I would cache said object graph and pull breadcrumbs and other heirarchical bits from said object graph.

So basically you would mimic a nested set by using a coded object, right? Any advantages of this over other methods?

[wwb_99]

Several, presuming you can handle the caching successfully.

1) [Insert Programming Language] has several dozen flow control and logical constructs. SQL has a handful. You can do much, much more elegant things much, much more easily.
2) Should be faster than hitting the database because you are not making that remote request.
3) Should be more easily unit testable if you are into that sort of thing.
4) Architectually, it is much more sound. Your app talks to the object, your object is loaded from your database. Switch to backing this information in an XML file? You just need to change how the object is loaded. The application doesn't care how the sausage is made, just how it eats it.

[r937]

"caching the object graph" requires
1) that the entire hierarchy actually fits into main memory, and
2) synchronization mechanisms to refresh recently updated database data

but the concept is fabulous

i'm sort of doing the same thing in coldfusion by caching query results (i don't build a graph)

[zealus]

wwb_99,

the outline reminds me of LINQ, but my concerns are as follows:
1) [insert database name here] is much more suitable to control large data volumes, then any programming language. That's why databases were created in first place.
2) True that, but think of all the memory allocations. What if there's an instance per each user and you have thousands of users. Having two copies of database looks cheaper than having all the memory to accommodate so many requests
3) Don't see the difference, but maybe I am just not knowledgeable enough. Testing isn't my strongest point.
4) Architecturally, it's not that much different. Application talks to object, object talks to database. Yeah, there's one more round trip to database in this scenario, but a lot less memory consumed, and if you, like r937 pointed, are caching query results, not the whole database object, then it suddenly makes a lot more sense.

I am no guru, but from materials I've stumbled upon, that describe how eBay/Yahoo/Google databases and applications are built, I haven't seen anybody caching objects like you've described. Now, I am not saying you're wrong, I am suggesting that maybe your solutions wouldn't be as easily scalable.

What do you think?