Finite Representation of Infinite Query Answers.

Jan Chomicki, Tomasz Imielinski: Finite Representation of Infinite Query Answers. ACM Trans. Database Syst. 18(2): 181-223(1993)
  author    = {Jan Chomicki and
               Tomasz Imielinski},
  title     = {Finite Representation of Infinite Query Answers},
  journal   = {ACM Trans. Database Syst.},
  volume    = {18},
  number    = {2},
  year      = {1993},
  pages     = {181-223},
  ee        = {, db/journals/tods/ChomickiI93.html},
  bibsource = {DBLP,}


We define here a formal notion of finite representation of infinite query answers in logic programs. We apply this notion to DatalognS programs may be infinite and consequently queries may have infinite answers.

We present a method to finitely represent infinite least Herbrand models of DatalognS program (and its underlying computational engine) can be forgotten. Given a query to be evaluated, it is easy to obtain from the relational specification finitely many answer substitutions that represent infinitely many answer substitutions to the query. The method involved is a combination of a simple, unificationless, computational mechanism (graph traversal, congruence closure, or term rewriting) and standard relational query evaluation methods. Second, a relational specification is effectively computable and its computation is no harder, in the sense of the complexity class, than answering yes-no queries.

Our method is applicable to every range-restricted DatalognS program. We also show that for some very simple non-DatalognS logic programs, finite representations of query answers do not exist.

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

Joint ACM SIGMOD / IEEE Computer Society Anthology

CDROM Version: Load the CDROM "Volume 3 Issue 2, TODS 1991-1995, TKDE 1989-1992" and ... DVD Version: Load ACM SIGMOD Anthology DVD 2" and ... BibTeX

Online Edition: ACM Digital Library

[Abstract and Index Terms]
[Full Text in PDF Format, 2741 KB]

Conference Version

Jan Chomicki, Tomasz Imielinski: Relational Specifications of Infinite Query Answers. SIGMOD Conference 1989: 174-183 BibTeX


Martín Abadi, Zohar Manna: Temporal Logic Programming. J. Symb. Comput. 8(3): 277-295(1989) BibTeX
Marianne Baudinet: Temporal Logic Programming is Complete and Expressive. POPL 1989: 267-280 BibTeX
Marianne Baudinet: On the Expressiveness of Temporal Logic Programming. Inf. Comput. 117(2): 157-180(1995) BibTeX
Marc Bezem: Characterizing Termination of Logic Programs with Level Mappings. NACLP 1989: 69-80 BibTeX
Marianne Baudinet, Marc Niézette, Pierre Wolper: On the Representation of Infinite Temporal Data and Queries. PODS 1991: 280-290 BibTeX
François Bancilhon, Raghu Ramakrishnan: An Amateur's Introduction to Recursive Query Processing Strategies. SIGMOD Conference 1986: 16-52 BibTeX
Laurence Cholvy, Robert Demolombe: Querying a Rule Base. Expert Database Conf. 1986: 477-485 BibTeX
Ashok K. Chandra, David Harel: Computable Queries for Relational Data Bases. J. Comput. Syst. Sci. 21(2): 156-178(1980) BibTeX
Ashok K. Chandra, David Harel: Horn Clauses Queries and Generalizations. J. Log. Program. 2(1): 1-15(1985) BibTeX
Hong Chen, Jieh Hsiang: Logic Programming with Recurrence Domains. ICALP 1991: 20-34 BibTeX
Jan Chomicki: Polynomial Time Query Processing in Temporal Deductive Databases. PODS 1990: 379-391 BibTeX
Jan Chomicki, Tomasz Imielinski: Temporal Deductive Databases and Infinite Objects. PODS 1988: 61-73 BibTeX
Jan Chomicki, Tomasz Imielinski: Relational Specifications of Infinite Query Answers. SIGMOD Conference 1989: 174-183 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
Thom W. Frühwirth, Ehud Y. Shapiro, Moshe Y. Vardi, Eyal Yardeni: Logic Programs as Types for Logic Programs. LICS 1991: 300-309 BibTeX
Nevin Heintze, Joxan Jaffar: A Decision Procedure for a Class of Set Constraints (Extended Abstract). LICS 1990: 42-51 BibTeX
Nevin Heintze, Joxan Jaffar: A Finite Presentation Theorem for Approximating Logic Programs. POPL 1990: 197-209 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
Joxan Jaffar, Jean-Louis Lassez: Constraint Logic Programming. POPL 1987: 111-119 BibTeX
Paris C. Kanellakis, Gabriel M. Kuper, Peter Z. Revesz: Constraint Query Languages. PODS 1990: 299-313 BibTeX
Dexter Kozen: Complexity of Finitely Presented Algebras. STOC 1977: 164-177 BibTeX
Paris C. Kanellakis, Peter Z. Revesz: On the Relationship of Congruence Closure and Unification. DBPL 1987: 23-41 BibTeX
Froduald Kabanza, Jean-Marc Stévenne, Pierre Wolper: Handling Infinite Temporal Data. PODS 1990: 392-403 BibTeX
John W. Lloyd: Foundations of Logic Programming, 2nd Edition. Springer 1987, ISBN 3-540-18199-7
Johann A. Makowsky: Why Horn Formulas Matter in Computer Science: Initial Structures and Generic Examples (Extended Abstract). TAPSOFT, Vol.1 1985: 374-387 BibTeX
Greg Nelson, Derek C. Oppen: Fast Decision Procedures Based on Congruence Closure. J. ACM 27(2): 356-364(1980) BibTeX
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
Peter Z. Revesz: A Closed Form for Datalog Queries with Integer Order. ICDT 1990: 187-201 BibTeX
John C. Shepherdson: Negation in Logic Programming. Foundations of Deductive Databases and Logic Programming. 1988: 19-88 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
Jeffrey D. Ullman: Principles of Database and Knowledge-Base Systems, Volume II. Computer Science Press 1989, ISBN 0-7167-8162-X
Contents BibTeX
Moshe Y. Vardi: The Complexity of Relational Query Languages (Extended Abstract). STOC 1982: 137-146 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
Mitchell Wand: Final Algebra Semantics and Data Type Extensions. J. Comput. Syst. Sci. 19(1): 27-44(1979) BibTeX

Referenced by

  1. Vitaliy L. Khizder, David Toman, Grant E. Weddell: On Decidability and Complexity of Description Logics with Uniqueness Constraints. ICDT 2001: 54-67
  2. Cyril Decleir, Mohand-Said Hacid, Jacques Kouloumdjian: A Database Approach for Modeling and Querying Video Data. ICDE 1999: 6-13
  3. Peter Z. Revesz: Safe Query Languages for Constraint Databases. ACM Trans. Database Syst. 23(1): 58-99(1998)
  4. Paolo Terenziani: Integrating Calendar Dates and Qualitative Temporal Constraints in the Treatment of Periodic Events. IEEE Trans. Knowl. Data Eng. 9(5): 763-783(1997)
  5. Peter Z. Revesz: Datalog Queries of Set Constraint Databases. ICDT 1995: 425-438
  6. Marianne Baudinet, Jan Chomicki, Pierre Wolper: Constraint-Generating Dependencies. ICDT 1995: 322-337
  7. Marianne Baudinet, Marc Niézette, Pierre Wolper: On the Representation of Infinite Temporal Data and Queries. PODS 1991: 280-290
ACM SIGMOD Anthology - DBLP: [Home | Search: Author, Title | Conferences | Journals]
TODS, ACM SIGMOD Anthology: Copyright © by ACM (, Corrections:
DBLP: Copyright © by Michael Ley (, last change: Tue Jun 24 18:39:14 2008