First-order queries on structures of bounded degree are computable with constant delay
First-order queries on structures of bounded degree are computable with constant delay
复制标题
有界度结构的一阶查询可以恒定延迟计算
DOI：
--
复制
发表时间：
2005
期刊：
影响因子：
--
通讯作者：
E. Grandjean
中科院分区：
文献类型：
--
作者：
Arnaud Durand;E. Grandjean
一个关系结构是<i>d</i>度有界的，对于某个整数<i>d</i>，如果定义域的每个元素最多属于<i>d个</i>元组。在本文中，我们重新评估问题的复杂性，不一定布尔一阶（<b>FO</b>）查询的<i>d</i>度有界结构。查询评估在这里被认为是一个动态的过程。我们证明<i>了d</i>度有界结构上的任何<b>FO</b>查询都属于复杂度类constant-Delay<inf><i>lin</i></inf>，也就是说，可以通过具有两个单独部分的算法来计算：它具有与结构的大小成时间线性的预计算步骤，然后，它输出所有解（即，满足该公式的元组）以恒定延迟一个接一个（即，仅取决于公式的大小）。作为一个全局过程，这意味着对<i>d</i>度有界结构的查询可以在总时间<i>f</i>（|ϕ|). (|<i>S</i>| + |海（<i>S</i>）|）和空间<i>g</i>（|ϕ|).| <i>S</i>|其中<i>S</i>是结构，f是公式，f（<i>S</i>）是查询的结果，<i>f</i>，<i>g</i>是一些固定的函数。
除其他事项外，我们的研究结果推广了Seese的数据复杂性的模型检测问题的<i>d</i>度有界结构。此外，我们的方法相比，相关结果的独创性是，它不依赖于Hanf的模型理论的技术，是简单和翔实的，因为它基本上取决于一个量词消除方法。
A relational structure is <i>d</i>-degree-bounded, for some integer <i>d</i>, if each element of the domain belongs to at most <i>d</i> tuples. In this paper, we revisit the complexity of the evaluation problem of not necessarily Boolean first-order (<b>FO</b>) queries over <i>d</i>-degree-bounded structures. Query evaluation is considered here as a dynamical process. We prove that any <b>FO</b> query on <i>d</i>-degree-bounded structures belongs to the complexity class constant-Delay<inf><i>lin</i></inf>, that is, can be computed by an algorithm that has two separate parts: it has a precomputation step of time linear in the size of the structure and then, it outputs all solutions (i.e., tuples that satisfy the formula) one by one with a constant delay (i.e., depending on the size of the formula only) between each. Seen as a global process, this implies that queries on <i>d</i>-degree-bounded structures can be evaluated in total time <i>f</i>(|ϕ|).(|<i>S</i>| + |ϕ(<i>S</i>)|) and space <i>g</i>(|ϕ|).|<i>S</i>| where <i>S</i> is the structure, ϕ is the formula, ϕ(<i>S</i>) is the result of the query and <i>f</i>, <i>g</i> are some fixed functions.
Among other things, our results generalize a result of Seese on the data complexity of the model-checking problem for <i>d</i>-degree-bounded structures. Besides, the originality of our approach compared to related results is that it does not rely on the Hanf's model-theoretic technique and is simple and informative since it essentially rests on a quantifier elimination method.