一句话：将使用结果有界访问方法回答查询的可回答性问题归约为带约束的查询包含问题，并给出常见约束类下的可判定性与复杂度结果。
本文研究通过数据访问方法回答查询的问题：访问方法对给定绑定返回匹配元组。此类接口在 Web 上常见，且常因分页或速率限制而只能返回有限数量的结果，称为结果有界方法。论文关注在底层数据满足完整性约束的前提下，判定一个查询是否可仅用这些有界方法回答，并构造返回全部答案的计划。作者首先将可回答性归约为带约束的查询包含问题；随后证明“模式简化”定理，刻画结果有界服务何时以及如何能被使用；最后基于这些定理，针对常见约束类给出可回答性问题的可判定性与复杂度结果。
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.
@article{paperbot1697,
title = {When Can We Answer Queries Using Result-Bounded Data Interfaces?},
author = {Antoine Amarilli and Michael Benedikt},
journal = {Logical Methods in Computer Science},
volume = {Volume 18, Issue 2},
year = {2022},
doi = {10.46298/lmcs-18(2:14)2022}
}