Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
Introduction to transitive closure / Common Table Expressions / iterative queries in SQL

Teh Social Netswork!

CREATE TABLE users (
 id SERIAL PRIMARY KEY,
 name VARCHAR(10) NOT NULL
);


INSERT into users VALUES
  (DEFAULT, 'Abbe'), (DEFAULT, 'Berta'), (DEFAULT, 'Carl'), (DEFAULT, 'Dorota');


CREATE TABLE invites (
 inviter_id INTEGER NOT NULL,
 invitee_id INTEGER NOT NULL
);

ALTER TABLE invites ADD CONSTRAINT no_self_ref CHECK (inviter_id <> invitee_id);

INSERT into invites VALUES
(1,2), (1,3), (3,4);

Who was invited by Abbe?

SELECT * FROM users u
  LEFT JOIN invites i ON u.id = i.invitee_id
WHERE i.inviter_id = 1;

Who invited Dorota?

SELECT * FROM users u
  LEFT JOIN invites i ON u.id = i.inviter_id
WHERE i.invitee_id = 4;

Full chain of inviters?

WITH RECURSIVE transitive_closure(inviter_id, invitee_id, distance) AS
( SELECT inviter_id, invitee_id, 1 AS distance FROM invites
 
  UNION ALL
 
  SELECT tc.inviter_id, i.invitee_id, tc.distance + 1 FROM invites AS i
    JOIN transitive_closure AS tc
      ON i.inviter_id = tc.invitee_id
)
SELECT * FROM transitive_closure
ORDER BY inviter_id, invitee_id, distance;

Recursive Query Evaluation, from Postgres docs

Evaluate the non-recursive term. For UNION (but not UNION ALL), discard duplicate rows. Include all remaining rows in the result of the recursive query, and also place them in a temporary working table. 2. So long as the working table is not empty, repeat these steps:

  1. Evaluate the recursive term, substituting the current contents of the working table for the recursive self-reference. For UNION (but not UNION ALL), discard duplicate rows and rows that duplicate any previous result row. Include all remaining rows in the result of the recursive query, and also place them in a temporary intermediate table.
  2. Replace the contents of the working table with the contents of the intermediate table, then empty the intermediate table.

Friends! (graph, not tree)

CREATE TABLE friends (
  a INTEGER NOT NULL,
  b INTEGER NOT NULL
);

ALTER TABLE friends ADD CONSTRAINT no_self_ref CHECK (a <> b);

INSERT INTO friends VALUES
(1,2),(1,3),(2,3),(2,4), (3,4);


WITH RECURSIVE transitive_closure(a, b, distance) AS
( SELECT a, b, 1 AS distance FROM friends
 
  UNION ALL
 
  SELECT tc.a, friends.b, tc.distance + 1 FROM friends
    JOIN transitive_closure AS tc
      ON friends.a = tc.b
)
SELECT * FROM transitive_closure
ORDER BY a, b, distance;

Introduce circularity

INSERT INTO friends VALUES (4,1)

INFINITE LOOP! We need to keep track of path traversed.

WITH RECURSIVE transitive_closure(a, b, distance, path_string) AS
( SELECT a, b, 1 AS distance,
    a || '.' || b || '.' AS path_string
  FROM friends
 
  UNION ALL
 
  SELECT tc.a, friends.b, tc.distance + 1,
  tc.path_string || friends.b || '.' AS path_string
  FROM friends
    JOIN transitive_closure AS tc
      ON friends.a = tc.b
  WHERE tc.path_string NOT LIKE '%' || friends.b || '.%'
)
SELECT * FROM transitive_closure
ORDER BY a, b, distance; 

Using Postgres Array

WITH RECURSIVE transitive_closure(a, b, distance, path) AS
( SELECT a, b, 1 AS distance,
    ARRAY[a, b] AS path
  FROM friends
 
  UNION ALL
 
  SELECT tc.a, friends.b, tc.distance + 1,
  tc.path || friends.b AS path
  FROM friends
    JOIN transitive_closure AS tc
      ON friends.a = tc.b
  WHERE NOT friends.b = ANY(path)
)
SELECT * FROM transitive_closure
ORDER BY a, b, distance;

How am I related to X?

WITH RECURSIVE transitive_closure(a, b, distance, path_string) AS
( SELECT a, b, 1 AS distance,
    a || '.' || b || '.' AS path_string
  FROM friends
  WHERE a = 1
 
  UNION ALL
 
  SELECT tc.a, friends.b, tc.distance + 1,
  tc.path_string || friends.b || '.' AS path_string
  FROM friends
    JOIN transitive_closure AS tc
      ON friends.a = tc.b
  WHERE tc.path_string NOT LIKE '%' || friends.b || '.%'
   -- AND distance < 7 --  for other than small data set
)
SELECT * FROM transitive_closure
WHERE b = 4
ORDER BY a, b, distance; 

LINKS

http://www.postgresql.org/docs/9.1/static/queries-with.html

http://techportal.inviqa.com/2009/09/07/graphs-in-the-database-sql-meets-social-networks/

http://hashrocket.com/blog/posts/recursive-sql-in-activerecord

https://en.wikipedia.org/wiki/Common_table_expressions#Common_table_expression

Related: closure tables and HierarchyId

https://coderwall.com/p/lixing

http://stackoverflow.com/questions/17302716/hierarchical-sql-data-recursive-cte-vs-hierarchyid-vs-closure-table

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment