Abstract
Query answering in the presence of integrity constraints is a fundamental problem in 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 the above 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.