Transactions in Page-Server Systems

• Robert K. Abbott and Hector Garcia-Molina. Scheduling real-time transactions. SIGMOD Record, 17(1):71–81, 1988a.

  Article  Google Scholar 

• Robert K. Abbott and Hector Garcia-Molina. Scheduling real-time transactions: a performance evaluation. In VLDB 1988, Proc. of the 14th Internat. Conf. on Very Large Data Bases, pages 1–12. Morgan Kaufmann, 1988b.

  Google Scholar 

• Robert K. Abbott and Hector Garcia-Molina. Scheduling real-time transactions with disk resident data. In VLDB 1989, Proc. of the 15th Internat. Conf. on Very Large Data Bases, pages 385–396. Morgan Kaufmann, 1989.

  Google Scholar 

• Devesh Agrawal, Deepak Ganesan, Ramesh K. Sitaraman, Yanlei Diao, and Shashi Singh. Lazy-adaptive tree: An optimized index structure for flash devices. Proc. of the VLDB Endowment, 2(1):361–372, 2009.

  Google Scholar 

• Divyakant Agrawal, Amr El Abbadi, Richard Jeffers, and Lijing Lin. Ordered shared locks for real-time databases. VLDB J., 4(1):87–126, 1995.

  Google Scholar 

• Gustavo Alonso, Radek Vingralek, Divyakant Agrawal, Yuri Breitbart, Amr El Abbadi, Hans-Jörg Schek, and Gerhard Weikum. A unified approach to concurrency control and transaction recovery (extended abstract). In Advances in Database Technology—EDBT’94, Proc. of the 4th Internat. Conf. on Extending Database Technology, volume 779 of Lecture Notes in Computer Science, pages 123–130. Springer, 1994.

  Google Scholar 

• Lars Arge. The buffer tree: A new technique for optimal I/O-algorithms (extended abstract). In WADS 1995, Proc. of the 4th Internat. Workshop on Algorithms and Data Structures, volume 955 of Lecture Notes in Computer Science, pages 334–345. Springer, 1995.

  Google Scholar 

• Lars Arge. The buffer tree: A technique for designing batched external data structures. Algorithmica, 37(1):1–24, 2003.

  Article  MATH  MathSciNet  Google Scholar 

• Morton M. Astrahan, Mike W. Blasgen, Donald D. Chamberlin, Kapali P. Eswaran, Jim N. Gray, Patricia P. Griffiths, W. Frank King III, Raymond A. Lorie, Paul R. McJones, James W. Mehl, Gianfranco R. Putzolu, Irving L. Traiger, Bradford W. Wade, and Vera Watson. System R: Relational approach to database management. ACM Trans. Database Syst., 1(2):97–137, 1976.

  Google Scholar 

• Manos Athanassoulis, Anastasia Ailamaki, Shimin Chen, Phillip B. Gibbons, and Radu Stoica. Flash in a DBMS: Where and how? IEEE Data Eng. Bull., 33(4):28–34, 2010.

  Google Scholar 

• Jason Baker, Chris Bond, James Corbett, J. J. Furman, Andrey Khorlin, James Larson, Jean-Michel Leon, Yawei Li, Alexander Lloyd, and Vadim Yushprakh. Megastore: Providing scalable, highly available storage for interactive services. In CIDR 2011, Proc. of the Fifth Biennial Conf. on Innovative Data Systems Research, pages 223–234, 2011.

  Google Scholar 

• Rudolf Bayer and Edward M. McCreight. Organization and maintenance of large ordered indices. Acta Inf., 1:173–189, 1972.

  Google Scholar 

• Rudolf Bayer and Mario Schkolnick. Concurrency of operations on b-trees. Acta Inf., 9:1–21, 1977.

  Google Scholar 

• Rudolf Bayer and Karl Unterauer. Prefix b-trees. ACM Trans. Database Syst., 2(1):11–26, 1977.

  Google Scholar 

• Rudolf Bayer, Hans Heller, and Angelika Reiser. Parallelism and recovery in database systems. ACM Trans. Database Syst., 5(2):139–156, 1980.

  Google Scholar 

• Bruno Becker, Stephan Gschwind, Thomas Ohler, Bernhard Seeger, and Peter Widmayer. An asymptotically optimal multiversion B-tree. VLDB J., 5 (4):264–275, 1996.

  Google Scholar 

• Hal Berenson, Philip A. Bernstein, Jim Gray, Jim Melton, Elizabeth J. O’Neil, and Patrick E. O’Neil. A critique of ANSI SQL isolation levels. In Proc. of the 1995 ACM SIGMOD Internat. Conf. on Management of Data, pages 1–10. ACM Press, 1995.

  Google Scholar 

• Philip A. Bernstein. Transaction processing monitors. Commun. ACM, 33 (11):75–86, 1990.

  Article  Google Scholar 

• Philip A. Bernstein and Nathan Goodman. Multiversion concurrency control—theory and algorithms. ACM Trans. Database Syst., 8(4): 465–483, 1983.

  Google Scholar 

• Philip A. Bernstein and Eric Newcomer. Principles of Transaction Processing for Systems Professionals. Morgan Kaufmann, 1996.

  Google Scholar 

• Philip A. Bernstein and Eric Newcomer. Transaction Processing. Second Edition. Morgan Kaufmann, 2009.

  Google Scholar 

• Philip A. Bernstein, David W. Shipman, and James B. Rothnie. Concurrency control in a system for distributed databases (SDD-1). ACM Trans. Database Syst., 5(1):18–51, 1980.

  Google Scholar 

