Requirements

• Open book, open notes.
• Calculators are allowed.
• No computer access is allowed.

Reading List

• Contents of database courses:

  • 214A: Li's course offerings of 2003 and 2004.
  • 214B: The topics covered by both Li's offering (Winter 2003) and Mehrotra's offering (Winter 2004), such as recovery (redo/undo logging), serializability, locking, concurency control, distributed commit protocols (2PC, 3PC). For these topics, you need to understand the materials in depth by looking at the materials of both offerings, and reading the corresponding papers below.
  • 215:. The necessary contents of different ICS215 offerings are covered by the following list.)

• Historical Systems Projects

  • A History and Evaluation of System R; Chamberlin et al., Readings in Database Systems (3rd edition); Ed. Stonebraker/Hellerstein pp. 54-68
  • The POSTGRES Next-Generation Database Management System; Stonebraker and Kemnitz, Readings in Database Systems (3rd edition); Ed. Stonebraker/Hellerstein pp. 524-538
  • Starburst Mid-Flight: As the Dust Clears; Haas et al., IEEE TKDE, 2(1), March 1990, pp. 143-160

• Query Processing:

  • Access Path Selection in a Relational Database Management System; Selinger et al., Readings in Database Systems (3rd edition); Ed. Stonebraker/Hellerstein pp. 141-152
  • An Overview of Query Optimization in Relational Systems; Chaudhuri, PODS 1998

• Distributed and Parallel Databases

  • Principles of Distributed Database Systems (2nd edition); Ozsu and Valduriez: chapters 5, 7, 8, 9
  • The Dangers of Replication and a Solution; Gray et al., Readings in Database Systems (3rd edition); Ed. Stonebraker/Hellerstein pp. 372-381

• Transaction Management and Concurrency Control

  • Transaction Processing: Concepts and Techniques; Gray and Reuter: chapters 1.2, 1.3.3, 3.5, 5.2.2, 5.2.4, 5.3, 5.4, 9.6, 10.3.2-10.3.6, 12.6
  • ARIES: A Transaction Recovery Method Supporting Fine-Granularity Locking and Partial Rollbacks Using Write-Ahead Logging; Mohan et al., Readings in Database Systems (3rd edition); Ed. Stonebraker/Hellerstein pp. 251-285

• Web Searching

  • Lawrence and Giles, Searching the World Wide Web, Science, 1998.
  • Brin and Page, The Anatomy of a Large-Scale Hypertextual Web Search Engine WWW7/Computer Networks 30(1-7): 107-117, 1998.
  • Jon M. Kleinberg, Authoritative Sources in a Hyperlinked Environment, Journal of ACM 46(5): 604-632, 1999.
  • Ravi Kumar, Prabhakar Raghavan, Sridhar Rajagopalan, and Andrew Tomkins, Trawling the Web for emerging cyber-communities, WWW 1999

• Indexing structures:

  • The Hybrid Tree: An Index Structure for High Dimensional Feature Spaces, Kaushik Chakrabarti, Sharad Mehrotra ICDE, 1999.
  • Distance-Based Indexing For High-Dimensional Metric Spaces, Tolga Bozkaya, SIGMOD 1997.
  • M-tree: An Efficient Access Method for Similarity Search in Metric Spaces, Paolo Ciaccia and Marco Patella and Pavel Zezula, VLDB Journal, 1997.
  • The SR-tree: An Index Structure for High-Dimensional Nearest Neighbor Queries, Norio Katayama, Shin'ichi Satoh, SIGMOD 1997.

• NN search:

  • An Optimal Algorithm for Approximate Nearest Neighbor Searching in Fixed Dimensions, Sunil Arya, David M. Mount, Nathan S. Netanyahu, Ruth Silverman, Angela Y. Wu, Journal of the ACM, 1994.
  • Nearest Neighbor Queries, Nick Roussopoulos, Stephen Kelley, Frédéric Vincent, SIGMOD 1995.
  • When is nearest neighbor meaningful?, K. Beyer, J. Goldstein, R. Ramakrishnan and U. Shaft. ICDT, 1999.

• Top-k queries:

  • Fagin, Combining fuzzy information from multiple systems (extended abstract), PODS 1996.
  • Fagin et al., Optimal Aggregation Algorithms for Middleware, PODS 2001