SQL 比较集，第二部分 : How to join sets of sets

Question

这question让我想起了整组比较的几个相关问题。鉴于:

1. 集合的集合，以及
2. 一个探针集合

三个问题:

1. 如何在 collection 中找到所有与 probe 匹配的集合，一个元素一个元素？
2. 如何在不使用显式循环结构的情况下找到 collection 中与 probe 集合匹配的所有集合？你如何加入集合集合？
3. 这是关系划分吗？如果不是，那是什么？

我对问题 1 有一个不错的解决方案(见下文)。

对于问题 2，我没有合适的关系解决方案。有接受者吗？

测试数据:

IF OBJECT_ID('tempdb..#elements') IS NOT NULL DROP TABLE #elements
IF OBJECT_ID('tempdb..#sets') IS NOT NULL DROP TABLE #sets

CREATE TABLE #sets (set_no INT, PRIMARY KEY (set_no))
CREATE TABLE #elements (set_no INT, elem CHAR(1), PRIMARY KEY (set_no, elem))

INSERT #elements VALUES (1, 'A')
INSERT #elements VALUES (1, 'B')
INSERT #elements VALUES (1, 'C')
INSERT #elements VALUES (1, 'D')
INSERT #elements VALUES (1, 'E')
INSERT #elements VALUES (1, 'F')
INSERT #elements VALUES (2, 'A')
INSERT #elements VALUES (2, 'B')
INSERT #elements VALUES (2, 'C')
INSERT #elements VALUES (3, 'D')
INSERT #elements VALUES (3, 'E')
INSERT #elements VALUES (3, 'F')
INSERT #elements VALUES (4, 'B')
INSERT #elements VALUES (4, 'C')
INSERT #elements VALUES (4, 'F')
INSERT #elements VALUES (5, 'F')

INSERT #sets SELECT DISTINCT set_no FROM #elements

第1题的设置及解法，set lookup:

IF OBJECT_ID('tempdb..#probe') IS NOT NULL DROP TABLE #probe
CREATE TABLE #probe (elem CHAR(1) PRIMARY KEY (elem))
INSERT #probe VALUES ('B')
INSERT #probe VALUES ('C')
INSERT #probe VALUES ('F')

-- I think this works.....upvotes for anyone who can demonstrate otherwise
SELECT set_no FROM #sets s
WHERE NOT EXISTS (
  SELECT * FROM #elements i WHERE i.set_no = s.set_no AND NOT EXISTS (
    SELECT * FROM #probe p WHERE p.elem = i.elem))
AND NOT EXISTS (
  SELECT * FROM #probe p WHERE NOT EXISTS (
    SELECT * FROM #elements i WHERE i.set_no = s.set_no AND i.elem = p.elem))

问题2的设置，无解:

IF OBJECT_ID('tempdb..#multi_probe') IS NOT NULL DROP TABLE #multi_probe
CREATE TABLE #multi_probe (probe_no INT, elem CHAR(1) PRIMARY KEY (probe_no, elem))
INSERT #multi_probe VALUES (1, 'B')
INSERT #multi_probe VALUES (1, 'C')
INSERT #multi_probe VALUES (1, 'F')
INSERT #multi_probe VALUES (2, 'C')
INSERT #multi_probe VALUES (2, 'F')
INSERT #multi_probe VALUES (3, 'A')
INSERT #multi_probe VALUES (3, 'B')
INSERT #multi_probe VALUES (3, 'C')

-- some magic here.....

-- result set:
-- probe_no | set_no
------------|--------
-- 1        | 4
-- 3        | 2

Answer 1

OK，我们一步一步来解决问题2:

(1) 内部连接集和探测它们各自的元素。通过这种方式，我们将了解测试集和探测集之间的关系(哪些集合与哪些探测有共同的元素):

SELECT
    e.set_no AS [test set],
    m.set_no AS [probe set],
    e.elem [common element]
FROM
    @elements e
JOIN
    @multi_probe m ON e.elem = m.elem

结果:

test set    probe set   common element
----------- ----------- --------------
1           3           A
1           1           B
1           3           B
1           1           C
1           2           C
1           3           C
1           1           F
1           2           F
2           3           A
2           1           B
2           3           B
2           1           C
2           2           C
2           3           C
3           1           F
3           2           F
4           1           B
4           3           B
4           1           C
4           2           C
4           3           C
4           1           F
4           2           F
5           1           F
5           2           F

(2) 计算每个测试集和探测集之间有多少共同元素(内连接意味着我们已经把“不匹配”放在一边)

SELECT
    e.set_no AS [test set],
    m.set_no AS [probe set],
    COUNT(*) AS [common element count]
FROM
    @elements e
    JOIN
        @multi_probe m ON e.elem = m.elem
GROUP BY
    e.set_no, m.set_no
ORDER BY
    e.set_no, m.set_no

结果:

 test set    probe set   common element count
----------- ----------- --------------------
1           1           3
1           2           2
1           3           3
2           1           2
2           2           1
2           3           3
3           1           1
3           2           1
4           1           3
4           2           2
4           3           2
5           1           1
5           2           1

(3) 将测试集和探测集的计数带上每一行(子查询可能不是最优雅的)

SELECT
    e.set_no AS [test set],
    m.set_no AS [probe set],
    COUNT(*) AS [common element count],
    (SELECT COUNT(*) FROM @elements e1 WHERE e1.set_no = e.set_no) AS [test set count],
    (SELECT COUNT(*) FROM @multi_probe m1 WHERE m1.set_no = m.set_no) AS [probe set count]
FROM
    @elements e
    JOIN @multi_probe m ON e.elem = m.elem
GROUP BY
    e.set_no, m.set_no
ORDER BY
    e.set_no, m.set_no

结果:

test set    probe set   common element count test set count probe set count
----------- ----------- -------------------- -------------- ---------------
1           1           3                    6              3
1           2           2                    6              2
1           3           3                    6              3
2           1           2                    3              3
2           2           1                    3              2
2           3           3                    3              3
3           1           1                    3              3
3           2           1                    3              2
4           1           3                    3              3
4           2           2                    3              2
4           3           2                    3              3
5           1           1                    1              3
5           2           1                    1              2

(4)求解:只保留那些元素个数相同的测试集和探测集，且这个数也是公共(public)元素的个数，即测试集和探测集相同

SELECT
    e.set_no AS [test set],
    m.set_no AS [probe set]
FROM
    @elements e
JOIN
    @multi_probe m ON e.elem = m.elem
GROUP BY
    e.set_no, m.set_no
HAVING
    COUNT(*) = (SELECT COUNT(*) FROM @elements e1 WHERE e1.set_no = e.set_no)
    AND (SELECT COUNT(*) FROM @elements e1 WHERE e1.set_no = e.set_no) = (SELECT COUNT(*) FROM @multi_probe m1 WHERE m1.set_no = m.set_no)
ORDER BY
    e.set_no, m.set_no

结果:

test set    probe set
----------- -----------
2           3
4           1

请原谅 @ 而不是 #，我更喜欢表变量 :)