• Philip A. Bernstein, Vassco Hadzilacos, and Nathan Goodman. Concurrency Control and Recovery in Database Systems. Addison Wesley, 1987.

  Google Scholar 

• Philip A. Bernstein, Colin W. Reid, and Sudipto Das. Hyder—a transactional record manager for shared flash. In CIDR 2011, Proc. of the Fifth Biennial Conf. on Innovative Data Systems Research, pages 9–20, 2011.

  Google Scholar 

• Alexandros Biliris. Operation specific locking in b-trees. In Proc. of the Sixth ACM SIGACT-SIGMOD-SIGART Symp. on Principles of Database Systems, pages 159–169. ACM Press, 1987.

  Google Scholar 

• Mike W. Blasgen, Morton M. Astrahan, Donald D. Chamberlin, Jim Gray, W. Frank King III, Bruce G. Lindsay, Raymond A. Lorie, James W. Mehl, Thomas G. Price, Gianfranco R. Putzolu, Mario Schkolnick, Patricia G. Selinger, Donald R. Slutz, H. Raymond Strong, Irving L. Traiger, Bradford W. Wade, and Robert A. Yost. System R: An architectural overview. IBM Systems Journal, 20(1):41–62, 1981.

  Google Scholar 

• Mike W. Blasgen, Morton M. Astrahan, Donald D. Chamberlin, Jim Gray, W. Frank King III, Bruce G. Lindsay, Raymond A. Lorie, James W. Mehl, Thomas G. Price, Gianfranco R. Putzolu, Mario Schkolnick, Patricia G. Selinger, Donald R. Slutz, H. Raymond Strong, Irving L. Traiger, Bradford W. Wade, and Robert A. Yost. System R: An architectural overview. IBM Systems Journal, 38(2/3):375–396, 1999.

  Google Scholar 

• Mark R. Brown and Robert Endre Tarjan. Design and analysis of a data structure for representing sorted lists. SIAM J. Comput., 9(3):594–614, 1980.

  Google Scholar 

• Michael J. Cahill, Uwe Röhm, and Alan David Fekete. Serializable isolation for snapshot databases. ACM Trans. Database Syst., 34(4), 2009.

  Google Scholar 

• Michael J. Carey, Michael J. Franklin, and Markos Zaharioudakis. Fine-grained sharing in a page server OODBMS. In Proc. of the 1994 ACM SIGMOD Internat. Conf. on Management of Data, pages 359–370. ACM Press, 1994.

  Google Scholar 

• Rick Cattell. Scalable SQL and NoSQL data stores. SIGMOD Record, 39 (4):12–27, 2010.

  Article  Google Scholar 

• Donald D. Chamberlin, Morton M. Astrahan, Mike W. Blasgen, Jim Gray, W. Frank King III, Bruce G. Lindsay, Raymond A. Lorie, James W. Mehl, Thomas G. Price, Gianfranco R. Putzolu, Patricia G. Selinger, Mario Schkolnick, Donald R. Slutz, Irving L. Traiger, Bradford W. Wade, and Robert A. Yost. A history and evaluation of System R. Commun. ACM, 24(10):632–646, 1981.

  Google Scholar 

• Fay Chang, Jeffrey Dean, Sanjay Ghemawat, Wilson C. Hsieh, Deborah A. Wallach, Mike Burrows, Tushar Chandra, Andrew Fikes, and Robert E. Gruber. Bigtable: A distributed storage system for structured data. ACM Trans. Comput. Syst., 26(2):4:1–4:26, 2008.

  Google Scholar 

• Feng Chen, David A. Koufaty, and Xiaodong Zhang. Understanding intrinsic characteristics and system implications of flash memory based solid state drives. In Proc. of the Eleventh Internat. Joint Conf. on Measurement and Modeling of Computer Systems, SIGMETRICS/Performance, pages 181–192. ACM Press, 2009.

  Google Scholar 

• Jianjun Chen, Chris Douglas, Michi Mutsuzaki, Patrick Quaid, Raghu Ramakrishnan, Sriram Rao, and Russell Sears. Walnut: a unified cloud object store. In Proc. of the 2012 ACM SIGMOD Internat. Conf. on Management of Data, pages 743–754. ACM Press, 2012.

  Google Scholar 

• Douglas Comer. The ubiquitous b-tree. ACM Comput. Surv., 11(2):121–137, 1979.

  Google Scholar 

• Sudipto Das, Divyakant Agrawal, and Amr El Abbadi. G-store: a scalable data store for transactional multi key access in the cloud. In SoCC’10, Proc. of the 1st ACM Symp. on Cloud Computing, pages 163–174, 2010.

  Google Scholar 

• David J. DeWitt, Randy H. Katz, Frank Olken, Leonard D. Shapiro, Michael Stonebraker, and David A. Wood. Implementation techniques for main memory database systems. In Proc. of the 1984 ACM SIGMOD Internat. Conf. on Management of data, pages 1–8. ACM Press, 1984.

  Google Scholar 

• David J. DeWitt, Philippe Futtersack, David Maier, and Fernando Vélez. A study of three alternative workstation-server architectures for object oriented database systems. In VLDB 1990, Proc. of the 16th Internat. Conf. on Very Large Data Bases, pages 107–121, 1990.

  Google Scholar 

• Kapali P. Eswaran, Jim Gray, Raymond A. Lorie, and Irving L. Traiger. On the notions of consistency and predicate locks. Technical report, IBM Research Laboratory, San Jose, Nov. 1974.

  Google Scholar 

• Kapali P. Eswaran, Jim Gray, Raymond A. Lorie, and Irving L. Traiger. The notions of consistency and predicate locks in a database system. Commun. ACM, 19(11):624–633, 1976.

  Article  MATH  MathSciNet  Google Scholar 

• Georgios Evangelidis, David B. Lomet, and Betty Salzberg. The hB-Pi-tree: A multi-attribute index supporting concurrency, recovery and node consolidation. VLDB J., 6(1):1–25, 1997.

  Google Scholar 

• Alan Fekete, Dimitrios Liarokapis, Elizabeth J. O’Neil, Patrick E. O’Neil, and Dennis Shasha. Making snapshot isolation serializable. ACM Trans. Database Syst., 30(2):492–528, 2005.

  Google Scholar 

• Michael J. Franklin, Michael J. Zwilling, C. K. Tan, Michael J. Carey, and David J. DeWitt. Crash recovery in client-server EXODUS. In Proc. of the 1992 ACM SIGMOD Internat. Conf. on Management of Data, pages 165–174. ACM Press, 1992.

  Google Scholar 

• Michael J. Franklin, Björn Thór Jónsson, and Donald Kossmann. Performance tradeoffs for client-server query processing. In Proc. of the 1996 ACM SIGMOD Internat. Conf. on Management of Data, pages 149–160. ACM Press, 1996.

  Google Scholar 

• Michael J. Franklin, Michael J. Carey, and Miron Livny. Transactional client-server cache consistency: Alternatives and performance. ACM Trans. Database Syst., 22(3):315–363, 1997.

  Google Scholar 

• Ada Wai-Chee Fu and Tiko Kameda. Concurrency control of nested transactions accessing B-trees. In Proc. of the Eighth ACM SIGACT-SIGMOD-SIGART Symp. on Principles of Database Systems, pages 270–285. ACM Press, 1989.

  Google Scholar 

• Seth Gilbert and Nancy A. Lynch. Brewer’s conjecture and the feasibility of consistent, available, partition-tolerant web services. SIGACT News, 33 (2), 2002.

  Google Scholar 

• Goetz Graefe. Sorting and indexing with partitioned B-trees. In CIDR 2003, Proc. of the First Biennial Conf. on Innovative Data Systems Research, 2003a.

  Google Scholar 

• Goetz Graefe. Partitioned B-trees—a user’s guide. In BTW 2003, Datenbanksysteme für Business, Technologie und Web, Tagungsband der 10. BTW-Konferenz, pages 668–671, 2003b.

  Google Scholar 

• Goetz Graefe. Write-optimized B-trees. In VLDB 2004, Proc. of the 30th Internat. Conf. on Very Large Data Bases, pages 672–683. Morgan Kaufmann, 2004.

  Google Scholar 

• Goetz Graefe. A survey of B-tree locking techniques. ACM Trans. Database Syst., 35(3):16:1–26, 2010.

  Google Scholar 

• Goetz Graefe. Modern B-tree techniques. Foundations and Trends in Databases, 3(4):203–402, 2011.

  Article  Google Scholar 

• Goetz Graefe. A survey of B-tree logging and recovery techniques. ACM Trans. Database Syst., 37(1):1:1–35, 2012.

  Google Scholar 

• Goetz Graefe, Hideaki Kimura, and Harumi A. Kuno. Foster B-trees. ACM Trans. Database Syst., 37(3):17:1–29, 2012.

  Google Scholar 

• Jim Gray. Notes on database operating systems. In Operating Systems: An Advanced Course, volume 60 of Lecture Notes in Computer Science, pages 393–481. Springer, 1978.

  Google Scholar 

• Jim Gray. A transaction model. In Automata, Languages and Programming, Proc. of the 7th Colloquium, volume 85 of Lecture Notes in Computer Science, pages 282–298. Springer, 1980.

  Google Scholar 

• Jim Gray. The transaction concept: Virtues and limitations. In VLDB 1981, Proc. of the 7th Internat. Conf. on Very Large Data Bases, pages 144–154. IEEE Computer Society, 1981.

  Google Scholar 

• Jim Gray and Leslie Lamport. Consensus on transaction commit. ACM Trans. Database Syst., 31(1):133–160, 2006.

  Google Scholar 

• Jim Gray and Andreas Reuter. Transaction Processing: Concepts and Techniques. Morgan Kaufmann, 1993.

  Google Scholar 

• Jim Gray, Raymond A. Lorie, Gianfranco R. Putzolu, and Irving L. Traiger. Granularity of locks in a large shared data base. In VLDB 1975, Proc. of the Internat. Conf. on Very Large Data Bases, pages 428–451. ACM, 1975.

  Google Scholar 

• Jim Gray, Raymond A. Lorie, Gianfranco R. Putzolu, and Irving L. Traiger. Granularity of locks and degrees of consistency in a shared data base. In IFIP Working Conf. on Modelling in Data Base Management Systems, pages 365–394, 1976.

  Google Scholar 

• Jim Gray, Paul R. McJones, Mike W. Blasgen, Bruce G. Lindsay, Raymond A. Lorie, Thomas G. Price, Gianfranco R. Putzolu, and Irving L. Traiger. The recovery manager of the System R database manager. ACM Comput. Surv., 13(2):223–243, 1981.

  Google Scholar 

• Jim Gray, Pat Helland, Patrick E. O’Neil, and Dennis Shasha. The dangers of replication and a solution. In Proc. of the 1996 ACM SIGMOD Internat. Conf. on Management of Data, pages 173–182. ACM Press, 1996.

  Google Scholar 

