Operator negation in AQL - part 1: negation with existence assumption #186
Comments
3 tasks
3 tasks
bors bot
added a commit
that referenced
this issue
Sep 8, 2021
189: Implement operator negation with existence assumption r=thomaskrause a=thomaskrause This implements #186 by splitting the current `BinaryOperator` trait into two traits (one that can only be used with nested loop joins and one that can be used with index joins) and adding an automatic implementation of the negated variant for each existing binary operator. This can only use the `filter_match` function, since there is no way to automatically find optimized implementations for the negation. A (slow) nested loop join is enforced instead. Since the current implementation of the negated operators are non-binding (as defined in #186), this is not an issue since in most cases this will be an additional filter function and not be used to generate new right-hand-side matches for a given left-hand-side. TO-DOs - [x] Fix issues reported by clippy in the changed files - [x] run benchmark to ensure no existing query is affected - [x] add specific test queries for the new operator Co-authored-by: Thomas Krause <[email protected]> Co-authored-by: Thomas Krause <[email protected]>
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
There are two types of operator negation that are desirable in AQL: with and without implied existence of one of the nodes. Negation with implied existence is probably easier and will be specified in this issue. Negation without existence could be accomplished in a second step and is described in issue #187 .
The negation of operators is done by placing ! before the operator. Negated conditions do not participate in variable binding. Variables participating in the query must be bound by some other operator(s) in the query. Here is an example:
This query is stating that an NP covers a PP and an ADVP, and it dominates the PP indirectly, but it does not dominate ADVP indirectly (there is no d edge from NP to ADVP, even though it is covered discontinuously). Note that all three nodes are already bound by the query without negation. The negation simply rules out some of the search results, since they violate the negative constraint.
Another example using precedence:
Finds cases of sentences containing "ne" and later on "pas", except if they are consecutive (not
#2 . #3).The text was updated successfully, but these errors were encountered: