By Mario Alviano,
Università della Calabria
December 2010
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. Expressiveness is a strength of the language, which indeed captures the second level of the polynomial hierarchy. However, because of this high expressive power, evaluating 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 deterministic 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 programs. Program instantiation is sufficient for computing the semantics of standard 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 extension 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 optimization 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 literature.
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.