Complexity and Expressiveness of ShEx for RDF
Type de document :
Communication dans un congrès avec actes
Titre :
Complexity and Expressiveness of ShEx for RDF
Auteur(s) :
Staworko, Slawomir [Auteur]
Centre de Recherche en Informatique, Signal et Automatique de Lille - UMR 9189 [CRIStAL]
Boneva, Iovka [Auteur]
Linking Dynamic Data [LINKS]
Centre de Recherche en Informatique, Signal et Automatique de Lille - UMR 9189 [CRIStAL]
Labra Gayo, Jose Emilio [Auteur]
Universidad de Oviedo [Oviedo]
Hym, Samuel [Auteur]
Extra Small Extra Safe [2XS]
Prud'Hommeaux, Eric Gordon [Auteur]
Computer Science and Artificial Intelligence Laboratory [Cambridge] [CSAIL]
Solbrig, Harold [Auteur]
Mayo Clinic [Scottsdale]
Centre de Recherche en Informatique, Signal et Automatique de Lille - UMR 9189 [CRIStAL]
Boneva, Iovka [Auteur]
Linking Dynamic Data [LINKS]
Centre de Recherche en Informatique, Signal et Automatique de Lille - UMR 9189 [CRIStAL]
Labra Gayo, Jose Emilio [Auteur]
Universidad de Oviedo [Oviedo]
Hym, Samuel [Auteur]
Extra Small Extra Safe [2XS]
Prud'Hommeaux, Eric Gordon [Auteur]
Computer Science and Artificial Intelligence Laboratory [Cambridge] [CSAIL]
Solbrig, Harold [Auteur]
Mayo Clinic [Scottsdale]
Éditeur(s) ou directeur(s) scientifique(s) :
Marcelo Arenas and Martín Ugarte
Titre de la manifestation scientifique :
18th International Conference on Database Theory (ICDT 2015)
Ville :
Brussels
Pays :
Belgique
Date de début de la manifestation scientifique :
2015-03-23
Titre de la revue :
18th International Conference on Database Theory (ICDT 2015)
Date de publication :
2015-03-23
Discipline(s) HAL :
Informatique [cs]/Base de données [cs.DB]
Informatique [cs]/Web
Informatique [cs]/Web
Résumé en anglais : [en]
We study the expressiveness and complexity of Shape Expression Schema (ShEx), a novel schema formalism for RDF currently under development by W3C. ShEx assigns types to the nodes of an RDF graph and allows to constrain the ...
Lire la suite >We study the expressiveness and complexity of Shape Expression Schema (ShEx), a novel schema formalism for RDF currently under development by W3C. ShEx assigns types to the nodes of an RDF graph and allows to constrain the admissible neighborhoods of nodes of a given type with regular bag expressions (RBEs). We formalize and investigate two alternative semantics, multi-and single-type, depending on whether or not a node may have more than one type. We study the expressive power of ShEx and study the complexity of the validation problem. We show that the single-type semantics is strictly more expressive than the multi-type semantics, single-type validation is generally intractable and multi-type validation is feasible for a small (yet practical) subclass of RBEs. To curb the high computational complexity of validation, we propose a natural notion of determinism and show that multi-type validation for the class of deterministic schemas using single-occurrence regular bag expressions (SORBEs) is tractable.Lire moins >
Lire la suite >We study the expressiveness and complexity of Shape Expression Schema (ShEx), a novel schema formalism for RDF currently under development by W3C. ShEx assigns types to the nodes of an RDF graph and allows to constrain the admissible neighborhoods of nodes of a given type with regular bag expressions (RBEs). We formalize and investigate two alternative semantics, multi-and single-type, depending on whether or not a node may have more than one type. We study the expressive power of ShEx and study the complexity of the validation problem. We show that the single-type semantics is strictly more expressive than the multi-type semantics, single-type validation is generally intractable and multi-type validation is feasible for a small (yet practical) subclass of RBEs. To curb the high computational complexity of validation, we propose a natural notion of determinism and show that multi-type validation for the class of deterministic schemas using single-occurrence regular bag expressions (SORBEs) is tractable.Lire moins >
Langue :
Anglais
Comité de lecture :
Oui
Audience :
Internationale
Vulgarisation :
Non
Collections :
Source :
Fichiers
- https://hal.archives-ouvertes.fr/hal-01218552/document
- Accès libre
- Accéder au document
- http://arxiv.org/pdf/1404.1270
- Accès libre
- Accéder au document
- https://hal.archives-ouvertes.fr/hal-01218552/document
- Accès libre
- Accéder au document
- https://hal.archives-ouvertes.fr/hal-01218552/document
- Accès libre
- Accéder au document
- document
- Accès libre
- Accéder au document
- staworko-icdt15a.pdf
- Accès libre
- Accéder au document
- 1404.1270
- Accès libre
- Accéder au document