skip to main content
research-article

Snapshot isolation and integrity constraints in replicated databases

Published: 02 July 2009 Publication History

Abstract

Database replication is widely used for fault tolerance and performance. However, it requires replica control to keep data copies consistent despite updates. The traditional correctness criterion for the concurrent execution of transactions in a replicated database is 1-copy-serializability. It is based on serializability, the strongest isolation level in a nonreplicated system. In recent years, however, Snapshot Isolation (SI), a slightly weaker isolation level, has become popular in commercial database systems. There exist already several replica control protocols that provide SI in a replicated system. However, most of the correctness reasoning for these protocols has been rather informal. Additionally, most of the work so far ignores the issue of integrity constraints. In this article, we provide a formal definition of 1-copy-SI using and extending a well-established definition of SI in a nonreplicated system. Our definition considers integrity constraints in a way that conforms to the way integrity constraints are handled in commercial systems. We discuss a set of necessary and sufficient conditions for a replicated history to be producible under 1-copy-SI. This makes our formalism a convenient tool to prove the correctness of replica control algorithms.

Supplementary Material

Lin Appendix (a11-lin-apndx.pdf)
Online appendix to snapshot isolation and integrity constraints in replicated databases. The appendix supports the information on article 11.

References

[1]
]]Adya, A. 1999. Weak consistency: A generalized theory and optimistic implementations for distributed transactions. Ph.D. thesis, MIT, Cambridge.
[2]
]]Adya, A., Liskov, B., and O'Neil, P. E. 2000. Generalized isolation level definitions. In Proceedings of the IEEE International Conference on Data Engineering (ICDE), 67--78.
[3]
]]Alomari, M., Cahill, M. J., Fekete, A., and Röhm, U. 2008. The cost of serializability on platforms that use snapshot isolation. In Proceedings of the IEEE International Conference on Data Engineering (ICDE), 576--585.
[4]
]]Amza, C., Cox, A. L., and Zwaenepoel, W. 2003. Distributed versioning: Consistent replication for scaling back-end databases of dynamic content Web sites. In Proceedings of the ACM/IFIP/USENIX International Middleware Conference, 282--302.
[5]
]]ANSI X3.135-1992. 1992. American National Standard for Information Systems—Database Language- SQL.
[6]
]]Berenson, H., Bernstein, P., Gray, J., Melton, J., O'Neil, E., and O'Neil, P. 1995. A critique of ANSI SQL isolation levels. In Proceedings of the ACM SIGMOD International Conference on Management of Data, 1--10.
[7]
]]Bernstein, P. A., Fekete, A., Guo, H., Ramakrishnan, R., and Tamma, P. 2006. Relaxed-currency serializability for middle-tier caching and replication. In Proceedings of the ACM SIGMOD International Conference on Management of Data, 599--610.
[8]
]]Bernstein, P. A., Hadzilacos, V., and Goodman, N. 1987. Concurrency Control and Recovery in Database Systems. Addison-Wesley.
[9]
]]Breitbart, Y., Komondoor, R., Rastogi, R., Seshadri, S., and Silberschatz, A. 1999. Update propagation protocols for replicated databases. In Proceedings of the ACM SIGMOD International Conference on Management of Data, 97--108.
[10]
]]Breitbart, Y. and Korth, H. F. 1997. Replication and consistency: Being lazy helps sometimes. In Proceedings of the ACM International Symposium on Principles of Database Systems (PODS), 173--184.
[11]
]]Cahill, M., Röhm, U., and Fekete, A. 2008. Serializable isolation for snapshot databases. In Proceedings of the ACM SIGMOD International Conference on Management of Data, 729--738.
[12]
]]Carey, M. J. and Livny, M. 1991. Conflict detection tradeoffs for replicated data. ACM Trans. Data. Syst. 16, 4, 703--746.
[13]
]]Cecchet, E., Marguerite, J., and Zwaenepoel, W. 2004. C-JDBC: Flexible database clustering middleware. In Proceedings of USENIX Annual Technical Conference, FREENIX Track. 9--18.
[14]
]]Chockler, G., Keidar, I., and Vitenberg, R. 2001. Group communication specifications: A comprehensive study. ACM Comput. Surv. 33, 4, 427--469.
[15]
]]Chundi, P., Rosenkrantz, D. J., and Ravi, S. S. 1996. Deferred updates and data placement in distributed databases. In Proceedings of the IEEE International Conference on Data Engineering (ICDE), 469--476.
[16]
]]Daudjee, K. and Salem, K. 2006. Lazy database replication with snapshot isolation. In Proceedings of International Conference on Very Large Data Bases (VLDB), 715--726.
[17]
]]Elnikety, S., Pedone, F., and Zwaenopoel, W. 2005. Database replication using generalized snapshot isolation. In Proceedings of the International Symposium on Reliable Distributed Systems (SRDS), 73--84.
[18]
]]Fekete, A., Liarokapis, D., O'Neil, E., O'Neil, P., and Shasha, D. 2005. Making snapshot isolation serializable. ACM Trans. Data. Syst. 30, 2, 492--528.
[19]
]]Gançarski, S., Naacke, H., Pacitti, E., and Valduriez, P. 2007. The leganet system: Freshness-Aware transaction routing in a database cluster. Inform. Syst. 32, 2, 320--343.
[20]
]]Holliday, J., Steinke, R. C., Agrawal, D., and Abbadi, A. E. 2003. Epidemic algorithms for replicated databases. IEEE Trans. Knowl. Data Engin. 15, 5, 1218--1238.
[21]
]]Kemme, B. and Alonso, G. 2000. A new approach to developing and implementing eager database replication protocols. ACM Trans. Data. Syst. 25, 3, 333--379.
[22]
]]Lin, Y., Kemme, B., Patiño-Martínez, M., and Jiménez-Peris, R. 2005. Middleware-based data replication providing snapshot isolation. In Proceedings of the ACM SIGMOD International Conference on Management of Data, 419--430.
[23]
]]Microsoft SQL Server 2005. 2007. SQL Server 2005 row versioning-based transaction isolation.
[24]
]]Muñoz-Escoí, F. D., Pla-Civera, J., Ruiz-Fuertes, M. I., Irún-Briz, L., Decker, H., Armendáriz-Iñigo, J. E., and González de Mendívil, J. R. 2006. Managing transaction conflicts in middleware-based database replication architectures. In Proceedings of the International Symposium on Reliable Distributed Systems (SRDS), 401--410.
[25]
]]Oracle Corporation. 2007. Oracle 11g Release 1.
[26]
]]Pacitti, E., Minet, P., and Simon, E. 1999. Fast algorithm for maintaining replica consistency in lazy master replicated databases. In Proceedings of the International Conference on Very Large Data Bases (VLDB), 126--137.
[27]
]]Patiño-Martínez, M., Jiménez-Peris, R., Kemme, B., and Alonso, G. 2005. MIDDLE-R: Consistent database replication at the middleware level. ACM Trans. Comput. Syst. 23, 4, 375--423.
[28]
]]Pedone, F., Guerraoui, R., and Schiper, A. 2003. The database state machine approach. Distrib. Parall. Data. 14, 1, 71--98.
[29]
]]Perez-Sorrosal, F., Patiño-Martínez, M., Jiménez-Peris, R., and Kemme, B. 2007. Consistent and scalable cache replication for multi-tier J2EE applications. In Proceedings of the ACM/IFIP/USENIX International Middleware Conference, 328--347.
[30]
]]Plattner, C. and Alonso, G. 2004. Ganymed: Scalable replication for transactional Web applications. In Proceedings of the ACM/IFIP/USENIX International Middleware Conference, 155--174.
[31]
]]Plattner, C., Alonso, G., and Özsu, M. T. 2008. Extending DBMSs with satellite databases. VLDB J. 17, 4, 657--682.
[32]
]]PostgreSQL. 2007. PostgreSQL, the world's most advanced open source database.
[33]
]]Röhm, U., Böhm, K., Schek, H.-J., and Schuldt, H. 2002. FAS - A freshness-sensitive coordination middleware for a cluster of OLAP components. In Proceedings of International Conference on Very Large Data Bases (VLDB), 754--765.
[34]
]]Schenkel, R., Weikum, G., Weißenberg, N., and Wu, X. 1999. Federated transaction management with snapshot isolation. In Proceedings of the International Workshop on Foundations of Models and Languages for Data and Objects (FMLDO) - Selected articles, 1--25.
[35]
]]Weikum, G. and Vossen, G. 2001. Transactional Information Systems. Morgan Kaufmann, Chapter 6.
[36]
]]Wu, S. and Kemme, B. 2005. Postgres-R(SI): Combining replica control with concurrency control based on snapshot isolation. In Proceedings of the IEEE International Conference on Data Engineering (ICDE), 422--433.

