In this course we study the foundations of query- and schema languages for tree-structured and graph-structured data (such as XML, JSON, RDF, and graph databases).

Contents:

  • Finite automata on trees. Topics: regular tree languages, deterministic and non-deterministic automata, top-down and bottom-up automata, minimization, etc.
  • Schema languages (for XML and JSON). Topics: DTDs and EDTDs, complexity, expressiveness.
  • Tree patterns (as query language for XML, JSON, RDF, and graph databases). Topics: Evaluation and optimization.