ACM SIGMOD Anthology TODS dblp.uni-trier.de

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)
@article{DBLP:journals/tods/ChomickiI93,
  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        = {http://doi.acm.org/10.1145/151634.151635, db/journals/tods/ChomickiI93.html},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}
BibTeX

Abstract

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

References

[1]
...
[2]
Martín Abadi, Zohar Manna: Temporal Logic Programming. J. Symb. Comput. 8(3): 277-295(1989) BibTeX
[3]
Marianne Baudinet: Temporal Logic Programming is Complete and Expressive. POPL 1989: 267-280 BibTeX
[4]
Marianne Baudinet: On the Expressiveness of Temporal Logic Programming. Inf. Comput. 117(2): 157-180(1995) BibTeX
[5]
Marc Bezem: Characterizing Termination of Logic Programs with Level Mappings. NACLP 1989: 69-80 BibTeX
[6]
...
[7]
Marianne Baudinet, Marc Niézette, Pierre Wolper: On the Representation of Infinite Temporal Data and Queries. PODS 1991: 280-290 BibTeX
[8]
François Bancilhon, Raghu Ramakrishnan: An Amateur's Introduction to Recursive Query Processing Strategies. SIGMOD Conference 1986: 16-52 BibTeX
[9]
Laurence Cholvy, Robert Demolombe: Querying a Rule Base. Expert Database Conf. 1986: 477-485 BibTeX
[10]
Ashok K. Chandra, David Harel: Computable Queries for Relational Data Bases. J. Comput. Syst. Sci. 21(2): 156-178(1980) BibTeX
[11]
Ashok K. Chandra, David Harel: Horn Clauses Queries and Generalizations. J. Log. Program. 2(1): 1-15(1985) BibTeX
[12]
Hong Chen, Jieh Hsiang: Logic Programming with Recurrence Domains. ICALP 1991: 20-34 BibTeX
[13]
...
[14]
...
[15]
Jan Chomicki: Polynomial Time Query Processing in Temporal Deductive Databases. PODS 1990: 379-391 BibTeX
[16]
Jan Chomicki, Tomasz Imielinski: Temporal Deductive Databases and Infinite Objects. PODS 1988: 61-73 BibTeX
[17]
Jan Chomicki, Tomasz Imielinski: Relational Specifications of Infinite Query Answers. SIGMOD Conference 1989: 174-183 BibTeX
[18]
Francisco Corella: Semantic Retrieval and Levels of Abstraction. Expert Database Workshop 1984: 91-114 BibTeX
[19]
Peter J. Downey, Ravi Sethi, Robert Endre Tarjan: Variations on the Common Subexpression Problem. J. ACM 27(4): 758-771(1980) BibTeX
[20]
...
[21]
Thom W. Frühwirth, Ehud Y. Shapiro, Moshe Y. Vardi, Eyal Yardeni: Logic Programs as Types for Logic Programs. LICS 1991: 300-309 BibTeX
[22]
...
[23]
...
[24]
...
[25]
Nevin Heintze, Joxan Jaffar: A Decision Procedure for a Class of Set Constraints (Extended Abstract). LICS 1990: 42-51 BibTeX
[26]
Nevin Heintze, Joxan Jaffar: A Finite Presentation Theorem for Approximating Logic Programs. POPL 1990: 197-209 BibTeX
[27]
Tomasz Imielinski: Domain Abstraction and Limited Reasoning. IJCAI 1987: 997-1003 BibTeX
[28]
Tomasz Imielinski: Intelligent Query Answering in Rule Based Systems. J. Log. Program. 4(3): 229-257(1987) BibTeX
[29]
Joxan Jaffar, Jean-Louis Lassez: Constraint Logic Programming. POPL 1987: 111-119 BibTeX
[30]
Paris C. Kanellakis, Gabriel M. Kuper, Peter Z. Revesz: Constraint Query Languages. PODS 1990: 299-313 BibTeX
[31]
Dexter Kozen: Complexity of Finitely Presented Algebras. STOC 1977: 164-177 BibTeX
[32]
Paris C. Kanellakis, Peter Z. Revesz: On the Relationship of Congruence Closure and Unification. DBPL 1987: 23-41 BibTeX
[33]
Froduald Kabanza, Jean-Marc Stévenne, Pierre Wolper: Handling Infinite Temporal Data. PODS 1990: 392-403 BibTeX
[34]
John W. Lloyd: Foundations of Logic Programming, 2nd Edition. Springer 1987, ISBN 3-540-18199-7
BibTeX
[35]
Johann A. Makowsky: Why Horn Formulas Matter in Computer Science: Initial Structures and Generic Examples (Extended Abstract). TAPSOFT, Vol.1 1985: 374-387 BibTeX
[36]
...
[37]
Greg Nelson, Derek C. Oppen: Fast Decision Procedures Based on Congruence Closure. J. ACM 27(2): 356-364(1980) BibTeX
[38]
...
[39]
David A. Plaisted: Complete Problems in the First-Order Predicate Calculus. J. Comput. Syst. Sci. 29(1): 8-35(1984) BibTeX
[40]
Raghu Ramakrishnan, François Bancilhon, Abraham Silberschatz: Safety of Recursive Horn Clauses With Infinite Relations. PODS 1987: 328-339 BibTeX
[41]
Peter Z. Revesz: A Closed Form for Datalog Queries with Integer Order. ICDT 1990: 187-201 BibTeX
[42]
John C. Shepherdson: Negation in Logic Programming. Foundations of Deductive Databases and Logic Programming. 1988: 19-88 BibTeX
[43]
Chung-Dak Shum, Richard R. Muntz: Implicit Representation for Extensional Answers. Expert Database Conf. 1988: 497-522 BibTeX
[44]
...
[45]
...
[46]
Jeffrey D. Ullman: Principles of Database and Knowledge-Base Systems, Volume I. Computer Science Press 1988, ISBN 0-7167-8158-1
Contents BibTeX
[47]
Jeffrey D. Ullman: Principles of Database and Knowledge-Base Systems, Volume II. Computer Science Press 1989, ISBN 0-7167-8162-X
Contents BibTeX
[48]
Moshe Y. Vardi: The Complexity of Relational Query Languages (Extended Abstract). STOC 1982: 137-146 BibTeX
[49]
Maarten H. van Emden, Robert A. Kowalski: The Semantics of Predicate Logic as a Programming Language. J. ACM 23(4): 733-742(1976) BibTeX
[50]
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
BibTeX
ACM SIGMOD Anthology - DBLP: [Home | Search: Author, Title | Conferences | Journals]
TODS, ACM SIGMOD Anthology: Copyright © by ACM (info@acm.org), Corrections: anthology@acm.org
DBLP: Copyright © by Michael Ley (ley@uni-trier.de), last change: Tue Jun 24 18:39:14 2008