dblp.uni-trier.de www.dagstuhl.de www.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},
  crossref  = {DBLP:conf/sigmod/90},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}

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

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

Last update Tue Sep 18 00:25:04 2012 CET by the DBLP TeamThis material is Open Data Data released under the ODC-BY 1.0 license — See also our legal information page