SQL复杂查询难题：如何判断有向图中两节点是否关联？

我被这个SQL查询卡了一天，需求如下：
生成一组tag（文章命名实体）对a和b，按共同出现的文章数量排序，这部分不难。但要额外检查link表，判断两个tag间是否存在有向关联（a->b或b->a）。

• 最低要求：过滤掉已关联的对
• 更优实现：返回所有对，若存在关联则显示type

基础Tag对生成查询 #

这是可正常运行的基础生成tag对的查询：

SELECT
   l.cluster AS left_id,
   l.cluster_type AS left_type,
   l.cluster_label AS left_label,
   r.cluster AS right_id,
   r.cluster_type AS right_type,
   r.cluster_label AS right_label,
   count(distinct(l.article)) AS articles
FROM tag AS l, tag AS r
WHERE
   l.cluster > r.cluster
   AND l.article = r.article
GROUP BY l.cluster, l.cluster_label, l.cluster_type, r.cluster, r.cluster_label, r.cluster_type
ORDER BY count(distinct(l.article)) DESC;

基于CTE的关联Tag对查询 #

下面是获取所有已关联Tag对的子方案，但它无法显示未关联对，也不能同时展示两类对，能不能通过links CTE处理未关联对？

WITH links AS (
  SELECT
    greatest(link.source_cluster, link.target_cluster) AS big,
    least(link.source_cluster, link.target_cluster) AS smol,
    link.type AS type
  FROM link AS link
)
SELECT l.cluster AS left_id, l.cluster_type AS left_type, l.cluster_label AS left_label, r.cluster AS right_id, r.cluster_type AS right_type, r.cluster_label AS right_label,
  count(distinct(l.article)) AS articles,
  array_agg(distinct(links.type)) AS link_types
FROM tag AS r, tag AS l
  JOIN links ON l.cluster = links.big
WHERE
  l.cluster > r.cluster
  AND l.article = r.article
  AND r.cluster = links.smol
GROUP BY l.cluster, l.cluster_label, l.cluster_type, r.cluster, r.cluster_label, r.cluster_type
ORDER BY count(distinct(l.article)) DESC

表结构定义 #

CREATE TABLE tag (
    cluster character varying(40),
    article character varying(255),
    cluster_type character varying(10),
    cluster_label character varying,
);

CREATE TABLE link (
    source_cluster character varying(40),
    target_cluster character varying(40),
    type character varying(255),
);

示例数据 #

tag表数据 #

"cluster","cluster_type","cluster_label","article"
"fffcc580c020f689e206fddbc32777f0d0866f23","LOC","Russia","a"
"fffcc580c020f689e206fddbc32777f0d0866f23","LOC","Russia","b"
"fff03a54c98cf079d562998d511ef2823d1f1863","PER","Vladimir Putin","a"
"fff03a54c98cf079d562998d511ef2823d1f1863","PER","Vladimir Putin","b"
"fff03a54c98cf079d562998d511ef2823d1f1863","PER","Vladimir Putin","d"
"ff9be8adf69cddee1b910e592b119478388e2194","LOC","Moscow","a"
"ff9be8adf69cddee1b910e592b119478388e2194","LOC","Moscow","b"
"ffeeb6ebcdc1fe87a3a2b84d707e17bd716dd20b","LOC","Latvia","a"
"ffd364472a999c3d1001f5910398a53997ae0afe","ORG","OCCRP","a"
"ffd364472a999c3d1001f5910398a53997ae0afe","ORG","OCCRP","d"
"fef5381215b1dfded414f5e60469ce32f3334fdd","ORG","Moldindconbank","a"
"fef5381215b1dfded414f5e60469ce32f3334fdd","ORG","Moldindconbank","c"
"fe855a808f535efa417f6d082f5e5b6581fb6835","ORG","KGB","a"
"fe855a808f535efa417f6d082f5e5b6581fb6835","ORG","KGB","b"
"fe855a808f535efa417f6d082f5e5b6581fb6835","ORG","KGB","d"
"fff14a3c6d8f6d04f4a7f224b043380bb45cb57a","ORG","Moldova","a"
"fff14a3c6d8f6d04f4a7f224b043380bb45cb57a","ORG","Moldova","c"

link表数据 #

"source_cluster","target_cluster","type"
"fff03a54c98cf079d562998d511ef2823d1f1863","fffcc580c020f689e206fddbc32777f0d0866f23","LOCATED"
"fe855a808f535efa417f6d082f5e5b6581fb6835","fff03a54c98cf079d562998d511ef2823d1f1863","EMPLOYER"
"fff14a3c6d8f6d04f4a7f224b043380bb45cb57a","fef5381215b1dfded414f5e60469ce32f3334fdd","LOCATED"

解决方案 #

方案1：过滤已关联的Tag对（满足最低要求） #

通过LEFT JOIN关联预处理后的关联数据，筛选出无关联的记录：

WITH links AS (
  SELECT
    greatest(source_cluster, target_cluster) AS big,
    least(source_cluster, target_cluster) AS smol
  FROM link
),
tag_pairs AS (
  SELECT
    l.cluster AS left_id,
    l.cluster_type AS left_type,
    l.cluster_label AS left_label,
    r.cluster AS right_id,
    r.cluster_type AS right_type,
    r.cluster_label AS right_label,
    COUNT(DISTINCT l.article) AS articles
  FROM tag l
  JOIN tag r ON l.article = r.article AND l.cluster > r.cluster
  GROUP BY l.cluster, l.cluster_type, l.cluster_label, r.cluster, r.cluster_type, r.cluster_label
)
SELECT *
FROM tag_pairs tp
LEFT JOIN links lk ON tp.left_id = lk.big AND tp.right_id = lk.smol
WHERE lk.big IS NULL
ORDER BY tp.articles DESC;

方案2：返回所有Tag对并显示关联类型（更优实现） #

用LEFT JOIN保留所有Tag对，聚合关联类型，无关联时link_types返回NULL：

WITH links AS (
  SELECT
    greatest(source_cluster, target_cluster) AS big,
    least(source_cluster, target_cluster) AS smol,
    type
  FROM link
),
tag_pairs AS (
  SELECT
    l.cluster AS left_id,
    l.cluster_type AS left_type,
    l.cluster_label AS left_label,
    r.cluster AS right_id,
    r.cluster_type AS right_type,
    r.cluster_label AS right_label,
    COUNT(DISTINCT l.article) AS articles
  FROM tag l
  JOIN tag r ON l.article = r.article AND l.cluster > r.cluster
  GROUP BY l.cluster, l.cluster_type, l.cluster_label, r.cluster, r.cluster_type, r.cluster_label
)
SELECT
  tp.*,
  ARRAY_AGG(DISTINCT lk.type) AS link_types
FROM tag_pairs tp
LEFT JOIN links lk ON tp.left_id = lk.big AND tp.right_id = lk.smol
GROUP BY tp.left_id, tp.left_type, tp.left_label, tp.right_id, tp.right_type, tp.right_label, tp.articles
ORDER BY tp.articles DESC;

核心逻辑说明 #

1. tag_pairs CTE先生成所有基础Tag对及共同文章数，拆分逻辑保证可读性
2. links CTE用greatest和least统一关联对的顺序，和Tag对的left_id > right_id规则对齐，避免重复匹配
3. 通过LEFT JOIN保留所有Tag对，再用聚合函数收集关联类型，无关联时自然返回NULL

内容的提问来源于stack exchange，提问作者pudo