Bounded Evaluation: Querying Big Data with Bounded Resources

Yang Cao, Wenfei Fan, Tengfei Yuan

Research output: Contribution to journalArticlepeer-review

Abstract / Description of output

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 if when posed on any big dataset D, there exists a fraction DQ of D such that Q(D) = Q(DQ), and the cost of identifying DQ is independent of the size of D. It has been shown that with 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 RAaggr, i.e., RA extended with aggregation, under the bag semantics. (1) We extend access schema to bag access schema, to help us identify Dfor RAaggr queries Q. (2) While it is undecidable to determine whether an RAaggr 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 RAaggr queries, i.e., a core subclass of boundedly evaluable RAaggr queries without sacrificing their expressive power. (4) Based on the effective syntax, we provide efficient algorithms to check the bounded evaluability of RAaggr queries and to generate query plans for bounded RAaggr 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.
Original languageEnglish
Pages (from-to)502–526
Number of pages20
JournalInternational Journal of Automation and Computing
Issue number4
Early online date4 Jul 2020
Publication statusPublished - 1 Aug 2020

Keywords / Materials (for Non-textual outputs)

  • Bounded evaluation
  • resource-bounded query processing,
  • effective syntax
  • access schema
  • boundedness


Dive into the research topics of 'Bounded Evaluation: Querying Big Data with Bounded Resources'. Together they form a unique fingerprint.

Cite this