Select Parent, Children, Children's Children, etc in single MySQL query

Question

I feel like this must be a classic problem, but I can't find the answer.

I have a table Person, which has basic details describing a person. Then, I have a ParentChildRelationship table, which looks something like this:

CREATE TABLE `ParentChildRelationship` (
    `ParentId` INT(10) UNSIGNED NOT NULL,
    `ChildId` INT(10) UNSIGNED NOT NULL,
 PRIMARY KEY(ParentId,ChildId),
 CONSTRAINT `FK_ParentRelationship`
    FOREIGN KEY (`ParentId` )
    REFERENCES `Person` (`idPerson` ),
 CONSTRAINT `FK_ChildRelationship`
    FOREIGN KEY (`ChildId` )
    REFERENCES `Person` (`idPerson` )
);

I need a select query that simply returns all Person records for the Parent and all Children down the tree.

For example, with the following data:

Parent   Child
1        3
1        8
2        4
3        5
3        6
6        9
4        7

Select all Person records where the ParentId = 1 OR ChildId is in the tree below ParentId of 1. This query should return the Person information (SELECT * FROM Person...) for the following PersonId's:

1,3,8,5,6,9

I don't know if this matters, but the order of how these are returned do not matter, as I will need to order based off of something like "LastName" or something like that. In other words, the result could also have been 1,3,5,6,9,8.

score 3 · Accepted Answer · answered Oct 26 '12 at 19:12

If you have a known limited depth, you can unroll the recursion and use a stored procedure or view. For MySQL, the following work:

Stored Routine solution:

DELIMITER $$ 

CREATE PROCEDURE GetRelatedPersonsWithPersonId( IN pId VARCHAR(36)) 
        BEGIN 
                select * from Person where idPerson in ( 
                        select ParentId from ParentChildRelationship where ParentId = pId 
                        union 
                        select ChildID from ParentChildRelationship where ParentId = pId 
                        union 
                        select ChildID from ParentChildRelationship where ParentId in (select ChildID from ParentChildRelationship where ParentId = pId) 
                        union 
                        select ChildID from ParentChildRelationship where ParentId in (select ChildID from ParentChildRelationship where ParentId in (select ChildID from ParentChildRelationship where ParentId = pId)) 
                ) ; 

        END $$

View solution:

Create view ChildRecurse 
As 
Select ParentId, ChildID from ParentChildRelationship 
Union 
Select x1.ParentId, x2.ChildId from ParentChildRelationship x1 
               Inner join ParentChildRelationship x2 on x2.ParentId = x1.ChildId 
Union 
Select x1.ParentId, x3.ChildId from ParentChildRelationship x1 
               Inner join ParentChildRelationship x2 on x2.ParentId = x1.ChildId 
               Inner join ParentChildRelationship x3 on x3.ParentId = x2.ChildId 
Union 
Select x1.ParentId, x4.ChildId from ParentChildRelationship x1 
               Inner join ParentChildRelationship x2 on x2.ParentId = x1.ChildId 
               Inner join ParentChildRelationship x3 on x3.ParentId = x2.ChildId 
               Inner join ParentChildRelationship x4 on x4.ParentId = x3.ChildId

Then select as such:

select * from person where idPerson=@ID or idPerson in (select ChildId from ChildRecurse where ParentId=@ID)

Wish I could mark two as the answer (Nested Interval Model is definitely interesting), but this one is more practical for what I need. I can artificially limit the depth for now. — thephatp, Oct 27 '12 at 00:15

score 1 · Answer 2 · answered Oct 26 '12 at 05:36

1

Your data model is called the adjacency list model. You cannot do the query you are describing with that model (although a stored procedure could).

The usual way of resolving this is to change to the nested set model. The Wikipedia article has some sample code and there's a nice tutorial about it here (along with a good description of what's involved in using the adjacency list model).

answered Oct 26 '12 at 05:36

Ted Hopp

232,168
48
399
521

This is very helpful. I would probably prefer a stored procedure to iterate manually to the nested set model, but before going that route, I'm going to look into the nested interval model. BTW, which of those three is the most common solution to this problem in the real world? – thephatp Oct 26 '12 at 13:17
@thephatp - [this thread](http://stackoverflow.com/questions/360738/are-nested-intervals-a-viable-solution-to-nested-set-modified-pre-order-travers) might be of interest to you. I don't have any experience with the nested interval model, but a cursory look at what others have written suggests that it can have better performance under normal usage patterns than the nested set model. – Ted Hopp Oct 26 '12 at 18:48

score 0 · Answer 3 · answered Oct 26 '12 at 05:40

0

I think this would be a job for the GROUP BY and HAVING statements.

Does something like this point you in the right direction?

SELECT * FROM ParentChildRelationship pcr
GROUP BY ParentID , ChildID
HAVING ParentID=1 OR Count(ChildID)>0

This would give you a list of parent child relations that you could join to the persons table with an INNER JOIN.

answered Oct 26 '12 at 05:40

Sean Dawson

5,587
2
27
34

This doesn't answer the question at all. :( This returns a list of all parent child relations. I need a list of all parent child relations existing under a single top node. – thephatp Oct 26 '12 at 13:20

Select Parent, Children, Children's Children, etc in single MySQL query

3 Answers3

Stored Routine solution:

View solution: