[PHP] Category and sub-category logic

[Chris W. Parker]

Ryan A <mailto:ryan@jumac.com>
on Thursday, August 14, 2003 3:21 PM said:

Read this [url]http://www.sitepoint.com/article/1105[/url] and you will know what
you should do.

The database organization you want to use is called Modified Preorder
Tree Traversal. It takes only one table to create all the relationships
needed.

If you have any questions about this technique send me an email as I've
got some experience with this method.


Chris.

p.s. The easiest way (I think) to learn this method is to actually use
your own data and draw it out on a piece of paper (as opposed to trying
to visualize the map in your head).

[Chris W. Parker]

David Otton <mailto:phpmail@jawbone.freeserve.co.uk>
on Thursday, August 14, 2003 4:58 PM said:

> The advantage of doing it this way is that your tree structure is
> generic and can have many levels. The disadvantage is that you may
> need many SQL queries to fully traverse the tree (though people
> rarely want to do this, and sub-selects, clever joins or post-query
> processing can reduce the overhead).

Which is why you should use the Modified Preorder Tree Traversal method
instead. With that method you've got one table that defines the
categories AND their relationships to each other.

Your SQL queries end up looking something like this.

SELECT name
FROM categories
WHERE lft >= x
AND rgt <= y



Chris.

[Cpt John W. Holmes]

From: "Mark" <mark_weinstock@yahoo.com>

> I'm trying to get a handle on this algorithm as well. If you add
> additional children to a parent record, doesn't that require
> renumbering all the rgt and lft values in the lineage? For example
> (table shamelessly stolen from a website):
>
> Personnel
> emp lft rgt
> ======================
> 'Albert' 1 12
> 'Bert' 2 3
> 'Chuck' 4 11
> 'Donna' 5 6
> 'Eddie' 7 8
> 'Fred' 9 10
>
> If I want to add 'Joe' as a subordinate to 'Fred', doesn't that mean
> I have to change the lft values for Fred, Chuck, and Albert? Yes,
> deleting definitely seems easier. I'm curious about adding...

Yes, you will have to update all of the right and left numbers to the right
(or higher) than the node where you are inserting. Deleting is basically the
same method done in reverse, but can get complicated when you delete a node
and have to determine what to do with the children.

I'd recommend, if you're really interested in this, to do some searching on
nested set tutorials. You could specifically search for Joe Celko who has
written a lot of information on the topic.

While it seems like a big deal to have to update all of the numbers, it's
really not. It can be done with a single query (with subselects). Yes, it's
more costly than inserting a name into an adjacentcy list model, but it's
worth it for all that you gain from the nested set model.

---John Holmes...

[Richard Baskett]

Wouldn¹t it just be easier to do a relationship table as in

Personnel
emp ID parent
========================
'Albert' 1 0
'Bert' 2 1
'Chuck' 3 1
'Donna' 4 0
'Eddie' 5 4
'Fred' 6 0
'Joe' 7 6

This way you know the ID of the person and the parentID if they have one,
otherwise they are a 0 which means they are the parent.. Seems like this
would be a much easier way of doing it doesn¹t it? And only one SQL
query...

Rick

"The only way to have a friend is to be one." - Ralph Waldo Emerson

> From: Mark <mark_weinstock@yahoo.com>
> Date: Fri, 15 Aug 2003 07:18:41 -0700 (PDT)
> To: "Chris W. Parker" <cparker@swatgear.com>
> Cc: [email]php-general@lists.php.net[/email]
> Subject: RE: [PHP] Category and sub-category logic
>
> I'm trying to get a handle on this algorithm as well. If you add
> additional children to a parent record, doesn't that require
> renumbering all the rgt and lft values in the lineage? For example
> (table shamelessly stolen from a website):
>
> Personnel
> emp lft rgt
> ======================
> 'Albert' 1 12
> 'Bert' 2 3
> 'Chuck' 4 11
> 'Donna' 5 6
> 'Eddie' 7 8
> 'Fred' 9 10
>
> If I want to add 'Joe' as a subordinate to 'Fred', doesn't that mean
> I have to change the lft values for Fred, Chuck, and Albert? Yes,
> deleting definitely seems easier. I'm curious about adding...
>
> Mark
>
>
>
> --- "Chris W. Parker" <cparker@swatgear.com> wrote:

>> David Otton <mailto:phpmail@jawbone.freeserve.co.uk>
>> on Thursday, August 14, 2003 4:58 PM said:
>>

>>> The advantage of doing it this way is that your tree structure is
>>> generic and can have many levels. The disadvantage is that you

>> may

>>> need many SQL queries to fully traverse the tree (though people
>>> rarely want to do this, and sub-selects, clever joins or

>> post-query

>>> processing can reduce the overhead).

