Relational Specifications of Infinite Query Answers.

Jan Chomicki, Tomasz Imielinski: Relational Specifications of Infinite Query Answers. SIGMOD Conference 1989: 174-183
  author    = {Jan Chomicki and
               Tomasz Imielinski},
  editor    = {James Clifford and
               Bruce G. Lindsay and
               David Maier},
  title     = {Relational Specifications of Infinite Query Answers},
  booktitle = {Proceedings of the 1989 ACM SIGMOD International Conference on
               Management of Data, Portland, Oregon, May 31 - June 2, 1989},
  publisher = {ACM Press},
  year      = {1989},
  pages     = {174-183},
  ee        = {, db/conf/sigmod/ChomickiI89.html},
  crossref  = {DBLP:conf/sigmod/89},
  bibsource = {DBLP,}


We investigate here functional deductive databases: an extension of DATALOG capable of representing infinite phenomena. Rules in functional deductive databases are Horn and predicates can have arbitrary unary and limited k-ary function symbols in one fixed position. This class is known to be decidable. However, least fixpoints of functional rules may be infinite. We present here a method to finitely represent infinite least fixpoints and infinite query answers as relational specifications. Relational specifications consist of a finite set of tuples and of a finitely specified congruence relation. Our method is applicable to every domain-independent set of functional rules.

Copyright © 1989 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

James Clifford, Bruce G. Lindsay, David Maier (Eds.): Proceedings of the 1989 ACM SIGMOD International Conference on Management of Data, Portland, Oregon, May 31 - June 2, 1989. ACM Press 1989 BibTeX , SIGMOD Record 18(2), June 1989

Online Edition: ACM Digital Library

Journal Version

Jan Chomicki, Tomasz Imielinski: Finite Representation of Infinite Query Answers. ACM Trans. Database Syst. 18(2): 181-223(1993) BibTeX


Laurence Cholvy, Robert Demolombe: Querying a Rule Base. Expert Database Conf. 1986: 477-485 BibTeX
Ashok K. Chandra, David Harel: Structure and Complexity of Relational Queries. J. Comput. Syst. Sci. 25(1): 99-128(1982) BibTeX
Ashok K. Chandra, David Harel: Horn Clauses Queries and Generalizations. J. Log. Program. 2(1): 1-15(1985) BibTeX
Jan Chomicki, Tomasz Imielinski: Temporal Deductive Databases and Infinite Objects. PODS 1988: 61-73 BibTeX
Francisco Corella: Semantic Retrieval and Levels of Abstraction. Expert Database Workshop 1984: 91-114 BibTeX
Peter J. Downey, Ravi Sethi, Robert Endre Tarjan: Variations on the Common Subexpression Problem. J. ACM 27(4): 758-771(1980) BibTeX
Hervé Gallaire, Jack Minker, Jean-Marie Nicolas: Logic and Databases: A Deductive Approach. ACM Comput. Surv. 16(2): 153-185(1984) BibTeX
Tomasz Imielinski: Domain Abstraction and Limited Reasoning. IJCAI 1987: 997-1003 BibTeX
Tomasz Imielinski: Intelligent Query Answering in Rule Based Systems. J. Log. Program. 4(3): 229-257(1987) BibTeX
Michael Kifer: On Safety, Domain Independence, and Capturability of Database Queries (Preliminary Report). JCDKB 1988: 405-415 BibTeX
John W. Lloyd: Foundations of Logic Programming, 2nd Edition. Springer 1987, ISBN 3-540-18199-7
David A. Plaisted: Complete Problems in the First-Order Predicate Calculus. J. Comput. Syst. Sci. 29(1): 8-35(1984) BibTeX
Raghu Ramakrishnan, François Bancilhon, Abraham Silberschatz: Safety of Recursive Horn Clauses With Infinite Relations. PODS 1987: 328-339 BibTeX
Chung-Dak Shum, Richard R. Muntz: Implicit Representation for Extensional Answers. Expert Database Conf. 1988: 497-522 BibTeX
Jeffrey D. Ullman: Principles of Database and Knowledge-Base Systems, Volume I. Computer Science Press 1988, ISBN 0-7167-8158-1
Contents BibTeX
Maarten H. van Emden, Robert A. Kowalski: The Semantics of Predicate Logic as a Programming Language. J. ACM 23(4): 733-742(1976) BibTeX

Referenced by

  1. Gultekin Özsoyoglu, Richard T. Snodgrass: Temporal and Real-Time Databases: A Survey. IEEE Trans. Knowl. Data Eng. 7(4): 513-532(1995)
  2. Paris C. Kanellakis: Constraint Programming and Database Languages: A Tutorial. PODS 1995: 46-53
  3. Jan Chomicki, Tomasz Imielinski: Finite Representation of Infinite Query Answers. ACM Trans. Database Syst. 18(2): 181-223(1993)
  4. Alexander Brodsky, Joxan Jaffar, Michael J. Maher: Toward Practical Constraint Databases. VLDB 1993: 567-580
  5. Marianne Baudinet, Marc Niézette, Pierre Wolper: On the Representation of Infinite Temporal Data and Queries. PODS 1991: 280-290
  6. Paris C. Kanellakis, Gabriel M. Kuper, Peter Z. Revesz: Constraint Query Languages. PODS 1990: 299-313
  7. Jan Chomicki: Polynomial Time Query Processing in Temporal Deductive Databases. PODS 1990: 379-391
  8. Peter Z. Revesz: A Closed Form for Datalog Queries with Integer Order. ICDT 1990: 187-201
  9. Anthony J. Bonner, Tomasz Imielinski: The Reuse and Modification of Rulebases by Predicate Substituation. EDBT 1990: 437-451
ACM SIGMOD Anthology - DBLP: [Home | Search: Author, Title | Conferences | Journals]
ACM SIGMOD Anthology: Copyright © by ACM (, Corrections:
DBLP: Copyright © by Michael Ley (, last change: Sat May 16 23:39:57 2009