CS 457 / 557
Database Software Design
Course web page cs.ubishops.ca/ljensen/csc417/
Prof: Lin Jensen
Office: Johnson 115. Office Hours (winter 2018)
Before class, and Friday 2 - 4 pm
e-Mail:
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:
- 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
- Indexes: Various index
structures, and their implications for efficient query
processing. If time permits, multi-dimensional indexes.
- 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.
- Failures: logging and recovery
- 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.
- Parallel processing
- Distributed databases. Distributed locking and
commit are particularly interesting problems.
- (if time permits) Information integration - wrappers and XML
- Internet issues, in particular page rank and "link spam."
Grading Scheme
Assignments
|
40%
|
35%
|
Midterm - 23 February
|
20%
|
20% |
Final exam
|
40%
|
35%
|
Graduate report
|
|
10% |
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.