Projects per year
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 quadratictime 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 reallife 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 language  English 

Title of host publication  ACM SIGMOD Conference on Management of Data (SIGMOD 2016) 
Publisher  ACM 
Pages  599614 
Number of pages  16 
ISBN (Print)  9781450335317 
DOIs  
Publication status  Published  2016 
Event  2016 ACM SIGMOD Conference on Management of Data  San Francisco, United States Duration: 26 Jun 2016 → 1 Jul 2016 http://sigmod2016.org/ 
Conference
Conference  2016 ACM SIGMOD Conference on Management of Data 

Abbreviated title  SIGMOD 2016 
Country/Territory  United States 
City  San Francisco 
Period  26/06/16 → 1/07/16 
Internet address 
Fingerprint
Dive into the research topics of 'An Effective Syntax for Bounded Relational Queries'. Together they form a unique fingerprint.Projects
 2 Finished
Profiles

Yang Cao
 School of Informatics  Chancellor's Fellow in Digital Technologies
 Laboratory for Foundations of Computer Science
 Foundations of Computation
Person: Academic: Research Active