ACCUEIL

Consignes aux
auteurs et coordonnateurs
Nos règles d'éthique

APPEL À
CONTRIBUTION
Décisions, argumentation et traçabilité dans l’Ingénierie des Systèmes d’Information
En savoir plus >>
Autres revues >>

Ingénierie des Systèmes d'Information

Networking and Information Systems
1633-1311
Revue des sciences et technologies de l'information
 

 ARTICLE VOL 15/1 - 2010  - pp.113-138  - doi:10.3166/isi.15.1.113-138
TITRE
Requêtes arbres régulières pour l'analyse de dépendances entre vues et mises à jour de documents XML

TITLE
Regular tree patterns for the analysis of updates and views dependencies on XML documents

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 à arités variables, (ii) une vue V est une requête arbre dont l'évaluation sur le document source fournit la vue partielle souhaitée du document (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 PSPACE-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. Nous montrons ensuite que le problème est polynomial pour la classe des requêtes de vues linéaires. Nous établissons également que le modèle de requête arbre choisi pour exprimer V et C., bien qu'incomparable avec XPath, permet d'exprimer les requêtes de CoreXPath positif.


ABSTRACT
In this paper we study the classical problem of the impact of an update on a view defined over semi-structured data. We adopt the following working hypotheses: (i) the source document is modeled by an unranked, labeled, ordered tree, (ii) a view V is a tree query whose evaluation on the source document provides a 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 PSPACE-hard. We propose a sufficient condition evaluable in polynomial time ensuring the independence of a view V with respect to a class of updates C.. We then consider the class of linear view queries for which the problem becomes polynomial. We also show that the tree query model chosen to express V and C., is incomparable with XPath but is able to capture positive queries of CoreXPath.


AUTEUR(S)
Hicham IDABAL, Françoise GIRE

MOTS-CLÉS
données semi-structurées, XML, requêtes, vues, mises à jour, automates d'arbres.

KEYWORDS
semi-structured data, XML, queries, updates, views, tree automata.

LANGUE DE L'ARTICLE
Français

 PRIX
• Abonné (hors accès direct) : 12.5 €
• Non abonné : 25.0 €
|
|
--> Tous les articles sont dans un format PDF protégé par tatouage 
   
ACCÉDER A L'ARTICLE COMPLET  (327 Ko)



Mot de passe oublié ?

ABONNEZ-VOUS !

CONTACTS
Comité de
rédaction
Conditions
générales de vente

 English version >> 
Lavoisier