Edinburgh Research Explorer

Complexity and Expressiveness of ShEx for RDF

Research output: Chapter in Book/Report/Conference proceedingConference contribution

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

Related Edinburgh Organisations

Access status

Open

Documents

http://dx.doi.org/10.4230/LIPIcs.ICDT.2015.195
Original languageEnglish
Title of host publication18th International Conference on Database Theory, ICDT 2015, March 23-27, 2015, Brussels, Belgium
Pages195-211
Number of pages17
DOIs
StatePublished - 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.

Download statistics

No data available

ID: 19313662