A three-phase query processing technique for indefinite databases
Shan Chi · 1988
A new method, called the compile-access-prove (CAP) algorithm, is proposed for query processing in indefinite databases. A database is logically represented as a set of clauses among which the non-Horn clauses represent indefinite information. Physically the database intension, containing view definitions, is compiled into access rules and the database extension, containing elementary facts, is stored as relations on disks. Each access rule is a procedure consisting of relational operations. In general, the indefinite elementary facts need to be processed with a theorem prover. By storing all elementary facts (including indefinite ones) into relations, it is possible to replace the theorem proving steps with more efficient relational operations. However, this process changes the semantics of the database. At query time, the related indefinite elementary facts are collected and sent to a theorem prover to recover the original semantics. The CAP algorithm has the following advantages: (a) it is capable of answering queries for recursive indefinite databases, (b) the theorem prover involves only the indefinite facts related to the query, (c) updating the database extension does not require the recompilation of the database, and (d) the techniques developed for Horn databases can be used in the algorithm.