LIST OF PAPERS AND BOOK CHAPTERS FOR THE DATABASE QUALIFYING EXAM

Note: The list below makes reference to chapters of two books:

* Fundamentals of Database Systems, by R. Elmasri and S. Navathe, Addison Wesley, Third Edition, 2000.
* Principles of Distributed Database Systems, by M. Ozsu and P. Valduriez, Prentice-Hall, Second Edition, 1999.

We refer to the first reference as Navathe and to the second as Ozsu. Another suggested book is the following:

* Database System Implementation, by H. Garcia-Molina, J. Ullman and J. Widom, Prentice-Hall, First Edition, 2000

 

- - - - - - - - - - - - - - - - -

Data Models

  1. ER Model - Navathe: Ch. 3 and 4

  2. Relational Model - Navathe: Ch. 7

  3. ER to Relational - Navathe: Sections 9.1 and 9.2

  4. Object Oriented Database - Navathe: Ch. 11 and Section 12.1

  5. Legacy Systems - Navathe: Appendix C and D

  6. Active Databases - "The Active Database Management System Manifesto: A Rulebase of ADBMS Features," ACM SIGMOD Record, 25(3), September 1996, 40-49.

  7. Database Design & Modeling - Navathe: Ch. 14 and 15

  8. Semantic and/or Temporal - R. Hull and R. King. "Semantic Database Modeling: Survey, Applications and Research Issues," ACM Computing Surveys, 19(3), 1987, pp.201-260 (Note: This is the old version. You should try to have access to the updated version as well.)

Query Processing

  1. Optimization

    • Areas

      • Syntactic
      • Semantic
      • Dynamic
      • Caching
      • Multiple
      • Cost Computation

    • Readings

      • Navathe: Ch. 18
      • Patricia G. Selinger, Morton M. Astrahan, Donald D. Chamberlin, Raymond A. Lorie, Thomas G. Price. "Access Path Selection in a Relational Database Management System." SIGMOD Conference 1979 : 23-34.
      • Guy M. Lohman: "Grammar-like Functional Rules for Representing Query Optimization Alternatives." SIGMOD 1988: 18-27.
      • EITHER Goetz Graefe, William J. McKenna "The Volcano Optimizer Generator: Extensibility and Efficient Search." ICDE 1993:209-218, 1993. -OR-Richard L. Cole, Goetz Graefe. "Optimization of Dynamic Query Evaluation Plans." SIGMOD 1994: 150-160.
      • Yannis E. Ioannidis, Younkyung Cha Kang: Randomized Algorithms for Optimizing Large Join Queries. SIGMOD 1990: 312-321
      • (Suggested Reading) Query Optimization (Yannis Ioannidis, unpublished: Another Good Complementary survey on Query Optimization)

  2. Algorithms

    • Areas
      • Join Algorithms (various)
      • Access Plans

    • Readings
      • Navathe: Ch. 18
      • G. Graefe, "Query Evaluation Techniques for Large Databases," ACM Computing Surveys, 25(2) (1993), pp. 73-170.

Transaction Processing
  1. Concurrency Control
    • Navathe: Ch. 19 and 20
    • Ozsu: Ch. 11
    • Naser S. Barghouti and Gail E. Kaiser. "Concurrency control in advanced database applications," ACM Computer Survey. 23(3) (Sep. 1991), pp. 269 - 317

  2. Recovery
    • Navathe: Ch. 21
    • T. Haerder and A. Reuter, "Principles of Transaction-Oriented Database Recovery," ACM Computing Surveys, 15(4), 287-317.
    • C. Mohan, et al."ARIES: A Transaction Method Supporting Fine-Granularity Locking and Partial Rollbacks Using Write-Ahead Logging," ACM TODS, 17(1), (March 1992).

Architectures
  1. Overview of Distributed Database - Ozsu: Ch. 4

  2. System Catalog - Navathe: Ch. 17

  3. Basics of allocation, fragmentation - Navathe 24

  4. M. Franklin, B. Jonsson, D. Kossman. "Performance Tradeoffs for Client-Server Query Processing" , SIGMOD, 1996

  5. "Parallel Database Systems: The Future of High Performance Database Systems," D. DeWitt and J. Gray, Comm. of the ACM, 35, 6, (June 1992), 85-97.

  6. CHOOSE A PAPER FROM: Heterogeneous Databases: Special Issue on Heterogeneous Databases, eds. A. Elmagarmid and C. Pu, ACM Computing Surveys, (1990).

Distributed Systems

  1. Fragmentation and Allocation - Ozsu: Ch. 5

  2. Distributed Query Optimization - Ozsu: Ch. 7-9

  3. Transation Management - Ozsu: Ch. 10

  4. S. Ceri, S.B. Navathe, G. Wiederhold, "Distribution Design of Logical Database Schemas," IEEE Transactions on Software Engineering, Vol. SE-9, No. 3, July 1983, pp. 487-504.

Physical Organization

  1. Navathe: Ch. 5 and 6

  2. V. Gaede and O. Gunther. "Multidimensional Access Methods." Computing Surveys, 30:2, 1998, 170-231.

  3. Patrick E. O'Neil, Dallan Quass. "Improved Query Performance with Variant Indexes." SIGMOD 1997: 38-49 available at: http://www.cs.umb.edu/~poneil/varindex.ps




Site current for Fall 2001.