As relational DBMSs become more and more popular and as organizations grow, the sizes of individual tables are increasing dramatically. Unfortunately, current DBMSs do not allow updates to be performed on a table while an index (e.g., a B+-tree) is being built for that table, thereby decreasing the systems' availability. This paper describes two algorithms in order to relax this restriction. Our emphasis has been to maximize concurrency, minimize overheads and cover all aspects of the problem. Builds of both unique and nonunique indexes are handled correctly. We also describe techniques for making the index-build operations restartable, without loss of all work, in case a system failure were to interrupt the completion of the creation of the index. In this connection, we also present algorithms for making a long sort of operation restartable. These include algorithms for the sort and merge phases of sorting.

Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.

	CHHIM91	Josephine M. Cheng , Donald J. Haderle , Richard Hedges , Balakrishna R. Iyer , Ted Messinger , C. Mohan , Yun Wang, An Efficient Hybrid Join Algorithm: A DB2 Prototype, Proceedings of the Seventh International Conference on Data Engineering, p.171-180, April 08-12, 1991
	DeGr90	David J. DeWitt , Jim Gray, Parallel database systems: the future of database processing or a passing fad?, ACM SIGMOD Record, v.19 n.4, p.104-112, Dec. 1990  [doi>10.1145/122058.122071]
	Gray78	Jim Gray, Notes on Data Base Operating Systems, Operating Systems, An Advanced Course, p.393-481, January 1978
	Knut73	Donald E. Knuth, The art of computer programming, volume 3: (2nd ed.) sorting and searching, Addison Wesley Longman Publishing Co., Inc., Redwood City, CA, 1998
	MHLPS92	C. Mohan , Don Haderle , Bruce Lindsay , Hamid Pirahesh , Peter Schwarz, ARIES: a transaction recovery method supporting fine-granularity locking and partial rollbacks using write-ahead logging, ACM Transactions on Database Systems (TODS), v.17 n.1, p.94-162, March 1992  [doi>10.1145/128765.128770]
	Moha90a	C. Mohan, ARIES/KVL: a key-value locking method for concurrency control of multiaction transactions operating on B-tree indexes, Proceedings of the sixteenth international conference on Very large databases, p.392-405, September 1990, Brisbane, Australia
	Moha90b	C. Mohan, Commit-LSN: a novel and simple method for reducing locking and latching in transaction processing systems, Proceedings of the sixteenth international conference on Very large databases, p.406-418, September 1990, Brisbane, Australia
	Moha92	Mohan, C. Supporting Very Lorge TobZes, Proc. 7th Brazilian Symposium on Database Systems, Porto Alegre, May 1992.
	MoLe92	C. Mohan , Frank Levine, ARIES/IM: an efficient and high concurrency index management method using write-ahead logging, Proceedings of the 1992 ACM SIGMOD international conference on Management of data, p.371-380, June 02-05, 1992, San Diego, California, United States
	MoPL92	C. Mohan , Hamid Pirahesh , Raymond Lorie, Efficient and flexible methods for transient versioning of records to avoid locking by read-only transactions, Proceedings of the 1992 ACM SIGMOD international conference on Management of data, p.124-133, June 02-05, 1992, San Diego, California, United States
	Ober80	Obermarck, R. IHS/V5 Progrom isolotion Feoture, IBM Research Report RJ2879, IBM San Jose Research Laboratory, July 1980.
	PMCLS90	Hamid Pirahesh , C. Mohan , Josephine Cheng , T. S. Liu , Pat Selinger, Parallelism in relational data base systems: architectural issues and design approaches, Proceedings of the second international symposium on Databases in parallel and distributed systems, p.4-29, July 02-04, 1990, Dublin, Ireland  [doi>10.1145/319057.319060]
	SiSU91	Avi Silberschatz , Michael Stonebraker , Jeff Ullman, Database systems: achievements and opportunities, Communications of the ACM, v.34 n.10, p.110-120, Oct. 1991  [doi>10.1145/125223.125272]
	SrCa91	Srinivasan, V., Carey, M. On-Line Index Construction Algorithms, Proc. 4th International Workshop on High Performance Transaction Systems, Asllomar, September 1991.
	TeGu84	Teng, J., Gumaer, R. Honogtng IBH Dotobose 2 Buffers to Hoximize Performonce, IBM Systems Journal, Vol. 23, No. 2, 1984.

• Data structures for quadtree approximation and compression Communications of the ACM   28, 9
  Hanan Samet
  
  
• A hierarchical single-key-lock access control using the Chinese remainder theorem Proceedings of the 1992 ACM/SIGAPP Symposium on Applied computing
  Kim S. Lee ,  Huizhu Lu ,  D. D. Fisher
  
  
• Putting innovation to work: adoption strategies for multimedia communication systems Communications of the ACM   34, 12
  Ellen Francik ,  Susan Ehrlich Rudman ,  Donna Cooper ,  Stephen Levine
  
  
• The GemStone object database management system Communications of the ACM   34, 10
  Paul Butterworth ,  Allen Otis ,  Jacob Stein
  
  
• An intelligent component database for behavioral synthesis Proceedings of the 27th ACM/IEEE conference on Design automation
  Gwo-Dong Chen ,  Daniel D. Gajski
  
  

• ACM SIGMOD Record
  Volume 21 ,  Issue 2   June 1, 1992