среда, 29 марта 2017 г.

Рекурсивные запросы

Задача ставится следующим образом:

Есть дерево определяемое через ID,PID и поле значения VAL. 

Необходимо просуммировать всё вверх от листовых узлов до корней. Причем промежуточные узлы изначально могут сами иметь значения отличные от суммы дочерних.

Создадим простое дерево.

 drop table testh;

  CREATE TABLE testh(
    id  integer constraint pk_testh primary key,
    pid integer constraint fk_testh_self references testh(id),
    val real,
    lvl integer
  );

И заполним его деревом (3 уровня, 5 узлов, 1 корень).

  insert into testh
  select unnest(array[1,    4,5,  10,11])   as ID,
              unnest(array[NULL, 1,1,  4,4])  as PID,
              unnest(array[NULL, 10,1, 2,4]) as VAL,  
              unnest(array[null,null,null,null,null]::int[]) as LVL;
       
  commit;

  select ID,PID,VAL from testh



Выведем дерево через рекурсивный запрос, с расчетом уровня LVL.

  -- [1] Вывод простого дерева, Иерархия

  WITH RECURSIVE temp1(ID,PID,VAL,PATH,LEVEL) AS
     (
      SELECT T1.ID,T1.PID, T1.VAL, CAST (T1.ID AS VARCHAR (50)) as PATH, 1
        FROM testh T1
       WHERE T1.PID IS NULL
     union
      SELECT T2.ID, T2.PID, T2.VAL, CAST ( temp1.PATH ||'->'|| T2.ID AS VARCHAR(50)) ,LEVEL + 1
        FROM testh T2 INNER JOIN temp1 on (temp1.ID = T2.PID)    
     )
  select *
    from temp1

Запрос выполняется в 4 шага:

1) Во "временную таблицу" temp1 попадает одна корневая запись, ID=1, LEVEL=1
    (Это выполнение верхнего из 2-х UNION-ов).

2) Выполнение нижнего из UNION-ов возвращает 2 строки с ID=4,5. Эти 2 узла достаются из таблицы testh и помещаются во временную таблицу temp1. На данный момент она содержит 3 записи, для этих вновь добавленных 2-х записей так же выполнилось LEVEL+1 и их проставился 2-й уровень.

3) Далее запускается цикл по вновь добавленным записям с ID=4,5 . Первый шаг, в нижнем UNION достаем детей 4-го, это 2 записи (10,11), им выставился LEVEL=2+1=3.

4) Второй шаг, в нижнем UNION достаем детей 5-го, их нет, поэтому выходим из рекурсии.

В итоге таблица temp1 содержит 5 записей


Для того чтобы далее применить рекурсивный запрос для суммирования заполним поле LVL в таблице testh.

 -- Заполнение поля LVL
 UPDATE testh
    SET lvl = res.level
FROM
    (
    -- -----------------------------------------------------------------------
      WITH RECURSIVE temp1(ID,PID,VAL,PATH,LEVEL) AS
        (
          SELECT T1.ID,T1.PID, T1.VAL, CAST (T1.ID AS VARCHAR (50)) as PATH, 1
            FROM testh T1
           WHERE T1.PID IS NULL
        union
          SELECT T2.ID, T2.PID, T2.VAL, CAST ( temp1.PATH ||'->'|| T2.ID AS VARCHAR(50)) ,LEVEL + 1
            FROM testh T2 INNER JOIN temp1 on (temp1.ID = T2.PID)    
         )
        select *
          from temp1
    -- -----------------------------------------------------------------------
   ) AS res
WHERE
  testh.id = res.id

  commit;

  select * from testh

Сам запрос для суммирования данных с листьев до корней имеет вид.

-- Суммировнаие узлов со своими детьми вверх к корням.
with recursive summ_values(id, pid, lvl, iteration_lvl, val)
as (
    select id, pid, lvl, max(lvl) over() - 1 as iteration_lvl, val
      from testh t1
 union all  /*  =============================== */
    select id, pid, lvl, iteration_lvl - 1 as iteration_lvl,
           case
             when iteration_lvl != lvl
             then val
             else sum(val) over(partition by case when iteration_lvl = lvl then id else pid end)
           end as val
      from summ_values t2
     where t2.iteration_lvl > 0
   )
   select *
     from summ_values
    where iteration_lvl = 0

Запрос выполняется в 3 шага (связано с количеством уровней):

1) На первом во временную таблицу summ_values попадает результат верхнего union.

 select id, pid, lvl, max(lvl) over() - 1 as iteration_lvl, val
      from testh t1


