The chase procedure is a fundamental algorithmic tool in databases that allows us to reason with constraints, such as existential rules, with a plethora of applications. It takes as input a database and a set of constraints, and iteratively completes the database as dictated by the constraints. A key challenge, though, is the fact that it may not terminate, which leads to the problem of checking whether it terminates given a database and a set of constraints. In this work, we focus on the semi-oblivious version of the chase, which is well-suited for practical implementations, and linear existential rules, a central class of constraints with several applications. In this setting, there is a mature body of theoretical work that provides syntactic characterizations of when the chase terminates, algorithms for checking chase termination, precise complexity results, and worst-case optimal bounds on the size of the result of the chase (whenever is finite). Our main objective is to experimentally evaluate the existing chase termination algorithms with the aim of understanding which input parameters affect their performance, clarifying whether they can be used in practice, and revealing their performance limitations.


翻译:撵追过程是数据库中用于处理约束(如存在规则)的基本算法工具,具有多种应用。它的输入是一个数据库和一组约束条件,根据约束条件来完成数据库的迭代。然而,一个关键的挑战是撵追过程可能无法终止,这导致了检查是否在给定数据库和一组约束条件下终止的问题。在这项工作中,我们重点关注半遗忘版本的撵追过程,这是实际实现的良好选择,以及线性存在规则,这是一类约束条件,具有多种应用。在这种情况下,有一些成熟的理论研究,提供了撵追过程终止的语法特征,用于检查撵追终止的算法,精确的复杂度结果,以及当结果的大小有限时,最坏情况下的最优边界。我们主要的目标是以实验方法评估现有的撵追终止算法,以便了解哪些输入参数会影响其性能,澄清它们是否可以在实践中使用,并揭示它们的性能限制。

0
下载
关闭预览

相关内容

【硬核书】稀疏多项式优化:理论与实践,220页pdf
专知会员服务
68+阅读 · 2022年9月30日
【硬核书】矩阵代数基础,248页pdf
专知会员服务
85+阅读 · 2021年12月9日
机器学习组合优化
专知会员服务
109+阅读 · 2021年2月16日
VCIP 2022 Call for Demos
CCF多媒体专委会
1+阅读 · 2022年6月6日
量化金融强化学习论文集合
专知
13+阅读 · 2019年12月18日
逆强化学习-学习人先验的动机
CreateAMind
15+阅读 · 2019年1月18日
强化学习的Unsupervised Meta-Learning
CreateAMind
17+阅读 · 2019年1月7日
无监督元学习表示学习
CreateAMind
27+阅读 · 2019年1月4日
Unsupervised Learning via Meta-Learning
CreateAMind
42+阅读 · 2019年1月3日
A Technical Overview of AI & ML in 2018 & Trends for 2019
待字闺中
17+阅读 · 2018年12月24日
笔记 | Deep active learning for named entity recognition
黑龙江大学自然语言处理实验室
24+阅读 · 2018年5月27日
笔记 | Sentiment Analysis
黑龙江大学自然语言处理实验室
10+阅读 · 2018年5月6日
国家自然科学基金
1+阅读 · 2017年12月31日
国家自然科学基金
0+阅读 · 2015年12月31日
国家自然科学基金
0+阅读 · 2015年12月31日
国家自然科学基金
0+阅读 · 2015年12月31日
国家自然科学基金
0+阅读 · 2012年12月31日
国家自然科学基金
1+阅读 · 2011年12月31日
国家自然科学基金
1+阅读 · 2011年12月31日
国家自然科学基金
0+阅读 · 2011年12月31日
国家自然科学基金
0+阅读 · 2009年12月31日
国家自然科学基金
0+阅读 · 2009年12月31日
Arxiv
0+阅读 · 2023年5月10日
Arxiv
0+阅读 · 2023年5月9日
A survey on deep hashing for image retrieval
Arxiv
14+阅读 · 2020年6月10日
VIP会员
相关VIP内容
【硬核书】稀疏多项式优化:理论与实践,220页pdf
专知会员服务
68+阅读 · 2022年9月30日
【硬核书】矩阵代数基础,248页pdf
专知会员服务
85+阅读 · 2021年12月9日
机器学习组合优化
专知会员服务
109+阅读 · 2021年2月16日
相关资讯
VCIP 2022 Call for Demos
CCF多媒体专委会
1+阅读 · 2022年6月6日
量化金融强化学习论文集合
专知
13+阅读 · 2019年12月18日
逆强化学习-学习人先验的动机
CreateAMind
15+阅读 · 2019年1月18日
强化学习的Unsupervised Meta-Learning
CreateAMind
17+阅读 · 2019年1月7日
无监督元学习表示学习
CreateAMind
27+阅读 · 2019年1月4日
Unsupervised Learning via Meta-Learning
CreateAMind
42+阅读 · 2019年1月3日
A Technical Overview of AI & ML in 2018 & Trends for 2019
待字闺中
17+阅读 · 2018年12月24日
笔记 | Deep active learning for named entity recognition
黑龙江大学自然语言处理实验室
24+阅读 · 2018年5月27日
笔记 | Sentiment Analysis
黑龙江大学自然语言处理实验室
10+阅读 · 2018年5月6日
相关基金
国家自然科学基金
1+阅读 · 2017年12月31日
国家自然科学基金
0+阅读 · 2015年12月31日
国家自然科学基金
0+阅读 · 2015年12月31日
国家自然科学基金
0+阅读 · 2015年12月31日
国家自然科学基金
0+阅读 · 2012年12月31日
国家自然科学基金
1+阅读 · 2011年12月31日
国家自然科学基金
1+阅读 · 2011年12月31日
国家自然科学基金
0+阅读 · 2011年12月31日
国家自然科学基金
0+阅读 · 2009年12月31日
国家自然科学基金
0+阅读 · 2009年12月31日
Top
微信扫码咨询专知VIP会员