Decidable Containment of Recursive Queries

Proc. of the 9th Int. Conf. on Database Theory (ICDT 2003). Volume 2572 of Lecture Notes in Computer Science. 2003.

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 (UC2RPQs), 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 UC2RPQs is decidable in 2EXPTIME.

@inproceedings{ICDT-2003,
   title = "Decidable Containment of Recursive Queries",
   year = "2003",
  author = "Diego Calvanese and De Giacomo, Giuseppe and Moshe Y. Vardi",
   booktitle = "Proc. of the 9th Int. Conf. on Database Theory (ICDT 2003)",
   pages = "330--345",
   volume = "2572",
   publisher = "Springer",
   series = "Lecture Notes in Computer Science",
   doi = "10.1007/3-540-36285-1_22",
}