Deterministic FOIES are Strictly Weaker

Document Type

Article

Publication Date

3-1997

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 relation

DOI

10.1023/A:1018951521198

Find in your library

Off-Campus WSU Users


Share

COinS