Graph Data
SELECT *
FROM edges;
WITH RECURSIVE
transitive_closure(source, destination, path_string) AS (
SELECT from_node, to_node,
from_node || '.' || to_node || '.' AS path_string
FROM edges
UNION ALL
SELECT tc.source, e.to_node,
tc.path_string || e.to_node || '.' AS path_string
FROM edges e
JOIN transitive_closure AS tc
ON e.from_node = tc.destination
WHERE tc.path_string NOT LIKE '%' || e.to_node || '.%'
)
SELECT *
FROM transitive_closure
ORDER BY source, destination;
DROP VIEW IF EXISTS edges2;
CREATE VIEW edges2 (from_node, to_node) AS (
SELECT from_node, to_node
FROM edges
UNION ALL
SELECT to_node, from_node
FROM edges
);
WITH RECURSIVE
transitive_closure(source, destination, path_string) AS (
SELECT from_node, to_node,
from_node || '.' || to_node || '.' AS path_string
FROM edges2
UNION ALL
SELECT tc.source, e.to_node,
tc.path_string || e.to_node || '.' AS path_string
FROM edges2 AS e
JOIN transitive_closure AS tc
ON e.from_node = tc.destination
WHERE tc.path_string NOT LIKE '%' || e.to_node || '.%'
)
SELECT *
FROM transitive_closure
ORDER BY source, destination;
WITH RECURSIVE
cycles AS (
SELECT src,
dest,
1 AS depth,
ARRAY[dest] AS path,
false AS cycle
FROM graph
UNION ALL
SELECT g.src,
g.dest,
c.depth + 1,
c.path || g.dest AS path,
g.dest = ANY(path) AS cycle
FROM cycles c
INNER JOIN graph g
ON c.dest = g.src AND c.cycle = false
),
mark_first AS (
SELECT *,
CASE
WHEN path <@ LEAD(path) OVER() THEN 0
ELSE 1
END AS contains
FROM cycles
WHERE cycle = TRUE
)
--SELECT * FROM cycles WHERE cycle = true ORDER BY src
SELECT src AS alpha_omega,
depth AS deepest,
path,
cycle
FROM mark_first
WHERE contains = 1
ORDER BY src;
SELECT *
FROM marked_loops;
CREATE TABLE folders (id int NOT NULL, parent_id int);
INSERT INTO folders
VALUES (1,null),
(2,1),
(3,1),
(4,3),
(5,2),
(6,1),
(7,1),
(8,7),
(9,7),
(10,7),
(11,15),
(12,2),
(13,11),
(14,13),
(15,14),
(21,21);
SELECT * FROM folders;
not_in_cycle as (
SELECT f.id AS node
FROM folders AS f
WHERE f.parent_id IS NULL
UNION ALL
SELECT f.id AS node
FROM folders AS f
INNER JOIN not_in_cycle AS c
ON f.parent_id = c.node
),
in_cycle AS (
SELECT f.id AS node
FROM folders AS f
EXCEPT
SELECT n.node
FROM not_in_cycle AS n
),
cycle_paths as (
SELECT
i.node, -- will start from any node
f.parent_id AS reached, -- we can reach its parent
greatest(i.node, f.parent_id) AS head -- we'll use this later to uniquely identify cycles
FROM in_cycle AS i
INNER JOIN folders f
ON i.node = f.id
-- what else we can reach?
UNION ALL
-- parents of reached node, of course.
-- end the recursions when the cycle_paths node != folders parent_id
SELECT
cp.node,
f.parent_id AS reached,
greatest(cp.head, f.parent_id) AS head
FROM cycle_paths as cp
INNER JOIN folders AS f
ON f.id = cp.reached
WHERE cp.node != f.parent_id
),
unique_cycles AS (
SELECT cp.head AS cycle_id, cp.reached
FROM cycle_paths as cp
WHERE cp.head = cp.node
UNION
SELECT cp.head AS cycle_id,
cp.head AS reached
FROM cycle_paths AS cp
WHERE cp.head = cp.node
),
cycles AS (
SELECT DISTINCT i.*
FROM (
SELECT
ARRAY_AGG(ucp.reached) OVER (PARTITION BY ucp.cycle_id) AS cycle
FROM unique_cycles AS ucp
ORDER BY ucp.cycle_id
) AS i
)
SELECT cycle
FROM (
SELECT *,
CASE
WHEN cycle <@ LEAD(cycle) OVER() THEN 1
ELSE 0
END AS contains
FROM cycles
) container
WHERE contains = 0;
WITH RECURSIVE
transitive_closure(source, destination, distance, path_string) AS (
SELECT from_node, to_node, 1 AS distance,
from_node || '.' || to_node || '.' AS path_string
FROM edges
WHERE from_node = 1 -- source
UNION ALL
SELECT tc.source, e.to_node, tc.distance + 1,
tc.path_string || e.to_node || '.' AS path_string
FROM edges AS e
JOIN transitive_closure AS tc
ON e.from_node = tc.destination
WHERE tc.path_string NOT LIKE '%' || e.to_node || '.%'
)
SELECT *
FROM transitive_closure
WHERE destination = 3 -- destination
ORDER BY source, destination, distance;
WITH RECURSIVE
transitive_closure(source, destination, distance, path_string) AS (
SELECT from_node, to_node, 1 AS distance,
from_node || '.' || to_node || '.' AS path_string
FROM edges2
UNION ALL
SELECT tc.source, e.to_node, tc.distance + 1,
tc.path_string || e.to_node || '.' AS path_string
FROM edges2 AS e
JOIN transitive_closure AS tc
ON e.from_node = tc.destination
WHERE tc.path_string NOT LIKE '%' || e.to_node || '.%'
)
SELECT source, destination, min(distance) AS min_distance
FROM transitive_closure
WHERE source = 1 AND destination = 3
GROUP BY source, destination
ORDER BY source, destination;
WITH RECURSIVE
transitive_closure(source, destination, distance, path_string) AS (
SELECT from_node, to_node, 1 AS distance,
from_node || '.' || to_node || '.' AS path_string
FROM edges2
WHERE from_node = 1 -- set the starting node
UNION ALL
SELECT tc.source, e.to_node, tc.distance + 1,
tc.path_string || e.to_node || '.' AS path_string
FROM edges2 AS e
JOIN transitive_closure AS tc
ON e.from_node = tc.destination
WHERE tc.path_string NOT LIKE '%' || e.to_node || '.%'
AND tc.distance = 0 -- limit recursion at the first level
)
SELECT *
FROM transitive_closure;
SELECT destination
FROM (
WITH RECURSIVE
transitive_closure(source, destination, distance, path_string) AS (
SELECT from_node, to_node, 1 AS distance,
from_node || '.' || to_node || '.' AS path_string
FROM edges2
WHERE from_node = 1 -- set the starting node
UNION ALL
SELECT tc.source, e.to_node, tc.distance + 1,
tc.path_string || e.to_node || '.' AS path_string
FROM edges2 AS e
JOIN transitive_closure AS tc
ON e.from_node = tc.destination
WHERE tc.path_string NOT LIKE '%' || e.to_node || '.%'
AND tc.distance = 0 -- limit recursion at the first level
)
SELECT destination
FROM transitive_closure
UNION ALL(
WITH RECURSIVE
transitive_closure(source, destination, distance, path_string) AS (
SELECT from_node, to_node, 1 AS distance,
from_node || '.' || to_node || '.' AS path_string
FROM edges2
WHERE from_node = 3 -- set the target node
UNION ALL
SELECT tc.source, e.to_node, tc.distance + 1,
tc.path_string || e.to_node || '.' AS path_string
FROM edges2 AS e
JOIN transitive_closure AS tc
ON e.from_node = tc.destination
WHERE tc.path_string NOT LIKE '%' || e.to_node || '.%'
AND tc.distance = 0 -- limit recursion at the first level
)
SELECT destination
FROM transitive_closure
)
) immediate_connections
GROUP BY destination
HAVING COUNT(destination) = 2;
WITH RECURSIVE
transitive_closure(source, destination, distance, path_string) AS (
SELECT src, dest, 1 AS distance,
src || '.' || dest || '.' AS path_string
FROM graph
WHERE src LIKE 'B' -- set the starting node
UNION ALL
SELECT tc.source, g.dest, tc.distance + 1,
tc.path_string || g.dest || '.' AS path_string
FROM graph AS g
JOIN transitive_closure AS tc
ON g.src = tc.destination
WHERE tc.path_string NOT LIKE '%' || g.dest || '.%'
AND tc.distance < 3 -- limit the recursion after this many levels
)
SELECT source, destination, path_string, distance--, MIN(distance)
FROM transitive_closure
--WHERE destination LIKE 'E' -- optionally choose one path from the result (remove this)
GROUP BY source, destination, path_string, distance
HAVING MIN(distance) = 3; --set the minimum distance
WITH RECURSIVE
transitive_closure(source, destination, distance, path_string) AS (
SELECT src, dest, 1 AS distance,
src || '.' || dest || '.' AS path_string,
dest AS direct_connection
FROM graph
WHERE src LIKE 'B' -- set the starting node
UNION ALL
SELECT tc.source, g.dest, tc.distance + 1,
tc.path_string || g.dest || '.' AS path_string,
tc.direct_connection
FROM graph g
JOIN transitive_closure tc
ON g.src = tc.destination
WHERE tc.path_string NOT LIKE '%' || g.dest || '.%'
AND tc.distance <= 2
)
SELECT *
FROM transitive_closure
WHERE destination LIKE 'E' -- set the target node
GROUP BY source, destination, distance, path_string, direct_connection
ORDER BY source, destination, distance;
JOIN (
WITH RECURSIVE
transitive_closure(source, destination, distance, path_string) AS (
SELECT src, dest, 1 AS distance,
src || '.' || dest || '.' AS path_string,
dest AS direct_connection
FROM graph
WHERE src LIKE 'B' -- set the starting node
UNION ALL
SELECT tc.source, g.dest, tc.distance + 1,
tc.path_string || g.dest || '.' AS path_string,
tc.direct_connection
FROM graph g
JOIN transitive_closure tc
ON g.src = tc.destination
WHERE tc.path_string NOT LIKE '%' || g.dest || '.%'
AND tc.distance <= 2
)
SELECT DISTINCT destination
FROM transitive_closure
WHERE distance <= 1
) tc
JOIN interests i
ON bi.interest = i.interest -- equivalence
JOIN (
[transitive_closure goes here]
) tc
ON i.id = tc.destination
SELECT i.id, i.rank AS interest_rank,
i.interest AS shared_interest,
ABS(bi.rank - i.rank) AS rank_variance
FROM (
SELECT id,
rank,
interest,
MAX(rank) OVER(PARTITION BY id) + 1 AS range
FROM interests
WHERE id LIKE 'B' -- subject
) bi
JOIN interests i
ON bi.interest = i.interest -- equivalence
JOIN (
WITH RECURSIVE
transitive_closure(source, destination, distance, path_string) AS (
SELECT src, dest, 1 AS distance,
src || '.' || dest || '.' AS path_string,
dest AS direct_connection
FROM graph
WHERE src LIKE 'B' -- set the starting node
UNION ALL
SELECT tc.source, g.dest, tc.distance + 1,
tc.path_string || g.dest || '.' AS path_string,
tc.direct_connection
FROM graph g
JOIN transitive_closure tc
ON g.src = tc.destination
WHERE tc.path_string NOT LIKE '%' || g.dest || '.%'
AND tc.distance <= 2
)
SELECT DISTINCT destination
FROM transitive_closure
WHERE distance <= 1
) tc
ON i.id = tc.destination
WHERE i.rank < bi.range -- priority
AND i.id NOT LIKE 'B' -- candidates only
AND ABS(bi.rank - i.rank) <= 1 -- similarity
ORDER BY id, interest_rank, rank_variance;
SELECT *
FROM reviews;
norms AS (
SELECT reviewer,
SUM(EXP(LN(rating * rating))) AS rating_sqr
FROM reviews
GROUP BY reviewer
),
WITH
norms AS (
SELECT reviewer,
SUM(EXP(LN(rating * rating))) AS rating_sqr
FROM reviews
GROUP BY reviewer
),
cosinesim AS (
SELECT x.reviewer, y.reviewer,
SUM(EXP(LN(x.rating * y.rating)))
/ SQRT(nx.rating_sqr * ny.rating_sqr) AS cosinesimilarity
FROM reviews x
JOIN reviews y
ON x.film = y.film
JOIN norms nx
ON (nx.reviewer = x.reviewer)
JOIN norms ny
ON (ny.reviewer = y.reviewer)
WHERE x.reviewer < y.reviewer
GROUP BY x.reviewer, y.reviewer, nx.rating_sqr, ny.rating_sqr
)
SELECT *
FROM cosinesim
ORDER BY cosinesimilarity DESC;