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

Откуда:
Сообщений: 52
Добрый день. Помогите, пожалуйста, оптимально решить задачу.

Есть данные исходного дерева
WITH 
--справочник
rf AS
(SELECT 0 ID, 'ROOT'    TYPE FROM dual UNION ALL
 SELECT 1 ID, 'Белый'   TYPE FROM dual UNION ALL
 SELECT 2 ID, 'Черный'  TYPE FROM dual UNION ALL
 SELECT 3 ID, 'Красный' TYPE FROM dual UNION ALL
 SELECT 4 ID, 'Зеленый' TYPE FROM dual UNION ALL 
 SELECT 5 ID, 'Синий'   TYPE FROM dual 
)
-- дерево: ИД ребенка, ИД родителя, уровень иерархии, ИД ветки
, tree AS
(-- ветка 1
 SELECT 4 child_id, 1 parent_id, 5 lev, 1 branch FROM dual UNION ALL
 SELECT 1 child_id, 5 parent_id, 4 lev, 1 branch FROM dual UNION ALL
 SELECT 5 child_id, 1 parent_id, 3 lev, 1 branch FROM dual UNION ALL
 SELECT 1 child_id, 0 parent_id, 2 lev, 1 branch FROM dual UNION ALL
 -- ветка 2
 SELECT 1 child_id, 2 parent_id, 6 lev, 2 branch FROM dual UNION ALL
 SELECT 2 child_id, 3 parent_id, 5 lev, 2 branch FROM dual UNION ALL
 SELECT 3 child_id, 2 parent_id, 4 lev, 2 branch FROM dual UNION ALL
 SELECT 2 child_id, 1 parent_id, 3 lev, 2 branch FROM dual UNION ALL
 SELECT 1 child_id, 0 parent_id, 2 lev, 2 branch FROM dual UNION ALL
 -- ветка 3
 SELECT 1 child_id, 1 parent_id, 6 lev, 3 branch FROM dual UNION ALL
 SELECT 1 child_id, 3 parent_id, 5 lev, 3 branch FROM dual UNION ALL
 SELECT 3 child_id, 5 parent_id, 4 lev, 3 branch FROM dual UNION ALL
 SELECT 5 child_id, 1 parent_id, 3 lev, 3 branch FROM dual UNION ALL
 SELECT 1 child_id, 0 parent_id, 2 lev, 3 branch FROM dual UNION ALL
 -- ветка 4
 SELECT 1 child_id, 4 parent_id, 5 lev, 4 branch FROM dual UNION ALL
 SELECT 4 child_id, 2 parent_id, 4 lev, 4 branch FROM dual UNION ALL
 SELECT 2 child_id, 1 parent_id, 3 lev, 4 branch FROM dual UNION ALL
 SELECT 1 child_id, 0 parent_id, 2 lev, 4 branch FROM dual UNION ALL
 -- корень
 SELECT 0 child_id, NULL parent_id, 1 lev, NULL branch FROM dual   
)
Из них нужно получить дерево, "схлопнутое" по одинаковым типам узлов и для одинаковых уровней, но так чтобы ветки не сростались образуя кольцо. Для пояснения нарисовал картинку.
На верхнем рисунке изображено исходное дерево, а на нижнем то, что нужно получить:
Картинка с другого сайта.
Предполагается использование 2-х таблиц для создания нового дерева
-- справочник узлов нового дерева  
create table new_tree_nodes
(
  ID     NUMBER, -- Сурогатный ключ (генерится сиквенсом)
  rf_id  NUMBER  -- Идентификатор справочника исходных данных
);
-- новое дерево
create table new_tree
(
  child_id     NUMBER, -- Идентификатор дочернего узла нового дерева
  parent_id    NUMBER  -- Идентификатор родителькского узла нового дерева
);
Весия Oracle 10g
30 июл 09, 13:09    [7478777]     Ответить | Цитировать Сообщить модератору
 Re: Сформировать дерево на основе другого дерева  [new]
