Non-deterministic languages to express deterministic transformations
Non-deterministic languages to express deterministic transformations
复制标题
用于表达确定性变换的非确定性语言
DOI：
--
复制
发表时间：
1990
期刊：
影响因子：
--
通讯作者：
V. Vianu
中科院分区：
文献类型：
--
作者：
S. Abiteboul;E. Simon;V. Vianu
使用务实和理论考虑的动机非确定性数据库语言的使用是动机的。结果表明，非确定性解决了确定性语言的表达能力的一些困难：有非确定性的语言表达低复杂性的查询/更新类别，而没有这种确定性语言。审查了产生非确定性的各种机制。重点是两个密切相关的非确定性语言家庭。第一个组成的数据构成的数据分析和/或规则的负责人以及非确定性fixpoint语义的扩展。第二阶段是使用证人操作员的一阶逻辑和FixPoint逻辑的非确定性扩展。表达各种非确定性语言表达确定性转换的能力。特别是，在多项式时间内可以精确地表达可计算的查询/更新的非确定性语言，而猜测不存在类似的确定性语言。还探讨了非确定性语言与确定论之间的联系。检查了几个实际兴趣的问题，例如（静态或动态）检查给定程序是否确定性，检测确定性和非确定性语义的巧合，以及对非确定性程序的验证终止。
The use of non-deterministic database languages is motivated using pragmatic and theoretical considerations. It is shown that non-determinism resolves some difficulties concerning the expressive power of deterministic languages: there are non-deterministic languages expressing low complexity classes of queries/updates, whereas no such deterministic languages exist. Various mechanisms yielding non-determinism are reviewed. The focus is on two closely related families of non-deterministic languages. The first consists of extensions of Datalog with negations in bodies and/or heads of rules, with non-deterministic fixpoint semantics. The second consists of non-deterministic extensions of first-order logic and fixpoint logics, using the witness operator. The ability of the various non-deterministic languages to express deterministic transformation is characterized. In particular, non-deterministic languages expressing exactly the queries/updates computable in polynomial time are exhibited, whereas it is conjectured that no analogous deterministic language exists. The connection between non-deterministic languages and determinism is also explored. Several problems of practical interest are examined, such as checking (statically or dynamically) if a given program is deterministic, detecting coincidence of deterministic and non-deterministic semantics, and verifying termination for non-deterministic programs.