How to model nested categories?

Questions / Help
1

Hi everybody,
I want to implement a system with categories and subcategories and subsub and subsubsub… lol.

ie: the category A has 2 subcategories: B and C and C have a sub-category D.

The deep of the nesting is not rigid and may grow.
How would you model this, allowing easy search in db? Search ancestor and children? Is there a way to avoid recursion?

2

Hello

Did you see this library https://github.com/Byzanteam-Labs/hierarch?
It is based on ltree postgres extension. I didn’t try it, but I’d try if I have this kind of requirements :slight_smile:

2 Likes
3

Thanks, seems great. I will have a look at this.

4

I’d imagine the database table (let’s call it categories) would have a reference to a parent category as a foreign key, parent_category_id.

If parent_category_id is NULL, it has no parent.

5

The problem with this is the need of potentially multiple joins on the same table and we dont know how many joins we need. Or potentially multiples chained requests.

6

Another way is to use a nested set model, using lft and rgt additional columns.

2 Likes
7

Postgres can do recursive common-table expressions if you really want, but it’s worth considering carefully exactly how your application will use the nested categories.

  • how often are new categories added? Some representations will make this expensive
  • how often do queries like “in this category and all its subcategories” occur? Some representations will make THAT expensive

Poking around in Hex turns up some candidates:

  • Arbor uses CTEs to traverse parent_id chains
  • Ancestry uses materialized paths; each record stores the full “path” through the hierarchy (a record in Subsubcategory D would store “A/C/D” or similar)
  • as_nested_set uses nested sets to make answering “and all subcatgories” questions faster
  • Hierarch linked up-thread by @fuelen uses a Postgres extension to offload some of the complexity to the database
3 Likes
8

Thank you.
I think i will remodel my app allowing only two levels to apply the KISS principle :wink:
I maybe will use one of these great libraries in the future.

1 Like
9

I just did this for a project I’ve been working on. I ended up settling on closure_table.

The biggest challenge was building the proper data structure required by the admin front-end widget to use drag-n-drop etc.

2 Likes
10

I suspect it’s paid work and thus confidential but if it accidentally is not then I’d absolutely love to see the code. Sounds like it’s extremely handy.

1 Like
11

It’s paid work but not confidential. If I get some free time, I’ll see if I can put together something.

As it stands, the code is still in a “first pass” state where I got things working the way I needed but had to move on due to time constraints, so at this point it’s not code I’d particularly proud of showing off. The idea was to circle back when things calmed down and have another pass at it :slight_smile:

1 Like
12

These are the famous last words written on the tombstones of countless never-released projects though… :icon_cry:

It will never be perfect. Post it on GitHub when you get a free hour some evening. People like me might like it and offer PRs.

Don’t be obsessed with a theoretical perfect state of your code. I know exactly how you feel but we the techies should apply some business thinking to our own voluntary work here and there: if it works and it’s good enough then it’s very likely just fine for presentation as well.

You don’t want to know how god-awful my Rust code in my sqlite3 Elixir<=>Rust library is. But it does what it’s supposed to for the moment. Overcoming analysis paralysis and the desire for perfection are skills that will put you above many programmers.

At least from my side I can promise not to judge. Only to send PRs if I feel that something can be improved.

2 Likes