- Lec 01 – 24 Jan:
Background, Relational Model.
[AHV95] Chapters 1-3.
- Lec 02 – 26 Jan:
Expressing properties of graphs and strings
in first-order and second-order sentences.
Material from [AHV95] Chapter 2,
[L04] Chapter 1 and parts of Chapter 2.
Probs 01 (PDF)
- Lec 03 – 31 Jan:
Material on E-F Games and FO definability.
[L04] Chapters 2-3.
- Lec 04 – 2 Feb:
E-F Games and FO definability, continued.
[L04] Chapters 2-3.
- Lec 05 – 7 Feb:
E-F Games and FO definability, concluded.
[L04] Chapters 2-3.
Probs 02 (PDF)
- Lec 06 – 9 Feb:
E-F Games and FO definability, really concluded.
Query Language Perspectives, Conjunctive Queries.
[L04] Chapters 2-3.
[AHV95] Chapter 4.
- Lec 07 – 14 Feb:
Conjunctive Calculus, Union.
[AHV95] Chapter 4.
- Lec 08 – 16 Feb:
Equivalence Theorems,
Calculus with Negation.
[AHV95] Chapters 4-5.
Probs 03 (PDF)
- Lec 09 – 21 Feb:
Algebra and Calculus Equivalence Theorems.
[AHV95] thru Section 5.3, plus Section 6.3.
- Lec 10 – 23 Feb:
Undecidability Proofs.
[AHV95] Section 5.4-5.6.
- Lec 11 – 28 Feb:
Finishing off domain-independence,
Tableau Queries.
[AHV95] Ch 6.
- Lec 12 – 2 Mar:
Tableaux: inclusion, minimization,
an NP-completeness result.
[AHV95] Ch 6.
- Lec 13 – 7 Mar:
Acyclic Joins.
[AHV95] Ch 6 (concluded).
- 9 Mar - 11 Apr
A long hiatus while nearly everybody in the course
is away at conferences or working on paper submissions.
- Lec 14 – 13 Apr:
Starting XPath theory.
G. Gottlob, C. Koch and R. Pichler.
Efficient Algorithms for Processing XPath Queries.
TODS, June 2005.
(PDF).
- Lec 15 – 18 Apr:
Finishing discussion of Efficient Algorithms paper,
starting the Koch XPath survey paper.
M. Benedikt and C. Koch.
XPath Leashed.
Not for public distribution, but I am mailing postscript
to everybody involved.
