Exam is Closed Book
COMPSCI 516: Qualifying Exam Syllabus
Topics Covered:
- Relational model and query
- Relational Algebra
- SQL (basic queries, aggregates, subqueries, null, joins, outerjoins, constraints, modification)
- SQL recursion
- Database Design
- Normalization (BCNF, BCNF decomposition, lossless decomposition, 4NF)
- Database Internals
- Index (clustered vs. unclustered, dense vs. sparse, tree vs. hash,
- B+tree index inserts and deletes)
- External sorting
- Join algorithms (nested loop joins - page oriented, index-nested, hash-join, sort-merge join) Query optimization (estimation of cost (as no. of pages) and size (no. of tuples), Selinger's dynamic programming algorithm) Parallel query processing (sorting and join)
- Transactions
- ACID properties
- Schedules (Serial, serializable, recoverable, cascading rollback) Two-phase locking/2PL (dependency graph, 2PL, strict 2PL) REDO/UNDO logging (steal/force, write ahead rule, recovery, checkpointing)
Reference:
- Database Systems: The Complete Book (second edition); Hector Garcia-Molina, Jeffrey Ullman, and Jennifer Widom
- Database Management Systems (third edition); Raghu Ramakrishnan and Johannes Gehrke
Sample Exams: