General Class Information
- Lecture times and Location:
- MW 5.00 pm to 6.45 pm, Stevenson 213
- Instructor:
- Name: Wang-Chiew
Tan
- Office: BE 359A
- Instructor Office Hours:
- MW 3.30 pm to 4.30 pm
Prerequisites: CMPS180 or mathematical maturity
Main Reference:
Foundations of Databases
By S. Abiteboul, R. Hull, and V. Vianu
Syllabus:
- History, Background
- Conjunctive Queries: Rule-Based CQ, Conjunctive Calculus, Tableau Queries
- Optimizing Conjunctive Queries
- under set semantics
- under bag semantics
- with built-in subgoals
- with union
- Functional Dependencies, Multivalued Dependencies, Join Dependencies
- Logical Implication and Axiomatization
- Normal Forms
- The Chase Technique
- Chasing with Embedded Dependencies
- Query Optimization and Logical Implication via Chasing
- Datalog
- Model-Theoretic, Fixpoint, Proof-Theoretic Semantics
- Magic Set Rewriting
Supplementary Readings:
- Principles of Database and Knowledge-Base Systems. Vol. I and II.
By Ullman. You may find some relevant chapters here.
- Optimal Implementation of Conjunctive Queries in Relational Data Bases.
By Chandra and Merlin. STOC 77.
- Optimization of Real Conjunctive Queries.
By Chaudhuri and Vardi. PODS 93.
- The Theory of Data Dependencies: A Survey.
By Fagin and Vardi.
Proceedings of Symposia in Applied Mathematics, American Mathematical Society, 1986.
- A Proof Procedure for Data Dependencies.
By Beeri and Vardi. JACM 84.
Homeworks:
Handouts/Resources:
Academic Integrity:
No form of academic dishonesty will be tolerated in this class. More information can be found here.
|