• Antonin Guttman. R-trees: a dynamic index structure for spatial searching. In Proc. of the 1984 ACM SIGMOD Internat. Conf. on Management of data, pages 47–57. ACM Press, 1984.

  Google Scholar 

• Tuukka Haapasalo. Accessing Multiversion Data in Database Transactions. PhD thesis, Department of Computer Science and Engineering, Aalto University School of Science and Technology, Espoo, Finland, 2010. http://lib.tkk.fi/Diss/2010/isbn9789526033600/.

• Tuukka Haapasalo, Ibrahim Jaluta, Bernhard Seeger, Seppo Sippu, and Eljas Soisalon-Soininen. Transactions on the multiversion B⁺-tree. In EDBT 2009, Proc. of the 12th Internat. Conf. on Extending Database Technology, volume 360 of ACM International Conference Proceeding Series, pages 1064–1075. ACM Press, 2009a.

  Google Scholar 

• Tuukka Haapasalo, Ibrahim Jaluta, Seppo Sippu, and Eljas Soisalon-Soininen. Concurrent updating transactions on versioned data. In IDEAS 2009, Proc. of the Internat. Database Engineering and Applications Symp., pages 77–87. ACM Press, 2009b.

  Google Scholar 

• Tuukka Haapasalo, Ibrahim Jaluta, Seppo Sippu, and Eljas Soisalon-Soininen. On the recovery of R-trees. IEEE Trans. Knowl. Data Eng., 25(1):145–157, 2013.

  Google Scholar 

• Ibrahim Jaluta. B-Tree Concurrency Control and Recovery in a Client-Server Database Management System. PhD thesis, Department of Computer Science and Engineering, Helsinki University of Technology, Espoo, Finland, 2002. http://lib.tkk.fi/Diss/2002/isbn9512257068/.

• Ibrahim Jaluta and Dibyendu Majumda. Efficient space management for B-tree structure-modification operations. In ICTTA’06, Proc. of the 2nd Internat. Conf. on Information and Communication Technologies, pages 2909–2912, 2006.

  Google Scholar 

• Ibrahim Jaluta, Seppo Sippu, and Eljas Soisalon-Soininen. Recoverable B⁺-trees in centralized database management systems. Internat. J. of Applied Science & Computations, 10(3):160–181, 2003.

  Google Scholar 

• Ibrahim Jaluta, Seppo Sippu, and Eljas Soisalon-Soininen. Concurrency control and recovery for balanced B-link trees. VLDB J., 14(2):257–277, 2005.

  Google Scholar 

• Ibrahim Jaluta, Seppo Sippu, and Eljas Soisalon-Soininen. B-tree concurrency control and recovery in page-server database systems. ACM Trans. Database Syst., 31(1):82–132, 2006.

  Google Scholar 

• Christian S. Jensen and David B. Lomet. Transaction timestamping in (temporal) databases. In VLDB 2001, Proc. of 27th Internat. Conf. on Very Large Data Bases, pages 441–450. Morgan Kaufmann, 2001.

  Google Scholar 

• Christopher M. Jermaine, Edward Omiecinski, and Wai Gen Yee. The partitioned exponential file for database storage management. VLDB J., 16(4):417–437, 2007.

  Google Scholar 

• Ricardo Jiménez-Peris, Marta Patiño-Martínez, Gustavo Alonso, and Bettina Kemme. Are quorums an alternative for data replication? ACM Trans. Database Syst., 28(3):257–294, 2003.

  Google Scholar 

• Ryan Johnson, Ippokratis Pandis, Radu Stoica, Manos Athanassoulis, and Anastasia Ailamaki. Aether: A scalable approach to logging. Proc. of the VLDB Endowment, 3(1):681–692, 2010.

  Google Scholar 

• Ryan Johnson, Ippokratis Pandis, Radu Stoica, Manos Athanassoulis, and Anastasia Ailamaki. Scalability of write-ahead logging on multicore and multisocket hardware. VLDB J., 21(2):239–263, 2012.

  Google Scholar 

• Theodore Johnson and Dennis Shasha. B-trees with inserts and deletes: Why free-at-empty is better than merge-at-half. J. Comput. Syst. Sci., 47(1): 45–76, 1993.

  Google Scholar 

• Martin V. Jørgensen, René B. Rasmussen, Simonas Šaltenis, and Carsten Schjønning. Fb-tree: a B⁺-tree for flash-based SSDs. In IDEAS 2011, Proc. of the 15th Internat. Database Engineering and Applications Symp., pages 34–42. ACM, 2011.

  Google Scholar 

• Michael Kifer, Arthur Bernstein, and Philip M. Lewis. Database Systems: An Application-Oriented Approach. Second Edition. Pearson Addison-Wesley, 2006.

  Google Scholar 

• Donald E. Knuth. The Art of Computer Programming, Volume III: Sorting and Searching. Addison-Wesley, 1973.

  Google Scholar 

• Marcel Kornacker, C. Mohan, and Joseph M. Hellerstein. Concurrency and recovery in generalized search trees. In Proc. of the 1997 ACM SIGMOD Internat. Conf. on Management of Data, pages 62–72. ACM Press, 1997.

  Google Scholar 

• Yat-Sang Kwong and Derick Wood. A new method for concurrency in B-trees. IEEE Trans. Software Eng., 8(3):211–222, 1982.

  Google Scholar 

