Home > Software design >  Find parent child loop in mysql table
Find parent child loop in mysql table

Time:01-03

I have a Parent Child Relations table in MySQL that has the following columns: id, pid, cid, value. Created like this:

create table PCRELATIONS(
 id INT NOT NULL AUTO_INCREMENT, 
 pid char(1) NOT NULL, 
 cid char(1) NOT NULL, 
 value varchar(10),   
 PRIMARY KEY ( id ) 
);

Here, id is the surrogate key, pid and cid are fks from another table, and value is varchar. I know pid and cid should be int but I am using char here just to make it easier to visualize the problem without causing confusion due to too many 1s and 2s.

I need to find all the loops in the table which involve exactly three nodes i.e. A->B->C->A.

For example, if the table has the following data:

id pid cid value
1 A B AB
2 B C BC
3 C A CA1
4 C A CA2
5 C D CD

Here are the insert queries:

insert into PCRELATIONS values(0, 'A', 'B', 'AB');
insert into PCRELATIONS values(0, 'B', 'C', 'BC');
insert into PCRELATIONS values(0, 'C', 'A', 'CA1');
insert into PCRELATIONS values(0, 'C', 'A', 'CA2');
insert into PCRELATIONS values(0, 'C', 'D', 'CD');

This data has two loops involving A->B->C->A because there are two paths from C to A.

I am trying to get this result:

leg1, leg2, leg3, p1id, p2id, p3id, val1, val2, val3
1, 2, 3, A, B, C, AB, BC, CA1,
1, 2, 4, A, B, C, AB, BC, CA2,

I was thinking that the following query will do it but it is returning too many rows. Where am I going wrong?

select x.id as leg1, y.id as leg2, z.id as leg3, 
  x.pid as pid1, y.pid as pid2, z.pid as pid3, 
  x.value as val1, y.value as val2, z.value as val3  
from pcrelations x 
inner join pcrelations y on x.cid=y.pid 
inner join pcrelations z on y.cid=z.pid 
where z.cid=x.pid;

Any thoughts?

CodePudding user response:

Just make sure that the id of the joined table is bigger.

select 
  t1.id as leg1, t2.id as leg2, t3.id as leg3 
-- , t1.cid as cid1, t2.cid as cid2, t3.cid as cid3
, t1.pid as pid1, t2.pid as pid2, t3.pid as pid3
, t1.value as val1, t2.value as val2, t3.value as val3  
from pcrelations t1
inner join pcrelations t2
  on t2.pid = t1.cid 
 and t2.id > t1.id
inner join pcrelations t3 
  on t3.pid = t2.cid 
 and t3.cid = t1.pid 
 and t3.id > t2.id;
leg1 leg2 leg3 pid1 pid2 pid3 val1 val2 val3
1 2 3 A B C AB BC CA1
1 2 4 A B C AB BC CA2

Demo on db<>fiddle here

CodePudding user response:

You can try to use CTE recursive to find your expected Root pid then do conditional aggregate function to get your expected result.

Query #1

with recursive cte  as (
  SELECT id,pid,cid,value, 1 rn,id group_id
  FROM PCRELATIONS
  WHERE cid = 'A'
  union all
  select p.id,p.pid,p.cid,p.value, rn  1 ,group_id
  from       PCRELATIONS p
  inner join cte c
  on p.cid = c.pid AND p.cid <> 'A'
)
SELECT MAX(CASE WHEN rn = 3 THEN id END) leg1,
       MAX(CASE WHEN rn = 2 THEN id END) leg2,
       MAX(CASE WHEN rn = 1 THEN id END) leg3,
       MAX(CASE WHEN rn = 3 THEN pid END) pid1,
       MAX(CASE WHEN rn = 2 THEN pid END) pid2,
       MAX(CASE WHEN rn = 1 THEN pid END) pid3,
       MAX(CASE WHEN rn = 3 THEN value END) val1,
       MAX(CASE WHEN rn = 2 THEN value END) val2,
       MAX(CASE WHEN rn = 1 THEN value END) val3
FROM cte
GROUP BY group_id;

| leg1 | leg2 | leg3 | pid1 | pid2 | pid3 | val1 | val2 | val3 |
| ---- | ---- | ---- | ---- | ---- | ---- | ---- | ---- | ---- |
| 1    | 2    | 3    | A    | B    | C    | AB   | BC   | CA1  |
| 1    | 2    | 4    | A    | B    | C    | AB   | BC   | CA2  |

View on DB Fiddle

  • Related