HAL will be down for maintenance from Friday, June 10 at 4pm through Monday, June 13 at 9am. More information
Skip to Main content Skip to Navigation
Journal articles

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 - 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
Document type :
Journal articles
Complete list of metadata

Cited literature [20 references]  Display  Hide  Download

Contributor : Inria Links Connect in order to contact the contributor
Submitted on : Sunday, October 4, 2015 - 6:00:26 PM
Last modification on : Thursday, March 31, 2022 - 4:37:50 AM
Long-term archiving on: : Tuesday, January 5, 2016 - 10:17:04 AM


TOCS 2015b.pdf
Files produced by the author(s)



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⟩



Record views


Files downloads