Best method for flexible sub-categories?? 1

[Sleidia]

Hi

I'm sorry .... I need help again

This time, I'm trying to build a navigation menu showing products categories with infinite levels of sub-categories.

First, I decided to use a table this way :

cat_ID | cat_level   | cat_name 
1      | 01.02       | A
2      | 02.02.02    | B
3      | 02          | C
4      | 01.01       | D
5      | 02.02.01    | E
6      | 02.02       | F
7      | 01          | G
8      | 02.02.02.01 | H
9      | 01.02.01    | I
10     | 02.01       | J

Then,

SELECT * FROM my_table ORDER BY cat_level, cat_name ASC

... would produce this :

G ( O1 )
    D ( 01.01 )
    A ( 01.02 )
        I ( 01.02.01 )
C ( 02 )
    J ( 02.01 )
    F ( 02.02 )
        E ( 02.02.01 )
        B ( 02.02.02 )
            H ( 02.02.02.01 )

It's good because the directory structure is respected but the problem is
that I also want to have all the subcategories listed in alphabetical order.
A should appear before D, F before J and B before E.

Then, I decided to change cat_level like this :

cat_ID | cat_level   | cat_name 
1      | 01.01       | A
2      | 02.02.03    | B
3      | 02          | C
4      | 01.01       | D
5      | 02.02.03    | E
6      | 02.02       | F
7      | 01          | G
8      | 02.02.03.04 | H
9      | 01.02.03    | I
10     | 02.02       | J

... which should output :

G ( O1 )
    A ( 01.01 )
    D ( 01.01 )
        I ( 01.02.03 )
C ( 02 )
    F ( 02.02 )
    J ( 02.02 )
        B ( 02.02.03 )
        E ( 02.02.03 )
            H ( 02.02.03.04 )

It looks like I've reached my 2 goals except that I also want to be able to easily retrieve the full tree directory path of any subcategory.

For example, using E, I want to output C > J > E
Using H, I want to output C > J > E > H
... and so on.

Now the problem is that this third goal seems impossible to reach with this method when it was possible with the first one.

So, my question (finally!) is : by what method could I achieve all the 3 goals?

Anyway, thanks a lot for helping !

 

[r937]

infinite levels? no can do

some maximum number, like thirty-seven levels? can do

(although if you show me a breadcrumb trail on a web page with thirty-seven levels, there's no way i'm browsing that site)


you might alternatively have a look at joe celko's nested set model to store your data


r937.com | rudy.ca

 

[Sleidia]

Well, by infinite, I meant : not a fixed number.
But I'm sure you did understand

I think that five sub-levels would be enough but I want all the categories and sub-categories to be in the same table. No cross-table manipulation.

I'll check the nested set thingy. Thanks for that.

 

[r937]

five levels is almost trivial, all you need is five LEFT OUTER JOINs (and mysql can handle many times that number easily)

furthermore you need not store the path (which is redundant, actually), just the parent of each row

this model is called adjacency or adjacency list model

let me know if you want to see the queries -- there's one query for displaying a total site map, which starts at the top of the hierarchies (roots), and there's another query for finding the breadcrumb (path to root) for any entry

r937.com | rudy.ca

 

[Sleidia]

Thanks Rudy

Sincerely, you would made me a huge favor if you could post the query and a small example of the data structure.

My ADSL connection has been broken for days and I'm currently posting by using a costly GPRS connection via my mobile phone .... yeah it can be that bad

Cheers

 

[guelphdad]

http://www.sqlsummit.com/AdjacencyList.htm

is an excerpt from Joe's book Trees and Hierarchies in SQL for Smarties.

 

[r937]

thanks, guelphdad, the link i had actually predates his book --

http://searchoracle.techtarget.com/tip/1,289483,sid41_gci1072361,00.html

sleidia, i'll post the queries soon

r937.com | rudy.ca

 

[r937]

okay, i've written up the queries here --

http://sqllessons.com/categories.html

let me know if you have any questions

r937.com | rudy.ca

 

[guelphdad]

Great stuff Rudy. Yes I've seen the link you have posted above to Joe's work. I think you pointed his work out to me.


