Queries as Parsers
If we can think of queries as formal parsers then we can explore the exact characteristics of what a query with traces can and can't accomplish. We can then use this to know when traces will fail and a more complex syncing mechanism is required. Whatever we can define as a Parsing Expression Grammar (PEG) has a known linear time parser called a packrat parser
I think pull expression are equivalent to regular expressions in their expressivity. This is why they are easier to trace. Maybe pull expressions are a slightly different type than regular expressions, I haven't thought too deeply on this point?
Queries plus rules may be equivalent to a Parsing Expression Grammar.
- Terminals - Strings, blobs, dates, etc
- Nonterminals - refs/entities
If we can figure out a mapping then we can use a packrat parser to do the traces.
https://en.wikipedia.org/wiki/Mildly_context-sensitive_grammar_formalism
There are a few good candidates for adding context to queries aka datview (or maybe even for syncing queries)
- https://en.wikipedia.org/wiki/Tree-adjoining_grammar
- http://www.let.rug.nl/~vannoord/papers/diss/diss/node59.html
- are labeled productions E -A-> V
- EAV describe trees with rewrites???
- EAV form graphs
- entities that describe terminals and non-terminals