Hypothetical reasoning in deductive databases
Anthony J. Bonner · 1992
This dissertation addresses a limitation of most deductive database systems: They cannot reason hypothetically. Although they reason effectively about the world as it is, they are poor at tasks such as planning and design, where one must infer the consequences of hypothetical actions and possibilities. For instance, with a typical database query language, a user can retrieve those students who are eligible to graduate, but cannot retrieve those students who would be eligible if they took one more course. To express such queries, the dissertation develops a logic programming language in which a user can create hypotheses and draw inferences from them. In addition, we show that the language has several important properties. First, it is more expressive than any database query language based on classical logic, since it can express some simple hypothetical queries that classical logic cannot. Second, it can describe large rulebases concisely, because as we show, hypothetical operations allow a user to specify new rulebases by reusing and modifying old ones. Finally, by imposing syntactic restrictions, the language expresses exactly the database queries in many well-known complexity classes, including polynomial space, exponential time, and the polynomial time hierarchy.