Representations for disjunctive deductive database [s]

Abstract

The concepts of the dual and complementary databases as alternative representations for a given disjunctive deductive database, DB, are introduced. The dual database results from interchanging the occurrences of OR and AND operators in the positive clause representation of DB. The complementary database is de ned to have as minimal models the complements of the minimal models of DB relative to the underlying Herbrand base, HBDB. The properties of these derivative databases are studied. In particular, we show that the minimal models of DB correspond to the minimally derivable clauses of the dual database and that the complementary database de nes the Extended Generalized Closed World Assumption (EGCW A) completion, and consequently the Generalized Closed World Assumption (GCW A) completion, of DB. A tree structure for minimally derivable clauses is de ned and algorithms for constructing and performing update and search operations on such trees are given