Taming the Infinite Chase: Query Answering under Expressive Relational Constraints

Principles of Knowledge Representation and Reasoning: Proceedings of the Eleventh International Conference (KR2008)

Volume

Principles of Knowledge Representation and Reasoning: Proceedings of the Eleventh International Conference (KR2008)

Contents

A crucial task in Knowledge Representation is answering queries posed over a knowledge base, represented as a set of facts plus a set of rules. In this paper we address the problem of answering conjunctive queries posed over knowledge bases where rules are an extension of Datalog rules, and may have existentially quantified variables in the head; this kind of rules are traditionally called tuple-generating dependencies (TGDs) in the database literature, but they are broadly used in description logics and in ontological reasoning. In this setting, the chase algorithm is an important tool for query answering. So far, most of the research has concentrated on cases where the chase terminates. We define and study large classes of TGDs under which the query evaluation problems remain decidable even in case the chase does not terminate. We provide tight complexity bounds for such cases. Our results immediately extend to query containment.