Bounded Evaluation: Querying Big Data with Bounded Resources

doi:10.1007/s11633-020-1236-1

CORC > 自动化研究所 > 中国科学院自动化研究所 > 学术期刊 > International Journal of Automation and Computing

	Bounded Evaluation: Querying Big Data with Bounded Resources
	Yang Cao 2; Wen-Fei Fan 1,2,3; Teng-Fei Yuan 2
刊名	International Journal of Automation and Computing
	2020
卷号	17 期号:4 页码:502-526
关键词	Bounded evaluation resource-bounded query processing effective syntax access schema boundedness.
ISSN号	1476-8186
DOI	10.1007/s11633-020-1236-1
英文摘要	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 ${\cal D}$, there exists a fraction ${\cal D}_Q$ of ${\cal D}$ such that $Q({\cal D}) = Q({\cal D}_Q)$, and the cost of identifying ${\cal D}_Q$ is independent of the size of ${\cal 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 ${\cal 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.
内容类型	期刊论文
源URL	[http://ir.ia.ac.cn/handle/173211/42275]
专题	自动化研究所_学术期刊_International Journal of Automation and Computing
作者单位	1.Shenzhen Institute of Computing Sciences, Shenzhen University, Shenzhen 518060, China 2.University of Edinburgh, Edinburg EH8 9AB, UK 3.Beijing Advanced Innovation Center for Big Data and Brain Computing, Beihang University, Beijing 100191, China
推荐引用方式 GB/T 7714	Yang Cao,Wen-Fei Fan,Teng-Fei Yuan. Bounded Evaluation: Querying Big Data with Bounded Resources[J]. International Journal of Automation and Computing,2020,17(4):502-526.
APA	Yang Cao,Wen-Fei Fan,&Teng-Fei Yuan.(2020).Bounded Evaluation: Querying Big Data with Bounded Resources.International Journal of Automation and Computing,17(4),502-526.
MLA	Yang Cao,et al."Bounded Evaluation: Querying Big Data with Bounded Resources".International Journal of Automation and Computing 17.4(2020):502-526.