Les évolutions technologiques ont consacré l'émergence des services web et du stockage des données en ligne, en complément des bases de données traditionnelles. Ces évolutions facilitent l'accès aux données, mais en contrepartie soulèvent de nouvelles problématiques de sécurité. La mise en œuvre de politiques de contrôle d'accès appropriées est une des approches permettant de réduire ces risques. Nous étudions ici les politiques de contrôle d'accès au niveau d'un document XML, politiques que nous modélisons par des vues de sécurité XML (non matérialisées) à l'instar de Fan et al. Ces vues peuvent être représentées facilement par des alignements d'arbres grâce à l'absence d'opérateurs arithmétiques ou de restructuration. Notre objectif est par conséquent d'examiner comment manipuler efficacement ce type de vues, à l'aide des méthodes formelles, et plus particulièrement des techniques de réécriture de requêtes et la théorie des automates d'arbres. Trois directions principales ont orienté nos recherches: nous avons tout d'abord élaboré des algorithmes pour évaluer l'expressivité d'une vue, en fonction des requêtes qui peuvent être exprimées à travers cette vue. Il s'avère que l'on ne peut décider en général si une vue permet d'exprimer une requête particulière, mais cela devient possible lorsque la vue satisfait des hypothèses générales. En second lieu, nous avons considéré les problèmes soulevés par la mises à jour du document à travers une vue. Enfin, nous proposons des solutions pour construire automatiquement un schéma de la vue. En particulier, nous présentons différentes techniques pour représenter de façon approchée l'ensemble des documents au moyen d'une DTD. / The evolution of web technologies and social trends fostered a shift from traditional enterprise databases to web services and online data. While making data more readily available to users, this evolution also raises additional security concerns regarding the privacy of users and more generally the disclosure of sensitive information. The implementation of appropriate access control models is one of the approaches to mitigate the threat. We investigate an access control model based on (non-materialized) XML views, as presented among others by Fan et al. The simplicity of such views, and in particular the absence of arithmetic features and restructuring, facilitates their modelization with tree alignments. Our objective is therefore to investigate how to manipulate efficiently such views, using formal methods, and especially query rewriting and tree automata. Our research follows essentially three directions: we first develop new algorithms to assess the expressivity of views, in terms of determinacy, query rewriting and certain answers. We show that those problems, although undecidable in our most general setting, can be decided under reasonable restrictions. Then we address the problem of handling updates in the security view framework. And last, we investigate the classical issues raised by schemata, focusing on the specific "determinism'' requirements of DTDs and XML Schemata. In particular, we survey some techniques to approximate the set of all possible view documents with a DTD, and we provide new algorithms to check if the content models of a DTD are deterministic.

Dans cette thèse, nous proposons la transposition de la notion de scalabilité des média, telle que définie par les codages hiérarchiques, aux scènes multimédia en charge de l'organisation spatiale et temporelle de la présentation interactive des différents média d'un document ou d'un service. Ainsi, une scène initiale est progressivement enrichie par des transformations successives, appelées mises à jour d'adaptation, de façon à aboutir à une présentation attractive et conforme à l'environnement d'usage. Notre approche, appelée Scalable MSTI, s'articule autour de trois axes de scalabilité qui séparent les Média et les propriétés Spatiales, Temporelles et Interactives d'une scène multimédia. Chacun de ces axes est constitué de couches de scalabilité contenant des mises à jour d'adaptation qui sont hiérarchisées selon une relation d'ordre définie par des paramètres d'adaptation choisis par l'éditeur en fonction des environnements d'usage envisagés. L'ensemble des présentations alternatives disponibles par scalabilité de scène est représenté sous la forme d'un graphe d'adaptation dans lequel une prise de décision constitue la sélection d'un parcours le long d'un chemin d'adaptation. La scalabilité de scène multimédia a été appliquée au domaine de la radio numérique au travers de la réception progressive de services multimédia. En outre, les capacités d'adaptation des services multimédia scalables de radio permettront, par exemple, l'exploitation de la largeur d'écran étendue de certains récepteurs ou encore une meilleure intégration des directives de sécurité routière en situation de conduite concernant les animations

