An Alternating Fixpoint Tailored to Magic Programs.

Shinichi Morishita: An Alternating Fixpoint Tailored to Magic Programs. PODS 1993: 123-134

@inproceedings{DBLP:conf/pods/Morishita93,
  author    = {Shinichi Morishita},
  title     = {An Alternating Fixpoint Tailored to Magic Programs},
  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     = {123-134},
  ee        = {http://doi.acm.org/10.1145/153850.153861, db/conf/pods/Morishita93.html},
  crossref  = {DBLP:conf/pods/93},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}

BibTeX

Abstract

We study applying the magic-sets transformation technique to Datalog programs with negation that may not have 2-valued well-founded models. In this general setting we encounter the problem that the well-founded model of the original program does not always agree with the well-founded model of the magic program derived by commonly used left-to-right sips on the query. In order to fix this disagreement we present a novel method that is obtained by slightly and naturally tailoring Van Gelder's alternating fixpoint technique [16] to a magic program.

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 ...

Windows: Click the letter of your CD drive
A B C D E F G H I J K L M N O P Q R S T U V W X Y Z
UNIX/LINUX/Mac: use mount point /pods8298/... or /cdrom/...

Load The ACM SIGMOD Anthology, Silver Edition, DVD 1, Proceedings. and ...

Windows: Click the letter of your CD drive
A B C D E F G H I J K L M N O P Q R S T U V W X Y Z
UNIX/LINUX/Mac: use mount point /aDVD1/... or /cdrom/...

BibTeX

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 BibTeX

Online Edition: ACM Digital Library

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

Journal Version

Shinichi Morishita: An Extension of Van Gelder's Alternating Fixpoint to Magic Programs. J. Comput. Syst. Sci. 52(3): 506-521(1996) BibTeX

References

[1]: ...
[2]: 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) BibTeX
[3]: Catriel Beeri, Raghu Ramakrishnan: On the Power of Magic. PODS 1987: 269-284 BibTeX
[4]: Weidong Chen, David Scott Warren: A Goal-Oriented Approach to Computing Well Founded Semantics. JICSLP 1992: 589-603 BibTeX
[5]: Marcia A. Derr, Shinichi Morishita, Geoffrey Phipps: Design and Implementation of the Glue-Nail Database System. SIGMOD Conference 1993: 147-156 BibTeX
[6]: Jean-Marc Kerisit, Jean-Marc Pugin: Efficient Query Answering on Stratified Databases. FGCS 1988: 719-726 BibTeX
[7]: David B. Kemp, Divesh Srivastava, Peter J. Stuckey: Magic Sets and Bottom-Up Evaluation of Well-Founded Models. ISLP 1991: 337-351 BibTeX
[8]: David B. Kemp, Peter J. Stuckey, Divesh Srivastava: Query Restricted Bottom-Up Evaluation of Normal Logic Programs. JICSLP 1992: 288-302 BibTeX
[9]: John W. Lloyd: Foundations of Logic Programming, 2nd Edition. Springer 1987, ISBN 3-540-18199-7
BibTeX
[10]: Raghu Ramakrishnan, Divesh Srivastava, S. Sudarshan: Controlling the Search in Bottom-Up Evaluation. JICSLP 1992: 273-287 BibTeX
[11]: Kenneth A. Ross: A Prodedural Semantics for Well-Founded Negation in Logic Programs. J. Log. Program. 13(1): 1-22(1992) BibTeX
[12]: Kenneth A. Ross: Modular Stratification and Magic Sets for DATALOG Programs with Negation. PODS 1990: 161-171 BibTeX
[13]: Yehoshua Sagiv: Is There Anything Better than Magic? NACLP 1990: 235-254 BibTeX
[14]: Jeffrey D. Ullman: Principles of Database and Knowledge-Base Systems, Volume II. Computer Science Press 1989, ISBN 0-7167-8162-X
Contents BibTeX
[15]: Allen Van Gelder, Kenneth A. Ross, John S. Schlipf: The Well-Founded Semantics for General Logic Programs. J. ACM 38(3): 620-650(1991) BibTeX
[16]: Allen Van Gelder: The Alternating Fixpoint of Logic Programs with Negation. PODS 1989: 1-10 BibTeX

Referenced by

R. Ramesh, Weidong Chen: Implementation of Tabled Evaluation with Delaying in Prolog. IEEE Trans. Knowl. Data Eng. 9(4): 559-574(1997)
Kenneth A. Ross: Tail Recursion Elimination in Deductive Databases. ACM Trans. Database Syst. 21(2): 208-237(1996)
Marcia A. Derr, Shinichi Morishita, Geoffrey Phipps: The Glue-Nail Deductive Database System: Design, Implementation, and Evaluation. VLDB J. 3(2): 123-160(1994)
Konstantinos F. Sagonas, Terrance Swift, David Scott Warren: XSB as an Efficient Deductive Database Engine. SIGMOD Conference 1994: 442-453
Marcia A. Derr, Shinichi Morishita, Geoffrey Phipps: Design and Implementation of the Glue-Nail Database System. SIGMOD Conference 1993: 147-156

BibTeX

ACM SIGMOD Anthology - DBLP: [Home | Search: Author, Title | Conferences | Journals]