CS556: Foundational
Aspects of Database Systems
Tentative Schedule
As we are in the process of developing this course, the schedule might
change slightly later as appropriate.
Lecture 1, Jan 20, 2009: Math basics and database basics
(Chapters 1, 2.1, 3, 6.1)
Handout on lecture pdf
Lecture 2, Jan 27, 2009: Logic Based Database Languages
(Chapters 4, 5.1, 5.2, 12.1, 15.2)
Handout on lecture pdf
Handout on how to use XSB pdf
Lecture 3, Feb 3, 2009: Semantics for Datalog queries
(Chapters 12.2, 12.3, 13.1)
Handout on lecture pdf
Lecture 4, Feb 10, 2009: Execution Techniques for Recursive Programs
(Chapters 12.4, 13.1, 13.2, 13.3)
Handout on lecture pdf
Lecture 5, Feb 17, 2009: Query Optimization: Minimizing Joins in Conjunctive
Queries (Chapters 6.2, 8, 9.4).
Handout on Lecture pdf
Some additional papers include:
- Ashok K. Chandra and Philip
M. Merlin, Optimal Implementation of Conjunctive Queries in Relational
Databases, ACM STOC, 1977 - this showed that for a conjunctive
query w/o constraints, there is a unique minimal query.
- A. V. Aho, Y. Sagiv and J. D. Ullman,
Efficient optimization of a class of relational expressions, TODS,
December 1979 - this considers FDs, and used the tableau approach.
- M. Mani, S. Wang, D. J. Dougherty,
E. A. Rundensteiner, Join Minimization in XML-to-SQL Translation:
An Algebraic Approach, SIGMOD Record, March 2006 - this studies
join minimization under bag semantics
Week 6: Decorrelating Nested Queries
We will study decorrelating queries based on IBM's QGM (Query Graph
Model). Two optimizations are performed (a) magic techniques are
applied to ensure that the inner subquery is executed only when needed
(b) we try to remove any nested iteration implied by correlation,
and replace it with join, so that more optimizations such as join
reordering, based on available indexes are possible.
Handout on lecture pdf
Powerpoint describing decorrelation
ppt
The relevant papers include:
- I. S. Mumick, S. J. Finkelstein,
H. Pirahesh, R. Ramakrishnan, Magic is Relevant, SIGMOD, 1990 - this
work is a preliminary attempt at realizing that magic set techniques
are applicable even to SQL systems.
- H. Pirahesh, J. M. Hellerstein,
W. Hasan, Extensible/Rule Based Query Rewrite Optimization in Starburst,
SIGMOD, 1992 - this work describes IBM's QGM representation of a
query, rewrite rules that preserve bag semantics are described.
- P. Seshadri, H. Pirahesh,
and T. Y. Cliff Leung, Complex Query Decorrelation, ICDE, 1996 -
this work describes how to use magic techniques for subqueries, as
well as eliminate correlation, if possible.
Week 7 - 8: Introduction to Data Integration
Handout 1 on lecture pdf
Handout 2 on lecture pdf
The relevant papers include:
Week 9: View Maintenance Algorithms
Handout on lecture pdf
Week 10 - 14: Presentations by Students on select topics, final exam.