Bounded Evaluation: Querying Big Data with Bounded Resources

CategoryPublications 255

Authors: Yang Cao, Wenfei Fan, Tengfei Yuan

Published in: International Journal of Automation and Computing (IJAC)

Date of Publication: July 4, 2020


This work aims to reduce queries on big data to computations on small data, and hence make querying big data possible under bounded resources. A query \( Q \) is boundedly evaluable when posed on any big dataset \( D \), there exists a fraction \(D_Q\) of \( D \) such that \( Q(D)=Q(D_Q) \), and the cost of identifying \(D_Q\) is independent of the size of \( D \). It has been shown that with an auxiliary structure known as access schema, many queries in relational algebra (RA) are boundedly evaluable under the set semantics of RA. This paper extends the theory of bounded evaluation to \(RA_{aggr}\), i.e., RA extended with aggregation, under the bag semantics. (1) We extend access schema to bag access schema, to help us identify \(D_Q\) for \(RA_{aggr}\) queries \( Q \). (2) While it is undecidable to determine whether an \(RA_{aggr}\) query is boundedly evaluable under a bag access schema, we identify special cases that are decidable and practical. (3) In addition, we develop an effective syntax for bounded \(RA_{aggr}\) queries, i.e., a core subclass of boundedly evaluable \(RA_{aggr}\) queries without sacrificing their expressive power. (4) Based on the effective syntax, we provide efficient algorithms to check the bounded evaluability of \(RA_{aggr}\) queries and to generate query plans for bounded \(RA_{aggr}\) queries. (5) As proof of concept, we extend PostgreSQL to support bounded evaluation. We experimentally verify that the extended system improves performance by orders of magnitude.

View Full Text

Keywords2020Data qualityIJACWenfei Fan Previous: Next: