Nikos Tsikoudis
ABSTRACT
One can audit SQL applications by running SQL programs over sequences of persistent snapshots, but care is needed to avoid wasteful duplicate computation. This paper describes the design, implementation, and performance of RID, the first language-independent optimization framework that eliminates duplicate computations in SQL programs running over low-level snapshots by exploiting snapshot metadata efficiently.
Supplemental Material
- Michael H. Bö hlen and Christian S. Jensen. 2018. Sequenced Semantics. In Encyclopedia of Database Systems, Second Edition. https://doi.org/10.1007/978--1--4614--8265--9_1053Google Scholar
- Ramesh Chandra, Taesoo Kim, Meelap Shah, Neha Narula, and Nickolai Zeldovich. 2011. Intrusion recovery for database-backed web applications. In Proceedings of the Twenty-Third ACM Symposium on Operating Systems Principles. ACM, 101--114.Google ScholarDigital Library
- Transaction Processing Performance Council. 2010. TPC-H: Decision Support Benchmark. http://www.tpc.org/tpchGoogle Scholar
- Anton Dignös, Michael H Böhlen, Johann Gamper, and Christian S Jensen. 2016. Extending the kernel of a relational DBMS with comprehensive support for sequenced temporal queries. ACM Transactions on Database Systems (TODS), Vol. 41, 4 (2016), 26.Google ScholarDigital Library
- Anton Dignös, Boris Glavic, Xing Niu, Michael Böhlen, and Johann Gamper. 2019. Snapshot Semantics for Temporal Multiset Relations. The VLDB Journal - The International Journal on Very Large Data Bases, Vol. 12, 6 (2019), 639 -- 652.Google Scholar
- Pradeep Kumar Gunda, Lenin Ravindranath, Chandramohan A Thekkath, Yuan Yu, and Li Zhuang. 2010. Nectar: Automatic Management of Data and Computation in Datacenters.. In OSDI, Vol. 10. 1--8.Google ScholarDigital Library
- Intel. 2010. Oracle Berkeley DB SQL API vs. SQLite API - Integration, Benefits and Differences. (October 2010).Google Scholar
- David Lomet, Roger Barga, Mohamed F Mokbel, and German Shegalov. 2006. Transaction time support inside a database engine. In 22nd International Conference on Data Engineering (ICDE'06). IEEE, 35--35.Google ScholarDigital Library
- David Lomet, Roger Barga, Mohamed F Mokbel, German Shegalov, Rui Wang, and Yunyue Zhu. 2005. Immortal DB: transaction time support for SQL server. In Proceedings of the 2005 ACM SIGMOD international conference on Management of data. ACM, 939--941.Google ScholarDigital Library
- David Lomet and Betty Salzberg. 1989. Access methods for multiversion data. Vol. 18. ACM.Google Scholar
- Donald Michie. 1968. Memo functions and machine learning. Nature, Vol. 218, 5136 (1968), 19.Google Scholar
- Soumyadeb Mitra, Marianne Winslett, Richard T. Snodgrass, Shashank Yaduvanshi, and Sumedh Ambokar. 2009. An Architecture for Regulatory Compliant Database Management. In Proceedings of the 25th International Conference on Data Engineering, ICDE 2009, March 29 2009 - April 2 2009, Shanghai, China. 162--173. https://doi.org/10.1109/ICDE.2009.69Google ScholarDigital Library
- Olson, M. A., Bostic, K. and Seltzer, M. I. 1999. Berkeley DB. In Proceedings of USENIX Annual Technical Conference, FREENIX Track. Monterey, CA, USA .Google Scholar
- Gultekin Ozsoyoglu and Richard T Snodgrass. 1995. Temporal and real-time databases: A survey. IEEE Transactions on Knowledge and Data Engineering, Vol. 7, 4 (1995), 513--532.Google ScholarDigital Library
- Betty Salzberg and Vassilis J Tsotras. 1999. Comparison of access methods for time-evolving data. ACM Computing Surveys (CSUR), Vol. 31, 2 (1999), 158--221.Google ScholarDigital Library
- Ross Shaull. 2013. A methodology for Retrospection Everywhere. Ph.D. Dissertation. Brandeis University.Google Scholar
- Ross Shaull, Liuba Shrira, and Barbara Liskov. 2014. A Modular and Efficient Past State System for Berkeley DB. In USENIX Annual Technical Conference. 157--168.Google Scholar
- Ross Shaull, Liuba Shrira, and Hao Xu. 2008. Skippy: a new snapshot indexing method for time travel in the storage manager. In Proceedings of the 2008 ACM SIGMOD international conference on Management of data. ACM, 637--648.Google ScholarDigital Library
- Cheng Tan, Lingfan Yu, Joshua B. Leners, and Michael Walfish. 2017. The Efficient Server Audit Problem, Deduplicated Re-execution, and the Web. In Proceedings of the 26th Symposium on Operating Systems Principles (SOSP '17). 546--564.Google ScholarDigital Library
- Abdullah Uz Tansel, James Clifford, Shashi Gadia, Sushil Jajodia, Arie Segev, and Richard Snodgrass. 1993. Temporal databases: theory, design, and implementation. Benjamin-Cummings Publishing Co., Inc.Google Scholar
- Nikos Tsikoudis. 2020. Retrospective Computations over Sets of Snapshots: Design, Implementation and Optimization. Ph.D. Dissertation. Brandeis University.Google Scholar
- Nikos Tsikoudis, Liuba Shrira, and Sara Cohen. 2018. RQL: Retrospective Computations over Snapshot Sets. In Proceedings of the 21th International Conference on Extending Database Technology, EDBT. 600--611.Google Scholar
Index Terms
- RID: Deduplicating Snapshot Computations
Recommendations
A critique of snapshot isolation
EuroSys '12: Proceedings of the 7th ACM european conference on Computer SystemsThe support for transactions is an essential part of a database management system (DBMS). Without this support, the developers are burdened with ensuring atomic execution of a transaction despite failures as well as concurrent accesses to the database ...
Concurrent updating transactions on versioned data
IDEAS '09: Proceedings of the 2009 International Database Engineering & Applications SymposiumModern database applications increasingly often require access to historical versions of the database. Storing such multiversion data in a single-version B+ -tree database index is inefficient, especially for key-range queries. In this article, we ...
Comments