How do I represent a Tree Structure in a mySQL table

Question

The tree has the following characteristics:

1. Each node can have multiple parents and multiple children.
2. The Parent nodes of a Node can have different depth.

Example

I am trying to represent a category structure such as the following:

Desktop and Mobile Applications

Desktop and Mobile Applications->Android Apps

Desktop and Mobile Applications->Android Apps->Games

Desktop and Mobile Applications->Android Apps->Games->Action

Desktop and Mobile Applications->Games

Desktop and Mobile Applications->Games->Action

Desktop and Mobile Applications->Games->Adventure

Desktop Applications

Desktop Applications->Games

Desktop Applications->Games->Action

Desktop Applications->Games->Adventure

IPhone Applications

Desktop Applications->Games

Desktop Applications->Games->Action

Desktop Applications->Games->Adventure

Tried using the Nested Set Algorithm and I end up with multiple "Games" categories with different categoryIDs and at different depths.

Any help with this will be much appreciated.

Answer 1

The simple way is to structure a table like:

Categories
CategoryID
ParentID
Name

Your data would look like:

1, 0, 'Desktop and Mobile Apps'
2, 1, 'Android Apps'
3, 2, 'Games'
4, 3, 'Action'
5, 1, 'Games'
6, 5, 'Action'
7, 5, 'Adventure'

8, 0, 'Desktop Apps'
9, 8, 'Games'

You would query it like: select * from Categories where ParentId = 1 which would return Android Apps and Games. To get the sub categories of games you would do select * from Categories where ParentId = 5 which would return action and adventure.

---

update In order to associate a single item with multiple categories you will want one additional table:

xref_CategoriesItems
CategoryId
ItemId

This would allow any single item to be associated with multiple categories. Let's say you have a desktop app that needs to appear with both Desktop Apps > Games and Desktop and Mobile Apps > Games.

Your table would have the following data for item 1:
3, 1
9, 1

When seeing what items were in a specific category you would do the following:

select I.*
  from items I
    inner join xref_CategoriesItems XCI on (XCI.ItemId = I.ItemID)
  WHERE (XCI.Category = @CategoryId)

To see which categories a specific item falls under:

select C.*
  from categories C
    inner join xref_CategoriesItems XCI on (XCI.CategoryId = C.CategoryId)
  where (XCI.ItemId = @ItemId)

The query for all items under a specific category is a little more complex if you need all of the child records. Basically you need to do a recursive join the xref_categories with the categories to get the children. I don't remember how to express that in MySQL's version of sql; however the following might be good to know: Using MySQL query to traverse rows to make a recursive tree