Simple Schemas for Unordered XML - Archive ouverte HAL Access content directly
Conference Papers Year :

Simple Schemas for Unordered XML

(1, 2) , (1, 2) , (1, 2)


We consider unordered XML, where the relative order among siblings is ignored, and propose two simple yet practical schema formalisms: disjunctive multiplicity schemas (DMS), and its restriction, disjunction-free multiplicity schemas (MS). We investigate their computational properties and characterize the complexity of the following static analysis problems: schema satisfiability, membership of a tree to the language of a schema, schema containment, twig query satisfiability, implication, and containment in the presence of schema. Our research indicates that the proposed formalisms retain much of the expressiveness of DTDs without an increase in computational complexity.
Fichier principal
Vignette du fichier
ciucanu-webdb13.pdf (346.39 Ko) Télécharger le fichier
Origin : Files produced by the author(s)

Dates and versions

hal-00824459 , version 1 (07-05-2015)



Iovka Boneva, Radu Ciucanu, Slawomir Staworko. Simple Schemas for Unordered XML. 16th International Workshop on the Web and Databases (WebDB), Jun 2013, New York, United States. ⟨hal-00824459⟩
110 View
56 Download



Gmail Facebook Twitter LinkedIn More