We investigate the complexity of query processing in databases which have both incompletely specified data and deductive rules. The paper is divided into two parts: in the first we consider databases in which incompletely specified data occurs only in the database intension; in the second we consider databases in which incomplete information is represented only in database extension. We prove that, in general, the query processing problem for databases with incomplete intensions is undecidable. A number of classes of rules for which all conjunctive queries can be processed in polynomial time is then characterized. For databases with incomplete extensions we prove a number of CoNP completeness results. For instance, we demonstrate that processing disjunctions which are restricted to individual columns of database predicates can, in general, be as bad as processing arbitrary disjunctions (i.e. CoNP-complete). This falsifies the conjecture that such limited disjunctions could be computationally beneficial. We also show two simple examples of situations in which query processing is guaranteed to be polynomial. These situations are linked to certain assumptions about database updates. Finally, we provide a summary of the data complexity of queries depending on the type of database extension, intension, query sublanguage and Open World vs Closed World assumption.
All Science Journal Classification (ASJC) codes
- Artificial Intelligence
- Applied Mathematics