Simple Schemas for Unordered XML

Iovka Boneva, Radu Ciucanu, Slawek Staworko

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract / Description of output

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.
Original languageEnglish
Title of host publicationProceedings of the 16th International Workshop on the Web and Databases 2013, WebDB 2013, New York, NY, USA, June 23, 2013.
Number of pages6
Publication statusPublished - 2013


Dive into the research topics of 'Simple Schemas for Unordered XML'. Together they form a unique fingerprint.

Cite this