How do I represent a Tree Structure in a mySQL table

Question

The tree has the following characteristics:

Each node can have multiple parents and multiple children.
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.

score 2 · Answer 1 · edited May 23 '17 at 11:53

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

I have been able to get this far, however, the same category "Games" now has two CatIDs - 3 & 5. this creates two difficulties for me. 1) I now have to associate every product in Cat3 with Cat5 as well. This creates duplicity and data overhead. 2) Creating new categories is a difficult process since we cannot really leverage a category that exists. We need to create all categories from scratch and then associate products with them. --- If there is a way to store "Games" with a single ID then I would avoid the above complexity. — Amar Mond, May 22 '13 at 17:15
@AmarMond: I see. You are missing another piece. I'll update my answer. — NotMe, May 22 '13 at 17:18

score 1 · Answer 2 · answered May 22 '13 at 17:44

What you are asking for is not really a tree, but a graph. Especifically it's a Directed Acyclic Graph (DAG). Here it's a link speaking about storing DAGs in a relational database.

It might be easier to just go with a traditional tree structure for the categories, and allow for items to be in multiple categories with the help of a item/category linking table.

score 1 · Answer 3 · edited May 23 '17 at 11:46

An alternative approach would be to use tags on whatever items you are storing instead of categories. From the example you give, that may even be more appropriate - instead of "Desktop and Mobile Applications", "Desktop Applications" and "Mobile Applications", you would use the "Desktop" and "Mobile" tags. An item with both would then naturally fall into the first category.

Ref: How to store tags in MySQL tags, one field in total or one filed for each tag?

How do I represent a Tree Structure in a mySQL table

3 Answers3

Linked