ACM SIGMOD Anthology ACM SIGMOD dblp.uni-trier.de

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

Online Edition: ACM Digital Library

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

References

[AB87]
Serge Abiteboul, Catriel Beeri: The Power of Languages for the Manipulation of Complex Values. VLDB J. 4(4): 727-794(1995) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[ASU79]
Alfred V. Aho, Yehoshua Sagiv, Jeffrey D. Ullman: Equivalences Among Relational Expressions. SIAM J. Comput. 8(2): 218-246(1979) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[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 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[CM84]
...
[FAGES87]
François Fages: Associative-Commutative Unification. J. Symb. Comput. 3(3): 257-275(1987) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[KN86]
Deepak Kapur, Paliath Narendran: NP-Completeness of the Set Unification and Matching Problems. CADE 1986: 489-495 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[KRS84]
...
[KV84]
Gabriel M. Kuper, Moshe Y. Vardi: A New Approach to Database Logic. PODS 1984: 86-96 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[LC87]
Patrick Lincoln, Jim Christian: Adventures in Associative-Commutative Unification. J. Symb. Comput. 8(1/2): 217-240(1989) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[LLOY84]
John W. Lloyd: Foundations of Logic Programming, 1st Edition. Springer 1984, ISBN 3-540-13299-6
CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[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) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[STICK81]
Mark E. Stickel: A Unification Algorithm for Associative-Commutative Functions. J. ACM 28(3): 423-434(1981) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[SZ87]
Domenico Saccà, Carlo Zaniolo: Implementation of Recursive Queries for a Data Language Based on Pure Horn Logic. ICLP 1987: 104-135 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[TZ86]
Shalom Tsur, Carlo Zaniolo: LDL: A Logic-Based Data Language. VLDB 1986: 33-41 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML

Copyright © Mon Mar 15 03:51:33 2010 by Michael Ley (ley@uni-trier.de)