Skip to Main content Skip to Navigation
Conference papers

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

Abstract : We consider answering queries where the underlying data is available only over limited interfaces which provide lookup access to the tuples matching a given binding, but possibly restricting the number of output tuples returned. Interfaces imposing such "result bounds" are common in accessing data via the web. Given a query over a set of relations as well as some integrity constraints that relate the queried relations to the data sources, we examine the problem of deciding if the query is answerable over the interfaces; that is, whether there exists a plan that returns all answers to the query, assuming the source data satisfies the integrity constraints. The first component of our analysis of answerability is a reduction to a query containment problem with constraints. The second component is a set of "schema simplification" theorems capturing limitations on how interfaces with result bounds can be useful to obtain complete answers to queries. These results also help to show decidability for the containment problem that captures answerability, for many classes of constraints. The final component in our analysis of answerability is a "linearization" method, showing that query containment with certain guarded dependencies -- including those that emerge from answerability problems -- can be reduced to query containment for a well-behaved class of linear dependencies. Putting these components together, we get a detailed picture of how to check answerability over result-bounded services.
Complete list of metadata
Contributor : Antoine Amarilli Connect in order to contact the contributor
Submitted on : Monday, March 25, 2019 - 5:34:46 PM
Last modification on : Wednesday, November 3, 2021 - 8:15:56 AM

Links full text


  • HAL Id : hal-02079064, version 1
  • ARXIV : 1706.07936



Antoine Amarilli, Michael Benedikt. When Can We Answer Queries Using Result-Bounded Data Interfaces?. PODS 2018, Jun 2018, Houston, United States. ⟨hal-02079064⟩



Record views