Как обрезать дублирующиеся ассоциации, чтобы получить уникальный наиболее полный набор

Question

Я не знаю, как сформулировать этот вопрос, не говоря уже о поиске ответов. Но вот мой лучший снимок. Предположим, у меня есть таблица

Col1   Col2
-----+-----
 A   | 1
 A   | 2
 A   | 3
 A   | 4
 B   | 1
 B   | 2
 B   | 3
 C   | 1
 C   | 2
 C   | 3
 D   | 1

Я хочу найти подмножество ассоциаций (строк), где:

1. В Col1
2. В Col2
3. Каждое значение в Col1 связано со значением в Col2

Таким образом, приведенный выше пример может дать такой результат

Col1   Col2
-----+-----
 A   | 4
 B   | 2
 C   | 3
 D   | 1

Обратите внимание, что A-4 должен быть в результате, потому что есть 4 уникальных буквы и 4 уникальных числа, поэтому, если вы не связываете A с 4, не остается подмножества, которое не отображает все значения в Col1 при сохранении Уникальность Col2.

Также обратите внимание, что было бы одинаково справедливо заменить B-2 и C-3 на B-3 и C-2. Мне все равно, какое подмножество выбрано, но я хочу, чтобы оно соответствовало всем требованиям.

Не каждый набор данных будет иметь подмножество, которое отвечает всем требованиям, но я хочу подобраться как можно ближе.

Я пытаюсь сделать это с помощью SQL-запроса. У меня был запрос, который, казалось, выполнил это для одного набора данных, но затем мне пришлось переписать его для немного другого набора (где Col2 на самом деле является парой столбцов) и не смог воспроизвести мой предыдущий успех. Мое первое решение использовало Min () и Group By и пару объединений для агрегированных результатов, чтобы помечать дубликаты для удаления в цикле, пока не останется ничего, что можно безопасно удалить. Мое более свежее решение заменяет запросы Group By выражениями ROW_NUMBER (), которые используют PARTITION_BY. Но я не могу понять, как обрабатывать случаи, когда в приведенном выше примере есть несколько действительных наборов результатов из пар с несколькими перекрестными связями, таких как B и C. Мой предыдущий запрос мог бы обработать его, но я не могу полностью понять, что я сделал (должно быть, у меня был хороший день, когда я его написал). Возможно, мне нужно выполнить JOIN для выражений ROW_NUMBER в моих подзапросах? Мой мозг выдал на сегодня. Я надеюсь, что кто-то может помочь мне найти гениально простое решение.

Answer 1

Проблема эквивалентна нахождению максимального совпадения в двудольном графе .Каждый элемент столбца представляет вершину, каждая строка представляет ребро.Связанная статья в Википедии содержит несколько указателей на алгоритмы для решения этой проблемы.Существует реализация венгерского алгоритма в библиотеке Google or-tools .

. Ниже приведен пример, сформулированный в виде графика, с красными краями, представляющими данное решение:

Мне было бы удивительно, если бы вы могли найти решение исключительно в SQL.

Answer 2

Попробуйте этот запрос, он не подходит для огромного набора данных, но делает то, что вы хотите, если в col1 есть значение, для которого он не может найти уникальный столбец col2, он поместил бы 0, который жестко закодирован, измените его на любое значение, чтобы указать отсутствие уникальной ценности. Я использовал таблицу с именем test (col1, col2) вместо имени вашей таблицы вместо места тестирования.

Это жадный алгоритм, который будет пытаться максимизировать вероятность привязки значения в Col1 ко всем значениям Col2. Шаги следующие.

1. Извлечение Col1 на основе количества значений Col2, с которым оно связано в порядке возрастания.
2. Начните с Col1, который имеет минимальное количество Col2, и свяжите значение (Начните с D, поскольку связано только одно значение).
3. Переход к следующему неассоциированному значению (B или C, так как они имеют 3 значения, связывают любое значение, которого нет в списке уже связанных значений, 1 связано с D, т. Е. 2 ​​или 3).
4. Повторите шаг 3 для всех значений в списке, выбранном на шаге 1.

Элемент списка

Следующий код реализует этот алгоритм и его неоптимальная реализация.

DECLARE @COUNTER    INT = 1
DECLARE @MAX        INT = 0  
DECLARE @COL2       CHAR(1) = NULL

DECLARE @TEMPTABLE TABLE
(
    ROWNUM  INT     IDENTITY(1,1)
    ,COL1   CHAR(1)
    ,COL2   INT
)

INSERT INTO @TEMPTABLE
SELECT COL1, 0
FROM    testing
GROUP BY COL1
ORDER BY COUNT(COL2)

SELECT @MAX = MAX(ROWNUM) FROM @TEMPTABLE

WHILE (  @COUNTER <= @MAX )
BEGIN
        UPDATE @TEMPTABLE 
        SET COL2 = T.COL2
        FROM TESTING T
        INNER JOIN @TEMPTABLE TT
        ON  T.COL1 = TT.COL1
        WHERE T.COL2 NOT IN (SELECT DISTINCT COL2 FROM @TEMPTABLE)
        AND TT.ROWNUM = @COUNTER
        SET @COUNTER = @COUNTER + 1
END

SELECT COL1, COL2 FROM @TEMPTABLE

Answer 3

Это, кажется, делает свое дело (я рассмотрю другие ответы и сравню после публикации):

CREATE TABLE Trial(Col1 nvarchar(5) not null, Col2 int not null, Eliminated bit not null)

INSERT INTO Trial(Col1, Col2, Eliminated) VALUES('A', 1, 0)
INSERT INTO Trial(Col1, Col2, Eliminated) VALUES('A', 2, 0)
INSERT INTO Trial(Col1, Col2, Eliminated) VALUES('A', 3, 0)
INSERT INTO Trial(Col1, Col2, Eliminated) VALUES('A', 4, 0)
INSERT INTO Trial(Col1, Col2, Eliminated) VALUES('B', 1, 0)
INSERT INTO Trial(Col1, Col2, Eliminated) VALUES('B', 2, 0)
INSERT INTO Trial(Col1, Col2, Eliminated) VALUES('B', 3, 0)
INSERT INTO Trial(Col1, Col2, Eliminated) VALUES('C', 1, 0)
INSERT INTO Trial(Col1, Col2, Eliminated) VALUES('C', 2, 0)
INSERT INTO Trial(Col1, Col2, Eliminated) VALUES('C', 3, 0)
INSERT INTO Trial(Col1, Col2, Eliminated) VALUES('D', 1, 0)

UPDATE T0 SET Eliminated = 1
FROM Trial T0
JOIN (
   SELECT Col1, COUNT(*) Dups
   FROM Trial
   WHERE Eliminated = 0
   GROUP BY Col1) T1
   ON T0.Col1 = T1.Col1
JOIN (
   SELECT Col2, COUNT(*) Dups
   FROM Trial
   WHERE Eliminated = 0
   GROUP BY Col2) T2
   ON T2.Col2 = T0.Col2
WHERE T2.Dups > T1.Dups AND T1.Dups > 1

UPDATE T0 SET Eliminated = 1
FROM Trial T0
JOIN (
   SELECT Col1, COUNT(*) Dups
   FROM Trial
   WHERE Eliminated = 0
   GROUP BY Col1) T1
   ON T0.Col1 = T1.Col1
JOIN (
   SELECT Col2, COUNT(*) Dups
   FROM Trial
   WHERE Eliminated = 0
   GROUP BY Col2) T2
   ON T2.Col2 = T0.Col2
WHERE T1.Dups > T2.Dups AND T2.Dups > 1

UPDATE T0 SET Eliminated = 1
FROM Trial T0
JOIN (
   SELECT Col1, Col2, ROW_NUMBER() OVER (PARTITION BY Col1 ORDER BY Col2) Dup
   FROM Trial
   WHERE Eliminated = 0) T1 ON T1.Col1 = T0.Col1 AND T1.Col2 = T0.Col2
JOIN (
   SELECT Col1, Col2, ROW_NUMBER() OVER (PARTITION BY Col2 ORDER BY Col1) Dup
   FROM Trial
   WHERE Eliminated = 0) T2 ON T2.Col1 = T0.Col1 AND T2.Col2 = T0.Col2
WHERE T1.Dup <> T2.Dup

Возможно, это не идеально, но, похоже, работает с моими данными.

Answer 4

Мне кажется, что вы стремитесь к чему-то, для чего SQL недостаточно силен.Это нестандартная алгоритмическая задача, и я думаю, что вам нужен настоящий язык программирования для ее достижения.Твоя задача напоминает мне шахматные загадки.