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

IDLOG: Extending the Expressive Power of Deductive Database Languages.

Yeh-Heng Sheng: IDLOG: Extending the Expressive Power of Deductive Database Languages. SIGMOD Conference 1990: 54-63
@inproceedings{DBLP:conf/sigmod/Sheng90,
  author    = {Yeh-Heng Sheng},
  editor    = {Hector Garcia-Molina and
               H. V. Jagadish},
  title     = {IDLOG: Extending the Expressive Power of Deductive Database Languages},
  booktitle = {Proceedings of the 1990 ACM SIGMOD International Conference on
               Management of Data, Atlantic City, NJ, May 23-25, 1990},
  publisher = {ACM Press},
  year      = {1990},
  pages     = {54-63},
  ee        = {http://doi.acm.org/10.1145/93597.93621, db/conf/sigmod/Sheng90.html},
  crossref  = {DBLP:conf/sigmod/90},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}
BibTeX

Abstract

The expressive power of pure deductive database languages, such as DATALOG and stratified DATALOG¬, is limited in a sense that some useful queries such as functions involving aggregation are not definable in these languages. Our concern in this paper is to provide a uniform logic framework for deductive databases with greater expressive power. It has been shown that with a linear ordering on the domain of the database, the expressive power of some database languages can be enhanced so that some functions involving aggregation can be defined. Yet, a direct implementation of the linear ordering in deductive database languages may seem unintuitive, and may not be very efficient to use in practice. We propose a logic for deductive databases which employs the notion of "identifying each tuple in a relation". Through the use of these tuple-identifications, different linear orderings are defined as a result. This intuitively explains the reason why our logic has greater expressive power. The proposed logic language is non-deterministic in nature. However, non-determinism is not the real reason for the enhanced expressive power. A deterministic subset of the programs in this language is computational complete in the sense that it defines all the computable deterministic queries. Although the problem of deciding whether a program is in this subset is in general undecidable, we do provide a rather general sufficient test for identifying such programs. Also discussed in this paper is an extended notion of queries which allows both the input and the output of a query to contain interpreted constants of an infinite domain. We show that extended queries involving aggregation can also be defined in the language.

Copyright © 1990 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.

ACM SIGMOD Anthology

Online Version (ACM WWW Account required): Full Text in PDF Format

CDROM Version: Load the CDROM "Volume 1 Issue 2, SIGMOD '75-'92" and ...

DVD Version: Load ACM SIGMOD Anthology DVD 1" and ... BibTeX

Printed Edition

Hector Garcia-Molina, H. V. Jagadish (Eds.): Proceedings of the 1990 ACM SIGMOD International Conference on Management of Data, Atlantic City, NJ, May 23-25, 1990. ACM Press 1990 BibTeX , SIGMOD Record 19(2), June 1990
Contents

Online Edition: ACM Digital Library

References

[AB88]
Serge Abiteboul, Catriel Beeri: The Power of Languages for the Manipulation of Complex Values. VLDB J. 4(4): 727-794(1995) BibTeX
[ABW88]
...
[AV87]
Serge Abiteboul, Victor Vianu: A Transcation Language Complete for Database Update and Specification. PODS 1987: 260-268 BibTeX
[AV88]
Serge Abiteboul, Victor Vianu: Procedural and Declarative Database Update Languages. PODS 1988: 240-250 BibTeX
[BR86]
François Bancilhon, Raghu Ramakrishnan: An Amateur's Introduction to Recursive Query Processing Strategies. SIGMOD Conference 1986: 16-52 BibTeX
[Ce76]
...
[CH80]
Ashok K. Chandra, David Harel: Computable Queries for Relational Data Bases. J. Comput. Syst. Sci. 21(2): 156-178(1980) BibTeX
[CH82]
Ashok K. Chandra, David Harel: Structure and Complexity of Relational Queries. J. Comput. Syst. Sci. 25(1): 99-128(1982) BibTeX
[CH85]
Ashok K. Chandra, David Harel: Horn Clauses Queries and Generalizations. J. Log. Program. 2(1): 1-15(1985) BibTeX
[Cha81]
Ashok K. Chandra: Programming Primitives for Database Languages. POPL 1981: 50-62 BibTeX
[Cha88]
Ashok K. Chandra: Theory of Database Queries. PODS 1988: 1-9 BibTeX
[Che88]
...
[Dah87]
...
[GL88]
Michael Gelfond, Vladimir Lifschitz: The Stable Model Semantics for Logic Programming. ICLP/SLP 1988: 1070-1080 BibTeX
[HS89]
Richard Hull, Jianwen Su: Untyped Sets, Invention, and Computable Queries. PODS 1989: 347-359 BibTeX
[Imm86]
Neil Immerman: Relational Queries Computable in Polynomial Time. Information and Control 68(1-3): 86-104(1986) BibTeX
[KL85]
...
[KL86]
...
[Klu82]
Anthony C. Klug: Equivalence of Relational Algebra and Relational Calculus Query Languages Having Aggregate Functions. J. ACM 29(3): 699-717(1982) BibTeX
[KP88]
Phokion G. Kolaitis, Christos H. Papadimitriou: Why Not Negation by Fixpoint? PODS 1988: 231-239 BibTeX
[OOM87]
Gultekin Özsoyoglu, Z. Meral Özsoyoglu, Victor Matos: Extending Relational Algebra and Relational Calculus with Set-Valued Attributes and Aggregate Functions. ACM Trans. Database Syst. 12(4): 566-592(1987) BibTeX
[Prz88a]
Teodor C. Przymusinski: On the Declarative and Procedural Semantics of Logic Programs. J. Autom. Reasoning 5(2): 167-205(1989) BibTeX
[Prz88b]
...
[RBK88]
Raghu Ramakrishnan, Catriel Beeri, Ravi Krishnamurthy: Optimizing Existential Datalog Queries. PODS 1988: 89-102 BibTeX
[Rei83]
...
[Saz80]
...
[She90]
...
[Ull82]
Jeffrey D. Ullman: Principles of Database Systems, 2nd Edition. Computer Science Press 1982, ISBN 0-914894-36-6
BibTeX
[Var82]
Moshe Y. Vardi: The Complexity of Relational Query Languages (Extended Abstract). STOC 1982: 137-146 BibTeX
[VG88]
...
[VGRS88]
...
[Zan86]
Carlo Zaniolo: Safety and Compilation of Non-recursive Horn Clauses. Expert Database Conf. 1986: 237-252 BibTeX

Referenced by

  1. Jan Paredaens, Peter Peelman, Letizia Tanca: G-Log: A Graph-Based Query Language. IEEE Trans. Knowl. Data Eng. 7(3): 436-453(1995)
  2. Yeh-Heng Sheng: A Non-deterministic Deductive Database Language. SIGMOD Conference 1991: 188-197
  3. Filippo Cacace, Stefano Ceri, Letizia Tanca: Consistency and Non-determinism in a Database Programming Language. MFDBS 1991: 325-341
  4. Richard Hull, Masatoshi Yoshikawa: ILOG: Declarative Creation and Manipulation of Object Identifiers. VLDB 1990: 455-468
  5. Mariano P. Consens, Alberto O. Mendelzon: Low Complexity Aggregation in GraphLog and Datalog. ICDT 1990: 379-394
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:40:00 2009