Nous nous intéressons par le problème de la sémantique des mises à jour et de la cohérence des bases de données dans différents contextes comme les documents XML et les services web. En effet, des difficultés particulières sont à prévoir lors de la mise à jour d'une base ayant des contraintes à respecter, car, des données originalement cohérentes par rapport aux contraintes peuvent devenir incohérentes suite aux mises à jour. Dans une première partie de notre travail, nous considérons la mise à jour et le maintien de la cohérence d'une base de données XML par rapport au type (ou schéma) ainsi que par rapport aux contraintes d'intégrité. Nous abordons ce problème de différentes manières. Tout d'abord, nous proposons une procédure de validation incrémentale par rapport aux contraintes, évitant de revalider les parties du document qui n'ont pas été touchées par les mises à jour. Cette approche traite aussi bien le cas des contraintes de schéma que le cas des contraintes d'intégrité. Dans ce cadre, les listes de mises à jour qui violent la validité sont rejetées. Quand la validation incrémentale échoue, c'est-à-dire, quand une mise à jour viole le type, deux propositions de traitement sont faites\,: (A) Une routine de correction est activée pour adapter le document XML au type tout en prenant en compte la mise à jour. La mise à jour a donc une priorité par rapport aux données déjà stockées. (B) Une routine propose une adaptation du type du document, de façon à accepter le document mis à jour en préservant la validité des autres documents originalement valides et non soumis à la mise à jour. Dans ce cas, la mise à jour est prioritaire et les contraintes peuvent être modifiées. Une deuxième partie du travail considère la construction d'une plate-forme d'aide à la spécification, à l'implémentation et à la manipulation de services. L'idée de pouvoir spécifier et modifier des compositions de services nous a amené à la définition du langage PEWS (\textit{Path Expressions for Web Services}), ayant une sémantique formelle bien définie et permettant la spécification du comportement des interfaces des services web simples ou composés. Pour pouvoir tester statiquement des propriétés liées à la composition des services, nous proposons l'utilisation de la théorie des traces et les graphes de dépendances.

Ces dernières années ont été marquées par l’adoption en masse de XML comme format d’échange et de représentation des données stockées sur le web. Cette évolution s’est accompagnée du développement de langages pour l’interrogation et la manipulation des données XML et de la mise en œuvre de plusieurs systèmes pour le stockage et le traitement des ces dernières. Parmi ces systèmes, les moteurs mémoire centrale ont été développés pour faire face à des besoins spécifiques d’applications qui ne nécessitant pas les fonctionnalités avancées des SGBD traditionnels. Ces moteurs offrent les mêmes fonctionnalités que les systèmes traditionnels sauf que contrairement à ces derniers, ils nécessitent de charger entièrement les documents en mémoire centrale pour pouvoir les traiter. Par conséquent, ces systèmes sont limités quant à la taille des documents pouvant être traités. Dans cette thèse nous nous intéressons aux aspects liés à l’évolution des données XML et à la gestion de la dimension temporelle de celles-ci. Cette thèse comprend deux parties ayant comme objectif commun le développement de méthodes efficaces pour le traitement des documents XML volumineux en utilisant les moteurs mémoire centrale. Dans la première partie nous nous focalisons sur la mise à jour des documents XML statiques. Nous proposons une technique d’optimisation basée sur la projection XML et sur l’utilisation des schémas. La projection est une méthode qui a été proposée dans le cadre des requêtes afin de résoudre les limitations des moteurs mémoire centrale. Son utilisation pour le cas des mises à jour soulève de nouveaux problèmes liés notamment à la propagation des effets des mises à jour. La deuxième partie est consacrée à la construction et à la maintenance des documents temporels, toujours sous la contrainte d’espace. A cette contrainte s’ajoute la nécessité de générer des documents efficaces du point de vue du stockage. Notre contribution consiste en deux méthodes. La première méthode s’applique dans le cas général pour lequel aucune information n’est utilisée pour la construction des documents temporels. Cette méthode est conçue pour être réalisée en streaming et permet ainsi le traitement de document quasiment sans limite de taille. La deuxième méthode s’applique dans le cas où les changements sont spécifiés par des mises à jour. Elle utilise le paradigme de projection ce qui lui permet en outre de manipuler des documents volumineux de générer des documents temporels satisfaisant du point de vue du stockage. / The last decade has witnessed a rapid expansion of XML as a format for representing and exchanging data through the web. In order to follow this evolution, many languages have been proposed to query, update or transform XML documents. At the same time, a range set of systems allowing to store and process XML documents have been developed. Among these systems, main-memory engines are lightweight systems that are the favored choice for applications that do not require complex functionalities of traditional DBMS such as transaction management and secondary storage indexes. These engines require to loading the documents to be processed entirely into main-memory. Consequently, they suffer from space limitations and are not able to process quite large documents. In this thesis, we investigate issues related to the evolution of XML documents and to the management of the temporal dimension for XML. This thesis consists of two parts sharing the common goal of developing efficient techniques for processing large XML documents using main-memory engines. The first part investigates the optimization of update for static XML documents. We have developed a technique based on XML projection, a method that has been proposed to overcome the limitations of main-memory engines in the case of querying. We have devised for a new scenario for projection allowing the propagation of the updates effects. The second of the thesis investigates building and maintaining time-stamped XML documents under space limitations. Our contribution consists in two methods. The first method can be applied in the general case where no restriction is made on the evolution of the XML documents. This method is designed to be performed in streaming and allows thus processing large documents. The second method deals with the case where the changes are specified by updates. It is based on the projection paradigm which it allows it for processing large documents and for generating time-stamped documents satisfactory from the point of view of storage. We provide a means to comparing time-stamped wrt space occupancy.

