HMC CS 133

Database and Knowledge-based Systems

Syllabus

Catalog Description
	Fundamental models of databases: entity-relationship, relational, deductive, object-oriented. Rela-tional algebra and calculus, query languages. Data storage, caching, indexing, and sorting. Locking protocols and other issues in concurrent and distributed data-bases. Prerequisite: Computer Science 70 and 80 (131 recommended). 3 credit hours.
Instructor
	Joshua S. Hodas 243 Olin, 621-8650 hodas@cs.hmc.edu http://www.cs.hmc.edu/~hodas For schedule and office hours, see schedule on office door, or check http://www.cs.hmc.edu/~hodas/schedule.html
Course Home Page
	http://www.cs.hmc.edu/~hodas/courses/cs133/
Textbook
	Database Management Systems (second edition), by Raghu Ramakrishnan and Johannes Gehrke, McGraw-Hill, 1999. (ISBN 0072322063) The cheapest I have found this is from Bigwords.com. I have set up a booklist (B-2BG3CZ) for direct ordering.
Date / Time / Place
	Monday and Wednesday, 2:45pm-4:00pm, in Parsons 285.
Selected Topics
	Entity-Relationship model as a modeling tool Relational data model Relational algebra, tuple and domain relational calculi Relational query languages (RDB, SQL) Relational design theory Physical data organization Query optimization Concurrent Databases: Transaction management and recovery techniques Distributed databases: Data distribution, distributed processing, coherency control As time allows, a selection from: Deductive Databases: Logic as a data model, Datalog. Data Mining Object-Oriented Databases
Assignments and Grading
	Grading in this course is based on three components: homework assignments, exams, and a term project.
Assignments	Homework assignments are given roughly weekly, and center on the details of the systems being discussed. They are designed to give you hands-on experience with different flavors of database models and query languages as well as design issues and theoretical foundations. Some are paper and pencil assignments, some involve online work with one of the systems, and some are a combination. Homeworks will generally be due at 5:00 PM on Friday afternoons. Together the homework assignments will account for 40% of your grade.
Term Project	A small-group (2-4 student) team project will account for 30% of your grade. The project will consist of the design and implementation of some web-based database application. Details will be discussed and determined in the early part of the semester.
Exams	There are two take-home midterms, one halfway through the course, and one at the end of the term. Each exam will count for 15% of your grade.
Grading and Late Policy	Grading of homework assignments will be on a ten-point scale. Late assignments will be dropped 1.5 points for every two days late. That is, as soon as an assignment is late it will drop 1.5 points. You then have 48 hours to submit it before it drops another 1.5 points. No assignments will be accepted more than four days late. In addition, you each begin with a bank of five free delay days that will offset late penalties. These days will be allocated optimally at the end of the term to give you the best possible score. There is no need to indicate that you are using them. Note that the limitation of submitting no later than four days after the due date is unaffected by the use of delay days. This is an absolute limit. In addition, the impact of late submission and delay days will not be reflected in the grades you receive on individual assignments. These affects will be calculated only at the end of the term. It is your responsibility to keep track of how many late days you have used.
Honor Code Policy
	With regard to both pencil-and-paper and computer-based assignments we expect you to hold to the following standard in your work: you are free to discuss a problem with other students, and hash out the general framework of the solution, but the actual work handed in must be your own. You should not share code, or substantial aspects of solutions. (The team-based project is, obviously, and exception to this rule.)
Course Outline / Reading Assignments
	Part 0 Database Systems Ch. 1 Introduction. The structure of database systems. Jan. 19 Part 1 The Entity-Relationship Model Ch. 2 The Entity-Relationship data model as a modeling tool. Jan. 24 Part 2 The Relational Model: Theory and Reality Ch. 3, 4, 5 The relational model. Mapping ER diagrams to the relational model. Jan. 26 Relational algebra Jan. 31 Views and updates. RDB. Feb. 2 Domain relational calculus, Tuple relational calculus. Feb. 7 The database "standard": SQL. Feb. 9 A tuple-relational calculus query language: Quel. Feb. 14 Part 3 Relational Design Theory Ch. 15 (16, 17) Integrity constraints. Functional dependencies. Feb. 16 Decomposition: losslessness and dependency preservation. Feb. 21 Schema normal forms. Feb. 23 Part 4 Physical Data Organization Ch. 7, 8, 9, 10, 11 File organization. Feb. 28 Indexing. Mar. 1 B+ -trees. Mar. 6 Hashing. Mar. 8 Part 5 Query Optimization and Processing Ch. 12, 13, 14 Query optimization. Mar. 20 Join Processing Mar. 22 Part 6 Concurrent Transaction Processing Ch. 18, 19, 20 Transactions as units of recovery, stable store, logging, and checkpoints. Mar. 27 Concurrency control, serializability. Mar. 29 Locking protocols, Two-phase locking. Apr. 3 Timestamp protocols, deadlocks, rollback, and other issues. Apr. 5 Part 7 Distributed Databases Ch. 21 Introduction. Fragmentation and replication. Apr. 10 Distributed query processing. The Semijoin optimization. Apr. 12 Transaction processing. Two-phase commit. Voting procedures. Apr. 17 Part 8 Additional Topics Apr. 19, May 5, May 7