• Leslie Lamport. The part-time parliament. ACM Trans. Database Syst., 16 (2):133–169, 1998.

  Google Scholar 

• Butler W. Lampson and Howard E. Sturgis. Crash recovery in a distributed data storage system. Technical report, Computer Science Laboratory, Xerox, Palo Alto Research Center, 1976.

  Google Scholar 

• Vladimir Lanin and Dennis Shasha. A symmetric concurrent b-tree algorithm. In Proc. of the Fall Joint Computer Conference, pages 380–389. IEEE Computer Society, 1986.

  Google Scholar 

• Philip L. Lehman and S. Bing Yao. Efficient locking for concurrent operations on b-trees. ACM Trans. Database Syst., 6(4):650–670, 1981.

  Google Scholar 

• Justin J. Levandoski, David B. Lomet, and Sudipta Sengupta. The Bw-tree: A B-tree for new hardware platforms. In ICDE 2013, Proc. of the 29th IEEE Internat. Conf. on Data Engineering, pages 302–313. IEEE Computer Society, 2013.

  Google Scholar 

• Yinan Li, Bingsheng He, Qiong Luo, and Ke Yi. Tree indexing on flash disks. In ICDE 2009, Proc. of the 25th Internat. Conf. on Data Engineering, pages 1303–1306. IEEE Computer Society, 2009.

  Google Scholar 

• Yinan Li, Bingsheng He, Jun Yang, Qiong Luo, and Ke Yi. Tree indexing on solid state drives. Proc. of the VLDB Endowment, 3(1):1195–1206, 2010.

  Google Scholar 

• Timo Lilja, Riku Saikkonen, Seppo Sippu, and Eljas Soisalon-Soininen. Online bulk deletion. In ICDE 2007, Proc. of the 23rd IEEE Internat. Conf. on Data Engineering, pages 956–965. IEEE Computer Society, 2007.

  Google Scholar 

• Yi Lin, Bettina Kemme, Ricardo Jiménez-Peris, Marta Patiño-Martínez, and José Enrique Armendáriz-Iñigo. Snapshot isolation and integrity constraints in replicated databases. ACM Trans. Database Syst., 34(2), 2009.

  Google Scholar 

• David Lomet. Advanced recovery techniques in practice. In Vijay Kumar and Meichun Hsu, editors, Recovery Mechanisms in Database Systems, pages 697–710. Prentice Hall, 1998.

  Google Scholar 

• David B. Lomet. MLR: A recovery method for multi-level systems. In Proc. of the 1992 ACM SIGMOD Internat. Conf. on Management of Data, pages 185–194. ACM Press, 1992.

  Google Scholar 

• David B. Lomet. Key range locking strategies for improved concurrency. In VLDB 1993, Proc. of the 19th Internat. Conf. on Very Large Data Bases, pages 655–664. Morgan Kaufmann, 1993.

  Google Scholar 

• David B. Lomet. The evolution of effective B-tree: Page organization and techniques: A personal account. SIGMOD Record, 30(3):64–69, 2001.

  Article  Google Scholar 

• David B. Lomet. Simple, robust and highly concurrent B-trees with node deletion. In ICDE 2004, Proc. of the 20th Internat. Conf. on Data Engineering, pages 18–28. IEEE Computer Society, 2004.

  Google Scholar 

• David B. Lomet and Feifei Li. Improving transaction-time DBMS performance and functionality. In ICDE 2009, Proc. of the 25th Internat. Conf. on Data Engineering, pages 581–591. IEEE Computer Society, 2009.

  Google Scholar 

• David B. Lomet and Betty Salzberg. Access methods for multiversion data. In Proc. of the 1989 ACM SIGMOD Internat. Conf. on Management of Data, pages 315–324. ACM Press, 1989.

  Google Scholar 

• David B. Lomet and Betty Salzberg. Access method concurrency with recovery. In Proc. of the 1992 ACM SIGMOD Internat. Conf. on Management of Data, pages 351–360. ACM Press, 1992.

  Google Scholar 

• David B. Lomet and Betty Salzberg. Exploiting a history database for backup. In VLDB 1993, Proc. of the 19th Internat. Conf. on Very Large Data Bases, pages 380–390. Morgan Kaufmann, 1993.

  Google Scholar 

• David B. Lomet and Betty Salzberg. Concurrency and recovery for index trees. VLDB J., 6(3):224–240, 1997.

  Google Scholar 

• David B. Lomet, Roger S. Barga, Mohamed F. Mokbel, German Shegalov, Rui Wang, and Yunyue Zhu. Immortal DB: Transaction time support for SQL server. In Proc. of the 2005 ACM SIGMOD Internat. Conf. on Management of Data, pages 939–941. ACM Press, 2005a.

  Google Scholar 

• David B. Lomet, Richard T. Snodgrass, and Christian S. Jensen. Using the lock manager to choose timestamps. In IDEAS 2005, Proc. of the 9th Internat. Database Engineering and Applications Symp., pages 357–368. IEEE Computer Society, 2005b.

  Google Scholar 

• David B. Lomet, Roger S. Barga, Mohamed F. Mokbel, German Shegalov, Rui Wang, and Yunyue Zhu. Transaction time support inside a database engine. In ICDE 2006, Proc. of the 22nd Internat. Conf. on Data Engineering, page 35. IEEE Computer Society, 2006.

  Google Scholar 

• David B. Lomet, Mingsheng Hong, Rimma V. Nehme, and Rui Zhang. Transaction time indexing with version compression. Proc. of the VLDB Endowment, 1(1), 2008.

  Google Scholar 

