Добро пожаловать в форум, Guest  >>   Войти | Регистрация | Поиск | Правила | В избранное | Подписаться
Все форумы / Oracle Новый топик    Ответить
 Деревянная аналитика  [new]
Maxim Demenko
Member

Откуда: Munich, Germany
Сообщений: 940
Привет, может здесь уже встречалось, навскидку однако не нашел, ну в общем может коллективный разум поможет ....
Имеется примитивное дерево, по нему сделать обход - обычный connect by:
SQL> WITH t AS (
  2  SELECT 1 t_id,1 t_level,NULL t_parent_id FROM dual UNION ALL
  3  SELECT 2,2,11 FROM dual UNION ALL
  4  SELECT 3,3,8 FROM dual UNION ALL
  5  SELECT 4,4,7 FROM dual UNION ALL
  6  SELECT 5,5,6 FROM dual UNION ALL
  7  SELECT 6,4,7 FROM dual UNION ALL
  8  SELECT 7,3,8 FROM dual UNION ALL
  9  SELECT 8,2,11 FROM dual UNION ALL
 10  SELECT 9,3,10 FROM dual UNION ALL
 11  SELECT 10,2,11 FROM dual UNION ALL
 12  SELECT 11,1,NULL FROM dual
 13  )
 14  SELECT t_id,t_level,LEVEL calculated_level,t_parent_id
 15  FROM t
 16  CONNECT BY PRIOR t_id=t_parent_id
 17  START WITH t_parent_id IS NULL
 18  ORDER BY t_id;

      T_ID    T_LEVEL CALCULATED_LEVEL T_PARENT_ID
---------- ---------- ---------------- -----------
         1          1                1 <NULL>
         2          2                2          11
         3          3                3           8
         4          4                4           7
         5          5                5           6
         6          4                4           7
         7          3                3           8
         8          2                2          11
         9          3                3          10
        10          2                2          11
        11          1                1 <NULL>
Для обратной задачи - по данному обходу построить исходное дерево - решение влоб - correlated subquery:
SQL> WITH t AS (
  2  SELECT 1 t_id,1 t_level,NULL t_parent_id FROM dual UNION ALL
  3  SELECT 2,2,11 FROM dual UNION ALL
  4  SELECT 3,3,8 FROM dual UNION ALL
  5  SELECT 4,4,7 FROM dual UNION ALL
  6  SELECT 5,5,6 FROM dual UNION ALL
  7  SELECT 6,4,7 FROM dual UNION ALL
  8  SELECT 7,3,8 FROM dual UNION ALL
  9  SELECT 8,2,11 FROM dual UNION ALL
 10  SELECT 9,3,10 FROM dual UNION ALL
 11  SELECT 10,2,11 FROM dual UNION ALL
 12  SELECT 11,1,NULL FROM dual
 13  )
 14  SELECT t_id,t_level,t_parent_id,
 15  (SELECT MIN(t_id)
 16  FROM t t1
 17  WHERE t1.t_id>t.t_id
 18  AND t1.t_level=t.t_level-1) calculated_parent
 19  FROM t
 20  ORDER BY t_id;

      T_ID    T_LEVEL T_PARENT_ID CALCULATED_PARENT
---------- ---------- ----------- -----------------
         1          1 <NULL>      <NULL>
         2          2          11                11
         3          3           8                 8
         4          4           7                 7
         5          5           6                 6
         6          4           7                 7
         7          3           8                 8
         8          2          11                11
         9          3          10                10
        10          2          11                11
        11          1 <NULL>      <NULL>
Альтернативный влоб - self outer join + группировка

Теперь вопрос: можно ли переписать это чудо с помощью analytics (+/- case and nested inline views) чтобы убрать корреляцию?
Пока максимально приближенное до чего досоображался :
MIN(t_id) KEEP(dense_rank FIRST ORDER BY t_id DESC) over(PARTITION BY t_level) + 1
(даёт правильный результат конечно далеко не для всех нод, но дальше наступает ментальный ступор).
В реальных данных ID могут быть и с дырками, но их всегда можно устранить обернув запрос в dense_rank(), то есть можно считать что
t_id + 1 = lead(t_id)
не является магией данных...


Best regards

Maxim
19 апр 07, 18:04    [4044410]     Ответить | Цитировать Сообщить модератору
 Re: Деревянная аналитика  [new]
Vladimir Sitnikov
Member

Откуда: Moscow, NetCracker
Сообщений: 407
Maxim Demenko
Для обратной задачи - по данному обходу построить исходное дерево


Так какова же формулировка задачи?

Дана таблица "ID, LEVEL". Получить "ID, LEVEL, PARENT_ID" ?

В таком виде, необходимы дополнительные условия или ограничения на множество деревьев, иначе решение неоднозначно:
ID  | LEVEL
----+-------
1   |   1
2   |   1
3   |   2
Какой parent_id у узла 3?
19 апр 07, 21:40    [4045251]     Ответить | Цитировать Сообщить модератору
 Re: Деревянная аналитика  [new]
