BEAS: Bounded Evaluation of SQL Queries

ABSTRACT

We demonstrate BEAS, a prototype system for querying relations with bounded resources. BEAS advocates an unconventional query evaluation paradigm under an access schema A, which is a combination of cardinality constraints and associated indices. Given an SQL query Q and a dataset D, BEAS computes Q(D) by accessing a bounded fraction D_Q of D, such that Q(D_Q) = Q(D) and D_Q is determined by A and Q only, no matter how big D grows. It identifies D_Q by reasoning about the cardinality constraints of A, and fetches D_Q using the indices of A. We demonstrate the feasibility of bounded evaluation by walking through each functional component of BEAS. As a proof of concept, we demonstrate how BEAS conducts CDR analyses in telecommunication industry, compared with commercial database systems.

References

1. S. Abiteboul, R. Hull, and V. Vianu. Foundations of Databases. Addison-Wesley, 1995.
2. S. Agarwal, B. Mozafari, A. Panda, H. Milner, S. Madden, and I. Stoica. BlinkDB: Queries with bounded errors and bounded response times on very large data. In EuroSys, 2013. łooseness = -1
3. M. Armbrust, S. Tu, A. Fox, M. J. Franklin, D. A. Patterson, N. Lanham, B. Trushkowsky, and J. Trutna. PIQL: a performance insightful query language. In SIGMOD, 2010.
4. BEAS.sl http://139.196.196.250:8000/BEAS.
5. Y. Cao and W. Fan. An effective syntax for bounded relational queries. In SIGMOD, 2016.
6. Y. Cao, W. Fan, F. Geerts, and P. Lu. Bounded query rewriting using views. In PODS, 2016.
7. Y. Cao, W. Fan, T. Wo, and W. Yu. Bounded conjunctive queries. PVLDB, 2014.
8. W. Fan, F. Geerts, Y. Cao, and T. Deng. Querying big data by accessing small data. In PODS, 2015.
9. W. Fan, F. Geerts, and L. Libkin. On scale independence for querying big data. In PODS, 2014.
10. R. Ramakrishnan and J. Gehrke. Database Management Systems. McGraw-Hill Higher Education, 2000.
11. S. Zilberstein. Using anytime algorithms in intelligent systems. AI magazine, 17(3), 1996.

Index Terms

• Information systems

  • Data management systems

    • Database management system engines

      • Database query processing

        • Query optimization

        • Query planning