Рекурсия + "хитрое" дерево / IBM DB2, WebSphere, IMS, U2

ReSQL.ru

Мобильная версия Контакт Правила FAQ Помощь

Гость

Войти | Регистрация | Профиль | Очистить

Новые сообщения | Избранное

Форумы | Пользователи | Статистика | Мод. лог | Поиск

Цитировать

Написать

Автор*:

Ввести пароль для входа

Тема*:

Сообщение

Данное сообщение тематическое

Сообщение содержит картинки или видео 18+

Автор:

ВНИМАНИЕ! На данном подфоруме действуют строгие правила. Удостоверьтесь, что ваше сообщение соответствует им!

Форум или тема закрыты для гостей. Необходима авторизация!

Загрузить последнюю сохраненную версию

Вложение:

Вставить как галерею

Максимальный размер вложений: 4,0 МБ, аудио/видео: 8,0 МБ. Картинки большего размера ужимаются, если возможно.

Введите код, изображенный на картинке. Если код нечитаемый, кликните картинку, чтобы загрузить другой вариант.

Отправляя сообщение, я выражаю свое согласие с правилами форума и принимаю пользовательское соглашение.

Доб. в избранное | Игнор. тему | Прикреп. тему | Пометить прочит. / непрочит. | Фильтр

Форумы / IBM DB2, WebSphere, IMS, U2 [игнор отключен] [закрыт для гостей] / Рекурсия + "хитрое" дерево

12 сообщений из 12, страница 1 из 1

Рекурсия + "хитрое" дерево

#37421811

DB2 Рекурсия

Гость

Все привет

Есть "хитрое" дерево, есть запрос (см ниже), хотелось бы выбрать всех потомков с уровнями, DB2 9.7 FP4

все как-бы хорошо (в большенстве случаев),
но есть возможность (идеи?) убрать дупликаты в рекурсии (они там кстати с чего появились - непонятно)?

Спасибо

---

Код: plaintext

1.
2.
3.
4.
5.
6.
7.
8.
9.

    12-13            
   /  \          /19 
  /   14-15-16-17-18
 /   /           \20
11-10-9-7-2         
    |\ 
    | 8-6-4-3
    |  
    5-1

Код: plaintext

1.
2.
3.
4.
5.
6.
7.
8.
9.

with x (new_id,old_id) as (
 values ( 11 , 10 ),( 10 , 9 ),( 10 , 8 ),( 9 , 7 ),( 8 , 6 ),( 8 , 5 ),( 7 , 2 ),( 4 , 3 ),( 6 , 4 ),( 5 , 1 ),( 11 , 12 ),( 12 , 13 ),( 12 , 14 ),
        ( 10 , 14 ),( 14 , 15 ),( 15 , 16 ),( 16 , 17 ),( 17 , 18 ),( 17 , 19 ),( 17 , 20 )
), y (new_id,old_id,level) as (
  select new_id,old_id, 0  from x where new_id =  11 
  union all
  select y.old_id,x.old_id,y.level+ 1 
    from x,y where x.new_id = y.old_id and y.level <  100 
) select * from y

Код: plaintext

1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
19.
20.
21.
22.
23.
24.
25.
26.
27.
28.
29.
30.

NEW_ID      OLD_ID      LEVEL
----------- ----------- -----------
         11          10           0
         11          12           0
         10           9           1
         10           8           1
         10          14           1
         12          13           1
         12          14           1
          9           7           2
          8           6           2
          8           5           2
          14          15           2 
          14          15           2 
          7           2           3
          6           4           3
         15          16           3
         15          16           3
          4           3           4
          4           1           4
         16          17           4
         16          17           4
         17          18           5
          17          19           5 
         17          20           5
         17          18           5
          17          19           5 
         17          20           5

  26 record(s) selected.

...

Рейтинг:

0 / 0

01.09.2011, 18:40

| Ответить | Цитировать | Написать

Рекурсия + "хитрое" дерево

#37421853

Mark Barinstein

Гость

DB2 Рекурсия,

Здравствуйте.

Это потому, что В 14 из 11 вы приходите 2-мя путями:

11->12->14->15...
11->10->14->15...

Здесь 14->15 в обоих случаях одного уровня (2), поэтому убрать не сложно (select distinct в последнем).
Но что вам надо будет делать, если было бы:

11->12->14->15...
11->10->NNN->14->15...

?

тогда у вас будет
14, 15, 2
14, 15, 3
и то жк самое дубли после 15 с разными уровнями...

...

Рейтинг:

0 / 0

01.09.2011, 19:04

| Ответить | Цитировать | Написать

Рекурсия + "хитрое" дерево

#37421919

DB2 Рекурсия

Гость

Mark Barinstein,

Mark BarinsteinЭто потому, что В 14 из 11 вы приходите 2-мя путями:

11->12->14->15...
11->10->14->15...

верно!

можно как-то агрегировать данные в-процессе по уровням (какая-то гибридная рекурсия получается- но все-таки)?

Mark BarinsteinЗдесь 14->15 в обоих случаях одного уровня (2), поэтому убрать не сложно (select distinct в последнем).

