Take a look at the new version of this page: [ beta version ]. Tell us what you think.

ABSTRACT

In practice, any database management system sometimes needs reorganization, that is, a change in some aspect of the logical and/or physical arrangement of a database. In traditional practice, many types of reorganization have required denying access to a database (taking the database offline) during reorganization. Taking a database offline can be unacceptable for a highly available (24-hour) database, for example, a database serving electronic commerce or armed forces, or for a very large database. A solution is to reorganize online (concurrently with usage of the database, incrementally during users' activities, or interpretively). This article is a tutorial and survey on requirements, issues, and strategies for online reorganization. It analyzes the issues and then presents the strategies, which use the issues. The issues, most of which involve design trade-offs, include use of partitions, the locus of control for the process that reorganizes (a background process or users' activities), reorganization by copying to newly allocated storage (as opposed to reorganizing in place), use of differential files, references to data that has moved, performance, and activation of reorganization. The article surveys online strategies in three categories of reorganization. The first category, maintenance, involves restoring the physical arrangement of data instances without changing the database definition. This category includes restoration of clustering, reorganization of an index, rebalancing of parallel or distributed data, garbage collection for persistent storage, and cleaning (reclamation of space) in a log-structured file system. The second category involves changing the physical database definition; topics include construction of indexes, conversion between B⁺ -trees and linear hash files, and redefinition (e.g., splitting) of partitions. The third category involves changing the logical database definition. Some examples are changing a column's data type, changing the inheritance hierarchy of object classes, and changing a relationship from one-to-many to many-to-many. The survey encompasses both research and commercial implementations, and this article points out several open research topics. As highly available or very large databases continue to become more common and more important in the world economy, the importance of online reorganization is likely to continue growing.

REFERENCES