Maxim Demenko
Member

Откуда: Munich, Germany
Сообщений: 940
Vladimir Sitnikov
Maxim Demenko
Для обратной задачи - по данному обходу построить исходное дерево


Так какова же формулировка задачи?

Дана таблица "ID, LEVEL". Получить "ID, LEVEL, PARENT_ID" ?

Именно.

В таком виде, необходимы дополнительные условия или ограничения на множество деревьев, иначе решение неоднозначно:
ID  | LEVEL
----+-------
1   |   1
2   |   1
3   |   2
Какой parent_id у узла 3?

Неувязочка вышла, каюсь.
Для таких исходных данных родительский узел отсутствует (равносильно - обход дерева был не завершён) - для завершения не хватает строки (4,1) которая будет родителем. В реальных данных такая ситуация возможна также, но только для последней ветви, во всех предыдущих гарантируется что для любого листа глубины N присутствует прямой родитель (строка имеющая глубину N-1 и больший ID).
Для последней ветви если её обход незавершен, результат можно игнорировать (т.е. для всех LEVEL>1 и PARENT IS NULL).
В принципе, потестировав немного на небольших количествах данных, пока самым быстрым вариантом оказался
SELECT a.t_id, a.t_level,MIN(b.t_id) parent_id
FROM t a,t b
WHERE a.t_id<b.t_id(+) AND a.t_level=b.t_level(+)+1
GROUP BY a.t_id,a.t_level
CONNECT BY (причем уровней довольно мало, 4-5, строк около 50К) по сравнению с ним прилично притормаживает:
SELECT t_id,t_level,MIN(PRIOR t_id) AS parent_id
FROM t
CONNECT BY PRIOR t_id>t_id AND PRIOR t_level=t_level-1
START WITH t_level=1
GROUP BY t_id,t_level

Спасибо за поправку

Best regards

Maxim
19 апр 07, 22:48    [4045468]     Ответить | Цитировать Сообщить модератору
 Re: Деревянная аналитика  [new]
Vladimir Sitnikov
Member

Откуда: Moscow, NetCracker
Сообщений: 407
first_value(t_id) over (order by c_l*10000+t_id range between 10000 preceding and t_id preceding)
?
20 апр 07, 00:12    [4045724]     Ответить | Цитировать Сообщить модератору
 Re: Деревянная аналитика  [new]
Maxim Demenko
Member

Откуда: Munich, Germany
Сообщений: 940
Vladimir Sitnikov
first_value(t_id) over (order by c_l*10000+t_id range between 10000 preceding and t_id preceding)
?


Спасибо, очень красиво.
Пропустил я ваши пятничные задачи, теперь придется учить матчасть...
Навскидку получается скорость выполнения почти такая же как с outer join (0.2-0.5s медленнее), но на несколько порядков быстрее чем connect by. Завтра попробую больше времени погонять запросы на разных datasets, может чего нагоняю...


Best regards

Maxim
20 апр 07, 02:09    [4045845]     Ответить | Цитировать Сообщить модератору
 Re: Деревянная аналитика  [new]
Elic
Member

Откуда:
Сообщений: 29990
Maxim Demenko
может здесь уже встречалось, навскидку однако не нашел
STFF генерация дерева по уровням
20 апр 07, 08:34    [4046077]     Ответить | Цитировать Сообщить модератору
 Re: Деревянная аналитика  [new]
Maxim Demenko
Member

Откуда: Munich, Germany
Сообщений: 940
Elic
Maxim Demenko
может здесь уже встречалось, навскидку однако не нашел
STFF генерация дерева по уровням


Elic, спасибо за ссылку, но насколько я понимаю в приведенном примере нет принципиального отличия от первого упомянутого мной влоб решения. Last там можно практическо безболезненно заменить на мах/мин (в зависимости от направления обхода) и тогда эти queries будут тождественными ( и обе используют correlated subquery от которой я и хотел избавиться).
Мне представлялось в принципе 3 варианта решения этой задачи :
1) correlated subquery с min/max/last/first и вариации на тему
2) self outer join + group by (условия join такие же как в 1)
3) иерархический запрос с последующей группировкой
Все три (по крайней мере в приведенных мной данных) осуществляют логику в лоб для очень простого алгоритма: мой родитель следующая за мной нода имеющая level меньше моего)
и больше в голову не приходило до того как я увидел решение Владимира.

Best regards

Maxim
20 апр 07, 10:44    [4046839]     Ответить | Цитировать Сообщить модератору
 Re: Деревянная аналитика  [new]
Elic
Member

Откуда:
Сообщений: 29990
Maxim Demenko
до того как я увидел решение Владимира.
То, что его решение замечательное, спору нет.
20 апр 07, 10:50    [4046888]     Ответить | Цитировать Сообщить модератору
Все форумы / Oracle Ответить