SQL Challenge/Puzzle: Как создать дерево иерархии изображений ASCII с помощью SQL-запроса?

Первоначальной мотивацией для этого было отображение фактических планов выполнения Oracle, сохраненных в GV$SQL_PLAN, в визуальном и ясном виде.

  • I've attached my suggested solutions.
    • Please feel free to add yours, as long as it fulfills the requirements.
    • Укажите имя базы данных, для которой было написано ваше решение.

Требования

Ввод

  • Таблица, содержащая столбцы «id» (идентификатор узла) и «pid» (идентификатор родителя узла).

Вывод

  • The result should be a an ASCII art graph (see example below)
    • Each pair of "id" and "pid" nodes should be connected with an edge.
    • Корневой узел может иметь дополнительное одиночное ребро.
    • Не должно быть других ребер, особенно ребер, которые не соединены ни с одним узлом одной из своих сторон.

Код

  • A single SELECT statement based only on native SQL
    • No UDF (User Defined Functions).
    • Нет T-SQL, PL/SQL и т.д.

Пример данных

create table h (id int,pid int);

insert into h (id,pid) values (0  ,null);
insert into h (id,pid) values (1  ,0   );
insert into h (id,pid) values (2  ,1   );
insert into h (id,pid) values (3  ,2   );
insert into h (id,pid) values (4  ,3   );
insert into h (id,pid) values (5  ,4   );
insert into h (id,pid) values (6  ,3   );
insert into h (id,pid) values (7  ,6   );
insert into h (id,pid) values (8  ,7   );
insert into h (id,pid) values (9  ,8   );
insert into h (id,pid) values (10 ,9   );
insert into h (id,pid) values (11 ,10  );
insert into h (id,pid) values (12 ,9   );
insert into h (id,pid) values (13 ,12  );
insert into h (id,pid) values (14 ,8   );
insert into h (id,pid) values (15 ,6   );
insert into h (id,pid) values (16 ,15  );
insert into h (id,pid) values (17 ,6   );
insert into h (id,pid) values (18 ,17  );
insert into h (id,pid) values (19 ,17  );
insert into h (id,pid) values (20 ,3   );
insert into h (id,pid) values (21 ,20  );
insert into h (id,pid) values (22 ,21  );
insert into h (id,pid) values (23 ,22  );
insert into h (id,pid) values (24 ,21  );

Полученные результаты

Вертикальные братья и сестры

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

Горизонтальные братья и сестры

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

sql graph ascii-art hierarchy tree
person David דודו Markovitz    schedule 07.10.2016    source источник

Ответы (5)


arrow_upward
0
arrow_downward

Оракул

Вертикальные братья и сестры

with        last_sibling (id)
            as
            (
                select      max (id)
                from        h
                group by    pid
            )

           ,tree (id,pid,branch) as
            (
                 select     h.id
                           ,h.pid
                           ,cast ('' as varchar (4000))

                 from       h

                 where      h.pid is null

                 union all

                 select     h.id
                           ,h.pid
                           ,t.branch || case when ls.id is not null then ' ' else '|' end || '    '

                 from                   tree            t

                            left join   last_sibling    ls

                            on          ls.id   =
                                        t.id

                            join        h

                            on          h.pid =
                                        t.id

                    ) search depth first by id set order_by_id

           ,vertical_space (n)
            as
            (
                select      1
                from        dual

                union all

                select      vs.n + 1
                from        vertical_space  vs
                where       vs.n - 1 < 1
            )

select      t.branch || case vs.n when 1 then '|____' || ' ' || cast (t.id as varchar(10)) else '|' end

from                    tree            t

            cross join  vertical_space  vs

order by    t.order_by_id
           ,vs.n desc
;
person David דודו Markovitz    schedule 09.10.2016

arrow_upward
0
arrow_downward

Оракул

Горизонтальные братья и сестры

with        il_parameters (atomic_width) as
            (
                 select     5   
            
                 from       dual
            )
            
