TY - GEN

T1 - Semantic acyclicity on graph databases

AU - Barceló, Pablo

AU - Romero, Miguel

AU - Vardi, Moshe Y.

PY - 2013

Y1 - 2013

N2 - It is known that unions of acyclic conjunctive queries (CQs) can be evaluated in linear time, as opposed to arbitrary CQs, for which the evaluation problem is NP-complete. It follows from techniques in the area of constraint-satisfaction problems that semantically acyclic unions of CQs - i.e., unions of CQs that are equivalent to a union of acyclic ones - can be evaluated in polynomial time, though testing membership in the class of semantically acyclic CQs is NP-complete. We study here the fundamental notion of semantic acyclic-ity in the context of graph databases and unions of conjunctive regular path queries with inverse (UC2RPQs). It is known that unions of acyclic C2RPQs can be evaluated efficiently, but it is by no means obvious whether the same holds for the class of UC2RPQs that are semantically acyclic. We prove that checking whether a UC2RPQ is semantically acyclic is decidable in 2Expspace, and that it is Expspace-hard even in the absence of inverses. Furthermore, we show that evaluation of semantically acyclic UC2RPQs is fixed-parameter tractable. In addition, our tools yield a strong theory of approximations for UC2RPQs when no equivalent acyclic UC2RPQ exists.

AB - It is known that unions of acyclic conjunctive queries (CQs) can be evaluated in linear time, as opposed to arbitrary CQs, for which the evaluation problem is NP-complete. It follows from techniques in the area of constraint-satisfaction problems that semantically acyclic unions of CQs - i.e., unions of CQs that are equivalent to a union of acyclic ones - can be evaluated in polynomial time, though testing membership in the class of semantically acyclic CQs is NP-complete. We study here the fundamental notion of semantic acyclic-ity in the context of graph databases and unions of conjunctive regular path queries with inverse (UC2RPQs). It is known that unions of acyclic C2RPQs can be evaluated efficiently, but it is by no means obvious whether the same holds for the class of UC2RPQs that are semantically acyclic. We prove that checking whether a UC2RPQ is semantically acyclic is decidable in 2Expspace, and that it is Expspace-hard even in the absence of inverses. Furthermore, we show that evaluation of semantically acyclic UC2RPQs is fixed-parameter tractable. In addition, our tools yield a strong theory of approximations for UC2RPQs when no equivalent acyclic UC2RPQ exists.

KW - Acyclic-ity

KW - Conjunctive regular path queries

KW - Graph databases

KW - Query approximation

KW - Query evaluation

UR - http://www.scopus.com/inward/record.url?scp=84880527450&partnerID=8YFLogxK

U2 - 10.1145/2463664.2463671

DO - 10.1145/2463664.2463671

M3 - Conference contribution

AN - SCOPUS:84880527450

SN - 9781450320665

T3 - Proceedings of the ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems

SP - 237

EP - 247

BT - PODS 2013 - Proceedings of the 32nd Symposium on Principles of Database Systems

T2 - 32nd ACM SIGMOD-SIGACT-SIGART Symposium on Principles of Database Systems, PODS 2013

Y2 - 22 June 2013 through 27 June 2013

ER -