2

Is function on CTE planned for SQL standard or in any of the current RDBMSes? Somewhat like this?

with strahler(node, sn) function(_parent int) as
(
    select 
        s.node,
        case 
            -- If the node is a leaf (has no children), 
            -- its Strahler number is one.
            when count(st.*) = 0 then 
                1

            when count(st.*) >= 2 then
                case 
                    -- If the node has one child with Strahler number i, 
                    -- and all other children have Strahler numbers less than i, 
                    -- then the Strahler number of the node is i again.
                    when min(st.sn) < max(st.sn) then
                        max(st.sn)

                    -- If the node has two or more children with Strahler number i, 
                    -- and no children with greater number, 
                    -- then the Strahler number of the node is i + 1.
                    when min(st.sn) = max(st.sn) then
                        max(st.sn) + 1                     
                end
        end
    from streams s
    left join lateral strahler(s.node) st  on true
    where _parent = 0 or s.to_node = _parent
    group by s.node    
)
select st.*, s.expected_order 
from strahler(0) st 
join streams s on st.node = s.node 
order by st.node;

I have a hard time devising a recursive CTE solution to this stackoverflow question: How to determine Strahler number on a directed graph for a stream network

Note that the conceptualized "function on CTE" is working if a function is created separately. See: https://www.db-fiddle.com/f/8z58LCVhD62YvkeJjriW8d/3

I'm wondering if that solution can be done with pure CTE alone, without writing a function. I tried but CTE cannot do a left join on itself.

Anyway, I'll just re-post the nature of the problem here.

enter image description here

CREATE TABLE streams (
  node integer PRIMARY KEY,
  to_node integer REFERENCES streams(node),
  expected_order integer
);

INSERT INTO streams(node, to_node, expected_order) VALUES
(1, NULL, 4),
(2, 1, 4),
(3, 2, 3),
(4, 2, 3),
(5, 4, 3),
(6, 3, 2),
(7, 3, 2),
(8, 5, 2),
(9, 5, 2),
(10, 6, 1),
(11, 6, 1),
(12, 7, 1),
(13, 7, 1),
(14, 8, 1),
(15, 8, 1),
(16, 9, 1),
(17, 9, 1),
(18, 4, 1),
(19, 1, 1);

From that data, using the following algorithm (sourced from wikipedia)...

All trees in this context are directed graphs, oriented from the root towards the leaves; in other words, they are arborescences. The degree of a node in a tree is just its number of children. One may assign a Strahler number to all nodes of a tree, in bottom-up order, as follows:

  • If the node is a leaf (has no children), its Strahler number is one.
  • If the node has one child with Strahler number i, and all other children have Strahler numbers less than i, then the Strahler number of the node is i again.
  • If the node has two or more children with Strahler number i, and no children with greater number, then the Strahler number of the node is i + 1.

...this is produced:

enter image description here

See the field expected_order above what should be the strahler order number of each node when the algorithm is applied.

Michael Buen
  • 38,643
  • 9
  • 94
  • 118
  • Oracle supports something like that, but it's not part of the SQL standard as far as I know –  Apr 19 '19 at 06:22
  • @a_horse_with_no_name Cool, so there's already at least one RDBMS that implements that functionality for CTE. I'll give it a fiddle – Michael Buen Apr 19 '19 at 06:24
  • @a_horse_with_no_name found it, Oracle's examples just return a scalar though https://oracle-base.com/articles/12c/with-clause-enhancements-12cr1 Will experiment with it later – Michael Buen Apr 19 '19 at 06:37
  • @MichaelBuen . . . I would suggest that you ask a *new* question with sample data, desired results and perhaps an explanation of what a "Strahler" number is. Setting up a dbfiddle of some sort would also be useful. I think this might be possible in SQL. – Gordon Linoff Apr 19 '19 at 12:54

0 Answers0