method for making categories/subcategories.

[Brian]

Greetings,

I'm working on a project that involved that has need of a categorization
system. Logically speaking, the system will have elements, these elements
will belong to at least a single category, sometimes more, additionally,
categories may also be members of any number of categories.

Well -- Thats the vision at least. I'm looking for some pointers, tutorials,
white paper, napkins, whatever explaining how this can be done.

I'm working on currently having a database entry:

category
cat_id | cat_name

category_map
map_id | cat_id | child_of

Category map would have a many to 1 relationship with category, I think. 1
entry in category will point to multiple entries in category_map.

To build the category list, I would have to walk all the category elements,
search for any children, then search each of those children for child
matches. Could get ugly with all the lookups, caching the result would help,
but it would be nice if there was some way of doing this that I'm just not
seeing. ;)

If anyone has worked on something like this before, I would really really
appreciate some pointers on how to structure this.

Thanks much,

--Brian

[Brian]

Re: method for making categories/subcategories.

I hate this.. Just as I give up and go begging for help, I find something:

http://groups.google.com/groups?hl=en&lr=&ie=UTF-8&oe=UTF-8&newwindow=1&safe=off&selm=b6j91v%24k52%241%40maud.ifi.uio.no

"Brian" <cpnmscg02 (@) sneakemail.com> wrote in message
news:cZ1lb.5984 52$Oz4.601263@r wcrnsc54...[color=blue]
> Greetings,
>
> I'm working on a project that involved that has need of a categorization
> system. Logically speaking, the system will have elements, these elements
> will belong to at least a single category, sometimes more, additionally,
> categories may also be members of any number of categories.
>
> Well -- Thats the vision at least. I'm looking for some pointers,[/color]
tutorials,[color=blue]
> white paper, napkins, whatever explaining how this can be done.
>
> I'm working on currently having a database entry:
>
> category
> cat_id | cat_name
>
> category_map
> map_id | cat_id | child_of
>
> Category map would have a many to 1 relationship with category, I think. 1
> entry in category will point to multiple entries in category_map.
>
> To build the category list, I would have to walk all the category[/color]
elements,[color=blue]
> search for any children, then search each of those children for child
> matches. Could get ugly with all the lookups, caching the result would[/color]
help,[color=blue]
> but it would be nice if there was some way of doing this that I'm just not
> seeing. ;)
>
> If anyone has worked on something like this before, I would really really
> appreciate some pointers on how to structure this.
>
> Thanks much,
>
> --Brian
>
>[/color]

[Unleaded]

Re: method for making categories/subcategories.

Brian wrote:
[color=blue]
> I hate this.. Just as I give up and go begging for help, I find something:
>
> http://groups.google.com/groups?hl=e...aud.ifi.uio.no
>
> "Brian" <cpnmscg02 (@) sneakemail.com> wrote in message
> news:cZ1lb.5984 52$Oz4.601263@r wcrnsc54...
>[color=green]
>>Greetings,
>>
>>I'm working on a project that involved that has need of a categorization
>>system. Logically speaking, the system will have elements, these elements
>>will belong to at least a single category, sometimes more, additionally,
>>categories may also be members of any number of categories.
>>
>>Well -- Thats the vision at least. I'm looking for some pointers,[/color]
>
> tutorials,
>[color=green]
>>white paper, napkins, whatever explaining how this can be done.
>>
>>I'm working on currently having a database entry:
>>
>>category
>>cat_id | cat_name
>>
>>category_ma p
>>map_id | cat_id | child_of
>>
>>Category map would have a many to 1 relationship with category, I think. 1
>>entry in category will point to multiple entries in category_map.
>>
>>To build the category list, I would have to walk all the category[/color]
>
> elements,
>[color=green]
>>search for any children, then search each of those children for child
>>matches. Could get ugly with all the lookups, caching the result would[/color]
>
> help,
>[color=green]
>>but it would be nice if there was some way of doing this that I'm just not
>>seeing. ;)
>>
>>If anyone has worked on something like this before, I would really really
>>appreciate some pointers on how to structure this.
>>
>>Thanks much,
>>
>>--Brian
>>
>>[/color]
>
>
>[/color]

Hi Brian,

I'll give my AU 2c anyway.

Some people like to say that the simple 'parent_id, child_id' type
relationship isn't an intelligent enough solution, and is quite
inffefficent.

