Answering FO+MOD Queries under Updates on Bounded Degree Databases
Answering FO+MOD Queries under Updates on Bounded Degree Databases
复制标题
在有界度数据库更新下回答 FO MOD 查询
DOI：
10.1145/3232056
复制
发表时间：
2017
期刊：
影响因子：
--
通讯作者：
Nicole Schweikardt
中科院分区：
文献类型：
--
作者：
Christoph Berkholz;Jens Keppeler;Nicole Schweikardt
我们研究了完全动态数据库上固定查询的查询评估问题，其中元组可以被插入或删除。我们的任务是设计一个动态算法，在每次数据库更新后立即报告固定查询的新结果。我们考虑了一阶逻辑(FO)中的查询及其带模计数量词(FO+MOD)的扩展，证明了只要动态数据库不超过一定的度界，它们在更新时就可以被有效地求值。特别地，我们构造了一个数据结构，使得我们能够在每次数据库更新后的固定时间内回答布尔FO+MOD查询并计算非布尔查询结果的大小。此外，每次数据库更新后，我们可以在固定时间内更新数据结构，以便之后能够在固定时间内测试给定的元组是否属于查询结果，枚举新查询结果中的所有元组，并以恒定的延迟枚举输出元组之间的旧查询结果和新查询结果之间的差异。建立数据结构所需的预处理时间与数据库的大小呈线性关系。我们的结果扩展了早期关于有界度静态数据库上一阶查询的评估工作，并依赖于Heimberg，Kuske和Schweikardt最近获得的FO+MOD的有效Hanf范式(LICs 2016)。
We investigate the query evaluation problem for fixed queries over fully dynamic databases, where tuples can be inserted or deleted. The task is to design a dynamic algorithm that immediately reports the new result of a fixed query after every database update.We consider queries in first-order logic (FO) and its extension with modulo-counting quantifiers (FO+MOD) and show that they can be efficiently evaluated under updates, provided that the dynamic database does not exceed a certain degree bound.In particular, we construct a data structure that allows us to answer a Boolean FO+MOD query and to compute the size of the result of a non-Boolean query within constant time after every database update. Furthermore, after every database update, we can update the data structure in constant time such that afterwards we are able to test within constant time for a given tuple whether or not it belongs to the query result, to enumerate all tuples in the new query result, and to enumerate the difference between the old and the new query result with constant delay between the output tuples. The preprocessing time needed to build the data structure is linear in the size of the database.Our results extend earlier work on the evaluation of first-order queries on static databases of bounded degree and rely on an effective Hanf normal form for FO+MOD recently obtained by Heimberg, Kuske, and Schweikardt (LICS 2016).
登录
查看更多内容
具有局部有界扩展的数据库上 FO 查询的恒定延迟枚举
DOI：
--
发表时间：
2017
期刊：
International Conference on Database Theory
影响因子：
--
作者：
L. Segoufin;Alexandre Vigny
通讯作者：
Alexandre Vigny
具有一元计数量词的一阶逻辑的 Hanf 范式
DOI：
--
发表时间：
2016
期刊：
Logic in Computer Science
影响因子：
--
作者：
Lucas Heimberg;D. Kuske;Nicole Schweikardt
通讯作者：
Nicole Schweikardt
DOI：
10.1145/3051095
发表时间：
2013-11
期刊：
Journal of the ACM (JACM)
影响因子：
--
作者：
Martin Grohe;S. Kreutzer;S. Siebertz
通讯作者：
Martin Grohe;S. Kreutzer;S. Siebertz
有界度结构的一阶查询可以恒定延迟计算
DOI：
--
发表时间：
2005
期刊：
TOCL
影响因子：
--
作者：
Arnaud Durand;E. Grandjean
通讯作者：
E. Grandjean
在更新和存在完整性约束的情况下回答 UCQ
DOI：
10.4230/lipics.icdt.2018.8
发表时间：
2017
期刊：
ArXiv
影响因子：
--
作者：
Christoph Berkholz;Jens Keppeler;Nicole Schweikardt
通讯作者：
Nicole Schweikardt