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

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

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 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML

References

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

Copyright © Tue Mar 16 02:22:07 2010 by Michael Ley (ley@uni-trier.de)