research-article

Online reorganization of databases

Authors:
Gary H. Sockut

IBM Silicon Valley Laboratory, San Jose, CA

IBM Silicon Valley Laboratory, San Jose, CA
View Profile

,
Balakrishna R. Iyer

IBM Silicon Valley Laboratory, San Jose, CA

IBM Silicon Valley Laboratory, San Jose, CA
View Profile

Authors Info & Claims

ACM Computing Surveys Volume 41 Issue 3Article No.: 14pp 1–136https://doi.org/10.1145/1541880.1541881

Published:30 July 2009Publication History

ACM Computing Surveys

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

Abdullahi, S. E. and Ringwood, G. A. 1998. Garbage collecting the Internet: A survey of distributed garbage collection. ACM Comput. Surv. 30, 3, 330--373. Google ScholarDigital Library
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.Google Scholar
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.Google Scholar
Achyutuni, K. J., Omiecinski, E., and Navathe, S. B. 1996. Two techniques for on-line index modification in shared nothing parallel databases. In Proceedings of the 1996 ACM SIGMOD International Conference on Management of Data. ACM, New York, 125--136. (SIGMOD Record 25, 2). Google ScholarDigital Library
Ahls&#233;n, M., Bj&#246;rnerstedt, A., Britts, S., Hult&#233;n, C., and S&#246;derlund, L. 1983. Making type changes transparent. In Proceedings of the IEEE Workshop on Languages for Automation. 110--117.Google Scholar
Ahls&#233;n, M., Bj&#246;rnerstedt, A., Britts, S., Hult&#233;n, C., and S&#246;derlund, L. 1984. An architecture for object management in OIS. ACM Trans. Office Info. Syst. 2, 3, 173--196. (This includes a summary of the work of Ahls&#233;n et al. {1983}). Google ScholarDigital Library
Almes, G. T. 1980. Garbage collection in an object-oriented system. Ph.D. dissertation, Department of Computer Science, Carnegie Mellon University, Pittsburgh. (Also Tech. rep. CMU-CS-80-128.) Google ScholarDigital Library
Amer. Natl. Standards Institute. 1992. Database Language SQL. Amer. National Standards Institute, New York. X3.135-1992.Google Scholar
Ammann, P., Jajodia, S., and Mavuluri, P. 1995. On-the-fly reading of entire databases. IEEE Trans. Knowl. Data Engin. 7, 5, 834--838. Google ScholarDigital Library
Amsaleg, L., Franklin, M. J., and Gruber, O. 1995. Efficient incremental garbage collection for client-server object database systems. In Proceedings of the 21st International Conference on Very Large Data Bases. Morgan Kaufmann Publishers, San Francisco, 42--53. (For a revision with more details, see Amsaleg etal. {1999}.) Google ScholarDigital Library
Amsaleg, L., Franklin, M. J., and Gruber, O. 1999. Garbage collection for a client-server persistent object store. ACM Trans. Computer Syst. 17, 3, 153--201. Google ScholarDigital Library
Appel, A. W., Ellis, J. R., and Li, K. 1988. Real-time concurrent collection on stock multiprocessors. In Proceedings of the SIGPLAN '88 Conference on Programming Language Design and Implementation. ACM, New York, 11--20. (SIGPLAN Notices 23, 7, ACM). Google ScholarDigital Library
Ashwin, S., Roy, P., Seshadri, S., Silberschatz, A., and Sudarshan, S. 1997. Garbage collection in object-oriented databases using transactional cyclic reference counting. In Proceedings of the 23rd International Conference on Very Large Data Bases. Morgan Kaufmann, San Francisco, 366--375. (For a revision with more details, see Roy et al. {1998}.) Google ScholarDigital Library
Azatchi, H., Levanoni, Y., Paz, H., and Petrank, E. 2003. An on-the-fly mark and sweep garbage collector based on sliding views. In Proceedings of the ACM SIGPLAN Conference on Object-Oriented Programming, Systems, Languages, and Applications (OOPSLA 2003). ACM, New York, 269--281. (SIGPLAN Notices 38, 11). Google ScholarDigital Library
Bacon, D. F. 2007. Real-time garbage collection. Queue 5, 1, 40--49. ACM, New York. Google ScholarDigital Library
Bacon, D. F., Cheng, P., and Rajan, V. T. 2004. A unified theory of garbage collection. In Proceedings of the 19th Annual ACM SIGPLAN Conference on Object-Oriented Programming, Systems, Languages, and Applications (OOPSLA 2004). ACM, New York, 50--68. (SIGPLAN Notices 39, 10). Google ScholarDigital Library
Bahaa-El-Din, W. H., Bastani, F. B., and Teng, J.-E. 1989. Performance analysis of periodic and concurrent data structure maintenance strategies for network servers. IEEE Trans. Soft. Engin. 15, 12, 1526--1536. Google ScholarDigital Library
Baker, Jr., H. G. 1978. List processing in real-time on a serial computer. Comm. ACM 21, 4, 280--294. Google ScholarDigital Library
Banerjee, J., Kim, W., Kim, H.-J., and Korth, H. F. 1987. Semantics and implementation of schema evolution in object-oriented databases. In Proceedings of the ACM SIGMOD 1987 Annual Conference. ACM, New York, 311--322. (SIGMOD Record 16, 3). Google ScholarDigital Library
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.Google Scholar
Barabash, K., Ben-Yitzhak, O., Goft, I., Kolodner, E. K., Leikehman, V., Ossia, Y., Owshanko, A., and Petrank, E. 2005. A parallel, incremental, mostly concurrent garbage collector for servers. ACM Trans. Prog. Lang. Syst. 27, 6, 1097--1146. Google ScholarDigital Library
Barabash, K., Ossia, Y., and Petrank, E. 2003. Mostly concurrent garbage collection revisited. In Proceedings of the ACM SIGPLAN Conference on Object-Oriented Programming, Systems, Languages, and Applications (OOPSLA 2003). ACM, New York, 255--268. (SIGPLAN Notices 38, 11). (For a revision, see Barabash et al. {2005}.) Google ScholarDigital Library
Bartlett, J. F. 1988. Compacting garbage collection with ambiguous roots. Tech. rep. 88/2, Western Research Lab., Digital Equipment Corp., Palo Alto.Google Scholar
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}.)Google Scholar
Bastani, F. B., Chen, I.-R., and Hilal, W. 1991. A model for the stability analysis of maintenance stragies for linear list. Comput. J. 34, 1, 80--87. Oxford University Press, Oxford, UK. Google ScholarDigital Library
Bastani, F. B., Hilal, W., and Chen, I.-R. 1986. Performance analysis of concurrent maintenance policies for servers in a distributed environment. In Proceedings of the Fall Joint Computer Conference. ACM and IEEE-CS, New York, 611--619. Google ScholarDigital Library
Bastani, F. B., Iyengar, S. S., and Yen, I.-L. 1988. Concurrent maintenance of data structures in a distributed environment. Comput. J. 31, 2, 165--174. Oxford University Press, Oxford, UK. Google ScholarDigital Library
Batory, D. S. 1982. Optimal file designs and reorganization points. ACM Trans. Datab. Syst. 7, 1, 60--81. Google ScholarDigital Library
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.Google Scholar
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}.)Google ScholarCross Ref
Bayer, R. and McCreight, E. 1972. Organization and maintenance of large ordered indexes. Acta Inf. 1, 3, 173--189.Google ScholarDigital Library
Bellahsene, Z. 1996. View mechanism for schema evolution in object-oriented DBMS. In Advances In Databases, R. Morrison and J. Kennedy, Eds. Lecture Notes in Computer Science, vol. 1094. Springer-Verlag, New York, 18--35. (Proceedings 14th British National Conference on Databases, BNCOD 14.) Google ScholarDigital Library
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.Google ScholarDigital Library
Bernstein, P. A. and Goodman, N. 1981. Concurrency control in distributed database systems. ACM Comput. Surv. 13, 2, 185--221. Google ScholarDigital Library
Bertino, E. 1992. A view mechanism for object-oriented databases. In Advances in Database Technology -- EDBT '92, A. Pirotte, C. Delobel, and G. Gottlob, Eds. Lecture Notes in Computer Science, vol. 580. Springer-Verlag, New York, 136--151. (Proceedings 3rd International Conference on Extending Database Technology.) Google ScholarDigital Library
Birrell, A. D. and Needham, R. M. 1978. An asynchronous garbage collector for the CAP filing system. Oper. Syst. Rev. 12, 2, 31--33. (ACM SIGOPS.) Google ScholarDigital Library
Blackburn, S. M., Cheng, P., and McKinley, K. S. 2004. Myths and realities: The performance impact of garbage collection. In Proceedings of the International Conference on Measurement and Modeling of Computer Systems (SIGMETRICS 2004). ACM, New York, 25--36. (Perform. Evalu. Rev. 32, 1, SIGMETRICS). Google ScholarDigital Library
Blackburn, S. M. and McKinley, K. S. 2003. Ulterior reference counting: Fast garbage collection without a long wait. In Proceedings of the 2003 ACM SIGPLAN Conference on Object-Oriented Programming, Systems, Languages, and Applications (OOPSLA 2003). ACM, New York, 344--358. (SIGPLAN Notices 38, 11). Google ScholarDigital Library
Blackwell, T., Harris, J., and Seltzer, M. 1995. Heuristic cleaning algorithms in log-structured file systems. In Proceedings of the 1995 USENIX Technical Conference USENIX Association, Berkeley, 277--288. Google ScholarDigital Library
BMC Software. 1997. REORG PLUS for DB2: General Information, Version 5.1. BMC Software.Google Scholar
BMC Software. 1998. CONCURRENT REORG and the Extended Performance Utilities: General Information, Version 1.3. BMC Software.Google Scholar
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.Google Scholar
Bracht, C. J., Malkemus, T. R., and Versteeg, A. 1991. Table reorganization identification. IBM Tech. Disclosure Bull. 34, 1, 163--165.Google Scholar
Bratsberg, S. E. 1992. Unified class evolution by object-oriented views. In Proceedings of the 11th International Conference on the Entity-Relationship Approach -- ER '92, G. Pernul and A. M. Tjoa, Eds. Lecture Notes in Computer Science, vol. 645. Springer-Verlag, New York, 423--439. (For more details, see Bratsberg {1993}.) Google ScholarDigital Library
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.Google Scholar
Bratsberg, S. E. and Humborstad, R. 2001. Online scaling in a highly available database. In Proceedings of the 27th International Conference on Very Large Data Bases. Morgan Kaufmann, San Francisco, 451--460. Google ScholarDigital Library
Bratsberg, S. E. Hvasshovd, S.-O., and Torbj&#248;rnsen, &#216;. 1997. Parallel solutions in ClustRa. Data Engin. 20, 2, 13--20.Google Scholar
Bratsberg, S. E. and Torbj&#248;rnsen, &#216;. 2000. Tutorial: Designing an ultra highly available DBMS. In Proceedings of the 2000 ACM SIGMOD International Conference on Management of Data. (SIGMOD Record 29, 2). Google ScholarDigital Library
Breitbart, Y., Vingralek, R., and Weikum, G. 1996. Load control in scalable distributed file structures. Distrib. Paral. Datab. 4, 4, 319--354. Google ScholarDigital Library
Brown, K. P., Carey, M. J., and Livny, M. 1993. Managing memory to meet multi-class workload response time goals. In Proceedings of the 19th International Conference on Very Large Data Bases. Morgan-Kaufmann, San Francisco, 328--341. Google ScholarDigital Library
Brown, K. P., Carey, M. J., and Livny, M. 1996. Goal-oriented buffer management revisited. In Proceedings of the 1996 ACM SIGMOD International Conference on Management of Data. ACM, New York, 353--364. (SIGMOD Record 25, 2). Google ScholarDigital Library
Brownbridge, D. R. 1985. Cyclic reference counting for combinator machines. In Functional Programming Languages and Computer Architecture, J.-P. Jouannaud, Ed. Lecture Notes in Computer Science, vol. 201. Springer-Verlag, New York, 273--288. (Proceedings IFIP Conference). Google ScholarDigital Library
Butler, M. H. 1986. Storage reclamation for object oriented database systems: A summary of the expected costs. In Proceedings of the 1986 International Workshop on Object-Oriented Database Systems. IEEE Computer Society Press, Los Alamitos, 210--211. (For more details, see Butler {1987}.) Google ScholarDigital Library
Butler, M. H. 1987. Storage reclamation in object oriented database systems. In Proceedings of the ACM SIGMOD 1987 Annual Conference. ACM, New York, 410--425. (SIGMOD Record 16, 3.) Google ScholarDigital Library
Chamberlin, D. D., Gray, J. N., and Traiger, I. L. 1975. Views, authorization, and locking in a relational data base system. In Proceedings of the National Computer Conference. vol. 44. AFIPS Press, Reston, 425--430. Google ScholarDigital Library
Chamberlin, D. D. and Schmuck, F. B. 1992a. Dynamic data distribution (D³) in a shared-nothing multiprocessor data store. In Proceedings of the 18th International Conference on Very Large Data Bases. Morgan-Kaufmann, San Francisco, 163--174. (For more details, see Chamberlin and Schmuck {1992b}.) Google ScholarDigital Library
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.Google Scholar
Chang, E. E. and Katz, R. H. 1989. Exploiting inheritance and structure semantics for effective clustering and buffering in an object-oriented DBMS. In Proceedings of the 1989 ACM SIGMOD International Conference on Management of Data. ACM, New York, 348--357. (SIGMOD Record 18, 2). Google ScholarDigital Library
Chee, C.-L., Lu, H., Tang, H., and Ramamoorthy, C. V. 1998. Adaptive prefetching and storage reorganization in a log-structured storage system. IEEE Trans. Knowl. Data Engin. 10, 5, 824--838. Google ScholarDigital Library
Chen, I.-R. 1995. A degradable B^link-tree with periodic data reorganization. Comput. J. 38, 3, 245--252.Google ScholarCross Ref
Chen, I.-R. and Banawan, S. A. 1993. Modeling and analysis of concurrent maintenance policies for data structures using pointers. IEEE Trans. Soft. Engin. 19, 9, 902--911. Google ScholarDigital Library
Chen, I.-R. and Banawan, S. A. 1999. Performance and stability analysis of multi-level data structures with deferred reorganization. IEEE Trans. Soft. Engin. 25, 5, 690--700. Google ScholarDigital Library
Chen, I.-R. and Hassan, S. 1995. Performance analysis of a periodic data reorganization algorithm for concurrent B^link-trees in database systems. In Proceedings of the 1995 ACM Symposium on Applied Computing. ACM, New York, 40--45. Google ScholarDigital Library
Chen, P. M., Lee, E. K., Gibson, G. A., Katz, R. H., and Patterson, D. A. 1994. RAID: High-performance, reliable secondary storage. ACM Comput. Surv. 26, 2, 145--185. Google ScholarDigital Library
Cheney, C. J. 1970. A nonrecursive list compacting algorithm. Comm. ACM 13, 11, 677--678. Google ScholarDigital Library
Cheng, J. R. and Hurson, A. R. 1991. Effective clustering of complex objects in object-oriented databases. In Proceedings of the 1991 ACM SIGMOD International Conference on Management of Data. ACM, New York, 22--31. (SIGMOD Record 20, 2). Google ScholarDigital Library
Chiang, M.-L. and Huang, J.-S. 2007. Improving the performance of log-structured file systems with adaptive block rearrangement. In Proceedings of the 2007 ACM Symposium on Applied Computing (SAC). 1136--1140. Google ScholarDigital Library
Clamen, S. M. 1994. Schema evolution and integration. Distrib. Paral. Datab. 2, 1, 101--126. Kluwer Academic Publishers, Hingham. Google ScholarDigital Library
Cohen, J. 1981. Garbage collection of linked data structures. ACM Comput. Surv. 13, 3 (Sept.), 341--367. Google ScholarDigital Library
Collins, G. E. 1960. A method for overlapping and erasure of lists. Comm. ACM 3, 12, 655--657. Google ScholarDigital Library
Comer, D. 1979. The ubiquitous B-tree. ACM Comput. Surv. 11, 2, 121--137. Google ScholarDigital Library
Cook, J. E., Klauser, A. W., Wolf, A. L., and Zorn, B. G. 1996. Semi-automatic, self-adaptive control of garbage collection rates in object databases. In Proceedings of the 1996 ACM SIGMOD International Conference on Management of Data. ACM, New York, 377--388. (SIGMOD Record 25, 2). Google ScholarDigital Library
Cook, J. E., Wolf, A. L., and Zorn, B. G. 1994. Partition selection policies in object database garbage collection. In Proceedings of the 1994 ACM SIGMOD International Conference on Management of Data. ACM, New York, 371--382. (SIGMOD Record 23, 2). (For a revision with more details and policies, see Cook et al. {1998}.) Google ScholarDigital Library
Cook, J. E., Wolf, A. L., and Zorn, B. G. 1998. A highly effective partition selection policy for object database garbage collection. IEEE Trans. Knowl. Data Engin. 10, 1, 153--172. Google ScholarDigital Library
Copeland, G., Alexander, W., Boughter, E., and Keller, T. 1988. Data placement in Bubba. In Proceedings of the SIGMOD International Conference on Management of Data. ACM, New York, 99--108. (SIGMOD Record 17, 3, ACM). Google ScholarDigital Library
Copeland, G., Franklin, M., and Weikum, G. 1990. Uniform object management. In Advances in Database Technology -- EDBT '90, F. Bancilhon, C. Thanos, and D. Tsichritzis, Eds. Lecture Notes in Computer Science, vol. 416. Springer-Verlag, New York, 253--268. (Proceedings of the International Conference on Extending Database Technology.) Google ScholarDigital Library
Crus, R. A. 1984. Data recovery in IBM Database 2. IBM Syst. J. 23, 2, 178--188.Google ScholarDigital Library
Detlefs, D. L. 1990. Concurrent, atomic garbage collection. Ph.D. dissertation, Department of Computer Science, Carnegie Mellon University, Pittsburgh. (Also Tech. rep. CMU-CS-90-177). Google ScholarDigital Library
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.Google ScholarCross Ref
Detlefs, D. L., Flood, C., Heller, S., and Printezis, T. 2004. Garbage-first garbage collection. In Proceedings of the 4th International Symposium on Memory Management (ISMM 2004). ACM, 37--48. Google ScholarDigital Library
Deutsch, L. P. and Bobrow, D. G. 1976. An efficient, incremental, automatic garbage collector. Comm. ACM 19, 9, 522--526. Google ScholarDigital Library
DeWitt, D. J. and Gray, J. 1992. Parallel database systems: The future of high-performance database systems. Comm. ACM 35, 6, 85--98. Google ScholarDigital Library
Dijkstra, E. W., Lamport, L., Martin, A. J., Scholten, C. S., and Steffens, E. F. M. 1978. On-the-fly garbage collection: An exercise in cooperation. Comm. ACM 21, 11, 966--975. Google ScholarDigital Library
Domani, T., Kolodner, E. K., Lewis, E., Salant, E. E., Barabash, K., Lahan, I., Levanoni, Y., Petrank, E., and Yanover, I. 2000a. Implementing an on-the-fly garbage collector for Java. In Proceedings of the ISMM 2000, International Symposium on Memory Management. ACM, New York, 155--166. (SIGPLAN Notices 36, 1, 2001). Google ScholarDigital Library
Domani, T., Kolodner, E. K., and Petrank, E. 2000b. A generational on-the-fly garbage collector for Java. In Proceedings of the 2000 ACM SIGPLAN Conference on Programming Language Design and Implementation (PLDI). ACM, New York, 274--284. (SIGPLAN Notices 35, 5). Google ScholarDigital Library
Eggert, L. and Touch, J. D. 2005. Ideltime scheduling with preemption intervals. In Proceedings of the 20th ACM Symposium on Operating Systems Principles. ACM, New York, 249--262. (Operat. Syst. Rev. 39, 5, SIGOPS). Google ScholarDigital Library
Englert, S. 1994. NonStop SQL: Scalability and availability for decision support. In Proceedings of the 1994 ACM SIGMOD International Conference on Management of Data. 491. (SIGMOD Record 23, 2). Google ScholarDigital Library
Fang, M. T., Lee, R. C. T., and Chang, C. C. 1986. The idea of de-clustering and its applications. In Proceedings of the 12th International Conference on Very Large Data Bases. Morgan-Kaufmann, San Francisco, 181--188. Google ScholarDigital Library
Feelifl, H. and Kitsuregawa, M. 2001. RING: A strategy for minimizing the cost of online data placement reorganization for Btree indexed database over shared-nothing parallel machines. In Proceedings of the 7th International Conference on Database Systems for Advanced Applications. IEEE Computer Society Press, Los Alamitos, 190--199. Google ScholarDigital Library
Feelifl, H., Kitsuregawa, M., and Ooi, B.-C. 2000. A fast convergence technique for online heat-balancing of Btree indexed database over shared-nothing parallel systems. In Proceedings of the 11th International Conference on Database and Expert Systems Applications, M. T. Ibrahim, J. K&#252;ng, and N. Revell, Eds. Lecture Notes in Computer Science, vol. 1873. Springer-Verlag, New York, 846--858. Google ScholarDigital Library
Ferrandina, F., Meyer, T., and Zicari, R. 1994. Correctness of lazy database updates for object database systems. In Proceedings of the 6th International Workshop on Persistent Object Systems, M. P. Atkinson, D. Maier, and V. Benzaken, Eds. Springer-Verlag, New York, 284--301. (For a revision, see Ferrandina et al. {1995}.) Google ScholarDigital Library
Ferrandina, F., Meyer, T., Zicari, R., Ferran, G., and Madec, J. 1995. Schema and database evolution in the O₂ object database System. In Proceedings of the 21st International Conference on Very Large Data Bases. Morgan-Kaufmann, San Francisco, 170--181. Google ScholarDigital Library
Ferreira, P. and Shapiro, M. 1994a. Garbage collection and DSM consistency. In Proceedings of the 1st USENIX Symposium on Operating Systems Design and Implementation (OSDI). USENIX Association, Berkeley, 229--241. (Also Operat. Syst. Rev., ACM SIGOPS.) Google ScholarDigital Library
Ferreira, P. and Shapiro, M. 1994b. Garbage collection of persistent objects in distributed shared memory. In Proceedings of the 6th International Workshop on Persistent Object Systems, M. P. Atkinson, D. Maier, and V. Benzaken, Eds. Springer-Verlag, New York, 184--199. Google ScholarDigital Library
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.Google Scholar
Ford, D. A. and Myllymaki, J. 1996. A log-structured organization for tertiary storage. In Proceedings of the 12th International Conference on Data Engineering. IEEE Computer Society Press, Los Alamitos, 20--27. Google ScholarDigital Library
Franaszek, P. A. and Considine, J. P. 1979. Reduction of storage fragmentation on direct access devices. IBM J. Res. Devel. 23, 2, 140--148.Google ScholarDigital Library
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.Google Scholar
Franklin, M., Copeland, G., and Weikum, G. 1989. What's different about garbage collection for persistent programming languages&quest; Tech. rep. ACA-ST-062-89, MCC, Austin.Google Scholar
Friske, C. A. 2004a. DB2 managing large partitioned tables in Version 8. Proc. SHARE 102. SHARE, Chicago.Google Scholar
Friske, C. A. 2004b. DB2 online schema changes -- what's new in DB2 Version 8. Proc. SHARE 102. SHARE, Chicago.Google Scholar
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.Google Scholar
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.Google Scholar
Friske, C. A. and Ruddy, J. A. 1998. Online reorganization. DB2 Mag. 3, 3. (Online Ed. http://www.db2mag.com.) CMP Media.Google Scholar
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.Google Scholar
Galante, R. d. M., dos Santos, C. S., Edelweiss, N., and Moreira, A. F. 2005. Temporal and versioning model for schema evolution in object-oriented databases. Data Knowl. Engin. 53, 2, 99--128. North-Holland, Amsterdam, Neth. Google ScholarDigital Library
Ganesan, P., Bawa, M., and Garcia-Molina, H. 2004. Online balancing of range-partitioned data with applications to peer-to-peer systems. In Proceedings of the 30th International Conference on Very Large Data Bases. Morgan-Kaufmann, San Francisco, 444--455. Google ScholarDigital Library
Garnett, N. H. and Needham, R. M. 1980. An asynchronous garbage collector for the Cambridge File Server. Operat. Syst. Rev. 14, 4, 36--40. Google ScholarDigital Library
Garthwaite, A. T. 2008. Concurrent incremental garbage collector with a card table summarizing modified reference locations. U.S. patent 7,412,580.Google Scholar
Gerritsen, R. 1994. Private communication.Google Scholar
Gerritsen, R. and Morgan, H. L. 1976. Dynamic restructuring of databases with generation data structures. In Proceedings of the ACM Annual Conference. ACM, New York, 281--286. Google ScholarDigital Library
Ghandeharizadeh, S. and DeWitt, D. J. 1990. A multiuser performance analysis of alternative declustering strategies. In Proceedings of the 6th International Conference on Data Engineering. IEEE Computer Society Press, Los Alamitos, 466--475. Google ScholarDigital Library
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&#253;, and T. K. Sellis, Eds. Lecture Notes in Computer Science, vol. 4152. Springer-Verlag, New York, 399--414. Google ScholarDigital Library
Ghandeharizadeh, S. and Kim, D. 1996. Online reorganization of data in scalable continuous media servers. In Proceedings of the 7th International Conference on Database and Expert Systems Applications, R. Wagner and H. Thoma, Eds. Lecture Notes in Computer Science, vol. 1134. Springer-Verlag, New York, 751--768. Google ScholarDigital Library
Golding, R., Bosch, P., Staelin, C., Sullivan, T., and Wilkes, J. 1995. Idleness is not sloth. In Proceedings of the 1995 USENIX Technical Conference. USENIX Assoc., Berkeley, 201--212. Google ScholarDigital Library
Goodman, N. and Shasha, D. 1985. Semantically-based concurrency control for search structures. In Proceedings of the 4th ACM SIGACT-SIGMOD Symposium on Principles of Database Systems. ACM, New York, 8--19. (For a revision, see Shasha and Goodman {1988}.) Google ScholarDigital Library
Goralwalla, I. A., Szafron, D., &#214;zsu, M. T., and Peters, R. J. 1998. A temporal approach to managing schema evolution in object database systems. Data Knowl. Engin. 28, 1, 73--105. North-Holland, Amsterdam, Netherlands. Google ScholarDigital Library
Goyal, B., Haritsa, J. R., Seshadri, S., and Srinivasan, V. 1995. Index concurrency control in firm real-time DBMS. In Proceedings of the 21st International Conference on Very Large Data Bases. Morgan-Kaufmann, San Francisco, 146--157. Google ScholarDigital Library
Graefe, G. 1993. Query evaluation techniques for large databases. ACM Comput. Surv. 25, 2, 73--170. Google ScholarDigital Library
Gray, J. 1978. Notes on data base operating systems. In Operating Systems&#8212;An Advanced Course, R. Bayer, R. M. Graham, and G. Seegm&#252;ller, Eds. Springer-Verlag, New York, 393--481. Google ScholarDigital Library
Gray, J. and Reuter, A. 1993. Transaction Processing: Concepts and Techniques. Morgan-Kaufmann, San Francisco. Google ScholarDigital Library
Guibas, L. J. and Sedgewick, R. 1978. A dichromatic framework for balanced trees. In Proceedings of the 19th Annual Symposium on Foundations of Computer Science. IEEE Computer Society Press, Los Alamitos, 8--21. Google ScholarDigital Library
Gupta, A. and Fuchs, W. K. 1993. Garbage collection in a distributed object-oriented system. IEEE Trans. Knowl. Data Engin. 5, 2, 257--265. Google ScholarDigital Library
Haerder, T. and Reuter, A. 1983. Principles of transaction-oriented database recovery. ACM Comput. Surv. 15, 4, 287--317. Google ScholarDigital Library
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.Google Scholar
Hartman, J. H. and Ousterhout, J. K. 1995. The Zebra striped network file system. ACM Trans. Comput. Syst. 13, 3, 274--310. Google ScholarDigital Library
Helal, A., Yuan, D., and El-Rewini, H. 1997. Dynamic data reallocation for skew management in shared-nothing parallel databases. Distrib. Paral. Datab. 5, 3, 271--288. Google ScholarDigital Library
Heyman, D. P. 1982. Mathematical models of database degradation. ACM Trans. Datab. Syst. 7, 4, 615--631. Google ScholarDigital Library
Ho, F., Jain, R., and Troisi, J. 1994. An overview of NonStop SQL/MP. Tandem Syst. Rev. 10, 3, 6--17. Hewlett-Packard.Google Scholar
Huras, M. A., Hing, N. H., Goss, J. J., and Lindsay, B. G. 2005. Online database table reorganization. U.S. patent 6,950,834.Google Scholar
IBM. 1986. IMS/VS Version 1 Utilities Reference Manual. IBM. SH20-9029-9.Google Scholar
IBM. 1993a. Implementing Concurrent Copy. IBM. GG24-3990-00.Google Scholar
IBM. 1993b. An Introduction to Data Propagator Relational Release 1. IBM. GC26-3398-01.Google Scholar
IBM. 1997. DB2 for OS/390 Version 5 Utility Guide and Reference. IBM. SC26-8967-00.Google Scholar
IBM. 2001. DB2 Universal Database for OS/390 and z/OS Utility Guide and Reference, Version 7. IBM. SC26-9945-00.Google Scholar
IBM. 2005. IMS Administration Guide: Database Manager, Version 9. IBM. SC18-7806-01.Google Scholar
IBM and Integrated Systems Solutions. 1994. Replidata/MVS User's Guide. IBM and Integrated Systems Solutions. BLD-REP-UG-00.Google Scholar
Isip, Jr., A. B. 2007. System and method for reorganizing stored data. U.S. patent 7,225,206.Google Scholar
Itasca Systems. 1993. ITASCA Distributed Object Database Management System: Technical Summary for Release 2.2. Itasca Systems.Google Scholar
Iyer, B. R. and Sockut, G. H. 2002. Methods for in-place online reorganization of a database. U.S. patent 6,411,964.Google Scholar
Iyer, B. R. and Wilhite, D. 1994. Data compression support in databases. In Proceedings of the 20th International Conference on Very Large Data Bases. Morgan-Kaufmann, San Francisco, 695--704. Google ScholarDigital Library
Jambor, M., Hruby, T., Taus, J., Krchak, K., and Holub, V. 2007. Implementation of a Linux log-structured file system with a garbage collector. Operat. Syst. Rev. 41, 1, 24--32. Google ScholarDigital Library
Johnson, T. and Shasha, D. 1990. A framework for the performance analysis of concurrent B-tree algorithms. In Proceedings of the 9th ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems. ACM, New York, 273--287. (For more details, see Johnson and Shasha {1993}.) Google ScholarDigital Library
Johnson, T. and Shasha, D. 1993. The performance of concurrent B-tree algorithms. ACM Trans. Datab. Syst. 18, 1, 51--101. Google ScholarDigital Library
Joisha, P. G. 2007. Overlooking roots: A framework for making nondeferred reference-counting garbage collection fast. In Proceedings of the 6th International Symposium on Memory Management (ISMM 2007). ACM, New York, 141--157. Google ScholarDigital Library
Joisha, P. G. 2008. A principled approach to nondeferred reference-counting garbage collection. In Proceedings of the 4th ACM SIGPLAN/SIGOPS International Conference on Virtual Execution Environments. ACM, New York, 131--140. Google ScholarDigital Library
Jones, R. and Lins, R. 1996. Garbage Collection: Algorithms for Automatic Dynamic Memory Management. Wiley, New York. Google ScholarDigital Library
De Jonge, W., Kaashoek, M. F., and Hsieh, W. C. 1993. The logical disk: A new approach to improving file systems. In Proceedings of the 14th ACM Symposium on Operating Systems Principles. ACM, New York, 15--28. (Operat. Syst. Rev. 27, 5, SIGOPS). Google ScholarDigital Library
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.Google Scholar
Kermany, H. and Petrank, E. 2006. The Compressor: Concurrent, incremental, and parallel compaction. In Proceedings of the 2006 ACM SIGPLAN Conference on Programming Language Design and Implementation (PLDI '06). ACM, New York, 354--363. (SIGPLAN Notices 41, 6). Google ScholarDigital Library
Kero, M., Nordlander, J., and Lindgren, P. 2007. A correct and useful incremental copying garbage collector. In Proceedings of the 6th International Symposium on Memory Management (ISMM 2007). ACM, New York, 129--140. Google ScholarDigital Library
Kessels, J. L. W. 1983. On-the-fly optimization of data structures. Comm. ACM 26, 11, 895--901. Google ScholarDigital Library
Keyes, J. 1992. DBAs face challenge of 24 by 7 availability. Software Mag. 12, 11, 58--63.Google Scholar
Kim, M. Y. 1986. Synchronized disk inter-leaving. IEEE Trans. Comput. C-35, 11, 978--988. Google ScholarDigital Library
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.Google Scholar
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.Google Scholar
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.Google Scholar
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}.)Google Scholar
Kolodner, E. K. 1992. Atomic incremental garbage collection and recovery for a large stable heap. Ph.D. dissertation, Department of Electrical Engineering and Computer Science, Massachusetts Institute of Technology, Cambridge. (Also Tech. rep. MIT/LCS/TR-534, Laboratory for Computer Science.) Google ScholarDigital Library
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.Google Scholar
Kolodner, E. K. and Petrank, E. 2002. On-the-fly garbage collector. U.S. patent 6,490,599.Google Scholar
Kolodner, E. K. and Weihl, W. E. 1993. Atomic incremental garbage collection and recovery for a large stable heap. In Proceedings of the 1993 ACM SIGMOD International Conference on Management of Data. 177--186. (SIGMOD Record 22, 2). For more details, see Kolodner {1992}.) Google ScholarDigital Library
Kung, H. T. and Lehman, P. L. 1980. Concurrent manipulation of binary search trees. ACM Trans. Datab. Syst. 5, 3, 354--382. Google ScholarDigital Library
Kuo, T.-W., Wei, C.-H., and Lam, K.-Y. 1999. Real-time data access control on B-tree index structures. In Proceedings of the 15th International Conference on Data Engineering. IEEE Computer Society Press, Los Alamitos, 458--467. Google ScholarDigital Library
Lakhamraju, M. K., Rastogi, R., Seshadri, S., and Sudarshan, S. 2000. On-line reorganization in object databases. In Proceedings of the 2000 ACM SIGMOD International Conference on Management of Data. ACM, New York, 58--69. (SIGMOD Record 29, 2). (This is similar to Lakhamraju et al. {2002}.) Google ScholarDigital Library
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}.)Google Scholar
Lam, K.-W. and Lee, V. C. S. 2006. On consistent reading of entire databases. IEEE Trans. Knowl. Data Engin. 18, 4, 569--572. Google ScholarDigital Library
Lampson, B. W. 1984. Hints for computer system design. Software 1, 1, 11--28. IEEE-CS. Google ScholarDigital Library
Langley, J. T. and Moore, D. W. 2008. Non-disruptive backup copy in a database online reorganization environment. U.S. patent 7,433,902.Google Scholar
Lee, M.-L., Kitsuregawa, M., Ooi, B. C., Tan, K.-L., and Mondal, A. 2000. Towards self-tuning data placement in parallel database systems. In Proceedings of the 2000 ACM SIGMOD International Conference on Management of Data. ACM, New York, 225--236. May (SIGMOD Record 29, 2). (For more details, see Mondal {2002}.) Google ScholarDigital Library
Litwin, W. 1980. Linear hashing: A new tool for file and table addressing. In Proceedings of the 6th International Conference on Very Large Data Bases. IEEE Computer Society Press, Los Alamitos, 212--223. Google ScholarDigital Library
Liu, C.-T., Chrysanthis, P. K., and Chang, S.-K. 1994a. Database schema evolution through the specification and maintenance of changes on entities and relationships. In Proceedings of the 13th International Conference on the Entity-Relationship Approach, ER '94, P. Loucopoulos, Ed. Lecture Notes in Computer Science, vol. 881. Springer-Verlag, New York, 132--151. Google ScholarDigital Library
Liu, L., Zicari, R., H&#252;rsch, W., and Lieberherr, K. 1994b. Polymorphic reuse mechanisms for object-oriented database specifications. In Proceedings of the 10th International Conference on Data Engineering. IEEE Computer Society Press, Los Alamitos, 180--189. Google ScholarDigital Library
Lohman, G. M. 1977. Optimal data storage and organization in computerized information processing systems subject to failures. Ph.D. dissertation. School of Operations Research and Industrial Engineering, Cornell University, Ithaca. Google ScholarDigital Library
Lohman, G. M. and Muckstadt, J. A. 1977. Optimal policy for batch operations: Backup, checkpointing, reorganization, and updating. ACM Trans. Datab. Syst. 2, 3, 209--222. Google ScholarDigital Library
L&#248;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&#8212;EDBT 2006, Y. E. Ioannidis, M. H. Scholl, J. W. Schmidt, F. Matthes, M. Hatzopoulos, K. B&#246;hm, A. Kemper, T. Grust, and C. B&#246;hm, Eds. Lecture Notes in Computer Science, vol. 3896. Springer-Verlag, New York, 405--422. Google ScholarDigital Library
Lomet, D. B. 2000. High-speed on-line backup when using logical log operations. In Proceedings of the 2000 ACM SIGMOD International Conference on Management of Data. ACM, New York, 34--45. (SIGMOD Record 29, 2). Google ScholarDigital Library
Lomet, D. B. and Salzberg, B. 1992. Access method concurrency with recovery. In Proceedings of the 1992 ACM SIGMOD International Conference on Management of Data. ACM, New York, 351--360. (SIGMOD Record 21, 2). (For more details, see Lomet and Salzberg {1997}.) Google ScholarDigital Library
Lomet, D. B. and Salzberg, B. 1997. Concurrency and recovery for index trees. VLDB J. 6, 3, 224--240. Google ScholarDigital Library
Lumb, C. R., Schindler, J., Ganger, G. R., and Nagle, D. 2000. Towards higher disk head utilization: Extracting free bandwidth from busy disk drives. In Proceedings of the 4th Symposium on Operating Systems Design and Implementation (OSDI 2000). USENIX Association, Berkeley, 87--102. Google ScholarDigital Library
Maheshwari, U. and Liskov, B. 1997. Partitioned garbage collection of a large object store. In Proceedings of the 1997 ACM SIGMOD International Conference on Management of Data. 313--323. (SIGMOD Record 26, 2). Google ScholarDigital Library
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.Google Scholar
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.Google Scholar
Manber, U. 1984. Concurrent maintenance of binary search trees. IEEE Trans. Softw. Engin. SE-10, 6, 777--784.Google ScholarDigital Library
Manber, U. and Ladner, R. E. 1982. Concurrency control in a dynamic search structure. In Proceedings of the ACM Symposium on Principles of Database Systems. ACM, New York, 268--282. (For a revision, see Manber and Ladner {1984}.) Google ScholarDigital Library
Manber, U. and Ladner, R. E. 1984. Concurrency control in a dynamic search structure. ACM Trans. Datab. Syst. 9, 3, 439--455. Google ScholarDigital Library
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.Google Scholar
Martin, J. 1975. Computer Data-Base Organization. Prentice-Hall, Englewood Cliffs, NJ. Google ScholarDigital Library
Martin, Jr., J. L. and Crown, Jr., G. N. 2003a. IMS on-line reorganization utility. U.S. patent 6,606,631.Google Scholar
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.Google Scholar
Maruyama, K. and Smith, S. E. 1976. Optimal reorganization of distributed space disk files. Comm. ACM 19, 11, 634--642. Google ScholarDigital Library
Matthews, J. N., Roselli, D., Costello, A. M., Wang, R. Y., and Anderson, T. E. 1997. Improving the performance of log-structured file systems with adaptive methods. In Proceedings of the 16th ACM Symposium on Operating Systems Principles. ACM, New York, 238--251. (Operat. Syst. Rev. 31, 5, SIGOPS). Google ScholarDigital Library
McAuliffe, M. L., Carey, M. J., and Solomon, M. H. 1998. Vclusters: A flexible, fine-grained object clustering mechanism. In Proceedings of the 1998 ACM SIGPLAN Conference on Object-Oriented Programming, Systems, Languages, and Applications (OOPSLA). ACM, New York, 230--243. (SIGPLAN Notices 33, 10). Google ScholarDigital Library
McCarthy, J. 1960. Recursive functions of symbolic expressions and their computation by machine, Part I. Comm. ACM 3, 4, 184--195. Google ScholarDigital Library
McCreight, A., Shao, Z., Lin, C., and Li, L. 2007. A general framework for certifying garbage collectors and their mutators. In Proceedings of the 2007 ACM SIGPLAN Conference on Programming Language Design and Implementation. ACM, New York, 468--479. (SIGPLAN Notices 42, 6). Google ScholarDigital Library
McIver, Jr., W. J. 1994. An approach to self-adaptive, on-line reclustering of complex object data. Ph.D. dessertation. Department of Computer Science, University of Colorado, Boulder. Google ScholarDigital Library
McIver, Jr., W. J. and King, R. 1994. Self-adaptive, on-line reclustering of complex object data. In Proceedings of the 1994 ACM SIGMOD International Conference on Management of Data. ACM, New York, 407--418. (SIGMOD Record 23, 2). (For more details, see McIver {1994}.) Google ScholarDigital Library
McNutt, B. 1994. Background data movement in a log-structured disk subsystem. IBM J. Resear. Develop. 38, 1, 47--58. Google ScholarDigital Library
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.Google Scholar
Meltzer, H. S. 1976. Structure and redundancy in the conceptual schema in the administration of very large data bases. In Proceedings of the 2nd International Conference on Very Large Data Bases, P. C. Lockemann and E. J. Neuhold, Eds. North-Holland, Amsterdam, The Netherlands, 13--25. Google ScholarDigital Library
Mendelson, H. and Yechiali, U. 1981. Optimal policies for data base reorganization. Oper. Resear. 29, 1, 23--36.Google ScholarCross Ref
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.)Google Scholar
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.)Google Scholar
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.Google Scholar
Mizoguchi, M. and Nishiyama, K. 1994. Database management system. Japan patent 06-67944.Google Scholar
Mogi, K. and Kitsuregawa, M. 1994. Dynamic parity stripe reorganizations for RAID5 disk arrays. In Proceedings of the 3rd International Conference on Parallel and Distributed Information Systems (PDIS 94). IEEE Computer Society Press, Los Alamitos, 17--26. Google ScholarDigital Library
Mogi, K. and Kitsuregawa, M. 1995. Hot block clustering for disk arrays with dynamic striping: Exploitation of accesses locality and its performance analysis. In Proceedings of the 21st International Conference on Very Large Data Bases. Morgan-Kaufmann, San Francisco, 90--99. Google ScholarDigital Library
Mohan, C. 1993a. IBM's relational DBMS products: Features and technologies. In Proceedings of the 1993 ACM SIGMOD International Conference on Management of Data. ACM, New York, 445--448. (SIGMOD Record 22, 2). Google ScholarDigital Library
Mohan, C. 1993b. A survey of DBMS research issues in supporting very large tables. In Proceedings of the 4th International Conference on Foundations of Data Organization and Algorithms, D. B. Lomet, Ed. Lecture Notes in Computer Science, vol. 730. Springer-Verlag, New York, 279--300. Google ScholarDigital Library
Mohan, C., Haderle, D., Lindsay, B., Pirahesh, H., and Schwarz, P. 1992. ARIES: A transaction recovery method supporting fine-granularity locking and partial rollbacks using write-ahead logging. ACM Trans. Datab. Syst. 17, 1, 94--162. Google ScholarDigital Library
Mohan, C. and Narang, I. 1992. Algorithms for creating indexes for very large tables without quiescing updates. In Proceedings of the 1992 ACM SIGMOD International Conference on Management of Data. ACM, New York, 361--370. (SIGMOD Record 21, 2). Google ScholarDigital Library
Mohan, C. and Narang, I. 1993. An efficient and flexible method for archiving a data base. In Proceedings of the 1993 ACM SIGMOD International Conference on Management of Data. ACM, New York, 139--146. (SIGMOD Record 22, 2). Google ScholarDigital Library
Moitra, A., Iyengar, S. S., Bastani, F. B., and Yen, I.-L. 1988. Multi-level data structures: Models and performance. IEEE Trans. Softw. Engin. 14, 6, 858--867. Google ScholarDigital Library
Mondal, A. 2002. Query-centric online reorganization of indexed data in shared-nothing architectures. Ph.D. dissertation, School of Computing, National University of Singapore.Google Scholar
Mondal, A., Kitsuregawa, M., Ooi, B. C., and Tan, K.-L. 2001. R-tree-based data migration and self-tuning strategies in shared-nothing spatial databases. In Proceedings of the 9th ACM International Symposium on Advances in Geographic Information Systems. ACM, New York, 28--33. (For more details, see Mondal {2002}.) Google ScholarDigital Library
Morsi, M. M. A. 1992. Extensible object-oriented databases with dynamic schemas. Ph.D. dissertation, College of Computing, Georgia Institute of Technology, Atlanta. Google ScholarDigital Library
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}.)Google Scholar
Morsi, M. M. A., Navathe, S. B., and Kim, H.-J. 1992. An extensible object-oriented database testbed. In Proceedings of the 8th International Conference on Data Engineering. IEEE Computer Society Press, Los Alamitos, 150--157. (For more details, see Morsi {1992}.) Google ScholarDigital Library
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.)Google Scholar
Munro, D. S., Brown, A. L., Morrison, R., and Moss, J. E. B. 1999. Incremental garbage collection of a persistent object store using PMOS. In Advances in Persistent Object Systems, Proceedings of the 8th International Workshop on Persistent Object Systems (POS8) and Proceedings of the 3rd International Workshop on Persistence and Java (PJW3), 1998, R. Morrison, M. J. Jordan, and M. P. Atkinson, Eds. Morgan-Kaufmann, San Francisco, 78--91. Google ScholarDigital Library
Nettles, S. and O'Toole, J. 1993. Real-time replication garbage collection. In Proceedings of the ACM SIGPLAN '93 Conference on Programming Language Design and Implementation. ACM, New York, 217--226. (SIGPLAN Notices 28, 6). Google ScholarDigital Library
Nilsen, K. D. and Schmidt, W. J. 1992. Cost-effective object space management for hardware-assisted real-time garbage collection. ACM Lett. Prog. Lang. Syst. 1, 4, 338--354. Google ScholarDigital Library
Nurmi, O., Soisalon-Soininen, E., and Wood, D. 1987. Concurrency control in database structures with relaxed balance. In Proceedings of the 6th ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems. ACM, New York, 170--176. Google ScholarDigital Library
Odberg, E. 1994. A global perspective of schema modification management for object-oriented data bases. In Proceedings of the 6th International Workshop on Persistent Object Systems, M. P. Atkinson, D. Maier, and V. Benzaken, Eds. Springer-Verlag, New York, 479--502. Google ScholarDigital Library
Olson, N. E. 1993. Partial indexing in POSTGRES. M.S. dissertation. Department of Electrical Engineering and Computer Science, University of California, Berkeley.Google Scholar
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.Google Scholar
Omiecinski, E. 1985b. Incremental file reorganization schemes. In Proceedings of the 11th International Conference on Very Large Data Bases. Morgan-Kaufmann, San Francisco, 346--357. Google ScholarDigital Library
Omiecinski, E. 1988. Concurrent storage structure conversion: from B+ tree to linear hash file. In Proceedings of the 4th International Conference on Data Engineering. IEEE Computer Society Press, Los Alamitos, 589--596. (For an extended revision, see Omiecinski {1989}.) Google ScholarDigital Library
Omiecinski, E. 1989. Concurrent file conversion between B⁺-tree and linear hash files. Inf. Syst. 14, 5, 371--383. Google ScholarDigital Library
Omiecinski, E. 1996. Concurrent file reorganization: Clustering, conversion and maintenance. Data Engin. 19, 2, 25--32. IEEE-CS TC DE.Google Scholar
Omiecinski, E., Lee, L., and Scheuermann, P. 1992. Concurrent file reorganization for record clustering: A performance study. In Proceedings of the 8th International Conference on Data Engineering. IEEE Computer Society Press, Los Alamitos, 265--272. (For more details, see Omiecinski et al. {1994}.) Google ScholarDigital Library
Omiecinski, E., Lee, L., and Scheuermann, P. 1994. Performance analysis of a concurrent file reorganization algorithm for record clustering. IEEE Trans. Knowl. Data Engin. 6, 2, 248--257. Google ScholarDigital Library
Omiecinski, E. and Scheuermann, P. 1984. A global approach to record clustering and file reorganization. In Proceedings of the 3rd Joint BCS and ACM Symposium on Research and Development in Information Retrieval, C. J. van Rijsbergen, Ed. Cambridge Univ. Press, Cambridge, 201--219. (For later work, see Omiecinski {1985b}.) Google ScholarDigital Library
Oracle. 2005. Oracle Database 10g Release 2 online data reorganization & redefinition. Oracle White Paper.Google Scholar
Osborn, S. L. 1989. The role of polymorphism in schema evolution in an object-oriented database. IEEE Trans. Knowl. Data Engin. 1, 3, 310--317. Google ScholarDigital Library
Ossia, Y., Ben-Yitzhak, O., Goft, I., Kolodner, E. K., Leikehman, V., and Owshanko, A. 2002. A parallel, incremental and concurrent GC for servers. In Proceedings of the 2002 ACM SIGPLAN Conference on Programming Language Design and Implementation (PLDI). ACM, New York, 129--140. (SIGPLAN Notices 37, 5). (For a revision, see Barabash et al. {2005}.) Google ScholarDigital Library
O'Toole, J., Nettles, S., and Gifford, D. 1993. Concurrent compacting garbage collection of a persistent heap. In Proceedings of the 14th ACM Symposium on Operating Systems Principles. ACM, New York, 161--174. (Operat. Syst. Rev. 27, 5, SIGOPS.) Google ScholarDigital Library
Ousterhout, J. and Douglis, F. 1989. Beating the I/O bottleneck: A case for log-structured file systems. Operat. Syst. Rev. 23, 1, 11--28. (For a revised, more detailed description, see Rosenblum and Ousterhout {1992}.) Google ScholarDigital Library
Park, J. S., Bartoszynski, R., De, P., and Pirkul, H. 1990. Optimal reorganization policies for stationary and evolutionary databases. Manag. Sci. 36, 5, 613--631. Google ScholarDigital Library
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}.)Google Scholar
Park, J. S. and Sridhar, V. 1997. Probabilistic model and optimal reorganization of B+-tree with physical clustering. IEEE Trans. Knowl. Data Engin. 9, 5, 826--832. Google ScholarDigital Library
Paz, H., Bacon, D. F., Kolodner, E. K., Petrank, E., and Rajan, V. T. 2007. An efficient on-the-fly cycle collection. ACM Trans. Prog. Lang. Syst. 29, 4. Article 20. Google ScholarDigital Library
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}.) Google ScholarDigital Library
Pereira, H. M. 2000. Method and apparatus for reorganizing an active DBMS table. U.S. patent 6,122, 640.Google Scholar
Peters, R. J. and &#214;zsu, M. T. 1995. Axiomatization of dynamic schema evolution in objectbases. In Proceedings of the 11th International Conference on Data Engineering. IEEE Computer Society Press, Los Alamitos, 156--164. (For a revision with more details, see Peters and &#214;zsu {1997}.) Google ScholarDigital Library
Peters, R. J. and &#214;zsu, M. T. 1997. An axiomatic model of dynamic schema evolution in objectbase systems. ACM Trans. Datab. Syst. 22, 1, 75--114. Google ScholarDigital Library
Pizlo, F., Frampton, D., Petrank, E., and Steensgaard, B. 2007. Stopless: a real-time garbage collector for multiprocessors. In Proceedings of the 6th International Symposium on Memory Management (ISMM 2007). ACM, New York, 159--172. Google ScholarDigital Library
Pizlo, F., Petrank, E., and Steensgaard, B. 2008. A study of concurrent real-time garbage collectors. In Proceedings of the 2008 ACM SIGPLAN Conference on Programming Language Design and Implementation. ACM, New York, 33--44. (SIGPLAN Notices 43, 6). Google ScholarDigital Library
Plow, G. M., Pourmirzaie, F. E., and Shiomi, T. 2008. Method for reorganizing a set of database partitions. U.S. patent 7,454,449.Google Scholar
Pollari-Malmi, K., Soisalon-Soininen, E., and Yl&#246;nen, T. 1996. Concurrency control in B-trees with batch updates. IEEE Trans. Knowl. Data Engin. 8, 6, 975--984. Google ScholarDigital Library
Pong, M. 1990. An overview of NonStop SQL Release 2. Tandem Syst. Rev. 6, 2, 4--11.Google Scholar
Ponnekanti, N. and Kodavalla, H. 2000. Online index rebuild. In Proceedings of the 2000 ACM SIGMOD International Conference on Management of Data. ACM, New York, 529--538. May (SIGMOD Record 29, 2). Google ScholarDigital Library
Printezis, T. and Detlefs, D. L. 2000. A generational mostly-concurrent garbage collector. In Proceedings of the International Symposium on Memory Management (ISMM 2000). ACM, New York, 143--154. (SIGPLAN Notices 36, 1, ACM 2001). Google ScholarDigital Library
Pu, C. 1985. On-the-fly, incremental, consistent reading of entire databases. In Proceedings of the 11th International Conference on Very Large Data Bases. Morgan-Kaufmann, San Francisco, 369--375. (For a revision, see Pu {1986}.) Google ScholarDigital Library
Pu, C. 1986. On-the-fly, incremental, consistent reading of entire databases. Algorithmica 1, 3, 271--287.Google ScholarCross Ref
Pu, C., Hong, C. H., and Wha, J. M. 1988. Performance evaluation of global reading of entire databases. In Proceedings of the International Symposium on Databases in Parallel and Distributed Systems. IEEE Computer Society Press, Los Alamitos, 167--176. Google ScholarDigital Library
Puffitsch, W. and Schoeberl, M. 2008. Non-blocking root scanning for real-time garbage collection. In Proceedings of the 6th International Workshop on Java Technologies for Real-Time and Embedded Systems. ACM, 68--76. Google ScholarDigital Library
Ra, Y.-G. and Rundensteiner, E. A. 1995. A transparent object-oriented schema change approach using view evolution. In Proceedings of the 11th International Conference on Data Engineering. IEEE Computer Society Press, Los Alamitos, 165--172. (For a revision with more details, see Ra and Rundensteiner {1997}.) Google ScholarDigital Library
Ra, Y.-G. and Rundensteiner, E. A. 1997. A transparent schema-evolution system based on object-oriented view technology. IEEE Trans. Knowl. Data Engin. 9, 4, 600--624. Google ScholarDigital Library
Radosevich, L. 1993. Hotel cans mainframes. Computerworld 27, 8, 1 and 16.Google Scholar
Raghuram, S., Ranganath, S., Olson, S., and Nandi, S. 2000. Taming the down-time: High availability in Sybase ASE 12. In Proceedings of the 16th International Conference on Data Engineering. IEEE Computer Society Press, Los Alamitos, 111--120. (For more details of index reorganization, see Ponnekanti and Kodavalla {2000}.) Google ScholarDigital Library
Rahm, E. and Bernstein, P. A. 2006. An online bibliography on schema evolution. SIGMOD Record 35, 4, 30--31. (For the current bibliography, see http://se-pubs.dbs.uni-leipzig.de.) Google ScholarDigital Library
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.Google Scholar
Ram&#237;rez, R. J., Tompa, F. W., and Munro, J. I. 1982. Optimum reorganization points for arbitrary database costs. Acta Informatica 18, 1, 17--30.Google ScholarDigital Library
Rengarajan, T. K., Dimino, L., and Chung, D. 1996. Sybase System 11 online capabilities. Data Engin. 19, 2, 19--24.Google Scholar
Robinson, J. T. and Franaszek, P. A. 1994. Analysis of reorganization overhead in log-structured file systems. In Proceedings of the 10th International Conference on Data Engineering. IEEE Computer Society Press, Los Alamitos, 102--110. Google ScholarDigital Library
Roddick, J. F. 1991. Dynamically changing schemas within database models. Austral. Comput. J. 23, 3, 105--109. Google ScholarDigital Library
Roddick, J. F. 1992. Schema evolution in database systems&#8212;An annotated bibliography. SIGMOD Record 21, 4, 35--40. (For a revision, see Roddick {1994}.) Google ScholarDigital Library
Roddick, J. F. 1994. Schema evolution in database systems&#8212;An updated bibliography. Tech. rep. CIS-94-012, School of Computer and Information Science, University of South Australia, The Levels, S. Australia.Google Scholar
Roddick, J. F. 1995. A survey of schema versioning issues for database systems. Inf. Softw. Tech. 37, 7, 383--393.Google ScholarCross Ref
Ronstr&#246;m, M. 2000. On-line schema update for a telecom database. In Proceedings of the 16th International Conference on Data Engineering. IEEE Computer Society Press, Los Alamitos, 329--338. Google ScholarDigital Library
Rosenblum, M. and Ousterhout, J. K. 1992. The design and implementation of a log-structured file system. ACM Trans. Computer Syst. 10, 1, 26--52. Google ScholarDigital Library
Rosenkrantz, D. J. 1978. Dynamic database dumping. In Proceedings of the ACM SIGMOD International Conference on Management of Data. ACM, New York, 3--8. Google ScholarDigital Library
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.Google Scholar
Roy, P., Seshadri, S., Silberschatz, A., Sudarshan, S., and Ashwin, S. 1998. Garbage collection in object-oriented databases using transactional cyclic reference counting. VLDB J. 7, 3, 179--193. Google ScholarDigital Library
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.Google Scholar
Sagiv, Y. 1985. Concurrent operations on B-trees with overtaking. In Proceedings of the 4th ACM SIGACT-SIGMOD Symposium on Principles of Database Systems. ACM, New York, 28--37. (For a revision, see Sagiv {1986}.) Google ScholarDigital Library
Sagiv, Y. 1986. Concurrent operations on B&ast;-trees with overtaking. J. Comput. Syst. Sci. 33, 2, 275--296. Google ScholarDigital Library
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.Google Scholar
Salem, K. and Garcia-Molina, H. 1986. Disk striping. In Proceedings of the International Conference on Data Engineering. IEEE Computer Society Press, Los Alamitos, 336--342. Google ScholarDigital Library
Salzberg, B. 1985. Restructuring the Lehman-Yao tree. Tech. rep. BS-85-21, College of Computer Science, Northeastern University, Boston.Google Scholar
Salzberg, B. and Dimock, A. 1992. Principles of transaction-based on-line reorganization. In Proceedings of the 18th International Conference on Very Large Data Bases. Morgan-Kaufmann, San Francisco, 511--520. Google ScholarDigital Library
Scheuermann, P., Park, Y. C., and Omiecinski, E. 1989. A heuristic file reorganization algorithm based on record clustering. BIT 29, 3, 428--447. Google ScholarDigital Library
Scheuermann, P., Weikum, G., and Zabback, P. 1993. Adaptive load balancing in disk arrays. In Proceedings of the 4th International Conference on Foundations of Data Organization and Algorithms, D. B. Lomet, Ed. Lecture Notes in Computer Science, vol. 730. Springer-Verlag, New York, 345--360. Foundations of Data Organization and Algorithms. Google ScholarDigital Library
Scheuermann, P., Weikum, G., and Zabback, P. 1994. &#8220;Disk cooling&#8221; in parallel disk systems. Bull. Tech. Committee Data Engin. 17, 3, 29--40.Google Scholar
Scheuermann, P., Weikum, G., and Zabback, P. 1998. Data partitioning and load balancing in parallel disk systems. VLDB J. 7, 1, 48--66. Google ScholarDigital Library
Schmidt, W. J. and Nilsen, K. D. 1994. Performance of a hardware-assisted real-time garbage collector. In Proceedings of the 6th International Conference on Architectural Support for Programming Languages and Operating Systems. ACM, New York, 76--85. (Operat. Syst. Rev. 28, 5, ACM SIGOPS). Google ScholarDigital Library
Schoeberl, M. and Puffitsch, W. 2008. Non-blocking object copy for real-time garbage collection. In Proceedings of the 6th International Workshop on Java Technologies for Real-Time and Embedded Systems. ACM, New York, 77--84. Google ScholarDigital Library
Schubert, R. F. 1974. Directions in data base management technology. Datamation 20, 9 (Sept), 48--51.Google Scholar
Schwarz, P. and Shoens, K. 1994. Managing change in the Rufus system. In Proceedings of the 10th International Conference on Data Engineering. IEEE Computer Society Press, Los Alamitos, 170--179. Google ScholarDigital Library
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.Google Scholar
Selinger, P. G. 1993. Predictions and challenges for database systems in the year 2000. In Proceedings of the 19th International Conference on Very Large Data Bases. Morgan-Kaufmann, San Francisco, 667--675. Google ScholarDigital Library
Seltzer, M., Bostic, K., McKusick, M. K., and Staelin, C. 1993. An implementation of a log-structured file system for UNIX. In Proceedings of the Winter 1993 USENIX Conference. USENIX Assoc., Berkeley, 307--326. Google ScholarDigital Library
Severance, D. G. and Lohman, G. M. 1976. Differential files: Their application to the maintenance of large databases. ACM Trans. Datab. Syst. 1, 3, 256--267. (For more details, see Lohman {1977}.) Google ScholarDigital Library
Shasha, D. and Goodman, N. 1988. Concurrent search structure algorithms. ACM Trans. Datab. Syst. 13, 1, 53--90. Google ScholarDigital Library
Shneiderman, B. 1973. Optimum data base reorganization points. Comm. ACM 16, 6, 362--365. Google ScholarDigital Library
Siebert, F. 2008. Limits of parallel marking garbage collection. In Proceedings of the 7th International Symposium on Memory Management (ISMM '08). ACM, 21--29. Google ScholarDigital Library
Silberschatz, A., Stonebraker, M., and Ullman, J. 1991. Database systems: Achievements and opportunities. Comm. ACM 34, 10, 110--120. Google ScholarDigital Library
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.Google Scholar
Siwiec, J. E. 1977. A high-performance DB/DC system. IBM Syst. J. 16, 2, 169--195.Google ScholarDigital Library
Skubiszewski, M. and Valduriez, P. 1997. Concurrent garbage collection in O₂. In Proceedings of the 23rd International Conference on Very Large Data Bases. Morgan-Kaufmann, San Francisco, 356--365. Google ScholarDigital Library
Smith, B. F. 1994. Understanding DB2 RUNSTATS statistics and version 3 enhancements. In Proceedings of the SHARE 82. Vol. II (CD-ROM). SHARE, Chicago.Google Scholar
Smith, G. S. 1990. Online reorganization of key-sequenced tables and files. Tandem Syst. Rev. 6, 2, 52--59.Google Scholar
Sockut, G. H. 1974. A graphics monitor for animation of dynamic processes. M.S. dissertation., Department of Electrical Engineering, Massachusetts Institute of Technology, Cambridge.Google Scholar
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.)Google Scholar
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}.)Google ScholarDigital Library
Sockut, G. H. 1985. A framework for logical-level changes within data base systems. Computer 18, 5, 9--27. Google ScholarDigital Library
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.)Google Scholar
Sockut, G. H., Beavin, T. A., and Chang, C.-C. 1997. A method for on-line reorganization of a database. IBM Syst. J. 36, 3, 411--436. Erratum in 37, 1, 1998, p. 152. Google ScholarDigital Library
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}.)Google Scholar
Sockut, G. H. and Goldberg, R. P. 1979. Database reorganization&#8212;Principles and practice. ACM Comput. Surv. 11, 4, 371--395. Google ScholarDigital Library
Sockut, G. H. and Iyer, B. R. 1996. A survey on online reorganization in IBM products and research. Data Engin. 19, 2, 4--11.Google Scholar
S&#246;derlund, L. 1980. A study on concurrent data base reorganization. Ph.D. dissertation. Deparment of Information Processing and Computer Science, University of Stockholm, Sweden.Google Scholar
S&#246;derlund, L. 1981a. Concurrent data base reorganization&#8212;Assessment of a powerful technique through modeling. In Proceedings of the 7th International Conference on Very Large Data Bases. ACM, New York, 499--509. (For more details, see S&#246;derlund {1980}.) Google ScholarDigital Library
S&#246;derlund, L. 1981b. Evaluation of concurrent physical database reorganization through simulation modeling. In Proceedings of the ACM SIGMETRICS Conference on Measurement and Modeling of Computer Systems. ACM, New York, 19--32. (Perform. Eval. Rev. 10, 3, Fall, SIGMETRICS). (For more details, see S&#246;derlund {1980}.) Google ScholarDigital Library
Srinivasan, J., Das, S., Freiwald, C., Chong, E. I., Jagannath, M., Yalamanchi, A., Krishnan, R., Tran, A.-T., DeFazio, S., and Banerjee, J. 2000. Oracle8i index-organized table and its application to new domains. In Proceedings of the 26th International Conference on Very Large Data Bases. Morgan-Kaufmann, San Francisco, 285--296. Google ScholarDigital Library
Srinivasan, V. 1992. On-line processing in large-scale transaction systems. Ph.D. dissertation. Computer Sciences Department, University of Wisconsin, Madison. (Also Tech. rep. 1071.) Google ScholarDigital Library
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}.)Google Scholar
Srinivasan, V. and Carey, M. J. 1991b. Performance of B-tree concurrency algorithms. In Proceedings of the 1991 ACM SIGMOD International Conference on Management of Data. ACM, New York, 416--425. (SIGMOD Record 20, 2). (For a revision, see Srinivasan and Carey {1993}, For more details, see Srinivasan {1992}.) Google ScholarDigital Library
Srinivasan, V. and Carey, M. J. 1992a. Compensation-based on-line query processing. In Proceedings of the 1992 ACM SIGMOD International Conference on Management of Data. ACM, New York, 331--340. (SIGMOD Record 21, 2). (For more details, see Srinivasan {1992}.) Google ScholarDigital Library
Srinivasan, V. and Carey, M. J. 1992b. Performance of on-line index construction algorithms. In Proceedings of the 3rd International Conference on Extending Database Technology, A. Pirotte, C. Delobel, and G. Gottlob, Eds. Lecture Notes in Computer Science, vol. 580. Springer-Verlag, New York, 293--309. (More details appear in Tech. rep. 1047, Computer Sciences Department, University of Wisconsin, Madison, 1991. (For even more details, see Srinivasan {1992}.) Google ScholarDigital Library
Srinivasan, V. and Carey, M. J. 1993. Performance of B⁺)-tree concurrency control algorithms. VLDB J. 2, 4, 361--406. (For more details, see Srinivasan {1992}.) Google ScholarDigital Library
Stanchina, S. and Meyer, M. 2007. Mark-sweep or copying&quest;: A &#8220;best of both worlds&#8221; algorithm and a hardware-supported real-time implementation. In Proceedings of the 6th International Symposium on Memory Management (ISMM 2007). ACM, New York, 173--182. Google ScholarDigital Library
Stonebraker, M. 1981. Hypothetical data bases as views. In Proceedings of the ACM-SIGMOD 1981 International Conference on Management of Data. ACM, New York, 224--229. Google ScholarDigital Library
Stonebraker, M. 1989. The case for partial indexes. SIGMOD Record 18, 4, 4--11. Google ScholarDigital Library
Stonebraker, M., Katz, R., Patterson, D., and Ousterhout, J. 1988. The design of XPRS. In Proceedings of the 14th International Conference on Very Large Data Bases. Morgan-Kaufmann, San Francisco, 318--330. Google ScholarDigital Library
Strickland, J. P., Uhrowczik, P. P., and Watts, V. L. 1982. IMS/VS: An evolving system. IBM Syst. J. 21, 4, 490--510.Google ScholarDigital Library
Subramaniam, M. and Loaiza, J. 2005. Online reorganization and redefinition of relational database tables. U.S. patent 6,965,899.Google Scholar
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.Google Scholar
Sun, X., Wang, R., Salzberg, B., and Zou, C. 2005. Online B-tree merging. In Proceedings of the 2005 ACM SIGMOD International Conference on Management of Data. ACM, New York, 335--346. Google ScholarDigital Library
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}.)Google Scholar
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.Google ScholarCross Ref
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.Google Scholar
Taylor, R. W. and Frank, R. L. 1976. CODASYL data-base management systems. ACM Comput. Surv. 8, 1, 67--103. Google ScholarDigital Library
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.Google Scholar
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.Google Scholar
Teorey, T. J. and Fry, J. P. 1982. Design of Database Structures. Prentice-Hall, Englewood Cliffs. Google ScholarDigital Library
Tranc&#243;n y Widemann, B. 2008. A reference-counting garbage collection algorithm for cyclical functional programming. In Proceedings of the 7th International Symposium on Memory Management (ISMM '08). ACM, New York, 71--80. Google ScholarDigital Library
Tresch, M. and Scholl, M. H. 1993. Schema transformation without database reorganization. SIGMOD Record 22, 1, 21--27. Google ScholarDigital Library
Troisi, J. 1994. Nonstop availability and database configuration operations. Tandem Syst. Rev. 10, 3, 18--23.Google Scholar
Troisi, J. 1996. Nonstop SQL/MP availability and database configuration operations. Data Engin. 19, 2, 12--18.Google Scholar
Tuel, J. W. G. 1978. Optimum reorganization points for linearly growing files. ACM Trans. Datab. Syst. 3, 1, 32--40. Google ScholarDigital Library
Valduriez, P. 1993. Parallel database systems: Open problems and new issues. Distrib. Paral. Datab. 1, 2, 137--165. Google ScholarDigital Library
Vechev, M. T., Yahav, E., and Bacon, D. F. 2006. Correctness-preserving derivation of concurrent garbage collection algorithms. In Proceedings of the 2006 ACM SIGPLAN Conference on Programming Language Design and Implementation (PLDI '06). 341--353. (SIGPLAN Notices 41, 6). Google ScholarDigital Library
Vechev, M. T., Yahav, E., Bacon, D. F., and Rinetzky, N. 2007. CGCExplorer: A semi-automated search procedure for provably correct concurrent collectors. In Proceedings of the 2007 ACM SIGPLAN Conference on Programming Language Design and Implementation. 456--467. (SIGPLAN Notices 42, 6). Google ScholarDigital Library
Versant Object Technology. 1991. VERSANT System Reference Manual (for IBM RISC System/6000). Versant Object Technology.Google Scholar
Vingralek, R., Breitbart, Y., and Weikum, G. 1994. Distributed file organization with scalable cost/performance. In Proceedings of the 1994 ACM SIGMOD International Conference on Management of Data. ACM, New York, 253--264. (SIGMOD Record 23, 2). (For a revision, see Breitbart et al. {1996}.) Google ScholarDigital Library
Vingralek, R., Breitbart, Y., and Weikum, G. 1998. SNOWBALL: Scalable storage on networks of work-stations with balanced load. Distrib. Paral. Datab. 6, 2, 117--156. Google ScholarDigital Library
Wang, J. and Hu, Y. 2001. PROFS -- Performance-oriented data reorganization for log-structured file system on multi-zone disks. In Proceedings of the 9th International Symposium on Modeling, Analysis, and Simulation of Computers and Telecommunication Systems (MASCOTS 2001). IEEE Computer Society Press, Los Alamitos, 285--292. Google ScholarDigital Library
Wang, J. and Hu, Y. 2002. WOLF -- A novel reordering write buffer to boost the performance of log-structured file systems. In Proceedings of the FAST '02 Conference on File and Storage Technologies. USENIX Association, Berkeley, 47--60. (For a revision, see Wang and Hu {2003}.) Google ScholarDigital Library
Wang, J. and Hu, Y. 2003. A novel reordering write buffer to improve write performance of log-structured file systems. IEEE Trans. Comput. 52, 12, 1559--1572. Google ScholarDigital Library
Wang, R. Y., Anderson, T. E., and Patterson, D. A. 1999. Virtual log based file systems for a programmable disk. In Proceedings of the 3rd Symposium on Operating Systems Design and Implementation (OSDI '99). ACM, New York, 29--43. (Operat. Syst. Rev., ACM SIGOPS (For more details, see Tech. rep. UCB/CSD 98/1031, Computer Science Department, University of California, Berkeley, 1998.) Google ScholarDigital Library
Wegiel, M. and Krintz, C. 2008. The mapping collector: Virtual memory support for generational, parallel, and concurrent compaction. In Proceedings of the 13th International Conference on Architectural Support for Programming Languages and Operating Systems (ASPLOS XIII). ACM, New York, 91--102. (Operat. Syst. Rev. 42, 2, ACM SIGOPS). Google ScholarDigital Library
Weikum, G. 1989. Clustering vs. concurrency: A framework and a case study. Tech. rep. ACA-ST-096-89, MCC, Austin.Google Scholar
Weikum, G., Zabback, P., and Scheuermann, P. 1991. Dynamic file allocation in disk arrays. In Proceedings of the 1991 ACM SIGMOD International Conference on Management of Data. ACM, New York, 406--415. (SIGMOD Record 20, 2). Google ScholarDigital Library
Wiederhold, G. 1983. Database Design. McGraw-Hill, New York. 2nd Ed. Google ScholarDigital Library
Wilkes, J., Golding, R., Staelin, C., and Sullivan, T. 1996. The HP AutoRAID hierarchical storage system. ACM Trans. Comput. Syst. 14, 1, 108--136. Google ScholarDigital Library
Wilson, P. R. 1992. Uniprocessor garbage collection techniques. In Proceedings of the International Workshop on Memory Management, Y. Bekkers and J. Cohen, Eds. Lecture Notes in Computer Science, vol. 637. Springer-Verlag, New York, 1--42. Google ScholarDigital Library
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.Google Scholar
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.Google Scholar
Winslow, L. E. and Lee, J. C. 1975. Optimal choice of data restructuring points. In Proceedings of the International Conference on Very Large Data Bases. ACM, New York, 353--363. Google ScholarDigital Library
Winter. 2005. TopTen program winners. On the web site (http://www.wintercorp.com), search the press releases for the most recent TopTen Program Winners.Google Scholar
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.Google Scholar
Yao, S. B., Das, K. S., and Teorey, T. J. 1976. A dynamic database reorganization algorithm. ACM Trans. Datab. Syst. 1, 2, 159--174. Google ScholarDigital Library
Yong, V.-F., Naughton, J. F., and Yu, J.-B. 1994. Storage reclamation and reorganization in client-server persistent object stores. In Proceedings of the 10th International Conference on Data Engineering. IEEE Computer Society Press, Los Alamitos, 120--131. Google ScholarDigital Library
Zabback, P., Onyuksel, I., Scheuermann, P., and Weikum, G. 1998. Database reorganization in parallel disk arrays with I/O service stealing. IEEE Trans. Knowl. Data Engin. 10, 5, 855--858. Google ScholarDigital Library
Zdonik, S. B. 1986. Maintaining consistency in a database with changing types. SIGPLAN Notices 21, 10, 120--127. Google ScholarDigital Library
Zilio, D. C. 1996. Modeling on-line rebalancing with priorities and executing on parallel database systems. In Proceedings of the CASCON '96. IBM Centre for Advanced Studies, Toronto, Ontario, Canada. CD-ROM, (For later, more extensive analysis, see Zilio {1998}.) Google ScholarDigital Library
Zilio, D. C. 1998. Physical database design decision algorithms and concurrent reorganization for parallel database systems. Ph.D. dissertation, Department of Computer Science, University of Toronto, Toronto, Ontario, Canada. Google ScholarDigital Library
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.Google Scholar
Zou, C. and Salzberg, B. 1996b. On-line reorganization of sparsely-populated B⁺-trees. In Proceedings of the 1996 ACM SIGMOD Intl. Conf. Management of Data. 115--124. (SIGMOD Record 25, 2). Google ScholarDigital Library
Zou, C. and Salzberg, B. 1996c. Towards efficient online database reorganization. Data Engin. 19, 2, 33--40.Google Scholar
Zou, C. and Salzberg, B. 1998. Safely and efficiently updating references during on-line reorganization. In Proceedings of the 24th Annual International Conference on Very Large Data Bases. Morgan-Kaufmann, San Francisco, 512--522. (For more details, see Zou and Salzberg {1996a}.) Google ScholarDigital Library

Index Terms

Online reorganization of databases

Recommendations

Optimal reorganization of distributed space disk files

In most database organizations, the cost of accessing the database will increase due to structural changes caused by updates and insertions. By reorganizing the database, the access costs can be reduced. A basic problem is to establish the proper ...
Read More
A dynamic database reorganization algorithm

Reorganization is necessary in some databases for overcoming the performance deterioration caused by updates. The paper presents a dynamic reorganization algorithm which makes the reorganization decision by measuring the database search costs. ...
Read More
Online reorganization in read optimized MMDBS
SIGMOD '11: Proceedings of the 2011 ACM SIGMOD International Conference on Management of data

Query performance is a critical factor in modern business intelligence and data warehouse systems. An increasing number of companies uses detailed analyses for conducting daily business and supporting management decisions. Thus, several techniques have ...
Read More

Reviews

Reviewer: Ned Chapin

This survey of literature on system maintenance of large databases focuses on databases that are used 24 hours a day, seven days a week. Since such a database is continuously online, system maintenance must also be done online, on the fly, without taking the database out of service, even briefly. This extensive survey relies on a reference list that consists of 373 items. Sockut and Iyer assume that the reader will recognize that a database can be regarded as having a logical structure-how the accessing software views the database-and a physical structure-how the data is represented in the storage media where the database resides, such as a hard disk. They use the term "reorganization" to refer to official intentional changes in one or both of these structures. The authors do not address the effects of malware attacks or recovery from them, and they say little about database management systems (DBMSs). Confusingly, and not in accordance with the relevant International Organization for Standardization (ISO) standards, the authors limit their use of the term "maintenance" to corrective maintenance for the restoration of the physical structure of a database that was affected adversely during its normal expected use-reading, replacing, inserting, or deleting data-without affecting the associated logical structure. Yet, the focus of this entire survey paper is online database system maintenance, including corrective maintenance. Based on what Sockut and Iyer regard as issues in online database reorganization, the survey is structured into three categories of reorganization: maintenance (their definition), physical restructuring, and logical restructuring. The summary of each reorganization category is presented in a format that can also be read as a tutorial. The authors are careful to note the effects of different kinds of databases-such as relational and hierarchical-as they report their survey of the literature. They are also alert to side effects, such as slower performance; the possible need for storage garbage collection; the additional storage space required; the use of log files; how up-to-date the database is; the effects on indexes, where relevant; and the kind and amount of general additional overhead created while processing online reorganization and providing the capability for processing online reorganization. Two outstanding features of the survey are: first, its comprehensive scope-the authors cover so much of the scattered literature that readers will be saved weeks of research; and, second, the terse and able summaries of the literature, which draw attention to the growing importance of the online system maintenance of online databases. Overall, this paper is a very worthwhile contribution to software maintenance and evolution literature. Online Computing Reviews Service

Access critical reviews of Computing literature here

Become a reviewer for Computing Reviews.

Comments

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Article

Published in

ACM Computing Surveys Volume 41, Issue 3
July 2009
284 pages
ISSN:0360-0300
EISSN:1557-7341
DOI:10.1145/1541880
Issue’s Table of Contents

Copyright © 2009 ACM
Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]
Sponsors
In-Cooperation
Publisher
Association for Computing Machinery
New York, NY, United States
Publication History
- Published: 30 July 2009
- Accepted: 1 April 2008
- Revised: 1 July 2000
- Received: 1 June 1993
Published in csur Volume 41, Issue 3

Permissions
Request permissions about this article.
Request Permissions

Check for updates
Author Tags
Clustering
concurrent reorganization
indexes
log-structured file systems
maintenance
online reorganization
redefinition
reorganization
restructuring
schema evolution
very large databases
Qualifiers
- research-article
- Research
- Refereed
Conference
Funding Sources
Other Metrics
View Article Metrics

Article Metrics
- 32
  Total Citations
  View Citations
- 4,714
  Total Downloads
- Downloads (Last 12 months)27
- Downloads (Last 6 weeks)5
Other Metrics
View Author Metrics
Cited By
View all

PDF Format

View or Download as a PDF file.

PDF

eReader

View online with eReader.

eReader

Online reorganization of databases

ACM Computing Surveys

Abstract

References

Cited By

Index Terms

Recommendations

Optimal reorganization of distributed space disk files

A dynamic database reorganization algorithm

Online reorganization in read optimized MMDBS

Reviews

Access critical reviews of Computing literature here

Comments

Login options

Full Access

Published in

Sponsors

In-Cooperation

Publisher

Publication History

Permissions

Check for updates

Author Tags

Qualifiers

Conference

Funding Sources

Other Metrics

Article Metrics

Other Metrics

Cited By

PDF Format

eReader

Digital Edition

Caption

Online reorganization of databases

ACM Computing Surveys

Abstract

References

Cited By

Index Terms

Recommendations

Optimal reorganization of distributed space disk files

A dynamic database reorganization algorithm

Online reorganization in read optimized MMDBS

Reviews

Access critical reviews of Computing literature here

Comments

Login options

Full Access

Published in

Sponsors

In-Cooperation

Publisher

Publication History

Permissions

Check for updates

Author Tags

Qualifiers

Conference

Funding Sources

Article Metrics

Other Metrics

PDF Format

eReader

Digital Edition

Share this Publication link

Share on Social Media