>>
>> Which is why you should use the Modified Preorder Tree Traversal
>> method
>> instead. With that method you've got one table that defines the
>> categories AND their relationships to each other.
>>
>> Your SQL queries end up looking something like this.
>>
>> SELECT name
>> FROM categories
>> WHERE lft >= x
>> AND rgt <= y
>>
>>
>>
>> Chris.
>>
>> --
>> PHP General Mailing List (http://www.php.net/)
>> To unsubscribe, visit: http://www.php.net/unsub.php
>>

>
>
> =====
> Mark Weinstock
> mark_weinstock@yahoo.com
> ***************************************
> You can't demand something as a "right" unless you are willing to fight to
> death to defend everyone else's right to the same thing.
> ***************************************
>
> __________________________________
> Do you Yahoo!?
> Yahoo! SiteBuilder - Free, easy-to-use web site design software
> http://sitebuilder.yahoo.com
>
> --
> PHP General Mailing List (http://www.php.net/)
> To unsubscribe, visit: http://www.php.net/unsub.php
>

[Mark]

--- "CPT John W. Holmes" <holmes072000@charter.net> wrote:

> From: "Mark" <mark_weinstock@yahoo.com>
>
>

> > I'm trying to get a handle on this algorithm as well. If you add
> > additional children to a parent record, doesn't that require
> > renumbering all the rgt and lft values in the lineage? For

> example

> > (table shamelessly stolen from a website):
> >
> > Personnel
> > emp lft rgt
> > ======================
> > 'Albert' 1 12
> > 'Bert' 2 3
> > 'Chuck' 4 11
> > 'Donna' 5 6
> > 'Eddie' 7 8
> > 'Fred' 9 10
> >
> > If I want to add 'Joe' as a subordinate to 'Fred', doesn't that

> mean

> > I have to change the lft values for Fred, Chuck, and Albert? Yes,
> > deleting definitely seems easier. I'm curious about adding...

>
> Yes, you will have to update all of the right and left numbers to
> the right
> (or higher) than the node where you are inserting. Deleting is
> basically the
> same method done in reverse, but can get complicated when you
> delete a node
> and have to determine what to do with the children.
>
> I'd recommend, if you're really interested in this, to do some
> searching on
> nested set tutorials. You could specifically search for Joe Celko
> who has
> written a lot of information on the topic.

Thanks. I'll take a look. I'm considering changing to this algorithm
from my basic parent-ID table.

>
> While it seems like a big deal to have to update all of the
> numbers, it's
> really not. It can be done with a single query (with subselects).
> Yes, it's
> more costly than inserting a name into an adjacentcy list model,
> but it's
> worth it for all that you gain from the nested set model.
>
> ---John Holmes...
>
>
> --
> PHP General Mailing List ([url]http://www.php.net/[/url])
> To unsubscribe, visit: [url]http://www.php.net/unsub.php[/url]
>

=====
Mark Weinstock
[email]mark_weinstock@yahoo.com[/email]
***************************************
You can't demand something as a "right" unless you are willing to fight to death to defend everyone else's right to the same thing.
***************************************

__________________________________
Do you Yahoo!?
Yahoo! SiteBuilder - Free, easy-to-use web site design software
[url]http://sitebuilder.yahoo.com[/url]

[Cpt John W. Holmes]

From: "Richard Baskett" <php@baskettcase.com>

> Wouldn¹t it just be easier to do a relationship table as in
>
> Personnel
> emp ID parent
> ========================
> 'Albert' 1 0
> 'Bert' 2 1
> 'Chuck' 3 1
> 'Donna' 4 0
> 'Eddie' 5 4
> 'Fred' 6 0
> 'Joe' 7 6
>
> This way you know the ID of the person and the parentID if they have one,
> otherwise they are a 0 which means they are the parent.. Seems like this
> would be a much easier way of doing it doesn¹t it? And only one SQL
> query...

Possibly. It depends on what you're trying to model. We're getting way off
topic for PHP, though.

What you gave above is called an adjacency list model and the other example
given was a nested set (or tree) model. Each has it's advantages and
disadvantages. I recommend counsulting your good friend Google if you're
interested in the details. :)

---John Holmes...

[Ryan A]

Hey,
Sorry I didnt reply, was having some computer problems.
Thanks for the link and the advise, will look into it.
Cheers,
-Ryan


We will slaughter you all! - The Iraqi (Dis)information ministers site
[url]http://MrSahaf.com[/url]


----- Original Message -----
From: "Chris W. Parker" <cparker@swatgear.com>
To: "David Otton" <phpmail@jawbone.freeserve.co.uk>; "Ryan A"
<ryan@jumac.com>
Cc: <php-general@lists.php.net>
Sent: Friday, August 15, 2003 2:04 AM
Subject: RE: [PHP] Category and sub-category logic

> David Otton <mailto:phpmail@jawbone.freeserve.co.uk>
> on Thursday, August 14, 2003 4:58 PM said:
>

> > The advantage of doing it this way is that your tree structure is
> > generic and can have many levels. The disadvantage is that you may
> > need many SQL queries to fully traverse the tree (though people
> > rarely want to do this, and sub-selects, clever joins or post-query
> > processing can reduce the overhead).

>
> Which is why you should use the Modified Preorder Tree Traversal method
> instead. With that method you've got one table that defines the
> categories AND their relationships to each other.
>
> Your SQL queries end up looking something like this.
>
> SELECT name
> FROM categories
> WHERE lft >= x
> AND rgt <= y
>
>
>
> Chris.
>
> --
> PHP General Mailing List (http://www.php.net/)
> To unsubscribe, visit: http://www.php.net/unsub.php
>
>