Nonrecursive incremental evaluation of Datalog queries
Nonrecursive incremental evaluation of Datalog queries
复制标题
数据记录查询的非递归增量评估
DOI：
10.1007/bf01530820
复制
发表时间：
1995
影响因子：
1.2
通讯作者：
R. Topor
中科院分区：
文献类型：
--
作者：
Guozhu Dong;Jianwen Su;R. Topor
我们考虑在这种情况下，在成功的查询请求之间更新的数据库中反复评估相同的（计算昂贵）查询。为了减少在下一个状态中评估查询的成本。使用连接查询的查询评估，我们给出了一个算法，该算法为每个常规链查询（包括及时的闭合作为特殊情况），一个非转录数据词程序，以计算更新之前的更新和答案之间的差异然后将此结果扩展到弱规则的查询，这些查询是常规的链条程序，并以所谓的笛卡尔封闭的增量属性增强，并将其插入二进制于二进制笛卡尔产品确定了带有笛卡尔封闭的增量属性的连接性查询类别。
We consider the problem of repeatedly evaluating the same (computationally expensive) query to a database that is being updated between successive query requests. In this situation, it should be possible to use the difference between successive database states and the answer to the query in one state to reduce the cost of evaluating the query in the next state. We use nonrecursive Datalog (which are unions of conjunctive queries) to compute the differences, and call this process “incremental query evaluation using conjunctive queries”. After formalizing the notion of incremental query evaluation using conjunctive queries, we give an algorithm that constructs, for each regular chain query (including transitive closure as a special case), a nonrecursive Datalog program to compute the difference between the answer after an update and the answer before the update. We then extend this result to weakly regular queries, which are regular chain programs augmented with conjunctive queries having the so-called Cartesian-closed increment property, and to the case of unbounded-set insertions where the sets are binary Cartesian products. Finally, we show that the class of conjunctive queries with the Cartesian-closed increment property is decidable.