An Effective Syntax for Bounded Relational Queries

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

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.
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

Fingerprint Dive into the research topics of 'An Effective Syntax for Bounded Relational Queries'. Together they form a unique fingerprint.

Cite this