ecrpq.pdf (386.11 kB)
Expressiveness and static analysis of extended conjunctive regular path queries
journal contribution
posted on 2017-09-19, 14:05 authored by Dominik FreydenbergerDominik Freydenberger, Nicole SchweikardtWe study the expressiveness and the complexity of static analysis of extended conjunctive regular path queries (ECRPQs), introduced by Barceló et al. (2010) [3]. ECRPQs are an extension of conjunctive regular path querie s (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 are 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. © 2013 Elsevier Inc.
History
School
- Science
Department
- Computer Science
Published in
Journal of Computer and System SciencesVolume
79Issue
6Pages
892 - 909Citation
FREYDENBERGER, D.D. and SCHWEIKARDT, N., 2013. Expressiveness and static analysis of extended conjunctive regular path queries. Journal of Computer and System Sciences, 79 (6), pp.892-909Publisher
© 2013 Elsevier Inc.Version
- AM (Accepted Manuscript)
Publisher statement
This work is made available according to the conditions of the Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International (CC BY-NC-ND 4.0) licence. Full details of this licence are available at: https://creativecommons.org/licenses/by-nc-nd/4.0/Publication date
2013Notes
This paper is a full version of the authors' conference contribution from the 5th Alberto Mendelzon International Workshop on Foundations of Data Management (AMW2011), Santiago, Chile, May 9-12, 2011.ISSN
0022-0000eISSN
1090-2724Publisher version
Language
- en