CS 811

Database Management Systems

Fall 1999

Abdullah Uz Tansel

Office 411, 360 Park Avenue South (Corner of 26^th Street), Office hours: Tu 1:00pm-2:25 pm, Th: 3:50pm-4:15pm, or by appointment.

Email: tansel@baruch.cuny.edu

Assignment I Solutions I (MS Word)

Assignment II

Assignment III

Assignment IV

Reading list Database Implementation Project

Overview

        The course focuses on the fundamentals of relational database management systems and the current developments in database theory and practice. The course aims at providing the foundations for practicing database technology and preparing students for research in database field. Thus, we will try to balance the practical and the theoretical aspects of the essential topics we will cover in the course. There will be assignments and a term project. The term project may involve the implementation of a database management system component or a survey of the current research in a database topic.

The students are expected to attend and participate in the lectures as well as reading relevant material listed below.

Prerequisites

Textbook

    Required:

 Database Management Systems,  R. Ramakrishnan,  McGraw-Hill, Second Edition, August 1999. I will follow this book closely with supporting material from the accompanying list of books and articles. -- Available (after Sept. 6) at Baruch College bookstore, in the basement of 360 Park Avenue South

    Other Relevant Books:

• Fundamentals of Database Systems, Third Edition, R. Elmasri, S. Navathe, Addison-Wesley. Comprehensive coverage and easy to read.
• Database : Principles, Programming and Performance, P. O'Neil, Morgan-Kaufman. Emphasis on commercial DBMSs and SQL.
• Database Systems : A Practical Approach to Design, Implementation, and Management, Second  Ed,   T. Connolly,  C. Begg, A. Strachan, Addison-Wesley.  A guide to how databases are used as tools in the world of IT.
• (WU) A First Course in Database Systems, J. Ullman, J. Widom, Prentice Hall, 1997.
  Written from the application programmer's point of view with detailed emphasis on data modeling.
• Database System Implementation, H. Garcia-Molina, J. Ullman, J. Widom, Prentice Hall, June 1999.
• Database System Concepts, Third Ed, A. Silberschatz, H. Korth, S. Sudarshan, McGraw-Hill. Very popular standard textbook.
• (U) Principles of Database and Knowledgebase Systems, J. D. Ullman, Academic Press, 1988. A classic on database theory.
• Object relational DBMS - The Next Great Wave, M. Stonebraker, Morgan Kaufmann, 1996.
• ODMG-3 Release 1.2, Morgan Kaufmann, 1988.
• Principles of Database Query Processing for Advanced Applications, C.T. Yu, and W. Meng, Morgan-Kaufmann, 1999.
• Query processing for Advanced Database Systems, J.C. Freytag, D. Maier, G. Vossen, Morgan-Kaufmann, 1994 (RES)
• Materialized Views, A. Gupta, I. S. Mumick, the MIT Press, 1999

• S. Chaudhuri, An Overview of Query Optimization in Relational Systems, ACM PODS 1998
• A. Guttman, R-Trees: A Dynamic Index Structure for Spatial Searching, in the Proceedings of ACM SIGMOD Conference, 1984.
• L. Shapiro, Join Processing in Database Systems with Large Main Memories, ACM Transactions on Database Systems, Vol. 11, No 3, pp: 239-264, 1986
• P. Selinger et al., Access Path Selection in a Relational Database Management System, in the Proceedings of ACM SIGMOD Conference, 1979.
• H-T. Chou and D. DeWitt, An Evaluation of Buffer Management Strategies for Relational Database Systems, in the Proceedings of the Conference on Very Large Databases, 1985
• C-Y. Chan, Y. Ioannidis, Bitmap Index Design and Evaluation, SIGMOD’98.
• G. Graefe, Query Evaluation Techniques for large databases, ACM Computing Surveys, 25; 2, June 1993.
• G. Graefe, On Optimizing an SQL-like nested Query, Kim, ACM TODS, Sept. 1982.
• Sudarshan et al, "On Index Selection Schemes for Nested Object Hierarchies", VLDB'94, pp. 331-342.

• Query processing in Object-Oriented Database Systems, M.T. Ozsu, J.A. Blakeley, Chapter 8 in Modern database Systems, Ed. W. Kim, Addison-Wesley, 1995.
• Kemper, A., Moerkotte, G., "Query Optimization in Object Bases", Chapter 3, Query Processing for Advanced Database Systems, Editors: Freytag, J.C., Maier, D., Vossen, G., 1994.
• Gardarin et al, "A Cost Model for Clustered Object-Oriented Databases", VLDB'95.
• Gardarin et al, "Cost-based Selection of Path Expression processing Algorithms in OO Databases", VLDB'96.
• Index Structures for Path Expressions, T. Milo and D. Suciu, ICDT, 1999.
• Query processing in Object-Oriented Database Systems,.T. Ozsu, J.A. Blakeley, Chapter 8 in Modern database Systems, Ed. W. Kim, Addison-Wesley, 1995.
• Kemper, A., Moerkotte, G., "Query Optimization in Object Bases", Chapter 3, Query Processing for Advanced Database Systems, Editors: Freytag, J.C., Maier, D., Vossen, G., 1994.
• Gardarin et al, "A Cost Model for Clustered Object-Oriented Databases", VLDB'95.
• Gardarin et al, "Cost-based Selection of Path Expression processing Algorithms in OO Databases", VLDB'96.
• Index Structures for Path Expressions, T. Milo and D. Suciu, ICDT, 1999.

• R. J. Miller, Using Schematically Heterogeneous Structures, ACM SIGMOD’98.
• SchemaSQL—A Language for Interoperability ..", VLDB’99.

• XML, Feb 98, http://www.w3.org/TR/REC-xml
• Abiteboul, S. et al, The Lorel Query Language for Semi-structured Data, 1998, available at http://pub-db.stanford.edu/publist.html
• J. McHugh, J. Widom, Query Optimization for XML, VLDB’99, available at http://pub-db.stanford.edu/publist.html (extended version).
• McHugh, J., Widom, J., Query Optimization for Semi-structured Data, 1999, available at http://pub-db.stanford.edu/publist.html.
• McHugh, J. et al, Indexing Semi-structured Data, 1999, available at http://pub-db.stanford.edu/publist.html.
• Abiteboul, S., Querying Semi-Structured Data, 1998, available at http://pub-db.stanford.edu/publist.html.
• Fernandez, M., Suciu, D., "Optimizing Regular Path Expressions Using Graph Schemas", IEEE ICDE’98.

• P.A. Bernstein and N. Goodman, Concurrency Control in Distributed Database Systems, ACM Computing Surveys, Vol. 13, No 2, p.p.: 185-222, 981.
• R. Bayer and M. Schkolnick, Concurrency of Operations on B-trees, Acta Informatica, Vol. 9, No 1, p.p.: 1-23. 1977.
• J. Gray et.al., Granularity of Locks and Degrees of Consistency in a Shared Database, In the proceedings of IFIP Working Conference on Modelling of Database Management Systems, 1977.
• M. Stonebraker, Operating System Support for Database Management, Communications of the ACM, Vol. 14, No 7, pp: 412 =418, 1981.
• M. Carey, D. DeWitt, and J. Naughton: The OO7 Benchmark, in the Proceedings of AACM SIGMOD Conference, 1993.

• S. Chaudhuri, U. Dayal, An Overview of Data Warehousing and OLAP Technology, ACM SIGMOD Record, Vol. 26, NO 1, March 1997.
• J. Widom, Research Problems in Data Warehousing, in the Proceedings of Conference on Information and Knowledge Management, Baltimore, MD1995.
• V. Harinarayan et al, Implementing Data Cubes Efficiently, 1999 in "Materialized Views", A. Gupta, I. S. Mumick, the MIT Press, 1999 (RES).
• S. Chaudhuri et al, Optimizing Queries with Materialized Views, Chapter 7 in Materialized Views, A. Gupta, I. S. Mumick, the MIT Press, 1999.
• J. A. Blakeley et al, Efficiently Updating Materialized Views, Chapter 13 in Materialized Views, A. Gupta, I. S. Mumick, the MIT Press, 1999.

• V. Ganti,…"Mining Very Large Databases", 1999 in IEEE Computer, Vol. 32, #8, Aug. 1999.
• J. Han,"Constrained-Based Multidimensional Data Mining, in IEEE Computer, Vol. 32, #8, Aug. 1999.
• S, Chakrabarti,…"Interactive Data Analysis: The Control Project"Mining the Web's Link Structure" in IEEE Computer, Vol. 32, #8, Aug. 1999
• R. Agrawal, T. Imelinski, A. Swami, Mining Association Rules Between Sets of Items in Large Datasets, in proceedings of ACM SIGMOD Conference, pp: 207 - 216, 1993.
• S. Sarawagi, et al, Integrating Association Rule Mining with Relational Database Systems: Alternatives and Implications, in proceedings of ACM SIGMOD Conference, p.p.: 343 - 354, 1998.
• V. Harinarayan, A. Rajaraman, J. D. Ullman, Implementing Data Cubes Effeciently, in proceedings of ACM SIGMOD Conference, pp: 205-216, 1996.

            All of the above material will be available on reserve. Most of the questions in the midterm and final exams will be drawn from the above material.

    Recommended for Project:

• C++: How to Program, Second Edition,  by Deitel & Deitel, Prentice Hall .
  This is a comprehensive C++ book with good coverage of templates and a chapter on the Standard Template Library. 
• STL for C++ Programmers, L. Ammeraal, John Wiley.
  This is a whole book on STL, not very thick and quite readable.

Course Components

• Course Project      -  30 %
• Assignments    -   20 %
• Midterm Exam       -   25 %
• Final Exam             -   25 %

Course Outline

Week