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:
- The basics of XML: data model, DTDs, XPath, XQuery, etc.
- The basics of automata theory: string and tree automata. Logic
background: FO and MSO.
- Formal model of XML documents: unranked trees.
- Automata for unranked trees. Logics for unranked trees;
connections between logic and automata; complexity of decision problems.
- DTDs: extended CFGs, connections with automata, extended DTDs,
automata and MSO.
- XPath: a fragment of FO, connections with temporal logics,
conditional XPath.
- Logics for querying XML, complexity of query evaluation (examples
may include ETL, monadic datalog, temporal logics).
- XML transformations and tree transducers.
- Streaming XML: models, expressiveness, complexity.
- XML constraints: keys, foreign keys, consistency.
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:
- Thomas Schwentick, Trees, Automata, and XML,
Invited Tutorial at PODS'04.
- Frank Neven, Automata, Logic, and XML.
Invited talk at CSL 2002.
- Nils Klarlund, Thomas Schwentick and Dan Suciu. XML: Model, Schemas, Types, Logics, and
Queries. In "Logics for Emerging Applications of Databases",
2003, Springer.
- Leonid Libkin, Logics for Unranked Trees: An Overview,
Invited talk at ICALP 2005.
- More references will be added.
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