Skip to Main content Skip to Navigation
Journal articles

When Can We Answer Queries Using Result-Bounded Data Interfaces?

Abstract : 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.
Complete list of metadata

https://hal.telecom-paris.fr/hal-03712199
Contributor : Antoine Amarilli Connect in order to contact the contributor
Submitted on : Saturday, July 2, 2022 - 4:40:33 PM
Last modification on : Friday, August 5, 2022 - 11:35:58 AM

Links full text

Identifiers

  • HAL Id : hal-03712199, version 1
  • ARXIV : 1810.07822

Collections

Citation

Antoine Amarilli, Michael Benedikt. When Can We Answer Queries Using Result-Bounded Data Interfaces?. Logical Methods in Computer Science, Logical Methods in Computer Science Association, 2022. ⟨hal-03712199⟩

Share

Metrics

Record views

18