0

I'm faced with a problem.I have a ternary structured data. The relation is from child to parent, more specific a child has an parent_id. A parent shouldn't have more than 3 children. When 4th child appears it should be added to first parent's child as a child. I need a solution PostgreSQL, procedure, recursion. Any help is appreciated!

  • Hi, welcome to DBA stack exchange. Would you please provide more information and example. – Ahmad Abuhasna May 19 at 12:18
0

When 4th child appears it should be added to first parent's child as a child.

I suspect that new child should be added to the nearest parent's child having less than 3 childs. So the problem is reduced to the ranking of the subtree nodes along with the counting their childs.

INSERT INTO tree (id, parent_id) 
  VALUES ( __id__
         , ( WITH RECURSIVE cte AS (
               SELECT 1 AS rank
                    , t.id
                    , ( SELECT COUNT(c.id) AS cnum
                          FROM tree AS c
                         WHERE c.parent_id = t.id
                      ) AS childnum
                 FROM tree AS t
                WHERE t.id = __DESIRED_PARENT_ID__ -- here is the subtree root node

              UNION ALL 

                SELECT cte.rank + 1 AS rank
                     , w.id
                     , ( SELECT COUNT(c.id) AS cnum
                           FROM tree AS c
                          WHERE c.parent_id = w.id
                       ) AS childnum
                  FROM tree AS w
                  JOIN cte ON w.parent_id = cte.id
               )
               SELECT id 
                 FROM cte
                WHERE childnum < 3
                ORDER BY rank ASC
                LIMIT 1
           )
         );

This query adds a child to the node of subtree having number of childs less than 3 and closest to the subtree root. Chosen node can be the subtree root itself if it has less than 3 childs. If more than one node of the same rank can be chosen as parent, arbitrary one is chosen. If you want to choose the node with the least number of childs you have to order that way: ORDER BY rank ASC, childnum ASC

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.