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:
- 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.
- 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