How to identify and list Circular Reference elements in Postgres

Question

I have an employee , manager hierarchy which could end up being circular.

Ex: 28397468N>88518119N>87606705N>28397468N

Create Table emp_manager (  Emp_id varchar(30), Manager_id varchar(30));

Insert into emp_manager    values ('28397468N','88518119N');

Insert into emp_manager    values ('88518119N','87606705N');

Insert into emp_manager    values ('87606705N','28397468N');

My requirement is: When my proc is called and there are circular hierarchies in the emp_manager table, we should return an error listing the employees in the hierarchy.

The below link contains some useful info: https://mccalljt.io/blog/2017/01/postgres-circular-references/

I have modified it as below:

select * from (
WITH RECURSIVE circular_managers(Emp_id, Manager_id, depth, path, cycle) AS (
SELECT u.Emp_id, u.Manager_id, 1,
ARRAY[u.Emp_id],
false
FROM emp_manager u  
UNION ALL
SELECT u.Emp_id, u.Manager_id, cm.depth + 1,
(path || u.Emp_id)::character varying(32)[],
u.Emp_id = ANY(path)
FROM emp_manager u, circular_managers cm
WHERE u.Emp_id = cm.Manager_id AND NOT cycle
)
select
     distinct (path) d
FROM circular_managers
WHERE cycle
AND path[1] = path[array_upper(path, 1)]) cm

BUT, the problem is, it is returning all combinations of the hierarchy:

{28397468N,88518119N,87606705N,28397468N}
{87606705N,28397468N,88518119N,87606705N}
{88518119N,87606705N,28397468N,88518119N}

I need a simple answer like this:

28397468N>88518119N>87606705N>28397468N

even this will do:
28397468N>88518119N>87606705N

Please help!

I don't understand from where appears id='28397468N' in results. I don't see an `INSERT` with such value. Did you missed it i? — Alex Yu, Jun 28 '21 at 12:37
I modified the question to be coherent with the data now. Please check. — AnuC, Jun 28 '21 at 14:40
What do you mean by "*SORT doesn't work since my employee IDs are VARCHAR and not INT*"? Sure you can `ORDER BY` a varchar column just like an integer column. — Bergi, Jun 28 '21 at 18:29
"*My requirement is: When my proc is called and there are circular hierarchies*" - what procedure are you talking about? Is it a trigger that should prevent such circular references from occurring by throwing an exception upon insert/update? Is it a stored view that should just list the circles? — Bergi, Jun 28 '21 at 18:31
It is a part of a stored procedure that should list each unique circle if there are circular references. I have added my SQL in the question. — AnuC, Jun 29 '21 at 05:03

Alex Yu · Accepted Answer · 2021-06-29T17:10:46.553

So all references:

{28397468N,88518119N,87606705N,28397468N}
{87606705N,28397468N,88518119N,87606705N}
{88518119N,87606705N,28397468N,88518119N}

are correct but just start from different element.

I need a simple answer like this: 28397468N>88518119N>87606705N>28397468N

So what's needed is a filter for the same circle refs.

Let's do that in a way:

sort distinct items in arrays
aggregate them back - so for all references it will be '{28397468N,87606705N,88518119N}'
use produced value for DISTINCT FIRST_VALUE

WITH D (circle_ref ) AS (
VALUES
('{28397468N,88518119N,87606705N,28397468N}'::text[]),
('{87606705N,28397468N,88518119N,87606705N}'::text[]),
('{88518119N,87606705N,28397468N,88518119N}'::text[])
), ordered AS (
SELECT 
        D.circle_ref,
        (SELECT ARRAY_AGG(DISTINCT el ORDER BY el) FROM  UNNEST(D.circle_ref) AS el ) AS ordered_circle
    FROM 
        D
)
SELECT DISTINCT
        FIRST_VALUE (circle_ref) OVER (PARTITION BY ordered_circle ORDER BY circle_ref) AS circle_ref 
    FROM 
        ordered;

circle_ref
{28397468N,88518119N,87606705N,28397468N}

DB Fiddle: https://www.db-fiddle.com/f/6ytb2v11s8T95PPLoTZZed/0

score 0 · Answer 2 · answered Jun 28 '21 at 16:54

To prevent circular references, you can use a closure table and a trigger - as explained in https://stackoverflow.com/a/38701519/5962802 The closure table will also allow you to easily get all subordinates for a given supervisor (no matter how deep in the hierarchy) - or all direct bosses of a given employee (up to the root).

Before using the rebuild_tree stored procedure you will have to remove all circular references from the hierarchy.

How to identify and list Circular Reference elements in Postgres

2 Answers2