Antoine Amarilli ; Michael Benedikt - When Can We Answer Queries Using Result-Bounded Data Interfaces?

lmcs:4903 - Logical Methods in Computer Science, June 2, 2022, Volume 18, Issue 2 - https://doi.org/10.46298/lmcs-18(2:14)2022
When Can We Answer Queries Using Result-Bounded Data Interfaces?Article

Authors: Antoine Amarilli ; Michael Benedikt

    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.


    Volume: Volume 18, Issue 2
    Published on: June 2, 2022
    Accepted on: March 1, 2022
    Submitted on: October 20, 2018
    Keywords: Computer Science - Logic in Computer Science,Computer Science - Databases
    Funding:
      Source : OpenAIRE Graph
    • PDQ: Proof-driven Query Planning; Funder: UK Research and Innovation; Code: EP/M005852/1
    • ED3: Enabling analytics over Diverse Distributed Datasources; Funder: UK Research and Innovation; Code: EP/N014359/1

    6 Documents citing this article

    Consultation statistics

    This page has been seen 1350 times.
    This article's PDF has been downloaded 575 times.