Contexte
Le langage XPath s'impose comme une brique de base essentielle de la construction du web et des technologies XML. Ses qualités font de lui le langage de choix pour effectuer des requêtes sur des données semi-structurées. Il constitue le coeur des langages de transformation et de requêtes XML (XSLT, XQuery), permet la désignation de fragments de documents (XPointer, XLink) et l'expression de contraintes structurelles (XML Schema). Un des défis actuels consiste en la modélisation de ce langage et l'élaboration de ses fondements mathématiques, de façon à permettre le développement de compilateurs, d'analyseurs statiques et d'optimiseurs sur des bases solides et claires.
Au cours des derniers mois, dans l'équipe WAM, nous avons mis au point le premier solveur au monde capable de résoudre des problèmes d'analyse statique mettant en jeu des requêtes XPath. Le solveur permet de vérifier automatiquement des propriétés sur les arbres, comme la navigation sous contrainte de type (DTDs, XML Schemas...). Cette avancée repose sur la conception d'une nouvelle logique d'arbres, également élaborée dans le projet WAM [2].
Le solveur permet par exemple de déterminer automatiquement si deux requêtes XPath sont équivalentes pour une infinité de documents sur lequel elles peuvent être évaluées. Ceci est très utile pour l'optimisation de programmes: il devient en effet possible de substituer une requête par sa version optimisée dans un programme, sans risque, au moment de la compilation, afin d'améliorer les performances à l'exécution par exemple.
La connaissance d'un type de données (DTD, XML Schema...) peut permettre de déterminer statiquement les parties d'un document qui sont nécessaires à l'évaluation d'une requête, de celles qui ne le sont pas. Dans certains cas, de telles considérations peuvent permettre d'économiser le chargement en mémoire de plusieurs giga-octets de données structurées inutiles. Les économies de ressources ainsi réalisées peuvent rendre possible l'évaluation de requêtes qui n'étaient pas a priori envisageables.
Description du stage
L'objectif de ce stage est d'élaborer des techniques pour optimiser des requêtes XPath. Pour cela, il conviendra de concevoir un mécanisme (qui peut être un modèle, une sémantique, ou une heuristique) permettant de juger de l'optimalité d'une requête XPath dans un contexte d'évaluation particulier, ainsi qu'une technique pour transformer une requête de façon à atteindre le critère d'optimalité.
Cette transformation (ou "réécriture") peut par exemple chercher à minimiser le nombres d'étapes de navigation nécessaires pour parvenir à l'ensemble de noeuds résultat, ou encore minimiser le nombre de fois où un noeud est visité dans un document. Pour cela, la connaissance du type des structures XML (via une DTD ou schéma..) pourra jouer un rôle décisif.
Un résultat concret attendu est un optimiseur de requêtes XPath. Celui-ci pourra être implanté grâce aux outils dont nous disposons déjà (parseurs, compilateurs, et solveur logique). En particulier, le solveur logique que nous avons déjà élaboré permettra de prouver l'équivalence entre la requête initiale et sa version optimisée.
Ce stage offre l'opportunité de se familiariser avec l'essence des technologies XML. Il comporte une partie théorique et pratique. Il offre en outre un très bon positionnement pour une éventuelle poursuite en thèse.
Références
[1] Static Analysis of XML Programs, Pierre Genevès and Nabil Layaïda, (invited article) in ERCIM news number 72: "The Future Web", 2008, http://ercim-news.ercim.org/content/view/326/536/
[2] Efficient Static Analysis of XML Paths and Types, Pierre Genevès and Nabil Layaïda and Alan Schmitt, Proceedings of the ACM SIGPLAN Conference on Programming Language Design and Implementation (PLDI), 2007
[3] Type-based optimization for regular patterns, Michael Y. Levin, Benjamin C. Pierce, in Proc. of DBPL 2005