Finite Representation of Infinite Query Answers

Jan Chomicki, Tomasz Imielinski

Research output: Contribution to journalArticle

51 Citations (Scopus)

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 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)
Volume18
Issue number2
DOIs
StatePublished - Jan 6 1993

Fingerprint

Substitution reactions
Specifications

All Science Journal Classification (ASJC) codes

  • Information Systems

Cite this

@article{e115e7f10494441cb7a3c0922accd80e,
title = "Finite Representation of Infinite Query Answers",
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 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.",
author = "Jan Chomicki and Tomasz Imielinski",
year = "1993",
month = "1",
day = "6",
doi = "10.1145/151634.151635",
language = "English (US)",
volume = "18",
pages = "181--223",
journal = "ACM Transactions on Database Systems",
issn = "0362-5915",
publisher = "Association for Computing Machinery (ACM)",
number = "2",

}

Finite Representation of Infinite Query Answers. / Chomicki, Jan; Imielinski, Tomasz.

In: ACM Transactions on Database Systems (TODS), Vol. 18, No. 2, 06.01.1993, p. 181-223.

Research output: Contribution to journalArticle

TY - JOUR

T1 - Finite Representation of Infinite Query Answers

AU - Chomicki, Jan

AU - Imielinski, Tomasz

PY - 1993/1/6

Y1 - 1993/1/6

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

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

UR - http://www.scopus.com/inward/record.url?scp=0027609181&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=0027609181&partnerID=8YFLogxK

U2 - 10.1145/151634.151635

DO - 10.1145/151634.151635

M3 - Article

AN - SCOPUS:0027609181

VL - 18

SP - 181

EP - 223

JO - ACM Transactions on Database Systems

JF - ACM Transactions on Database Systems

SN - 0362-5915

IS - 2

ER -