CS 386d Database Systems Spring 2014
	Instructor	Prof. Don Batory	batory@cs.utexas.edu
	TA	Akanksha Bansal	akankshabansal90@gmail.com
	Office Hours	Batory	TBD
		Bansal	1-3pm Wednesday, GDC 3.718F
	Room	GDC 4.304
	Time	9:30-11:00 Tuesday, Thursday
	Unique#	53993
	Ground Rules	Rules of Conduct and Academic Honesty
	Your Grades	TDB
	Final Exam	to be announced

This is a graduate-level introduction to the principles of relational database systems. We review and explain fundamental ideas and algorithms that are used in the construction of centralized DBMSs, distributed DBMSs, and database machines. Topics to be covered include:  query processing and optimization, database machines, object-oriented databases, concurrency control and recovery. Recent directions in database research are also surveyed.

Course Prerequisites

All students must have taken undergraduate database or its equivalent.

Lecture Notes, Texts, and Class Lectures

Notes for each lecture will be posted immediately after a lecture. Class lectures are supplemented by papers. Both are available via hyperlinks in the course outline below.  Students are responsible for reading these papers.  Remember: DO NOT PRINT THESE PAPERS ON CS PRINTERS!

• An excellent reference for concurrency control and recovery is by  Bernstein, Hadzilacos, & Goodman, Concurrency Control and Recovery.
• Additional postings on lecture notes, homework assignments, and software will be made available through this web page as they become available.

Presentations

The last class periods of the semester are devoted to student group presentations. These presentations will survey recent results presented in major database conferences. Group lectures will be critiqued prior to the actual presentation to enhance quality and content.  Topics for presentation can be chosen from any recent database conference, among them are:

• ACM SIGMOD
• Very Large Database Conference

Programming Projects and Homework

A series of 4 programming projects is given in this course.  The first project will refresh your memory on SQL and your use of DBMSs; you will build in the 2nd-4th an inverted file system using Berkeley DB (which is a file management system written in Java). An award (of no particular consequence) will be given to the judged-fastest entry.

• Project Submission.  Submitting homework or program assignment (HP): create a pdf/zip file <yourname>.pdf/zip , and run on a linux box:
  

where HP is a designator H1,H2, ... for homeworks and P1,P2... for programs.

• Verify Submission. To check if the submission was successful, use:
  

> turnin -- list bansal cs386_HP

• Retrieve Submission. To download your submission, use:
  

> turnin -- verify bansal cs386_HP

Evaluation

Final grades will be determined approximately by the following scheme:

1. Your accumulative project grade will determine the maximum final grade for the course.  Ex: if you get a "B" average across all of your projects, your final grade will be no greater than a "B".
2. Final counts 40%; midterm counts 35%; classroom participation 10%; and class presentation counts 15%.
   

Homework grades and class participation is used to decide borderline cases for final grades.

If you have difficulty meeting the requirements of this course, fail to hand in an assignment, or miss an exam because of extenuating circumstances, please advise the instructor in writing (not email) at the earliest possible date so that your situation can be discussed. If you encounter an unexpected medical or family emergency or a random act of Nature that causes you to miss the due date for homework or miss a quiz or exam, you must present suitable documentation in writing (not email) to the instructor before special consideration will be given. A file of all written correspondence will be kept by the instructor and decisions regarding them will be made at the end of the semester.

Numbers in [brackets] indicates the estimated number of lectures on a topic. The number indicated is a lower-bound, as there will be class room discussions to work on problems and review of homework assignments. Papers that are listed below are required readings and are accessible via a web link.

Topic [# of lectures + days of discussion]	Assignment
Query Processing [6] basic concepts in centralized and distributed query optimization [3] Chaudhuri, "An Overview of Query Optimization in Relational Systems" Selinger, et al., "Access Path Selection in a Relational Database Management System" Mackert and Lohman, "R* Optimizer Validation and Performance Evaluation for Distributed Queries" query processing and optimization in database machines [2] Nyberg, Barclay, Cvetanovic, Gray, and Lomet, "AlphaSort: A Cache-Sensitive Parallel External Sort" DeWitt, et. al., "The Gamma Database Machine Project" object-oriented query optimization [1] Hellerstein, "Predicate Migration: Optimizing Queries with Expensive Predicates"	Complete Course Survey Due Fri Jan 17th 10pm P1: SQL Refresher Due Wed, Jan 22, 12noon H1: Query Optimization #1 Due Tues, Jan 21, 12noon H2: Query Optimization #2 Due Tues, Jan 28, 12noon P2: MDB Data Definition Language and Database Loading Due Wed, Feb 5, 12noon
Data Strorage, Data Warehouses, Database Optimization [3+1] spatial file structures and join algorithms [1] Guttman, "R-Trees: A Dynamic Index Structure for Spatial Searching" Hjaltason and Samet, "Incremental Distance Join Algorithms for Spatial Databases" data warehouses and data cubes [1] Gray, et al., "Data Cube: A Relational Aggregation Operator Generalizing Group-by, Cross-Tab, and Sub-Totals" Zhao, et al., "Simultaneous Optimization and Evaluation of Multiple Dimensional Queries" Gray video, "The Revolution in Database Architecture" [1] Gray, "The Revolution in Database Architecture" (optional) automatic database tuning [1] Zilio, et al. "DB2 Design Advisor: Integrated Automatic Physical Database Design"	H3: R-Trees, Cubes and Group Assignments Due TBD P3: MDB Data Manipulation Language and Query Processing Due Wed, Feb 26, 12noon Collect into Groups for Presentation and Select Presentation Topic
Midterm  [1]
Concurrency Control [7] basic concepts of concurrency control and recovery [1] Bernstein chapter on "Serializability Theory" two-phase locking, phantoms, and multigranularity locking [2] Mohan, "Interactions Between Query Optimization and Concurrency Control" Bernstein chapter on "Two Phase Locking" degrees of consistency [1] Gray, et al. "Granularity of Locks and Degrees of Consistency in a Shared Data Base" Batory, "Degrees of Consistency Notes" B+ tree locking protocols [1] Lehman and Yao, "Efficient Locking for Concurrent Operations on B-Trees" key range locking and distributed concurrency control [1] Mohan, "ARIES/KVL: A Key-Value Locking Method for Concurrency Control of Multiaction Transactions Operating on B-Tree Indices" non-locking protocols [1] H.T. Kung and J.T. Robinson, "On Optimistic Methods for Concurrency Control"	H4: CC & R Basics Due TBD H5: Multi Granularity Locking Due TBD H6: Pulling It All Together Due TBD P4: MDB Query Optimization Due Wed, March 26, 12noon
Recovery [3+1] basic concepts and operation logging [2] Haerder and Reuter, "Principles of Transaction-Oriented Database Recovery" Mohan, et al., "ARIES: A Transaction Recovery Method Supporting Fine-Granularity Locking and Partial Rollbacks Using Write-Ahead Logging" recovery in distributed databases [1] Mohan, Lindsay, and Obermarck, "Transaction Management in the R* Distributed Database Management System" (optional) enterprise java beans [1]
Current Trends in Database Research [6]	Group Presentations
Course Recap [1]