-1

I have a table of categories:

id,label,parent_id
1,Animals,null
2,Dogs,1
3,Cats,1
4,Black,3

This means that "Animals" is a top-level category, and "Dogs" and "Cats" are both sub-categories to "Animals", and "Black" is a sub-category of "Cats" (itself a sub-category of "Animals"). It can be any number of levels/"generations".

I frankly never expected this to be any kind of issue, but once I wanted to create a query to count all the objects in the "Animals" category (meaning also all in the sub-categories), I hit a hopeless dead end. Both the PostgreSQL manual and the Stack Exchange questions and the other online resources just show these massive, confusing WITH RECURSIVE queries full of UNIONs and everything. I simply cannot follow them.

It cannot possibly be this difficult. I must be misunderstanding something.

All I try is to do is:

SELECT count(*) FROM table WHERE id = $1 OR parent_id RECURSIVE = $1;

And:

SELECT id FROM table WHERE id = $1 OR parent_id RECURSIVE = $1;

Naturally, I have made up the RECURSIVE keyword here, but that's how I expected it to work.

I've read the manual and the Stack Exchange answer numerous times now and I just have no idea how I'd "adapt" it to my situation. I don't even understand what they are doing in the examples. It's simply too damn complex. This seems like such a common problem that it must have been long since elegantly solved... right?

3
  • Oracle has CONNECT BY, which is more elegant for your type of query, but more limited for many other types Jan 10 at 4:47
  • @Charlieface It's insane if I'm going to have to implement this in application code... and will be awfully slow. Jan 10 at 5:09
  • The with recursive is how this is defined in the SQL standard. If you want a query to traverse a hierarchy, it's the way to go (and how it works on pretty much every database). And no, recursive queries don't need to be "awfully slow" Jan 10 at 10:32
3

I think if you get your head round a basic recursive CTE implementation, you won't find them so difficult to understand in future.

I'm going to try and show you how to do the COUNT(*) you mention in very, very easy steps.

We are going to find all Animals that are of the Cat family. Apologies to any taxonomists here.

1. Firstly, we need to define a starting query: let's grab the id for Cat. We will put this into a CTE (basically a view defined within the query):

WITH cte AS (
    SELECT a.Id, a.Name
        FROM Animal AS a
        WHERE name = 'Cat'
)

Result:

Id Name
1 Cat

2. Now we take the result of the previous query and UNION ALL (concatenate) the next level down:

WITH Anchor AS (
    SELECT a.Id, a.Name
        FROM Animal AS a
        WHERE name = 'Cat'
),
Recursion AS (
    SELECT *
        FROM Anchor
    UNION ALL
    SELECT a.Id, a.Name
        FROM Animal AS a
        JOIN Anchor AS cte ON cte.id = a.parent_id
),

Result:

Id Name
1 Cat
5 Panther
6 Lynx
7 Domestic

3. The problem at this stage is we would have to make a new query for each level. So we need to combine these two queries and get the DB to keep UNIONing each result again and again. This is where the magic happens:

WITH RECURSIVE cte AS (
    SELECT a.Id, a.Name
        FROM Animal AS a
        WHERE name = 'Cat'
    UNION ALL
    SELECT a.Id, a.Name
        FROM Animal AS a
        JOIN cte ON cte.id = a.parent_id
)

What happens here is that the Anchor part (step 1) is executed and output. The result is also fed back in to the join in the recursive part. The result from that is again output and fed back in again to the recursion, until the recursion returns an empty result.

Result:

Id Name
1 Cat
5 Panther
6 Lynx
7 Domestic
10 Lion
11 Leopard
16 Bobcat
17 Tabby

4. This is the easy bit: we count the final result

WITH RECURSIVE cte AS (
    SELECT a.Id, a.Name
        FROM Animal AS a
        WHERE name = 'Cat'
    UNION ALL
    SELECT a.Id, a.Name
        FROM Animal AS a
        JOIN cte ON cte.id = a.parent_id
)
SELECT COUNT(*)
FROM cte;

Result:

count
8
0
0

It sounds like you're designing and thinking about the problem more procedurally as opposed to relationally. You should normalize your data so that the top level category Animals is it's own table with Dogs and Cats being values in the Animals table. Then attributes of those Animals would either be additional fields in the Animals table like AnimalColor, OR you can normalize them into their own tables as well and reference them by ID, such as a table for Colors (or AnimalColors depending on what other objects could reference a Color). This then simplifies your questions such as "how many animals are there?" to basic queries like SELECT COUNT(*) FROM Animals.

If you must store all entities under one hierarchical table as you mentioned, then you need to use something like a recursive CTE. See this basic walkthrough on how to implement one.


Here's an example query that leverages a recursive CTE:

