Rewriting and Efficient Computation of Bound Disjunctive Datalog Queries

A strong interest in enhancing Datalog programs by the capability of disjunction emerged in several areas, such as databases, artificial intelligence, logic programming, and so forth (Lobo, Minker & Rajasekar, 1992). Disjunctive rules have been profitably used in several contexts including knowledge representation, databases querying, and representation of incomplete information (Eiter, Gottlob & Mannila, 1997a; Gelfond & Lifschitz, 1991). Most of the works on disjunction are concerned with the definition of intuitive and expressive semantics, which are commonly based on the paradigm of minimal models (Abiteboul, Hull & Vianu, 1995; Lobo et al., 1992; Ullman, 1989).