Semantic Acyclicity on Graph Databases

Abstract

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