Recti cultus pectora roborant

CS 457 / 557

Database Software Design

Course outline

Course web page

Prof: Lin Jensen
Office: Johnson 115.  Office Hours (winter 2018) Before class, and Friday 2 - 4 pm

phone extension: 2361

Textbook: "Database Systems, the Complete Book, Second Edition" Hector Garcia-Molina, Jeffrey Ullman, Jennifer Widom. ISBN 0-13-187325-3. This is the same book used for  CS 307, "Using and designing databases." We will essentially cover the second half of the book.

Database management systems (DBMS) offer a generalized solution to many problems of storing, updating, processing, and retrieving (querying) data. Major topics:
  1. Storage Management. We must assume that, in general, so much data will be stored that it cannot fit into main memory. Thus we must make effective use of secondary storage (usually, disks), which is block structured. This strongly influences the data structures and algorithms that are appropriate. Record structures
  2. Indexes: Various index structures, and their implications for efficient query processing. If time permits, multi-dimensional indexes.
  3. Query Processing: Algorithms for efficient implementation of relational algebra operations. Joins of tables are generally the most time-intensive. Compiling SQL queries into relational algebra, and optimizing them.
  4. Failures: logging and recovery
  5. Transaction processing. Transactions in a DBMS are ACID, that is, they are Atomic(all actions or none), leave the database in a Consistent state, Isolated from other concurrent transactions, and Durable. Logging and error recovery are important for this. Data must survive power interruptions, computer or disk crashes, fire, and other calamities. Transaction may have to be rolled back in some circumstances, in which case the database must contain no trace of whatever it had done. The most common methods of isolation are locking and using timestamps.
  6. Parallel processing
  7. Distributed databases.  Distributed locking and commit are particularly interesting problems.
  8. (if time permits) Information integration - wrappers and XML
  9. Internet issues, in particular page rank and "link spam."

Grading Scheme

Midterm - 23 February
Final exam
Graduate report


No supplemental exam will be allowed.

Graduate students may submit a short report on some topic related to databases for 10% of the course grade.
To be completed by the last week of classes. I would be happy to have some of you present your findings to the class.