CS 33 (Spring 2011): Amit Chakrabarti

Teaching Home

Computer Science 33
Information Systems

Amit Chakrabarti

Spring 2011

Under Construction

[ Announcements | Administrative Basics | Useful Resources | Schedule and Homeworks | Grades Database ]

Course Description

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.

Announcements

Newer announcements are at the top. Think "blogs" or "twitter".

[Mar 28] Please set up for the course by sending the instructor an email with your name, Unix username, and chosen CS33 password.
[Mar 3] Spread the word! There are some big changes in the course this year.
[Mar 3] You will need an account on the CS department UNIX servers for some of your work in this course. Make sure you have one.

Administrative Basics

Important! Please also read and familiarize yourself with the administrative details not covered in the outline below.

In there, you will find

general instructions for preparing homework submissions,
the late submission policy, and
how the honor code applies to this course.

Please pay special attention to the latter; violations of the honor code will be treated with extreme seriousness.

Lectures
Sudikoff 214 | 2 hour | Mon-Wed-Fri 13:45-14:50, X-hr Thu 13:00-13:50

Instructor
Amit Chakrabarti | Sudikoff 107 | 6-1710 | Office hours: Wed 15:00-16:00, Fri XXX, or by appointment

Teaching Assistants
Shahrzad Haddadan | Sudikoff 253 | 6-0319 | Office hours: Thu 16:00-17:00, Sun 17:00-18:00, or by appointment

Textbook (Required)
"Database System Concepts," Fifth or Sixth Edition.
Avi Silberschatz, Henry F. Korth, S. Sudarshan.

Prerequisites
CS 23

Work
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.

Useful Resources

MySQL reference manual, for Version 5.1, which is what we have on sunapee.
PHP function reference.
Javascript tutorial and reference, at w3schools.
Short XPath and XQuery tutorials and references, at w3schools.

Schedule and Homeworks

Please ignore the "reading due" column for now. It is woefully out of sync.

Lecture # and Date		Corresponding Book Sections	Homework Due	Topics Covered in This Lecture
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
10.	Apr 13	Chap. 4		More on PHP; input validation using JavaScript
	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

Homework Submission Form and Grades Database

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!