Simple Schemas for Unordered XML

Iovka Boneva 1, 2 Radu Ciucanu 1, 2, * Slawomir Staworko 1, 2
* Auteur correspondant
2 LINKS - Linking Dynamic Data
LIFL - Laboratoire d'Informatique Fondamentale de Lille, Inria Lille - Nord Europe
Abstract : 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.
Type de document :
Communication dans un congrès
16th International Workshop on the Web and Databases (WebDB), Jun 2013, New York, United States
Liste complète des métadonnées

https://hal.inria.fr/hal-00824459
Contributeur : Radu Ciucanu <>
Soumis le : jeudi 7 mai 2015 - 17:02:56
Dernière modification le : jeudi 11 janvier 2018 - 06:25:27
Document(s) archivé(s) le : mercredi 19 avril 2017 - 19:34:50

Fichier

ciucanu-webdb13.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : hal-00824459, version 1
  • ARXIV : 1303.4277

Citation

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〉

Partager

Métriques

Consultations de la notice

331

Téléchargements de fichiers

86