Efficient Evaluation of n-ary Conjunctive Queries over Trees and Graphs

N-ary conjunctive queries, i.e., queries with any number of answer variables, are the formal core of many Web query languages including XSLT, XQuery, SPARQL, and Xcerpt. Despite a considerable body of research on the optimization of such queries over tree-shaped XML data, little attention has been paid so far to efficient access to graph-shaped XML, RDF, or Topic Maps. We propose the first evaluation technique for n-ary conjunctive queries that applies to both tree- and graph-shaped data and retains the same complexity as the best known approaches that are restricted to tree-shaped data only. Furthermore, the approach treats tree and graph-shaped queries uniformly without sacrificing evaluation complexity on the restricted query class. The core of the evaluation technique is based on dynamic programming using a memoization data structure, called “memoization matrix”. It can be populated and consumed in different ways. For each of population and consumption, we propose two resp. three algorithms each having their own advantages. The complexity of the algorithms is compared analytically and experimentally. Categories and Subject Descriptors: E.1[Data]: Dat