Query processing in deductive databases with incomplete information

We study here automated deduction in databases in the presence of various types of inference rules of the form of Horn Clauses with Skolem functions. These inference rules are typical for databases with incomplete information. We demonstrate a number of results related to processing of conjunctive queries for different types of database intensions. In particular, we show that when a database intension is built from possibly cyclic inclusion dependencies and view definitions any conjunctive query can be translated to the an equivalent form which can be evaluated directly over the database extension (disregarding inference rules). We also demonstrate that the complexity of query processing significantly grows when we mix incomplete information with recursive rules. In particular, we demonstrate here that even the power of least fixpoint extension of first order logic may be not sufficient to process queries in the presence of incomplete data and recursive rules. The same is demonstrated in case disjunctive information is allowed in the database.