Cited By

View all
  • (2022)Elastic scalable transaction processing in LeanXcaleInformation Systems10.1016/j.is.2022.102043108:COnline publication date: 1-Sep-2022
  • (2019)RepliSmartProceedings of the ACM India Joint International Conference on Data Science and Management of Data10.1145/3297001.3297022(164-170)Online publication date: 3-Jan-2019
  • (2019)DynaStar: Optimized Dynamic Partitioning for Scalable State Machine Replication2019 IEEE 39th International Conference on Distributed Computing Systems (ICDCS)10.1109/ICDCS.2019.00145(1453-1465)Online publication date: Jul-2019
  • Show More Cited By

Index Terms

  1. Snapshot isolation and integrity constraints in replicated databases

    Recommendations

    Comments

    Information & Contributors

    Information

    Published In

    cover image ACM Transactions on Database Systems
    ACM Transactions on Database Systems  Volume 34, Issue 2
    June 2009
    210 pages
    ISSN:0362-5915
    EISSN:1557-4644
    DOI:10.1145/1538909
    Issue’s Table of Contents
    Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

    Publisher

    Association for Computing Machinery

    New York, NY, United States

    Publication History

    Published: 02 July 2009
    Revised: 01 December 2008
    Accepted: 01 November 2008
    Received: 01 October 2007
    Published in TODS Volume 34, Issue 2

    Permissions

    Request permissions for this article.

    Check for updates

    Author Tags

    1. Replication
    2. integrity constraints
    3. snapshot isolation

    Qualifiers

    • Research-article
    • Research
    • Refereed

    Funding Sources

    Contributors

    Other Metrics

    Bibliometrics & Citations

    Bibliometrics

    Article Metrics

    • Downloads (Last 12 months)9
    • Downloads (Last 6 weeks)2
    Reflects downloads up to 20 Feb 2025

    Other Metrics

    Citations

    Cited By

    View all
    • (2022)Elastic scalable transaction processing in LeanXcaleInformation Systems10.1016/j.is.2022.102043108:COnline publication date: 1-Sep-2022
    • (2019)RepliSmartProceedings of the ACM India Joint International Conference on Data Science and Management of Data10.1145/3297001.3297022(164-170)Online publication date: 3-Jan-2019
    • (2019)DynaStar: Optimized Dynamic Partitioning for Scalable State Machine Replication2019 IEEE 39th International Conference on Distributed Computing Systems (ICDCS)10.1109/ICDCS.2019.00145(1453-1465)Online publication date: Jul-2019
    • (2018)Analysing Snapshot IsolationJournal of the ACM10.1145/315239665:2(1-41)Online publication date: 31-Jan-2018
    • (2018)Concurrency Control for Replicated DatabasesEncyclopedia of Database Systems10.1007/978-1-4614-8265-9_433(566-574)Online publication date: 7-Dec-2018
    • (2018)Snapshot IsolationEncyclopedia of Database Systems10.1007/978-1-4614-8265-9_346(3513-3519)Online publication date: 7-Dec-2018
    • (2017)Posterior Snapshot Isolation2017 IEEE 33rd International Conference on Data Engineering (ICDE)10.1109/ICDE.2017.130(797-808)Online publication date: Apr-2017
    • (2017)Concurrency Control for Replicated DatabasesEncyclopedia of Database Systems10.1007/978-1-4899-7993-3_433-2(1-9)Online publication date: 24-Jan-2017
    • (2016)The end of slow networksProceedings of the VLDB Endowment10.14778/2904483.29044859:7(528-539)Online publication date: 1-Mar-2016
    • (2016)Analysing Snapshot IsolationProceedings of the 2016 ACM Symposium on Principles of Distributed Computing10.1145/2933057.2933096(55-64)Online publication date: 25-Jul-2016
    • Show More Cited By

    View Options

    Login options

    Full Access

    View options

    PDF

    View or Download as a PDF file.

    PDF

    eReader

    View online with eReader.

    eReader

    Figures

    Tables

    Media

    Share

    Share

    Share this Publication link

    Share on social media