Работа с рекурсией (оракул)

Question

У меня возникли проблемы при попытке сделать какую-то бизнес-логику для клиента (веб-трейдинг):

У моего клиента есть таблица (упрощенная), подобная этой:

|| ID ||  OFFERED_PRODUCT_ID  || DEMANDED_PRODUCT_ID ||
|| 01 ||  34                  || 45                  ||
|| 01 ||  34                  || 16                  ||
|| 01 ||  45                  || 57                  ||
|| 01 ||  47                  || 57                  ||
|| 01 ||  57                  || 63                  ||
|| 01 ||  16                  || 20                  ||

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

Это торговые сети:

<34, 45, 57, 63> <34, 16, 20> <45, 57, 63> <47, 57, 63> <57, 63> <16, 20>

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

Я сделал это:

  select  o.OFFERED_PRODUCT_ID, o.DEMANDED_PRODUCT_ID
  from TRADES o
  start with 
  o.DEMANDED_PRODUCT_ID = (SELECT MIN(o.DEMANDED_PRODUCT_ID) from TRADES)
  connect by NOCYCLE prior o.DEMANDED_PRODUCT_ID = o.OFFERED_PRODUCT_ID;

Я пытаюсь начать рекурсию с самого старого продукта в системе (с минимальными идентификаторами). Но это не работает. Это дало мне все торговые сети. Мне нужен только самый большой.

Вот пример вывода:

OFFERED_PRODUCT_ID      DEMANDED_PRODUCT_ID

9920896475501851        59587794888502550724
59587794888502550724    13197303523502765990
13197303523502765990    54010274740204405159
54010274740204405159    14505831337880766413
14505831337880766413    89607128670993987443
89607128670993987443    8802863939059413452
8802863939059413452  7779127922701247342
7779127922701247342  3810800421539873909
3810800421539873909  12423373218147473557

Answer 1

Я полагаю, вы хотите что-то вроде

SQL> ed
Wrote file afiedt.buf

  1  with trades as (
  2    select 34 offered_product_id, 45 demanded_product_id from dual
  3    union all
  4    select 34, 16 from dual
  5    union all
  6    select 45, 57 from dual
  7    union all
  8    select 47, 57 from dual
  9    union all
 10    select 57, 63 from dual
 11    union all
 12    select 16, 20 from dual
 13  )
 14  select path
 15    from (
 16    select offered_product_id,
 17           demanded_product_id,
 18           level + 1,
 19           sys_connect_by_path( offered_product_id, '/' ) ||
 20              '/' || demanded_product_id path,
 21           dense_rank() over (order by level desc) rnk
 22      from trades
 23   connect by prior demanded_product_id = offered_product_id )
 24*  where rnk = 1
SQL> /

PATH
--------------------
/34/45/57/63

Answer 2

Длина торговой цепочки равна глубине рекурсии.В Oracle есть переменная psuedo, LEVEL, которую вы можете использовать.Если вы берете свой исходный запрос и сортируете по LEVEL, то в конце будет стоять конец самой длинной цепочки.Тогда нам нужно исключить оставшуюся часть запроса.

select *
  from
  ( select  o.OFFERED_PRODUCT_ID, o.DEMANDED_PRODUCT_ID
      from TRADES o
      start with    o.DEMANDED_PRODUCT_ID = 
                (SELECT MIN(o.DEMANDED_PRODUCT_ID) from TRADES)
      connect by NOCYCLE prior o.DEMANDED_PRODUCT_ID = o.OFFERED_PRODUCT_ID
      order by level desc
   )
  where rownum = 1;

<p> The above will return the last row in the chain. To get the entire chain in a comma seperated list: <p><pre> select lvl, opath ||','|| DEMANDED_PRODUCT_ID chain from ( select level lvl, o.OFFERED_PRODUCT_ID, o.DEMANDED_PRODUCT_ID, SYS_CONNECT_BY_PATH(o.OFFERED_PRODUCT_ID, ',') opath from TRADES o start with o.DEMANDED_PRODUCT_ID = (SELECT MIN(o.DEMANDED_PRODUCT_ID) from TRADES)connect by NOCYCLE prior o.DEMANDED_PRODUCT_ID = o.OFFERED_PRODUCT_ID order by level desc ) where rownum = 1 </pre>

Вы можете удалить начальную запятую.

Если вы хотите самую длинную цепочку, одну строку за раз:

select c.OFFERED_PRODUCT_ID, c.DEMANDED_PRODUCT_ID
  from TRADES c
  start with  (c.OFFERED_PRODUCT_ID,  c.DEMANDED_PRODUCT_ID) in
            (
             select o1,  d1
              from (
                       select level lvl,  o.OFFERED_PRODUCT_ID, o.DEMANDED_PRODUCT_ID
                          , CONNECT_BY_ROOT OFFERED_PRODUCT_ID   o1
                          , CONNECT_BY_ROOT DEMANDED_PRODUCT_ID   d1
                         from TRADES o
                         start with    o.OFFERED_PRODUCT_ID not in (select st.DEMANDED_PRODUCT_ID from trades st)
                         connect by NOCYCLE prior o.DEMANDED_PRODUCT_ID = o.OFFERED_PRODUCT_ID
                        order by level desc
                    )
                  where rownum = 1
            )
   connect by NOCYCLE prior c.DEMANDED_PRODUCT_ID = c.OFFERED_PRODUCT_ID

Команда CONNECT_BY_ROOT получает данные из корня рекурсии, то есть из первой строки цепочки.Я работаю на 10g Rel 2. Я не уверен, доступен ли он на старых версиях.

Answer 3

Предложение start with, которое у вас есть, почти ничего не делает, потому что "o". коррелирует это с основным запросом. Это эквивалентно start with o.OFFERED_PRODUCT_ID is not null. Я думаю, что вы хотите:

select level, o.OFFERED_PRODUCT_ID, o.DEMANDED_PRODUCT_ID, SYS_CONNECT_BY_PATH(o.OFFERED_PRODUCT_ID, ','), SYS_CONNECT_BY_PATH(o.DEMANDED_PRODUCT_ID, ',') , CONNECT_BY_ROOT OFFERED_PRODUCT_ID o1 , CONNECT_BY_ROOT DEMANDED_PRODUCT_ID d1 from TRADES o start with o.OFFERED_PRODUCT_ID not in (select st.DEMANDED_PRODUCT_ID from trades st) connect by NOCYCLE prior o.DEMANDED_PRODUCT_ID = o.OFFERED_PRODUCT_ID

Вышеприведенное даст вам все цепочки, но не будет начинать цепочку "в середине". Если вам нужна только самая длинная цепь, вам явно не нужны более короткие цепи, которые начинаются «посередине».