• 1: Saleh E. Abdullahi , Graem A. Ringwood, Garbage collecting the Internet: a survey of distributed garbage collection, ACM Computing Surveys (CSUR), v.30 n.3, p.330-373, Sept. 1998 [doi>10.1145/292469.292471]
• 2: Achyutuni, K. J., Omiecinski, E., and Navathe, S. B. 1992. HISET: A generalized technique for efficient concurrent reorganization. Tech. rep. GIT-CC-92/57, College of Computing, Georgia Institute of Technology, Atlanta.
• 3: Achyutuni, K. J., Omiecinski, E., and Navathe, S. B. 1993. The impact of data placement strategies on reorganization costs in parallel disk systems. Tech. rep. GIT-CC-93/58, College of Computing, Georgia Institute of Technology, Atlanta.
• 4: Kiran J. Achyutuni , Edward Omiecinski , Shamkant B. Navathe, Two techniques for on-line index modification in shared nothing parallel databases, Proceedings of the 1996 ACM SIGMOD international conference on Management of data, p.125-136, June 04-06, 1996, Montreal, Quebec, Canada
• 5: Ahlsén, M., Björnerstedt, A., Britts, S., Hultén, C., and Söderlund, L. 1983. Making type changes transparent. In Proceedings of the IEEE Workshop on Languages for Automation. 110--117.
• 6: Matts Ahlsen , Anders Bjornerstedt , Stefan Britts , Christer Hulten , Lars Soderlund, An architecture for object management in OIS, ACM Transactions on Information Systems (TOIS), v.2 n.3, p.173-196, July 1984 [doi>10.1145/1206.1207]
• 7: Guy Thomas Almes, Garbage collection in an object-oriented system, Carnegie Mellon University, Pittsburgh, PA, 1980
• 8: Amer. Natl. Standards Institute. 1992. Database Language SQL. Amer. National Standards Institute, New York. X3.135-1992.
• 9: Paul Ammann , Sushil Jajodia , Padmaja Mavuluri, On-The-Fly Reading of Entire Databases, IEEE Transactions on Knowledge and Data Engineering, v.7 n.5, p.834-838, October 1995 [doi>10.1109/69.469836]
• 10: Laurent Amsaleg , Michael J. Franklin , Olivier Gruber, Efficient Incremental Garbage Collection for Client-Server Object Database Systems, Proceedings of the 21th International Conference on Very Large Data Bases, p.42-53, September 11-15, 1995
• 11: Laurent Amsaleg , Michael J. Franklin , Olivier Gruber, Garbage collection for a client-server persistent object store, ACM Transactions on Computer Systems (TOCS), v.17 n.3, p.153-201, Aug. 1999 [doi>10.1145/320656.322741]
• 12: A. W. Appel , J. R. Ellis , K. Li, Real-time concurrent collection on stock multiprocessors, Proceedings of the ACM SIGPLAN 1988 conference on Programming Language design and Implementation, p.11-20, June 20-24, 1988, Atlanta, Georgia, United States
• 13: Srinivas Ashwin , Prasan Roy , S. Seshadri , Abraham Silberschatz , S. Sudarshan, Garbage Collection in Object Oriented Databases Using Transactional Cyclic Reference Counting, Proceedings of the 23rd International Conference on Very Large Data Bases, p.366-375, August 25-29, 1997
• 14: Hezi Azatchi , Yossi Levanoni , Harel Paz , Erez Petrank, An on-the-fly mark and sweep garbage collector based on sliding views, Proceedings of the 18th annual ACM SIGPLAN conference on Object-oriented programing, systems, languages, and applications, October 26-30, 2003, Anaheim, California, USA
• 15: David F. Bacon, Realtime Garbage Collection, Queue, v.5 n.1, February 2007 [doi>10.1145/1217256.1217268]
• 16: David F. Bacon , Perry Cheng , V. T. Rajan, A unified theory of garbage collection, Proceedings of the 19th annual ACM SIGPLAN conference on Object-oriented programming, systems, languages, and applications, October 24-28, 2004, Vancouver, BC, Canada
• 17: W. H. Bahaa-El-Din , F. B. Bastani , J.-F. Teng, Performance Analysis of Periodic and Concurrent Data Structure Maintenance Strategies for Network Servers, IEEE Transactions on Software Engineering, v.15 n.12, p.1526-1536, December 1989 [doi>10.1109/32.58765]
• 18: Henry G. Baker, Jr., List processing in real time on a serial computer, Communications of the ACM, v.21 n.4, p.280-294, April 1978 [doi>10.1145/359460.359470]
• 19: Jay Banerjee , Won Kim , Hyoung-Joo Kim , Henry F. Korth, Semantics and implementation of schema evolution in object-oriented databases, Proceedings of the 1987 ACM SIGMOD international conference on Management of data, p.311-322, May 27-29, 1987, San Francisco, California, United States
• 20: Banzon, A. T., Friske, C. A., Garth, J. M., Ng, K. C., Ruddy, J. A., and Vizconde, B. B. 2006. Method, apparatus and program storage device for managing buffers during online reorganization. U. S. patent application 2006/0173922.
• 21: Katherine Barabash , Ori Ben-Yitzhak , Irit Goft , Elliot K. Kolodner , Victor Leikehman , Yoav Ossia , Avi Owshanko , Erez Petrank, A parallel, incremental, mostly concurrent garbage collector for servers, ACM Transactions on Programming Languages and Systems (TOPLAS), v.27 n.6, p.1097-1146, November 2005 [doi>10.1145/1108970.1108972]
• 22: Katherine Barabash , Yoav Ossia , Erez Petrank, Mostly concurrent garbage collection revisited, Proceedings of the 18th annual ACM SIGPLAN conference on Object-oriented programing, systems, languages, and applications, October 26-30, 2003, Anaheim, California, USA
• 23: Bartlett, J. F. 1988. Compacting garbage collection with ambiguous roots. Tech. rep. 88/2, Western Research Lab., Digital Equipment Corp., Palo Alto.
• 24: Baru, C. and Zilio, D. C. 1993. Data reorganization in parallel database systems. In Proceedings of the IEEE Workshop on Advances in Parallel and Distributed Systems IEEE-CS. IEEE Computer Society Press, Los Alamitos, 102--107. (For later, more extensive analysis, see Zilio {1998}.)
• 25: F. B. Bastani , I.-R. Chen , W. Hilal, A model for the stability analysis of maintenance strategies for linear list, The Computer Journal, v.34 n.1, p.80-87, Feb. 1991 [doi>10.1093/comjnl/34.1.80]
• 26: Farokh Bastani , Wael Hilal , Ing-Ray Chen, Performance analysis of concurrent maintenance policies for servers in a distributed environment, Proceedings of 1986 ACM Fall joint computer conference, p.611-619, November 1986, Dallas, Texas, United States
• 27: F. B. Bastani , S. S. Iyengar , I-Ling Yen, Concurrent maintenance of data systems for telecommunications, The Computer Journal, v.31 n.2, p.165-174, April, 1988 [doi>10.1093/comjnl/31.2.165]
• 28: D. S. Batory, Optimal file designs and reorganization points, ACM Transactions on Database Systems (TODS), v.7 n.1, p.60-81, March 1982 [doi>10.1145/319682.319696]
• 29: Batra, D. P. 1989. Response time analysis for computer database reorganisation with concurrent usage and changeover state. Defence Sci. J. 39, 1, 33--41. Defence Scientific Info. and Documentation Centre, Ministry of Defence, Delhi, India.
• 30: Bayer, R. and McCreight, E. 1970. Organization and maintenance of large ordered indices. In Proceedings of the ACM SICFIDET Workshop on Data Description and Access. ACM, New York, 107--141. (For a revision, see Bayer and McCreight {1972}.)
• 31: Bayer, R. and McCreight, E. 1972. Organization and maintenance of large ordered indexes. Acta Inf. 1, 3, 173--189.
• 32: Zohra Bellahsene, View Mechanism for Schema Evolution, Proceedings of the 14th British National Conference on Databases: Advances in Databases, p.18-35, July 03-05, 1996
• 33: Bennett, B. T. and Franaszek, P. A. 1977. Permutation clustering: An approach to on-line storage reorganization. IBM J. Res. Develop. 21, 6, 528--533.
• 34: Philip A. Bernstein , Nathan Goodman, Concurrency Control in Distributed Database Systems, ACM Computing Surveys (CSUR), v.13 n.2, p.185-221, June 1981 [doi>10.1145/356842.356846]
• 35: Elisa Bertino, A View Mechanism for Object-Oriented Databases, Proceedings of the 3rd International Conference on Extending Database Technology: Advances in Database Technology, p.136-151, March 23-27, 1992
• 36: A. D. Birrell , R. M. Needham, An asynchronous garbage collector for the CAP filing system, ACM SIGOPS Operating Systems Review, v.12 n.2, p.31-33, April 1978 [doi>10.1145/775332.775338]
• 37: Stephen M. Blackburn , Perry Cheng , Kathryn S. McKinley, Myths and realities: the performance impact of garbage collection, Proceedings of the joint international conference on Measurement and modeling of computer systems, June 10-14, 2004, New York, NY, USA
• 38: Stephen M. Blackburn , Kathryn S. McKinley, Ulterior reference counting: fast garbage collection without a long wait, Proceedings of the 18th annual ACM SIGPLAN conference on Object-oriented programing, systems, languages, and applications, October 26-30, 2003, Anaheim, California, USA
• 39: Trevor Blackwell , Jeffrey Harris , Margo Seltzer, Heuristic cleaning algorithms in log-structured file systems, Proceedings of the USENIX 1995 Technical Conference Proceedings on USENIX 1995 Technical Conference Proceedings, p.23-23, January 16-20, 1995, New Orleans, Louisiana
• 40: BMC Software. 1997. REORG PLUS for DB2: General Information, Version 5.1. BMC Software.
• 41: BMC Software. 1998. CONCURRENT REORG and the Extended Performance Utilities: General Information, Version 1.3. BMC Software.
• 42: Bollella, G., Lizzi, C., and Daynes, L. P. 2009. System and method for ensuring non-interfering garbage collection in a real-time multi-threaded environment. U.S. patent 7,484,067.
• 43: Bracht, C. J., Malkemus, T. R., and Versteeg, A. 1991. Table reorganization identification. IBM Tech. Disclosure Bull. 34, 1, 163--165.
• 44: Svein Erik Bratsberg, Unified Class Evolution by Object-Oriented Views, Proceedings of the 11th International Conference on the Entity-Relationship Approach: Entity-Relationship Approach, p.423-439, October 07-09, 1992
• 45: Bratsberg, S. E. 1993. Evolution and integration of classes in object-oriented databases. Dr.Ing. thesis, Division of Computer Systems and Telematics, Norwegian Institute of Technology, Trondheim, Norway.
• 46: Svein Erik Bratsberg , Rune Humborstad, Online Scaling in a Highly Available Database, Proceedings of the 27th International Conference on Very Large Data Bases, p.451-460, September 11-14, 2001
• 47: Bratsberg, S. E. Hvasshovd, S.-O., and Torbjørnsen, Ø. 1997. Parallel solutions in ClustRa. Data Engin. 20, 2, 13--20.
• 48: Svein Erik Bratsberg , Øystein Torbjørnsen, Designing an ultra highly available DBMS (tutorial session), Proceedings of the 2000 ACM SIGMOD international conference on Management of data, p.577, May 15-18, 2000, Dallas, Texas, United States
• 49: Yuri Breitbart , Radek Vingralek , Gerhard Weikum, Load control in scalable distributed file structures, Distributed and Parallel Databases, v.4 n.4, p.319-354, Oct. 1996 [doi>10.1007/BF00119338]
• 50: Kurt P. Brown , Michael J. Carey , Miron Livny, Managing Memory to Meet Multiclass Workload Response Time Goals, Proceedings of the 19th International Conference on Very Large Data Bases, p.328-341, August 24-27, 1993
• 51: Kurt P. Brown , Michael J. Carey , Miron Livny, Goal-oriented buffer management revisited, Proceedings of the 1996 ACM SIGMOD international conference on Management of data, p.353-364, June 04-06, 1996, Montreal, Quebec, Canada
• 52: D. R. Brownbridge, Cyclic reference counting for combinator machines, Proc. of a conference on Functional programming languages and computer architecture, p.273-288, January 1985, Nancy, France
• 53: Margaret H. Butler, Storage reclamation for object-oriented database systems: a summary of the expected costs, Proceedings on the 1986 international workshop on Object-oriented database systems, p.210-211, September 23-26, 1986, Pacific Grove, California, United States
• 54: Margaret H. Butler, Storage reclamation in object oriented database systems, Proceedings of the 1987 ACM SIGMOD international conference on Management of data, p.410-425, May 27-29, 1987, San Francisco, California, United States
• 55: D. D. Chamberlin , J. N. Gray , I. L. Traiger, Views, authorization, and locking in a relational data base system, Proceedings of the May 19-22, 1975, national computer conference and exposition, May 19-22, 1975, Anaheim, California [doi>10.1145/1499949.1500032]
• 56: Donald D. Chamberlin , Frank B. Schmuck, Dynamic Data Distribution (D3) in a Shared-Nothing Multiprocessor Data Store, Proceedings of the 18th International Conference on Very Large Data Bases, p.163-174, August 23-27, 1992
• 57: Chamberlin, D. D. and Schmuck, F. B. 1992b. Dynamic data distribution in a shared-nothing multiprocessor data store. Resear. rep. RJ 8730, IBM T. J. Watson Research Center, Yorktown Heights.
• 58: E. E. Chang , R. H. Katz, Exploiting inheritance and structure semantics for effective clustering and buffering in an object-oriented DBMS, Proceedings of the 1989 ACM SIGMOD international conference on Management of data, p.348-357, June 1989, Portland, Oregon, United States
• 59: Chye Lin Chee , Hongjun Lu , Hong Tang , C. v. Ramamoorthy, Adaptive Prefetching and Storage Reorganization In A Log-Structured Storage System, IEEE Transactions on Knowledge and Data Engineering, v.10 n.5, p.824-838, September 1998 [doi>10.1109/69.729739]
• 60: Chen, I.-R. 1995. A degradable B^link-tree with periodic data reorganization. Comput. J. 38, 3, 245--252.
• 61: Ing-Ray Chen , S. A. Banawan, Modeling and Analysis of Concurrent Maintenance Policies for Data Structures Using Pointers, IEEE Transactions on Software Engineering, v.19 n.9, p.902-911, September 1993 [doi>10.1109/32.241772]
• 62: Ing-Ray Chen , Sayed A. Banawan, Performance and Stability Analysis of Multilevel Data Structures with Deferred Reorganization, IEEE Transactions on Software Engineering, v.25 n.5, p.690-700, September 1999 [doi>10.1109/32.815327]
• 63: Ing-Ray Chen , Salah Hassan, Performance analysis of a periodic data reorganization algorithm for concurrent Blink-trees in database systems, Proceedings of the 1995 ACM symposium on Applied computing, p.40-45, February 26-28, 1995, Nashville, Tennessee, United States [doi>10.1145/315891.315901]
• 64: Peter M. Chen , Edward K. Lee , Garth A. Gibson , Randy H. Katz , David A. Patterson, RAID: high-performance, reliable secondary storage, ACM Computing Surveys (CSUR), v.26 n.2, p.145-185, June 1994 [doi>10.1145/176979.176981]
• 65: C. J. Cheney, A nonrecursive list compacting algorithm, Communications of the ACM, v.13 n.11, p.677-678, Nov 1970 [doi>10.1145/362790.362798]
• 66: Jia-Bing R. Cheng , A. R. Hurson, Effective clustering of complex objects in object-oriented databases, Proceedings of the 1991 ACM SIGMOD international conference on Management of data, p.22-31, May 29-31, 1991, Denver, Colorado, United States
• 67: Mei-Ling Chiang , Jia-Shin Huang, Improving the performance of log-structured file systems with adaptive block rearrangement, Proceedings of the 2007 ACM symposium on Applied computing, March 11-15, 2007, Seoul, Korea [doi>10.1145/1244002.1244250]
• 68: Stewart M. Clamen, Schema evolution and integration, Distributed and Parallel Databases, v.2 n.1, p.101-126, Jan. 1994 [doi>10.1007/BF01263340]
• 69: Jacques Cohen, Garbage Collection of Linked Data Structures, ACM Computing Surveys (CSUR), v.13 n.3, p.341-367, Sept. 1981 [doi>10.1145/356850.356854]
• 70: George E. Collins, A method for overlapping and erasure of lists, Communications of the ACM, v.3 n.12, p.655-657, Dec. 1960 [doi>10.1145/367487.367501]
• 71: Douglas Comer, Ubiquitous B-Tree, ACM Computing Surveys (CSUR), v.11 n.2, p.121-137, June 1979 [doi>10.1145/356770.356776]
• 72: Jonathan E. Cook , Artur W. Klauser , Alexander L. Wolf , Benjamin G. Zorn, Semi-automatic, self-adaptive control of garbage collection rates in object databases, Proceedings of the 1996 ACM SIGMOD international conference on Management of data, p.377-388, June 04-06, 1996, Montreal, Quebec, Canada
• 73: Jonathan E. Cook , Alexander L. Wolf , Benjamin G. Zorn, Partition selection policies in object database garbage collection, Proceedings of the 1994 ACM SIGMOD international conference on Management of data, p.371-382, May 24-27, 1994, Minneapolis, Minnesota, United States
• 74: Jonathan E. Cook , Alexander L. Wolf , Benjamin G. Zorn, A Highly Effective Partition Selection Policy for Object Database Garbage Collection, IEEE Transactions on Knowledge and Data Engineering, v.10 n.1, p.153-172, January 1998 [doi>10.1109/69.667100]
• 75: George Copeland , William Alexander , Ellen Boughter , Tom Keller, Data placement in Bubba, Proceedings of the 1988 ACM SIGMOD international conference on Management of data, p.99-108, June 01-03, 1988, Chicago, Illinois, United States
• 76: George Copeland , Michael Franklin , Gerhard Weikum, Uniform object management, Proceedings of the 2nd international conference on extending database technology: Advances in Database Technology, p.253-268, March 1990, Venice, Italy
• 77: Crus, R. A. 1984. Data recovery in IBM Database 2. IBM Syst. J. 23, 2, 178--188.
• 78: David Luke Detlefs , Jeannette Wing, Concurrent atomic garbage collection, Carnegie Mellon University, Pittsburgh, PA, 1990
• 79: Detlefs, D. L. 2004. A hard look at hard real-time garbage collection. In Proceedings of the 7th IEEE International Symposium on Object-Oriented Real-Time Distributed Computing (ISORC 2004). IEEE Computer Society Press, Los Alamitos, 23--32.
• 80: David Detlefs , Christine Flood , Steve Heller , Tony Printezis, Garbage-first garbage collection, Proceedings of the 4th international symposium on Memory management, October 24-25, 2004, Vancouver, BC, Canada [doi>10.1145/1029873.1029879]
• 81: L. Peter Deutsch , Daniel G. Bobrow, An efficient, incremental, automatic garbage collector, Communications of the ACM, v.19 n.9, p.522-526, Sept. 1976 [doi>10.1145/360336.360345]
• 82: David DeWitt , Jim Gray, Parallel database systems: the future of high performance database systems, Communications of the ACM, v.35 n.6, p.85-98, June 1992 [doi>10.1145/129888.129894]
• 83: Edsger W. Dijkstra , Leslie Lamport , A. J. Martin , C. S. Scholten , E. F. M. Steffens, On-the-fly garbage collection: an exercise in cooperation, Communications of the ACM, v.21 n.11, p.966-975, Nov. 1978 [doi>10.1145/359642.359655]
• 84: Tamar Domani , Elliot K. Kolodner , Ethan Lewis , Eliot E. Salant , Katherine Barabash , Itai Lahan , Yossi Levanoni , Erez Petrank , Igor Yanorer, Implementing an on-the-fly garbage collector for Java, Proceedings of the 2nd international symposium on Memory management, p.155-166, October 15-16, 2000, Minneapolis, Minnesota, United States
• 85: Tamar Domani , Elliot K. Kolodner , Erez Petrank, A generational on-the-fly garbage collector for Java, Proceedings of the ACM SIGPLAN 2000 conference on Programming language design and implementation, p.274-284, June 18-21, 2000, Vancouver, British Columbia, Canada
• 86: Lars Eggert , Joseph D. Touch, Idletime scheduling with preemption intervals, Proceedings of the twentieth ACM symposium on Operating systems principles, October 23-26, 2005, Brighton, United Kingdom
• 87: Susanne Englert, Nonstop SQL: scalability and availability for decision support, Proceedings of the 1994 ACM SIGMOD international conference on Management of data, p.491, May 24-27, 1994, Minneapolis, Minnesota, United States
• 88: M. T. Fang , Richard C. T. Lee , C. C. Chang, The Idea of De-Clustering and its Applications, Proceedings of the 12th International Conference on Very Large Data Bases, p.181-188, August 25-28, 1986
• 89: Hisham Feelifl , Masaru Kitsuregawa, RING: A Strategy for Minimizing the Cost of Online Data Placement Reorganization for Btree Indexed Database over Shared-nothing Machines, Proceedings of the 7th International Conference on Database Systems for Advanced Applications, p.190-199, April 18-20, 2001
• 90: Hisham Feelifl , Masaru Kitsuregawa , Beng Chin Ooi, A Fast Convergence Technique for Online Heat-Balancing of Btree Indexed Database over Shared-Nothing Parallel Systems, Proceedings of the 11th International Conference on Database and Expert Systems Applications, p.846-858, September 04-08, 2000
• 91: Fabrizio Ferrandina , Thorsten Meyer , Roberto Zicari, Correctness of Lazy Database Updates for Object Database Systems, Proceedings of the Sixth International Workshop on Persistent Object Systems, p.284-301, September 05-09, 1994
• 92: Fabrizio Ferrandina , Thorsten Meyer , Roberto Zicari , Guy Ferran , Joëlle Madec, Schema and Database Evolution in the O2 Object Database System, Proceedings of the 21th International Conference on Very Large Data Bases, p.170-181, September 11-15, 1995
• 93: Paulo Ferreira , Marc Shapiro, Garbage collection and DSM consistency, Proceedings of the 1st USENIX conference on Operating Systems Design and Implementation, p.17-es, November 14-17, 1994, Monterey, California
• 94: Paulo Ferreira , Marc Shapiro, Garbage Collection of Persistent Objects in Distributed Shared Memory, Proceedings of the Sixth International Workshop on Persistent Object Systems, p.184-199, September 05-09, 1994
• 95: Fontana, E. and Dennebouy, Y. 1995. Time-stamped versions for lazy propagation of schema changes. Tech. rep. 95/100, Department of Informatics, Swiss Federal Institute of Technology, Lausanne, Switzerland.
• 96: Daniel Alexander Ford , Jussi Myllymaki, A Log-Structured Organization for Tertiary Storage, Proceedings of the Twelfth International Conference on Data Engineering, p.20-27, February 26-March 01, 1996
• 97: Franaszek, P. A. and Considine, J. P. 1979. Reduction of storage fragmentation on direct access devices. IBM J. Res. Devel. 23, 2, 140--148.
• 98: Franaszek, P. A., Robinson, J. T., and Thomasian, A. 1994. Reorganizing data in log-structured file systems. IBM Tech. Disclos. Bull. 37, 6A, 623--624.
• 99: Franklin, M., Copeland, G., and Weikum, G. 1989. What's different about garbage collection for persistent programming languages? Tech. rep. ACA-ST-062-89, MCC, Austin.
• 100: Friske, C. A. 2004a. DB2 managing large partitioned tables in Version 8. Proc. SHARE 102. SHARE, Chicago.
• 101: Friske, C. A. 2004b. DB2 online schema changes -- what's new in DB2 Version 8. Proc. SHARE 102. SHARE, Chicago.
• 102: Friske, C. A., Garth, J. M., Lee, C. M., and Ruddy, J. A. 2007. Method and apparatus for building one or more indexes on data concurrent with manipulation of data. U.S. patent 7,308,456.
• 103: Friske, C. A., Garth, J. M., and Ruddy, J. A. 2003a. Method of estimating an amount of changed data over plurality of intervals of time measurements. U.S. patent 6,535,870.
• 104: Friske, C. A. and Ruddy, J. A. 1998. Online reorganization. DB2 Mag. 3, 3. (Online Ed. http://www.db2mag.com.) CMP Media.
• 105: Friske, C. A., Ruddy, J. A., and Shibamiya, A. 2003b. Method for estimating the elapsed-time required for a log apply process. U.S. patent 6,535,893.
• 106: Nina Edelweiss , Álvaro Freitas Moreira, Temporal and versioning model for schema evolution in object-oriented databases, Data & Knowledge Engineering, v.53 n.2, p.99-128, May 2005 [doi>10.1016/j.datak.2004.07.001]
• 107: Prasanna Ganesan , Mayank Bawa , Hector Garcia-Molina, Online balancing of range-partitioned data with applications to peer-to-peer systems, Proceedings of the Thirtieth international conference on Very large data bases, p.444-455, August 31-September 03, 2004, Toronto, Canada
• 108: N. H. Garnett , R. M. Needham, An asynchronous garbage collector for the Cambridge File Server, ACM SIGOPS Operating Systems Review, v.14 n.4, p.36-40, October 1980 [doi>10.1145/850708.850711]
• 109: Garthwaite, A. T. 2008. Concurrent incremental garbage collector with a card table summarizing modified reference locations. U.S. patent 7,412,580.
• 110: Gerritsen, R. 1994. Private communication.
• 111: Rob Gerritsen , Howard L. Morgan, Dynamic restructuring of databases with generation data structures, Proceedings of the annual conference, p.281-286, October 20-22, 1976, Houston, Texas, United States [doi>10.1145/800191.805598]
• 112: Shahram Ghandeharizadeh , David J. DeWitt, A Multiuser Performance Analysis of Alternative Declustering Strategies, Proceedings of the Sixth International Conference on Data Engineering, p.466-475, February 05-09, 1990
• 113: Ghandeharizadeh, S., Gao, S., Gahagan, C., and Krauss, R. 2006. An on-line reorganization framework for SAN file systems. In Proceedings of the 10th East European Conference on Advances in Databases and Information Systems, Y. Manolopoulos, J. Pokorný, and T. K. Sellis, Eds. Lecture Notes in Computer Science, vol. 4152. Springer-Verlag, New York, 399--414.
• 114: Shahram Ghandeharizadeh , Dongho Kim, On-line Reorganization of Data in Scalable Continuous Media Servers, Proceedings of the 7th International Conference on Database and Expert Systems Applications, p.751-768, September 09-13, 1996
• 115: Richard Golding , Peter Bosch , Carl Staelin , Tim Sullivan , John Wilkes, Idleness is not sloth, Proceedings of the USENIX 1995 Technical Conference Proceedings on USENIX 1995 Technical Conference Proceedings, p.17-17, January 16-20, 1995, New Orleans, Louisiana
• 116: Nathan Goodman , Dennis Shasha, Semantically-based concurrancy control for search structures, Proceedings of the fourth ACM SIGACT-SIGMOD symposium on Principles of database systems, p.8-19, March 25-27, 1985, Portland, Oregon, United States [doi>10.1145/325405.325407]
• 117: Iqbal A. Goralwalla , Duane Szafron , M. Tamer Özsu , Randal J. Peters, A temporal approach to managing schema evolution in object database systems, Data & Knowledge Engineering, v.28 n.1, p.73-105, Oct. 30, 1998 [doi>10.1016/S0169-023X(98)00014-7]
• 118: Brajesh Goyal , Jayant R. Haritsa , S. Seshadri , V. Srinivasan, Index Concurrency Control in Firm Real-Time Database Systems, Proceedings of the 21th International Conference on Very Large Data Bases, p.146-157, September 11-15, 1995
• 119: Goetz Graefe, Query evaluation techniques for large databases, ACM Computing Surveys (CSUR), v.25 n.2, p.73-169, June 1993 [doi>10.1145/152610.152611]
• 120: Jim Gray, Notes on Data Base Operating Systems, Operating Systems, An Advanced Course, p.393-481, January 1978
• 121: Jim Gray , Andreas Reuter, Transaction Processing: Concepts and Techniques, Morgan Kaufmann Publishers Inc., San Francisco, CA, 1992
• 122: Leo J. Guibas , Robert Sedgewick, A dichromatic framework for balanced trees, Proceedings of the 19th Annual Symposium on Foundations of Computer Science, p.8-21, October 16-18, 1978
• 123: A. Gupta , W. K. Fuchs, Garbage Collection in a Distributed Object-Oriented System, IEEE Transactions on Knowledge and Data Engineering, v.5 n.2, p.257-265, April 1993 [doi>10.1109/69.219734]
• 124: Theo Haerder , Andreas Reuter, Principles of transaction-oriented database recovery, ACM Computing Surveys (CSUR), v.15 n.4, p.287-317, December 1983 [doi>10.1145/289.291]
• 125: Hamada, Y., Ishihara, K., Masumoto, T., Fujita, T., Masatomi, K., Takeda, Y., and Kawashima, M. 2000. On-line database duplication with incorporation of concurrent database updates. U.S. patent 6,023,707.
• 126: John H. Hartman , John K. Ousterhout, The Zebra striped network file system, ACM Transactions on Computer Systems (TOCS), v.13 n.3, p.274-310, Aug. 1995 [doi>10.1145/210126.210131]
• 127: Abdelsalam (Sumi) Helal , David Yuan , Hesham El-Rewini, Dynamic Data Reallocation for Skew Management inShared-Nothing Parallel Databases, Distributed and Parallel Databases, v.5 n.3, p.271-288, July 1997 [doi>10.1023/A:1008637328830]
• 128: Daniel P. Heyman, Mathematical models of database degradation, ACM Transactions on Database Systems (TODS), v.7 n.4, p.615-631, Dec. 1982 [doi>10.1145/319758.319771]
• 129: Ho, F., Jain, R., and Troisi, J. 1994. An overview of NonStop SQL/MP. Tandem Syst. Rev. 10, 3, 6--17. Hewlett-Packard.
• 130: Huras, M. A., Hing, N. H., Goss, J. J., and Lindsay, B. G. 2005. Online database table reorganization. U.S. patent 6,950,834.
• 131: IBM. 1986. IMS/VS Version 1 Utilities Reference Manual. IBM. SH20-9029-9.
• 132: IBM. 1993a. Implementing Concurrent Copy. IBM. GG24-3990-00.
• 133: IBM. 1993b. An Introduction to Data Propagator Relational Release 1. IBM. GC26-3398-01.
• 134: IBM. 1997. DB2 for OS/390 Version 5 Utility Guide and Reference. IBM. SC26-8967-00.
• 135: IBM. 2001. DB2 Universal Database for OS/390 and z/OS Utility Guide and Reference, Version 7. IBM. SC26-9945-00.
• 136: IBM. 2005. IMS Administration Guide: Database Manager, Version 9. IBM. SC18-7806-01.
• 137: IBM and Integrated Systems Solutions. 1994. Replidata/MVS User's Guide. IBM and Integrated Systems Solutions. BLD-REP-UG-00.
• 138: Isip, Jr., A. B. 2007. System and method for reorganizing stored data. U.S. patent 7,225,206.
• 139: Itasca Systems. 1993. ITASCA Distributed Object Database Management System: Technical Summary for Release 2.2. Itasca Systems.
• 140: Iyer, B. R. and Sockut, G. H. 2002. Methods for in-place online reorganization of a database. U.S. patent 6,411,964.
• 141: Balakrishna R. Iyer , David Wilhite, Data Compression Support in Databases, Proceedings of the 20th International Conference on Very Large Data Bases, p.695-704, September 12-15, 1994
• 142: Martin Jambor , Tomas Hruby , Jan Taus , Kuba Krchak , Viliam Holub, Implementation of a Linux log-structured file system with a garbage collector, ACM SIGOPS Operating Systems Review, v.41 n.1, January 2007 [doi>10.1145/1228291.1228299]
• 143: Theodore Johnson , Dennis Shasha, A framework for the performance analysis of concurrent B-tree algorithms, Proceedings of the ninth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, p.273-287, April 02-04, 1990, Nashville, Tennessee, United States [doi>10.1145/298514.298580]
• 144: Theodore Johnson , Dennis Sasha, The performance of current B-tree algorithms, ACM Transactions on Database Systems (TODS), v.18 n.1, p.51-101, March 1993 [doi>10.1145/151284.151286]
• 145: Pramod G. Joisha, Overlooking roots: a framework for making nondeferred reference-counting garbage collection fast, Proceedings of the 6th international symposium on Memory management, October 21-22, 2007, Montreal, Quebec, Canada [doi>10.1145/1296907.1296926]
• 146: Pramod G. Joisha, A principled approach to nondeferred reference-counting garbage collection, Proceedings of the fourth ACM SIGPLAN/SIGOPS international conference on Virtual execution environments, March 05-07, 2008, Seattle, WA, USA [doi>10.1145/1346256.1346275]
• 147: Richard Jones , Rafael Lins, Garbage collection: algorithms for automatic dynamic memory management, John Wiley & Sons, Inc., New York, NY, 1996
• 148: Wiebren de Jonge , M. Frans Kaashoek , Wilson C. Hsieh, The logical disk: a new approach to improving file systems, Proceedings of the fourteenth ACM symposium on Operating systems principles, p.15-28, December 05-08, 1993, Asheville, North Carolina, United States
• 149: Katabami, N., Itoh, T., and Takahashi, Y. 1997. Method and apparatus for reorganizing an on-line database system in accordance with an access time increase. U.S. patent 5,596,747.
• 150: Haim Kermany , Erez Petrank, The Compressor: concurrent, incremental, and parallel compaction, Proceedings of the 2006 ACM SIGPLAN conference on Programming language design and implementation, June 11-14, 2006, Ottawa, Ontario, Canada
• 151: Martin Kero , Johan Nordlander , Per Lindgren, A correct and useful incremental copying garbage collector, Proceedings of the 6th international symposium on Memory management, October 21-22, 2007, Montreal, Quebec, Canada [doi>10.1145/1296907.1296924]
• 152: J. L. W. Kessels, On-the-fly optimization of data structures, Communications of the ACM, v.26 n.11, p.895-901, Nov. 1983 [doi>10.1145/182.358442]
• 153: Keyes, J. 1992. DBAs face challenge of 24 by 7 availability. Software Mag. 12, 11, 58--63.
• 154: M Y Kim, Synchronized Disk Interleaving, IEEE Transactions on Computers, v.35 n.11, p.978-988, November 1986 [doi>10.1109/TC.1986.1676699]
• 155: Kitsuregawa, M., Goda, K., and Kawamura, N. 2008. Method and system for data processing with database reorganization for the same. U.S. patent 7,421,456.
• 156: Kitsuregawa, M. and Mogi, K. 1993. Virtual striping: A RAID5 storage management scheme with robustness for the peak access traffic. In Proceedings of the International Symposium on Next Generation Database Systems and Their Applications. ACM, New York, 280--287.
• 157: Kohl, J. T., Staelin, C., and Stonebraker, M. 1993. HighLight: Using a log-structured file system for tertiary storage management. In Proceedings of the Winter 1993 USENIX Conference. USENIX Assoc., Berkeley, 435--447.
• 158: Kolodner, E. K. 1990. Atomic incremental garbage collection and recovery for a large stable heap. In Proceedings of the 4th International Workshop on Persistent Object Systems, A. Dearle, G. M. Shaw, and S. B. Zdonik, Eds. Morgan-Kaufmann, San Francisco, 185--198. (see Kolodner {1992}.)
• 159: Elliot K. Kolodner, Atomic incremental garbage collection and recovery for a large stable heap, Massachusetts Institute of Technology, Cambridge, MA, 1992
• 160: Kolodner, E. K., Lewis, E., and Petrank, E. 2005. Trace termination for on-the-fly garbage collection for weakly-consistent computer architecture. U.S. patent 6,920,541.
• 161: Kolodner, E. K. and Petrank, E. 2002. On-the-fly garbage collector. U.S. patent 6,490,599.
• 162: Elliot K. Kolodner , William E. Weihl, Atomic incremental garbage collection and recovery for a large stable heap, Proceedings of the 1993 ACM SIGMOD international conference on Management of data, p.177-186, May 25-28, 1993, Washington, D.C., United States
• 163: H. T. Kung , Philip L. Lehman, Concurrent manipulation of binary search trees, ACM Transactions on Database Systems (TODS), v.5 n.3, p.354-382, Sept. 1980 [doi>10.1145/320613.320619]
• 164: Real-Time Data Access Control on B-Tree Index Structures, Proceedings of the 15th International Conference on Data Engineering, p.458, March 23-26, 1999
• 165: Mohana K. Lakhamraju , Rajeev Rastogi , S. Seshadri , S. Sudarshan, On-line reorganization in object databases, Proceedings of the 2000 ACM SIGMOD international conference on Management of data, p.58-69, May 15-18, 2000, Dallas, Texas, United States
• 166: Lakhamraju, M. K., Rastogi, R., Seshadri, S., and Sudarshan, S. 2002. On-line reorganization in object-oriented databases. U.S. patent 6,343,296. (This is similar to Lakhamraju et al. {2000}.)
• 167: Kwok-Wa Lam , Victor C. S. Lee, On Consistent Reading of Entire Databases, IEEE Transactions on Knowledge and Data Engineering, v.18 n.4, p.569-572, April 2006 [doi>10.1109/TKDE.2006.64]
• 168: B. W. Lampson, Hints for Computer System Design, IEEE Software, v.1 n.1, p.11-28, January 1984 [doi>10.1109/MS.1984.233391]
• 169: Langley, J. T. and Moore, D. W. 2008. Non-disruptive backup copy in a database online reorganization environment. U.S. patent 7,433,902.
• 170: Mong Li Lee , Masaru Kitsuregawa , Beng Chin Ooi , Kian-Lee Tan , Anirban Mondal, Towards self-tuning data placement in parallel database systems, Proceedings of the 2000 ACM SIGMOD international conference on Management of data, p.225-236, May 15-18, 2000, Dallas, Texas, United States
• 171: Witold Litwin, Linear hashing: a new tool for file and table addressing, Proceedings of the sixth international conference on Very Large Data Bases, p.212-223, October 01-03, 1980, Montreal, Quebec, Canada
• 172: Chien-Tsai Liu , Panos K. Chrysanthis , Shi-Kuo Chang, Database Schema Evolution through the Specification and Maintenance of Changes on Entities and Relationships, Proceedings of the13th International Conference on the Entity-Relationship Approach, p.132-151, December 13-16, 1994
• 173: Ling Liu , Roberto Zicari , Walter L. Hürsch , Karl J. Lieberherr, Polymorphic Reuse Mechanisms for Object-Oriented Database Specifications, Proceedings of the Tenth International Conference on Data Engineering, p.180-189, February 14-18, 1994
• 174: Guy Maring Lohman, Optimal data storage and organization in computerized information processing systems subject to failures., Cornell University, Ithaca, NY, 1977
• 175: Guy M. Lohman , John A. Muckstadt, Optimal policy for batch operations: backup, checkpointing, reorganization, and updating, ACM Transactions on Database Systems (TODS), v.2 n.3, p.209-222, Sept. 1977 [doi>10.1145/320557.320558]
• 176: Løland, J. and Hvasshovd, S.-O. 2006. Online, non-blocking relational schema changes. In Proceedings of the 10th International Conference on Extending Database Technology. Advances in Database Technology—EDBT 2006, Y. E. Ioannidis, M. H. Scholl, J. W. Schmidt, F. Matthes, M. Hatzopoulos, K. Böhm, A. Kemper, T. Grust, and C. Böhm, Eds. Lecture Notes in Computer Science, vol. 3896. Springer-Verlag, New York, 405--422.
• 177: David B. Lomet, High speed on-line backup when using logical log operations, Proceedings of the 2000 ACM SIGMOD international conference on Management of data, p.34-45, May 15-18, 2000, Dallas, Texas, United States
• 178: David Lomet , Betty Salzberg, Access method concurrency with recovery, Proceedings of the 1992 ACM SIGMOD international conference on Management of data, p.351-360, June 02-05, 1992, San Diego, California, United States
• 179: David Lomet , Betty Salzberg, Concurrency and recovery for index trees, The VLDB Journal — The International Journal on Very Large Data Bases, v.6 n.3, p.224-240, August 1997 [doi>10.1007/s007780050042]
• 180: Christopher R. Lumb , Jiri Schindler , Gregory R. Ganger , David F. Nagle , Erik Riedel, Towards higher disk head utilization: extracting free bandwidth from busy disk drives, Proceedings of the 4th conference on Symposium on Operating System Design & Implementation, p.7-7, October 22-25, 2000, San Diego, California
• 181: Umesh Maheshwari , Barbara Liskov, Partitioned garbage collection of a large object store, Proceedings of the 1997 ACM SIGMOD international conference on Management of data, p.313-323, May 11-15, 1997, Tucson, Arizona, United States
• 182: Maier, D. S., Marton, R. S., Troisi, J. H., and Celis, P. 1997. Relational database system and method with high data availability during table data restructuring. U.S. patent 5,625,815.
• 183: Malhotra, A. and Munroe, S. J. 1997. Schema evolution in persistent object systems. In Proceedings of the 7th International Workshop on Persistent Object Systems, R. Connor and S. Nettles, Eds. Morgan-Kaufmann, San Francisco, 194--204.
• 184: Manber, U. 1984. Concurrent maintenance of binary search trees. IEEE Trans. Softw. Engin. SE-10, 6, 777--784.
• 185: Udi Manber , Richard E. Ladner, Concurrency control in a dynamic search structure, Proceedings of the 1st ACM SIGACT-SIGMOD symposium on Principles of database systems, March 29-31, 1982, Los Angeles, California [doi>10.1145/588111.588156]
• 186: Udi Manbar , Richard E. Ladner, Concurrency control in a dynamic search structure, ACM Transactions on Database Systems (TODS), v.9 n.3, p.439-455, Sept. 1984 [doi>10.1145/1270.318576]
• 187: Marshall, B. J., Henderson, M. D., Bailey, M. I., Bruce, T. R., Rogala, R. J., Webster, W. A., Metzner, D. F., and Dres, P. J. 2006. Method and system for online reorganization of databases. U.S. patent 7,117,229.
• 188: James Martin, Computer Database Organization, 2nd Ed, Prentice Hall PTR, Upper Saddle River, NJ, 1977
• 189: Martin, Jr., J. L. and Crown, Jr., G. N. 2003a. IMS on-line reorganization utility. U.S. patent 6,606,631.
• 190: Martin, Jr., J. L. and Crown, Jr., G. N. 2003b. System and method for analyzing a database for on-line reorganization. U.S. patent 6,633,884.
• 191: K. Maruyama , S. E. Smith, Optimal reorganization of distributed space disk files, Communications of the ACM, v.19 n.11, p.634-642, Nov. 1976 [doi>10.1145/360363.360370]
• 192: Jeanna Neefe Matthews , Drew Roselli , Adam M. Costello , Randolph Y. Wang , Thomas E. Anderson, Improving the performance of log-structured file systems with adaptive methods, Proceedings of the sixteenth ACM symposium on Operating systems principles, p.238-251, October 05-08, 1997, Saint Malo, France
• 193: Mark L. Mcauliffe , Michael J. Carey , Marvin H. Solomon, Vclusters: a flexible, fine-grained object clustering mechanism, Proceedings of the 13th ACM SIGPLAN conference on Object-oriented programming, systems, languages, and applications, p.230-243, October 18-22, 1998, Vancouver, British Columbia, Canada
• 194: John McCarthy, Recursive functions of symbolic expressions and their computation by machine, Part I, Communications of the ACM, v.3 n.4, p.184-195, April 1960 [doi>10.1145/367177.367199]
• 195: Andrew McCreight , Zhong Shao , Chunxiao Lin , Long Li, A general framework for certifying garbage collectors and their mutators, Proceedings of the 2007 ACM SIGPLAN conference on Programming language design and implementation, June 10-13, 2007, San Diego, California, USA
• 196: William James Mciver, Jr., An approach to self-adaptive, on-line reclustering of complex object data, University of Colorado at Boulder, Boulder, CO, 1995
• 197: William J. McIver, Jr. , Roger King, Self-adaptive, on-line reclustering of complex object data, Proceedings of the 1994 ACM SIGMOD international conference on Management of data, p.407-418, May 24-27, 1994, Minneapolis, Minnesota, United States
• 198: B. McNutt, Background data movement in a log-structured disk subsystem, IBM Journal of Research and Development, v.38 n.1, p.47-58, Jan. 1994
• 199: Meltzer, H. S. 1975. An overview of the administration of data bases. In Proceedings of the 2nd USA-Japan Computer Conference. AFIPS Press, Reston, 365--370.
• 200: Herbert S. Meltzer, Structure and redundancy in the conceptual schema in the administration of very large data bases, Proceedings of the second international conference on Systems for Large Data Bases, p.13-25, September 08-10, 1976, Brussels, Belgium, North Holland
• 201: Mendelson, H. and Yechiali, U. 1981. Optimal policies for data base reorganization. Oper. Resear. 29, 1, 23--36.
• 202: Menon, J. and Stockmeyer, L. 1998. An age-threshold algorithm for garbage collection in log-structured arrays and file systems. In Proceedings of the 12th Annual International Symposium on High-Performance Computing Systems and Application, J. Schaefer, Ed. Kluwer Academic Publishers, Hingham, 119--132. (More details appear in Resear. Rep. RJ 10120, IBM T. J. Watson Research Center, Yorktown Heights.)
• 203: Mix, F. 1992. DB2 Reorg and continuous select access. In Proceedings of the Summer 1992 Meeting/SHARE 79. SHARE, Chicago, 2577--2614. Vol. II (microfiche). (Mix {1994} describes a revision.)
• 204: Mix, F. 1994. DB2 Reorg and continuous select. In Proceedings of the 6th Annual North American Conference of the International DB2 Users Group. IDUG, Chicago, 545--563.
• 205: Mizoguchi, M. and Nishiyama, K. 1994. Database management system. Japan patent 06-67944.
• 206: Kazuhiko Mogi , Masaru Kitsuregawa, Dynamic parity stripe reorganizations for RAID5 disk arrays, Proceedings of the third international conference on on Parallel and distributed information systems, p.17-26, October 1994, Autin, Texas, United States
• 207: Kazuhiko Mogi , Masaru Kitsuregawa, Hot Block Clustering for Disk Arrays with Dynamic Striping, Proceedings of the 21th International Conference on Very Large Data Bases, p.90-99, September 11-15, 1995
• 208: C. Mohan, IBM's relational DBMS products: features and technologies, Proceedings of the 1993 ACM SIGMOD international conference on Management of data, p.445-448, May 25-28, 1993, Washington, D.C., United States
• 209: C. Mohan, A Survey of DBMS Research Issues in Supporting Very Large Tables, Proceedings of the 4th International Conference on Foundations of Data Organization and Algorithms, p.279-300, October 13-15, 1993
• 210: C. Mohan , Don Haderle , Bruce Lindsay , Hamid Pirahesh , Peter Schwarz, ARIES: a transaction recovery method supporting fine-granularity locking and partial rollbacks using write-ahead logging, ACM Transactions on Database Systems (TODS), v.17 n.1, p.94-162, March 1992 [doi>10.1145/128765.128770]
• 211: C. Mohan , Inderpal Narang, Algorithms for creating indexes for very large tables without quiescing updates, Proceedings of the 1992 ACM SIGMOD international conference on Management of data, p.361-370, June 02-05, 1992, San Diego, California, United States
• 212: C. Mohan , Inderpal Narang, An efficient and flexible method for archiving a data base, Proceedings of the 1993 ACM SIGMOD international conference on Management of data, p.139-146, May 25-28, 1993, Washington, D.C., United States
• 213: A. Moitra , S. S. Iyengar , F. B. Bastani , I. L. Yen, Multilevel Data Structures: Models and Performance, IEEE Transactions on Software Engineering, v.14 n.6, p.858-867, June 1988 [doi>10.1109/32.6164]
• 214: Mondal, A. 2002. Query-centric online reorganization of indexed data in shared-nothing architectures. Ph.D. dissertation, School of Computing, National University of Singapore.
• 215: Anirban Mondal , Masaru Kitsuregawa , Beng Chin Ooi , Kian Lee Tan, R-tree-based data migration and self-tuning strategies in shared-nothing spatial databases, Proceedings of the 9th ACM international symposium on Advances in geographic information systems, November 09-10, 2001, Atlanta, Georgia, USA [doi>10.1145/512161.512169]
• 216: Magdi M. A. Morsi, Extensible object-oriented databases with dynamic schemas, Georgia Institute of Technology, Atlanta, GA, 1992
• 217: Morsi, M. M. A., Navathe, S. B., and Kim, H.-J. 1991. A schema management and prototyping interface for an object-oriented database environment. In Proceedings of the IFIP Working Conference on Object-Oriented Approach in Information Systems, F. Van Assche, B. Moulin, and C. Rolland, Eds. North-Holland, Amsterdam, The Netherlands, 157--180. (For more details, see Morsi {1992}.)
• 218: Magdi M. A. Morsi , Shamkant B. Navathe , Hyoung-Joo Kim, An Extensible Object-Oriented Database Testbed, Proceedings of the Eighth International Conference on Data Engineering, p.150-157, February 03-07, 1992
• 219: Moss, J. E. B., Munro, D. S., and Hudson, R. L. 1997. PMOS: A complete and coarse-grained incremental garbage collector for persistent object stores. In Proceedings of the 7th International Workshop on Persistent Object Systems, R. Connor and S. Nettles, Eds. Morgan Kaufmann Publishers, San Francisco, 140--150. (Munro et al. {1999} describe an implementation.)
• 220: David S. Munro , Alfred L. Brown , Ronald Morrison , J. Eliot B. Moss, Incremental Garbage Collection of a Persistent Object Store using PMOS, Proceedings of the 8th International Workshop on Persistent Object Systems (POS8) and Proceedings of the 3rd International Workshop on Persistence and Java (PJW3): Advances in Persistent Object Systems, p.78-91, January 1999
• 221: Scott Nettles , James O'Toole, Real-time replication garbage collection, Proceedings of the ACM SIGPLAN 1993 conference on Programming language design and implementation, p.217-226, June 21-25, 1993, Albuquerque, New Mexico, United States
• 222: Kelvin D. Nilsen , William J. Schmidt, Cost-effective object space management for hardware-assisted real-time garbage collection, ACM Letters on Programming Languages and Systems (LOPLAS), v.1 n.4, p.338-354, Dec. 1992 [doi>10.1145/161494.161508]
• 223: O. Nurmi , E. Soisalon-Soininen , D. Wood, Concurrency control in database structures with relaxed balance, Proceedings of the sixth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, p.170-176, March 23-25, 1987, San Diego, California, United States [doi>10.1145/28659.28677]
• 224: Erik Odberg, A Global Perspective of Schema Modification Management for Object-Oriented Databases, Proceedings of the Sixth International Workshop on Persistent Object Systems, p.479-502, September 05-09, 1994
• 225: Olson, N. E. 1993. Partial indexing in POSTGRES. M.S. dissertation. Department of Electrical Engineering and Computer Science, University of California, Berkeley.
• 226: Omiecinski, E. 1985a. Concurrency during the reorganization of indexed files. In Proceedings of the 9th International Conference on Computer Software and Applications (COMPSAC 85). IEEE Computer Society Press, Los Alamitos, 482--488.
• 227: Edward Omiecinski, Incremental file reorganization schemes, Proceedings of the 11th international conference on Very Large Data Bases, p.346-357, August 21-23, 1985, Stockholm, Sweden
• 228: Edward Omiecinski, Concurrent Storage Structure Conversion: from B+ Tree to Linear Hash File, Proceedings of the Fourth International Conference on Data Engineering, p.589-596, February 01-05, 1988
• 229: E. Omiecinski, Concurrent file conversion between B⁺-tree and linear hash files, Information Systems, v.14 n.5, p.371-383, 1989 [doi>10.1016/0306-4379(89)90002-1]
• 230: Omiecinski, E. 1996. Concurrent file reorganization: Clustering, conversion and maintenance. Data Engin. 19, 2, 25--32. IEEE-CS TC DE.
• 231: Edward Omiecinski , Liehuey Lee , Peter Scheuermann, Concurrent File Reorganization for Record Clustering: A Performance Study, Proceedings of the Eighth International Conference on Data Engineering, p.265-272, February 03-07, 1992
• 232: E. Omiecinski , L. Lee , P. Scheuermann, Performance Analysis of a Concurrent File Reorganization Algorithm for Record Clustering, IEEE Transactions on Knowledge and Data Engineering, v.6 n.2, p.248-257, April 1994 [doi>10.1109/69.277769]
• 233: Edward Omiecinski , Peter Scheuermann, A global approach to record clustering and file reorganization, Proc. of the third joint BCS and ACM symposium on Research and development in information retrieval, p.201-219, November 1984, King's College, Cambridge
• 234: Oracle. 2005. Oracle Database 10g Release 2 online data reorganization & redefinition. Oracle White Paper.
• 235: S. L. Osborn, The Role of Polymorphism in Schema Evolution in an Object-Oriented Database, IEEE Transactions on Knowledge and Data Engineering, v.1 n.3, p.310-317, September 1989 [doi>10.1109/69.87977]
• 236: Yoav Ossia , Ori Ben-Yitzhak , Irit Goft , Elliot K. Kolodner , Victor Leikehman , Avi Owshanko, A parallel, incremental and concurrent GC for servers, Proceedings of the ACM SIGPLAN 2002 Conference on Programming language design and implementation, June 17-19, 2002, Berlin, Germany
• 237: James O'Toole , Scott Nettles , David Gifford, Concurrent compacting garbage collection of a persistent heap, Proceedings of the fourteenth ACM symposium on Operating systems principles, p.161-174, December 05-08, 1993, Asheville, North Carolina, United States
• 238: John Ousterhout , Fred Douglis, Beating the I/O bottleneck: a case for log-structured file systems, ACM SIGOPS Operating Systems Review, v.23 n.1, p.11-28, Jan. 1989 [doi>10.1145/65762.65765]
• 239: J. S. Park , R. Bartoszynski , Prabuddha De , H. Pirkul, Optimal reorganization policies for stationary and evolutionary, Management Science, v.36 n.5, p.613-631, May 1990 [doi>10.1287/mnsc.36.5.613]
• 240: Park, J. S., Bartoszynski, R., and Pirkul, H. 1989. Optimal database reorganization policies: A stochastic control approach. In Proceedings of the 22nd Annual Hawaii International Conference on System Sciences. Vol. 3. IEEE Computer Society Press, Los Alamitos, 752--761. (For a revision, see Park et al. {1990}.)
• 241: June S. Park , V. Sridhar, Probabilistic Model and Optimal Reorganization of B+-Tree with Physical Clustering, IEEE Transactions on Knowledge and Data Engineering, v.9 n.5, p.826-832, September 1997 [doi>10.1109/69.634758]
• 242: Harel Paz , David F. Bacon , Elliot K. Kolodner , Erez Petrank , V. T. Rajan, An efficient on-the-fly cycle collection, ACM Transactions on Programming Languages and Systems (TOPLAS), v.29 n.4, p.20-es, August 2007 [doi>10.1145/1255450.1255453]
• 243: Paz, H., Petrank, E., Bacon, D. F., Kolodner, E. K., and Rajan, V. T. 2005. An efficient on-the-fly cycle collection. In Compiler Construction: 14th International Conference, CC 2005, Held as Part of Joint European Conferences on Theory and Practice of Software, ETAPS 2005, R. Bodik, Ed. Lecture Notes in Computer Science, vol. 3443. Springer-Verlag, New York, 156--171. (For a revision, see Paz et al. {2007}.)
• 244: Pereira, H. M. 2000. Method and apparatus for reorganizing an active DBMS table. U.S. patent 6,122, 640.
• 245: Randal J. Peters , M. Tamer Özsu, Axiomatization of Dynamic Schema Evolution in Objectbases, Proceedings of the Eleventh International Conference on Data Engineering, p.156-164, March 06-10, 1995
• 246: Randel J. Peters , M. Tamer Özsu, An axiomatic model of dynamic schema evolution in objectbase systems, ACM Transactions on Database Systems (TODS), v.22 n.1, p.75-114, March 1997 [doi>10.1145/244810.244813]
• 247: Filip Pizlo , Daniel Frampton , Erez Petrank , Bjarne Steensgaard, Stopless: a real-time garbage collector for multiprocessors, Proceedings of the 6th international symposium on Memory management, October 21-22, 2007, Montreal, Quebec, Canada [doi>10.1145/1296907.1296927]
• 248: Filip Pizlo , Erez Petrank , Bjarne Steensgaard, A study of concurrent real-time garbage collectors, Proceedings of the 2008 ACM SIGPLAN conference on Programming language design and implementation, June 07-13, 2008, Tucson, AZ, USA
• 249: Plow, G. M., Pourmirzaie, F. E., and Shiomi, T. 2008. Method for reorganizing a set of database partitions. U.S. patent 7,454,449.
• 250: Kerttu Pollari-Malmi , Eljas Soisalon-Soininen , Tatu Ylönen, Concurrency Control in B-Trees with Batch Updates, IEEE Transactions on Knowledge and Data Engineering, v.8 n.6, p.975-984, December 1996 [doi>10.1109/69.553166]
• 251: Pong, M. 1990. An overview of NonStop SQL Release 2. Tandem Syst. Rev. 6, 2, 4--11.
• 252: Nagavamsi Ponnekanti , Hanuma Kodavalla, Online index rebuild, Proceedings of the 2000 ACM SIGMOD international conference on Management of data, p.529-538, May 15-18, 2000, Dallas, Texas, United States
• 253: Tony Printezis , David Detlefs, A generational mostly-concurrent garbage collector, Proceedings of the 2nd international symposium on Memory management, p.143-154, October 15-16, 2000, Minneapolis, Minnesota, United States
• 254: Calton Pu, On-the-fly, incremental, consistent reading of entire databases, Proceedings of the 11th international conference on Very Large Data Bases, p.369-375, August 21-23, 1985, Stockholm, Sweden
• 255: Pu, C. 1986. On-the-fly, incremental, consistent reading of entire databases. Algorithmica 1, 3, 271--287.
• 256: C. Pu , C. H. Hong , J. M. Wha, Performance evaluation of global reading of entire databases, Proceedings of the first international symposium on Databases in parallel and distributed systems, p.167-176, December 05-07, 1988, Austin, Texas, United States
• 257: Wolfgang Puffitsch , Martin Schoeberl, Non-blocking root scanning for real-time garbage collection, Proceedings of the 6th international workshop on Java technologies for real-time and embedded systems, September 24-26, 2008, Santa Clara, California [doi>10.1145/1434790.1434801]
• 258: Young-Gook Ra , Elke A. Rundensteiner, A Transparent Object-Oriented Schema Change Approach Using View Evolution, Proceedings of the Eleventh International Conference on Data Engineering, p.165-172, March 06-10, 1995
• 259: Young-Gook Ra , Elke A. Rundensteiner, A Transparent Schema-Evolution System Based on Object-Oriented View Technology, IEEE Transactions on Knowledge and Data Engineering, v.9 n.4, p.600-624, July 1997 [doi>10.1109/69.617053]
• 260: Radosevich, L. 1993. Hotel cans mainframes. Computerworld 27, 8, 1 and 16.
• 261: Taming the Downtime: High Availability in Sybase ASE 12, Proceedings of the 16th International Conference on Data Engineering, p.111, February 28-March 03, 2000
• 262: Erhard Rahm , Philip A. Bernstein, An online bibliography on schema evolution, ACM SIGMOD Record, v.35 n.4, p.30-31, December 2006 [doi>10.1145/1228268.1228273]
• 263: Ram, S. and Shankaranarayanan, G. 2003. Research issues in database schema evolution: The road not taken. Working Paper 2003-15, Information Systems Department, Boston University School of Management.
• 264: Ramírez, R. J., Tompa, F. W., and Munro, J. I. 1982. Optimum reorganization points for arbitrary database costs. Acta Informatica 18, 1, 17--30.
• 265: Rengarajan, T. K., Dimino, L., and Chung, D. 1996. Sybase System 11 online capabilities. Data Engin. 19, 2, 19--24.
• 266: John T. Robinson , Peter A. Franaszek, Analysis of Reorganization Overhead in Log-Structured File Systems, Proceedings of the Tenth International Conference on Data Engineering, p.102-110, February 14-18, 1994
• 267: John F. Roddick, Dynamically changing schemas within database models, Australian Computer Journal, v.23 n.3, p.105-109, Aug. 1991
• 268: John F. Roddick, Schema evolution in database systems: an annotated bibliography, ACM SIGMOD Record, v.21 n.4, p.35-40, Dec. 1992 [doi>10.1145/141818.141826]
• 269: Roddick, J. F. 1994. Schema evolution in database systems—An updated bibliography. Tech. rep. CIS-94-012, School of Computer and Information Science, University of South Australia, The Levels, S. Australia.
• 270: Roddick, J. F. 1995. A survey of schema versioning issues for database systems. Inf. Softw. Tech. 37, 7, 383--393.
• 271: On-line Schema Update for a Telecom Database, Proceedings of the 16th International Conference on Data Engineering, p.329, February 28-March 03, 2000
• 272: Mendel Rosenblum , John K. Ousterhout, The design and implementation of a log-structured file system, ACM Transactions on Computer Systems (TOCS), v.10 n.1, p.26-52, Feb. 1992 [doi>10.1145/146941.146943]
• 273: Daniel J. Rosenkrantz, Dynamic database dumping, Proceedings of the 1978 ACM SIGMOD international conference on management of data, May 31-June 02, 1978, Austin, Texas [doi>10.1145/509252.509257]
• 274: Roy, P., Seshadri, S., Silberschatz, A., and Sudarshan, S. 2002. Garbage collection in object-oriented databases using transactional cyclic reference counting. U.S. patent 6,363,403.
• 275: P. Roy , S. Seshadri , A. Silberschatz , S. Sudarshan , S. Ashwin, Garbage collection in object-oriented databases using transactional cyclic reference counting, The VLDB Journal — The International Journal on Very Large Data Bases, v.7 n.3, p.179-193, August 1998 [doi>10.1007/s007780050062]
• 276: Ruddy, J. A., Shyam, K., Sockut, G. H., and Watts, J. A. 1999. Application of log records to data compressed with different encoding scheme. U.S. patent 5,897,641.
• 277: Yehoshua Sagiv, Concurrent operations on B-trees with overtaking, Proceedings of the fourth ACM SIGACT-SIGMOD symposium on Principles of database systems, p.28-37, March 25-27, 1985, Portland, Oregon, United States [doi>10.1145/325405.325409]
• 278: Yehoshua Sagiv, Concurrent operations on B*-trees with overtaking, Journal of Computer and System Sciences, v.33 n.2, p.275-296, Oct. 1986 [doi>10.1016/0022-0000(86)90021-8]
• 279: Salant, E. E. and Kolodner, E. K. 2002. Data structure for keeping track of objects remaining to be traced by concurrent garbage collector. U.S. patent 6,393,440.
• 280: Kenneth Salem , Hector Garcia-Molina, Disk Striping, Proceedings of the Second International Conference on Data Engineering, p.336-342, February 05-07, 1986
• 281: Salzberg, B. 1985. Restructuring the Lehman-Yao tree. Tech. rep. BS-85-21, College of Computer Science, Northeastern University, Boston.
• 282: Betty Salzberg , Allyn Dimock, Principles of Transaction-Based On-Line Reorganization, Proceedings of the 18th International Conference on Very Large Data Bases, p.511-520, August 23-27, 1992
• 283: P. Scheuermann , Y. C. Park , E. Omiecinski, A heuristic file reorganization algorithm based on record clustering, BIT, v.29 n.3, p.428-447, August 1989 [doi>10.1007/BF02219229]
• 284: Peter Scheuermann , Gerhard Weikum , Peter Zabback, Adaptive Load Balancing in Disk Arrays, Proceedings of the 4th International Conference on Foundations of Data Organization and Algorithms, p.345-360, October 13-15, 1993
• 285: Scheuermann, P., Weikum, G., and Zabback, P. 1994. “Disk cooling” in parallel disk systems. Bull. Tech. Committee Data Engin. 17, 3, 29--40.
• 286: Peter Scheuermann , Gerhard Weikum , Peter Zabback, Data partitioning and load balancing in parallel disk systems, The VLDB Journal — The International Journal on Very Large Data Bases, v.7 n.1, p.48-66, February 1998 [doi>10.1007/s007780050053]
• 287: William J. Schmidt , Kelvin D. Nilsen, Performance of a hardware-assisted real-time garbage collector, Proceedings of the sixth international conference on Architectural support for programming languages and operating systems, p.76-85, October 05-07, 1994, San Jose, California, United States
• 288: Martin Schoeberl , Wolfgang Puffitsch, Non-blocking object copy for real-time garbage collection, Proceedings of the 6th international workshop on Java technologies for real-time and embedded systems, September 24-26, 2008, Santa Clara, California [doi>10.1145/1434790.1434802]
• 289: Schubert, R. F. 1974. Directions in data base management technology. Datamation 20, 9 (Sept), 48--51.
• 290: Peter M. Schwarz , Kurt A. Shoens, Managing Change in the Rufus System, Proceedings of the Tenth International Conference on Data Engineering, p.170-179, February 14-18, 1994
• 291: Seidl, M. L., Wright, G. M., and Wolczko, M. I. 2008. Method and system for concurrent garbage collection and mutator execution. U.S. patent 7,421,539.
• 292: Patricia G. Selinger, Predictions and Challenges for Database Systems in the Year 2000, Proceedings of the 19th International Conference on Very Large Data Bases, p.667-675, August 24-27, 1993
• 293: Margo Seltzer , Keith Bostic , Marshall Kirk Mckusick , Carl Staelin, An implementation of a log-structured file system for UNIX, Proceedings of the USENIX Winter 1993 Conference Proceedings on USENIX Winter 1993 Conference Proceedings, p.3-3, January 25-29, 1993, San Diego, California
• 294: Dennis G. Severance , Guy M. Lohman, Differential files: their application to the maintenance of large databases, ACM Transactions on Database Systems (TODS), v.1 n.3, p.256-267, Sept. 1976 [doi>10.1145/320473.320484]
• 295: Dennis Shasha , Nathan Goodman, Concurrent search structure algorithms, ACM Transactions on Database Systems (TODS), v.13 n.1, p.53-90, March 1988 [doi>10.1145/42201.42204]
• 296: Ben Shneiderman, Optimum data base reorganization points, Communications of the ACM, v.16 n.6, p.362-365, June 1973 [doi>10.1145/362248.362267]
• 297: Fridtjof Siebert, Limits of parallel marking garbage collection, Proceedings of the 7th international symposium on Memory management, June 07-08, 2008, Tucson, AZ, USA [doi>10.1145/1375634.1375638]
• 298: Avi Silberschatz , Michael Stonebraker , Jeff Ullman, Database systems: achievements and opportunities, Communications of the ACM, v.34 n.10, p.110-120, Oct. 1991 [doi>10.1145/125223.125272]
• 299: Singhal, V., Kakkad, S. V., and Wilson, P. R. 1992. Texas: An efficient, portable persistent store. In Proceedings of the 5th International Workshop on Persistent Object Systems, A. Albano and R. Morrison, Eds. Springer-Verlag, New York, 11--33.
• 300: Siwiec, J. E. 1977. A high-performance DB/DC system. IBM Syst. J. 16, 2, 169--195.
• 301: Marcin Skubiszewski , Patrick Valduriez, Concurrent Garbage Collection in O2, Proceedings of the 23rd International Conference on Very Large Data Bases, p.356-365, August 25-29, 1997
• 302: Smith, B. F. 1994. Understanding DB2 RUNSTATS statistics and version 3 enhancements. In Proceedings of the SHARE 82. Vol. II (CD-ROM). SHARE, Chicago.
• 303: Smith, G. S. 1990. Online reorganization of key-sequenced tables and files. Tandem Syst. Rev. 6, 2, 52--59.
• 304: Sockut, G. H. 1974. A graphics monitor for animation of dynamic processes. M.S. dissertation., Department of Electrical Engineering, Massachusetts Institute of Technology, Cambridge.
• 305: Sockut, G. H. 1977. Data base performance under concurrent reorganization and usage. Ph.D. dissertation, Division of Applied Sciences, Harvard University, Cambridge. (Also Tech. rep. 12-77, Center for Research in Computing Technology.)
• 306: Sockut, G. H. 1978. A performance model for computer data-base reorganization performed concurrently with usage. Oper. Res. 26, 5, 789--804. (For more details, see Sockut {1977}.)
• 307: G. H. Sockut, A Framework for Logical-Level Changes Within Database Systems, Computer, v.18 n.5, p.9-27, May 1985 [doi>10.1109/MC.1985.1662890]
• 308: Sockut, G. H. and Beavin, T. A. 1998. Interaction between application of a log and maintenance of a table that maps record identifiers during online reorganization of a database. U.S. patent 5,721,915. (Also U.S. Patent 6,026,412, 2000.)
• 309: G. H. Sockut , T. A. Beavin , C.-C. Chang, A method for on-line reorganization of a database, IBM Systems Journal, v.36 n.3, p.411-436, 1997
• 310: Sockut, G. H. and Goldberg, R. P. 1976. Motivation for data base reorganization performed concurrently with usage. Tech. rep. 16-76, Center for Research in Computing Technology, Harvard University, Cambridge, MA. (full article). (Also in Preprints, IEEE-CS Workshop on Operating and Data base Management Systems (Datab. Engin. 1, 1, 1977, IEEE-CS Technical Communication on Data Base Engineering), 18-19 (abstract). For more details, see Sockut {1977}.)
• 311: Gary H. Sockut , Robert P. Goldberg, Database Reorganization—Principles and Practice, ACM Computing Surveys (CSUR), v.11 n.4, p.371-395, Dec. 1979 [doi>10.1145/356789.356796]
• 312: Sockut, G. H. and Iyer, B. R. 1996. A survey on online reorganization in IBM products and research. Data Engin. 19, 2, 4--11.
• 313: Söderlund, L. 1980. A study on concurrent data base reorganization. Ph.D. dissertation. Deparment of Information Processing and Computer Science, University of Stockholm, Sweden.
• 314: Lars Söderlund, Concurrent data base reorganization - assessment of a powerful technique through modeling, Proceedings of the seventh international conference on Very Large Data Bases, p.499-509, September 09-11, 1981, Cannes, France
• 315: Lars Söderlund, Evaluation of concurrent physical database reorganization through simulation modeling, Proceedings of the 1981 ACM SIGMETRICS conference on Measurement and modeling of computer systems, p.19-32, September 14-16, 1981, Las Vegas, Nevada, United States
• 316: Jagannathan Srinivasan , Souripriya Das , Chuck Freiwald , Eugene Inseok Chong , Mahesh Jagannath , Aravind Yalamanchi , Ramkumar Krishnan , Anh-Tuan Tran , Samuel DeFazio , Jayanta Banerjee, Oracle8i Index-Organized Table and Its Application to New Domains, Proceedings of the 26th International Conference on Very Large Data Bases, p.285-296, September 10-14, 2000
• 317: Venkatachary Srinivasan, On-line processing in large-scale transaction systems, University of Wisconsin at Madison, Madison, WI, 1992
• 318: Srinivasan, V. and Carey, M. J. 1991a. On-line index construction algorithms. Tech. rep. 1008, Computer Sciences Department, University of Wisconsin, Madison. (Presented at 4th International Workshop on High-Performance Transaction Systems; For more details, see Srinivasan {1992}.)
• 319: V. Srinivasan , Michael J. Carey, Performance of B-tree concurrency control algorithms, Proceedings of the 1991 ACM SIGMOD international conference on Management of data, p.416-425, May 29-31, 1991, Denver, Colorado, United States
• 320: V. Srinivasan , Michael J. Carey, Compensation-based on-line query processing, Proceedings of the 1992 ACM SIGMOD international conference on Management of data, p.331-340, June 02-05, 1992, San Diego, California, United States
• 321: V. Srinivasan , Michael J. Carey, Performance of On-Line Index Construction Algorithms, Proceedings of the 3rd International Conference on Extending Database Technology: Advances in Database Technology, p.293-309, March 23-27, 1992
• 322: V. Srinivasan , Michael J. Carey, Performance of B⁺ tree concurrency control algorithms, The VLDB Journal — The International Journal on Very Large Data Bases, v.2 n.4, p.361-406, October 1993 [doi>10.1007/BF01263046]
• 323: Sylvain Stanchina , Matthias Meyer, Mark-sweep or copying?: a "best of both worlds" algorithm and a hardware-supported real-time implementation, Proceedings of the 6th international symposium on Memory management, October 21-22, 2007, Montreal, Quebec, Canada [doi>10.1145/1296907.1296928]
• 324: Michael Stonebraker, Hypothetical data bases as views, Proceedings of the 1981 ACM SIGMOD international conference on Management of data, April 29-May 01, 1981, Ann Arbor, Michigan [doi>10.1145/582318.582352]
• 325: M. Stonebraker, The case for partial indexes, ACM SIGMOD Record, v.18 n.4, p.4-11, Dec. 1989 [doi>10.1145/74120.74121]
• 326: Michael Stonebraker , Randy H. Katz , David A. Patterson , John K. Ousterhout, The Design of XPRS, Proceedings of the 14th International Conference on Very Large Data Bases, p.318-330, August 29-September 01, 1988
• 327: Strickland, J. P., Uhrowczik, P. P., and Watts, V. L. 1982. IMS/VS: An evolving system. IBM Syst. J. 21, 4, 490--510.
• 328: Subramaniam, M. and Loaiza, J. 2005. Online reorganization and redefinition of relational database tables. U.S. patent 6,965,899.
• 329: Sun, X. 2005. Online reorganization in parallel database systems: Scalability, load balancing and high availability. Ph.D. dissertation, College of Computer Science, Northeastern University, Boston.
• 330: Xiaowei Sun , Rui Wang , Betty Salzberg , Chendong Zou, Online B-tree merging, Proceedings of the 2005 ACM SIGMOD international conference on Management of data, June 14-16, 2005, Baltimore, Maryland [doi>10.1145/1066157.1066196]
• 331: Takahashi, H. and Takahashi, J. 1990. Record-type change method by binary relations. IBM Tech. Disclosure Bull. 33, 2, 262--264. (For more details, see Takahashi {1990}.)
• 332: Takahashi, J. 1990. Hybrid relations for database schema evolution. In Proceedings of the 14th Annual International Computer Software and Applications Conference (COMPSAC 90). IEEE Computer Society Press, Los Alamitos, 465--470.
• 333: Tan, L. and Katayama, T. 1990. Meta operations for type management in object-oriented databases: A lazy mechanism for schema evolution. In Proceedings of the 1st International Conference on Deductive and Object-Oriented Databases, W. Kim, J.-M. Nicolas, and S. Nishio, Eds. North-Holland, Amsterdam, The Netherlands, 241--258.
• 334: Robert W. Taylor , Randall L. Frank, CODASYL Data-Base Management Systems, ACM Computing Surveys (CSUR), v.8 n.1, p.67-103, March 1976 [doi>10.1145/356662.356666]
• 335: Tene, G. and Wolf, M. A. 2008. System and method for concurrent compacting self pacing garbage collection using loaded value and access barriers. U.S. patent 7,469,324.
• 336: Teng, J. Z. and Todd, J. A. 2002. Method, system, and program for managing file names during the reorganization of a database object. U.S. patent 6,460,048.
• 337: Toby J. Teorey , James P. Fry, Design of Database Structures, Prentice Hall Professional Technical Reference, 1982
• 338: Baltasar Trancón y Widemann, A reference-counting garbage collection algorithmfor cyclical functional programming, Proceedings of the 7th international symposium on Memory management, June 07-08, 2008, Tucson, AZ, USA [doi>10.1145/1375634.1375645]
• 339: Markus Tresch , Marc H. Scholl, Schema transformation without database reorganization, ACM SIGMOD Record, v.22 n.1, p.21-27, March 1993 [doi>10.1145/156883.156886]
• 340: Troisi, J. 1994. Nonstop availability and database configuration operations. Tandem Syst. Rev. 10, 3, 18--23.
• 341: Troisi, J. 1996. Nonstop SQL/MP availability and database configuration operations. Data Engin. 19, 2, 12--18.
• 342: William G. Tuel, Jr., Optimum reorganization points for linearly growing files, ACM Transactions on Database Systems (TODS), v.3 n.1, p.32-40, March 1978 [doi>10.1145/320241.320244]
• 343: Patrick Valduriez, Parallel database systems: open problems and new issues, Distributed and Parallel Databases, v.1 n.2, p.137-165, April 1993 [doi>10.1007/BF01264049]
• 344: Martin T. Vechev , Eran Yahav , David F. Bacon, Correctness-preserving derivation of concurrent garbage collection algorithms, Proceedings of the 2006 ACM SIGPLAN conference on Programming language design and implementation, June 11-14, 2006, Ottawa, Ontario, Canada
• 345: Martin T. Vechev , Eran Yahav , David F. Bacon , Noam Rinetzky, CGCExplorer: a semi-automated search procedure for provably correct concurrent collectors, Proceedings of the 2007 ACM SIGPLAN conference on Programming language design and implementation, June 10-13, 2007, San Diego, California, USA
• 346: Versant Object Technology. 1991. VERSANT System Reference Manual (for IBM RISC System/6000). Versant Object Technology.
• 347: Radek Vingralek , Yuri Breitbart , Gerhard Weikum, Distributed file organization with scalable cost/performance, Proceedings of the 1994 ACM SIGMOD international conference on Management of data, p.253-264, May 24-27, 1994, Minneapolis, Minnesota, United States
• 348: Radek Vingralek , Yuri Breitbart , Gerhard Weikum, Snowball: Scalable Storage on Networks of Workstations with Balanced Load, Distributed and Parallel Databases, v.6 n.2, p.117-156, April 1998 [doi>10.1023/A:1008609030195]
• 349: Jun Wang , Yiming Hu, PROFS-Performance-Oriented Data Reorganization for Log-Structured File System on Multi-Zone Disks, Proceedings of the Ninth International Symposium in Modeling, Analysis and Simulation of Computer and Telecommunication Systems, p.285, August 15-18, 2001
• 350: Jun Wang , Yiming Hu, WOLF - A Novel Reordering Write Buffer to Boost the Performance of Log-Structured File Systems, Proceedings of the Conference on File and Storage Technologies, p.47-60, January 28-30, 2002
• 351: Jun Wang , Yiming Hu, A Novel Reordering Write Buffer to Improve Write Performance of Log-Structured File Systems, IEEE Transactions on Computers, v.52 n.12, p.1559-1572, December 2003 [doi>10.1109/TC.2003.1252852]
• 352: Randolph Y. Wang , Thomas E. Anderson , David A. Patterson, Virtual log based file systems for a programmable disk, Proceedings of the third symposium on Operating systems design and implementation, p.29-43, February 1999, New Orleans, Louisiana, United States
• 353: Michal Wegiel , Chandra Krintz, The mapping collector: virtual memory support for generational, parallel, and concurrent compaction, Proceedings of the 13th international conference on Architectural support for programming languages and operating systems, March 01-05, 2008, Seattle, WA, USA
• 354: Weikum, G. 1989. Clustering vs. concurrency: A framework and a case study. Tech. rep. ACA-ST-096-89, MCC, Austin.
• 355: Gerhard Weikum , Peter Zabback , Peter Scheuermann, Dynamic file allocation in disk arrays, Proceedings of the 1991 ACM SIGMOD international conference on Management of data, p.406-415, May 29-31, 1991, Denver, Colorado, United States
• 356: Gio C. Wiederhold, Database Design, McGraw-Hill, Inc., New York, NY, 1983
• 357: John Wilkes , Richard Golding , Carl Staelin , Tim Sullivan, The HP AutoRAID hierarchical storage system, ACM Transactions on Computer Systems (TOCS), v.14 n.1, p.108-136, Feb. 1996 [doi>10.1145/225535.225539]
• 358: Paul R. Wilson, Uniprocessor Garbage Collection Techniques, Proceedings of the International Workshop on Memory Management, p.1-42, September 17-19, 1992
• 359: Wilson, T. B. 1979. Data base restructuring: Options and obstacles. In Proceedings of the European Conference on Applied Information Technology (EURO IFIP 79), P. A. Samet, Ed. North-Holland, Amsterdam, The Netherlands, 567--573.
• 360: Wilson, T. B. 1980. The description and usage of evolving schemas. In Proceedings of the 4th International Computer Software and Application Conference (COMPSAC '80). IEEE Computer Society Press, Los Alamitos, 546--551.
• 361: L. E. Winslow , J. C. Lee, Optimal choice of data restructuring points, Proceedings of the 1st International Conference on Very Large Data Bases, September 22-24, 1975, Framingham, Massachusetts [doi>10.1145/1282480.1282506]
• 362: Winter. 2005. TopTen program winners. On the web site (http://www.wintercorp.com), search the press releases for the most recent TopTen Program Winners.
• 363: Wolczko, M. and Williams, I. 1992. Multi-level garbage collection in a high-performance persistent object system. In Proceedings of the 5th International Workshop on Persistent Object Systems, A. Albano and R. Morrison, Eds. Springer-Verlag, New York, 396--418.
• 364: S. B. Yao , K. S. Das , T. J. Teorey, A dynamic database reorganization algorithm, ACM Transactions on Database Systems (TODS), v.1 n.2, p.159-174, June 1976 [doi>10.1145/320455.320467]
• 365: Voon-Fee Yong , Jeffrey F. Naughton , Jie-Bing Yu, Storage Reclamation and Reorganization in Client-Server Persistent Object Stores, Proceedings of the Tenth International Conference on Data Engineering, p.120-131, February 14-18, 1994
• 366: Peter Zabback , Ibrahim Onyuksel , Peter Scheuermann , Gerhard Weikum, Database Reorganization in Parallel Disk Arrays with I/O Service Stealing, IEEE Transactions on Knowledge and Data Engineering, v.10 n.5, p.855-858, September 1998 [doi>10.1109/69.729749]
• 367: Stanley B. Zdonik, Maintaining consistency in a database with changing types, ACM SIGPLAN Notices, v.21 n.10, p.120-127, Oct. 1986
• 368: Daniel C. Zilio, Modeling on-line rebalancing with priorities and executing on parallel database systems, Proceedings of the 1996 conference of the Centre for Advanced Studies on Collaborative research, p.43, November 12-14, 1996, Toronto, Ontario, Canada
• 369: Daniel Costante Zilio , Kenneth C. Sevcik, Physical database design decision algorithms and concurrent reorganization for parallel database systems, University of Toronto, Toronto, Ont., Canada, 1998
• 370: Zou, C. and Salzberg, B. 1996a. Efficiently updating references during on-line reorganization. Tech. rep. NU-CCS-96-08, College of Computer Science, Northeastern University, Boston.
• 371: Chendong Zou , Betty Salzberg, On-line reorganization of sparsely-populated B+-trees, Proceedings of the 1996 ACM SIGMOD international conference on Management of data, p.115-124, June 04-06, 1996, Montreal, Quebec, Canada
• 372: Zou, C. and Salzberg, B. 1996c. Towards efficient online database reorganization. Data Engin. 19, 2, 33--40.
• 373: Chendong Zou , Betty Salzberg, Safely and Efficiently Updating References During On-line Reorganization, Proceedings of the 24rd International Conference on Very Large Data Bases, p.512-522, August 24-27, 1998

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.7 Database Administration

Additional Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.4 Distributed Systems
          Subjects: Distributed databases
  C.4 PERFORMANCE OF SYSTEMS

  D. Software
  D.2 SOFTWARE ENGINEERING
      D.2.9 Management
          Subjects: Life cycle
  D.3 PROGRAMMING LANGUAGES
      D.3.3 Language Constructs and Features
          Subjects: Dynamic storage management
      D.3.4 Processors
          Subjects: Memory management (garbage collection)
  D.4 OPERATING SYSTEMS
      D.4.1 Process Management
          Subjects: Scheduling; Synchronization; Concurrency
      D.4.2 Storage Management
          Subjects: Allocation/deallocation strategies; Garbage collection
      D.4.3 File Systems Management
          Subjects: File organization; Distributed file systems; Access methods
      D.4.9 Systems Programs and Utilities

  E. Data
  E.5 FILES
      Subjects: Organization/structure

  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.1 Logical Design
          Subjects: Schema and subschema
      H.2.2 Physical Design
          Subjects: Access methods
      H.2.4 Systems
          Subjects: Distributed databases; Concurrency; Parallel databases

  K. Computing Milieux
  K.6 MANAGEMENT OF COMPUTING AND INFORMATION SYSTEMS
      K.6.3 Software Management
          Subjects: Software maintenance

General Terms:
Algorithms, Design, Performance

Keywords:
Clustering, concurrent reorganization, indexes, log-structured file systems, maintenance, online reorganization, redefinition, reorganization, restructuring, schema evolution, very large databases