XML access modules : towards physical data independence in XML databases
Institution:
Paris 11Disciplines:
Abstract EN:
The purpose of this thesis is to design a framework for achieving the goal of physical data independence in XML databases. We first propose the XML Access Modules - a rich tree pattern language featuring multiple returned nodes, nesting, structural identifiers and optional nodes, and we show how it can be used to uniformly describe a large set of XML storage schemes, indices and materialized views. A second part of this thesis focuses on the problem of XQuery rewriting using XML Access Modules. As a first step of our rewriting approach we present an algorithm to extract XML Access Modules patterns from XQuery and we show that the patterns we identify are strictly larger than in previous works, and in particular may span over nested XQuery blocks. We characterize the complexity of tree pattern containment (which is a key subproblem of rewriting) and rewriting itself, under the constraints expressed by a structural summary, whose enhanced form also entails integrity constraints. We also show how to exploit the structural identifiers from the view definitions in order to enhance the rewriting opportunities.
Abstract FR:
Nous étudions dans cette thèse le problème de l'indépendance physique des données dans les bases de données XML. Dans une première partie de cette thèse nous proposons les modules d'accès XML (XML Access Modules ou XAMs) - un langage de motifs d'arbre conçu pour exprimer un grand sous-ensemble de XQuery, et enrichi avec des noeuds optionnels (permettant de capturer des motifs qui couvrent plusieurs requêtes imbriquées) et des identiants structurels (qui augmentent les possibilités de réécriture). Nous démontrons que ce langage des vues peut être utilise pour décrire uniformément un grand nombre de schémas de stockage, d'index et de vues matérialisées. Dans une deuxième partie de cette thèse nous étudions le problème de la réécriture des requêtes XQuery à travers des vues exprimées par des modules d'accès XML. Dans un premier temps, nous présentons un algorithme capable d'extraire des motifs XAM à partir des requêtes XQuery et nous démontrons l'importance d'utiliser des vues qui peuvent enjamber plusieurs blocs XQuery imbriqués. Par la suite, nous étudions le problème de la réécriture des requêtes en utilisant des vues materialisées, où la requête et les vues sont décrites par des vues XAM. Nous caractérisons la complexité de l'inclusion de motifs d'arbre et de la réécriture des requêtes sous les contraintes exprimées par des résumés structurels, dont une forme augmentée permettra également d'exprimer des contraintes d'intégrité.