WITH RECURSIVE CTE (child_id, child_label, parent_label, parent_id) AS (
    -- This is your recursion's base cass
    SELECT id AS child_id, label AS child_label, '' AS parent_label, parent_id
    FROM CategoriesTable

    UNION ALL

    -- This is the recursive case. Notice how the previous UNIONed data set becomes the child and the new join becomes the parent, and then on the next case this parent becomes the child and it's parent is joined to. Basically the current Parent becomes the Child of the next Parent on each iteration, as it crawls the hierarchy.
    SELECT C.parent_id AS child_id, C.label AS child_label, CT.label as parent_label, CT.parent_id 
    FROM CategoriesTable AS CT
    INNER JOIN CTE C
        ON C.parent_id = CT.id
)
-- This is your final result set, which currently is the entire hierarchy crawled. You can add a WHERE clause to filter on a certain subcategory's ancestor branch only, or you can do your aggregation here like COUNT(*) to count how many subcategories there are, etc.
SELECT child_id, child_label, parent_label, parent_id FROM CTE;
4
  • 1
    Having a separate table for every category would be insanity and make zero sense. You cannot seriously be suggesting that. As for the link you provided, that's yet another one of those I don't understand. There's nothing basic about the SQL code in that page. Jan 10 at 5:08
  • OP is right that it's impossible to store each type in a new table. That would mean every category, and sub-category and sub-sub-category etc going in a new table. I will give an rCTE answer. Jan 10 at 5:16
  • @user14756437 Based on your limited example it actually is a standard design solution. If you could elaborate further on what other kinds of things could be children in your current design then perhaps an alternative design pattern makes more sense than what I suggested. But with your current example, the normalized design I suggested results in you having two tables total (since things like Animals and things like Colors are two different things typically).
    – J.D.
    Jan 10 at 5:41
  • @user14756437 I've updated my answer to include an example RECURSIVE CTE using your example table. Hopefully that coupled with my comments makes it a little more clear on how they work. If you have any questions, feel free.
    – J.D.
    Jan 10 at 5:56
0

If you have a fixed number - say n - of levels in your tree, you can use n-1 self-joins and then aggregate over that. However, most of the time the depth of the tree is not fixed so you need a variable number of joins.

A recursive CTE can be thought of a just that, a variable number of joins. The syntax admittedly is a lot worse than in other languages, and for efficiency reasons, there are restrictions in what kind of recursion that is allowed. A function like Ackermann function makes no sense in data management so there is no real point in implementing functionality that supports it.

Your current table is sometimes referred to as an Adjacency List Model (ALM). Most of the time it is the best option to simply stick with that and use a rCTE to determine the Transitive Closure (TC) of the tree. Since others have already mentioned rCTE, I will not delve into that.

IN your case the objection seems to be that you don't like the syntax. That dilemma can be solved by encapsulating the CTE in a recursive view or a recursive table function. The function can be called as:

SELECT * FROM my_function(node);

In general, the table function tends to be more efficient since the predicate for where to start can be used to prune the search space.

On occasion, a rCTE will not meet the performance requirements. This can happen for large hierarchies or when you simply don't get the responce time that you need. In that case, an alternative may be to use some kind of Incremental Evaluation Systems (IES). The idea is to pre-calculate the hierarchical information when modifying the tree. Three common models used are Materialized Path (MP), Nested Set (NS) and a separate Transitive Closure (TC)

In MP you store a string in each node describing the path to root

1,Animals,'#'
2,Dogs,'#Animals#'
3,Cats,'#Animals#'
4,Black,'#Animals#Cats#'

To determine the subtree of say Cats:

select * from categories where path like '%#Cats#%'

or as:

select y.* 
from categories x
join categories y
    on y.path like x.path || x.category || '#%
where x.category = 'Cats'

The second alternative can better utilize indexes

To get the ancestors you either split the path, or:

select x.* 
from categories x
join categories y
    on y.path like x.path || x.category || '#%
where y.category = 'Cats'

You can easily create table functions for these two queries. When adding a subnode you simply prepend the parents path with parent as the path. Note that the parent_id attribute is replaced with the path attribute since you don't need it.

In nested set (NS) you instead replace parent_id with a lower and an upper bound. You can think of it as a Matryoshka doll

1,Animals,1,8
2,Dogs,2,3
3,Cats,4,7
4,Black,5,6

To determine the sub-tree

select * from categories where lb > 4 and ub < 7

and the ancestors

select * from categories where lb < 4 and ub > 7

A nice algebraic property is that ub - lb = 1 for leafs. From there we can derive that the size of the subtree is (ub - lb - 1) / 2. In your example we would get:

(8-1-1)/2=3 

for animals. Pretty neat, but the downside is that we may have to re-number large parts of the tree for small modifications. It is therefore unsuitable for trees that change a lot.

For TC we add a new table that holds information about the transitive close. Let's call int category_ancestors

categories

1,Animals,null
2,Dogs,1
3,Cats,1
4,Black,3  

category_ancestors

2,1
3,1
4,3
4,1

To determine the sub-tree

select category_id from category_ancestors where ancestor_id = 3

to determine the ancestors

select ancestor_id from category_ancestors where category_id = 3

Modifications of ancestors is a consequence of modifying parents so it makes sense to use triggers for this. Adding a new node means we also add the parent's ancestors + parent for the new node.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.