 |
|
|
Binding Propagation in Disjunctive Databases |
Full Paper (PDF)
|
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.
|
References, where available, link to the DBLP on the World Wide Web.
[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-16[3]Catriel Beeri, Raghu Ramakrishnan:
On the Power of Magic.
PODS 1987: 269-283[4]...
[5]Thomas Eiter, Georg Gottlob, Heikki Mannila:
Disjunctive Datalog.
TODS 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 Computing 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.
Information and Computation 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 Computing 9(3/4): 401-424(1991)[20]Raghu Ramakrishnan, Yehoshua Sagiv, Jeffrey D. Ullman, Moshe Y. Vardi:
Logical Query Optimization by Proff-Tree Transformation.
JCSS 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
[22]Allen Van Gelder, Kenneth A. Ross, John S. Schlipf:
The Well-Founded Semantics for General Logic Programs.
JACM 38(3): 620-650(1991)
|
@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},
crossref = {DBLP:conf/vldb/98},
bibsource = {DBLP, http://dblp.uni-trier.de}
}
|
DBLP: Copyright ©1999 by Michael Ley (ley@uni-trier.de).
|
|
