Edinburgh Research Explorer

An Effective Syntax for Bounded Relational Queries

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

Related Edinburgh Organisations

Open Access permissions

Open

Documents

http://dl.acm.org/citation.cfm?id=2882942&CFID=635020502
Original languageEnglish
Title of host publicationACM SIGMOD Conference on Management of Data (SIGMOD 2016)
PublisherACM
Pages599-614
Number of pages16
ISBN (Print)978-1-4503-3531-7
DOIs
Publication statusPublished - 2016
Event2016 ACM SIGMOD Conference on Management of Data - San Francisco, United States
Duration: 26 Jun 20161 Jul 2016
http://sigmod2016.org/

Conference

Conference2016 ACM SIGMOD Conference on Management of Data
Abbreviated titleSIGMOD 2016
CountryUnited States
CitySan Francisco
Period26/06/161/07/16
Internet address

Abstract

A query Q is boundedly evaluable under a set A of access constraints if for all datasets D that satisfy A, there exists a fraction DQ of D such that Q(D) = Q(DQ), and the sizeof DQ and time for identifying DQ are both independent of the size of D. That is, we can compute Q(D) by accessing abounded amount of data no matter how big D grows. However,while desirable, it is undecidable to determine whether a query in relational algebra (RA) is bounded under A.In light of the undecidability, this paper develops an effective syntax for bounded RA queries. We identify a class of covered RA queries such that under A, (a) every boundedly evaluable RA query is equivalent to a covered query, (b) every covered RA query is boundedly evaluable, and (c) it takes PTIME in |Q| and |A| to check whether Q is covered by A.We provide quadratic-time algorithms to check the coverage of Q, and to generate a bounded query plan for covered Q.We also study a new optimization problem for minimizing access constraints for covered queries. Using real-life data,we experimentally verify that a large number of RA queries in practice are covered, and that bounded query plans improve RA query evaluation by orders of magnitude.

Event

2016 ACM SIGMOD Conference on Management of Data

26/06/161/07/16

San Francisco, United States

Event: Conference

Download statistics

No data available

ID: 24353757