Loughborough University
Browse
paper9.pdf (335.43 kB)

Expressiveness and static analysis of extended conjunctive regular path queries

Download (335.43 kB)
conference contribution
posted on 2017-09-05, 13:47 authored by Dominik FreydenbergerDominik Freydenberger, Nicole Schweikardt
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 con- junctive 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.

History

School

  • Science

Department

  • Computer Science

Published in

CEUR Workshop Proceedings

Volume

749

Citation

FREYDENBERGER, D.D. and SCHWEIKARDT, N., 2011. Expressiveness and static analysis of extended conjunctive regular path queries. IN: Barceló, P. and Tannen, V. (eds). CEUR Workshop Proceedings: Proceedings of the 5th Alberto Mendelzon International Workshop on Foundations of Data Management (AMW2011), Santiago, Chile, May 9-12, 2011, vol. 749, paper 9

Publisher

CEUR-WS.org (© the authors)

Version

  • NA (Not Applicable or Unknown)

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

2011

Notes

This conference paper was published by CEUR Workshop Proceedings and can be found at: http://ceur-ws.org/Vol-749/paper9.pdf. Copying of items, in particular papers, and proceedings volumes is permitted only for private and academic purposes. The permission for academic use implies an attribution obligation, i.e., you must properly cite the items that you use in your own published work. Modification of items is not permitted unless a suitable license is granted by its copyright owners. Copying or use for commercial purposes is forbidden unless an explicit permission is acquired from the copyright owners. Re-publication of a CEUR Workshop Proceedings volume or of an individual item inside a proceedings volume requires permission by the copyright owners, i.e. either the respective proceedings editors, or the authors of the respective item in that volume, or both.

ISSN

1613-0073

Book series

CEUR Workshop Proceedings;749

Language

  • en

Usage metrics

    Loughborough Publications

    Exports

    RefWorks
    BibTeX
    Ref. manager
    Endnote
    DataCite
    NLM
    DC