Rewriting of Rules Containing Set Terms in a Logic Data Model (LDL).
Oded Shmueli, Shalom Tsur, Carlo Zaniolo:
Rewriting of Rules Containing Set Terms in a Logic Data Model (LDL).
PODS 1988: 15-28@inproceedings{DBLP:conf/pods/ShmueliTZ88,
author = {Oded Shmueli and
Shalom Tsur and
Carlo Zaniolo},
title = {Rewriting of Rules Containing Set Terms in a Logic Data Model
(LDL)},
booktitle = {Proceedings of the Seventh ACM SIGACT-SIGMOD-SIGART Symposium
on Principles of Database Systems, March 21-23, 1988, Austin,
Texas},
publisher = {ACM},
year = {1988},
isbn = {0-89791-263-2},
pages = {15-28},
ee = {http://doi.acm.org/10.1145/308386.308400, db/conf/pods/ShmueliTZ88.html},
crossref = {DBLP:conf/pods/88},
bibsource = {DBLP, http://dblp.uni-trier.de}
}
Abstract
We propose compilation methods for supporting set terms in Horn clause programs, without using general-purpose set matching algorithms, which tend to run in times exponential in the size of the participating sets. Instead, we take the approach of formulating specialized computation plans that, by taking advantage of information available in the given rules, limit the number of alternatives explored. Our strategy is to employ compile time rewriting techniques and to transform the problem into an "ordinary" Horn clause compilation problem, with minimal additional overhead. The execution cost of the rewritten rules is substantially lower than that of the original rules and the additional cost of compilation can thus be amortized over many executions.
Copyright © 1988 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 ...
Printed Edition
Proceedings of the Seventh ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems, March 21-23, 1988, Austin, Texas.
ACM 1988, ISBN 0-89791-263-2
Contents 
Journal Version
Oded Shmueli, Shalom Tsur, Carlo Zaniolo:
Compilation of Set Terms in the Logic Data Language (LDL).
J. Log. Program. 12(1&2): 89-119(1992)
References
- [AB87]
- Serge Abiteboul, Catriel Beeri:
The Power of Languages for the Manipulation of Complex Values.
VLDB J. 4(4): 727-794(1995)
- [ASU79]
- Alfred V. Aho, Yehoshua Sagiv, Jeffrey D. Ullman:
Equivalences Among Relational Expressions.
SIAM J. Comput. 8(2): 218-246(1979)
- [BNRST87]
- Catriel Beeri, Shamim A. Naqvi, Raghu Ramakrishnan, Oded Shmueli, Shalom Tsur:
Sets and Negation in a Logic Database Language (LDL1).
PODS 1987: 21-37
- [CM84]
- ...
- [FAGES87]
- François Fages:
Associative-Commutative Unification.
J. Symb. Comput. 3(3): 257-275(1987)
- [KN86]
- Deepak Kapur, Paliath Narendran:
NP-Completeness of the Set Unification and Matching Problems.
CADE 1986: 489-495
- [KRS84]
- ...
- [KV84]
- Gabriel M. Kuper, Moshe Y. Vardi:
A New Approach to Database Logic.
PODS 1984: 86-96
- [LC87]
- Patrick Lincoln, Jim Christian:
Adventures in Associative-Commutative Unification.
J. Symb. Comput. 8(1/2): 217-240(1989)
- [LLOY84]
- John W. Lloyd:
Foundations of Logic Programming, 1st Edition.
Springer 1984, ISBN 3-540-13299-6
- [LS76]
- ...
- [OO83]
- ...
- [RS79]
- ...
- [STZ87]
- Oded Shmueli, Shalom Tsur, Carlo Zaniolo:
Compilation of Set Terms in the Logic Data Language (LDL).
J. Log. Program. 12(1&2): 89-119(1992)
- [STICK81]
- Mark E. Stickel:
A Unification Algorithm for Associative-Commutative Functions.
J. ACM 28(3): 423-434(1981)
- [SZ87]
- Domenico Saccà, Carlo Zaniolo:
Implementation of Recursive Queries for a Data Language Based on Pure Horn Logic.
ICLP 1987: 104-135
- [TZ86]
- Shalom Tsur, Carlo Zaniolo:
LDL: A Logic-Based Data Language.
VLDB 1986: 33-41
Copyright © Mon Mar 15 03:51:33 2010
by Michael Ley (ley@uni-trier.de)
