Гость
Войти | Профиль | Очистить
Целевая тема:
Создать новую тему:
Автор:
Действия ...
Форумы / IBM DB2, WebSphere, IMS, U2 [игнор отключен] [закрыт для гостей] / Рекурсия + "хитрое" дерево / 12 сообщений из 12, страница 1 из 1
01.09.2011, 18:40
    #37421811
DB2 Рекурсия
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, 19:04
    #37421853
Mark Barinstein
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, 20:03
    #37421919
DB2 Рекурсия
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:48
    #37421944
Mark Barinstein
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, 21:02
    #37421962
Mark Barinstein
Mark Barinstein
Гость
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Рекурсия + "хитрое" дерево
упс, забыл ещё в мои тестовые данные данные добавить

Код: plaintext
, (15, 16)
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
02.09.2011, 03:49
    #37422174
DB2 Рекурсия
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, 11:53
    #37422585
Mark Barinstein
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, 12:58
    #37422728
DB2 Рекурсия,
DB2 Рекурсия,
Гость
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Рекурсия + "хитрое" дерево
Mark BarinsteinНужно написать свою небольшую UDF (скажем, на java), которая будет запоминать переданные в неё значения.

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


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

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


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

было бы интересно, спасибо.
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
02.09.2011, 13:58
    #37422845
Mark Barinstein
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, 16:19
    #37423200
DB2 Рекурсия
DB2 Рекурсия
Гость
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Рекурсия + "хитрое" дерево
Mark Barinstein,

Спасибо, буду пробывать (и также сравню с версией: простые SQL запросы + java рекурсия )
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
05.09.2011, 15:13
    #37425428
golsa
golsa
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Рекурсия + "хитрое" дерево
Заключительный select в рекурсии:
Код: plaintext
select new_id, old_id, min(level) from y order by new_id, old_id
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
05.09.2011, 16:06
    #37425576
DB2 Рекурсия
DB2 Рекурсия
Гость
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Рекурсия + "хитрое" дерево
golsaЗаключительный select в рекурсии:
Код: plaintext
select new_id, old_id, min(level) from y order by new_id, old_id


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

когда дерево "сложное" то можно ждать 20-30 минут пока дело дойдет "до заключительного селекта", при этом результат будет каких-то пару сотен узлов...
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
Форумы / IBM DB2, WebSphere, IMS, U2 [игнор отключен] [закрыт для гостей] / Рекурсия + "хитрое" дерево / 12 сообщений из 12, страница 1 из 1
Найденые пользователи ...
Разблокировать пользователей ...
Читали тему (0):
Читали форум (0):
Пользователи онлайн (0):
x
x
Закрыть


Просмотр
0 / 0
Close
Debug Console [Select Text]