Computer Science 33
Spring 2011Under Construction
In this course we shall study the management of large bodies of data or information. During the first half of the course, we shall study schemes for the representation, manipulation, and storage of complex information structures as well as algorithms for processing these structures efficiently and for retrieving the information they contain. In particular, we shall spend considerable time on relational algebra, SQL, database normalization, indexing and hashing.
In the second half of the course, we shall study — at a high level — the issues raised when databases are shared by several users and/or several computers. This includes such topics as transaction processing, robustness guarantees against failure, security and data integrity guarantees from unauthorized access, privacy. Time permitting, we might also consider data mining, warehousing and object-oriented schemes for multimedia data.
It is expected that a student who enrols for this course already knows how to program and is comfortable working within a UNIX-like environment. Some degree of mathematical maturity will be required for the more theoretical aspects of the course.
Important! Please also read and familiarize yourself with the administrative details not covered in the outline below.
In there, you will find
Please pay special attention to the latter; violations of the honor code will be treated with extreme seriousness.
||Sudikoff 214 | 2 hour | Mon-Wed-Fri 13:45-14:50, X-hr Thu 13:00-13:50|
||Amit Chakrabarti | Sudikoff 107 | 6-1710 | Office hours: Wed 15:00-16:00, Fri XXX, or by appointment|
Shahrzad Haddadan | Sudikoff 253 | 6-0319 |
Office hours: Thu 16:00-17:00, Sun 17:00-18:00, or by appointment
"Database System Concepts," Fifth or Sixth Edition.
Avi Silberschatz, Henry F. Korth, S. Sudarshan.
Homework assignments, roughly one a week [45 points] |
Three in-class quizzes [30 points]
Final exam [25 points]
Towards the end of term, the homework assignments might resemble a mini-project.
Please take note of the late homework policy. It will be enforced, strictly.
Topics Covered in
|1.||Mar 28||—||Course overview; relational algebra; the fundamental operators|
|2.||Mar 30||Chaps. 1, 2||More relational algebra including joins; intro to SQL|
|3.||Mar 31 (X-hr)||SQL help session|
|4.||Apr 1||Chap. 2||Extended relational algebra operators; null values; more SQL|
|5.||Apr 4||6.1||HW1||Yet more SQL; nested subqueries; modifying the database|
|6.||Apr 6||3.1-3.5||Combining SQL with a general-purpose langauge; embedded and dynamic SQL|
|7.||Apr 7 (X-hr)||ODBC help session|
|8.||Apr 8||Keys; key constraints; E-R diagrams|
|9.||Apr 11||HW2||More on E-R diagrams; web-based interfaces; PHP|
|Apr 14 (X-hr)||Quiz 1: Closed notes, in class|
|11.||Apr 15||Chap. 5||Relational calculus; QBE|
|12.||Apr 18||Chap. 6; C.1||HW3||More QBE; Introduction to XML and DTDs|
|13.||Apr 20||Chap. 7||XPath and XQuery|
|14.||Apr 21 (X-hr)||(not used)|
|15.||Apr 22||Normal forms: 1NF and BCNF|
|16.||Apr 25||HW4||Normal forms: 3NF; Various algorithms|
|17.||Apr 27||Chap. 8||Normal forms: MVDs and 4NF|
|Apr 28 (X-hr)||Quiz 2: Closed notes, in class|
|18.||Apr 29||Organizing storage; RAID|
|19.||May 2||HW5||File structure; Minimizing disk access; Intro to indexing|
|20.||May 4||Indexing: B+ trees|
|21.||May 5 (X-hr)||Updates on B+ trees; Multi-key and covering indices|
|22.||May 6||Hash file organization; Hash indices; Bitmap indices|
|23.||May 9||HW6||Query processing I: selection and sorting|
|24.||May 11||Query processing II: joins, hash join|
|25.||May 12 (X-hr)||(not used)|
|26.||May 13||Query optimization (overview)|
|27.||May 16||HW7||Join ordering; Introduction to Transactions; ACID properties|
|28.||May 18||13.1 – 13.2||Serializability; Concurrency Control I|
|May 19 (X-hr)||Quiz 3: Closed notes, in class|
|29.||May 20||15.1 – 15.3||Concurrency Control II; Two-phase locking|
|30.||May 23||HW8||(no class; Amit is out of town)|
|31.||May 25||15.4; 15.5||Advanced locking protocols; Timestamp-based protocols|
|32.||May 26 (X-hr)||(not used)|
|33.||May 27||16.1 – 16.3||Failures; Overview of recovery system|
|34.||Jun 1||Chap. 16||Recovery II; Logging|
|Jun 3||Final Exam: In class, 15:00 – 18:00|
All homework is to be submitted electronically, using a homework submission form. Click here to get to that form.
The homework submission system is still experimental. Please use it only as instructed, for everyone's safety!