Database General Exam Reading List

Basic Textbooks

• J. Ullman and J. Widom.  A First Course in Database Systems.  All chapters.

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.  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.

  Optional:

  • Michael Stonebraker, Eugene Wong, Peter Kreps, Gerald Held, "The Design and Implementation of INGRES," TODS 1(3), p189-222 (1976).

Query Optimization

• S. Chaudhuri.  An Overview of Query Optimization in Relational Systems.  PODS 1998. 
  

  Optional:

  • P. Selinger, M. Astrahan, D. Chamberlin, R. Lorie, T. Price.  Access Path Selection in a Relational Database Management System.  SIGMOD 1979.

  • L. M. Haas, J. C. Freytag, G. M. Lohman, H. Pirahesh.  Extensible Query Processing in Starburst. SIGMOD 1989.
  • G.  Graefe, W. J. McKenna: The Volcano Optimizer Generator: Extensibility and Efficient Search. ICDE 1993.

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.
• Ron Avnur and Joseph. M. Hellerstein. Eddies: Continuously Adaptive Query Processing. SIGMOD 2000.
• David A Patterson, Garth A Gibson, Randy H Katz. A Case for Redundant Arrays of Inexpensive Disks (RAID). SIGMOD 1998, Ten-Year Paper.

Mathematical Foundations

• J. Ullman. Database and Knowledge Base Systems, vol. I.  Chapter 7 (Design Theory).
• 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.

• Jeffrey D. Ullman. Information Integration Using Logical Views. ICDT 1997.

Database Statistics and Indexing

• Y. E. Ioannidis, S. Christodoulakis. On the Propagation of Errors in the Size of Join Results.  SIGMOD 1991.
• J. M. Hellerstein, J. F. Naughton, A. Pfeffer: Generalized Search Trees for Database Systems. VLDB 1995
• Lothar F. Mackert, Guy M. Lohman: R* Optimizer Validation and Performance Evaluation for Distributed Queries. VLDB 1986
• 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

• D. Chamberlin. XQuery: an XML query language. IBM Systems Journal 41(4), 2002.
• Shankar 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.

Optional:

• R. Baeza-Yates, B. Rebeiro-Neto. Modern Information Retrieval. 1999. Chapter 2.4-2.5 (Modeling); Chapter 8.1-8.3 (Indexing and Searching).

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.

Web

• Choose 3-4 papers from the Data Engineering Bulletin special issue on Web-Scale Data, Systems, and Semantics.

More Optional Reading

• M.J. Carey, D.J. DeWitt, J. Naughton.  The OO7 Benchmark.  SIGMOD 1993.
• J. Goldstein and P. Larson. Optimizing queries using materialized views: a practical scalable solution. Sigmod 2001
• P. Buneman, S. A. Naqvi, V. Tannen, L. Wong: Principles of Programming with Complex Objects and Collection Types. TCS 149(1): 3-8 (1995).
• J. Hellerstein, P. Haas, H. Wang. Online Aggregation. SIGMOD 1997.
• Z.G. Ives, A.Y. Levy, D.S. Weld, D. Florescu, M. Friedman. Adaptive Query Processing for Internet Applications. IEEE Data Engineering Bulletin 23(2), 2000.
• Alon Y. Halevy, Zachary G. Ives, Peter Mork, Igor Tatarinov. Peer Data Management Systems: Infrastructure for the Semantic Web. WWW Conference, 2003.
• C. Zaniolo, S. Ceri, C. Faloutsos, R. T. Snodgrass, V.S. Subrahmanian, R. Zicari.  Advanced Database Systems.  Chapter 5 (Overview of Temporal Databases), pp. 99-121.
• S. Ceri, R. Cochrane, J. Widom. Practical Applications of Triggers and Constraints: Successes and Lingering Issues. VLDB 2000.
• A. Doan, P. Domingos, A. Halevy: Learning to Match the Schemas of Data Sources: A Multistrategy Approach. Machine Learning 50(3): 279-301 (2003).

The list was updated on Oct 1 2007 by YongChul Kwon, using advice from Dan Suciu and Magda Balazinska.

The student should read all of the papers listed here, including at least eight (8) of the papers listed as optional.