этот вариант не проходит,
результат рекурсии огромен и скорость выполнения запроса низкая из-за выше. "феномена"
нужно все сделать "до"

Mark Barinsteinтогда у вас будет
14, 15, 2
14, 15, 3
и то жк самое дубли после 15 с разными уровнями...
здесь не так важно, уровни разные и проще обработать (если потребуется)

...

Рейтинг:

0 / 0

01.09.2011, 20:03

| Ответить | Цитировать | Написать

Рекурсия + "хитрое" дерево

#37421944

Mark Barinstein

Гость

DB2 Рекурсия,

пока вы не опишете нужный алгоритм, помочь вам будет невозможно.
Ещё раз.
Какой результат вам надо получить на таких данных:

Код: plaintext

1.
2.
3.
4.
5.
6.
7.
8.

with x (new_id, old_id) as (values 
  (11, 12)
, (12, 14)
, (14, 15) -- <--
, (11, 10)
, (10, 99)
, (99, 14)
)
...

?
Другими словами: что вы будете делать, если на очередной итерации вы вдруг выяснили, что new_id=14 уже добавлялась?

...

Рейтинг:

0 / 0

01.09.2011, 20:48

| Ответить | Цитировать | Написать

Рекурсия + "хитрое" дерево

#37421962

Mark Barinstein

Гость

упс, забыл ещё в мои тестовые данные данные добавить

Код: plaintext

, (15, 16)

...

Рейтинг:

0 / 0

01.09.2011, 21:02

| Ответить | Цитировать | Написать

Рекурсия + "хитрое" дерево

#37422174

DB2 Рекурсия

Гость

Mark Barinstein,

нужно чтоб результатом выполнения рекурсии не было дупликатов

в вашем примере, дерево выглядит

Код: plaintext

1.
2.
3.
4.

11->12->14->15->16 
|       ^
|       |
-> 10->99

так?

результат:

Код: plaintext

1.
2.
3.
4.
5.
6.
7.
8.
9.

         11          12           0
         11          10           0
         12          14           1
         10          99           1
         14          15           2
         99          14           2
         15          16           3
         14          15           3
         15          16           4

в идеале хотелось бы получить сразу:

Код: plaintext

1.
2.
3.
4.
5.
6.
7.

         11          12           0
         11          10           0
         12          14           1
         10          99           1
         14          15           2
         99          14           2
         15          16           3

или

Код: plaintext

1.
2.
3.
4.
5.
6.
7.

         11          12           0
         11          10           0
         12          14           1
         10          99           1
         14          15           3
         99          14           2
         15          16           4

другими словами:
в 14->15->16 можно прийти из 99 или 12, нужен один и только один любой из них

...

Рейтинг:

0 / 0

02.09.2011, 03:49

| Ответить | Цитировать | Написать

Рекурсия + "хитрое" дерево

#37422585

Mark Barinstein

Гость

DB2 Рекурсия,

Нужно написать свою небольшую UDF (скажем, на java), которая будет запоминать переданные в неё значения.
Вот, например, есть у меня функция, которая работает так:

Код: plaintext

1.
2.

select i, counter_grp_j(rtrim(char(i))) cnt
from table(values  1 ,  2 , null,  2 ,  1 ,  2 , null) t (i)

Код: plaintext

1.
2.
3.
4.
5.
6.
7.
8.

I           CNT        
----------- -----------
          1           1
          2           1
          -           1
          2           2
          1           2
          2           3
          -           2

С её использованием нужный вам результат будет получен таким запросом:

Запрос с UDF

Код: plaintext

1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
19.
20.
21.
22.
23.

with x (new_id, old_id) as (values 
  ( 11 ,  12 )
, ( 12 ,  14 )
, ( 14 ,  15 )
, ( 11 ,  10 )
, ( 10 ,  99 )
, ( 99 ,  14 )
--, (10, 14)
, ( 15 ,  16 )
)
, y (new_id, old_id, level, is_used) as (
select new_id, old_id,  0 
, counter_grp_j(rtrim(char(old_id)))
from x
where new_id= 11 
  union all
select x.new_id, x.old_id, y.level+ 1 
, counter_grp_j(rtrim(char(x.old_id)))
from x, y
where x.new_id=y.old_id 
and y.is_used= 1 
)
select *
from y

Можно было бы и без неё обойтись, но rownumber() не работает в рекурсивных запросах.
Если кому интересно, могу выложить исходник с инструкцией создания...

...

Рейтинг:

0 / 0

02.09.2011, 11:53

| Ответить | Цитировать | Написать

Рекурсия + "хитрое" дерево

#37422728

DB2 Рекурсия,

Гость

Mark BarinsteinНужно написать свою небольшую UDF (скажем, на java), которая будет запоминать переданные в неё значения.

можно такое сделать на SQL UDF?

Mark BarinsteinМожно было бы и без неё обойтись, но rownumber() не работает в рекурсивных запросах.

Оракловский диалект может в данном случае чем-то помочь?

Mark BarinsteinЕсли кому интересно, могу выложить исходник с инструкцией создания