mlf777
Member

Откуда:
Сообщений: 52
странно но картинка не отобразилась, вот прямая ссылка
http://keep4u.ru/full/2009/07/30/75330a9af0679284967631ce72b4cf85/jpg
30 июл 09, 13:13    [7478806]     Ответить | Цитировать Сообщить модератору
 Re: Сформировать дерево на основе другого дерева  [new]
ERROR MESSAGE
Member

Откуда: Москва
Сообщений: 376
Скажи-ка, друже, како твой справочник rf связан с твоим дубом tree?
А ещщё нарисуй нам нужный тебе результат в виде таблицы выборки, а то картинка сработывает, запутывалка какая-то.
Како и что у тебы выселекчивается, когда ветки твои "сростались образуя кольцо"?

Без етих дополненций заандерстендить тебя достаточно диффикультно ))
30 июл 09, 14:15    [7479197]     Ответить | Цитировать Сообщить модератору
 Re: Сформировать дерево на основе другого дерева  [new]
mlf777
Member

Откуда:
Сообщений: 52
ERROR MESSAGE,
Извините, если непонятно объяснил.

>>Скажи-ка, друже, како твой справочник rf связан с твоим дубом tree?
child_id и parent_id (tree) это ссылки на id справочника (rf), обычная связь один ко многим

>> А ещщё нарисуй нам нужный тебе результат в виде таблицы выборки, а то картинка
>> сработывает, запутывалка какая-то.
>>Како и что у тебы выселекчивается, когда ветки твои "сростались образуя кольцо"?
попробую прояснить, думал на картинке все понятно, там те узлы одного уровня, что имеют один тип(цвет) должны сростись, но так, что бы не получилось сростание веток (на картинке ветки X срослись), разрушая само понятие дерево:
         --0
     --0
--0
     --0    --X
         --0     --X
             --X
30 июл 09, 14:42    [7479471]     Ответить | Цитировать Сообщить модератору
 Re: Сформировать дерево на основе другого дерева  [new]
Elic
Member

Откуда:
Сообщений: 29988
+
WITH
rf AS
(SELECT 0 ID, 'ROOT'    TYPE FROM dual UNION ALL
 SELECT 1 ID, 'Белый'   TYPE FROM dual UNION ALL
 SELECT 2 ID, 'Черный'  TYPE FROM dual UNION ALL
 SELECT 3 ID, 'Красный' TYPE FROM dual UNION ALL
 SELECT 4 ID, 'Зеленый' TYPE FROM dual UNION ALL
 SELECT 5 ID, 'Синий'   TYPE FROM dual
),
 tree AS
