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

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

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 BibTeX

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

References

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

Referenced by

  1. Colin Bell, Anil Nerode, Raymond T. Ng, V. S. Subrahmanian: Implementing Deductive Databases by Mixed Integer Programming. ACM Trans. Database Syst. 21(2): 238-269(1996)
  2. Colin Bell, Anil Nerode, Raymond T. Ng, V. S. Subrahmanian: Implementing Deductive Databases by Linear Programming. PODS 1992: 283-292
  3. Guozhu Dong: On the Monotonicity of (LDL) Logic Programs with Sets. MFDBS 1991: 201-215
  4. Danette Chimenti, Ruben Gamboa, Ravi Krishnamurthy, Shamim A. Naqvi, Shalom Tsur, Carlo Zaniolo: The LDL System Prototype. IEEE Trans. Knowl. Data Eng. 2(1): 76-90(1990)
  5. Carlo Zaniolo: Deductive Databases - Theory Meets Practice. EDBT 1990: 1-15
  6. Michael Kifer, James Wu: A Logic for Object-Oriented Logic Programming (Maier's O-Logic Revisited). PODS 1989: 379-393
  7. Ravi Krishnamurthy, Shamim A. Naqvi: Towards a Real Horn Clause Language. VLDB 1988: 252-263
BibTeX
ACM SIGMOD Anthology - DBLP: [Home | Search: Author, Title | Conferences | Journals]
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:33:53 2009