Hierarchical Data - Nested Set Model: MySql

Question

I am just learning how to implement the Nested Set Model but still have confusion with a certain aspect of it involving items that may be part of multiple categories. Given the example below that was pulled from HERE and mirrors many other examples I have come across...

How do you avoid duplication in the DB when you add Apples since they are multi-colored (i.e. Red, Yellow, Green)?

Answer 1

Old thread, but I found a better answer to this problem.

Since apple can have different color, your structure is a graph,not a tree. The nested set model is not the right structure for that.

Since you mention in a comment that you're using Mysql, a better solution is to use the Open Query Graph engine (http://openquery.com/graph/doc) which is a mysql plugin that lets you create a special table where you put the relationships, basically parentId and childId. The magic is that you query this table with a special column latch depending of the value passed in the query will tell the OQGRAPH engine which command to execute. See the docs for details.

Answer 2

Thinking out loud here, but perhaps it would be helpful to view some attributes (like Red, Yellow and Green) as 'tags' instead of 'categories' and handle them with separate logic. That would let you keep the Nested Set model and avoid unnecessary duplication. Plus, it would allow you to keep your categories simpler.

It's all in how you think about the information. Categories are just another way of representing attributes. I understand your example was just for illustrative purposes, but if you're going to categorize fruit by color, why would you not also categorize meat the same way, i.e., white meat and red meat? Most likely you would not. So my point is it's probably not necessary to categorize fruit by color, either.

Instead, some attributes are better represented in other ways. In fact, in its simplest form, it could be recorded as a column in the 'food' table labeled 'color'. Or, if it's a very common attribute and you find yourself duplicating the value significantly, it could be split off to a separate table named 'color' and mapped to each food item from a third table. Of course, the more abstract approach would be to generalize the table as 'tags' and include each color as an individual tag that can then be mapped to any food item. Then you can map any number of tags (colors) to any number of food items, giving you a true many-to-many relationship and freeing up your category designations to be more generalized as well.

I know there's ongoing debate about whether tags are categories or categories are tags, etc., but this appears to be one instance in which they could be complimentary and create a more abstract and robust system that's easier to manage.

Answer 3

You do not avoid duplications and the apple (or a reference to the apple) will be placed twice in your tree otherwise it won't be a tree but rather a graph. Your question is equally applicable if you build a... Swing JTree or an HTML tree ;).

The nested set model is just an efficient way to push and traverse a tree structure in a relational DB.It is not a data structure itself. It's more popular among MySQL users since MySQL lacks functionality for processing tree structures (e.g. like the one that Oracle provides).

Cheers!

Answer 4

Nested set model is a structure for 1:N (one-to-many) relationships, you want to use M:N (many to many) relationship (many items can have apple as parent, but can have more than one parent).

See this article

Wikipedia

But you should be aware, that hierarchical M:N relationships can get quite complex really fast!