Creating optimal graph relation in PostgreSQL

Question

I have a table in PostgreSQL which consists of 2 columns, first ID and second ID. Every entry in it means that there's a relation between first and second ID, and it can be guaranteed that first ID will always be larger than the second ID.

My goal is to process the table so that it can detect networks (multiple IDs that relates to one another), and change every relations of that networks in the table so that first ID is the large IDs in the network and the second ID is always the smallest ID in the network.
Example:

D->C , C->B , B->A , F->E , H->G

Will become:

D->A , C->A , B->A , F->E , H->G

Another example:

D->C , D->B , D->A

Will become:

D->A , C->A , B->A

How to do this using SQL or a Postgres procedural language?

Edit : The PostgreSQL version that i'm using is 9.4. The table consists of column id1 (integer) and id2 (integer), with both of them as primary key.

As to how to conclude that A is the smallest in the set of second example (A,B,C), I used this query to determine the smallest id2

SELECT id1, MIN(id2) FROM table GROUP BY id1

In your second example: How do you conclude that A is the smallest in the set (A, B, C)? Please always provide your Postgres version and, ideally, a table definition. — Erwin Brandstetter
– Erwin Brandstetter, Commented Apr 2, 2016 at 4:10

Erwin Brandstetter · Accepted Answer · 2016-04-02 04:08:54Z

1

Assuming a table like this:

CREATE TABLE tbl (
  id1 int
, id2 int
, PRIMARY KEY (id1, id2)
);

Circular references are not possible according to your logic.

This recursive CTE would do the job:

WITH RECURSIVE cte AS (
   SELECT t1.id1, t1.id2, t2.id2 AS next_id2
   FROM   tbl t1
   LEFT   JOIN tbl t2 ON t2.id1 = t1.id2

   UNION ALL
   SELECT t1.id1, t1.next_id2, t2.id2
   FROM   cte t1
   LEFT   JOIN tbl t2 ON t2.id1 = t1.next_id2
   WHERE  t1.next_id2 IS NOT NULL  -- stop iterating at end of graph
   )
SELECT id1, id2
FROM   cte
WHERE  next_id2 IS NULL;  -- only rows where the graph ends

In the non-recursive term, select every row and try to find the next step with a LEFT JOIN.

In the recursive term replace the second ID with the next step until we reach the end of the graph (next_id2 IS NULL).

In the outer SELECT only return rows where the graph ends. Result in arbitrary sort order.

It's unclear how you determine the deepest rabbit hole if graphs can fork.

edited Apr 2, 2016 at 4:08

answered Apr 2, 2016 at 3:35

Erwin Brandstetter

669k160 gold badges1.2k silver badges1.3k bronze badges

Sign up to request clarification or add additional context in comments.

3 Comments

Aldibe Over a year ago

Sorry for my late reply. I'm using PostgreSQL 9.4 and the assumption for the table is correct. I've never used recursive CTE before (still pretty new to database :/ ), so i'll look into it. Thanks :)

Aldibe Over a year ago

p.s : yes, there's no circular reference in the table. the possible problems that I've found are those two example, and probably the combination of those two.

Erwin Brandstetter Over a year ago

@Aldibe: Please put all defining information into the question. Press edit left under your question. And please also address my most important request for clarification: How do you conclude that A is the smallest in the set (A, B, C)?

Collectives™ on Stack Overflow

Creating optimal graph relation in PostgreSQL

1 Answer 1

3 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

3 Comments

Your Answer

Sign up or log in

Post as a guest

Related