Reading list (selected from CMU)

The Roots

Background: Stonebraker

and Hellerstein, Introduction to the Section "The Roots", pages 1-4

1. Astrahan, M. , et al., "System R: Relational Approach to Database Management", ACM TODS, 1(2), 1976 (*)
2. Chamberlin, D., et al., A History and Evaluation of System R, Communications of the ACM, 24(10), 1981 (*)
3. Stonebraker, M., et al., (1976) "The Design and Implementation of INGRES", ACM TODS, 1(3), 1976 (*)
4. Stonebraker, M., (1980) Retrospection on a Database System, ACM TODS, 5(2), 1980

Object-Oriented and Object-Relational Database Systems

Background:

Atkinson, M., et al., The Object-Oriented Database System Manifesto (HTML version), First International Conference on Deductive and Object-Oriented Databases, Kyoto, Japan, 1989 (also appeared in Proceedings of ACM SIGMOD 1990)

1. Lamb et al., The ObjectStore System, Communications of the ACM, 34(10), 1991 (*)
2. Stonebraker, M., "Inclusion of New Types in Relational Database Systems", Proceedings of the IEEE Conference on Data Engineering, 1986 (*)

Concurrency Control

Background:

Gray and Reuter, Sections 7.3 and 7.4

1. Gray, J., et al., "Granularity of Locks and Degrees of Consistency in a Shared Database", IFIP Working Conference on Modelling of Database management Systems, AFIPS Press, 1976 (*)
2. H. T. Kung, John T. Robinson, "On Optimistic Methods for Concurrency Control", VLDB 1979 (*)
3. Philip L. Lehman, S. Bing Yao, "Efficient Locking for Concurrent Operations on B-Trees", ACM TODS 6(4): 650-670, 1981 (*)
4. Mohan, C., ARIES/KVL: A Key-Value Locking Method for Concurrency Control of Multiaction Transactions Operating on B-Tree Indexes, Proceedings of the 16th VLDB Conference, Brisbane, August 1990
5. Srinivasan, V., and Carey, M., Performance of B-Tree Concurrency Control Algorithms, Proceedings of the ACM SIGMOD Conference, Denver, CO, June 1991.

Logging and Recovery

Background:

Gray and Reuter, Chapters 9-11

1. Mohan, C., et al., ARIES: A Transaction Recovery Method Supporting Fine-Granularity Locking and Partial Rollbacks Using Write-Ahead Logging, ACM TODS, 18(1), 1991 (*)
2. Mohan, C., Repeating History Beyond ARIES, Proceedings of VLDB conference, 1999 (*)

Access Paths and Indexes

1. Gray and Reuter, Section 15.4 "B-Trees" (Recommendation: Read the whole Chapter 15) (*)
2. Ramakrishnan & Gehrke, Chapter 6, "Hash-Based Indexing" (*)

Buffer Management

Background:

Gray and Reuter, Chapter 13

1. Chou, H., and DeWitt, D., An Evaluation of Buffer Management Strategies for Relational Database Systems, Proceedings of the 11th VLDB Conference, 1985 (*)
2. O'Neil, E. , O'Neil, P., and Weikum, G., The LRU-K Replacement Algorithm for Database Disk Buffering, Proceedings of the ACM SIGMOD Conference, Washington, D.C., June 1993 (*)

Query Processing and Optimization

1. Shapiro, L., Join Processing in Database Systems with Large Main Memories, ACM TODS, 11(3), September 1986 (*)
2. Goetz Graefe, The Value of Merge-Join and Hash-Join in SQL Server, Proceedings of the VLDB Conference, September 1999 (*)
3. Ioannidis, Y., Kang, Y., Randomized Algorithms for Optimizing Large Join Queries, Proceedings of the ACM SIGMOD Conference, Atlantic City, NJ, May 1990
4. T. Urhan & M. Franklin, XJoin: A Reactively-Scheduled Pipelined Join Operator, IEEE Data Engineering Bulletin, June 2000, pp. 27-33
5. Graefe, G., Query Evaluation Techniques for Large Databases, ACM Computing Surveys, 25(2), June 1993 (Read only Sections 1 through 5) (*)
6. Graefe, G., Dynamic query evaluation plans: Some course corrections?, IEEE Database Engineering 23(2), Jume 2000 (*)
7. Selinger, P., et al., Access Path Selection in a Relational Database Management System, Proceedings of the ACM SIGMOD Conference, Boston, MA, 1979 (*)
8. Chaudhuri, S., An Overview of Query Optimization in Relational Systems, Proceedings of the ACM PODS Conference,, Seattle, WA, 1998 (*)
9. V. Poosala, P.J. Haas, Y. Ioannidis, and E.J. Shekita. Improved histograms for selectivity estimation of range predicates, Proceedings of the ACM SIGMOD Conference, 1996
10. IEEE Database Engineering, Special issue on Query Processing in Commercial Database Systems, 16(4), Dec. 1993
11. IEEE Database Engineering, Special issue on Adaptive Query Processing, 23(2), Dec. 1993

