Handling Infinite Category Depth

jon3k

I've got a table:
id - int, autonumber
parent_id = int
categorytitle = varchar(50)
depth = int

I've written a query using a reflexive relationship that produces the necessary output:

select fields from table inner join same_table alias on alias.parent_id = table.id

This joins each record with its parent record. The only problem I have is correctly ordering and grouping the result set to prepare it for the easiest (one pass) output possible.

Has anyone ever done anything like this? I did some searching (here and google) and didn't find anything specific to what I'm trying to do.

Basically, I want to be able to maintain an infinite level of depth, retreive it with a single query, and output it easily.

Any information would definitely be appreciated.

eoghain

You should be able to just order by the parent_id since each parent will have to exist before it's child.

jon3k

Unfortunatly its not that easy.

Consider thes records:

ID - Parent_ID - Depth - Title

1 - 0 - 1 - Cars
2 - 0 - 1 - Boats
3 - 1 - 2 - Audi
4 - 1 - 2 - BMW
5 - 1 - 2 - Ferrari
6 - 2 - 2 - SeaRay
7 - 2 - 2 - Merlin
8 - 5 - 3 - 360 Modena
9 - 4 - 3 - M3
10 - 5 - 3 - 550 Barchetta

If you ordered that by Category.Parent_ID you get:
Boats - Merlin
Cars - Ferrari
Cars - Audi
Boats - SeaRay
Cars - BMW
BMW - M3
Ferrari - 550 Marchetta
Ferrari - 360 Modena

I need it in this format:
Boats - Merlin
Boats - SeaRay
Cars - Ferrari
--Ferrari - 550 Marchetta
--Ferrari - 360 Modena
Cars - Audi
Cars - BMW
--BMW - M3

So each branch in the tree is ordered (Cars -> BMW - M3). Sorting by parent_id won't create the proper order.

nemonoman

You wish you had a database command like Oracle's "CONNECT BY" which handles this kind of thing, but apparently you don't have this sort of command. So you will have to do some PHP programming to handle the returned values.

This is a fairly simple loop:
SELECT a row
Get the id value
SELECT the children having that ID and loop...

etc.

Your challenge will be to create arrays of information from these values, and then managing the arrays. These arrays will be designed based on your program's needs, and they will be up to you to figure out. But the basic looping required for a parent-child relationship is pretty simple and a basic part of database programming.

PS there are 2 approaches to this problem: Drill down from a top component: This has the possibilty of near infinite looping. Alternate is roll up from a predefined lower level component or component level. This is a finite problem. Oracle's CONNECT BY statement is based on this second method, which is much easier to program, as you can predefine the number of columns in a returned row.

Typical use of this is a 'parts list': This part is made up these 5 smaller components, each of which is made of smaller components, etc. 1 component might appear in 200 parts, etc.

Database designers I have known call this a 'guzintaa*' relationship,

This part guzinta that part, that part guzinta another part, etc.

*guzinta == 'goes in to'

Roger_Ramjet

Infinite recursion sounds very attractive untill you try and use it in a database, as you are discovering. In relational database terms what you have created for yourself is a fan trap . Each parent has many children, which in turn have many children, etc. A definite no-no. You need to rethink your approach to this or deal with it in code; it is not possible to do so in standard SQL.

Before Oracle developed such usefull extentions, nemonoman's parts list problem had to be done through full normalisation of the data. Additional entities would be created to break down the M:N relations, the 'fan-traps and 'chasm-traps'. A whole list of assemblies and sub-assemblies were required such that one could finally return a full parts-list for an item or component, and also return the list of items that an individual part was used in.

If it was only 3 or 4 levels of recursion then one would simply store parent and grandparent, etc along with each child record; or do multiple joins with additional aliases. As it is, if you order by parent_id and by level you will have a reasonably well ordered result set to work on with your arrays.

kpzani

I have encountered a similar problem when creating a forum style system as the client wanted to be able to branch conversations at any level.

The most efficient fix I found was to add a field called nochildren default 0.

then work through like this

select fields from table where parent_id=0
while record = get record
output record details
if record[nochildren] > 1
get all children records using recursive function
end if
end while

you can also then optimise the query a little by using the limit statement.

I found this method pretty rapid. it sounds dogged but php/mysql is so fast the end result was better than most large static sites.

jon3k

Well I guess that answers the question, apparently there isn't a way to order this using a single SQL select. I was hoping to avoid a complex loop, where I took my result set, and made multiple passes, checking the current parent_id, then outputting the children. You end up making an absurd number of passes, possibly as many as N * N, unless I removed each found record from the result set, then each pass would be N-1 and speed up incrimentally as it progressed.

I've found a couple ways to work around this in the application, so its really a non-issue. Any place that needs the entire category tree output will simply be generated statically as a php include which contains a pre-built array. It will then be re-built each time a category is added or changed, which would be fairly infrequently.

Thanks for your help, this has been very interesting!!