License: Creative Commons Attribution-NonCommercial-NoDerivs 3.0 Unported license (CC BY-NC-ND 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.ICLP.2010.226
URN: urn:nbn:de:0030-drops-26012
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2010/2601/
Go to the corresponding LIPIcs Volume Portal

Alviano, Mario

Dynamic Magic Sets for Disjunctive Datalog Programs

pdf-format:
10003.AlvianoMario.2601.pdf (0.2 MB)

Abstract

Answer set programming (ASP) is a powerful formalism for knowledge representation and common sense reasoning that allows disjunction in rule heads and nonmonotonic negation in bodies. Magic Sets are a technique for optimizing query answering over logic programs and have been originally defined for standard Datalog, that is, ASP without disjunction and negation. Essentially, the input program is rewritten in order to identify a subset of the program instantiation which is sufficient for answering the query.

Dynamic Magic Sets (DMS) are an extension of this technique to ASP. The optimization provided by DMS can be exploited also during the nondeterministic phase of ASP systems. In particular, after some assumptions have been made during the computation, parts of the program may become irrelevant to a query (because of these assumptions). This allows for dynamic pruning of the search space, which may result in exponential performance gains.

DMS has been implemented in the dlv system and experimental results confirm the effectiveness of the technique.

BibTeX - Entry

@InProceedings{alviano:LIPIcs:2010:2601,
  author =	{Mario Alviano},
  title =	{{Dynamic Magic Sets for Disjunctive Datalog Programs}},
  booktitle =	{Technical Communications of the 26th International Conference on Logic Programming},
  pages =	{226--235},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-17-0},
  ISSN =	{1868-8969},
  year =	{2010},
  volume =	{7},
  editor =	{Manuel Hermenegildo and Torsten Schaub},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2010/2601},
  URN =		{urn:nbn:de:0030-drops-26012},
  doi =		{10.4230/LIPIcs.ICLP.2010.226},
  annote =	{Keywords: Answer set programming, decidability, magic sets, disjunctive logic programs}
}

Keywords: Answer set programming, decidability, magic sets, disjunctive logic programs
Collection: Technical Communications of the 26th International Conference on Logic Programming
Issue Date: 2010
Date of publication: 25.06.2010

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI