Relational Specifications of Infinite Query Answers

Jan Chomicki, Tomasz Imieliński

Research output: Contribution to journalArticlepeer-review

26 Scopus citations


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.

Original languageEnglish (US)
Pages (from-to)174-183
Number of pages10
JournalACM SIGMOD Record
Issue number2
StatePublished - Jun 1 1989

All Science Journal Classification (ASJC) codes

  • Software
  • Information Systems


Dive into the research topics of 'Relational Specifications of Infinite Query Answers'. Together they form a unique fingerprint.

Cite this