DBMS and the Operating System

1. Stonebraker, M., Operating System Support for Database Management, Communications of the ACM, 24(7), 1981 (*)
2. Ramakrishnan & Gehrke, Section 3.3.2, "Buffer Management in DBMS versus OS" (*)

Disks

1. Ruemmler, C., and Wilkes, J., An Introduction to Disk Drive Modelling, IEEE Computer, 27 (3), March 1994 (*)
2. Gray, J., and Graefe, G., The Five Minute Rule Ten Years Later and Other Computer Storage Rules of Thumb, ACM SIGMOD Record, December 1997 (*)
3. Gray, J., and Shenoy, P., Rules of Thumb in Data Engineering, Proceedings of the IEEE Conference on Data Engineering, 2000.

Sorting

Background:	Common Sorting Algorithms (quicksort, binary sort, etc)
	Ramakrishnan and Gehrke Chapter 11

1. Nyberg, C., Barclay, T., Cvetanovic, Z., Gray, J., Lomet, D., AlphaSort: A RISC Machine Sort, Proceedings of the ACM SIGMOD Conference, May 1994 (*)
2. Agarwal, R., A super scalar sort algorithm for RISC processors, Proceedings of the ACM SIGMOD Conference, June 1996 (*)
3. Andrea C. Arpaci-Dusseau, Remzi H. Arpaci-Dusseau, David E. Culler, Joseph M. Hellerstein and David A. Patterson, High-performance sorting on networks of workstations , Proceedings of the ACM SIGMOD Conference, May 1997

DBMSs on Modern Processors

1. A. Ailamaki, D. J. DeWitt, M. D. Hill, and D. A. Wood, DBMSs on a Modern Processor: Where Does Time Go?, Proceedings of the VLDB Conference, September 1999 (*)
2. K. Keeton, D. A. Patterson, Y. Q. He, R. C. Raphael, and W. E. Baker, Performance Characterization of a Quad Pentium Pro SMP Using OLTP Workloads, Proceedings of the 25th International Symposium on Computer Architecture, Barcelona, Spain, June 1998 (*)
3. J. L. Lo, L. A. Barroso, S. J. Eggers, K. Gharachorloo, H. M. Levy, and S. S. Parekh. An analysis of database workload performance on simultaneous multithreaded processors, Proceedings of the 25th Annual International Symposium on Computer Architecture, pages 39-50, June 1998.

Main-memory Database Systems

1. Hector Garcia-Molina and Kenneth Salem, Main memory database systems: an overview, TKDE 4(6), 1992 (*)
2. Philip Bohannon et al., The architecture of the Dali main-memory storage manager, Journal of Multimedia Tools and Applications, 1997 (*)

   More references are available in Mengzhi's last slide.

Benchmarking

Background:

Gray's Benchmark handbook, Chapter 1

1. Anon et al., "A Measure of Transaction Processing Power" (in red book), Datamation, 31(7), 1985 (*)
2. Eisenberg, A., and Melton, J., Standards in Practice, ACM SIGMOD Record, September 1998

Self-tuning Database systems

1. Chaudhuri, S. and Weikum, G. Rethinking Database System Architecture: Towards a Self-tuning RISC-style Database System, Proceedings of the VLDB conference, September 2000 (*)

Distributed and Mobile Database Systems

