First-order queries on finite structures over the reals
First-order queries on finite structures over the reals
复制标题
实数有限结构的一阶查询
DOI：
--
复制
发表时间：
1995
期刊：
影响因子：
--
通讯作者：
D. V. Gucht
中科院分区：
文献类型：
--
作者：
J. Paredaens;J. V. D. Bussche;D. V. Gucht
我们研究了由一阶语句表示的实数上的有限关系结构的性质，这些语句的谓词是结构加上任意多项式不等式的关系，并且其量词可以覆盖整个实数集。在约束编程术语中，这对应于有限结构上的布尔实多项式约束查询。量词覆盖所有实数的事实似乎至关重要；然而，我们观察到，实数的一阶理论中的每一句话都可以通过让每个量词只覆盖有限的实数集来评估，而不改变其真值。受此启发，我们证明了当所使用的所有多项式都是线性的时，每个查询可以在所有有限结构上由量词仅在结构的有限域上的句子一致地表示。换言之，有限结构上的线性约束规划可以归结为有限模型理论和数据库中常见的查询求值问题。此外，如果只考虑“一般”查询，我们证明了这样的查询可以用仅使用简单形式z的句子作为多项式不等式的句子来表示，从而进一步简化这一点
We investigate properties of finite relational structures over the reals expressed by first-order sentences whose predicates are the relations of the structure plus arbitrary polynomial inequalities, and whose quantifiers can range over the whole set of reals. In constraint programming terminology, this corresponds to Boolean real polynomial constraint queries on finite structures. The fact that quantifiers range over all reals seems crucial; however, we observe that each sentence in the first-order theory of the reals can be evaluated by letting each quantifier range over only a finite set of real numbers without changing its truth value. Inspired by this observation, we then show that when all polynomials used are linear, each query can be expressed uniformly on all finite structures by a sentence of which the quantifiers range only over the finite domain of the structure. In other words, linear constraint programming on finite structures can be reduced to ordinary query evaluation as usual in finite model theory and databases. Moreover, if only "generic" queries are taken into consideration, we show that this can be reduced even further by proving that such queries can be expressed by sentences using as polynomial inequalities only those of the simple form z