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

Question

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?

I added the tags to be more specific, but I'd say it's pretty much an SQL-related question. — FirstOne, Aug 19 '17 at 01:30
possible duplicate of https://stackoverflow.com/questions/23751672/sql-query-how-to-extract-last-child-of-a-table — William Perron, Aug 19 '17 at 01:38
This type of relationship is usually evaluated with recursion. Is there a particular reason you are trying to avoid recursion? — user681574, Aug 19 '17 at 02:34

score 2 · Answer 1 · answered Aug 19 '17 at 01:52

2

One way to find nodes without children is to use not exists to only select rows that are not referenced as parents in the cat_id column:

select id from cat c1
where not exists (
    select 1 from cat c2 where c2.cat_id = c1.id
)

answered Aug 19 '17 at 01:52

FuzzyTree

32,014
3
54
85

score 2 · Accepted Answer · answered Aug 19 '17 at 03:00

2

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

answered Aug 19 '17 at 03:00

user681574

553
2
15

1

Ok, it just clicked.. ::::: get everything from the table (`left`) -> bring the ones that have a parent (`join/on`), the ones that don't have children won't merge, causing them to not have a reference -> remove null references (`where`).. Thanks a lot. – FirstOne Aug 19 '17 at 03:32

score 1 · Answer 3 · answered Aug 19 '17 at 04:48

1

Try this:

select * from cat
where id not in (
    select distinct cat_id 
    from cat
    where cat_id is not null)

Finding rows that don't have any other rows pointing to it, means finding rows which 'id' is not in any row of 'cat_id' column.

answered Aug 19 '17 at 04:48

JMS786

1,103
2
11
22

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

3 Answers3