While this may be true for some cases, the fact is all the methods of
tree storage, you either shift the processing time to tree
generation-time, or shift it too creation time, and in the end if you
are using PHP to generate a listing, you still need to do some
processing on it!

In most of the programming that I've needed to do, creation/modification
times [of a tree] is essential, so doing complex rebuilds for the sake
of generation-time efficiency, isn't an option. A content management
system I've created has over 100,000 documents, each document
categorised by a large number of categories, which uses the simple
'parent, child' table relationship!

That said, for some of the 'solutions' stated in many of the alternative
tree storage documents, they are difficult to implement in simpler
DBMS's (such as MySQL) and generally just a waste of human time, even
though technically cool :).

The biggest issue with simple tree traversal is the DBMS quieries, as
you stated earlier, as you step down the tree you would need to do a
query to find children etc... Resulting in a minimum of one query per
category! Not very efficent.

The solution? Do it in PHP with ONE function (as I said before, if your
going to generate the tree in HTML or whatever, you will still need to
do some PHP anyway, so why not just trade the load from the DBMS, and
leave it up to the PHP thread), do the tree in ONE query.

Benifits:
- You can store a tree simply. Good old 'parent, child' thing.
- You only do one query.
- You leave the dirty work for PHP, and don't thrash the DBMS.
- You can modify the tree easily, relates to the first point.


For my example, let's say we have two tables.
- 'hierarchy' (category_id, child_category_ id) and
- 'category' (category_id, title)

The 'hierarchy' has a crap load of rows, and there is equally as many
categories.

-So to create a tree, first do a simply query, say.

$sql = "SELECT c.category_id, h.category_id AS parent_id, c.title
FROM heirarchy h, category c
WHERE h.child_categor y_id = c.category_id";


- This makes a rather large list, but who really cares.
- Now Stick it in an array.

$listing = Array ();
while($row = getrow($result) )
{

$listing[] = array(
'parent_id' => $row['parent_id'],
'category_id' => $row['category_id'],
'category_title ' => $row['title']
);
}

- Done the first part. Your DBMS loves you, all in one query.
- Time to generate the 'tree', you need a recursive PHP function for this.


// Create a function
function display_tree($p arent, $level, $array)
{

foreach ($array AS $node)
{
// Indent
for ($i = 0; $i < $level; $i++) $html .= '&nbsp;'

if ($parent == $node['parent_id'])
{

$html .= $row['category_title '].'<br />';

// Get the children of this node
$html .= display_tree($n ode['category_id'], ($level + 1), $array);


} // end parent

} // end foreach

return $html;

} // end display list


// Now use it
echo display_tree(0, 0, $listing);


Done!


That's my 2c. Hope it helps, just another solution to the problem. IMHO
it does the job really well, at least for me. I use this approach on a
tree with around ~3000 nodes and it only takes a few milliseconds to create.

[Unleaded]

Re: method for making categories/subcategories.

Brian wrote:
[color=blue]
> I hate this.. Just as I give up and go begging for help, I find something:
>
> http://groups.google.com/groups?hl=e...aud.ifi.uio.no
>
> "Brian" <cpnmscg02 (@) sneakemail.com> wrote in message
> news:cZ1lb.5984 52$Oz4.601263@r wcrnsc54...
>[color=green]
>>Greetings,
>>
>>I'm working on a project that involved that has need of a categorization
>>system. Logically speaking, the system will have elements, these elements
>>will belong to at least a single category, sometimes more, additionally,
>>categories may also be members of any number of categories.
>>
>>Well -- Thats the vision at least. I'm looking for some pointers,[/color]
>
> tutorials,
>[color=green]
>>white paper, napkins, whatever explaining how this can be done.
>>
>>I'm working on currently having a database entry:
>>
>>category
>>cat_id | cat_name
>>
>>category_ma p
>>map_id | cat_id | child_of
>>
>>Category map would have a many to 1 relationship with category, I think. 1
>>entry in category will point to multiple entries in category_map.
>>
>>To build the category list, I would have to walk all the category[/color]
>
> elements,
>[color=green]
>>search for any children, then search each of those children for child
>>matches. Could get ugly with all the lookups, caching the result would[/color]
>
> help,
>[color=green]
>>but it would be nice if there was some way of doing this that I'm just not
>>seeing. ;)
>>
>>If anyone has worked on something like this before, I would really really
>>appreciate some pointers on how to structure this.
>>
>>Thanks much,
>>
>>--Brian
>>
>>[/color]
>
>
>[/color]