было бы интересно, спасибо.

...

Рейтинг:

0 / 0

02.09.2011, 12:58

| Ответить | Цитировать | Написать

Рекурсия + "хитрое" дерево

#37422845

Mark Barinstein

Гость

DB2 Рекурсияможно такое сделать на SQL UDF?Нет.
Здесь надо сохранять результаты предыдущих вызовов.

DB2 РекурсияОракловский диалект может в данном случае чем-то помочь?Может быть, но я не специалист в оракловом диалекте...

Counter_grp.java

Код: plaintext

1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
19.
20.
21.
22.
23.
24.
25.
26.
27.
28.

 import  java.util.HashMap;
 import  COM.ibm.db2.app.UDF;

 public   class  Counter_grp  extends  UDF {
	
	 static   int  DEF_CAP =  100 ; 
	HashMap els =  null ; 
	
	 int  counter_grp0 (String str,  int  initialCapacity)  throws  Exception {
		 if  (getCallType() == UDF.SQLUDF_FIRST_CALL) els =  new  HashMap(initialCapacity);
		Object o = els.get(str);
		 int  i = (o== null )? 1 :(((Integer)o).intValue()+ 1 );
		els.put(str,  new  Integer(i));
		 return  i;
	}
	
	 public   void  counter_grp (String str,  int  initialCapacity,  int  __res)   throws  Exception {
		set( 3 , counter_grp0 (str, initialCapacity));
	}
	  
	 public   void  counter_grp (String str,  int  __res)   throws  Exception {
		set( 2 , counter_grp0 (str, DEF_CAP));
	}
	  
	 public   void  close() {
		els.clear();
	}

}

из-под владельца инстанса из командной строки (если windows, то db2cw) компилируем:
javac Counter_grp.java
и кладём *.class в sqllib/function

Counter_grp_j.sql

Код: plaintext

1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.

create function counter_grp_j(v varchar( 4000 ))
RETURNS int
LANGUAGE Java
EXTERNAL NAME 'Counter_grp.counter_grp'
FENCED THREADSAFE
NO SQL
NULL CALL
NOT DETERMINISTIC
NO EXTERNAL ACTION
DISALLOW PARALLEL
PARAMETER STYLE db2general
SCRATCHPAD
FINAL CALL;

Исправленный запрос для вашего примера

Код: plaintext

1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
19.
20.
21.
22.
23.

with x (new_id, old_id) as (values 
  ( 11 ,  12 )
, ( 12 ,  14 )
, ( 14 ,  15 )
, ( 11 ,  10 )
, ( 10 ,  99 )
, ( 99 ,  14 )
--, (10, 14)
, ( 15 ,  16 )
)
, y (new_id, old_id, level, is_used) as (
select distinct cast(null as int), new_id, - 1 ,  1 
from x
where new_id= 11 
  union all
select x.new_id, x.old_id, y.level+ 1 
, counter_grp_j(rtrim(char(x.old_id)))
from x, y
where x.new_id=y.old_id 
and y.is_used= 1 
)
select *
from y
where level<>- 1

а то функции в 2-х местах имеют не сообщающиеся scratchpad'ы...

...

Рейтинг:

0 / 0

02.09.2011, 13:58

| Ответить | Цитировать | Написать

Рекурсия + "хитрое" дерево

#37423200

DB2 Рекурсия

Гость

Mark Barinstein,

Спасибо, буду пробывать (и также сравню с версией: простые SQL запросы + java рекурсия )

...

Рейтинг:

0 / 0

02.09.2011, 16:19

| Ответить | Цитировать | Написать

Рекурсия + "хитрое" дерево

#37425428

golsa

Участник

Откуда: Красноярск

Сообщения: 789

Рейтинг: 0 / 0

Заключительный select в рекурсии:

Код: plaintext

select new_id, old_id, min(level) from y order by new_id, old_id

...

Рейтинг:

0 / 0

05.09.2011, 15:13

| Ответить | Цитировать | Написать

Рекурсия + "хитрое" дерево

#37425576

DB2 Рекурсия

Гость

golsaЗаключительный select в рекурсии:

Код: plaintext

select new_id, old_id, min(level) from y order by new_id, old_id

имеется ввиду после рекурсии?

когда дерево "сложное" то можно ждать 20-30 минут пока дело дойдет "до заключительного селекта", при этом результат будет каких-то пару сотен узлов...

...

Рейтинг:

0 / 0

05.09.2011, 16:06

| Ответить | Цитировать | Написать

12 сообщений из 12, страница 1 из 1

Форумы / IBM DB2, WebSphere, IMS, U2 [игнор отключен] [закрыт для гостей] / Рекурсия + "хитрое" дерево

Читали тему (0):

Читали форум (0):

Пользователи онлайн (0):

start [/forum/topic.php?fid=43&msg=37422728&tid=1602127]:	0ms
get settings:	10ms
get forum list:	14ms
check forum access:	4ms
check topic access:	4ms
track hit:	174ms
get topic data:	10ms
get forum data:	2ms
get page messages:	48ms
get tp. blocked users:	2ms
others:	288ms

total:	556ms