News

• 1/9: Project proposals are due by Tuesday 1/17.
• 1/9: A list of suggested projects is available.

Class Description:

CMPS278 covers advanced research topics in the implementation of modern relational databases, with a clear focus on system-related issues. The covered topics include: query processing techniques for massive data sets, transaction management, locking protocols, advanced indexing techniques for relational and multi-dimensional data, query optimization and database statistics, database recovery, object-oriented databases, parallel and distributed database systems, and data mining. The course will also involve a term project with significant research and implementation components.

Enrolled students are expected to have a basic background in relational database systems. The official pre-requisite is CMPS180, or CMPS277, or equivalent.

Lecture times:

When: TTh, 2:00PM-3:45PM

Where: Cowell Acad 216

Instructor:

Name: Neoklis (Alkis) Polyzotis (alkis@cs.ucsc.edu)

Phone: x9-1304

Office: E2#353

Office Hours: T, 4:00-6:00PM

Text Book

M. Stonebraker, J.M.Hellerstein, "Readings in Database Systems", 4th edition, Morgan-Kaufmann.

Syllabus

Date	Topic	Paper(s)	Additional material
1/5	The Roots	M.M.Astrahan et al.,"System R: Relational Approach to Database Management" M.Stonebraker et al.,"The Design and Implementation of INGRES"	Wikipedia Entry for Ted Codd A tutorial in CODASYL 1995 SQL Reunion
1/10	Concurrency Control and Transaction Management	J. Gray et al., "Granularity of Locks and Degrees of Consistency in a Shared Data Base". H.T.Kung and J.T. Robinson, "On Optimistic Methods for Concurrency Control". P.L.Lehman and S.B.Yao, "Efficient Locking for Concurrent Operations on B-Trees".	Rakesh Agrawal, Michael J. Carey, Miron Livny, "Concurrency Control Performance Modeling: Alternatives and Implications". Rudolf Bayer, Mario Schkolnick, "Concurrency of Operations on B-Trees". Acta Inf. 9: 1-21 (1977).
1/12
1/17
1/19	Query Processing	L.D.Shapiro, "Join Processing in Database Systems with Large Main Memories". H.T.Chou and D.J.DeWitt, "An Evaluation of Buffer Management Strategies for Relational Database Systems".	G. Graefe, "Query evaluation techniques for large databases", ACM Comput. Surv. 25, 2 (Jun. 1993), 73-169.
1/24
1/26	Indexing	A.Guttman, "R-Trees: A Dynamic Index Structure for Spatial Searching".	J. M. Hellerstein, J. F. Naughton, A. Pfeffer, "Generalized Search Trees for Database Systems".
1/31	Query Optimization	P.G.Selinger et al., "Access Path Selection in a Relational Database Management System". Y.Ioannidis and Y.C.Kang, "Randomized Algorithms for Optimizing Large Join Queries", SIGMOD 1990. R. Avnur and J.M. Hellerstein, "Eddies: Continuously Adaptive Query Processing".	S. Chaudhuri, "An overview of query optimization in relational systems", In PODS 1998. A. Ghosh, J. Parikh, V. Sengar and J. Haritsa, "Plan Selection based on Query Clustering", Proc. of 28th Intl. Conf. on Very Large Data Bases (VLDB), August 2002. J.M. Hellerstein, "Optimization techniques for queries with expensive methods", ACM Trans. Database Syst. 23, 2 (Jun. 1998), 113-157. N. Kabra, D.J. DeWitt, "Efficient mid-query re-optimization of sub-optimal query execution plans", In ACM SIGMOD 1998.
2/2
2/7
2/9	MIDTERM
2/14	Data Statistics	V.Poosala et al., "Improved Histograms for Selectivity Estimation of Range Predicates", SIGMOD 1996.	Y. Matias, J. S. Vitter, M. Wang, Wavelet-based histograms for selectivity estimation , In ACM SIGMOD 1998. Y. Ioannidis, "The History of Histograms (abridged)" In VLDB 2003 (Ten Year Best Paper Award).
2/16	Database Recovery	P.L.Lehman and S.B.Yao, "Principles of Transaction-Oriented Database Recovery". C. Mohan et al.,"ARIES: A Transaction Recovery Method Supporting Fine-Granularity Locking and Partial Rollbacks".	C. fMohan, "Repeating History beyond ARIES", In VLDB 1999 (Ten Year Best Paper Award).
2/21
2/23	Distributed and Parallel Systems	C.Mohan et al., "Transaction Management in the R* Distributed Management System". D.J.DeWitt and J. Gray, "The Future of High Performance Database Systems". D.J.DeWitt et al., "The Gamma Database Machine Project".	Michael Stonebraker, Paul M. Aoki, Witold Litwin, Avi Pfeffer, Adam Sah, Jeff Sidell, Carl Staelin, Andrew Yu, "Mariposa: A Wide-Area Distributed Database System". The Paradise Team, "Paradise: a database system for GIS applications", In ACM SIGMOD 1995.
2/28
3/2	Data Analysis and Decision Support	J.Gray et al.,"Data Cube: A Relational Aggregation Operator Generalizing Group-By, Cross-Tab, and Sub-Totals". R.Agrawal and R.Srikant, "Fast Algorithms for Mining Association Rules". T. Zhang, R. Ramakrishnan, M. Livny, "BIRCH: An Efficient Data Clustering Method for Very Large Databases".	Surajit Chaudhuri, Umeshwar Dayal, "An Overview of Data Warehousing and OLAP Technology".
3/7
3/9	Extensible Systems	M. Stonebraker, "Inclusion of New Types in Relational Data Base Systems"	P. Seshadri et al., "The Case for Enhanced Abstract Data Types", In VLDB 1997.
3/14	New Paradigms of Data Management	S. Abiteboul, "Querying Semi-Structured Data". Donald Carney, Ugur Cetintemel, Mitch Cherniack, Christian Convey, Sangdon Lee, Greg Seidman, Michael Stonebraker, Nesime Tatbul, Stanley B. Zdonik, "Monitoring Streams - A New Class of Data Management Applications".
3/16	VLDB Deadline - No Class