TY - GEN
T1 - Boundedness of conjunctive regular path queries
AU - Barceló, Pablo
AU - Figueira, Diego
AU - Romero, Miguel
N1 - Funding Information:
Funding Barceló is funded by the Millennium Inst. for Foundational Research on Data and Fondecyt 1170109, and Figueira by ANR project DELTA (grant ANR-16-CE40-0007) and ANR project QUID (grant ANR-18-CE40-0031). This project has received funding from the European Research Council (ERC) under the European Union’s Horizon 2020 research and innovation programme (grant agreement No 714532). The paper reflects only the authors’ views and not the views of the ERC or the European Commission. The European Union is not liable for any use that may be made of the information contained therein.
Publisher Copyright:
© Pablo Barceló, Diego Figueira, and Miguel Romero; licensed under Creative Commons License CC-BY
PY - 2019/7/1
Y1 - 2019/7/1
N2 - We study the boundedness problem for unions of conjunctive regular path queries with inverses (UC2RPQs). This is the problem of, given a UC2RPQ, checking whether it is equivalent to a union of conjunctive queries (UCQ). We show the problem to be ExpSpace-complete, thus coinciding with the complexity of containment for UC2RPQs. As a corollary, when a UC2RPQ is bounded, it is equivalent to a UCQ of at most triple-exponential size, and in fact we show that this bound is optimal. We also study better behaved classes of UC2RPQs, namely acyclic UC2RPQs of bounded thickness, and strongly connected UCRPQs, whose boundedness problem is, respectively, PSpace-complete and ΠP2 -complete. Most upper bounds exploit results on limitedness for distance automata, in particular extending the model with alternation and two-wayness, which may be of independent interest.
AB - We study the boundedness problem for unions of conjunctive regular path queries with inverses (UC2RPQs). This is the problem of, given a UC2RPQ, checking whether it is equivalent to a union of conjunctive queries (UCQ). We show the problem to be ExpSpace-complete, thus coinciding with the complexity of containment for UC2RPQs. As a corollary, when a UC2RPQ is bounded, it is equivalent to a UCQ of at most triple-exponential size, and in fact we show that this bound is optimal. We also study better behaved classes of UC2RPQs, namely acyclic UC2RPQs of bounded thickness, and strongly connected UCRPQs, whose boundedness problem is, respectively, PSpace-complete and ΠP2 -complete. Most upper bounds exploit results on limitedness for distance automata, in particular extending the model with alternation and two-wayness, which may be of independent interest.
KW - Boundedness
KW - Distance automata
KW - Limitedness
KW - Regular path queries
UR - http://www.scopus.com/inward/record.url?scp=85069149711&partnerID=8YFLogxK
U2 - 10.4230/LIPIcs.ICALP.2019.104
DO - 10.4230/LIPIcs.ICALP.2019.104
M3 - Conference contribution
AN - SCOPUS:85069149711
T3 - Leibniz International Proceedings in Informatics, LIPIcs
BT - 46th International Colloquium on Automata, Languages, and Programming, ICALP 2019
A2 - Baier, Christel
A2 - Chatzigiannakis, Ioannis
A2 - Flocchini, Paola
A2 - Leonardi, Stefano
PB - Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing
T2 - 46th International Colloquium on Automata, Languages, and Programming, ICALP 2019
Y2 - 9 July 2019 through 12 July 2019
ER -