Complexity and Expressiveness of ShEx for RDF

Slawek Staworko; Iovka Boneva; José Emilio Labra Gayo; Samuel Hym; Eric G. Prud'hommeaux; Harold R. Solbrig

doi:10.4230/LIPIcs.ICDT.2015.195

Complexity and Expressiveness of ShEx for RDF

Slawek Staworko, Iovka Boneva, José Emilio Labra Gayo, Samuel Hym, Eric G. Prud'hommeaux, Harold R. Solbrig

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

Abstract

We study the expressiveness and complexity of Shape Expression Schema (ShEx), a novel schema formalism for RDF currently under development by W3C. A 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.

Original language	English
Title of host publication	18th International Conference on Database Theory, ICDT 2015, March 23-27, 2015, Brussels, Belgium
Pages	195-211
Number of pages	17
DOIs	https://doi.org/10.4230/LIPIcs.ICDT.2015.195
Publication status	Published - 2015

Access to Document

10.4230/LIPIcs.ICDT.2015.195

Staworko Boneva ET AL 2015 Complexity and Expressiveness of ShEx for RDFFinal published version, 598 KB

http://dx.doi.org/10.4230/LIPIcs.ICDT.2015.195

Fingerprint Dive into the research topics of 'Complexity and Expressiveness of ShEx for RDF'. Together they form a unique fingerprint.

Cite this

@inproceedings{38163313ea9f4fd481fe981dec635f20,

title = "Complexity and Expressiveness of ShEx for RDF",

abstract = "We study the expressiveness and complexity of Shape Expression Schema (ShEx), a novel schema formalism for RDF currently under development by W3C. A 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. ",

author = "Slawek Staworko and Iovka Boneva and Gayo, {Jos{\'e} Emilio Labra} and Samuel Hym and Prud'hommeaux, {Eric G.} and Solbrig, {Harold R.}",

year = "2015",

doi = "10.4230/LIPIcs.ICDT.2015.195",

language = "English",

pages = "195--211",

booktitle = "18th International Conference on Database Theory, ICDT 2015, March 23-27, 2015, Brussels, Belgium",

}

TY - GEN

T1 - Complexity and Expressiveness of ShEx for RDF

AU - Staworko, Slawek

AU - Boneva, Iovka

AU - Gayo, José Emilio Labra

AU - Hym, Samuel

AU - Prud'hommeaux, Eric G.

AU - Solbrig, Harold R.

PY - 2015

Y1 - 2015

N2 - We study the expressiveness and complexity of Shape Expression Schema (ShEx), a novel schema formalism for RDF currently under development by W3C. A 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.

AB - We study the expressiveness and complexity of Shape Expression Schema (ShEx), a novel schema formalism for RDF currently under development by W3C. A 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.

U2 - 10.4230/LIPIcs.ICDT.2015.195

DO - 10.4230/LIPIcs.ICDT.2015.195

M3 - Conference contribution

SP - 195

EP - 211

BT - 18th International Conference on Database Theory, ICDT 2015, March 23-27, 2015, Brussels, Belgium

ER -