Сравнение наборов SQL, часть II: Как объединить наборы наборов

Question

Этот вопрос напомнил мне пару проблем, связанных с полным набором сравнений. Дано:

1. a collection наборов и
2. a probe set

Три вопроса:

1. Как найти все наборы в collection, которые соответствуют probe, элемент для элемента?
2. Как найти все наборы в collection, которые соответствуют коллекции probe s, без использования явных циклических конструкций? Как вы объединяете наборы наборов?
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, настройка поиска:

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

ОК, давайте решим вопрос 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) Найти решение: сохранить толькоте наборы тестов и наборов датчиков, которые имеют одинаковое количество элементов И это число также является числом общих элементов, то есть набор тестов и набор датчиков идентичны

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

Извините @ с вместо # с, мне больше нравятся табличные переменные:)

Answer 2

Могу ли я представить более «математически склонное» решение вопроса (1) в синтаксисе SQL Server:

SELECT
    s.set_no
FROM
    #sets s
    JOIN @elements e ON s.set_no = e.set_no
    LEFT JOIN #probe p ON e.elem = p.elem
GROUP BY
    s.set_no
HAVING
    COUNT(DISTINCT p.elem) = COUNT(*)
    AND COUNT(*) = (SELECT COUNT(*) FROM #probe)

• COUNT(*) всегда будет обозначать количество элементов в каждом наборе тестов (из-за LEFT JOIN)
• COUNT(DISTINCT p.elem) будет обозначать количество «совпадений» между элементом в наборе тестов и элементом в наборе проб (поскольку NULL s не будет учитываться), т.е. сколько элементов в наборе проб было также присутствует в тестовом наборе

В переводе на математические термины COUNT(DISTINCT p.elem) = COUNT(*) будет означать, что набор тестов является подмножеством набора зондов (test ⊆ probe), в то время как COUNT(*) = (SELECT COUNT(*) FROM #probe) будет означать, что мощность набора тестов равна мощности набора тестов. (|test| = |probe|). Из этих двух условий мы заключаем, что test = probe.

Answer 3

[Отвечая на мой собственный вопрос ....]

Во-первых, решение. Синтаксис EXCEPT может корректно обрабатывать несколько столбцов и NULL, поэтому это ближе к общему решению:

SELECT 
  s.set_no AS test_set_no
, p.set_no AS probe_set_no
FROM #test_sets s CROSS JOIN #probe_sets p
WHERE NOT EXISTS (
    SELECT elem FROM #test_elements  te WHERE te.set_no = s.set_no EXCEPT 
    SELECT elem FROM #probe_elements pe WHERE pe.set_no = p.set_no)
  AND NOT EXISTS (
    SELECT elem FROM #probe_elements pe WHERE pe.set_no = p.set_no EXCEPT
    SELECT elem FROM #test_elements  te WHERE te.set_no = s.set_no)
ORDER BY 
  test_set_no
, probe_set_no

Далее пересмотренный набор данных:

IF OBJECT_ID('tempdb..#test_elements') IS NOT NULL DROP TABLE #test_elements
IF OBJECT_ID('tempdb..#test_sets') IS NOT NULL DROP TABLE #test_sets

CREATE TABLE #test_sets (set_no INT, PRIMARY KEY (set_no))
CREATE TABLE #test_elements (set_no INT, elem CHAR(1), PRIMARY KEY (set_no, elem))

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

INSERT #test_sets SELECT DISTINCT set_no FROM #test_elements

IF OBJECT_ID('tempdb..#probe_elements') IS NOT NULL DROP TABLE #probe_elements
IF OBJECT_ID('tempdb..#probe_sets') IS NOT NULL DROP TABLE #probe_sets
CREATE TABLE #probe_sets (set_no INT PRIMARY KEY (set_no))
CREATE TABLE #probe_elements (set_no INT, elem CHAR(1) PRIMARY KEY (set_no, elem))

INSERT #probe_elements VALUES (1, 'B')
INSERT #probe_elements VALUES (1, 'C')
INSERT #probe_elements VALUES (1, 'F')
INSERT #probe_elements VALUES (2, 'C')
INSERT #probe_elements VALUES (2, 'F')
INSERT #probe_elements VALUES (3, 'A')
INSERT #probe_elements VALUES (3, 'B')
INSERT #probe_elements VALUES (3, 'C')

INSERT #probe_sets SELECT DISTINCT set_no FROM #probe_elements

Для сравнения, используя агрегаты, согласно CyberDude:

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