You signed in with another tab or window. Reload to refresh your session.You signed out in another tab or window. Reload to refresh your session.You switched accounts on another tab or window. Reload to refresh your session.Dismiss alert
The RecursiveStreams API always does an implicit distinct, i.e., computing the fixedpoint $y = \mathit{distinct}(f(i+Δi, y))$ to ensure convergence in more cases. Yet, sometimes this is overkill: If you happen to know that your data is, e.g., an acyclic graph or a (per-definition cycle-free) abstract syntax tree, you should not have to pay for the implicit deduplication operation and simply compute the fixedpoint $y = f(i+Δi, y)$.
Motivation
SQL's recursive common table expressions (CTEs) expose this trade-off: Either you use UNION ALL and have no implicit deduplication step (at the expense of non-termination for cyclic data) or you use UNION and get to enjoy the reverse properties. Why not have this for DBSP's recursion API, too? The updated tutorials 10 and 11 of this PR show this for the example of a transitive closure over an acyclic and cyclic graph, respectively.
Regarding (1) and (2): By now there exist approaches to fix this with DBSP natively (see #6653 and #6577, respectively).
Hence, I think there is the opportunity to create a new API for recursive computations that fixes all three limitations in a principled way.
Reference-level explanation
The SQL-to-DBSP compiler would need adjustments to make use of DBSP's new API. TBD; I don't know the compiler well enough.
Drawbacks
This would either be a breaking change if adjusting the RecursiveStreams API or it would cause a depreciation notice and introduce a new API.
Potential new API for Recursive Streams
The current API for
RecursiveStreamshas some limitations:RecursiveStreamsAPI always does an implicitdistinct, i.e., computing the fixedpointMotivation
SQL's recursive common table expressions (CTEs) expose this trade-off: Either you use
UNION ALLand have no implicit deduplication step (at the expense of non-termination for cyclic data) or you useUNIONand get to enjoy the reverse properties. Why not have this for DBSP's recursion API, too? The updated tutorials 10 and 11 of this PR show this for the example of a transitive closure over an acyclic and cyclic graph, respectively.Regarding (1) and (2): By now there exist approaches to fix this with DBSP natively (see #6653 and #6577, respectively).
Hence, I think there is the opportunity to create a new API for recursive computations that fixes all three limitations in a principled way.
Reference-level explanation
The SQL-to-DBSP compiler would need adjustments to make use of DBSP's new API. TBD; I don't know the compiler well enough.
Drawbacks
This would either be a breaking change if adjusting the
RecursiveStreamsAPI or it would cause a depreciation notice and introduce a new API.