SQL finding top parent from list of parent

Question

I've two tables: table 1 with a column of parent ID's (P-id), and table 2 with two columns: P_id and C-id(Child ID's ).

In table 2 for each child the parent is shown, but the child can have more then one parent and vice versa.(many to many). Now I need to find all P-id's which presents parents who do not have parents themselves based on this P-id|C_id relationship. The difficulty in my opinion is that there is no direct info about the parent level.

P_id
------
1
2
3

C_id
------
1 
2 
3 
4 
5

P_id   C_id
-----------
1      1  
1      2  
1      3   
2      1   
2      2   
2      3   
2      4   
3      1  
3      5  
3      3

The answer should be P_id 2 and 3

@tom - this doesn't appear to be a parent/child relationship like we would normally think of it - I think CID 1 and PID 1 are different entities. — JNK, Jul 12 '11 at 16:59

JNK · Answer 1 · 2011-07-12T17:13:16.737

0

SELECT p_id from TableA as A
WHERE NOT EXISTS (SELECT * FROM TableB as B
                  WHERE B.C_id = A.P_ID)

This will show you all parents who's ID does not appear as a child_id in the second table.

EDIT:

Try this....

SELECT b1.p_id 
from #TableB as B1
WHERE c_id NOT IN ( SELECT c_id
                    FROM #TableB as b2
                    WHERE b2.p_id <> b1.p_id)

If I am thinking this through correctly, this should show you all parent_id's that have a child_id that no other parent_id has.

edited Jul 12 '11 at 17:13

answered Jul 12 '11 at 16:54

JNK

63,321
15
122
138

hello JNK, thanks for the response, but the thing is C_ID and P_ID are not related. They are two distinct set of numbers. Perhaps I've should have labeled the C_id's with letters instead of numbers – robert Jul 12 '11 at 16:59
1

@robert - if that is the case then how do you know if a child is also a parent? It's not in your data model. – JNK Jul 12 '11 at 16:59
@Robert - more specifically, how did you get your answer of 2 and 3? – JNK Jul 12 '11 at 17:03
@ JNK Well, I know all the children of each parent. So each parent is sort of a container (containing children). So by comparing all the children of one parent with another I need to answer the question if one parent is a subset of another one based on their children – robert Jul 12 '11 at 17:04
@robert - so it's based on if one parent has all of another parent's children as it's own children? – JNK Jul 12 '11 at 17:05
@ JNK YES, but I have to continue doing this until parents emerge that are not subsets of other parents ---> top parents – robert Jul 12 '11 at 17:06

score 0 · Answer 2 · edited May 23 '17 at 12:04

I've explored this issue a bit. Depending on your requirements you should think of your relation table as a DAG. You need to ascend until you find a row with no parents.

This is inherently a recursive operation so your SQL version will come into play here.

Given a value, you can find the parent (or lack of), you then need to re-run the same test to determine the same thing.... all the way until you find no parent.

Does your situation limit the number of nesting layers? If so, this can be accomplished without recursion.

See my question here for additional discussion:
Return all nodes in many-to-many hierarchal tree

EDIT:
Say you have a limited nesting depth of 3, you could simply JOIN repeatedly to exhaust your nesting depth.

SELECT 
    *
FROM 
    table a
LEFT OUTER JOIN table b 
    ON b.C_id = a.P_id
LEFT OUTER JOIN table c 
    ON c.C_id = b.P_id
LEFT OUTER JOIN table d 
    ON d.C_id = c.P_id
WHERE
    a.C_id = @pYourValue
    AND (
        a.P_id IS NULL 
        OR b.P_id IS NULL
        OR c.P_id IS NULL
        OR d.P_id IS NULL
        )

This approach will only work if you have a known, finite nesting depth

@ Matthew Thanks for the clue. It is indeed related to a DAG. However the number nesting layers is limited. You mentioned that is can be accomplished without recursion. How? — robert, Jul 13 '11 at 16:16
@robert if the nesting depth is limited to n you *could* simply self-`OUTER JOIN` n times — Matthew, Jul 13 '11 at 20:22

SQL finding top parent from list of parent

2 Answers2