Publisher: Springer Publishing Company
ISSN: 1012-2443
Source: Annals of Mathematics and Artificial Intelligence, Vol.19, Iss.1-2, 1997-01, pp. : 127-146
Disclaimer: Any content in publications that violate the sovereignty, the constitution or regulations of the PRC is not accepted or approved by CNPIEC.
Abstract
After a bounded update to a database, a first-order incremental evaluation system (abbreviated foies) derives the new answer to an expensive database query by applying a first-order query on the old answer and perhaps some stored auxiliary relations. The auxiliary relations are also maintained in first order. A foies can be deterministic or nondeterministic, depending on whether its (stored) auxiliary relations are defined by deterministic or nondeterministic mappings (from databases). In this paper we study the impact of the determinism restriction on foies and we compare nondeterminism with determinism in foies. It turns out that nondeterministic foies are more powerful than the deterministic ones: deterministic foies using auxiliary relations with arity <= k="" are="" shown="" to="" be="" strictly="" weaker="" than="" their="" nondeterministic="" counterparts="" for="" each="" k=""> 1, and it is shown that there is a simple query which has a nondeterministic foies with binary auxiliary relations but does not have any deterministic foies with auxiliary relations of any arity. A strict arity hierarchy of deterministic foies is established for the small arities (<= 2).="" interestingly,="" the="" deterministic="" foies="" arity="" hierarchy="" collapses="" to="" 0-ary="" when="" limited="" to="" queries="" over="" unary="" relations.=""></=></=>
Related content
A Decomposition of a Weaker Form of Continuity
By Noiri T. Rajamani M. Sundaram P.
Acta Mathematica Hungarica, Vol. 93, Iss. 1-2, 2001-10 ,pp. :
On a Weaker Form of Countable Compactness
By Bonanzinga Maddalena Cammaroto Filippo Matveev Mikhail V.
Quaestiones Mathematicae, Vol. 30, Iss. 4, 2007-12 ,pp. :
On Weaker Forms of Separability
By Bonanzinga Maddalena Cammaroto Filippo Matveev Mikhail Pansera Bruno
Quaestiones Mathematicae, Vol. 31, Iss. 4, 2008-12 ,pp. :