How can I create an "eBay style" hierarchy of categories and sub-categories?

Question

I am building a classified-ads website using asp.net web forms and linq-to-sql.

The items for sale need to be categorised in a hierarchical manner, however, an individual item may be in multiple child categories.

For an example take a look at this battery on eBay. Notice there are two breadcrumbs:

Sound & Vision > Multipurpose Batteries & Power > Rechargeable Batteries
and well as:
Computers/Tablets & Networking > Laptop & Desktop Accessories > Laptop Batteries

In addition to an item belonging to multiple categories, a category may have more than one parent as well, e.g. when browsing the categories "Sound & Vision > Batteries" or "Electronics > Batteries", one should see the exact same sub-categories of Batteries in both cases (e.g. Rechargeable or Non-Rechargeable, etc).

I'm uncertain as to how to even begin structuring the database tables, let alone querying them from the web site, so any help or guidance would be much appriciated.

I've looked at articles such as Storing Hierarchical Data in a Database, but don't think it would apply in my case due to the many-to-many nature of the items and categories.

Thanks.

Andrew Walters · Answer 1 · 2012-09-19T13:22:19.210

Recently I've faced the same problem and am storing categories in a tall table like this

CATEGORIES
------------------
Id
Text
ParentId

So far it's working for me, but I'd be curious if better answers come along

For your example, you may want to split out the parents into a separate table since you want to be able to have a many-to-many relationship

You could do it like this

CATEGORIES
----------------
Id
Text


CATEGORY_PARENTS
----------------
ID
ParentId

Bhrugesh Patel · Answer 2 · 2012-09-19T15:41:14.787

Usually the most efficient way is to breakdown the data at lowest level possible and avoid data redundancy as much as possible. In short, break the tables as much as you can while keeping related data in a group (or a table here) and making sure that you are not repeating any real data in tables (by creating join tables on IDs).

I am not sure how much you are willing to change your database schema or how your current schema is built but one solution can be that you create a table for storing all major categories (lets call it table A), another table for second level of categories (table B) and one more for lowest level of categories (table C).

Then you can create a new table (table D) to attach table A and table B. So now your main categories and sub categories are connected.

Now creating a sub category for a sub category is a bit of a challenge. You can overcome this problem by adding one more field to the table D indicating if the current item is a 'sub sub item' (i know, my naming sense sucks :P) or not. i.e. if indicator field is 0, its a sub cat., otherwise indicator field value is the id of the parent sub item. That is kind of self join.

For an item belonging to multiple categories, create one more table (table E) that connects item table and table D. Here you connect 'itemID' with 'subcatID'. i.e. if battery itemID is 10, subcatID of rechargeable battery is 5 and subcatID of laptop battery is 7 then you make two rows in table E

itemID        subcatID
  10             5
  10             7

When you search, search for all 10 and you will have all categories.

Again, this is one possible solution. You can also use star schema but its specially effective for data warehousing. If your category level numbers are fixed (i.e. you will only have 3 levels categories or so on) then you can use cascading style tables (i.e. table A is main cat., table B is sub cat. and table C is last sub sub cat.). This will make your queries a bit long but simple none the less. I am only starting in the database field so moving / tagging this question with database tags will probably get you a better answer.

Good Luck!

The star schema seems like an interesting approach. I've up-voted, and will accept the answer once I've been able to see if it works in my situation. Thanks. — Adnan, Sep 19 '12 at 15:40

score 0 · Accepted Answer · edited May 23 '17 at 11:49

Thanks to @bhrugesh-patel and @andrew-walters for attempting to answer my question. However, on further research it appears that the hierarchy described above is called a Directed Acyclic Graph (DAG), i.e. almost a tree but with one major difference: you can reach the same node through different paths.

Graph Databases such as Neo4j are designed for storing structures like DAGs, but as I'm stuck with using a relational database (SQL Server), I'll attempt to implement the solution mentioned in this article: A Model to Represent Directed Acyclic Graphs (DAG) on SQL Databases.

FYI: Another question on SO also discusses this topic in more detail.

How can I create an "eBay style" hierarchy of categories and sub-categories?

3 Answers3