Least intensive way to find all nested subcategories using mysql query

Question

I have a database in which items are placed into categories. Some of these categories are nested, so as an example:

Animals > Birds > Parrots  
Animals >  Birds > Penguin 
Animals > Mammals > Cats  
Animals > Mammals > Dogs 
Animals > Reptiles > Snakes 
Plants > Trees 
Plants > Flowers

etc

I have these in a table along the lines of

CATEGORY    PARENT
Animals     -
Birds       Animals
Penguin     Birds

etc

I'd like to be able to take the starting point of say, Animals and list all of the subcategories that come under that, so for animals we would have listed Birds, Mammals, Reptiles, Parrots, Penguin, Cats, DOgs, Snakes

Is this possible with a single qury? If not, what would I need to do

TIA

Answer 1

SQL is notoriously bad at traversing hierarchical data.

I would program this and recursively or iteratively find all children.

the following pseudo code should work (if there are no loops in the data)

• add children of animals to array A
• index = 0
• while index < length(A)
  • append children(A[i]) to array
  • index = index + 1

If there are loops in the hierarchy you must make sure you do not append children which are already in the array or the loop will consume all memory and crash

Answer 2

It is possible and efficient to do this with a single query if you add some hierarchy metadata to your schema.

Add two integer columns (start and end) to your category table. Then do a depth-first traversal of your tree incrementing a counter at each step and assigning the counter value to start when entering a node and to end when leaving (i.e. when all it's children have been processed).

So for your example, with the values shown as (start,end):

Animals (1,18)
   Birds (2,7)
      Parrots (3,6 )
      Penguin (4,5)
   Mammals (8,13)
      Cats (9,12)
      Dogs (10,11)
   Reptiles (14,17)
      Snakes (15,16)
Plants (19,24)
   Trees (20,23)
   Flowers (21,22)

Now to select get Animals and it's children you can just run something like this query:

SELECT * FROM Category where start >=1 and start < 18

You obviously have weigh the cost of rebuilding the metadata when the hierarchy changes against the efficiency for read queries. For relatively static hierarchies this technique works fairly well.

Answer 3

You can get away of recursion and use single queries to find child count, immediate categories and subcategories within using single SQL query by following the "Modified Preorder Tree Traversal" article below:

1. Managing Hierarchical Data in MySQL

Search google.com for the keywords "Modified Tree Traversal + Sitepoint" to read the an article on sitepoint.com that explains the same pattern.