select      decode
            (
                 n.n      
               
                ,1
                
                ,listagg 
                 (
                      lpad (' ',x_lpad * il_parameters.atomic_width) 
                   || rpad (lpad (decode (h.n_within_parent,1,decode (h.n_desc_within_parent,1,'|','-'),'-'),h.width/2 * il_parameters.atomic_width + 1,decode (h.n_within_parent,1,' ','-')),h.width * il_parameters.atomic_width,decode (h.n_desc_within_parent,1,' ','-'))
                 ) within group (order by h.id)                               
                                                       
                ,2
                
                ,listagg 
                 (
                      lpad (' ',x_lpad * il_parameters.atomic_width) 
                   || rpad (lpad (' ',h.width/2 * il_parameters.atomic_width,' ') || '|' ,h.width * il_parameters.atomic_width)
                 ) within group (order by h.id)                        
                
                ,3
                
                ,listagg 
                 (
                      lpad (' ',x_lpad * il_parameters.atomic_width) 
                   || rpad (lpad (' ',h.width/2 * il_parameters.atomic_width,' ') || '|' ,h.width * il_parameters.atomic_width)
                 ) within group (order by h.id)    
                                         
                ,4
                
                ,listagg 
                 (
                      lpad (' ',x_lpad * il_parameters.atomic_width) 
                   || rpad (lpad (' ',h.width/2 * il_parameters.atomic_width,' ') || h.id,h.width * il_parameters.atomic_width)
                 ) within group (order by h.id)     
                 
                ,5
                
                ,listagg 
                 (
                      lpad (' ',x_lpad * il_parameters.atomic_width) 
                   || rpad (lpad (' ',h.width/2 * il_parameters.atomic_width,' ') || decode (h.isleaf,0,'|',' ') ,h.width * il_parameters.atomic_width)
                 ) within group (order by h.id)   
                       
                ,6
                
                ,listagg 
                 (
                      lpad (' ',x_lpad * il_parameters.atomic_width) 
                   || rpad (lpad (' ',h.width/2 * il_parameters.atomic_width,' ') || decode (h.isleaf,0,'|',' ') ,h.width * il_parameters.atomic_width)
                 ) within group (order by h.id)                                                                     
            )                                                           graph
            
            

from                       (select          h.id                                                                                 id
                                           ,h.width                                                                              width
                                           ,h.y                                                                                  y
                                           ,h.isleaf                                                                             isleaf
                                           ,h.n_within_parent                                                                    n_within_parent
                                           ,h.n_desc_within_parent                                                               n_desc_within_parent                                                                       
                                           
                                           ,     sum (regexp_substr (heirarchy_x_within_parent,'\d+',1,n.n))
                                               - lag (sum (regexp_substr (heirarchy_x_within_parent,'\d+',1,n.n)),1,0) over
                                                 (
                                                      partition by   h.y
                                                                    
                                                      order by       h.id
                                                 ) 
                                               - lag (h.width,1,0) over
                                                 (
                                                      partition by   h.y
                                                                    
                                                      order by       h.id
                                                 )                                                                               x_lpad
                                               
                                            
                                            
                            from                           (select      h.id
                                                                       ,h.width
                                                                       ,h.n_within_parent
                                                                       ,h.n_desc_within_parent
                                                                       ,level                                        y
                                                                       ,sys_connect_by_path (x_within_parent,',')    heirarchy_x_within_parent
                                                                       ,connect_by_isleaf                            isleaf                          
                                                                             
                                                            from       (select      h.id                                              id
                                                                                   ,h.pid                                             pid
                                                                                   ,count (*)                                         width
                                                                                                            
                                                                                   ,nvl
                                                                                    (
                                                                                         sum (count (*)) over
                                                                                         (
                                                                                              partition by   h.pid
                                                                                                            
                                                                                              order by       h.id
                                                                                              
                                                                                              rows between   unbounded preceding
                                                                                                   and       1 preceding 
                                                                                         )
                                                                                        ,0
                                                                                    )                                                 x_within_parent
                                                                                    
                                                                                   ,row_number () over
                                                                                    (
                                                                                         partition by   h.pid
                                                                                                       
                                                                                         order by       h.id
                                                                                    )                                                 n_within_parent
                                                                                    
                                                                                   ,row_number () over
                                                                                    (
                                                                                         partition by   h.pid
                                                                                                       
                                                                                         order by       h.id desc
                                                                                    )                                                 n_desc_within_parent
                                                          
                                                                        from       (select      connect_by_root h.id          id  
                                                                                               ,connect_by_root h.pid         pid                                                       
                                                                                                
                                                                                    from        h
                                                                                                
                                                                                    where       connect_by_isleaf = 1
                                                                                                
                                                                                    connect by  h.pid = prior h.id
                                                                                    ) h
                                                          
                                                                        group by    h.id 
                                                                                   ,h.pid
                                                                        ) h
                                                                                            
                                                            connect by  h.pid = prior h.id
                                                                                 
                                                            start with  h.pid is null 
                                                            ) h
                                                            
                                            join           (select      rownum n 
                                                            from        dual 
                                                            connect by  level <= 100
                                                           ) n
                                                           
                                            on              n.n <=
                                                            regexp_count (h.heirarchy_x_within_parent,',') 
                                                           
                            group by        h.id  
                                           ,h.width       
                                           ,h.y 
                                           ,h.isleaf
                                           ,h.n_within_parent                                                                    
                                           ,h.n_desc_within_parent                                                                          
                            ) h     
            
            cross join      il_parameters
                                
            cross join     (select      rownum n 
                            from        dual 
                            connect by  level <= 6
                           )  n
            
group by    h.y  
           ,n.n

order by    h.y 
           ,n.n                                                                                                                                       
;
person David דודו Markovitz    schedule 08.10.2016

arrow_upward
0
arrow_downward

SQLite

Вертикальные братья и сестры

with        last_sibling (id)
            as
            (
                select      max (id)
                from        h
                group by    pid
            )

           ,tree (id,branch,path)
            as
            (
                select      1       as id
                           ,''      as branch
                           ,'001'   as path

                union all

                select      h.id
                           ,t.branch || case when ls.id is not null then ' ' else '|' end || '    '
                           ,t.path || '_' || substr ('00000' || h.id,-5)

                from                    tree            t

                            left join   last_sibling    ls

                            on          ls.id   =
                                        t.id

                            join        h

                            on          h.pid =
                                        t.id
            )

           ,vertical_space (n)
            as
            (
                select      1

                union all

                select      vs.n + 1
                from        vertical_space  vs
                where       vs.n < 2
            )

select      t.branch || case vs.n when 1 then '|____' || ' ' || cast (t.id as text) else '|' end

from                    tree            t

            cross join  vertical_space  vs

order by    t.path
           ,vs.n desc
;
person David דודו Markovitz    schedule 07.10.2016

arrow_upward
0
arrow_downward

SQL-сервер

Вертикальные братья и сестры

with        last_sibling (id)
            as
            (
                select      max (id)
                from        h
                group by    pid
            )

           ,tree (id,branch,path)
            as
            (
                select      h.id
                           ,cast ('' as varchar(max))
                           ,cast (right (replicate ('0',10) + cast (h.id as varchar(10)),10) as varchar(max))

                from        h

                where       h.pid is null

                union all

                select      h.id
                           ,t.branch + case when (select 1 xxxfrom last_sibling ls where ls.id = t.id) = 1 then ' ' else '|' end + '    '
                           ,t.path + '_' + right (replicate ('0',10) + cast (h.id as varchar(10)),10)

                from                    tree            t

                            join        h

                            on          h.pid =
                                        t.id
            )

           ,vertical_space (n)
            as
            (
                select      1

                union all

                select      vs.n + 1
                from        vertical_space  vs
                where       vs.n < 2
            )

select      t.branch + case vs.n when 1 then '|____' + ' ' + cast (t.id as varchar(10)) else '|' end

from                    tree            t

            cross join  vertical_space  vs

order by    t.path
           ,vs.n desc

option      (maxrecursion 0)
;
person David דודו Markovitz    schedule 09.10.2016
comment
По какой-то причине редактору кода stackoverflow не нравится слово «от» в подзапросе. Пожалуйста, замените «xxxfrom» на «от» - person David דודו Markovitz; 09.10.2016

arrow_upward
0
arrow_downward

Терадата

Вертикальные братья и сестры

with        recursive tree (id,branch,path)
            as
            (
                select      1                               as id
                           ,cast (''    as varchar (1000))  as branch
                           ,cast ('001' as varchar (1000))  as path
                           
                from        (select 'x') x(x)

                union all

                select      h.id
                           ,t.branch || case when ls.id is not null then ' ' else '|' end || '    '
                           ,t.path || '_' || substr ('00000' || h.id,-5)

                from                    tree            t

                            left join   last_sibling    ls

                            on          ls.id   =
                                        t.id

                            join        h

                            on          h.pid =
                                        t.id
            )

           ,last_sibling (id)
            as
            (
                select      max (id)
                from        h
                group by    pid
            )

           ,recursive vertical_space (n)
            as
            (
                select      1
                
                from        (select 'x') x(x)

                union all

                select      vs.n + 1
                from        vertical_space  vs
                where       vs.n < 2
            )

select      t.branch || case vs.n when 1 then '|____' || ' ' || cast (t.id as varchar(10)) else '|' end

from                    tree            t

            cross join  vertical_space  vs

order by    t.path
           ,vs.n desc
;
person David דודו Markovitz    schedule 24.10.2016