Relaxed currency and consistency: how to say "good enough" in SQL

ABSTRACT

Despite the widespread and growing use of asynchronous copies to improve scalability, performance and availability, this practice still lacks a firm semantic foundation. Applications are written with some understanding of which queries can use data that is not entirely current and which copies are "good enough"; however, there are neither explicit requirements nor guarantees. We propose to make this knowledge available to the DBMS through explicit currency and consistency (C&C) constraints in queries and develop techniques so the DBMS can guarantee that the constraints are satisfied. In this paper we describe our model for expressing C&C constraints, define their semantics, and propose SQL syntax. We explain how C&C constraints are enforced in MTCache, our prototype mid-tier database cache, including how constraints and replica update policies are elegantly integrated into the cost-based query optimizer. Consistency constraints are enforced at compile time while currency constraints are enforced at run time by dynamic plans that check the currency of each local replica before use and select sub-plans accordingly. This approach makes optimal use of the cache DBMS while at the same time guaranteeing that applications always get data that is "good enough" for their purpose.

REFERENCES

• 1: Rafael Alonso , Daniel Barbará , Hector Garcia-Molina , Soraya Abad, Quasi-Copies: Efficient Data Sharing for Information Retrieval Systems, Proceedings of the International Conference on Extending Database Technology: Advances in Database Technology, p.443-468, March 14-18, 1988
• 2: {ABK+03} M. Altinel, C. Bornhövd, S. Krishnamurthy, C. Mohan, H. Pirahesh, and B. Reinwald. Cache Tables: Paving The Way For An Adaptive Database Cache. In VLDB, 2003.
• 3: Christof Bornhövd , Mehmet Altinel , Sailesh Krishnamurthy , C. Mohan , Hamid Pirahesh , Berthold Reinwald, DBCache: middle-tier database caching for highly scalable e-business architectures, Proceedings of the 2003 ACM SIGMOD international conference on Management of data, June 09-12, 2003, San Diego, California [doi>10.1145/872757.872849]
• 4: Daniel Barbará , Hector Garcia-Molina, The Demarcation Protocol: A Technique for Maintaining Linear Arithmetic Constraints in Distributed Database Systems, Proceedings of the 3rd International Conference on Extending Database Technology: Advances in Database Technology, p.373-388, March 23-27, 1992
• 5: {BR02} L. Bright and L. Raschid. Using Latency-Recency Profiles for Data Delivery on the Web. In Proc. In VLDB, 2002.
• 6: Francis Chu , Joseph Y. Halpern , Praveen Seshadri, Least expected cost query optimization: an exercise in utility, Proceedings of the eighteenth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, p.138-147, May 31-June 03, 1999, Philadelphia, Pennsylvania, United States [doi>10.1145/303976.303990]
• 7: Donko Donjerkovic , Raghu Ramakrishnan, Probabilistic Optimization of Top N Queries, Proceedings of the 25th International Conference on Very Large Data Bases, p.411-422, September 07-10, 1999
• 8: Avigdor Gal, Obsolescent materialized views in query processing of enterprise information systems, Proceedings of the eighth international conference on Information and knowledge management, p.367-374, November 02-06, 1999, Kansas City, Missouri, United States [doi>10.1145/319950.320029]
• 9: Hector Garcia-Molina , Gio Wiederhold, Read-only transactions in a distributed database, ACM Transactions on Database Systems (TODS), v.7 n.2, p.209-234, June 1982 [doi>10.1145/319702.319704]
• 10: Rainer Gallersdörfer , Matthias Nicola, Improving Performance in Replicated Databases through Relaxed Coherency, Proceedings of the 21th International Conference on Very Large Data Bases, p.445-456, September 11-15, 1995
• 11: Jonathan Goldstein , Per-Åke Larson, Optimizing queries using materialized views: a practical, scalable solution, Proceedings of the 2001 ACM SIGMOD international conference on Management of data, p.331-342, May 21-24, 2001, Santa Barbara, California, United States
• 12: Yixiu Huang , Robert H. Sloan , Ouri Wolfson, Divergence caching in client-server architectures, Proceedings of the third international conference on on Parallel and distributed information systems, p.131-139, October 1994, Autin, Texas, United States
• 13: A. M. Kermarrec , I. Kuz , M. Van Steen , A. S. Tanenbaum, A Framework for Consistent, Replicated Web Objects, Proceedings of the The 18th International Conference on Distributed Computing Systems, p.276, May 26-29, 1998
• 14: {LC02} S. Weissman L. and P. Chrysanthis. Personalizing Information Gathering For Mobile Database Clients. In SAC, 2002.
• 15: Per-Åke Larson , Jonathan Goldstein , Jingren Zhou, MTCache: Transparent Mid-Tier Database Caching in SQL Server, Proceedings of the 20th International Conference on Data Engineering, p.177, March 30-April 02, 2004
• 16: {LR03} A. Labrinidis and N. Roussopoulos. Balancing Performance And Data Freshness In Web Database Servers. In VLDB, 2003.
• 17: Chris Olston , Boon Thau Loo , Jennifer Widom, Adaptive precision setting for cached approximate values, Proceedings of the 2001 ACM SIGMOD international conference on Management of data, p.355-366, May 21-24, 2001, Santa Barbara, California, United States
• 18: Chris Olston , Jennifer Widom, Offering a Precision-Performance Tradeoff for Aggregation Queries over Replicated Data, Proceedings of the 26th International Conference on Very Large Data Bases, p.144-155, September 10-14, 2000
• 19: Calton Pu , Avraham Leff, Replica control in distributed systems: as asynchronous approach, Proceedings of the 1991 ACM SIGMOD international conference on Management of data, p.377-386, May 29-31, 1991, Denver, Colorado, United States
• 20: {RBSS02} U. Röhm, K. Böhm, H. Schek, and H. Schuldt. FAS - a Freshness-Sensitive Coordination Middleware for a Cluster of OLAP Components. In VLDB, 2002.
• 21: Arie Segev , Weiping Fang, Currency-Based Updates to Distributed Materialized Views, Proceedings of the Sixth International Conference on Data Engineering, p.512-520, February 05-09, 1990
• 22: Len Seligman , Larry Kerschberg, A Mediator for Approximate Consistency: Supporting “GoodEnough” Materialized Views, Journal of Intelligent Information Systems, v.8 n.3, p.203-225, June 1997 [doi>10.1023/A:1008646507484]
• 23: {SR90} A. Sheth and M. Rusinkiewicz. Management Of Interdependent Data: Specifying Dependency And Consistency Requirements. In Workshop on the Management of ReplicatedData, pages 133--136, 1990.
• 24: Gio Wiederhold , Xiaolei Qian, Modeling Asynchrony in Distributed Databases, Proceedings of the Third International Conference on Data Engineering, p.246-250, February 03-05, 1987
• 25: Ouri Wolfson , Bo Xu , Sam Chamberlain , Liqin Jiang, Moving Objects Databases: Issues and Solutions, Proceedings of the 10th International Conference on Scientific and Statistical Database Management, p.111-122, July 01-03, 1998 [doi>10.1109/SSDM.1998.688116]
• 26: Haifeng Yu , Amin Vahdat, Efficient Numerical Error Bounding for Replicated Network Services, Proceedings of the 26th International Conference on Very Large Data Bases, p.123-133, September 10-14, 2000