FirstOne FirstOne - 30 days ago 6
SQL Question

Select rows not pointed by any other row on self referencing table

I have a self referencing table and I'm having trouble finding rows that don't have any other rows pointing to it - or, in other words, getting the ones that aren't parents to any other, meaning, of course, they don't have children.

This is my table with sample data:

+----+------+--------+
| id | name | cat_id |
+----+------+--------+
| 1 | C1 | |
| 2 | C2 | |
| 3 | C3 | 1 |
| 4 | C4 | 2 |
| 5 | C5 | 2 |
| 6 | C6 | 5 |
+----+------+--------+


Here,
cat_id
is the parent. This is a 'representation':

.
├── C1
| └── C3
└── C2
├── C4
└── C5
└── C6


As seen, categories can have sub-categories indefinitely and they are defined by pointing to
cat_id
. If it's a 'main' category, it just doesn't point to anything. I can get all categories that don't have a 'parent' by selecting
NULL
in
cat_id
, but how do I select categories that don't have 'children'?

I tried:

SELECT
c1.id, c1.name, c1.cat_id
FROM
cat c1
INNER JOIN
cat c2
ON
c1.id != c2.cat_id


But this not only returns duplicated rows, but also includes categories that have children. The expected results are in bold in the representation. You can run tests in this SQLFiddle.

How can I accomplish this? Is it achievable without recursion?

Answer Source

This is probably what you were aiming for in your initial query:

select a.*
from cat a left outer join
   cat b on a.id = b.cat_id
where b.cat_id is null