Edinburgh Research Explorer

Querying Big Data by Accessing Small Data

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Related Edinburgh Organisations

Open Access permissions

Open

Documents

http://doi.acm.org/10.1145/2745754.2745771
Original languageEnglish
Title of host publicationProceedings of the 34th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems
Place of PublicationNew York, NY, USA
PublisherACM
Pages173-184
Number of pages12
ISBN (Print)978-1-4503-2757-2
DOIs
Publication statusPublished - 20 May 2015
Event34th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems - Melbourne, Australia
Duration: 31 May 20154 Jun 2015
http://www.sigmod2015.org/

Conference

Conference34th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems
Abbreviated titlePODS 2015
CountryAustralia
CityMelbourne
Period31/05/154/06/15
Internet address

Abstract

This paper investigates the feasibility of querying big data by accessing a bounded amount of the data. We study boundedly evaluable queries under a form of access constraints, when their evaluation cost is determined by the queries and constraints only. While it is undecidable to determine whether FO queries are boundedly evaluable, we show that for several classes of FO queries, the bounded evaluability problem is decidable. We also provide characterization and effective syntax for their boundedly evaluable queries.

When a query Q is not boundedly evaluable, we study two approaches to approximately answering Q under access constraints. (1) We search for upper and lower envelopes of Q that are boundedly evaluable and warrant a constant accuracy bound. (2) We instantiate a minimum set of variables (parameters) in Q such that the specialized query is boundedly evaluable. We study problems for deciding the existence of envelopes and bounded specialized queries, and establish their complexity for various classes of FO queries.

    Research areas

  • big data, complexity, query answering

Event

34th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems

31/05/154/06/15

Melbourne, Australia

Event: Conference

Download statistics

No data available

ID: 19939234