С оговоркой: гнездящиеся деревья - PullRequest
Новая
       10

С оговоркой: гнездящиеся деревья

6 голосов
/ 06 апреля 2019

У меня есть древовидная иерархия с порядковым порядком элементов. Мне нужно добавить ссылку на другие деревья.

Вот данные: 

drop table if exists org; CREATE TABLE org(id int primary key, name text, boss int, sibling int, ref int) without rowid;
INSERT INTO org VALUES(0, 'Alice', NULL, null, null);
INSERT INTO org VALUES(1, 'Bob', 0, null, null);
INSERT INTO org VALUES(2, 'Cindy', 0, 1, null);
INSERT INTO org VALUES(3, 'Dave', 1, 4, 7);
INSERT INTO org VALUES(4, 'Emma', 1, null, null);
INSERT INTO org VALUES(5, 'Fred', 2, null, null);
INSERT INTO org VALUES(6, 'Gail', 2, 5, null);
INSERT INTO org VALUES(7, 'Helen', NULL, null, null);
INSERT INTO org VALUES(8, 'Igor', 7, null, null);
INSERT INTO org VALUES(9, 'Jerome', 7, 8, null);

Дэйв ссылается на дерево, возглавляемое Еленой.

Я добавил пункт refs: 

WITH RECURSIVE
refs(id, name, boss, sibling, ref, lref) AS (
 SELECT id, name, boss, sibling, ref, 0 FROM org
UNION ALL
 SELECT org.id, org.name, org.boss, org.sibling, org.ref, refs.lref+1
 FROM org JOIN refs ON org.id=refs.ref
),
sibs(id, name, boss, lref, lsib) AS (
 SELECT id, name, boss, lref, 0 FROM refs
 WHERE sibling IS NULL
UNION ALL
 SELECT refs.id, refs.name, refs.boss, refs.lref, sibs.lsib + 1
 FROM refs
 JOIN sibs ON refs.boss = sibs.boss
 AND refs.sibling = sibs.id
),
tree(id, name, lsib, lref, level) AS (
 select id, name, 0, 0, 0 from org where id = 0
UNION ALL
 SELECT sibs.id, sibs.name, sibs.lsib, sibs.lref, tree.level+1
 FROM sibs JOIN tree ON sibs.boss=tree.id
ORDER BY 4 DESC, 5 DESC, 3 DESC
)
SELECT group_concat(name) FROM tree;

Но результат не включает дерево Хелен:

Алиса, Синди, Гейл, Фред, Боб, Дэйв, Эмма

Как получить полный результат с деревом Елены:

Алиса, Синди, Гейл, Фред, Боб, Дэйв, Хелен, Игорь, Иероним, Эмма

РЕДАКТИРОВАТЬ:

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

Алиса, Боб, Дэйв, Хелен, Игорь, Иероним, Эмма, Синди, Фред, Gail

Ответы [ 2 ]

1 голос
/ 09 апреля 2019

Не думаю, что вы можете получить следующий ожидаемый результат:

Алиса, Синди, Гейл, Фред, Боб, Дейв, Хелен, Игорь, Джером, Эмма

Поскольку вы запрашиваете другой результат для одного и того же случая:

  • Синди и Боб: один и тот же родитель.Синди брат с Бобом, а ты хочешь Синди перед Бобом.
  • Джером и Игорь: один и тот же родитель.Джером брат с Игорем, и вы хотите, чтобы Игорь был раньше Джерома.

(Если Синди должна быть напечатана до Боба, то Джером должен быть напечатан до Игоря)

Iдумаю, что ожидаемый результат должен быть:

Алиса, Синди, Гейл, Фред, Боб, Дейв, Хелен, Джером, Игорь, Эмма

ИЛИ

Алиса, Боб, Дейв, Хелен, Игорь, Джером, Эмма, Синди, Фред, Гейл

Первый метод

Я попробовал следующий запрос (используйте refs.id вместо org.boss) : 

WITH RECURSIVE
refs(id, name, boss, sibling, ref, lref) AS (
 SELECT id, name, boss, sibling, ref, 0 FROM org

UNION ALL
 SELECT org.id, org.name, refs.id, org.sibling, org.ref, refs.lref+1
 FROM org JOIN refs ON org.id=refs.ref
),
sibs(id, name, boss, lref, lsib,ref) AS (
 SELECT id, name, boss, refs.lref, 0,ref FROM refs
  WHERE sibling IS NULL
UNION ALL
 SELECT refs.id, refs.name, refs.boss, refs.lref, sibs.lsib + 1,refs.ref
 FROM refs
 JOIN sibs ON refs.boss = sibs.boss
 AND refs.sibling = sibs.id
),
tree(id, name, lsib, lref, level) AS (
 select org.id, org.name, 0, 0, 0 from org 
  where id = 0

UNION ALL
 SELECT sibs.id, sibs.name, sibs.lsib, sibs.lref, tree.level+1
 FROM sibs JOIN tree ON sibs.boss = tree.id 
ORDER BY  4 DESC, 5 DESC
)
select group_concat(name) from tree;

Алиса, Боб, Дейв, Хелен, Игорь, Джером, Эмма, Синди, Фред, Гейл

Второй метод

Я использовал другой подход: 

WITH RECURSIVE
pc(id,name,parent,priority) AS(
  select org.id,org.name,coalesce(refs.id,org.boss,-1) as "parent",
  case
  when refs.id is not null then 3
  when sibls.id is not null then 2
  when org.boss is not null then 1
  else 0 end as  "priority"
  from org left join org as refs on org.id = refs.ref
  left join org as sibls on org.id = sibls.sibling
where org.id > 0),
  tree(id,name,parent,priority,level) AS(
    select id,name,0,0,0 from org where id = 0
    UNION ALL
    select pc.id,pc.name,pc.parent,pc.priority,tree.level + 1 from pc 
    join tree on tree.id = pc.parent
    order by 3 desc )
    select group_concat(name) from tree

Алиса, Боб, Дейв, Хелен, Игорь, Джером, Эмма, Синди, Фред,Гейл

0 голосов
/ 09 апреля 2019

это будет работать: 

SELECT LISTAGG(name, ', ') WITHIN GROUP (ORDER BY name)
      FROM org
      START WITH boss is null 
      CONNECT BY PRIOR id= boss
      ORDER SIBLINGS BY sibling;

требуемый вывод: 

Alice, Bob, Cindy, Dave, Emma, Fred, Gail, Helen, Igor, Jerome
...