Bigquery: найти семейные кланы на основе таблицы родственников

Question

У меня есть база данных семейных отношений:

with example_data as(
  SELECT 'abc' as relative_1, 'def' as relative_2
  union all
  SELECT 'abc' as relative_1, '123' as relative_2
  union all
  SELECT 'def' as relative_1, '334' as relative_2
  union all
  SELECT 'fdc' as relative_1, '123' as relative_2
  union all
  SELECT 'fgl' as relative_1, '342' as relative_2
) 

Как я могу создать базу на основе этих данных полных семейных кланов, чтобы получить такой результат:

Код, который я написал для создания желаемого результата, кажется не совсем практичным, и действительно, с таблицей из 100 000 строк ввода мой запрос достигает предела 6 часов после 5-го самостоятельного соединения , Я не волнуюсь, что это может привести к тому, что вся таблица будет соединена в одну длинную строку - я знаю, что в клане так много членов семьи.

Кроме того, было бы здорово, если бы это было можно вернуть результат в виде вложенной таблицы с list_all_relatives в качестве повторяющегося поля с минимальным количеством шагов между относительным_1 и соответствующим дальним родственником.

Мой неэффективный код, который возвращает результат на изображении:

  SELECT 'abc' as relative_1, 'def' as relative_2, 'abc' as list_0
  union all
  SELECT 'abc' as relative_1, '123' as relative_2, 'abc' as list_0
  union all
  SELECT 'def' as relative_1, '334' as relative_2, 'def' as list_0
  union all
  SELECT 'fdc' as relative_1, '123' as relative_2, 'fdc' as list_0
  union all
  SELECT 'fgl' as relative_1, '342' as relative_2, 'fgl' as list_0
)
,
step_0 as (
 SELECT relative_1, relative_2,
        ARRAY_TO_STRING(ARRAY(SELECT DISTINCT x FROM UNNEST(SPLIT(concat(relative_1,',',relative_2,',',list_0), ',')) AS x ORDER BY x), ',') AS combined_list
  from raw_data
)
,
step_1 as (
SELECT relative_1, relative_2, list_1,
       ARRAY_TO_STRING(ARRAY(SELECT DISTINCT x FROM UNNEST(SPLIT(concat(relative_1,',',relative_2,',',list_1), ',')) AS x ORDER BY x), ',') AS combined_list
from 
    step_0
  left join
    (select relative_2,combined_list as list_1 from step_0)
  using(relative_2)
)
,
step_2 as (
SELECT distinct * except (combined_list,list_1), 
       ARRAY_TO_STRING(ARRAY(SELECT DISTINCT x FROM UNNEST(SPLIT(concat(combined_list,',',list_2), ',')) AS x ORDER BY x), ',') AS combined_list,
from 
    step_1
left join
    (select relative_1,combined_list as list_2 from step_1)
  using(relative_1) 
)
,
step_3 as (
SELECT distinct * except (combined_list,list_2), 
       ARRAY_TO_STRING(ARRAY(SELECT DISTINCT x FROM UNNEST(SPLIT(concat(combined_list,',',list_3), ',')) AS x ORDER BY x), ',') AS combined_list,
from 
    step_2
left join
    (select relative_2,combined_list as list_3 from step_2)
  using(relative_2) 
)
,
step_4 as (
SELECT distinct * except (combined_list,list_3), 
       ARRAY_TO_STRING(ARRAY(SELECT DISTINCT x FROM UNNEST(SPLIT(concat(combined_list,',',list_4), ',')) AS x ORDER BY x), ',') AS combined_list,
from 
    step_3
left join
    (select relative_1,combined_list as list_4 from step_3)
  using(relative_1) 
),

step_N as (
SELECT *
from step_4 
)
,
step_prefinal as (
SELECT distinct
        relative_1,list_4, combined_list, 
        1+length(REGEXP_REPLACE(REGEXP_REPLACE(LOWER(combined_list), '[a-z]', ''),'[0-9]','')) as n_elements_in_list,
        max(1+length(REGEXP_REPLACE(REGEXP_REPLACE(LOWER(combined_list), '[a-z]', ''),'[0-9]',''))) over (partition by relative_1) as longest_list_relatives
from step_N
)
,
step_final as (
SELECT relative_1, combined_list, n_elements_in_list,
       count(*) over (partition by relative_1) as cnt_lists_per_relative,
       max(n_elements_in_list) over (partition by relative_1) as max_elements
from 
  step_prefinal 
 where true
 and longest_list_relatives = n_elements_in_list
 group by 1,2,3
)
,
stats as (
SELECT cnt_lists_per_relative, count(distinct relative_1) as cnt,   
       max(max_elements) as max_elements
from 
step_final
group by 1
order by 1
)

SELECT relative_1, combined_list as list_all_relatives 
from step_final
where true

Answer 1

Мне удалось создать код для воспроизведения вашего вывода в гораздо более простой форме.

Я использовал предоставленные example_data для его воспроизведения. Я достиг желаемого результата, используя UDF и JavaScript. Ниже приведен код:

#Custom UDF to return a list of strings from an array
CREATE TEMP FUNCTION
  rel (relatives ARRAY<String>)
  RETURNS string
  LANGUAGE js AS '''
  return relatives;
''';

#provided data
WITH example_data AS(
  SELECT 'abc' AS relative_1, 'def' AS relative_2
  UNION ALL
  SELECT 'abc' AS relative_1, '123' AS relative_2
  UNION ALL
  SELECT 'def' AS relative_1, '334' AS relative_2
  UNION ALL
  SELECT 'fdc' AS relative_1, '123' AS relative_2
  UNION ALL
  SELECT 'fgl' AS relative_1, '342' AS relative_2
),

#Manipulating the data
data AS 
(
  SELECT
    t2.key,
    ARRAY_AGG(CAST(relative_2 AS string) ) AS relatives 
  FROM example_data t1
  LEFT JOIN ( SELECT DISTINCT relative_1 AS key FROM example_data
    GROUP BY relative_1) t2
  ON key=relative_1
  GROUP BY 1
  ORDER BY key 
)

#selecting the desired fields and using the UDF
SELECT key, rel(relatives) AS list_of_relatives FROM data
ORDER BY key

Как видите, первым шагом было создание UDF , который получает вложенное поле Strings и просто возвращает их в списке строк для каждого " Ключ ". После объявления example_data на шаг 2 необходимо было выполнить некоторые манипуляции с данными. Чтобы получить следующую таблицу:

Как видите, таблица имеет lative_1 ( назван ключом ) и родственниками во вложенном столбце.

После этого выбираются нужные поля. Это означает, что key и UDF как list_of_relatives , которые были записаны на первом шаге, и результат будет таким, как показано ниже:

Наконец, обратите внимание, что list_of_relatives больше не является вложенным полем. Вместо этого это String с каждым значением, разделенным запятой. Как показано ниже: