Graduate Center, PhD Program in Computer Science
Fall 2005
Dr. Abdullah Uz Tansel

CS 535 Database Management Systems II

Office: 11-238, Vertical Campus, Baruch College
Office Hours:
Email: mailto:tansel@baruch.cuny.edu

Course Description and Objective

The course focuses on the relational databases, relational query languages and their expressive power, and object relational systems. Logic as a data model and object oriented databases are introduced. The SQL language and its new standard (SQL3) are examined. Emerging database fields such as temporal, spatial, multimedia databases, and data warehousing and data mining are also covered.

This is an advanced course on databases focusing on data modeling and exploring expressive power of their query languages. The course also aims at guiding and encouraging students to do research on database fields such as temporal, spatial data modeling and query languages. Students are expected to prepare a research report on a topic selected by a student and approved by the instructor. The term project requires researching a topic and preparing a term paper on that topic. Research involves a literature survey to identify state of the art and the issues in the topic selected and a critical analysis of these issues with possible solution methods (if they can be devised).

The course will be conducted through lectures delivered by the instructor and paper presentations by the students. The instructor will lecture on the expressive power of (object) relational query languages, datalog, object oriented data modeling and query languages and SQL. Each student will present in class a paper selected from the list of papers provided below. All students are expected to read the paper to be presented and actively participate in class discussion during the paper presentations.

Prerequisites: A first course in DBMS

Textbook: No textbook required

Relevant Books:

• (GUW) Database Systems: The Complete Book, H. Garcia-Molina, J. Ullman, J. Widom, Prentice Hall, 2002.

• (U) Principles of Database and Knowledgebase Systems, J. D. Ullman, Academic Press, 1988. A classic on database theory.
•  Database Management Systems, Third edition, R. Ramakrishnan,  McGraw-Hill, Third Edition, 2004.
•  Fundamentals of Database Systems, Fourth Edition, R. Elmasri, S. Navathe, Addison-Wesley, 2004. Comprehensive coverage and easy to read.
• Database System Concepts, Third Ed, A. Silberschatz, H. Korth, S. Sudarshan, McGraw-Hill. Very popular standard textbook.
• Object relational DBMS - The Next Great Wave, M. Stonebraker, Morgan Kaufmann, 1996.
• ODMG-3 Release 1.2, Morgan Kaufmann, 1988.
• Data Mining Concepts and Techniques, Jiawei Han, M. Kamber, Morgan-Kaufmann, 1999.
• Data on the Web: From Relational to Semistructured Data and XML, S. Abiteboul, P. Buneman, D. Sucio, Morgan-Kaufmann, 1999.

Course outline (Subject to change, as of March 8, 2005)

   Week                                               Topic

1	Introduction, E/R Data Model (Read chapters 1 & 2 in GUW).
	Review of the relational data model relational algebra and calculus languages. Nested relations and extended algebra and calculus languages. (Read chapter 3.1 – 3. 3 in GUW and  4). Assignment of term project topics.
2	Domain independent formulas, expressive power of relational query languages. (Read Section 3.8 & 3.9).
3	Introduction to temporal databases, temporal data modeling and temporal query languages. (Read references 5, 3, 7, 32)
4	Expressive power of temporal query languages (Read reference 2).
5	Temporal extensions to SQL. Presentation of reference (12, 13, 14). Review of TSQL2. (Read 14, 15).
6, 7	Temporal aggregates. Presentation of reference (25). Temporal database design. Presentation of reference (8). SQL3 standard. SQL/Temporal. Presentation of reference (16).
8	More on temporal data modeling. Presentation of reference (10, 11). The concept of now. Presentation of reference (9).
	Introduction to object oriented databases, object oriented data model ODL. (Read Chapter 4 in GUW)
8,9	Object oriented query language OQL (Read Chapter 4 in GUW)
	Spatial data models and query languages. Presentation of reference (17, 31).
10	Spatial data models and query languages. Presentation of reference (18, 31).
11	Spatio-temporal databases. Presentation of reference (19).
12	Logic as a data model - Datalog (Read Chapter 3 in U)
13	Calendars and time series. Presentation of reference (21, 22, 23).
14	Information integration (Read Chapter 20 in GUW)
15	Concluding remarks

Grading

• Course Project               -   40 %
• Exams                            -   40%
• Presentation                    -   10 %
• Class participation           -  10 %

Work Submission Standards

Students are reminded of the Bilkent University guidelines that relate to the integrity of student behavior regarding submissions and assignments.

Bibliography

1. Tansel, A. U., Clifford, J., Gadia, S., Jajodia, S., Segev, A., Snodgrass, R. (Editors), Temporal Databases: Theory, Design and Implementation, Benjamin/Cummings Publishing Company, Redwood City, California, March 1993, 650 pages.

2. Tansel A., Tin, E., "Expressive Power of Temporal Relational Query Languages", IEEE Transactions on Knowledge and Data Engineering, Vol. 9, No. 1, Jan. 1997.

3. Tansel A. U., "Temporal Relational Data Model", IEEE Transactions on Knowledge and Data Engineering, Vol. 9, No. 3, May 1997.

4. Garnett, L., Tansel, A.U., "Equivalence of the Relational Algebra and Calculus Languages for Nested Relations", Journal of Computers and Mathematics with Applications, Vol. 23, No. 10, 1992, pp. 3-25.

5. Tansel, A. U., "Modeling Temporal Data", Journal of Information and Software Technology, Vol. 32, No. 8, 1990, pp. 514-520.

6. Tansel, A.U., Arkun, M.E. and Ozsoyoglu, G., "Time-By-Example Data- base Query Language", IEEE Transactions on Software Engineering, Vol. 15, No.4, 1989, pp. 464-478.

7. Tansel, A. U., "Adding Time Dimension to Relational Model and Extending Relational Algebra", Information Systems, Vol. 11, No. 4, 1986, pp. 343-355.

8. Wang, X., et al. "Logical Design for Temporal Databases with Multiple Time Granularities", ACM TODS, Vol. 22, No. 2, June 1997.

9. Clifford, J., at al., "On the Semantics of now in Databases", ACM TODS, Vol. 22, No. 2, June 1997.

10. Jensen, C., Soo, M., Snodgrass R., "Unification of Temporal Data Models", Technical Report, University of Arizona, 1992.

11. Jensen, C., Soo, M., Snodgrass R., "Extending Normal Forms to Temporal Relations", Technical Report, University of Arizona, 1992.

12. G. Bhargava, Gadia, S. K., "Relational Database Systems with Zero Information Loss", IEEE TKDE,
13. Gadia, S. K., "A Seamless Generic Extension of SQL for Querying Temporal Data", Technical Report, Iowa State University, 1982.
14. Snodgrass, R., et al., TSQL2, Kluwer Academic Publishers, 1996.
15. Lorentzos, N., Mitsopoulos, Y., "SQL Extensions for Interval Data", IEEE TKDE, Vol. 9, No. 3. May 1997, pp. 480 - 499.
16. Snodgrass, R., et al., "SQL/Temporal - A Standard Proposal, June 1997.
17. Guting, R. H., "An Introduction to Spatial Database Systems", VLDB Journal, Vol. 3, pp. 357-399.
18. Adam, N., Gangopadhay, A., Database Issues in Geographic Information Systems, Kluwer Academic Publishers, 1997.
19. Time in Geographic Information Systems,
20. Sukan, E., Ozsoyoglu, M., "Extended Set Operators for Complex Objects", Technical Report, Case Western Reserve University, 1995.
21. Chandra, R., Segev, A., Stonebraker, M., "Implementing Rules and Calendars in Next Generation Databases"
22. Lee, J. Y., Elmasri, R., "An Integral Temporal Data Model Incorporating Time Series Concept", Data & Knowledge Engineering, Vol. 24, 1998, pp.257 - 276.
23. Terenziani, P., "Integrating Calendar Dates and Qualitative Temporal Constraints in the Treatment of Periodic Events", IEEE TKDE, Vol. 9, No. 5, September 1997, pp. 763 - 783.
24. Georgakopoulos, D., Hornick, M., Sheth, A., "An Overview of Workflow Management: From Process Modeling to Workflow Automation Infrastructure", Distributed and Parallel Database, Vol. 3, 1995, pp. 119 0 153.
25. Snodgrass, R. T, Gomez, S.,McKenzie, E., "Aggregates in the Temporal Query Language TQuel", IEEE TKDE.Vol.5. Oct. 1993, pp: 826-842.

1.      26.  Betini, C., Jajodia, S., Wang, S.: Time Granularities in Databases, Data Mining and Temporal Reasoning, Springer Verlag, (1998).

2.      27.  Bohlen, M. H., Snodgrass, R. T., Soo, M. D.: Coalescing in Temporal Databases, in Proceedings of International Conference on Very Large Databases, (1996).

3.      28.  Chomicki, J.: Efficient Checking of Temporal Integrity Constraints Using Bounded History Encoding, ACM  Transactions on Database Systems, 20(2) (1995) 149-186.

4.      29.  Date, C. J., Darwen, H., Lorentzos, N.: Temporal Data and the Relational Data Model, Morgan Kaufmann Publishers, (2003).

5.      30.  Ozsoyoglu, Z. M., Yuan, L-Y.: A New Normal Form for Nested Relations, ACM Transactions on Database Systems 12(1), (1987).

31. Shekhar, S. Spatial Databases, Prentice Hall, 2003.
32. Tansel, Abdullah Uz, On handling time-varying data in the relational data model. Information & Software Technology 46(2): 119-126 (2004)