2026-07-23T00:19:02Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:4985 2024-03-06T10:35:39Z ddc:004 open_access

Complexity and Expressiveness of ShEx for RDF Staworko, Slawek Boneva, Iovka Labra Gayo, Jose E. Hym, Samuel Prud'hommeaux, Eric G. Solbrig, Harold RDF Schema Graph topology Validation Complexity Expressiveness 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Slawek Staworko and Iovka Boneva and Jose E. Labra Gayo and Samuel Hym and Eric G. Prud'hommeaux and Harold Solbrig 2015 Is Part Of LIPIcs, Volume 31, 18th International Conference on Database Theory (ICDT 2015) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ICDT.2015.195 urn:nbn:de:0030-drops-49856 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICDT.2015.195 eng https://creativecommons.org/licenses/by/3.0/legalcode