Ces dernières années ont été marquées par l'adoption en masse de XML comme format d'échange et de représentation des données stockées sur le web. Cette évolution s'est accompagnée du développement de langages pour l'interrogation et la manipulation des données XML et de la mise en œuvre de plusieurs systèmes pour le stockage et le traitement des ces dernières. Parmi ces systèmes, les moteurs mémoire centrale ont été développés pour faire face à des besoins spécifiques d'applications qui ne nécessitant pas les fonctionnalités avancées des SGBD traditionnels. Ces moteurs offrent les mêmes fonctionnalités que les systèmes traditionnels sauf que contrairement à ces derniers, ils nécessitent de charger entièrement les documents en mémoire centrale pour pouvoir les traiter. Par conséquent, ces systèmes sont limités quant à la taille des documents pouvant être traités. Dans cette thèse nous nous intéressons aux aspects liés à l'évolution des données XML et à la gestion de la dimension temporelle de celles-ci. Cette thèse comprend deux parties ayant comme objectif commun le développement de méthodes efficaces pour le traitement des documents XML volumineux en utilisant les moteurs mémoire centrale. Dans la première partie nous nous focalisons sur la mise à jour des documents XML statiques. Nous proposons une technique d'optimisation basée sur la projection XML et sur l'utilisation des schémas. La projection est une méthode qui a été proposée dans le cadre des requêtes afin de résoudre les limitations des moteurs mémoire centrale. Son utilisation pour le cas des mises à jour soulève de nouveaux problèmes liés notamment à la propagation des effets des mises à jour. La deuxième partie est consacrée à la construction et à la maintenance des documents temporels, toujours sous la contrainte d'espace. A cette contrainte s'ajoute la nécessité de générer des documents efficaces du point de vue du stockage. Notre contribution consiste en deux méthodes. La première méthode s'applique dans le cas général pour lequel aucune information n'est utilisée pour la construction des documents temporels. Cette méthode est conçue pour être réalisée en streaming et permet ainsi le traitement de document quasiment sans limite de taille. La deuxième méthode s'applique dans le cas où les changements sont spécifiés par des mises à jour. Elle utilise le paradigme de projection ce qui lui permet en outre de manipuler des documents volumineux de générer des documents temporels satisfaisant du point de vue du stockage.

Durant cette dernière décennie, la diffusion du format XML pour représenter les données générées par et échangées sur le Web a été accompagnée par la mise en œuvre de nombreux moteurs d'évaluation de requêtes et de mises à jour XQuery. Parmi ces moteurs, les systèmes " mémoire centrale " (Main-memory Systems) jouent un rôle très important dans de nombreuses applications. La gestion et l'intégration de ces systèmes dans des environnements de programmation sont très faciles. Cependant, ces systèmes ont des problèmes de passage à l'échelle puisqu'ils requièrent le chargement complet des documents en mémoire centrale avant traitement.Cette thèse présente une technique de partitionnement des documents XML qui permet aux moteurs " mémoire principale " d'évaluer des expressions XQuery (requêtes et mises à jour) pour des documents de très grandes tailles. Cette méthode de partitionnement s'applique à une classe de requêtes et mises à jour pertinentes et fréquentes, dites requêtes et mises à jour itératives.Cette thèse propose une technique d'analyse statique pour reconnaître les expressions " itératives ". Cette analyse statique est basée sur l'extraction de chemins à partir de l'expression XQuery, sans utilisation d'information supplémentaire sur le schéma. Des algorithmes sont spécifiés, utilisant les chemins extraits par l'étape précédente, pour partitionner les documents en entrée en plusieurs parties, de sorte que la requête ou la mise à jour peut être évaluée sur chaque partie séparément afin de calculer le résultat final par simple concaténation des résultats obtenus pour chaque partie. Ces algorithmes sont mis en œuvre en " streaming " et leur efficacité est validée expérimentalement.En plus, cette méthode de partitionnement est caractérisée également par le fait qu'elle peut être facilement implémentée en utilisant le paradigme MapReduce, permettant ainsi d'évaluer une requête ou une mise à jour en parallèle sur les données partitionnées.