• Raymond A. Lorie. Physical integrity in a large segmented database. ACM Trans. Database Syst., 2(1):91–104, 1977.

  Google Scholar 

• C. Mohan. ARIES/KVL: A key-value locking method for concurrency control of multiaction transactions operating on B-Tree indexes. In VLDB 1990, Proc. of the 16th Internat. Conf. on Very Large Data Bases, pages 392–405. Morgan Kaufmann, 1990a.

  Google Scholar 

• C. Mohan. Commit_LSN: A novel and simple method for reducing locking and latching in transaction processing systems. In VLDB 1990, Proc. of the 16th Internat. Conf. on Very Large Data Bases, pages 406–418. Morgan Kaufmann, 1990b.

  Google Scholar 

• C. Mohan. ARIES/LHS: A concurrency control and recovery method using write-ahead logging for linear hashing with separators. In ICDE 1993, Proc. of the 9th Internat. IEEE Conf. on Data Engineering, pages 243–252. IEEE Computer Society, 1993a.

  Google Scholar 

• C. Mohan. A cost-effective method for providing improved data availability during DBMS restart recovery after a failure. In VLDB 1993, Proc. of the 19th Internat. Conf. on Very Large Data Bases, pages 368–379. Morgan Kaufmann, 1993b.

  Google Scholar 

• C. Mohan. Concurrency control and recovery methods for B⁺-Tree indexes: ARIES/KVL and ARIES/IM. In Vijay Kumar, editor, Performance of Concurrency Control Mechanisms in Centralized Database Systems, pages 248–306. Prentice Hall, 1996a.

  Google Scholar 

• C. Mohan. Commit_LSN: A novel and simple method for reducing locking and latching in transaction processing systems. In Vijay Kumar, editor, Performance of Concurrency Control Mechanisms in Centralized Database Systems, pages 307–335. Prentice Hall, 1996b.

  Google Scholar 

• C. Mohan. Repeating history beyond ARIES. In VLDB 1999, Proc. of the 25th Internat. Conf. on Very Large Data Bases, pages 1–17. Morgan Kaufmann, 1999.

  Google Scholar 

• C. Mohan. An efficient method for performing record deletions and updates using index scans. In VLDB 2002, Proc. of the 28th Internat. Conf. on Very Large Data Bases, pages 940–949. Morgan Kaufmann, 2002.

  Google Scholar 

• C. Mohan. History repeats itself: Sensible and NonsenSQL aspects of the NoSQL hoopla. In EDBT 2013, Proc. of the 16th Internat. Conf. on Database Technology, pages 11–16. ACM Press, 2013.

  Google Scholar 

• C. Mohan and Frank E. Levine. ARIES/IM: An efficient and high concurrency index management method using write-ahead logging. In Proc. of the 1992 ACM SIGMOD Internat. Conf. on Management of Data, pages 371–380. ACM Press, 1992.

  Google Scholar 

• C. Mohan and Inderpal Narang. Recovery and coherency-control protocols for fast intersystem page transfer and fine-granularity locking in a shared disks transaction environment. In VLDB 1991, Proc. of the 17th Internat. Conf. on Very Large Data Bases, pages 193–207. Morgan Kaufmann, 1991.

  Google Scholar 

• C. Mohan and Inderpal Narang. Algorithms for creating indexes for very large tables without quiescing updates. In Proc. of the 1992 ACM SIGMOD Internat. Conf. on Management of Data, pages 361–370. ACM Press, 1992.

  Google Scholar 

• C. Mohan and Inderpal Narang. ARIES/CSA: A method for database recovery in client-server architectures. In Proc. of the 1994 ACM SIGMOD Internat. Conf. on Management of Data, pages 55–66. ACM Press, 1994.

  Google Scholar 

• C. Mohan and Hamid Pirahesh. ARIES-RRH: Restricted repeating of history in the ARIES transaction recovery method. In ICDE 1991, Proc. of the 7th Internat. IEEE Conf. on Data Engineering, pages 718–727. IEEE Computer Society, 1991.

  Google Scholar 

• C. Mohan, Bruce G. Lindsay, and Ron Obermarck. Transaction management in the R^∗ distributed database management system. ACM Trans. Database Syst., 11(4):378–396, 1986.

  Google Scholar 

• C. Mohan, Donald J. Haderle, Yun Wang, and Josephine M. Cheng. Single table access using multiple indexes: Optimization, execution, and concurrency control techniques. In Advances in Database Technology—EDBT’90, Proc. of the Internat. Conf. on Extending Database Technology, volume 416 of Lecture Notes in Computer Science, pages 29–43. Springer, 1990.

  Google Scholar 

• C. Mohan, Donald J. Haderle, Bruce G. Lindsay, Hamid Pirahesh, and Peter M. Schwarz. ARIES: A transaction recovery method supporting fine-granularity locking and partial rollbacks using write-ahead logging. ACM Trans. Database Syst., 17(1):94–162, 1992a.

  Google Scholar 

• C. Mohan, Hamid Pirahesh, and Raymond A. Lorie. Efficient and flexible methods for transient versioning of records to avoid locking by read-only transactions. In Proc. of the 1992 ACM SIGMOD Internat. Conf. on Management of Data, pages 124–133. ACM Press, 1992b.

  Google Scholar 

• C. Mohan, Kent Treiber, and Ron Obermarck. Algorithms for the management of remote backup data bases for disaster recovery. In ICDE 1993, Proc. of the 9th Internat. IEEE Conf. on Data Engineering, pages 511–518. IEEE Computer Society, 1993.

  Google Scholar 

