Database General Exam Reading List

Basic Textbooks

• H. Garcia-Molina, J. Ullman and J. Widom. Database Systems: The Complete Book. Chapter 3: Design Theory for Relational Databases.

Data Models

• E.F. Codd. A Relational Model of Data for Large Shared Data Banks.CACM 13(6), 1970, pp. 377-387.
• M.J. Carey, D.J DeWitt. Of Objects and Databases: A Decade of Turmoil.  VLDB 1996.
• Stonebraker and Hellerstein. What goes around comes around. Red Book 4th Ed.

Systems

• Hellerstein and Stonebraker. Anatomy of a database system. Red Book. 4th Ed.
• M. Stonebraker, G. Kemnitz. The Postgres Next Generation Database Management System. CACM 34(10), 1991, pp. 78-92.
• Michael Stonebraker, Eugene Wong, Peter Kreps, Gerald Held, The Design and Implementation of INGRES. TODS 1(3), p189-222 (1976).
• Michael Stonebraker. Operating System Support for Database Management. CACM 24(7), 1981, pp. 412-418.
• Chamberlin, et al. A History and Evaluation of System R. CACM 24(10), 1981, pp. 632-646.

Query Optimization

• S. Chaudhuri. An Overview of Query Optimization in Relational Systems. PODS 1998.
• P. Selinger, M. Astrahan, D. Chamberlin, R. Lorie, T. Price. Access Path Selection in a Relational Database Management System. IGMOD 1979.

Query Execution

• G. Graefe. Query Evaluation Techniques for Large Databases. ACM Computing Surveys 25(2), 1993, pp. 73-170.
• A. Ailamaki, D. J. DeWitt, M. D. Hill, D. A. Wood: DBMSs on a Modern Processor: Where Does Time Go? VLDB 1999.

Mathematical Foundations

• J. Ullman and J. Widom. A First Course in Database Systems.,. All Chapters.
• S. Abiteboul, R. Hull, V. Vianu. Foundations of Databases. Chapter 8 (Functional and Join Dependency); Chapter 9 (Inclusion Dependency), except proofs.
• S. Abiteboul, R. Hull, V. Vianu. Foundations of Databases. Chapter 6, Sections 6.2 (Global Optimizations) and 6.4 (Computing with Acyclic Joins).
• J. Ullman. Database and Knowledge Base Systems, vol. I. Chapter 3 (Logic as a Data Model).
• J. Ullman. Database and Knowledge Base Systems, vol. II. Chapters 12 (Top-Down Evaluation), 13 (Magic Sets), 14 (Containment).
• M. Y. Vardi: Constraint Satisfaction and Database Theory: A Tutorial. PODS 2000, pp. 76-5.

Database Statistics and Indexing

• S. Chaudhuri, R. Motwani, V. Narasayya. On Random Sampling Over Joins.  SIGMOD 1999.
• J. M. Hellerstein, J. F. Naughton, A. Pfeffer: Generalized Search Trees for Database Systems. VLDB 1995
• L. Getoor, B. Taskar, D Killer. Selectivity Estimation Using Probabilistic Models. SIGMOD 2001.

Transaction Processing

• P. A. Bernstein, E. Newcomer.  Principles of Transaction Processing, 2nd ed., Chapter 1 (Introduction), Chapter 9 (Two-Phase Commit), Chapter 6 (Locking)--the new version, Chapter 8 (Database System Recovery).
• Michael J. Franklin. Concurrency Control and Recovery. The Handbook of Computer Science and Engineering, A. Tucker, ed., CRC Press, Boca Raton, 1997.

Parallel and Distributed Databases

• P. A. Bernstein, E. Newcomer. Principles of Transaction Processing, 2nd ed., Chapter 10 (Replication).
• T. Oszu, P. Valduriez. Principles of Distributed Database Systems, 2nd ed. Chapter 4 (Distributed Database Systems), pp. 82-99; Chapter 5 (Distributed Database Design), pp. 107-154, skimming examples, algorithms, and Section 5.4.3; Chapter 13 (Parallel Database Systems), pp. 420-452.
• D. Kossman. The State of the Art in Distributed Query Processing. ACM Computing Surveys 32(4), 2000, pp. 418-469.

Data Integration

• A.Y. Halevy.  Answering Queries Using Views: A Survey. VLDB Journal, 10(4).
• E. Rahm, P. Bernstein. A Survey of Approaches to Automatic Schema Matching. VLDB Journal (10), 2001.
• Alon Y. Halevy, Anand Rajaraman, Joann Ordille. Data Integration: The Teenage Years. In proceedings of VLDB, 2006.

Semistructured and XML Data

• Hankar Pal, Istvan Cseri, Gideon Schaller, Oliver Seeliger, Leo Giakoumakis, Vasili Vasili Zolotov: Indexing XML Data Stored in a Relational Database. VLDB 2004.

Data Warehousing and Mining

• S. Chaudhuri, U. Dayal. An Overview of Data Warehousing and OLAP Technology. SIGMOD Record 26(1), 1997, pp. 65-74.
• R. Agrawal, R. Srikant. Fast Algorithms for Mining Association Rules in Large Databases. VLDB 1994.
• J. Gray, S. Chaudhuri, A. Bosworth, A. Layman, D. Reichart, M. Venkatrao, F. Pellow, H. Pirahesh. Data Cube: A Relational Aggregation Operator Generalizing Group-By, Cross-Tab, and Sub-Totals. Data Mining and Knowledge Discovery 1997.

Ranking and Information Retrieval

• Ronald Fagin, Amnon Lotem, Moni Naor: Optimal aggregation algorithms for middleware. JCSS 66(4): 614-656 (2003)
• Sanjay Agrawal, Surajit Chaudhuri, Gautam Das, Aristides Gionis. Automated Ranking of Database Query Results. CIDR, 2003.

Stream Processing

• Brian Babcock, Shivnath Babu, Mayur Datar, Rajeev Motwani, Jennifer Widom: Models and Issues in Data Stream Systems. PODS 2002: 1-16.
• D. Abadi, D. Carney, U. ?etintemel, M. Cherniack, C. Convey, S. Lee, M. Stonebraker, N. Tatbul, and S. Zdonik. Aurora: A New Model and Architecture for Data Stream Management. In VLDB Journal (12)2, 2003.