Dependencies between lecture topics
The web has been constantly evolving from a distributed hypertext system to a very large information processing machine. As fast as it is, this evolution is grounded on theoretical principles borrowing to several fields of computer science such as programming languages, data bases, structured documentation, logic and artificial intelligence. The smooth operation of the past and future web at a large scale is relying on these foundations. The goal of this course is to present them, the problem that they solve as those that they uncover. It considers two successive milestones of this evolution: XML and the semantic web.
The first part introduces the foundations of XML technologies: the XML language for document markup, DTDs as a type system for XML documents, XML query languages (XPath and XQuery) and XML transformation language XSLT. We will consider the major results obtained on each of these languages as well as the open questions. Then we introduce the challenges raised by these technologies to theoretica computer science. This covers formal methods used for grounding these technologies (tree automata, tree logics, their algorithms and complexity) as well as their application to XML query typing and static analysis of XML transformation languages.
The second part takes advantage of the XML structure to introduce the semantics of knowledge representation on the web. The semantic web extends the web with richer and more precise information because it is expressed in a formal language using a vocabulary defined in an ontology (a structured vocabulary of concepts and properties defined in a logic). Ontologies are used for describing web resource content and reasoning about these resources formally. We introduce the semantic web languages (RDF, RDFS, OWL) and show their relations with knowledge representation formalisms (conceptual graphs, description logics) and XML. This provides the tools for reasoning with ontologies and, in particular, to evaluate queries. However, the distributed nature of the web leads to heterogeneous ontologies which must be matched before using them. We show how to match ontologies and how to semantically interpret the relations between ontologies. Finally, this is applied to network of peers using knowledge together.
Lectures are on Wednesday from 14h00 to 17h15.
| Date | Title | Room | Lecturer |
| 28/9 | Core XML (XML, DTD, XML Schema) | H104 | PG |
| 5/10 | Programming with XML (DOM, SAX, XPath, XSLT) | CNAM 128 | PG |
| 19/10 | Foundations of XML types (tree grammars, tree automata) | H104 | PG |
| 21/10 (9h45-12h45) | A taste of research: introduction to some grand challenges | H202 | PG |
| 9/11 | Tree Logics (FO, MSO, μ-calculus) | CNAM132 | PG |
| 23/11 | Wrap-up and questions | D117 | PG |
| 25/11 (9h45-12h45) | Mid-term exam (90mn) | H203 | PG |
| 30/11 | Semantic web languages (Data: URI, RDF, closure, interpolation lemma) | H104 | JE |
| 7/12 | Semantic web languages (Ontologies: RDFS and OWL) | H104 | JE |
| 15/12 (14-17h) | Querying RDF (SPARQL) | H104 | JE |
| 4/1 | Querying data though ontologies (NSPARQL, PSPARQL, DL-Lite) | H104 | JE |
| 11/1 | Alignment semantics and networked ontologies | H104 | JE |
| 19/1 (9h45-12h45) | Semantic peer-to-peer systems | H101 | JE |
| 25/1 (9h-10h30) | Final exam (90mn) | H206 | JE |
The second part of the course is now collected into a single Lecture notes volume. These notes are always evolving so, avoid printing them until before the exams. It is easier to download (and update) it and browse through the PDF. It is divided in three parts correponding to the main sessions.
In previous years, we had 3h exams at the end of the course. Starting in 2010-2011, we have two exams. This aims at being sure that the students know what is expected from them. In addition here are some past exams.
Here are some questions of an exam proposed at EPFL in 2009 and their corrections (in English) for the XML part only.
Here is the exam of 2008-2009 (in French) and its correction (in English) for the semantic web part only.
Here is the exam of 2009-2010 (in French or English) and its correction (in English) for the semantic web part only.
Here is the exam of 2010-2011 (in French or English) and its correction (in English) for the semantic web part only.
Le web est en constante évolution d'un système hypertexte distribué à une gigantesque machine de traitement de l'information. Pour rapide qu'elle soit, cette évolution est basée sur des principes théoriques à la croisée de différents domaines de l'informatique comme les langages de programmation, les bases de données, les documents structurés, la logique et l'intelligence artificielle. L'application systématique de ces fondements garantit le fonctionnement du web, passé et futur, à une large échelle. Le but du cours est de présenter ces fondements, les problèmes qu'ils résolvent et ceux qu'ils posent. Le cours considère deux développements majeurs de cette évolution: XML et le web sémantique.
La première partie du cours introduit l'essence des technologies XML: le langage XML de balisage descriptif de documents, le langage DTD de typage de documents XML, les langages de requêtes XPath et XQuery et de transformation XSLT, tout en récapitulant les résultats majeurs obtenus sur chacun d'entre eux, et les questions demeurant ouvertes. On introduit ensuite les défis en informatique théorique qui sont posés par l'essor de ces technologies et l'élaboration de leurs fondements. Les méthodes formelles utilisées pour construire ces fondements généraux sont ensuite présentées (automates d'arbres, logiques d'arbres, algorithmes et complexité), ainsi que leur application pour le typage des langages de requêtes sur XML et le contrôle statique de type pour les langages de transformation de documents XML.
La deuxième partie prolonge la première en s'appuyant sur la structure introduite avec XML et en y associant la sémantique décrite dans différents langages (RDF, RDFS et OWL) qui se fondent sur des langages de représentation de connaissances (graphes conceptuels, logique de description). Le web sémantique permet d'offrir sur le web une information plus précise car exprimée dans un langage formel non ambigu et utilisant un vocabulaire défini dans une ontologie. Une ontologie est un vocabulaire structuré de noms de concepts et de propriétés définis précisément dans une logique. Elles servent de vocabulaire pivot entre les ressources du web qui utilisent les termes d'ontologies existantes pour décrire leur contenu. Elles permettent donc l'exploitation de l'information qu'elles décrivent en utilisant des techniques d'inférence, mises en oeuvre, entre autre, lors de l'évaluation de requêtes. L'aspect distribué du web introduit cependant la nécessité de mettre en correspondance ces ontologies mais permet, en contrepartie d'exploiter automatiquement des sources d'information indépendantes. Nous montrons comment les fondements sémantiques et algorithmiques des langages permettent le raisonnement distribué sur le web sémantique.