Finite Representation of Infinite Query Answers

Jan Chomicki, Tomasz Imieliński

Research output: Contribution to journalArticlepeer-review

51 Scopus citations


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

Original languageEnglish (US)
Pages (from-to)181-223
Number of pages43
JournalACM Transactions on Database Systems (TODS)
Issue number2
StatePublished - Jan 6 1993

All Science Journal Classification (ASJC) codes

  • Information Systems

Fingerprint Dive into the research topics of 'Finite Representation of Infinite Query Answers'. Together they form a unique fingerprint.

Cite this