Dynamic magic sets

Abstract

Disjunctive Datalog with stable model semantics is a rule–based language for knowledge representation and common sense reasoning that also allows to use queries for checking the presence of specific atoms in stable models. Expressive- ness is a strength of the language, which indeed captures the second level of the polynomial hierarchy. However, because of this high expressive power, evalu- ating Disjunctive Datalog programs and queries is inherently nondeterministic. In fact, Disjunctive Datalog computations are typically characterized by two distinct phases. The first phase, referred to as program instantiation, is deter- ministic and associates input programs with equivalent ground programs; only deterministic knowledge is inferred in this phase. The second phase, referred to as stable model search, is nondeterministic and computes stable models of instantiated programs. Many query optimization techniques have been proposed in the literature. Among them are Magic Sets, originally introduced for standard Datalog pro- grams. Program instantiation is sufficient for computing the semantics of stan- dard Datalog programs because only deterministic knowledge can be represented in this case. For this reason, the original Magic Set technique is only focused on the optimization of program instantiation. Dynamic Magic Sets are an exten- sion of the technique that takes into account the nondeterministic knowledge encoded into Disjunctive Datalog programs. In fact, in addition to the standard optimization of program instantiation, Dynamic Magic Sets provide further op- timization potential to the subsequent stable model search. In this thesis, Dynamic Magic Sets are proved to be sound and complete for stratified and super–coherent programs. To this end, a strong relationship between magic atoms and unfounded sets is highlighted. Dynamic Magic Sets are also used for proving decidability of reasoning for a class of programs with uninterpreted function symbols. In particular, it is shown that the application of Dynamic Magic Sets to finitely recursive queries generates finitely ground programs, for which decidability of reasoning has been established in the liter- ature. Dynamic Magic Sets have been implemented in a prototype extending DLV, a state–of–the–art system for Disjunctive Datalog programs and queries. The effectiveness of Dynamic Magic Sets has been assessed by experimenting with the prototype system. Experimental results confirm that Dynamic Magic Sets can provide significant, possibly exponential, performance gains.