Recursive Graph Pattern Matching: With Magic Sets and Global Search Plans

TitleRecursive Graph Pattern Matching: With Magic Sets and Global Search Plans
Publication TypeConference Paper
Year of Publication2007
AuthorsVarró, G., Horváth, Á., and Varró, D.
EditorSchürr, A., Nagl, M., and Zündorf, A.
Conference NameProc. Third International Workshop and Symposium on Applications of Graph Transormation with Industrial Relevance (AGTIVE 2007)
PublisherSpringer
KeywordsPattern matching, recursive pattern matching, Viatra
Abstract

We present core data structures and algorithms for matching graph patterns with general recursion. Our approach uses magic sets, a well-known technique from deductive databases, which combines fixpoint-based bottom-up query evaluation with top-down handling of input parameters. Furthermore, this technique is enhanced with the global search plans, thus non-recursive calls are always flattened before elementary pattern matching operations are initiated in order to improve performance.

PDF: