Deterministic FOIES are Strictly Weaker

Guozhu Dong, The University of Melbourne

Jianwen Su, UCSB

Status

To appear in Annals of Mathematics and Artificial Intelligence.

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.