CODEWITHSUNDEEP
mysqldatabasedatabase-designerd
Xitcod13
Xitcod13

Reputation: 6089

modeling many to many unary relationship and 1:M unary relationship

Im getting back into database design and i realize that I have huge gaps in my knowledge.

I have a table that contains categories. Each category can have many subcategories and each subcategory can belong to many super-categories.

I want to create a folder with a category name which will contain all the subcategories folders. (visual object like windows folders) So i need to preform quick searches of the subcategories.

I wonder what are the benefits of using 1:M or M:N relationship in this case? And how to implement each design?

I have create a ERD model which is a 1:M unary relationship. (the diagram also contains an expense table which stores all the expense values but is irrelevant in this case)

1:M unary relationship

is this design correct?

will many to many unary relationship allow for faster searches of super-categories and is the best design by default?

I would prefer an answer which contains an ERD

Upvotes: 0

Views: 5106

Answers (2)

Joni
Joni

Reputation: 111349

In some cases the easiest way to maintain a multilevel hierarchy in a relational database is the Nested Set Model, sometimes also called "modified preorder tree traversal" (MPTT).

Basically the tree nodes store not only the parent id but also the ids of the left-most and right-most leaf:

spending_category
-----------------
parent_id    int
left_id      int
right_id     int
name        char

The major benefit from doing this is that now you are able to get an entire subtree of a node with a single query: the ids of subtree nodes are between left_id and right_id. There are many variations; others store the depth of the node in addition to or instead of the parent node id.

A drawback is that left_id and right_id have to be updated when nodes are inserted or deleted, which means this approach is useful only for trees of moderate size.

The wikipedia article and the slideshow mentioned by Branko explains the technique better than I can. Also check out this list of resources if you want to know more about different ways of storing hierarchical data in a relational database.

Upvotes: 1

Branko Dimitrijevic
Branko Dimitrijevic

Reputation: 52137

If I understand you correctly, a single sub-category can have at most one (direct) super-category, in which case you don't need a separate table. Something like this should be enough:

enter image description here

Obviously, you'd need a recursive query to get the sub-categories from all levels, but it should be fairly efficient provided you put an index on PARENT_ID.

Going in the opposite direction (and getting all ancestors) would also require a recursive query. Since this would entail searching on PK (which is automatically indexed), this should be reasonably efficient as well.

For some more ideas and different performance tradeoffs, take a look at this slide-show.

Upvotes: 3

Related Questions