Qualifying Exam Syllabus for COMPSCI 516: Computer Systems

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)


  • 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:

Return to:  Quals Home