ACM SIGMOD Anthology ACM SIGMOD dblp.uni-trier.de

Query Evaluation under the Well Founded Semantics.

Weidong Chen, David Scott Warren: Query Evaluation under the Well Founded Semantics. PODS 1993: 168-179
@inproceedings{DBLP:conf/pods/ChenW93,
  author    = {Weidong Chen and
               David Scott Warren},
  title     = {Query Evaluation under the Well Founded Semantics},
  booktitle = {Proceedings of the Twelfth ACM SIGACT-SIGMOD-SIGART Symposium
               on Principles of Database Systems, May 25-28, 1993, Washington,
               DC},
  publisher = {ACM Press},
  year      = {1993},
  isbn      = {0-89791-593-3},
  pages     = {168-179},
  ee        = {http://doi.acm.org/10.1145/153850.153865, db/conf/pods/ChenW93.html},
  crossref  = {DBLP:conf/pods/93},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}

Abstract

SLD resolution with negation as finite failure (or SLDNF) reflects the procedural interpretation of Horn-clause predicate logic as a programming language and forms the computational basis for prolog systems. Despite its advantages in memory management, SLDNF is often not appropriate for query evaluation for three reasons; a) it may not terminate due to infinite positive recursion; b) it may not terminate due to infinite recursion through negation; and c) it may repeatedly evaluate the same clause body literal, leading to unacceptable performance.

We address all three problems for goal-oriented query evaluation of arbitrary programs by presenting an extension of SLDNF, called SLG resolution, with the following distinctive features:

(i) SLG resolution is a partial deduction procedure, consisting of several transformations. Each query is transformed step by step into a set of answer clauses;
(ii) SLG resolution is sound and ideally complete for all non-floundering queries with respect to all three-valued stable models (including the well founded partial model);
(iii) SLG resolution allows an arbitrary computation rule and an arbitrary control strategy for selecting transformations to apply;
(iv) SLG resolution avoids both positive and negative loops and always terminates for programs with the bounded-term-size property;
(v) SLG resolution has a polynomial time data complexity for well founded negation.

Restricted forms of SLG resolution are identified for definite, locally stratified, and modularly stratified programs, thereby shedding light on the role each transformation plays. To provide answers to a query under different three-valued stable models, SLG resolution can be enhanced by further processing of the derived set of answer clauses.

SLG resolution makes many more clausal specifications into effective programs. With simple (user or computer generated) annotations, SLDNF resolution and SLG resolution can be fully integrated. Thus a system including SLG resolution can be fully integrated. Thus a system including SLG resolution is naturally upward compatible with Prolog. For all these reasons we believe that SLG resolution will provide the computational basis for the next generation of logic programming systems.

Copyright © 1993 by the ACM, Inc., used by permission. Permission to make digital or hard copies is granted provided that copies are not made or distributed for profit or direct commercial advantage, and that copies show this notice on the first page or initial screen of a display along with the full citation.


Load The ACM SIGMOD Anthology, CDROM Edition, Volume 1-3, PODS '82-'98. and ... Load The ACM SIGMOD Anthology, Silver Edition, DVD 1, Proceedings. and ...

Printed Edition

Proceedings of the Twelfth ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems, May 25-28, 1993, Washington, DC. ACM Press 1993, ISBN 0-89791-593-3
Contents CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML

Online Edition: ACM Digital Library

[Abstract and Index Terms]
[Full Text in PDF Format, 1104 KB]

References

[1]
Isaac Balbin, Graeme S. Port, Kotagiri Ramamohanarao, Krishnamurthy Meenakshi: Efficient Bottom-UP Computation of Queries on Stratified Databases. J. Log. Program. 11(3&4): 295-344(1991) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[2]
François Bancilhon, David Maier, Yehoshua Sagiv, Jeffrey D. Ullman: Magic Sets and Other Strange Ways to Implement Logic Programs. PODS 1986: 1-15 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[3]
Nicole Bidoit, P. Legay: WELL!: An Evaluation Procedure for All Logic Programs. ICDT 1990: 335-348 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[4]
...
[5]
...
[6]
Weidong Chen, David Scott Warren: A Goal-Oriented Approach to Computing Well Founded Semantics. JICSLP 1992: 589-603 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[7]
...
[8]
...
[9]
David B. Kemp, Divesh Srivastava, Peter J. Stuckey: Magic Sets and Bottom-Up Evaluation of Well-Founded Models. ISLP 1991: 337-351 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[10]
David B. Kemp, Peter J. Stuckey, Divesh Srivastava: Query Restricted Bottom-Up Evaluation of Normal Logic Programs. JICSLP 1992: 288-302 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[11]
David B. Kemp, Rodney W. Topor: Completeness of a Top-Down Query Evaluation Procedure for Stratified Databases. ICLP/SLP 1988: 178-194 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[12]
...
[13]
John W. Lloyd, John C. Shepherdson: Partial Evaluation in Logic Programming. J. Log. Program. 11(3&4): 217-242(1991) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[14]
V. Wiktor Marek, Miroslaw Truszczynski: Autoepistemic Logic. J. ACM 38(3): 588-619(1991) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[15]
Shinichi Morishita: An anternating fixpoint tailored to magic programs. Workshop on Deductive Databases, JICSLP 1992: 86-95 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[16]
Halina Przymusinska, Teodor C. Przymusinski: Weakly Perfect Model Semantics for Logic Programs. ICLP/SLP 1988: 1106-1120 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[17]
Teodor C. Przymusinski: Every Logic Program Has a Natural Stratification And an Iterated Least Fixed Point Model. PODS 1989: 11-21 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[18]
Teodor C. Przymusinski: On the Declarative and Procedural Semantics of Logic Programs. J. Autom. Reasoning 5(2): 167-205(1989) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[19]
...
[20]
Raghu Ramakrishnan: Magic Templates: A Spellbinding Approach To Logic Programs. J. Log. Program. 11(3&4): 189-216(1991) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[21]
Raghu Ramakrishnan, Divesh Srivastava, S. Sudarshan: Controlling the Search in Bottom-Up Evaluation. JICSLP 1992: 273-287 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[22]
Kenneth A. Ross: A Procedural Semantics for Well Founded Negation in Logic Programs. PODS 1989: 22-33 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[23]
Kenneth A. Ross: A Prodedural Semantics for Well-Founded Negation in Logic Programs. J. Log. Program. 13(1): 1-22(1992) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[24]
...
[25]
Hirohisa Seki: On the Power of Alexander Templates. PODS 1989: 150-159 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[26]
Hirohisa Seki, Hidenori Itoh: A Query Evaluation Method for Stratified Programs Under the Extended CWA. ICLP/SLP 1988: 195-211 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[27]
Hisao Tamaki, Taisuke Sato: OLD Resolution with Tabulation. ICLP 1986: 84-98 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[28]
...
[29]
Allen Van Gelder, Kenneth A. Ross, John S. Schlipf: The Well-Founded Semantics for General Logic Programs. J. ACM 38(3): 620-650(1991) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[30]
Laurent Vieille: Recursive Query Processing: The Power of Logic. Theor. Comput. Sci. 69(1): 1-53(1989) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML

Copyright © Fri Mar 12 17:19:57 2010 by Michael Ley (ley@uni-trier.de)