Schemas for Unordered XML on a DIME

Boneva, Iovka; Ciucanu, Radu; Staworko, Slawomir

Type de document :

Article dans une revue scientifique: Article original

DOI :

10.1007/s00224-014-9593-1

Titre :

Schemas for Unordered XML on a DIME

Auteur(s) :

Boneva, Iovka [Auteur]

Laboratoire d'Informatique Fondamentale de Lille [LIFL]
Linking Dynamic Data [LINKS]
Ciucanu, Radu [Auteur correspondant]
Linking Dynamic Data [LINKS]
Laboratoire d'Informatique Fondamentale de Lille [LIFL]
Staworko, Slawomir [Auteur]
Linking Dynamic Data [LINKS]
Laboratoire d'Informatique Fondamentale de Lille [LIFL]

Titre de la revue :

Theory of Computing Systems

Pagination :

337--376

Éditeur :

Springer Verlag

Date de publication :

2015-08-01

ISSN :

1432-4350

Discipline(s) HAL :

Informatique [cs]/Base de données [cs.DB]

Résumé en anglais : [en]

We investigate schema languages for unordered XML having no relative order among siblings. First, we propose unordered regular expressions (UREs), essentially regular expressions with unordered concatenation instead of ...
Lire la suite >We investigate schema languages for unordered XML having no relative order among siblings. First, we propose unordered regular expressions (UREs), essentially regular expressions with unordered concatenation instead of standard concatenation, that define languages of unordered words to model the allowed content of a node (i.e., collections of the labels of children). However, unrestricted UREs are computationally too expensive as we show the intractability of two fundamental decision problems for UREs: membership of an unordered word to the language of a URE and containment of two UREs. Consequently, we propose a practical and tractable restriction of UREs, disjunctive interval multiplicity expressions (DIMEs). Next, we employ DIMEs to define languages of unordered trees and propose two schema languages: disjunctive interval multiplicity schema (DIMS), and its restriction, disjunction-free interval multiplicity schema (IMS). We study the complexity of the following static analysis problems: schema satisfiability, membership of a tree to the language of a schema, schema containment, as well as twig query satisfiability, implication, and containment in the presence of schema. Finally, we study the expressive power of the proposed schema languages and compare them with yardstick languages of unordered trees (FO, MSO, and Presburger constraints) and DTDs under commutative closure. Our results show that the proposed schema languages are capable of expressing many practical languages of unordered trees and enjoy desirable computational properties.Lire moins >

Langue :

Anglais

Comité de lecture :

Oui

Audience :

Internationale

Vulgarisation :

Non

Collections :