Skip to main content
Jump to: navigation, search


Local Search

This page summarizes the improvement ideas concerning the local search-based pattern matching capabilites of VIATRA Query.

  • Hybrid pattern matching:
    • New ISearchOperation to support calling an incremental matcher
    • Provide input for the flattener: which patterns should NOT be flattened. Implement this by creating an interface with a method that expects a constraint and a pattern. (Interface added)
  • Implement a weight function to estimate the cost of a given search plan over a model
  • Learning algorithm: the planner shall be able to tune its internal parameters regarding the planning process. This could be done by providing (small) example models and measuring pattern matching performance.
  • Provide a low-level code generator: instead of the current execution method, that is based on sequential exectuion of ISearchOperations contained in plans, generate executable code. This might be in a form of several embedded for loops and if conditions.
  • Support the POperationCompiler with normalization capability to remove redundant constraints thus decrease the search plan size.
  • Investigate if new VQL elements (e.g. containment) should be added that are only supported by either the local search-based or the RETE algorithm.
  • Support parallelism for plan execution. For example, the search graph traversal can be done simultaneously starting from different nodes.
  • Discuss different plan generation options and additional capabilities here.

Known problems

Based on the fact that the local search matcher itself does not use the EMF notification API, in some cases the RETE and the local search-based matchers may return different match sets after model modification. At the current state of development this issue can be reproduced by running the School tests "deleteAllYear" or "deleteTeacher2", where EObjects, which are not part of the EMF model, are still reached by object level references by the local search matcher, generating unexpected matches. When calling EcoreUtil#delete on the object to-be-removed, the phenomenon does not occur. By rewriting the mentioned tests to use this EMF utility class the mentioned tests are also passing.

It is important to also note that the local search matcher might use the base index to get nodes/edges located in the model. This case (while all elements are collected using the index) the result set will be the same as the RETE matcher, for the base index does listen to the notifications from the EMF model.

Back to the top