ACM SIGMOD Anthology VLDB dblp.uni-trier.de

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}
}
BibTeX

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

ACM SIGMOD DiSC

CDROM Version: Load the CDROM "DiSC, Volume 1 Number 1" and ...

ACM SIGMOD Anthology

DVD Version: Load ACM SIGMOD Anthology DVD 1" and ... BibTeX

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 BibTeX

References

[1]
Serge Abiteboul, Richard Hull, Victor Vianu: Foundations of Databases. Addison-Wesley 1995, ISBN 0-201-53771-0
Contents BibTeX
[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 BibTeX
[3]
Catriel Beeri, Raghu Ramakrishnan: On the Power of Magic. PODS 1987: 269-284 BibTeX
[4]
...
[5]
Thomas Eiter, Georg Gottlob, Heikki Mannila: Disjunctive Datalog. ACM Trans. Database Syst. 22(3): 364-418(1997) BibTeX
[6]
Thomas Eiter, Nicola Leone, Cristinel Mateis, Gerald Pfeifer, Francesco Scarcello: A Deductive System for Non-Monotonic Reasoning. LPNMR 1997: 364-375 BibTeX
[7]
José Alberto Fernández, Jack Minker: Semantics of Disjunctive Deductive Databases. ICDT 1992: 21-50 BibTeX
[8]
Michael Gelfond, Vladimir Lifschitz: The Stable Model Semantics for Logic Programming. ICLP/SLP 1988: 1070-1080 BibTeX
[9]
Michael Gelfond, Vladimir Lifschitz: Classical Negation in Logic Programs and Disjunctive Databases. New Generation Comput. 9(3/4): 365-386(1991) BibTeX
[10]
...
[11]
Sergio Greco, Domenico Saccà, Carlo Zaniolo: The PushDown Method to Optimize Chain Logic Programs (Extended Abstract). ICALP 1995: 523-534 BibTeX
[12]
...
[13]
Laks V. S. Lakshmanan, Fereidoon Sadri: Probabilistic Deductive Databases. SLP 1994: 254-268 BibTeX
[14]
Nicola Leone, Pasquale Rullo, Francesco Scarcello: Disjunctive Stable Models: Unfounded Sets, Fixpoint Semantics, and Computation. Inf. Comput. 135(2): 69-112(1997) BibTeX
[15]
...
[16]
Jack Minker: On Indefinite Databases and the Closed World Assumption. CADE 1982: 292-308 BibTeX
[17]
Jeffrey F. Naughton, Raghu Ramakrishnan, Yehoshua Sagiv, Jeffrey D. Ullman: Argument Reduction by Factoring. VLDB 1989: 173-182 BibTeX
[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 BibTeX
[19]
Teodor C. Przymusinski: Stable Semantics for Disjunctive Programs. New Generation Comput. 9(3/4): 401-424(1991) BibTeX
[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) BibTeX
[21]
Jeffrey D. Ullman: Principles of Database and Knowledge-Base Systems, Volume II. Computer Science Press 1989, ISBN 0-7167-8162-X
Contents BibTeX
[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) BibTeX
BibTeX
ACM SIGMOD Anthology - DBLP: [Home | Search: Author, Title | Conferences | Journals]
VLDB Proceedings: Copyright © by VLDB Endowment,
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:46:21 2009