Последовательные преобразования в SQL

Question

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

Итак, вернемся к моей проблеме: у меня есть таблица с преобразованиямистолбец идентификатора, который используется в других таблицах. Он включает в себя последовательные преобразования, возможно, несколько таких преобразований. Все строки имеют отметку даты. Вот пример игрушки:

|---------|-------|------------|
| from_id | to_id |       date |
|---------|-------|------------|
|    1001 |  2001 | 2019-01-01 |
|    1002 |  2002 | 2019-01-01 |
|    1003 |  2003 | 2019-02-02 |
|    2001 |  3001 | 2019-03-03 |
|    2002 |  3002 | 2019-03-03 |
|    3001 |  4001 | 2019-04-04 |
|---------|-------|------------|

Из этих данных я хотел бы создать две таблицы:

1. Таблица, связывающая каждый from_id с последним to_id. Для моего игрушечного примера я хочу следующее:

|---------|-------------|
| from_id | final_to_id |
|---------|-------------|
|    1001 |        4001 |
|    1002 |        3002 |
|    1003 |        2003 |
|    2001 |        4001 |
|    2002 |        3002 |
|    3001 |        4001 |
|---------|-------------|

Мне также нужна таблица со всеми связанными идентификаторами в обоих направлениях. Для моего игрушечного примера:

|------|------|
| id_1 | id_2 |
|------|------|
| 1001 | 2001 |
| 1001 | 3001 |
| 1001 | 4001 |
| 1002 | 2002 |
| 1002 | 3002 |
| 1003 | 2003 |
| 2001 | 1001 |
| 2001 | 3001 |
| 2001 | 4001 |
| 2002 | 1002 |
| 2002 | 3002 |
| 2003 | 1003 |
| 3001 | 1001 |
| 3001 | 2001 |
| 3001 | 4001 |
| 3002 | 1002 |
| 3002 | 2002 |
| 4001 | 1001 |
| 4001 | 2001 |
| 4001 | 3001 |
|------|------|

Эти два результата, конечно, могут быть объединены в одну таблицу, где соответствующие строки для результата 1 просто выделены флагом.

Итак, как мне сделать это в SQL? Любая помощь высоко ценится. Обратите внимание, что я не знаю, сколько шагов содержит самая длинная цепочка преобразований, но я знаю, что она увеличивается со дня на день.

Answer 1

Как сказал Гордон, вам нужен рекурсивный CTE, который воплощает определенный тип рекурсии с фиксированной точкой. Я думаю, что проще всего думать об этом в два этапа:

1. Завершить переходное замыкание;затем
2. Используйте это для получения желаемого результата.

Мы будем использовать CTE для первой части. У CTE есть два предложения, разделенных «объединением всех». Первый пункт запускается один раз, чтобы заполнить их насосом;второй выполняется многократно, пока не выдаст выходных данных (или не превысит допустимое количество итераций). Каждый раз, когда выполняется второе предложение, происходят две вещи:

• Результаты добавляются к результатам CTE;и
• Результаты заменяют «рабочее» значение CTE в CTE.

Имея это в виду, вот CTE, которое вычисляет переходное замыканиезапрос. Он делает несколько важных предположений:

• В ваших цепочках идентификаторов нет циклов;
• Идентификаторы постоянно увеличиваются;и
• Даты не имеют значения.

Вот код:

with cte as (
  select from_id, to_id
  from t
  union all
  select t1.from_id, t2.to_id
  from cte t1 join t t2 on t1.to_id = t2.from_id
)
select * from cte;

Первое предложение сгенерирует вашу исходную таблицу (без столбца даты):

Round 1:
FROM_ID    TO_ID   
-------  -------  
   1001     2001  
   1002     2002  
   1003     2003  
   2001     3001  
   2002     3002  
   3001     4001  

Тогда второе предложение будет использовать этот результат в качестве рабочей таблицы и объединит ее с исходной таблицей. Это приведет к следующему раунду:

Round 2:
FROM_ID    TO_ID   
-------  ------- 
   1001     3001  
   1002     3002  
   2001     4001  

Это будет добавлено к результату, но станет рабочим столом для следующего раунда. Таким образом, наш третий раунд дает нам:

Round 3:
FROM_ID    TO_ID   
-------  ------- 
   1001     4001  

Следующий раунд не дает результатов, что означает, что ни один раунд не даст никаких новых результатов - CTE достиг фиксированной точки. Это когда CTE завершает работу и дает нам свой окончательный результат:

FROM_ID    TO_ID   
-------  -------  
   1001     2001  
   1002     2002  
   1003     2003  
   2001     3001  
   2002     3002  
   3001     4001  
   1001     3001  
   1002     3002  
   2001     4001  
   1001     4001 

Нам все еще нужно выполнить шаг 2, но здесь все относительно просто: ваш результат - это просто набор строк в CTE смаксимальный TO_ID для каждого FROM_ID. Мы добавим небольшую постобработку в CTE:

with cte as (
  select from_id, to_id
  from t
  union all
  select t1.from_id, t2.to_id
  from cte t1 join t t2 on t1.to_id = t2.from_id
)
select from_id, max(to_id) as to_id
from cte
group by from_id; 

, что даст нам:

FROM_ID    TO_ID   
-------  ------- 
   1001     4001
   1002     3002
   1003     2003
   2001     4001
   2002     3002
   3001     4001

Вот и все. Как отметил Гордон, другой вопрос также должен быть простым с использованием результатов того же CTE:

with cte as (
  select from_id, to_id
  from t
  union all
  select t1.from_id, t2.to_id
  from cte t1 join t t2 on t1.to_id = t2.from_id
)
select from_id id_1, to_id id_1
from cte
union all
select to_id id_1, from_id id_1
from cte;

Answer 2

Для этой цели вам нужен рекурсивный CTE. Я думаю, что самый простой способ - вернуться назад от самой последней даты:

with cte as (
      select t.to_id, t.from_id, t.from_id as terminal_id
      from toy t
      where not exists (select 1 from toy t2 where t2.from_id = t.to_id)
      union all
      select t.to_id, t.from_id, cte.terminal_id
      from cte join
           toy t
           on t.to_id = cte.from_id
     )
select *
from cte;

Это дает половину строк. Для другой половины вы можете сделать:

select to_id, from_id, terminal_id
from cte
union all
select from_id, to_id, terminal_id
from cte;