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.
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:
See the field expected_order
above what should be the strahler order number
of each node when the algorithm is applied.