Answering UCQs under updates and in the presence of integrity constraints
Answering UCQs under updates and in the presence of integrity constraints
复制标题
在更新和存在完整性约束的情况下回答 UCQ
DOI：
10.4230/lipics.icdt.2018.8
复制
发表时间：
2017
期刊：
影响因子：
--
通讯作者：
Nicole Schweikardt
中科院分区：
文献类型：
--
作者：
Christoph Berkholz;Jens Keppeler;Nicole Schweikardt
我们研究了可以插入或删除元组的完全动态数据库的固定查询的查询评估问题。任务是设计一个动态数据结构，可以在每个数据库更新后立即报告固定查询的新结果。我们考虑联合查询工会（UCQ），并专注于查询评估任务测试（确定输入元组是否属于查询结果），枚举（枚举，无需重复，查询结果中的所有元组）和计数（输出计数（输出）查询结果中的单元数）。
我们确定了三种日益严格的UCQ类，我们称为T层次结构，Q层次结构和详尽的Q层次结构UCQ。我们的主要结果提供了以下二分法：如果查询的同形核心是t层次结构（Q层次结构，详尽的Q层次结构），则可以通过持续的更新时间和持续的测试时间（延迟测试时间）来解决测试（枚举，计数）问题，计数时间）。否则，除非OV-conture和/或OMV-conture失败，否则无法使用均方根更新时间和sublinear测试时间（延迟，计数时间）来解决它。
我们还研究了存在完整性约束的动态设置中查询评估的复杂性，并根据小域约束的特殊情况获得了二分法结果（即，约束，指出关系中所有值的所有值到一个恒定大小的固定域）。
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 data structure that can immediately report the new result of a fixed query after every database update. We consider unions of conjunctive queries (UCQs) and focus on the query evaluation tasks testing (decide whether an input tuple belongs to the query result), enumeration (enumerate, without repetition, all tuples in the query result), and counting (output the number of tuples in the query result).
We identify three increasingly restrictive classes of UCQs which we call t-hierarchical, q-hierarchical, and exhaustively q-hierarchical UCQs. Our main results provide the following dichotomies: If the query's homomorphic core is t-hierarchical (q-hierarchical, exhaustively q-hierarchical), then the testing (enumeration, counting) problem can be solved with constant update time and constant testing time (delay, counting time). Otherwise, it cannot be solved with sublinear update time and sublinear testing time (delay, counting time), unless the OV-conjecture and/or the OMv-conjecture fails.
We also study the complexity of query evaluation in the dynamic setting in the presence of integrity constraints, and we obtain according dichotomy results for the special case of small domain constraints (i.e., constraints which state that all values in a particular column of a relation belong to a fixed domain of constant size).
动态连接查询
DOI：
10.1016/j.jcss.2017.03.014
发表时间：
2017
期刊：
影响因子：
--
作者：
Thomas Zeume;Thomas Schwentick
通讯作者：
Thomas Schwentick