Master of Science in Informatics at Grenoble

The course "Fundamentals of Data Processing and Distributed Knowledge" is a course on the foundations for processing tree-shaped and graph-shaped data given in the Master of Science in Informatics at Grenoble at the University Grenoble Alpes.

This course aims at introducing programming language foundations, theories, algorithms and tools for processing structured information in a robust and efficient manner. It consists in an introduction to relevant theoretical tools with applications to XML technologies and graph queries.

The theoretical part for tree-shaped data introduces tree grammars, finite tree automata, classical tree logics and a recent mu-calculus of finite trees, in connection to practical problems and technologies such as XPath/XQuery, DTD, schemas, etc. Applications are illustrated through on-the-fly validation of document streams, efficient query evaluation, static analysis of expressive queries in the presence of constraints, and static type-checking of programs manipulating labeled trees.

The theoretical part for graph-shaped data introduces the recursive relational algebra, with an application to recursive (C2RPQ) graph queries.

The course also aims at presenting important challenges, significant results, and open research issues. Pointers to teaching material can be found below.

Course Introduction	slides
Core XML: XML, DTD, XML Schema, XML Parsing	slides
Excursion (streaming DTD validation with SAX)	slides
XPath	slides
XQuery and Static Type-Checking	slides
Foundations of XML Types: An Introduction	slides
Tree Grammars	slides
Finite Tree Automata (inspired by W. Martens and T. Schwentick)	slides
First-Order Logic and Monadic Second-Order Logic	slides
Advanced Static Analysis with a Fixpoint Tree Logic	slides
Graph Query Optimization with the Recursive Relational Algebra	slides

A few sample questions and suggested answers of a course exam given at EPFL.

You may also want to have a look at some auxiliary reading material.