Decidable Containment of Recursive Queries

Theoretical Computer Science. 336(1):33--56 2005.

One of the most important reasoning tasks on queries is checking containment, i.e., verifying whether one query yields necessarily a subset of the result of another one. Query containment is crucial in several contexts, such as query optimization, query reformulation, knowledge-base verification, information integration, integrity checking, and cooperative answering. Containment is undecidable in general for Datalog, the fundamental language for expressing recursive queries. On the other hand, it is known that containment between monadic Datalog queries and between Datalog queries and unions of conjunctive queries are decidable. It is also known that containment between unions of conjunctive two-way regular path queries, which are queries used in the context of semistructured data models containing a limited form of recursion in the form of transitive closure, is decidable. In this paper we combine the automata-theoretic techniques at the base of these two decidability results to show that containment of Datalog in union of conjunctive two-way regular path queries is decidable in 2EXPTIME. By sharpening a known lower bound result for containment of Datalog in union of conjunctive queries we show also a matching lower bound.

@article{TCS-2005,
   title = "Decidable Containment of Recursive Queries",
   year = "2005",
  author = "Diego Calvanese and De Giacomo, Giuseppe and Moshe Y. Vardi",
   journal = "Theoretical Computer Science",
   pages = "33--56",
   number = "1",
   volume = "336",
   doi = "10.1016/j.tcs.2004.10.031",
}