Answering Recursive Queries under Keys and Foreign Keys is Undecidable

Proc. of the 10th Int. Workshop on Knowledge Representation meets Databases (KRDB 2003). Volume 79 of CEUR Workshop Proceedings, https://ceur-ws.org/. 2003.

Query answering in the presence of integrity constraints is a fundamental problem is several settings, such as information integration. Keys, foreign keys and inclusion dependencies are the most common forms of constraints used in databases. It has been established recently that, in the presence of such constraints, query answering is decidable for non-recursive queries. Obviously, in the absence of constraints, query answering is also decidable for recursive queries, which are a powerful querying mechanism that subsumes query languages for semistructured data and the semantic web. It was open whether answering recursive queries in the presence of these classes of constraints is decidable. In this paper we show that this is indeed not the case. In particular, we show that answering recursive queries under keys and foreign keys or under inclusion dependencies is undecidable, both for unrestricted and for finite databases.

@inproceedings{KRDB-2003,
   title = "Answering Recursive Queries under Keys and Foreign Keys is
Undecidable",
   year = "2003",
   author = "Diego Calvanese and Riccardo Rosati",
   booktitle = "Proc. of the 10th Int. Workshop on Knowledge Representation
meets Databases (KRDB 2003)",
   pages = "3--14",
   volume = "79",
   publisher = "CEUR-WS.org",
   series = "CEUR Workshop Proceedings, https://ceur-ws.org/",
}