Knowledge Commons of Institute of Automation，CAS
| Bounded Evaluation: Querying Big Data with Bounded Resources | |
| Yang Cao1; Wen-Fei Fan1,2,3; Teng-Fei Yuan1 | |
| 发表期刊 | International Journal of Automation and Computing
 |
| ISSN | 1476-8186 |
| 2020 | |
| 卷号 | 17期号:4页码:502-526 |
| 摘要 | 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 RAaggr, 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 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. |
| 关键词 | Bounded evaluation resource-bounded query processing effective syntax access schema boundedness. |
| DOI | 10.1007/s11633-020-1236-1 |
| 引用统计 | |
| 文献类型 | 期刊论文 |
| 条目标识符 | http://ir.ia.ac.cn/handle/173211/42275 |
| 专题 | 学术期刊_Machine Intelligence Research |
| 作者单位 | 1.University of Edinburgh, Edinburg EH8 9AB, UK 2.Shenzhen Institute of Computing Sciences, Shenzhen University, Shenzhen 518060, China 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. |
| 条目包含的文件 | 下载所有文件 | |||||
| 文件名称/大小 | 文献类型 | 版本类型 | 开放类型 | 使用许可 | ||
| IJAC-2020-02-034.pdf（2149KB） | 期刊论文 | 出版稿 | 开放获取 | CC BY-NC-SA | 浏览 下载 | |
除非特别说明，本系统中所有内容都受版权保护，并保留所有权利。
修改评论