1. Swarup Acharya, Rafael Alonso, Michael J. Franklin, and Stanley B. Zdonik, Broadcast Disks: Data Management for Asymmetric Communications Environments, Proceedings of SIGMOD Conference 1995 (*)
2. Daniel Barbara, Mobile Computing and Databases - A Survey, TKDE 11(1), 108-117, 1999 (*)

Parallel Database Systems

1. D. J. DeWitt and J. Gray, Parallel Database Systems: The Future of High Performance Database Processing, Communications of the ACM, June 1992 (*)
2. D. J. DeWitt, S. Ghandeharizadeh, D. Schneider, H. Hsiao, A. Bricker, and R. Rasmussen, The GAMMA Database Machine Project, IEEE Transactions on Knowledge and Data Engineering, Vol. 2, No. 1, March 1990 (*)
3. R. D. Sloan, A practical implementation of the data base machine-Teradata DBC/1012, Proceedings of the Twenty-Fifth Hawaii International Conference on System Sciences, January 1992.

Data Mining

1. Rakesh Agrawal, Tomasz Imielinski and Arun Swami, Mining Association Rules Between Sets of Items in Large Databases, Proceedings of the ACM SIGMOD Conference, May 1993 (*)
2. M. Mehta, R. Agrawal and J. Rissanen, SLIQ: A Fast Scalable Classifier for Data Mining, Proceedings of the Fifth International Conference on Extending Database Technology, Avignon, France, March 1996 (*)

Spatial Applications

1. A. Guttman, R-Trees: A Dynamic Index Structure for Spatial Searching, Proceedings of the ACM SIGMOD Conference, 1984 (*)
2. H. Samet and W.G. Aref, Spatial Data Models and Query Processing, Modern Database Systems, 1995 (*)
3. Y. Manolopoulos, E. Nardelli, A. Papadopoulos, and G. Proietti, QR-Tree: A Hybrid Spatial Data Structure, , 1996
4. J. Karlsson, hQT*: A Scalable Distributed Data Structure for High-Performance Spatial Accesses, Proceedings of the International Conference on Foundations of Data Organization and Algorithms (FODO), 1998
5. H. Samet, The Design and Analysis of Spatial Data Structures, Addison-Wesley, Reading, MA, 1990
6. H. Samet, The Applications of Spatial Data Structures: Computer Graphics, Image Processing and GIS, Addison-Wesley, Reading, MA, 1990

Semistructured Data and XML

Background:

S. Abiteboul, P. Buneman, D. Suciu, Data on the Web: From Relations to Semistructured Data and XML, Morgan Kaufmann, 2000. Chapters/sections: 2, 3.1, 3.2.1, 3.2.2, 3.3.1, 4.1, 4.2

1. D. Suciu, An Overview of Semistructured Data, SIGACT News, 29(4):28-38, Dec 1998 (*)
2. J. Shanmugasundaram, G. He, K. Tufte, C. Zhang, D. DeWitt, J. Naughton, Relational Databases for Querying XML Documents: Limitations and opportunities Proceedings of the 25th VLDB, 302-314, 1999 (*)
3. J. Shanmugasundaram, E. Shekita, R.Barr, M. J. Carey, B. G. Lindsay, H. Pirahesh, B. Reinwald, Effciently Publishing Relational Data as XML Documents, Proceedings of the 26th VLDB, 65-67, 2000

Adaptive Query Processing

1. Joseph M. Hellerstein, Michael J. Franklin, Sirish Chandrasekaran, Amol Deshpande, Kris Hildrum, Sam Madden, Vijayshankar Raman, Mehul A. Shah, Adaptive Query Processing: Technology in Evolution, Special issue on Adaptive Query Processing, 23(2), Dec. 1993 (*)
2. Zachary G. Ives, Alon Y. Levy, Daniel S. Weld, Daniela Florescu, Marc Friedman, Adaptive Query Processing for Internet Applications, Special issue on Adaptive Query Processing, 23(2), Dec. 1993 (*)
3. Tolga Urhan and Michael J. Franklin, XJoin: A Reactively-Scheduled Pipelined Join Operator, Special issue on Adaptive Query Processing, 23(2), Dec. 1993 (*)
4. Luc Bouganim, Françoise Fabret, and C. Mohan, A Dynamic Query Processing Architecture for Data Integration Systems, Special issue on Adaptive Query Processing, 23(2), Dec. 1993 (*)