We consider answering queries on data available through access methods, that provide lookup access to the tuples matching a given binding. Such interfaces are common on the Web; further, they often have bounds on how many results they can return, e.g., because of pagination or rate limits. We thus study result-bounded methods, which may return only a limited number of tuples. We study how to decide if a query is answerable using result-bounded methods, i.e., how to compute a plan that returns all answers to the query using the methods, assuming that the underlying data satisfies some integrity constraints. We first show how to reduce answerability to a query containment problem with constraints. Second, we show "schema simplification" theorems describing when and how result-bounded services can be used. Finally, we use these theorems to give decidability and complexity results about answerability for common constraint classes.


翻译:我们考虑通过访问方法回答关于可用数据的问题,通过访问方法提供对与给定约束匹配的图例的访问访问。这种界面在网上是常见的;此外,这些界面往往有关于他们可以返回多少结果的界限,例如由于页数或费率的限制。因此我们研究受结果限制的方法,这些方法可能只返回有限的图例。我们研究如何使用受结果限制的方法来决定查询是否可以回答,即如何计算一个计划,在假设基本数据符合某些完整性限制的情况下,将所有答案都返回到使用方法的查询中。我们首先展示如何减少对受限制的查询限制问题的可回答性。第二,我们展示“系统简化”的标语,说明何时以及如何使用受结果限制的服务。最后,我们用这些标语来给共同约束类的可回答性提供可决定性和复杂的结果。

0
下载
关闭预览

相关内容

最新《序列预测问题导论》教程,212页ppt
专知会员服务
83+阅读 · 2020年8月22日
基于深度学习的表面缺陷检测方法综述
专知会员服务
83+阅读 · 2020年5月31日
因果图,Causal Graphs,52页ppt
专知会员服务
238+阅读 · 2020年4月19日
深度强化学习策略梯度教程,53页ppt
专知会员服务
175+阅读 · 2020年2月1日
FlowQA: Grasping Flow in History for Conversational Machine Comprehension
专知会员服务
22+阅读 · 2019年10月18日
强化学习最新教程,17页pdf
专知会员服务
166+阅读 · 2019年10月11日
2019年机器学习框架回顾
专知会员服务
35+阅读 · 2019年10月11日
分布式并行架构Ray介绍
CreateAMind
9+阅读 · 2019年8月9日
Hierarchically Structured Meta-learning
CreateAMind
23+阅读 · 2019年5月22日
Transferring Knowledge across Learning Processes
CreateAMind
24+阅读 · 2019年5月18日
已删除
将门创投
8+阅读 · 2019年1月30日
【TED】生命中的每一年的智慧
英语演讲视频每日一推
9+阅读 · 2019年1月29日
强化学习的Unsupervised Meta-Learning
CreateAMind
17+阅读 · 2019年1月7日
Unsupervised Learning via Meta-Learning
CreateAMind
41+阅读 · 2019年1月3日
A Technical Overview of AI & ML in 2018 & Trends for 2019
待字闺中
15+阅读 · 2018年12月24日
disentangled-representation-papers
CreateAMind
26+阅读 · 2018年9月12日
Arxiv
0+阅读 · 2021年4月19日
QuAC : Question Answering in Context
Arxiv
4+阅读 · 2018年8月21日
VIP会员
相关VIP内容
最新《序列预测问题导论》教程,212页ppt
专知会员服务
83+阅读 · 2020年8月22日
基于深度学习的表面缺陷检测方法综述
专知会员服务
83+阅读 · 2020年5月31日
因果图,Causal Graphs,52页ppt
专知会员服务
238+阅读 · 2020年4月19日
深度强化学习策略梯度教程,53页ppt
专知会员服务
175+阅读 · 2020年2月1日
FlowQA: Grasping Flow in History for Conversational Machine Comprehension
专知会员服务
22+阅读 · 2019年10月18日
强化学习最新教程,17页pdf
专知会员服务
166+阅读 · 2019年10月11日
2019年机器学习框架回顾
专知会员服务
35+阅读 · 2019年10月11日
相关资讯
分布式并行架构Ray介绍
CreateAMind
9+阅读 · 2019年8月9日
Hierarchically Structured Meta-learning
CreateAMind
23+阅读 · 2019年5月22日
Transferring Knowledge across Learning Processes
CreateAMind
24+阅读 · 2019年5月18日
已删除
将门创投
8+阅读 · 2019年1月30日
【TED】生命中的每一年的智慧
英语演讲视频每日一推
9+阅读 · 2019年1月29日
强化学习的Unsupervised Meta-Learning
CreateAMind
17+阅读 · 2019年1月7日
Unsupervised Learning via Meta-Learning
CreateAMind
41+阅读 · 2019年1月3日
A Technical Overview of AI & ML in 2018 & Trends for 2019
待字闺中
15+阅读 · 2018年12月24日
disentangled-representation-papers
CreateAMind
26+阅读 · 2018年9月12日
Top
微信扫码咨询专知VIP会员