(-- ветка 1
 SELECT 4 child_id, 1 parent_id, 5 lev, 1 branch FROM dual UNION ALL
 SELECT 1 child_id, 5 parent_id, 4 lev, 1 branch FROM dual UNION ALL
 SELECT 5 child_id, 1 parent_id, 3 lev, 1 branch FROM dual UNION ALL
 SELECT 1 child_id, 0 parent_id, 2 lev, 1 branch FROM dual UNION ALL
 -- ветка 2
 SELECT 1 child_id, 2 parent_id, 6 lev, 2 branch FROM dual UNION ALL
 SELECT 2 child_id, 3 parent_id, 5 lev, 2 branch FROM dual UNION ALL
 SELECT 3 child_id, 2 parent_id, 4 lev, 2 branch FROM dual UNION ALL
 SELECT 2 child_id, 1 parent_id, 3 lev, 2 branch FROM dual UNION ALL
 SELECT 1 child_id, 0 parent_id, 2 lev, 2 branch FROM dual UNION ALL
 -- ветка 3
 SELECT 1 child_id, 1 parent_id, 6 lev, 3 branch FROM dual UNION ALL
 SELECT 1 child_id, 3 parent_id, 5 lev, 3 branch FROM dual UNION ALL
 SELECT 3 child_id, 5 parent_id, 4 lev, 3 branch FROM dual UNION ALL
 SELECT 5 child_id, 1 parent_id, 3 lev, 3 branch FROM dual UNION ALL
 SELECT 1 child_id, 0 parent_id, 2 lev, 3 branch FROM dual UNION ALL
 -- ветка 4
 SELECT 1 child_id, 4 parent_id, 5 lev, 4 branch FROM dual UNION ALL
 SELECT 4 child_id, 2 parent_id, 4 lev, 4 branch FROM dual UNION ALL
 SELECT 2 child_id, 1 parent_id, 3 lev, 4 branch FROM dual UNION ALL
 SELECT 1 child_id, 0 parent_id, 2 lev, 4 branch FROM dual UNION ALL
 -- корень
 SELECT 0 child_id, NULL parent_id, 1 lev, NULL branch FROM dual
),
new_tree1 as
( select distinct child_id, parent_id, sys_connect_by_path(child_id, '\') as path
    from tree
    start with parent_id is null
    connect by parent_id = prior child_id and lev = prior lev + 1 and (lev = 2 or branch = prior branch)
),
new_tree2 as
( select row_number() over (order by path) as id, child_id, parent_id, path
    from new_tree1
),
new_tree as
( select t1.id, t2.id as parent_id, t1.child_id as rf_id
    from new_tree2 t1, new_tree2 t2
    where t2.path(+) = rtrim(rtrim(t1.path, t1.child_id), '\')
)
select rpad(' ', (level-1)*2) || rf.type as tree
  from new_tree t, rf
  where rf.id = t.rf_id
  start with t.parent_id is null
  connect by t.parent_id = prior t.id
  order siblings by rf.type
;

TREE
--------------------
ROOT
  Белый
    Синий
      Белый
        Зеленый
      Красный
        Белый
          Белый
    Черный
      Зеленый
        Белый
      Красный
        Черный
          Белый

14 rows selected.
30 июл 09, 15:46    [7479947]     Ответить | Цитировать Сообщить модератору
 Re: Сформировать дерево на основе другого дерева  [new]
mlf777
Member

Откуда:
Сообщений: 52
Elic, огромное спасибо, мне казалось будет более громоздкое решение, но оказалось все элегантно решается.
30 июл 09, 16:00    [7480076]     Ответить | Цитировать Сообщить модератору
 Re: Сформировать дерево на основе другого дерева  [new]
Elic
Member

Откуда:
Сообщений: 29988
mlf777
но оказалось все элегантно решается.
Каковы максимальные глубина дерева и значение id-шника? :)
30 июл 09, 18:16    [7481183]     Ответить | Цитировать Сообщить модератору
 Re: Сформировать дерево на основе другого дерева  [new]
mlf777
Member

Откуда:
Сообщений: 52
id NUMBER(28)
а вот глубина, сейчас до 15 уровня доросла, но может и дальше рости
30 июл 09, 18:30    [7481250]     Ответить | Цитировать Сообщить модератору
 Re: Сформировать дерево на основе другого дерева  [new]
Elic
Member

Откуда:
Сообщений: 29988
mlf777
id NUMBER(28)
а вот глубина, сейчас до 15 уровня доросла, но может и дальше рости
Пока хороший запас есть :)
30 июл 09, 18:44    [7481312]     Ответить | Цитировать Сообщить модератору
 Re: Сформировать дерево на основе другого дерева  [new]
mlf777
Member

Откуда:
Сообщений: 52
Имелось ввиду это 15 * 28 = 420 (максимальный путь), при ограничении 4000?
30 июл 09, 19:03    [7481393]     Ответить | Цитировать Сообщить модератору
 Re: Сформировать дерево на основе другого дерева  [new]
Elic
Member

Откуда:
Сообщений: 29988
mlf777
Имелось ввиду
Да. Только *(28+1) :)
30 июл 09, 19:07    [7481413]     Ответить | Цитировать Сообщить модератору
Все форумы / Oracle Ответить