Deterministic FOIES are strictly weaker
Deterministic FOIES are strictly weaker
复制标题
确定性 FOIES 较弱
DOI：
--
复制
发表时间：
2004
影响因子：
1.2
通讯作者：
Jianwen Su
中科院分区：
文献类型：
--
作者：
Guozhu Dong;Jianwen Su
对数据库进行有界更新后，一阶增量评估系统（缩写为 foies）通过对旧答案以及可能的一些存储的辅助关系应用一阶查询，得出昂贵的数据库查询的新答案。辅助关系也保持第一顺序。 foies 可以是确定性的或非确定性的，具体取决于其（存储的）辅助关系是由确定性映射还是非确定性映射（来自数据库）定义的。在本文中，我们研究了决定论限制对鹅的影响，并将鹅的非决定论与决定论进行了比较。事实证明，非确定性 foies 比确定性 foies 更强大：对于每个 k > 1，使用 arity <= k 的辅助关系的确定性 foies 被证明严格弱于其非确定性对应关系，并且表明存在一个简单的查询，该查询具有具有二元辅助关系的非确定性 foies，但不具有任何具有任何 arity 辅助关系的确定性 foies。为小 arities (<= 2) 建立了确定性 foies 的严格 arity 层次结构。有趣的是，当仅限于一元关系的查询时，确定性 foies 元数层次结构会崩溃为 0 元。
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.