La projection est une des techniques utilisées pour permettre de réduire les besoins en terme de taille mémoire nécessaire aux moteurs de requêtes XML (in-memory). L'idée sous-jacente à cette technique est simple : étant donnée une requête Q à évaluer sur un document XML D, au lieu de procéder sur D, la requête est évaluée sur un document D', plus petit que D, construit lors du chargement de ce dernier en mémoire, par élagage des parties de D inutiles pour Q. Le document D', est une projection du document initial D. Il est souvent de taille drastiquement inférieure à celle de D.Alors que cette technique de projection a été étudiée et développée assez largement pour l'interrogation de document XML, à notre connaissance, ce type de technique n'a pas été explorée ni appliquée aux mises à jour de documents XML.L'objet de cette thèse a donc été de proposer une technique d'optimisation de mises à jour de documents au format XML exploitant le typage des documents.La contribution a porté sur la spécification de l'algorithme Merge, c'est-à-dire la fusion des modifications avec le document initial, ainsi que sur le développement d'un prototype sur lequel des tests ont été effectués. / XML projection is one of the main adopted optimization techniques for reducing memory consumption in XQuery in-memory engines. The main idea behind this technique is quite simple: given a query Q over an XML document D, instead of evaluating Q on D, the query Q is evaluated on a smaller document D' obtained from D by pruning out, at loading-time, parts of D that are unrelevant for Q. The actual queried document D' is a projection of the original one, and is often much smaller than D due to the fact that queries tend to be quite selective in general.While projection techniques have been extensively investigated for XML querying, we are not aware of applications to XML updating.This Thesis investigates application of a projection based optimization mechanism for XQuery Update Facility expressions in the presence of a schema. The current work includes study of the method and a formal development of Merge algorithm as well as experiments testifying its effectiveness.

Durant cette dernière décennie, la diffusion du format XML pour représenter les données générées par et échangées sur le Web a été accompagnée par la mise en œuvre de nombreux moteurs d’évaluation de requêtes et de mises à jour XQuery. Parmi ces moteurs, les systèmes « mémoire centrale » (Main-memory Systems) jouent un rôle très important dans de nombreuses applications. La gestion et l’intégration de ces systèmes dans des environnements de programmation sont très faciles. Cependant, ces systèmes ont des problèmes de passage à l’échelle puisqu’ils requièrent le chargement complet des documents en mémoire centrale avant traitement.Cette thèse présente une technique de partitionnement des documents XML qui permet aux moteurs « mémoire principale » d’évaluer des expressions XQuery (requêtes et mises à jour) pour des documents de très grandes tailles. Cette méthode de partitionnement s’applique à une classe de requêtes et mises à jour pertinentes et fréquentes, dites requêtes et mises à jour itératives.Cette thèse propose une technique d'analyse statique pour reconnaître les expressions « itératives ». Cette analyse statique est basée sur l’extraction de chemins à partir de l'expression XQuery, sans utilisation d'information supplémentaire sur le schéma. Des algorithmes sont spécifiés, utilisant les chemins extraits par l’étape précédente, pour partitionner les documents en entrée en plusieurs parties, de sorte que la requête ou la mise à jour peut être évaluée sur chaque partie séparément afin de calculer le résultat final par simple concaténation des résultats obtenus pour chaque partie. Ces algorithmes sont mis en œuvre en « streaming » et leur efficacité est validée expérimentalement.En plus, cette méthode de partitionnement est caractérisée également par le fait qu'elle peut être facilement implémentée en utilisant le paradigme MapReduce, permettant ainsi d'évaluer une requête ou une mise à jour en parallèle sur les données partitionnées. / With the widespread diffusion of XML as a format for representing data generated and exchanged over the Web, main query and update engines have been designed and implemented in the last decade. A kind of engines that are playing a crucial role in many applications are « main-memory » systems, which distinguish for the fact that they are easy to manage and to integrate in a programming environment. On the other hand, main-memory systems have scalability issues, as they load the entire document in main-memory before processing. This Thesis presents an XML partitioning technique that allows main-memory engines to process a class of XQuery expressions (queries and updates), that we dub « iterative », on arbitrarily large input documents. We provide a static analysis technique to recognize these expressions. The static analysis is based on paths extracted from the expression and does not need additional schema information. We provide algorithms using path information for partitioning the input documents, so that the query or update can be separately evaluated on each part in order to compute the final result. These algorithms admit a streaming implementation, whose effectiveness is experimentally validated. Besides enabling scalability, our approach is also characterized by the fact that it is easily implementable into a MapReduce framework, thus enabling parallel query/update evaluation on the partitioned data.

