Tentative schedule

Week 1: Orientation and Review of the Relational Model and Queries

• Topics:
  Relational Model: review of standard results and possible extensions: complex objects, recursion, interpreted structures.
  a few transparencies on this topics
• Reading (optional):
  Foundations of Databases (Abiteboul, Hull, and Vianu, Addison-Welsley)

Week 2-3: Constraint representation and Spatial Data

• Topics:
  Constraint representation, queries, query evaluation and constraint algebras, applications (e.g., to spatial databases and GIS), recursion and termination, aggregation.
• Reading:
  Paris C. Kanellakis, Gabriel M. Kuper, Peter Z. Revesz: Constraint Query Languages. JCSS 51(1): 26-52 (1995) (do read at least this)
  Michael Benedikt and Leonid Libkin: Relational queries over interpreted structures. Journal of the ACM, 47 (2000), to appear.
  Stephane Grumbach, Jianwen Su: Queries with Arithmetical Constraints. TCS 173(1): 151-181 (1997)
  Michael Benedikt, Leonid Libkin: Safe Constraint Queries. SIAM J. Comput. 29(5): 1652-1682 (2000)
  Michael Benedikt, Leonid Libkin: Exact and Approximate Aggregation in Constraint Query Languages. PODS 1999: 102-113
  

Week 4-5: Historical Data

• Topics:
  Abstract models, compact representation in secondary storage, query languages (temporal logic vs. first-order logic), practical proposals (points vs. intervals), efficient query evaluation, histories of relational databases.
• Reading:
  Jan Chomicki and David Toman. Temporal Logic in Information Systems In Logics for Databases and Information Systems, Kluwer Academic publishers, 1998, 31-70., SLIDES
  David Toman. Point-based Temporal Extensions of SQL and their Efficient Implementation, In Temporal Databases: Research and Practice LNCS 1399, 1998, 211-236.

Week 6-7: Integrity Constraints and Query Processing

• Topics:
  Semantic Query optimization, Access patterns, Plan generation, Information Integration and XML.
• Reading:
  Grant and I are working on it

Week 8-9: Incomplete and/or Inconsistent Databases

• Topics:
  Incompleteness (and how to deal with it), Inconsistency and query answering.
• Reading:
  Tomasz Imielinski, Witold Lipski Jr. Incomplete Information in Relational Databases. JACM 31(4): 761-791 (1984),
  Grahne, Mendelzon, and Reiter. On Semantics of Belief Revision Systems. KKR-TR-95-1, University of Toronto, 1995.,
  Marcelo Arenas, Leopoldo E. Bertossi, Jan Chomicki. Consistent Query Answers in Inconsistent Databases. PODS 1999: 68-79,
  Marcelo Arenas, Leopoldo E. Bertossi, Jan Chomicki. Scalar aggregation in FD-inconsistent databases. ICDT 2001,
  Peter Revesz. Model-Theoretic Minimal Change Operators for Constraint Databases. ICDT 1997.,
  Peter Revesz. On the Semantics of Arbitration. International Journal of Algebra and Computation, vol. 7, no. 2, pp. 133-160, 1997.,
  

Week 10-12: Project presentations

• 11/20:
  • Ivan Bowman: Query Rewrite Optimizations for Temporal Queries
  • Lubomir Stanchev: Bags and C-tables
• 11/27:
  • Yan Wang:
  • Ningyan Zhong: Constraint Extension of the XSB System

Slack:

• Approximate query answering
• Nested, complex-object, and object-oriented approaches
• Description logics for query optimization
• Managing change in databases, logics of change