DROPS

Document

DOI: 10.4230/LIPIcs.ICDT.2015.195

Complexity and Expressiveness of ShEx for RDF

Authors: Slawek Staworko, Iovka Boneva, Jose E. Labra Gayo, Samuel Hym, Eric G. Prud'hommeaux, and Harold Solbrig

Published in: LIPIcs, Volume 31, 18th International Conference on Database Theory (ICDT 2015)

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.

Cite as

Slawek Staworko, Iovka Boneva, Jose E. Labra Gayo, Samuel Hym, Eric G. Prud'hommeaux, and Harold Solbrig. Complexity and Expressiveness of ShEx for RDF. In 18th International Conference on Database Theory (ICDT 2015). Leibniz International Proceedings in Informatics (LIPIcs), Volume 31, pp. 195-211, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2015)

Copy BibTex To Clipboard

@InProceedings{staworko_et_al:LIPIcs.ICDT.2015.195,
  author =	{Staworko, Slawek and Boneva, Iovka and Labra Gayo, Jose E. and Hym, Samuel and Prud'hommeaux, Eric G. and Solbrig, Harold},
  title =	{{Complexity and Expressiveness of ShEx for RDF}},
  booktitle =	{18th International Conference on Database Theory (ICDT 2015)},
  pages =	{195--211},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-79-8},
  ISSN =	{1868-8969},
  year =	{2015},
  volume =	{31},
  editor =	{Arenas, Marcelo and Ugarte, Mart{\'\i}n},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICDT.2015.195},
  URN =		{urn:nbn:de:0030-drops-49856},
  doi =		{10.4230/LIPIcs.ICDT.2015.195},
  annote =	{Keywords: RDF, Schema, Graph topology, Validation, Complexity, Expressiveness}
}

Search Results

Documents authored by Boneva, Iovka

Complexity and Expressiveness of ShEx for RDF

Abstract

Cite as

Thanks for your feedback!

Could not send message