What kind of DB structure should I use for a site has infinite sub-category?

Question

For example, "Dole Banana" is a kind of product, it's listed under the "Bananas" category, when I open the "Fruits" category, I want to see "Dole Banana".

+ Food
|--+ Fruits
|------+ Bananas   
|------+ Apples
|--+ Vegetables
|------+ Onion
|------+ Spinach

Answer 1

I've usually used left-right trees which are very well adapted to database querys. You have a parentId,left and right value for each node. Every nodes children has a left/right value that is between the parent nodes left and right which makes it very easy to find for example all children/parents of a node. It does give a slight overhead on insertions, but it shouldn't be too much of an impact unless you insert alot.

Edit: Just a word of warning though, you need to make the insert/update operations in a locked transaction or the tree can get messed up.

Answer 2

If you're looking for online resources that address this problem, "Storing a Tree in a Database" would be a good search phrase.

As for the solution, note that each subcategory can have either one or zero parent categories. Therefore, the entire tree can be stored in a single self-refferental table with a "parent" field.

Using your example tree:

 ID  | PARENT | NAME
-----+--------+-------------
  1  |  null  | Food
  2  |   1    | Fruits
  3  |   2    | Bananas
  4  |   2    | Apples
  5  |   1    | Vegetables
  6  |   5    | Onion
  7  |   5    | Spinach

Answer 3

A Table "Categories" with 3 fields.

1. CategoryId not null (primary key)
2. ParentCategoryId null
3. CategoryName not null

To get all root categories

select * from Categories where ParentCategoryId is null

To get all sub categories of some specific category:

select * from Categories where ParentCategoryId = 12

Answer 4

You could use simple table structure with parent_category_id and retrieve whole tree with recursion or implement left/right values and fetch whole tree using preordered tree traversal method.

Answer 5

If you mean an infinite number of levels, then a self referencing table that can be recursed. Example: StuffID, StuffName, StuffParentID (FK to Stuff ID)

For a finite number, fixed tables: parent-child-grandchild

Answer 6

    CREATE TABLE [dbo].[Category](
    [CategoryId] [int] NOT NULL,
    [ParentCategoryId] [int] NULL,
    [CategoryName] [nvarchar](50) NOT NULL,
     CONSTRAINT [PK_Category] PRIMARY KEY CLUSTERED 
    (
        [CategoryId] ASC
    )WITH (PAD_INDEX  = OFF, STATISTICS_NORECOMPUTE  = OFF, IGNORE_DUP_KEY = OFF, ALLOW_ROW_LOCKS  = ON, ALLOW_PAGE_LOCKS  = ON) ON [PRIMARY]
    ) ON 

[PRIMARY]

GO

ALTER TABLE [dbo].[Category]  WITH CHECK ADD  CONSTRAINT [FK_Category_Category] FOREIGN KEY([ParentCategoryId])
REFERENCES [dbo].[Category] ([CategoryId])
GO

ALTER TABLE [dbo].[Category] CHECK CONSTRAINT [FK_Category_Category]
GO

Answer 7

For infinite hierarchy, use the modified preorder tree traversal algorithm

Answer 8

Here's a different approach that might be useful to you. It has slightly more maintenance costs than the PARENT_ID or lft/rght approach, but retrieval is much easier (and faster).

Dole bananas can be in products table. You have a single category_id for a product.

We had a requirement to allow multiple categories for a product. This lead us to having a categories_products join table, where product could have multiple joined rows. Then, we had to decide whether to have Dole bananas in just bananas, or in bananas and all its parents as well. As speed of retrieval was critical, we put dole bananas in its categories and all of their parent categories. There are three category-product joins for dole bananas.

Using this structure, returning all the items from any category is easy and quick, only one query. You can't do this in the PARENT_ID approach (unless you hard-code parents, grand-parents, etc.) Adding a category is easy. Categorizing a product requires inserting multiple rows in the join table. Deleting and moving categories are a bit trickier.