Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Interactive: Support recursive queries #140

Open
frankmcsherry opened this issue Feb 16, 2019 · 0 comments
Open

Interactive: Support recursive queries #140

frankmcsherry opened this issue Feb 16, 2019 · 0 comments

Comments

@frankmcsherry
Copy link
Member

A query is a list of rule definitions, binding a plan to a name. Each of these plans can invoke other sources of data by name. If the sequence of rules only reference previously bound names, then we do not need any recursion, and can just implement each rule in order. That is how the code currently works.

More generally, we can have some non-standard behavior if:

  1. A rule references itself,
  2. A rule references a name bound later in the query.
  3. A rule references a bound name that is rebound later in the query.

In these cases, and perhaps others I haven't thought of, we might prefer the semantics of a query to be the fixed point of repeated application of its rules, in order. This is a strict generalization of just requiring an acyclic "depends on" relation among the rules.

It seems natural to construct the "depends on" relation and find the strongly connected components. Each of these can be independently rendered as an iterative scope, with iterate::Variable types used for collections that must develop recursively. For re-bound names, the initial value of the variable should be the initial collection, and the recursive definition then overwrites this.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
None yet
Projects
None yet
Development

No branches or pull requests

1 participant