Ce travail traite deux problèmes rencontrés dans les environnements où l'on utitlise un SGBD de haut niveau sémantique et où les traitements réalisés sont peu structurés et évolutifs et se font sur des objets complexes et volumineux. II s"appui sur l'expérience acquise dans la réalisation des projets TIGRE ET DOEOIS. Le premier aspect porte sur la cohérence sémantique, ce qui concerne plus particulièrement les contraintes implicitement établies lors de la définition du schéma conceptuel de la base. La sémantique introduite dans les modèles que nous avons utilisés, est réalisée en intégrant des concepts déjà existants comme celui d'agrégation et de spécialisation qui se traduisent au niveau du schéma conceptuel par des dépendances existentielles entre les entités. Nous proposons pour les opérations de mise à jour, un ensemble de règles de propagations pour assurer que la base de données soit cohérente par rapport à son propre schéma conceptuel. Le deuxième aspect prend en compte l'exécution des opérations elles mêmes. Fournir la notion de transaction, c'est donner au programmeur d'application le moyen de définir' une séquence d'opérations comme étant un tout qui permet à la base de données d'évoluer entre deux états cohérents. Le problème que nous nous posons est de fournir un support pour l'exécution des applications qui assure le maintien de la cohérence, compte tenu des données et des caractéristiques des traitements faits aux données dans l'activité bureautique. Cet étude a abouti à la réalisation d'un mécanisme transactionnel simple et fléxible.

DANS CETTE THÈSE, NOUS NOUS POSITIONNONS DANS UN CONTEXTE DYNAMIQUE, OÙ LES DONNÉES XML ÉVOLUENT AU COURS DU TEMPS ET SONT SOUMISES À UN ENSEMBLE DE MISES À JOUR, ET NOUS NOUS INTÉRESSONS À DEUX PROBLÈMES MAJEURS, LARGEMENT ÉTUDIÉS DANS LE CADRE RELATIONNEL : -LA DÉTECTION DE L'IMPACT D'UN ENSEMBLE DE MISE À JOUR SUR UNE VUE, DÉFINIE PAR UNE REQUÊTE.-LA DÉTECTION DE L'IMPACT D'UN ENSEMBLE DE MISE À JOUR SUR LA SATISFACTION D'UNE DÉPENDANCE FONCTIONNELLE. DANS LE PREMIER CAS, L'OBJECTIF EST DE DÉTECTER SI L'ENSEMBLE DE MISES À JOUR A MODIFIÉ LA VUE. DANS LE DEUXIÈME CAS, L'OBJECTIF EST DE DÉTECTER SI L'ENSEMBLE DE MISE À JOUR A PRODUIT UN NOUVEAU DOCUMENT QUI NE SATISFAIT PLUS LES CONTRAINTES QU'IL SATISFAISAIT AVANT LES MISES À JOUR. NOUS NOUS DIFFÉRENCIONS DES TRAVAUX ANTÉRIEURS PRINCIPALEMENT SUR DEUX POINTS : (1) NOUS SUPPOSONS QUE LES DONNÉES SOURCES SONT À PRIORI INDISPONIBLES ET NOUS ÉTUDIONS LES DEUX PROBLÈMES EN EFFECTUANT UNE ANALYSE STATIQUE DES DÉFINITIONS DES MISES À JOUR, ET DE LA VUE (CAS1) OU DE LA DÉPENDANCE FONCTIONNELLE (CAS 2). DE PLUS, DANS LE CAS OÙ UN SCHÉMA XML CONTRAIGNANT LA STRUCTURE DES DONNÉES, EST DISPONIBLE NOUS UTILISONS CETTE INFORMATION SUPPLÉMENTAIRE DANS NOTRE ANALYSE AFIN DE DÉTECTER ÉVENTUELLEMENT PLUS DE CAS D'INDÉPENDANCES ENTRE LES MISES À JOUR ET LA VUE OU LA DÉPENDANCE FONCTIONNELLE SELON LE CAS. (2) NOUS PRENONS L'OPTION D'UTILISER, COMME MÉCANISME DE SÉLECTION DE NŒUDS, DANS LA DÉFINITION DES MISES À JOUR, DES VUES ET DES DÉPENDANCES FONCTIONNELLES, UN LANGAGE FORMEL BASÉ SUR L'UTILISATION DE MOTIFS RÉGULIER ARBORESCENTS, PERMETTANT DE DÉFINIR DES REQUÊTES APPELÉES 'REQUÊTES ARBRES RÉGULIÈRES' (EN ABRÉGÉ RARS).