Expressiveness and Static Analysis of Extended Conjunctive Regular Path Queries

Alberto Mendelzon International Workshop on Foundations of Data Management 2011.

社会科学（总论）;计算机科学

Dominik D. Freydenberger ; Nicole Schweikardt

Others  :  http://ceur-ws.org/Vol-749/paper9.pdf
PID  :  41710

来源: CEUR

【 摘 要 】

We study the expressiveness and the complexity of static analysis of extended conjunctive regular path queries (ECRPQs), introduced by Barceló et al. (PODS '10). ECRPQs are an extension of conjunctive regular path queries (CRPQs), a well-studied language for querying graph structured databases. Our first main result shows that query containment and equivalence of a CRPQ in an ECRPQ is undecidable. This settles one of the main open problems posed by Barceló et al. As a second main result, we prove a non-recursive succinctness gap between CRPQs and the CRPQ-expressible fragment of ECRPQs. Apart from this, we develop a tool for proving inexpressibility results for CRPQs and ECRPQs. In particular, this enables us to show that there exist queries definable by regular expressions with backreferencing, but not expressible by ECRPQs.