Résumé

Dans ce papier nous étudions le problème classique de l’impact d’une mise à jour sur une vue, dans le cadre de données semi-structurées. Nous faisons les hypothèses suivantes: (i) le document source est modélisé par un arbre ordonné étiqueté par des symboles d’arité variable, (ii) une vue V est une requête arbre dont l’évaluation sur le document source fournit la vue partielle du document souhaitée (iii) une classe de mises à jour C est également donnée par une requête arbre sélectionnant les noeuds à modifier. Nous étudions alors le problème suivant: étant donné une requête de vue V et une classe de mise à jour C est-il possible de détecter si la vue V est indépendante de toute mise à jour q de C ? Nous montrons que le problème est en général NP-difficile. Nous exhibons une condition suffisante évaluable en temps polynomial assurant l’indépendance d’une vue V par rapport à une classe de mises à jour C ainsi que certaines sous-classes de requêtes de vues pour lesquelles le problème devient polynomial.

Abstract

In this paper we study the classical problem of the impact of an update on a view defined over semi-structured data. We make the following assumptions: (i) the source docu- ment is modelized by an unranked, labeled, ordered tree, (ii) a view V is a tree query whose evaluation on the source document provides the desired partial view of the document, (iii) a class of updates C is also given by a tree query selecting the nodes to modify. We then study the following problem : given a view query V and a class of updates C, is it possible to detect if the view V is independent of each update q in C? We show that the problem is in general NP-hard. We propose a sufficient condition evaluable in polynomial time ensuring the independence of a view V with a class of updates C. We then address some subclasses of view queries V for which the problem becomes polynomial.