Hi Brian,

I'll give my AU 2c anyway.

Some people like to say that the simple 'parent_id, child_id' type
relationship isn't an intelligent enough solution, and is quite
inffefficent.

While this may be true for some cases, the fact is all the methods of
tree storage, you either shift the processing time to tree
generation-time, or shift it too creation time, and in the end if you
are using PHP to generate a listing, you still need to do some
processing on it!

In most of the programming that I've needed to do, creation/modification
times [of a tree] is essential, so doing complex rebuilds for the sake
of generation-time efficiency, isn't an option. A content management
system I've created has over 100,000 documents, each document
categorised by a large number of categories, which uses the simple
'parent, child' table relationship!

That said, for some of the 'solutions' stated in many of the alternative
tree storage documents, they are difficult to implement in simpler
DBMS's (such as MySQL) and generally just a waste of human time, even
though technically cool :).

The biggest issue with simple tree traversal is the DBMS quieries, as
you stated earlier, as you step down the tree you would need to do a
query to find children etc... Resulting in a minimum of one query per
category! Not very efficent.

The solution? Do it in PHP with ONE function (as I said before, if your
going to generate the tree in HTML or whatever, you will still need to
do some PHP anyway, so why not just trade the load from the DBMS, and
leave it up to the PHP thread), do the tree in ONE query.

Benifits:
- You can store a tree simply. Good old 'parent, child' thing.
- You only do one query.
- You leave the dirty work for PHP, and don't thrash the DBMS.
- You can modify the tree easily, relates to the first point.


For my example, let's say we have two tables.
- 'hierarchy' (category_id, child_category_ id) and
- 'category' (category_id, title)

The 'hierarchy' has a crap load of rows, and there is equally as many
categories.

-So to create a tree, first do a simply query, say.

$sql = "SELECT c.category_id, h.category_id AS parent_id, c.title
FROM heirarchy h, category c
WHERE h.child_categor y_id = c.category_id";


- This makes a rather large list, but who really cares.
- Now Stick it in an array.

$listing = Array ();
while($row = getrow($result) )
{

$listing[] = array(
'parent_id' => $row['parent_id'],
'category_id' => $row['category_id'],
'category_title ' => $row['title']
);
}

- Done the first part. Your DBMS loves you, all in one query.
- Time to generate the 'tree', you need a recursive PHP function for this.


// Create a function
function display_tree($p arent, $level, $array)
{

foreach ($array AS $node)
{
// Indent
for ($i = 0; $i < $level; $i++) $html .= '&nbsp;'

if ($parent == $node['parent_id'])
{

$html .= $row['category_title '].'<br />';

// Get the children of this node
$html .= display_tree($n ode['category_id'], ($level + 1), $array);


} // end parent

} // end foreach

return $html;

} // end display list


// Now use it
echo display_tree(0, 0, $listing);


Done!


That's my 2c. Hope it helps, just another solution to the problem. IMHO
it does the job really well, at least for me. I use this approach on a
tree with around ~3000 nodes and it only takes a few milliseconds to create.

[Perttu Pulkkinen]

Re: method for making categories/subcategories.


"Brian" <cpnmscg02 (@) sneakemail.com> wrote in message
news:cZ1lb.5984 52$Oz4.601263@r wcrnsc54...[color=blue]
> Greetings,
> I'm working on a project that involved that has need of a categorization
> system. Logically speaking, the system will have elements, these elements
> will belong to at least a single category, sometimes more, additionally,
> categories may also be members of any number of categories.
> Well -- Thats the vision at least. I'm looking for some pointers,[/color]
tutorials,[color=blue]
> white paper, napkins, whatever explaining how this can be done.[/color]

I'm working with a product catalog system. My categories table is something
like this:

id
name
parent_id
generation

why I added generation? because I want to be sure that there are no
recursive categories where a is child of b and b is child of a.

when I add category, I 1) add it under some category with generation one
less than the parent OR 2) find the lowest generation that exists.

I made a category class in order to make sure that my operations go right
always.
Member functions like
category->insert
category->delete
category->destroy
should return true if successfull or false (and error message) if failure.

Other normal functions:
get_lowest_gen( ) returns lowest generation (integer)
get_children($c at_id) returns in array of integers the children of $cat_id
build_cat_tree( ) should order all categories - AND YOU DON'T NEED to do one
database query for every category. Just find the lowest generation then
start to recursively go trough every category in that generation
(get_children). Function needs perhaps to add some more indent to every
generation, if it prints something.