• Yehudit Mond and Yoav Raz. Concurrency control in B⁺-trees databases using preparatory operations. In VLDB 1985, Proc. of the 11th Internat. Conf. on Very Large Data Bases, pages 331–334. Morgan Kaufmann, 1985.

  Google Scholar 

• Patrick E. O’Neil, Edward Cheng, Dieter Gawlick, and Elizabeth J. O’Neil. The log-structured merge-tree (LSM-tree). Acta Inf., 33(4):351–385, 1996.

  Google Scholar 

• M. Tamer Özsu and Patrick Valduriez. Principles of Distributed Database Systems. Third Edition. Springer, 2011.

  Google Scholar 

• Christos H. Papadimitriou. The Theory of Database Concurrency Control. Computer Science Press, 1986.

  Google Scholar 

• Stacy Patterson, Aaron J. Elmore, Faisal Nawab, Divyakant Agrawal, and Amr El Abbadi. Serializability, not serial: Concurrency control and availability in multi-datacenter datastores. Proc. of the VLDB Endowment, 5(11):1459–1470, 2012.

  Google Scholar 

• Kerttu Pollari-Malmi, Eljas Soisalon-Soininen, and Tatu Ylönen. Concurrency control in B-trees with batch updates. IEEE Trans. Knowl. Data Eng., 8(6):975–984, 1996.

  Google Scholar 

• Dan R. K. Ports and Kevin Grittner. Serializable snapshot isolation in PostgreSQL. Proc. of the VLDB Endowment, 5(12):1850–1861, 2012.

  Google Scholar 

• Saeed K. Rahimi and Frank S. Haug. Distributed Database Management Systems. A Practical Approach. Wiley, 2010.

  Google Scholar 

• Mendel Rosenblum and John K. Ousterhout. The design and implementation of a log-structured file system. ACM Trans. Comput. Syst., 10(1):26–52, 1992.

  Google Scholar 

• Kurt Rothermel and C. Mohan. ARIES/NT: A recovery method based on write-ahead logging for nested transactions. In VLDB 1989, Proc. of the 15th Internat. Conf. on Very Large Data Bases, pages 337–346. Morgan Kaufmann, 1989.

  Google Scholar 

• James B. Rothnie, Philip A. Bernstein, Stephen Fox, Nathan Goodman, Michael Hammer, Terry A. Landers, Christopher L. Reeve, David W. Shipman, and Eugene Wong. Introduction to a system for distributed databases (SDD-1). ACM Trans. Database Syst., 5(1):1–17, 1980.

  Google Scholar 

• Yehoshua Sagiv. Concurrent operations on B^∗-trees with overtaking. J. Comput. Syst. Sci., 33(2):275–296, 1986.

  Google Scholar 

• Betty Salzberg. Timestamping after commit. In PDIS 1994, Proc. of the Third Internat. Conf. on Parallel and Distributed Information Systems, pages 160–167. IEEE Computer Society, 1994.

  Google Scholar 

• Betty Salzberg and Allyn Dimock. Principles of transaction-based on-line reorganization. In VLDB 1992, Proc. of the 18th Internat. Conf. on Very Large Data Bases, pages 511–520. Morgan Kaufmann, 1992.

  Google Scholar 

• Behrokh Samadi. B-trees in a system with multiple users. Inf. Process. Lett., 5(4):107–112, 1976.

  Google Scholar 

• Hans-Jörg Schek, Gerhard Weikum, and Haiyan Ye. Towards a unified theory of concurrency control and recovery. In Proc. of the 12th ACM SIGACT-SIGMOD-SIGART Symp. on Principles of Database Systems, pages 300–311. ACM Press, 1993.

  Google Scholar 

• Russell Sears and Raghu Ramakrishnan. bLSM: a general purpose log structured merge tree. In Proc. of the 2012 ACM SIGMOD Internat. Conf. on Management of Data, pages 217–228. ACM Press, 2012.

  Google Scholar 

• Russell Sears, Mark Callaghan, and Eric A. Brewer. Rose: Compressed, log-structured replication. Proc. of the VLDB Endowment, 1(1):526–537, 2008.

  Google Scholar 

• Dennis G. Severance and Guy M. Lohman. Differential files: Their application to the maintenance of large databases. ACM Trans. Database Syst., 1(3):256–267, 1976.

  Google Scholar 

• Avi Silberschatz, Henry F. Korth, and S. Sudarshan. Database System Concepts. Fifth Edition. McGraw-Hill, 2006.

  Google Scholar 

• Seppo Sippu and Eljas Soisalon-Soininen. A theory of transactions on recoverable search trees. In Database Theory—ICDT 2001, Proc. of the 8th Internat. Conf., volume 1973 of Lecture Notes in Computer Science, pages 83–98. Springer, 2001.

  Google Scholar 

• Gary H. Sockut and Balakrishna R. Iyer. A survey on online reorganization in IBM products and research. IEEE Data Eng. Bull., 19(2):4–11, 1996.

  Google Scholar 

• Gary H. Sockut and Balakrishna R. Iyer. Online reorganization of databases. ACM Comput. Surv., 41(3):14:1–136, 2009.

  Google Scholar 

• Gary H. Sockut, Thomas A. Beavin, and Chung-C. Chang. A method for on-line reorganization of a database. IBM Systems Journal, 36(3):411–436, 1997.

  Google Scholar 

