The authors address the issue of reasoning with two classes of commonly used semantic integrity constraints in database and knowledge-base systems: implication constraints and referential constraints. They first consider a central problem in this respect, the IRC-refuting problem, which is to decide whether a conjunctive query always produces an empty relation on (finite) database instances satisfying a given set of implication and referential constraints. Since the general problem is undecidable, they only consider acyclic referential constraints. Under this assumption, they prove that the IRC-refuting problem is decidable, and give a novel necessary and sufficient condition for it. Under the same assumption, they also study several other problems encountered in semantic query optimization, such as the semantics-based query containment problem, redundant join problem, and redundant selection-condition problem, and show that they are polynomially equivalent or reducible to the IRC-refuting problem. Moreover, they give results on reducing the complexity for some special cases of the IRC-refuting problem.

We study the issue of providing intelligent answers to recursive queries. We first extend the notion of intelligent answers by allowing them to be incomplete. Complete and incomplete intelligent answers are both useful in that they provide (possibly partial) characterizations of queries for users to understand. Complete intelligent answers also allows us to compute the queries more efficiently. We propose a general approach that enables us to combine several cases studied previously for constructing intelligent answers, Moreover, in our approach, semantic constraints can be systematically utilized to provide complete intelligent answers to a wider range of queries. We consider two commonly used classes of semantic constraints called implication and referential constraints, and show that the completeness of intelligent answers with respect to semantic constraints can be reduced to the semantics-based query containment problem.>