Enhancing magic sets with an application to ontological reasoning
From MaRDI portal
Abstract: Magic sets are a Datalog to Datalog rewriting technique to optimize query answering. The rewritten program focuses on a portion of the stable model(s) of the input program which is sufficient to answer the given query. However, the rewriting may introduce new recursive definitions, which can involve even negation and aggregations, and may slow down program evaluation. This paper enhances the magic set technique by preventing the creation of (new) recursive definitions in the rewritten program. It turns out that the new version of magic sets is closed for Datalog programs with stratified negation and aggregations, which is very convenient to obtain efficient computation of the stable model of the rewritten program. Moreover, the rewritten program is further optimized by the elimination of subsumed rules and by the efficient handling of the cases where binding propagation is lost. The research was stimulated by a challenge on the exploitation of Datalog/ extsc{dlv} for efficient reasoning on large ontologies. All proposed techniques have been hence implemented in the extsc{dlv} system, and tested for ontological reasoning, confirming their effectiveness. Under consideration for publication in Theory and Practice of Logic Programming.
Recommendations
Cites work
- Analyzing logic programs using “prop”-ositional logic programs and a magic wand
- Anytime answer set optimization via unsatisfiable core shrinking
- Anytime computation of cautious consequences in answer set programming
- Bottom-up evaluation and query optimization of well-founded models
- Cautious reasoning in ASP via minimal models and unsatisfiable cores
- Complexity of super-coherence problems in ASP
- Dynamic magic sets and super-coherent answer set programs
- Dynamic magic sets for programs with monotone recursive aggregates
- Efficient bottom-up computation of queries on stratified databases
- Evaluation of disjunctive programs in WASP
- Extending and implementing the stable model semantics
- scientific article; zbMATH DE number 25190 (Why is no real title available?)
- Logic programs with abstract constraint atoms: the role of computations
- Logic programs with propositional connectives and aggregates
- Magic sets for disjunctive Datalog programs
- Modular stratification and magic sets for Datalog programs with negation
- Negation as failure using tight derivations for general logic programs
- On the declarative and procedural semantics of logic programs
- On the Implementation of Weight Constraint Rules in Conflict-Driven ASP Solvers
- On the power of magic
- Optimization of bound disjunctive queries with constraints
- Programming Languages and Systems
- Pushing extrema aggregates to optimize logic queries
- Rewriting recursive aggregates in answer set programming: back to monotonicity
- Semantics and complexity of recursive aggregates in answer set programming
- Shared aggregate sets in answer set programming
- The ASP system DLV2
- The well-founded semantics for general logic programs
- Vicious circle principle and logic programs with aggregates
- Well-founded and stable semantics of logic programs with aggregates
Cited in
(3)
This page was built for publication: Enhancing magic sets with an application to ontological reasoning
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5108494)
