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

Modular Stratification and Magic Sets for DATALOG Programs with Negation.

Kenneth A. Ross: Modular Stratification and Magic Sets for DATALOG Programs with Negation. PODS 1990: 161-171
@inproceedings{DBLP:conf/pods/Ross90,
  author    = {Kenneth A. Ross},
  title     = {Modular Stratification and Magic Sets for DATALOG Programs with
               Negation},
  booktitle = {Proceedings of the Ninth ACM SIGACT-SIGMOD-SIGART Symposium on
               Principles of Database Systems, April 2-4, 1990, Nashville, Tennessee},
  publisher = {ACM Press},
  year      = {1990},
  isbn      = {0-89791-352-3},
  pages     = {161-171},
  ee        = {http://doi.acm.org/10.1145/298514.298558, db/conf/pods/Ross90.html},
  crossref  = {DBLP:conf/pods/90},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}
BibTeX

Abstract

We propose a class of programs, called modularly stratified programs that have several attractive properties. Modular stratification generalizes stratification and local stratification, while allowing programs that are not expressible by stratified programs. For modularly stratified programs the well-founded semantics coincides with the stable model semantics, and makes every ground literal true or false. Modularly stratified programs are all weakly stratified, but the converse is false. Unlike some weakly stratified programs, modularly stratified programs can be evaluated in a subgoal-at-a-time fashion. We demonstrate a techinque for rewriting a modularly stratified program for bottom-up evaluation and extend this rewriting to include magic-set techniques. The rewritten program, when evaluated bottom-up, gives the same answers as the well-founded semantics. We discuss extending modular stratification to other operators such as set-grouping and aggregation that have traditionally been stratified to prevent semantic difficulties.

Copyright © 1990 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 ... BibTeX

Printed Edition

Proceedings of the Ninth ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems, April 2-4, 1990, Nashville, Tennessee. ACM Press 1990, ISBN 0-89791-352-3
Contents BibTeX

Online Edition: ACM Digital Library

References

[BMR88]
...
[BPR87]
...
[BPRMar]
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
[BR86]
François Bancilhon, Raghu Ramakrishnan: An Amateur's Introduction to Recursive Query Processing Strategies. SIGMOD Conference 1986: 16-52 BibTeX
[BR87]
Catriel Beeri, Raghu Ramakrishnan: On the Power of Magic. PODS 1987: 269-284 BibTeX
[BRSS89]
...
[Bry89a]
...
[Bry89b]
François Bry: Logic Programming as Constructivism: A Formalization and its Application to Databases. PODS 1989: 34-50 BibTeX
[BS89]
Alexander Brodsky, Yehoshua Sagiv: Inference of Monotonicity Constraints in Datalog Programs. PODS 1989: 190-199 BibTeX
[DW85]
...
[GL88]
Michael Gelfond, Vladimir Lifschitz: The Stable Model Semantics for Logic Programming. ICLP/SLP 1988: 1070-1080 BibTeX
[Kol87]
...
[KP88]
Jean-Marc Kerisit, Jean-Marc Pugin: Efficient Query Answering on Stratified Databases. FGCS 1988: 719-726 BibTeX
[KT88]
David B. Kemp, Rodney W. Topor: Completeness of a Top-Down Query Evaluation Procedure for Stratified Databases. ICLP/SLP 1988: 178-194 BibTeX
[PP88]
Halina Przymusinska, Teodor C. Przymusinski: Weakly Perfect Model Semantics for Logic Programs. ICLP/SLP 1988: 1106-1120 BibTeX
[Prz88]
...
[Ram88]
Raghu Ramakrishnan: Magic Templates: A Spellbinding Approach to Logic Programs. ICLP/SLP 1988: 140-159 BibTeX
[Ros89]
Kenneth A. Ross: A Procedural Semantics for Well Founded Negation in Logic Programs. PODS 1989: 22-33 BibTeX
[SI88]
Hirohisa Seki, Hidenori Itoh: A Query Evaluation Method for Stratified Programs Under the Extended CWA. ICLP/SLP 1988: 195-211 BibTeX
[Ull98a]
Jeffrey D. Ullman: Bottom-Up Beats Top-Down for Datalog. PODS 1989: 140-149 BibTeX
[Ull89b1]
Jeffrey D. Ullman: Principles of Database and Knowledge-Base Systems, Volume I. Computer Science Press 1988, ISBN 0-7167-8158-1
Contents BibTeX
[Ull89b2]
Jeffrey D. Ullman: Principles of Database and Knowledge-Base Systems, Volume II. Computer Science Press 1989, ISBN 0-7167-8162-X
Contents BibTeX
[VGRS88]
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
[Vie86]
Laurent Vieille: Recursive Axioms in Deductive Databases: The Query/Subquery Approach. Expert Database Conf. 1986: 253-267 BibTeX
[Vie87]
Laurent Vieille: A Database-Complete Proof Procedure Based on SLD-Resolution. ICLP 1987: 74-103 BibTeX

Referenced by

  1. David B. Kemp, Kotagiri Ramamohanarao: Efficient Recursive Aggregation and Negation in Deductive Databases. IEEE Trans. Knowl. Data Eng. 10(5): 727-745(1998)
  2. Nicola Leone, Pasquale Rullo, Antonella Mecchia, Giuseppe Rossi: A Deductive Environment for Dealing with Objects and Nonmonotonic Reasoning. IEEE Trans. Knowl. Data Eng. 9(4): 539-558(1997)
  3. Kotagiri Ramamohanarao, James Harland: An Introduction to Deductive Database Languages and Systems. VLDB J. 3(2): 107-122(1994)
  4. Raghu Ramakrishnan, Divesh Srivastava, S. Sudarshan, Praveen Seshadri: The CORAL Deductive System. VLDB J. 3(2): 161-210(1994)
  5. Marcia A. Derr, Shinichi Morishita, Geoffrey Phipps: The Glue-Nail Deductive Database System: Design, Implementation, and Evaluation. VLDB J. 3(2): 123-160(1994)
  6. Konstantinos F. Sagonas, Terrance Swift, David Scott Warren: XSB as an Efficient Deductive Database Engine. SIGMOD Conference 1994: 442-453
  7. Divesh Srivastava, Raghu Ramakrishnan, Praveen Seshadri, S. Sudarshan: Coral++: Adding Object-Orientation to a Logic Database Language. VLDB 1993: 158-170
  8. Marcia A. Derr, Shinichi Morishita, Geoffrey Phipps: Design and Implementation of the Glue-Nail Database System. SIGMOD Conference 1993: 147-156
  9. Shinichi Morishita: An Alternating Fixpoint Tailored to Magic Programs. PODS 1993: 123-134
  10. Raghu Ramakrishnan, Divesh Srivastava, S. Sudarshan: CORAL - Control, Relations and Logic. VLDB 1992: 238-250
  11. Catriel Beeri, Raghu Ramakrishnan, Divesh Srivastava, S. Sudarshan: The Valid Model Semantics for Logic Programs. PODS 1992: 91-104
  12. Kenneth A. Ross: On Negation in HiLog. PODS 1991: 206-215
  13. Kenneth A. Ross: Modular Acyclicity and Tail Recursion in Logic Programs. PODS 1991: 92-101
  14. Inderpal Singh Mumick, Hamid Pirahesh, Raghu Ramakrishnan: The Magic of Duplicates and Aggregates. VLDB 1990: 264-277
BibTeX
ACM SIGMOD Anthology - DBLP: [Home | Search: Author, Title | Conferences | Journals]
ACM SIGMOD Anthology: Copyright © by ACM (info@acm.org), Corrections: anthology@acm.org
DBLP: Copyright © by Michael Ley (ley@uni-trier.de), last change: Sat May 16 23:33:59 2009