Как генерировать связанные компоненты с учетом большого графика в BigQuery?

Question

Я хотел бы сгенерировать связанных компонентов графика, используя BigQuery.

Учитывая, следующий график (представлен парами узлов, которые связаны):

(E1, E2)
(E2, E3)
(E3, E4)
(E4, E5)

Мы можем сделать вывод, что все эти компоненты связаны и, следовательно, представляют один связанный компонент:

(E1, E2, E3, E4, E5)

Вот традиционные алгоритмы, используемые для генерации связанных компонентов графика: Поиск в ширину и Поиск в глубину

Мой начальныйИдея заключалась в том, чтобы воссоздать пары узлов, которые совпадают, так что все сущности в конечном итоге будут указывать на один общий узел (заставляя дочерние узлы указывать на их узлы-предки).Поэтому, если (E1, E2) является парой, а (E2, E3) является парой.Я могу написать логику SQL для создания новой пары (E1, E3), а затем могу отказаться (E2, E3).

Вот более подробный пример:

Ввод:

(E1, E2)
(E2, E3)
(E3, E4)
(E4, E5)

Итерация 1:

(E1, E2)
(E1, E3) which replaces (E2, E3)
(E2, E4) which replaces (E3, E4)
(E3, E5) which replaces (E4, E5)

Итерация 2:

(E1, E2)
(E1, E3)
(E1, E4) which replaces (E2, E4)
(E1, E5) which replaces (E3, E5)

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

Можно ли быстрее генерировать подключенные компоненты при наличии пар совпадений в таблице BigQuery?

Ввод:

|--------------------|------------------|
|      Entity 1      |      Entity 2    |
|--------------------|------------------|
|         E1         |         E2       |
|--------------------|------------------|
|         E2         |         E3       |
|--------------------|------------------|
|         E3         |         E4       |
|--------------------|------------------|
|         E4         |         E5       |
|--------------------|------------------|

Требуемый вывод:

Я хотел бы написать запрос, который читает в таблице ввода выше и выводит следующее:

|--------------------|------------------|
|       Entity       |       Group      |
|--------------------|------------------|
|          E1        |         1        |
|--------------------|------------------|
|          E2        |         1        |
|--------------------|------------------|
|          E3        |         1        |
|--------------------|------------------|
|          E4        |         1        |
|--------------------|------------------|
|          E5        |         1        |
|--------------------|------------------|

Возможно ли это в BigQuery?

Answer 1

Вам необходимо рекурсивное соединение: https://en.wikipedia.org/wiki/Recursive_join

Но поскольку BigQuery не поддерживает это напрямую, вы можете повторно объединить таблицу с самим собой, создать новую таблицу подключенных компонентов и делать это до тех пор, покаколичество компонентов больше не меняется.

Что-то вроде:

select a, min(if(c > a, a, c)) c 
from (select x.a, y.c from data x join data y on x.c = y.a)
group by a;

Это присваивает идентификатор компонента c каждому значению на основе минимума его собственного значения и идентификатора подключенного значения.

После каждого запуска проверяйте

select count(distinct c) from data;

Как только он перестал меняться - все готово.

Answer 2

Вы можете попробовать использовать ROW_NUMBER с оконной функцией, чтобы сделать это.

Что такое функция окна.

OVER (   
       [ <PARTITION BY clause> ]  
       [ <ORDER BY clause> ]   
       [ <ROW or RANGE clause> ]  
      )  

Определяет разбиение и упорядочение набора строк перед применением связанной оконной функции. Таким образом, предложение OVER определяет окно или заданный пользователем набор строк в наборе результатов запроса. Затем оконная функция вычисляет значение для каждой строки в окне.

чтобы вы могли сделать номер строки по Entity1

SELECT  Entity1,
         ROW_NUMBER() OVER(partition by Entity1) Group      
FROM T

row_number