Pierre Genevès

Research Director, Computer Science

Data-centric programming, data management, data science, analytics

Master of Science in Informatics at Grenoble, Option Artificial Intelligence and the Web

The course "Fundamentals of Data Processing and Distributed Knowledge - Foundations for Processing Trees" is a course on the foundations for processing tree-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, algorithms and tools for processing tree-structured information, and for the analysis of queries and programs that manipulate trees. It consists in an introduction to relevant theoretical tools with an application to NoSQL and XML technologies in particular. The theoretical part 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 course also aims at presenting challenges, important results, and open theoretical issues in the area of NoSQL programming. 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 for XML/XPath 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.