It is very good idea to test the class separately with as simple interface
as possible, in order to be sure.

[Brian]

Re: method for making categories/subcategories.

Wow, what a great post, thank you for taking the time to write that.

I'm going to take some time to absorb it, and I'll get back to you.

-Brian

"Unleaded" <unleaded@unlea dedonline.net.n 0spam> wrote in message
news:3F94B937.2 000804@unleaded online.net.n0sp am...[color=blue]
> Brian wrote:
>[color=green]
> > I hate this.. Just as I give up and go begging for help, I find[/color][/color]
something:[color=blue][color=green]
> >
> >[/color][/color]
http://groups.google.com/groups?hl=e...aud.ifi.uio.no[color=blue][color=green]
> >
> > "Brian" <cpnmscg02 (@) sneakemail.com> wrote in message
> > news:cZ1lb.5984 52$Oz4.601263@r wcrnsc54...
> >[color=darkred]
> >>Greetings,
> >>
> >>I'm working on a project that involved that has need of a categorization
> >>system. Logically speaking, the system will have elements, these[/color][/color][/color]
elements[color=blue][color=green][color=darkred]
> >>will belong to at least a single category, sometimes more, additionally,
> >>categories may also be members of any number of categories.
> >>
> >>Well -- Thats the vision at least. I'm looking for some pointers,[/color]
> >
> > tutorials,
> >[color=darkred]
> >>white paper, napkins, whatever explaining how this can be done.
> >>
> >>I'm working on currently having a database entry:
> >>
> >>category
> >>cat_id | cat_name
> >>
> >>category_ma p
> >>map_id | cat_id | child_of
> >>
> >>Category map would have a many to 1 relationship with category, I think.[/color][/color][/color]
1[color=blue][color=green][color=darkred]
> >>entry in category will point to multiple entries in category_map.
> >>
> >>To build the category list, I would have to walk all the category[/color]
> >
> > elements,
> >[color=darkred]
> >>search for any children, then search each of those children for child
> >>matches. Could get ugly with all the lookups, caching the result would[/color]
> >
> > help,
> >[color=darkred]
> >>but it would be nice if there was some way of doing this that I'm just[/color][/color][/color]
not[color=blue][color=green][color=darkred]
> >>seeing. ;)
> >>
> >>If anyone has worked on something like this before, I would really[/color][/color][/color]
really[color=blue][color=green][color=darkred]
> >>appreciate some pointers on how to structure this.
> >>
> >>Thanks much,
> >>
> >>--Brian
> >>
> >>[/color]
> >
> >
> >[/color]
>
> Hi Brian,
>
> I'll give my AU 2c anyway.
>
> Some people like to say that the simple 'parent_id, child_id' type
> relationship isn't an intelligent enough solution, and is quite
> inffefficent.
>
> While this may be true for some cases, the fact is all the methods of
> tree storage, you either shift the processing time to tree
> generation-time, or shift it too creation time, and in the end if you
> are using PHP to generate a listing, you still need to do some
> processing on it!
>
> In most of the programming that I've needed to do, creation/modification
> times [of a tree] is essential, so doing complex rebuilds for the sake
> of generation-time efficiency, isn't an option. A content management
> system I've created has over 100,000 documents, each document
> categorised by a large number of categories, which uses the simple
> 'parent, child' table relationship!
>
> That said, for some of the 'solutions' stated in many of the alternative
> tree storage documents, they are difficult to implement in simpler
> DBMS's (such as MySQL) and generally just a waste of human time, even
> though technically cool :).
>
> The biggest issue with simple tree traversal is the DBMS quieries, as
> you stated earlier, as you step down the tree you would need to do a
> query to find children etc... Resulting in a minimum of one query per
> category! Not very efficent.
>
> The solution? Do it in PHP with ONE function (as I said before, if your
> going to generate the tree in HTML or whatever, you will still need to
> do some PHP anyway, so why not just trade the load from the DBMS, and
> leave it up to the PHP thread), do the tree in ONE query.
>
> Benifits:
> - You can store a tree simply. Good old 'parent, child' thing.
> - You only do one query.
> - You leave the dirty work for PHP, and don't thrash the DBMS.
> - You can modify the tree easily, relates to the first point.
>
>
> For my example, let's say we have two tables.
> - 'hierarchy' (category_id, child_category_ id) and
> - 'category' (category_id, title)
>
> The 'hierarchy' has a crap load of rows, and there is equally as many
> categories.
>
> -So to create a tree, first do a simply query, say.
>
> $sql = "SELECT c.category_id, h.category_id AS parent_id, c.title
> FROM heirarchy h, category c
> WHERE h.child_categor y_id = c.category_id";
>
>
> - This makes a rather large list, but who really cares.
> - Now Stick it in an array.
>
> $listing = Array ();
> while($row = getrow($result) )
> {
>
> $listing[] = array(
> 'parent_id' => $row['parent_id'],
> 'category_id' => $row['category_id'],
> 'category_title ' => $row['title']
> );
> }
>
> - Done the first part. Your DBMS loves you, all in one query.
> - Time to generate the 'tree', you need a recursive PHP function for this.
>
>
> // Create a function
> function display_tree($p arent, $level, $array)
> {
>
> foreach ($array AS $node)
> {
> // Indent
> for ($i = 0; $i < $level; $i++) $html .= '&nbsp;'
>
> if ($parent == $node['parent_id'])
> {
>
> $html .= $row['category_title '].'<br />';
>
> // Get the children of this node
> $html .= display_tree($n ode['category_id'], ($level + 1), $array);
>
>
> } // end parent
>
> } // end foreach
>
> return $html;
>
> } // end display list
>
>
> // Now use it
> echo display_tree(0, 0, $listing);
>
>
> Done!
>
>
> That's my 2c. Hope it helps, just another solution to the problem. IMHO
> it does the job really well, at least for me. I use this approach on a
> tree with around ~3000 nodes and it only takes a few milliseconds to[/color]
create.[color=blue]
>
>[/color]

[Brian]

Re: method for making categories/subcategories.

Thanks for your thoughts on this, I'll have to review the logic and see how
it fits for me.

My biggest issue is the application I'm writing has the requirement of child
categories belonging to multiple parents


Cat1 Cat6
/\ /\
/ \ / \
cat2 Cat3 / Cat7
/ \---+---+------\--+
/ \ / \ |
cat4 cat5 cat8


Screwed up, eh?

I'm thinking that the system is going to have to be a complex php function
that generates the categorys, stores it as a hash, then retreieves the hash
vs. regenerating it. The cache would be cleared and regenerated whenever a
category modifications were made.

Again, thank you.

"Perttu Pulkkinen" <Perttu.Pulkkin en@co.jyu.fi> wrote in message
news:_94lb.49$m n2.46@read3.ine t.fi...[color=blue]
>
> "Brian" <cpnmscg02 (@) sneakemail.com> wrote in message
> news:cZ1lb.5984 52$Oz4.601263@r wcrnsc54...[color=green]
> > Greetings,
> > I'm working on a project that involved that has need of a categorization
> > system. Logically speaking, the system will have elements, these[/color][/color]
elements[color=blue][color=green]
> > will belong to at least a single category, sometimes more, additionally,
> > categories may also be members of any number of categories.
> > Well -- Thats the vision at least. I'm looking for some pointers,[/color]
> tutorials,[color=green]
> > white paper, napkins, whatever explaining how this can be done.[/color]
>
> I'm working with a product catalog system. My categories table is[/color]
something[color=blue]
> like this:
>
> id
> name
> parent_id
> generation
>
> why I added generation? because I want to be sure that there are no
> recursive categories where a is child of b and b is child of a.
>
> when I add category, I 1) add it under some category with generation one
> less than the parent OR 2) find the lowest generation that exists.
>
> I made a category class in order to make sure that my operations go right
> always.
> Member functions like
> category->insert
> category->delete
> category->destroy
> should return true if successfull or false (and error message) if failure.
>
> Other normal functions:
> get_lowest_gen( ) returns lowest generation (integer)
> get_children($c at_id) returns in array of integers the children of $cat_id
> build_cat_tree( ) should order all categories - AND YOU DON'T NEED to do[/color]
one[color=blue]
> database query for every category. Just find the lowest generation then
> start to recursively go trough every category in that generation
> (get_children). Function needs perhaps to add some more indent to every
> generation, if it prints something.
>
> It is very good idea to test the class separately with as simple interface
> as possible, in order to be sure.
>
>
>
>[/color]