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

У меня есть таблица 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.

1
задан zvolkov 10 September 2010 в 22:57
поделиться