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

Sets and Negation in a Logic Database Language (LDL1).

Catriel Beeri, Shamim A. Naqvi, Raghu Ramakrishnan, Oded Shmueli, Shalom Tsur: Sets and Negation in a Logic Database Language (LDL1). PODS 1987: 21-37
@inproceedings{DBLP:conf/pods/BeeriNRST87,
  author    = {Catriel Beeri and
               Shamim A. Naqvi and
               Raghu Ramakrishnan and
               Oded Shmueli and
               Shalom Tsur},
  title     = {Sets and Negation in a Logic Database Language (LDL1)},
  booktitle = {Proceedings of the Sixth ACM SIGACT-SIGMOD-SIGART Symposium on
               Principles of Database Systems, March 23-25, 1987, San Diego,
               California},
  publisher = {ACM},
  year      = {1987},
  isbn      = {0-89791-223-3},
  pages     = {21-37},
  ee        = {http://doi.acm.org/10.1145/28659.28662, db/conf/pods/BeeriNRST87.html},
  crossref  = {DBLP:conf/pods/87},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}
BibTeX

Abstract

In this paper we extend LDL, a Logic Based Database Language, to include finite sets and negation. The new language is called LDLl. We define the notion of a model and show that a negtion-free program need not have a model, and that it may have more than one minimal model. We impose syntactic restrictions in order to define a deterministic language. These restrictios allow only layered (stratified) programs. We prove that for any program satisfying the syntactic restrictions of layering, there is a minimal model, and that this model can be constructed in a bottom-up fashion. Extensions to the basic grouping mechanism are proposed. We show that these extensions can be translated into equivalent LDLl programs. Finally,, we show how the technique of magic sets can be extended to translate LDLl progams into equivalent programs which can often be executed more efficiently.

Copyright © 1987 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 Sixth ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems, March 23-25, 1987, San Diego, California. ACM 1987, ISBN 0-89791-223-3
Contents BibTeX

Online Edition: ACM Digital Library

Journal Version

Catriel Beeri, Shamim A. Naqvi, Oded Shmueli, Shalom Tsur: Set Constructors in a Logic Database Language. J. Log. Program. 10(1/2/3&4): 181-232(1991) BibTeX

References

[ABW86]
...
[AE82]
Krzysztof R. Apt, Maarten H. van Emden: Contributions to the Theory of Logic Programming. J. ACM 29(3): 841-862(1982) BibTeX
[BMSU86]
François Bancilhon, David Maier, Yehoshua Sagiv, Jeffrey D. Ullman: Magic Sets and Other Strange Ways to Implement Logic Programs. PODS 1986: 1-15 BibTeX
[BR87]
Catriel Beeri, Raghu Ramakrishnan: On the Power of Magic. PODS 1987: 269-284 BibTeX
[CH85]
Ashok K. Chandra, David Harel: Horn Clauses Queries and Generalizations. J. Log. Program. 2(1): 1-15(1985) BibTeX
[CLAR78]
...
[FITT85]
Melvin Fitting: A Kripke-Kleene Semantics for Logic Programs. J. Log. Program. 2(4): 295-312(1985) BibTeX
[GELD86]
Allen Van Gelder: Negation as Failure using Tight Derivations for General Logic Programs. J. Log. Program. 6(1&2): 109-133(1989) BibTeX
[KE76]
Maarten H. van Emden, Robert A. Kowalski: The Semantics of Predicate Logic as a Programming Language. J. ACM 23(4): 733-742(1976) BibTeX
[KUPE86]
Gabriel M. Kuper: Logic Programming With Sets. PODS 1987: 11-20 BibTeX
[LLOY84]
John W. Lloyd: Foundations of Logic Programming, 1st Edition. Springer 1984, ISBN 3-540-13299-6
BibTeX
[NAQV86]
...
[TARS55]
...
[TZ85]
...
[TZ86]
Shalom Tsur, Carlo Zaniolo: LDL: A Logic-Based Data Language. VLDB 1986: 33-41 BibTeX
[ZANI85]
Carlo Zaniolo: The Representation and Deductive Retrieval of Complex Objects. VLDB 1985: 458-469 BibTeX
[SN86]
...
[ULLM86]
Jeffrey D. Ullman: Implementation of Logical Query Languages for Databases. ACM Trans. Database Syst. 10(3): 289-321(1985) BibTeX

Referenced by

  1. Serge Abiteboul, Sophie Cluet, Tova Milo: Correspondence and Translation for Heterogeneous Data. ICDT 1997: 351-363
  2. Serge Abiteboul, Catriel Beeri: The Power of Languages for the Manipulation of Complex Values. VLDB J. 4(4): 727-794(1995)
  3. Weidong Chen, Michael Kifer: Sorted HiLog: Sorts in Higher-Order Logic Data Languages. ICDT 1995: 252-265
  4. Serge Abiteboul, Richard Hull, Victor Vianu: Foundations of Databases. Addison-Wesley 1995, ISBN 0-201-53771-0
    Contents
  5. Raghu Ramakrishnan, Divesh Srivastava, S. Sudarshan: Rule Ordering in Bottom-Up Fixpoint Evaluation of Logic Programs. IEEE Trans. Knowl. Data Eng. 6(4): 501-517(1994)
  6. Xian Ye, Christine Parent, Stefano Spaccapietra: Cardinality Consistency of Derived Objects in DOOD Systems. ER 1994: 278-295
  7. Gabriel M. Kuper, Moshe Y. Vardi: The Logical Data Model. ACM Trans. Database Syst. 18(3): 379-413(1993)
  8. Jorng-Tzong Horng, Gwo-Dong Chen, Baw-Jhiune Liu: Query Processing Techniques in the Team-Oriented Database Query Language. DASFAA 1993: 245-252
  9. Jan Paredaens, Dirk Van Gucht: Converting Nested Algebra Expressions into Flat Algebra Expressions. ACM Trans. Database Syst. 17(1): 65-93(1992)
  10. Narain H. Gehani, H. V. Jagadish, Oded Shmueli: Composite Event Specification in Active Databases: Model & Implementation. VLDB 1992: 327-338
  11. Sergio Greco, Carlo Zaniolo: Optimization of Linear Logic Programs Using Counting Methods. EDBT 1992: 72-87
  12. Allen Van Gelder, Rodney W. Topor: Safety and Translation of Relational Calculus Queries. ACM Trans. Database Syst. 16(2): 235-278(1991)
  13. Serge Abiteboul, Stéphane Grumbach: A Rule-Based Language with Functions and Sets. ACM Trans. Database Syst. 16(1): 1-30(1991)
  14. S. Sudarshan, Raghu Ramakrishnan: Aggregation and Relevance in Deductive Databases. VLDB 1991: 501-511
  15. Yanjun Lou, Z. Meral Özsoyoglu: LLO: An Object-Oriented Deductive Language with Methods and Method Inheritance. SIGMOD Conference 1991: 198-207
  16. Qiming Chen, Yahiko Kambayashi: Nested Relation Based Database Knowledge Representation. SIGMOD Conference 1991: 328-337
  17. Stéphane Grumbach, Victor Vianu: Tractable Query Languages for Complex Object Databases. PODS 1991: 315-327
  18. Peter Sander: Specifying Operations for Nested Relations by Rules and Partial Orders. MFDBS 1991: 44-58
  19. Andreas Heuer, Peter Sander: Classifying Object-Oriented Query Results in a Class/Type Lattice. MFDBS 1991: 14-28
  20. Guozhu Dong: On the Monotonicity of (LDL) Logic Programs with Sets. MFDBS 1991: 201-215
  21. Val Tannen, Peter Buneman, Shamim A. Naqvi: Structural Recursion as a Query Language. DBPL 1991: 9-19
  22. Stéphane Grumbach, Victor Vianu: Expressiveness and Complexity of Restricted Languages for Complex Objects. DBPL 1991: 111-122
  23. Paolo Atzeni, Riccardo Torlone: Management of Multiple Models: A Metamodel for Conceptual Models. DBPL 1991: 169-181
  24. Burkhard Freitag, Heribert Schütz, Günther Specht: LOLA - A Logic Language for Deductive Databases and its Implementation. DASFAA 1991: 216-225
  25. Inderpal Singh Mumick, Hamid Pirahesh, Raghu Ramakrishnan: The Magic of Duplicates and Aggregates. VLDB 1990: 264-277
  26. Anthony J. Bonner, Tomasz Imielinski: The Reuse and Modification of Rulebases by Predicate Substituation. EDBT 1990: 437-451
  27. Catriel Beeri, Yoram Kornatzky: The Many Faces of Query Monotonicity. EDBT 1990: 120-135
  28. Stefano Ceri, Georg Gottlob, Letizia Tanca: What you Always Wanted to Know About Datalog (And Never Dared to Ask). IEEE Trans. Knowl. Data Eng. 1(1): 146-166(1989)
  29. Michael Kifer, Georg Lausen: F-Logic: A Higher-Order language for Reasoning about Objects, Inheritance, and Scheme. SIGMOD Conference 1989: 134-146
  30. Marc Gyssens, Jan Paredaens, Dirk Van Gucht: A Grammar-Based Approach Towards Unifying Hierarchical Data Models (Extended Abstract). SIGMOD Conference 1989: 263-272
  31. Serge Abiteboul, Paris C. Kanellakis: Object Identity as a Query Language Primitive. SIGMOD Conference 1989: 159-173
  32. Richard Hull, Jianwen Su: Untyped Sets, Invention, and Computable Queries. PODS 1989: 347-359
  33. Weidong Chen, David Scott Warren: C-Logic of Complex Objects. PODS 1989: 369-378
  34. Douglas Stott Parker Jr., Richard R. Muntz, H. Lewis Chau: The Tangram Stream Query Processing System. ICDE 1989: 556-563
  35. Richard Hull, Jianwen Su: On Bulk Data type Constructors and Manipulation Primitives: A Framework for Analyzing Power and Complexity. DBPL 1989: 396-410
  36. Weidong Chen, Michael Kifer, David Scott Warren: HiLog as a Platform for Database Languages. DBPL 1989: 315-329
  37. Serge Abiteboul, Stéphane Grumbach, Agnès Voisard, Emmanuel Waller: An Extensible Rule-Based Language with Complex Objects and data-Functions. DBPL 1989: 298-314
  38. Jeffrey D. Ullman: Principles of Database and Knowledge-Base Systems, Volume II. Computer Science Press 1989, ISBN 0-7167-8162-X
    Contents
  39. Christophe de Maindreville, Eric Simon: Modelling Non Deterministic Queries and Updates in Deductive Databases. VLDB 1988: 395-406
  40. Ravi Krishnamurthy, Shamim A. Naqvi: Towards a Real Horn Clause Language. VLDB 1988: 252-263
  41. Qiming Chen, Georges Gardarin: An Implementation Model for Reasoning with Complex Objects. SIGMOD Conference 1988: 164-172
  42. Serge Abiteboul, Richard Hull: Data Functions, Datalog and Negation (Extended Abstract). SIGMOD Conference 1988: 143-153
  43. Oded Shmueli, Shalom Tsur, Carlo Zaniolo: Rewriting of Rules Containing Set Terms in a Logic Data Model (LDL). PODS 1988: 15-28
  44. Jan Paredaens, Dirk Van Gucht: Possibilities and Limitations of Using Flat Operators in Nested Algebra Expressions. PODS 1988: 29-38
  45. Shamim A. Naqvi, Ravi Krishnamurthy: Database Updates in Logic Programming. PODS 1988: 251-262
  46. Gabriel M. Kuper: On the Expressive Power of Logic Programming Languages with Sets. PODS 1988: 10-14
  47. Richard Hull, Jianwen Su: On the Expressive Power of Database Queries with Intermediate Types. PODS 1988: 39-51
  48. Ashok K. Chandra: Theory of Database Queries. PODS 1988: 1-9
  49. Catriel Beeri: Data Models and Languages for Databases. ICDT 1988: 19-40
  50. Ravi Krishnamurthy, Carlo Zaniolo: Optimization in a Logic Based Language for Knowledge and Data Intensive Applications. EDBT 1988: 16-33
  51. Serge Abiteboul, Stéphane Grumbach: COL: A Logic-Based Language for Complex Objects. EDBT 1988: 271-293
  52. Gabriel M. Kuper: Logic Programming With Sets. PODS 1987: 11-20
  53. Catriel Beeri, Raghu Ramakrishnan: On the Power of Magic. PODS 1987: 269-284
  54. Shamim A. Naqvi, Ravi Krishnamurthy: Semantics of Updates in Logic Programming. DBPL 1987: 313-327
  55. Serge Abiteboul, Stéphane Grumbach: COL: A Logic-Based Language for Complex Objects. DBPL 1987: 347-374
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:50 2009