Binding Propagation in Disjunctive Databases.

Sergio Greco: Binding Propagation in Disjunctive Databases. VLDB 1998: 287-298

@inproceedings{DBLP:conf/vldb/Greco98,
  author    = {Sergio Greco},
  editor    = {Ashish Gupta and
               Oded Shmueli and
               Jennifer Widom},
  title     = {Binding Propagation in Disjunctive Databases},
  booktitle = {VLDB'98, Proceedings of 24rd International Conference on Very
               Large Data Bases, August 24-27, 1998, New York City, New York,
               USA},
  publisher = {Morgan Kaufmann},
  year      = {1998},
  isbn      = {1-55860-566-5},
  pages     = {287-298},
  ee        = {db/conf/vldb/Greco98.html},
  crossref  = {DBLP:conf/vldb/98},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}

Abstract

In this paper we present a technique for the propagation of bindings into disjunctive deductive databases. The optimization is based on the rewriting of the source program into a program which is equivalent to the original one under the possible semantics. In particular, the rewriting technique generates a program which is disjunctive with nested rules in the head, i.e., elements in the head may also be (special) rules. The proposed optimization reduces the size of the data relevant to answer the query and, consequently, (i) reduces the complexity of computing a single model and, more importantly, (ii) greatly reduces the number of modelsto be considered to answer the query. Although in this paper we consider negation free and stratified linear programs, the technique can easily be extended to the full class of programs with stratified negation.

Copyright © 1998 by the VLDB Endowment. Permission to copy without fee all or part of this material is granted provided that the copies are not made or distributed for direct commercial advantage, the VLDB copyright notice and the title of the publication and its date appear, and notice is given that copying is by the permission of the Very Large Data Base Endowment. To copy otherwise, or to republish, requires a fee and/or special permission from the Endowment.

Online Paper

Download PDF file (www.vldb.org, Darmstadt, Germany)
Download PDF file (www.acm.org, New York, USA)

ACM SIGMOD DiSC

CDROM Version: Load the CDROM "DiSC, Volume 1 Number 1" 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
Mac: Click here
UNIX/LINUX: mount the CD and click on the path of your mount point:
/Anthology/Disc99_1 or /cdrom

ACM SIGMOD Anthology

DVD Version: Load ACM SIGMOD Anthology DVD 1" 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
Mac: Click here
UNIX/LINUX: mount the DVD and click on the path of your mount point:
/Anthology/aDVD1 or /dvd

Printed Edition

Ashish Gupta, Oded Shmueli, Jennifer Widom (Eds.): VLDB'98, Proceedings of 24rd International Conference on Very Large Data Bases, August 24-27, 1998, New York City, New York, USA. Morgan Kaufmann 1998, ISBN 1-55860-566-5
Contents

References

[1]: Serge Abiteboul, Richard Hull, Victor Vianu: Foundations of Databases. Addison-Wesley 1995, ISBN 0-201-53771-0
Contents
[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
[3]: Catriel Beeri, Raghu Ramakrishnan: On the Power of Magic. PODS 1987: 269-284
[4]: ...
[5]: Thomas Eiter, Georg Gottlob, Heikki Mannila: Disjunctive Datalog. ACM Trans. Database Syst. 22(3): 364-418(1997)
[6]: Thomas Eiter, Nicola Leone, Cristinel Mateis, Gerald Pfeifer, Francesco Scarcello: A Deductive System for Non-Monotonic Reasoning. LPNMR 1997: 364-375
[7]: José Alberto Fernández, Jack Minker: Semantics of Disjunctive Deductive Databases. ICDT 1992: 21-50
[8]: Michael Gelfond, Vladimir Lifschitz: The Stable Model Semantics for Logic Programming. ICLP/SLP 1988: 1070-1080
[9]: Michael Gelfond, Vladimir Lifschitz: Classical Negation in Logic Programs and Disjunctive Databases. New Generation Comput. 9(3/4): 365-386(1991)
[10]: ...
[11]: Sergio Greco, Domenico Saccà, Carlo Zaniolo: The PushDown Method to Optimize Chain Logic Programs (Extended Abstract). ICALP 1995: 523-534
[12]: ...
[13]: Laks V. S. Lakshmanan, Fereidoon Sadri: Probabilistic Deductive Databases. SLP 1994: 254-268
[14]: Nicola Leone, Pasquale Rullo, Francesco Scarcello: Disjunctive Stable Models: Unfounded Sets, Fixpoint Semantics, and Computation. Inf. Comput. 135(2): 69-112(1997)
[15]: ...
[16]: Jack Minker: On Indefinite Databases and the Closed World Assumption. CADE 1982: 292-308
[17]: Jeffrey F. Naughton, Raghu Ramakrishnan, Yehoshua Sagiv, Jeffrey D. Ullman: Argument Reduction by Factoring. VLDB 1989: 173-182
[18]: Jeffrey F. Naughton, Raghu Ramakrishnan, Yehoshua Sagiv, Jeffrey D. Ullman: Efficient Evaluation of Right-, Left-, and Mult-Lineare Rules. SIGMOD Conference 1989: 235-242
[19]: Teodor C. Przymusinski: Stable Semantics for Disjunctive Programs. New Generation Comput. 9(3/4): 401-424(1991)
[20]: Raghu Ramakrishnan, Yehoshua Sagiv, Jeffrey D. Ullman, Moshe Y. Vardi: Logical Query Optimization by Proff-Tree Transformation. J. Comput. Syst. Sci. 47(1): 222-248(1993)
[21]: Jeffrey D. Ullman: Principles of Database and Knowledge-Base Systems, Volume II. Computer Science Press 1989, ISBN 0-7167-8162-X
Contents
[22]: Allen Van Gelder, Kenneth A. Ross, John S. Schlipf: The Well-Founded Semantics for General Logic Programs. J. ACM 38(3): 620-650(1991)