Which XML Schemas are Streaming Bounded Repairable?

Pierre Bourhis 1 Gabriele Puppis 2 Cristian Riveros 3
1 LINKS - Linking Dynamic Data
Inria Lille - Nord Europe, CRIStAL - Centre de Recherche en Informatique, Signal et Automatique de Lille (CRIStAL) - UMR 9189
Abstract : In this paper we consider the problem of repairing, that is, restoring validity of, documents with respect to XML schemas. We formalize this as the problem of determining, given an XML schema, whether or not a streaming procedure exists that transforms an input document so as to satisfy the XML schema, using a number of edits independent of the document. We show that this problem is decidable. In fact, we show the decidability of a more general problem, which allows the repair procedure to work on documents that are already known to satisfy another XML schema. The decision procedure relies on the analysis of the structure of an automaton model specifying the restriction and target XML schemas and reduces te problem to a novel notion of game played on pushdown systems associated with the schemas. Keywords bounded repair ⋅ streaming repair ⋅ DTD ⋅ XML Schema ⋅ top-down deterministic tree automaton
Type de document :
Article dans une revue
Theory of Computing Systems, Springer Verlag, 2015, 〈10.1007/s00224-015-9611-y〉
Liste complète des métadonnées

Littérature citée [20 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/hal-01211290
Contributeur : Inria Links <>
Soumis le : dimanche 4 octobre 2015 - 18:00:26
Dernière modification le : mardi 3 juillet 2018 - 11:42:20
Document(s) archivé(s) le : mardi 5 janvier 2016 - 10:17:04

Fichier

TOCS 2015b.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

Citation

Pierre Bourhis, Gabriele Puppis, Cristian Riveros. Which XML Schemas are Streaming Bounded Repairable?. Theory of Computing Systems, Springer Verlag, 2015, 〈10.1007/s00224-015-9611-y〉. 〈hal-01211290〉

Partager

Métriques

Consultations de la notice

215

Téléchargements de fichiers

90