CSC2428    TOPICS IN DATABASES: FOUNDATIONS OF XML  FALL 2005



We meet in BA1200, 3-5pm on Fridays   starting 28 October we meet in Pratt 378
   But: no class on 30 September, 7 October
        on 14 and 21 October class will run 3-6pm
Instructor: L. Libkin
Syllabus

Requirements: class attendance, taking notes, presentation, small-scale research project (for A+ only)

             
Topics:

Possible topics for student presentations

typechecking of XML transformations, complexity of XQuery evaluation, automata with counting, tree-walking automata, compressed trees, conjunctive queries for XML, data extraction on the web.

Suggested reading:

Background  - Logic and Automata

Background: XML Tutorial

Surveys:



LECTURES:

Lecture 1 slides (16 September)       .tex template for scribes
Lecture 2
Lecture 3
Lecture 4 (nothing there yet)
Lecture 5: based on the MSO section of my ICALP 2005 survey. Outline. See also the slides of the talk.
Lecture 6
Lecture 7 (nothing there yet)
Lecture 8


Student presentations


Typechecking and pebble automata (Alvin Chin) pdf file
XML constraints (Pablo Barcelo) pdf file
Tree-walking automata (Anthony Widjaja To) pdf file
Xpath containment (Zheng Zhang) pdf file