Nice article you have written there.

 

[Sleidia]

Thanks again for this great help.
It's really appreciated since I still don't have the internet working ( I've copied your page locally on my comp ).

Anyway, if you allow me to say so, there is only one drawback to your method : it's not scalable in its actual form. You have to know in advance how many nodes you need to explore.

To make it totally scalable, you have to add a query that counts all the nodes in order to dynamically build the main query afterwards.

Nothing too difficult though.
But I would have prefered to use only one query.

Thanks again !

 

[r937]

that's quite true

however, there is another approach, and that is to restrict the number of levels, using application logic

i.e. if you want to have no more than 4 levels, then you simply reject any attempt to insert a subcategory at the 5th level

i'm not suggesting that this strategy makes sense everywhere, but if you're talking about a web site navigation bar, for example, you definitely want to restrict the depth

r937.com | rudy.ca

 

[Sleidia]

Hi again Rudy

I'm not sure if you're still with us or not (maybe on holiday!) but I have one question, if you don't mind.

I managed to do what I needed thanks to your explanation, (

http://sqllessons.com/categories.html

) but now, I would like to know what query you would use if you wanted to count the number of childs of any specific node (ie: the total number of nodes and leaves that are under "doggie").

Anyway, in case someone is interested, here is the PHP code I made in order to generate a query that can manage an unknown number of nodes :

// - ! - count number of levels
$sql_query[1] = "SELECT COUNT(cat_ID) AS levels_total FROM ecom_categories WHERE cat_parent_ID IS NULL";

// - ! - build query according to levels number
$sql_query[1] = "
SELECT 
";

    for ($k=0; $k < $levels_total; $k++) {

    $sql_query[1] .= "
    level" . $k . ".cat_ID AS level" . $k . "_ID, 
    level" . $k . ".cat_parent_ID AS level" . $k . "_parent_ID, 
    level" . $k . ".cat_name AS level" . $k . "_name 
    ";
    
        if ($k != ($levels_total - 1)) $sql_query[1] .= ", ";
    
    }

$sql_query[1] .= "    
FROM ecom_categories 
AS level0 
";

    for ($k=1; $k < $levels_total; $k++) {

    $sql_query[1] .= "
    LEFT OUTER 
    JOIN ecom_categories AS level" . $k . " 
    ON level" . $k . ".cat_parent_ID = level" . ($k - 1) . ".cat_ID 
    ";
    
    }

$sql_query[1] .= "
WHERE level0.cat_parent_ID IS NULL 
ORDER BY 
";    
   
    for ($k=0; $k < $levels_total; $k++) {

    $sql_query[1] .= "level" . $k . "_name ";
    
        if ($k != ($levels_total - 1)) $sql_query[1] .= ", ";
    
    }

... which produces this :

SELECT level0.cat_ID AS level0_ID, level0.cat_parent_ID AS level0_parent_ID, level0.cat_name AS level0_name, level1.cat_ID AS level1_ID, level1.cat_parent_ID AS level1_parent_ID, level1.cat_name AS level1_name, level2.cat_ID AS level2_ID, level2.cat_parent_ID AS level2_parent_ID, level2.cat_name AS level2_name, level3.cat_ID AS level3_ID, level3.cat_parent_ID AS level3_parent_ID, level3.cat_name AS level3_name
FROM ecom_categories AS level0
LEFT OUTER JOIN ecom_categories AS level1 ON level1.cat_parent_ID = level0.cat_ID
LEFT OUTER JOIN ecom_categories AS level2 ON level2.cat_parent_ID = level1.cat_ID
LEFT OUTER JOIN ecom_categories AS level3 ON level3.cat_parent_ID = level2.cat_ID
WHERE level0.cat_parent_ID IS NULL
ORDER BY level0_name, level1_name, level2_name, level3_name

 

[r937]

that's pretty neat

r937.com | rudy.ca

 

[Sleidia]

Not neat at all, actually

In fact, the first query doesn't count the real number of levels.
It only counts the number of main categories. My bad ! ;(

I had to make $levels_total an arbitrary number for the script to work as expected.