Magic sets and bottom-up evaluation of well-founded models

David B. Kemp, Peter J. Stuckey, Divesh Srivastava

Research output: Contribution to conferencePaper

29 Citations (Scopus)

Abstract

We present a bottom-up operational procedure for computing well-founded models of allowed DATALOG programs with negation. This procedure provides a practical method of handling programs that involve unstratified negation in a manner that may be mixed with other evaluation approaches, such as semi-naive evaluation. We also define classes of programs and sips for which the magic sets transformation preserves well-founded models with respect to the query. The class of programs and sips we consider strictly subsume those already considered in the literature, and include stratified programs (with any choice of sips), modularly stratified programs (with left-to-right sips) and programs with three-valued well-founded models (with well-founded sips). For these programs and sips, our procedure for computing well-founded models is applicable to the magic programs, thus allowing increased efficiency by specializing a program for a query.

Original languageEnglish
Pages337-351
Number of pages15
Publication statusPublished - 1 Dec 1991
Externally publishedYes
EventInternational Logic Programming Symposium 1991 - San Diego, United States of America
Duration: 28 Oct 19911 Nov 1991

Conference

ConferenceInternational Logic Programming Symposium 1991
Abbreviated titleILPS 1991
CountryUnited States of America
CitySan Diego
Period28/10/911/11/91

Cite this

Kemp, D. B., Stuckey, P. J., & Srivastava, D. (1991). Magic sets and bottom-up evaluation of well-founded models. 337-351. Paper presented at International Logic Programming Symposium 1991, San Diego, United States of America.