Идентификация графов в куче связанных узлов - как это называется?

Question

У меня есть таблица SQL с тремя столбцами X, Y, Z. Мне нужно разбить ее на группы таким образом, чтобы все записи с одинаковыми значениями X или Y или Z были отнесены к одной и той же группе. Мне нужно убедиться, что записи с одинаковыми значениями X или Y или Z никогда не разделяются на несколько групп.

Если вы рассматриваете записи как узлы, а значения X, Y, Z как ребра, эта проблема аналогична поиску всех графов, где узлы в каждом графе будут связаны прямо или косвенно через X, Y или Z- ребро, но у каждого графа не будет общих ребер с другими графами (в противном случае он будет частью того же графа).

Несколько лет назад я знал, как это называется, и даже запомнил алгоритм, но теперь он ускользает от меня. Пожалуйста, скажите мне, как эта проблема называется, чтобы я мог Google для решения. Если у вас сейчас хороший алгоритм - укажите мне на него. Если у вас есть реализация SQL - я выйду за вас замуж:)

Пример:

    X                   Y               Z            BUCKET
---------     ----------------      ---------      -----------
   1                   34              56              1
   54                  43              45              2
   1                   12              22              1
   2                   34              11              1

Последняя строка находится в сегменте 1 из-за значения Y = 34, которое совпадает со значением первой строки, которая находится в сегменте 1.

Answer 1

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

Однако, для этой конкретной проблемы естьможет быть некоторым простым решением, достижимым с помощью SQL, который я не искал.

Answer 2

Почему бы вам изначально GROUP BY не поставить один из столбцов (скажем, X), сделать сегменты, затем сделать это для Y и Z, каждый раз объединяя все сегменты из предыдущего шага, если вы найдете новые группы.

Повторяйте процесс для X, Y и Z, пока сегменты не перестанут меняться.

Работаете ли вы на линк-ин или фейсбук?:)

Answer 3

чтобы узнать, сколько узлов в каждой группе x:

select x, count(x) 
from mytable
group by x

или найти список множеств x:

select distinct x from mytable;