Semantic acyclicity on graph databases

Pablo Barceló, Miguel Romero, Moshe Y. Vardi

Research output: Contribution to journalArticlepeer-review

19 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 acyclicity 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 similarly good evaluation properties hold for the class of UC2RPQs that are semantically acyclic. We prove that checking whether a UC2RPQ is semantically acyclic is Expspace-complete and obtain as a corollary 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
Pages (from-to)1339-1376
Number of pages38
JournalSIAM Journal on Computing
Issue number4
StatePublished - 2016
Externally publishedYes


  • Acyclicity
  • Conjunctive queries
  • Conjunctive regular path queries
  • Constraint satisfaction problems
  • 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