VIATRA/Query/UserDocumentation/DRED

< VIATRA‎ | Query

Since the 1.6 version, VIATRA Queries supports Delete and REDerive evaluation in the query engine. This evaluation strategy makes it possible to correctly compute the results of recursive graph patterns on instance models that contain cycles. Prior versions of VIATRA Queries supported only scenarios where at least one of the cycles was missing, that is, either the patterns were not recursive or the instance models were acyclic. We demonstrate the differences with a concrete example.

Once in a while, people share secrets with each other. For the sake of the example, imagine that if a person is in a "talks to" relationship with another, then that person will also share his/her secret with the other person. The other person will eventually also share the previous person's secrets with others, that is, the sharing of secrets is transitive. In our example, it is also possible that a person revokes a secret, and, by that, the secret will be/should be also forgotten by all people that heard about that secret.

Given these assumptions, let’s model some real people and their secrets. Assume that we have four people Ann (A), Bill (B), Jane (J), and Mike (M), and we have the following talks to relationships: A -> B, B -> J, J -> M, J -> B. The four people also have some secrets, four numbers, these are respectively A - 1, B - 2, J - 3, and M - 4. In this initial setup, Ann does not know any secrets, but the others know everybody's secrets (including Ann's).

We can encode the secret sharing with VIATRA Queries graph patterns as follows:

```// Directly known secrets by the given person through the talks to relationship
pattern directSecrets(person : Person, secret : EString) {
Person(other);
Person.talksTo(other, person);
Person.secret(other, secret);
}

// Directly or transitively known secrets by the given person
pattern allSecrets(person : Student, secret : EString) {
find directSecrets(person, secret);
} or {
Person(other);
Person.talksTo(other, person);
find allSecrets(other, secret);
}
```

We can observe that the allSecrets pattern is recursive, and that the input model has a cycle through the "talks to" relationship. We encourage you to actually model this scenario in VIATRA Queries, and observe what happens if you DELETE the A -> B edge, that is, the scenario when Ann does not want to share her secret anymore. We would expect that the VIATRA Queries evaluation will derive that Ann's secret will be forgotten by the others (as it should be according to our example). However, this is not the case, Ann's secret is still known by everybody else. What has just happened?

In order to better understand what is going on under the hood, we need to introduce the notion of an alternative derivation of a tuple. Lets focus on the [Bill, 1] tuple which represents that Bill knows Ann's secret. Before the deletion of the A -> B edge, this tuple had two alternative derivations. One of them directly came from Ann because she shared her secret with Bill by directly talking to him. Bill then shared this secret with Jane, Jane with Mike, and Mike with Bill again, that is, Bill got to know Ann's secret through another alternative source, specifically, through Mike. Intuitively this means that two people shared Ann's secret with Bill, even though Mike got to know that secret through Bill himself. More formally, one of the derivations of the [Bill, 1] tuple is derived from the path A -> B, while the other is from A -> B -> J -> M -> B. Now, if we delete the A -> B edge, Ann's secret only loses one alternative derivation, but another one still remains because Bill relies on the information what Mike told him, while Mike relies on Jane, and, finally, Jane relies on Bill. What has happened is that the people in the cyclic "talks to" relationship are reinforcing each other in some false information (what is actually not true anymore). Because one alternative derivation remained, Bill is not forgetting Ann's secret, even though, he should (!), any, by that, all the others also keep that secret to themselves.

The Delete and REDerive evaluation helps in correctly computing the results in scenarios like this. The difference in the evaluation is as follows. When the A -> B edge is deleted, we decrement the counter of alternative derivations at Bill for Ann's secret from 2 to 1, but instead of concluding that Ann's secret is still known because of the remaining derivation, we kind of put the remaining derivation onto the side and temporarily forget about it. We do that because we want to see if that alternative still holds, and we do not want to falsely reinforce anybody by using that alternative. First, we let all the deletions to purge whatever needs to be purged, and only then start re-deriving information from what has survived the delete phase. What this means is that upon the deletion of the A -> B edge, Bill will say that he also does not know Ann's secret anymore (even though he has put aside the fact that he heard it from Mike). In response to that, Jane will also say that she does not know the secret, and, finally, Mike will also revoke his knowledge about that. The last bit is crucial because that one invalidates Bill's alternative information that was put aside before. The deletion phase has ended, and no tuples remained in the temporary store, which also means that we cannot re-derive anything. The evaluation has correctly derived that nobody knows Ann's secret once she is not talking to Bill anymore.

There are some important things to note:

• The first one is related to the non-DRED evaluation. The VIATRA Queries engine propagates tuples as long as the results of some pattern(s) change, that is, until a fixpoint is reached. When we concluded that after the deletion of A -> B everybody still knows Ann's secret, the engine has reached a fixpoint, but it was not the LEAST (or minimal) fixpoint. Intuitively, we associated the non-minimal fixpoint to a wrong pattern result.
• Another important aspect is that Delete and REDerive evaluation is not required if the model is changed only through insertions even if we have both kinds of cycles (patterns + instance models). This is because insertions are just expanding the results of patterns, and the previously explained cyclic reinforcement is not an issue in this case.
• Note that for the very common special case of transitive closures, the dedicated language element (transitive pattern call) is still likely to be more efficient than the DRED-based recursive solutions.
• With a small penalty in execution time, DRed guarantees correct result maintenance for arbitrary recursive pattern structures as long as all recursive calls are positive (i.e. no negation or aggregation along cycles of recursion occur).

As of now, the Delete and REDerive evaluation can be manually enabled using the query evaluation hint ReteHintOptions.deleteRederiveEvaluation.