Semantic acyclicity on graph databases

Pablo Barceló, Miguel Romero, Moshe Y. Vardi

Research output: Chapter in Book/Report/Conference proceedingConference contributionpeer-review

10 Scopus citations


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.

Original languageEnglish
Title of host publicationPODS 2013 - Proceedings of the 32nd Symposium on Principles of Database Systems
Number of pages11
StatePublished - 2013
Externally publishedYes
Event32nd ACM SIGMOD-SIGACT-SIGART Symposium on Principles of Database Systems, PODS 2013 - New York, NY, United States
Duration: 22 Jun 201327 Jun 2013

Publication series

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


Conference32nd ACM SIGMOD-SIGACT-SIGART Symposium on Principles of Database Systems, PODS 2013
Country/TerritoryUnited States
CityNew York, NY


  • Acyclic-ity
  • Conjunctive regular path queries
  • Graph databases
  • Query approximation
  • Query evaluation


Dive into the research topics of 'Semantic acyclicity on graph databases'. Together they form a unique fingerprint.

Cite this