Generic Search Plans for Matching Advanced Graph Patterns

Abstract

In the current paper, we present search plans which can guide pattern
matching for advanced graph patterns with edge identities, containment
constraints, type variables, negative application conditions, attribute
conditions, and injectivity constraints. Based on a generic search graph
representation, all search plan operations (e.g. checking the existence of
an edge, or extending a matching candidate by navigating along an edge) are
uniformly represented as special predicates with heuristically assigned
costs. Finally, an executable search plan is defined as an appropriate
ordering of these predicates. As a main consequence, attribute, injectivity,
and negative application conditions can be checked early (but not
unnecessarily early) in the pattern matching process to cut off infeasible
matching candidates at the right time.