473,326 Members | 2,081 Online
Bytes | Software Development & Data Engineering Community
Post Job

Home Posts Topics Members FAQ

Join Bytes to post your question to a community of 473,326 software developers and data experts.

method for making categories/subcategories.

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
Jul 17 '05 #1
6 18206
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.598452$Oz4.601263@rwcrnsc54...
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

Jul 17 '05 #2
Brian wrote:
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.598452$Oz4.601263@rwcrnsc54...
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



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_category_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($parent, $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($node['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.
Jul 17 '05 #3
Brian wrote:
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.598452$Oz4.601263@rwcrnsc54...
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



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_category_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($parent, $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($node['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.
Jul 17 '05 #4

"Brian" <cpnmscg02 (@) sneakemail.com> wrote in message
news:cZ1lb.598452$Oz4.601263@rwcrnsc54...
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 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($cat_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.


Jul 17 '05 #5
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" <un******@unleadedonline.net.n0spam> wrote in message
news:3F**************@unleadedonline.net.n0spam...
Brian wrote:
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.598452$Oz4.601263@rwcrnsc54...
Greetings,

I'm working on a project that involved that has need of a categorization
system. Logically speaking, the system will have elements, these elementswill 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. 1entry 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 notseeing. ;)

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

Thanks much,

--Brian



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_category_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($parent, $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($node['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.

Jul 17 '05 #6
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" <Pe**************@co.jyu.fi> wrote in message
news:_9*************@read3.inet.fi...

"Brian" <cpnmscg02 (@) sneakemail.com> wrote in message
news:cZ1lb.598452$Oz4.601263@rwcrnsc54...
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 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($cat_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.

Jul 17 '05 #7

This thread has been closed and replies have been disabled. Please start a new discussion.

Similar topics

2
by: Troy Lynch | last post by:
I'm working on writing a website which I need to have lists of products listed in categories and subcategories, and need to keep track of whats in the tree. Like how many products from the root all...
4
by: Bill | last post by:
I've got a bookstore I'm developing, and I wanted to list all the categories on the home page of the site. However, there are so many, that they now extend way below the screen, making the page...
0
by: Ralph Guzman | last post by:
TASK: I have to generate a report with all categories, subcategories and products in database. PROBLEM: I want to write one query that will return: 1. category 2. subcategory: determined by...
1
by: Neil McGuigan | last post by:
Hi, I want to store product categories in my db and am a little lost as to where to start. They can be hierarchical, such as "Books" > "Cook Books", so my table is like this: int...
13
by: hornedw | last post by:
I have been working on a ecommerce website for myself. What I needed some assistance on was when i was trying to display the categories/subcategories for the different products. I decided to use...
4
by: Drew | last post by:
I posted this to the asp.db group, but it doesn't look like there is much activity on there, also I noticed that there are a bunch of posts on here pertaining to database and asp. Sorry for...
3
Staria
by: Staria | last post by:
Hi... I'm currently working on a project where I would like to have Categories and SubCategories. I've banged my head on this for several days, but can't seem to get this the way I want it to...
2
by: DotNetNewbie | last post by:
Hello, I need to display a list of categories on the left side of a page, and I am confused how I would do this using a List Control (as appose to weaving my own HTML on the server side). My...
2
by: itpvision | last post by:
Hello, I have a link navigation of categories retrieved from the database, while I know how to display subcategories based on category link clicked with classical approach, I want to do this with...
0
by: DolphinDB | last post by:
Tired of spending countless mintues downsampling your data? Look no further! In this article, you’ll learn how to efficiently downsample 6.48 billion high-frequency records to 61 million...
0
by: ryjfgjl | last post by:
ExcelToDatabase: batch import excel into database automatically...
0
isladogs
by: isladogs | last post by:
The next Access Europe meeting will be on Wednesday 6 Mar 2024 starting at 18:00 UK time (6PM UTC) and finishing at about 19:15 (7.15PM). In this month's session, we are pleased to welcome back...
1
isladogs
by: isladogs | last post by:
The next Access Europe meeting will be on Wednesday 6 Mar 2024 starting at 18:00 UK time (6PM UTC) and finishing at about 19:15 (7.15PM). In this month's session, we are pleased to welcome back...
0
by: Vimpel783 | last post by:
Hello! Guys, I found this code on the Internet, but I need to modify it a little. It works well, the problem is this: Data is sent from only one cell, in this case B5, but it is necessary that data...
1
by: PapaRatzi | last post by:
Hello, I am teaching myself MS Access forms design and Visual Basic. I've created a table to capture a list of Top 30 singles and forms to capture new entries. The final step is a form (unbound)...
1
by: CloudSolutions | last post by:
Introduction: For many beginners and individual users, requiring a credit card and email registration may pose a barrier when starting to use cloud servers. However, some cloud server providers now...
1
by: Shællîpôpï 09 | last post by:
If u are using a keypad phone, how do u turn on JavaScript, to access features like WhatsApp, Facebook, Instagram....
0
by: af34tf | last post by:
Hi Guys, I have a domain whose name is BytesLimited.com, and I want to sell it. Does anyone know about platforms that allow me to list my domain in auction for free. Thank you

By using Bytes.com and it's services, you agree to our Privacy Policy and Terms of Use.

To disable or enable advertisements and analytics tracking please visit the manage ads & tracking page.