Topics for Database Systems

Comprehensive Exam

Posted: October 2006

Database Design

Entity-Relationship Modeling
Functional Dependencies (Armstrong's axioms, closure, minimal cover, etc)
Lossless Decompositions
Normalization

Normal Forms
BCNF
3NF

Relational Database Model

Integrity Constraints
Relational Algebra

SQL

DDL
DML
Simple SELECT Statements
Subqueries
INNER joins and OUTER joins
Grouping of tuples and aggregate functions
SQL:1999 JOIN Syntax

Data Organization and Indexing

B+-Tree Index
Clustered vs. Non-Clustered, Dense vs. Sparse

Query Processing

Algorithms for Selection, Projection, Join
Query trees
Query Evaluation Plans, Left-Deep evaluation Plans
Pipeline Evaluation

Transaction Management

ACID Properties
Serializability
Locking and lock management
Two-Phase Locking

Reading List

The topics above can be found in several advanced database textbooks. The exam will also contain questions to test your comprehension of published papers on database systems. The following is a list of the publications that you may be asked questions about:

1. An Overview of Data Warehousing and OLAP Technology
   by Surajit Chaudhuri and Umeshwar Dayal
   Appears in ACM SIGMOD Record, March 1997.
   
   
2. The Object-Oriented Database System Manifesto
   by M. Atkinson, F. Bancilhon, D. DeWitt, K. Dittrich, D. Maier, and S. Zdoni
   In Proceedings of the First International Conference on Deductive and Object-Oriented Databases, pages 223-40, Kyoto, Japan, December 1989.