2) На втором шаге к данным во временной таблице summ_values (шаг 1.) добавляется результат второго UNION.

  select id, pid, lvl, iteration_lvl - 1 as iteration_lvl,
           case
             when iteration_lvl != lvl
             then val
             else sum(val) over(partition by case when iteration_lvl = lvl then id else pid end)
           end as val
      from summ_values t2
     where t2.iteration_lvl > 0

Для наглядности и понимания заменим summ_values на подзапрос с шага 1.

    select id, pid, lvl, iteration_lvl - 1 as iteration_lvl,
           case
             when iteration_lvl != lvl
             then val
             else sum(val) over(partition by case when iteration_lvl = lvl then id else pid end)
           end as val
      from (
            ---- query from step 1 ----
            select id, pid, lvl, max(lvl) over() - 1 as iteration_lvl, val
              from testh t1
            ---------------------------
           ) t2
     where t2.iteration_lvl > 0

получаем


Этот результат во-первых добавляется к уже имеющемуся в summ_values, во-вторых идёт в следуюущую рекурсию.

Опять для наглядности поменяем заменим summ_values на подзапрос из п.2.

 -- step 3 -------
 select id, pid, lvl, iteration_lvl - 1 as iteration_lvl,
           case
             when iteration_lvl != lvl
             then val
             else sum(val) over(partition by case when iteration_lvl = lvl then id else pid end)
           end as val
      from (
           -- query from step 2 --------------------------
           select id, pid, lvl, iteration_lvl - 1 as iteration_lvl,
                case
                  when iteration_lvl != lvl
                  then val
                  else sum(val) over(partition by case when iteration_lvl = lvl then id else pid end)
                end as val
            from (
                  ---- query from step 1 ----
                  select id, pid, lvl, max(lvl) over() - 1 as iteration_lvl, val
                    from testh t1
                  ---------------------------
                 ) t2
           where t2.iteration_lvl > 0
           -----------------------------------------------
           ) t2
     where t2.iteration_lvl > 0


Дальше рекурсия не идёт, т.к. в нижнем UNION стоит условие  where t2.iteration_lvl > 0 

==================================================================

Итоговый запрос дереве с 3-мя корнями и результат суммирования:

drop table testh;
 
  CREATE TABLE testh(
    id  integer constraint pk_testh primary key,
    pid integer constraint fk_testh_self references testh(id),
    val real,
    lvl integer

  );

  insert into testh
  select unnest(array[1,2,3,          4,5,  6,7, 8,9, 10,11, 12,13, 14,15])   as ID,  
         unnest(array[NULL,NULL,null, 1,1,  2,2, 3,3, 4,4,   6,6,    8,8])  as PID,
         unnest(array[NULL,NULL,null, 10,1, 5,6, 2,4, 2,4,   6,1,    2,3]) as VAL,    
         unnest(array[null,null,null,null,null,null,null,null,null,null,null,null,null,null,null]::int[]) as LVL;

  select ID,PID,VAL from testh
 
  -- [1] Вывод простого дерева, Иерархия
  WITH RECURSIVE temp1(ID,PID,VAL,PATH,LEVEL) AS
     (
     --1
     SELECT T1.ID,T1.PID, T1.VAL, CAST (T1.ID AS VARCHAR (50)) as PATH, 1
        FROM testh T1
       WHERE T1.PID IS NULL
     union
     -- 2,3
     SELECT T2.ID, T2.PID, T2.VAL, CAST ( temp1.PATH ||'->'|| T2.ID AS VARCHAR(50)) ,temp1.LEVEL + 1
        FROM testh T2 INNER JOIN temp1 on (temp1.ID = T2.PID)    
     )
  select *
    from temp1
  order by path

+ -- Заполнение поля LVL
 UPDATE testh ..... (см. запрос выше)



-- Суммировнаие узлов со своими детьми вверх к корням.
with recursive summ_values(id, pid, lvl, iteration_lvl, val)
as (
    select id, pid, lvl, max(lvl) over() - 1 as iteration_lvl, val
      from testh t1
 union all  /*  =============================== */
    select id, pid, lvl, iteration_lvl - 1 as iteration_lvl,
           case
             when iteration_lvl != lvl
             then val
             else sum(val) over(partition by case when iteration_lvl = lvl then id else pid end)
           end as val
      from summ_values t2
     where t2.iteration_lvl > 0
   )
   select *
     from summ_values
    where iteration_lvl = 0


















Комментариев нет:

Отправить комментарий