DETERMINISTIC FOIES ARE STRICTLY WEAKER

After a bounded update to a database, a first-order incremental evalua tion 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 a lso maintained in first order. A foies can be deterministic or nondete rministic, depending on whether its (stored) auxiliary relations are d efined by deterministic or nondeterministic mappings (from databases). In this paper we study the impact of the determinism restriction on f oies and we compare nondeterminism with determinism in foies. It turns out that nondeterministic foies are more powerful than the determinis tic ones: deterministic foies using auxiliary relations with arity les s than or equal to k are shown to be strictly weaker than their nondet erministic counterparts for each k greater than or equal to 1, and it is shown that there is a simple query which has a nondeterministic foi es 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 (less tha n or equal to 2). Interestingly the deterministic foies arity hierarch y collapses to 0-ary when limited to queries over unary relations.