(nested?) Select Query...

safra

Hi,

I have some data in sql format, the table has a column PARENT. Each entry has a parent apart from top level entries.

How can you get all level 3 entries that are part of a specific level 1 entry. The only way I can think of doing this is, first get all Level 2 entries with that specific Level 1 entry as a parent. Then go through all level 2 entries and find all Level 3 entries with these level 2 entries as the parent.

I just wonder if all this can this be done in a single query?

Thanks!

laserlight

safra wrote:
How can you get all level 3 entries that are part of a specific level 1 entry. The only way I can think of doing this is, first get all Level 2 entries with that specific Level 1 entry as a parent. Then go through all level 2 entries and find all Level 3 entries with these level 2 entries as the parent.

Yes, so the number of queries will be proportional to the number of levels, since you can go through all the entries for a given level in one query.

safra wrote:
I just wonder if all this can this be done in a single query?

Search the Web for "database modified preorder tree traversal algorithm".

safra

Thank you laserlight!

I did a search on "database modified preorder tree traversal algorithm" and read several articles about this. They all seem to have one thing in common, each record has a left and right index number applied. I cannot see how I can use this on my table. which looks like:

ID
Name
Parent

If either the left or right index would represent the parent then I belief I understand how to use it but that is not the case. They all seem to be unqiue numbers. In my case parent will hold the index of the entry one level higher...

safra

Seems something like this is what I need:

http://mikehillyer.com/articles/managing-hierarchical-data-in-mysql/

SELECT t1.name AS lev1, t2.name as lev2, t3.name as lev3, t4.name as lev4
FROM category AS t1
LEFT JOIN category AS t2 ON t2.parent = t1.category_id
LEFT JOIN category AS t3 ON t3.parent = t2.category_id
LEFT JOIN category AS t4 ON t4.parent = t3.category_id
WHERE t1.name = 'ELECTRONICS' AND t4.name = 'FLASH';

Weedpacket

safra wrote:
If either the left or right index would represent the parent then I belief I understand how to use it but that is not the case. They all seem to be unqiue numbers. In my case parent will hold the index of the entry one level higher...

They're used instead of a parent ID. I don't know which articles you were reading, but they should have described how the identifiers were used. The first two I picked out of a Google search certainly did, along with diagrams. So does the article you just linked to (and so does the article that article links to).

For example, all of the ancestors of a node N have a left-number less than N's left-number and greater than N's right-number (look at any of those diagrams of a numbered tree); the parent either has a left-number that is one less than N's left-number or a right-number that is one more than N's right-number.

safra

It is not that I completely do not understand this approach, all was explained in the articles I read. What I meant was, that we have purchased data in the specific format I mentioned so I don't think it is prepared to work with this left, right identifiers approach as this info is not in the file. Also, the parent data is not a nummeric unique field.

johanafm

safra;11010377 wrote:
so I don't think it is prepared to work with this left, right identifiers approach

Which does not mean you can't adapt the data to suit your needs. Alogrithms and data structures go hand in hand, so if you wish to use a specific algorithm to solve your problem, you will need to use the proper data structure as well. As you've allready discovered, you can solve your problem using the current data structure (only a parent id), but the queries to do this will be cumbersome and.

safra;11010377 wrote:
Also, the parent data is not a nummeric unique field.

which does not mean you can't assign a uniqie numeric field to the parent data to suit your needs. Once again, choose a structure that works for the algorithm.

Weedpacket

safra wrote:
What I meant was, that we have purchased data in the specific format I mentioned so I don't think it is prepared to work with this left, right identifiers approach as this info is not in the file.

But you can work it out from the data that is in the file. It's called programming - a useful skill for a programmer.

As a matter of fact the article you linked to says

Those of you who currently use the adjacency list model and would like to experiment with the nested set model will find sample code for converting between the two in the Storing Hierarchical Data in a Database resource listed below.