• Eljas Soisalon-Soininen and Tatu Ylönen. Partial strictness in two-phase locking. In Database Theory—ICDT 1995, Proc. of the 5th Internat. Conf., volume 893 of Lecture Notes in Computer Science, pages 139–147. Springer, 1995.

  Google Scholar 

• Jagannathan Srinivasan, Souripriya Das, Chuck Freiwald, Eugene Inseok Chong, Mahesh Jagannath, Aravind Yalamanchi, Ramkumar Krishnan, Anh-Tuan Tran, Samuel DeFazio, and Jayanta Banerjee. Oracle8i index-organized table and its application to new domains. In VLDB 2000, Proc. of the 26th Internat. Conf. on Very Large Data Bases, pages 285–296. Morgan Kaufmann, 2000.

  Google Scholar 

• V. Srinivasan and Michael J. Carey. On-line index construction algorithms. In Proc. of the High Performance Transaction Systems Workshop, 1991.

  Google Scholar 

• V. Srinivasan and Michael J. Carey. Performance of on-line index construction algorithms. In Advances in Database Technology—EDBT’92, Proc. of the 3rd Internat. Conf. on Extending Database Technology, volume 580 of Lecture Notes in Computer Science, pages 293–309. Springer, 1992.

  Google Scholar 

• V. Srinivasan and Michael J. Carey. Performance of B⁺ tree concurrency control algorithms. VLDB J., 2(4):361–406, 1993.

  Google Scholar 

• Michael Stonebraker. Operating system support for database management. Commun. ACM, 24(7):412–418, 1981.

  Article  Google Scholar 

• Michael Stonebraker, editor. The INGRES Papers: Anatomy of a Relational Database System. Addison-Wesley, 1986.

  Google Scholar 

• Michael Stonebraker. The design of the POSTGRES storage system. In VLDB 1987, Proc. of the 13th Internat. Conf. on Very Large Data Bases, pages 289–300. Morgan Kaufmann, 1987.

  Google Scholar 

• Michael Stonebraker. The case for partial indexes. SIGMOD Record, 18(4): 4–11, 1989.

  Article  Google Scholar 

• Michael Stonebraker. In search of database consistency. Commun. ACM, 53 (10):8–9, 2010a.

  Article  Google Scholar 

• Michael Stonebraker. Sql databases v. NoSQL databases. Commun. ACM, 53(4):10–11, 2010b.

  Google Scholar 

• Michael Stonebraker and Rick Cattell. 10 rules for scalable performance in ‘simple operation’ datastores. Commun. ACM, 54(6):72–80, 2011.

  Article  Google Scholar 

• Michael Stonebraker and Lawrence A. Rowe. The design of Postgres. In Proc. of the 1986 ACM SIGMOD Internat. Conf. on Management of Data, pages 340–355. ACM Press, 1986.

  Google Scholar 

• Michael Stonebraker, Eugene Wong, Peter Kreps, and Gerald Held. The design and implementation of INGRES. ACM Trans. Database Syst., 1(3): 189–222, 1976.

  Google Scholar 

• Michael Stonebraker, Lawrence A. Rowe, and Michael Hirohama. The implementation of Postgres. IEEE Trans. Knowl. Data Eng., 2(1):125–142, 1990.

  Google Scholar 

• Michael Stonebraker, Daniel J. Abadi, David J. DeWitt, Samuel Madden, Erik Paulson, Andrew Pavlo, and Alexander Rasin. MapReduce and parallel DBMSs: Friends or foes? Commun. ACM, 53(1):64–71, 2010.

  Article  Google Scholar 

• Xiaowei Sun, Rui Wang, Betty Salzberg, and Chendong Zou. Online B-tree merging. In Proc. of the 205 ACM SIGMOD Internat. Conf. on Management of Data, pages 335–346. ACM Press, 2005.

  Google Scholar 

• Irving L. Traiger. Trends in system aspects of database management. In Proc. of the 2nd Internat. Conf. on Databases, pages 1–21, 1983.

  Google Scholar 

• Hoang Tam Vo, Sheng Wang, Divyakant Agrawal, Gang Chen, and Beng Chin Ooi. Logbase: A scalable log-structured database system in the cloud. Proc. of the VLDB Endowment, 5(10):1004–1015, 2012.

  Google Scholar 

• Gerhard Weikum. Principles and realization strategies of multilevel transaction management. ACM Trans. Database Syst., 16(1):132–180, 1991.

  Google Scholar 

• Gerhard Weikum and Gottfried Vossen. Transactional Information Systems. Theory, Algorithms, and the Practice of Concurrency Control and Recovery. Morgan Kaufmann, 2002.

  Google Scholar 

• Chin-Hsien Wu, Tei-Wei Kuo, and Li-Ping Chang. An efficient b-tree layer implementation for flash-memory storage systems. ACM Trans. Embedded Comput. Syst., 6(3), 2007.

  Google Scholar 

• Markos Zaharioudakis, Michael J. Carey, and Michael J. Franklin. Adaptive, fine-grained sharing in a client-server OODBMS: A callback-based approach. ACM Trans. Database Syst., 22(4):570–627, 1997.

  Google Scholar 

• Chendong Zou and Betty Salzberg. On-line reorganization of sparsely-populated B⁺-trees. In Proc. of the 1996 ACM SIGMOD Internat. Conf. on Management of Data, pages 115–124. ACM Press, 1996a.

  Google Scholar 

• Chendong Zou and Betty Salzberg. Towards efficient online database reorganization. IEEE Data Eng. Bull., 19(2):33–40, 1996b.

  Google Scholar 

Download references