Skip to Main content Skip to Navigation
Conference papers

Containment of Shape Expression Schemas for RDF

Slawomir Staworko 1, 2 Piotr Wieczorek 3
2 LINKS - Linking Dynamic Data
CRIStAL - Centre de Recherche en Informatique, Signal et Automatique de Lille - UMR 9189, Inria Lille - Nord Europe
Abstract : We study the problem of containment of shape expression schemas (ShEx) for RDF graphs. We identify a subclass of ShEx that has a natural graphical representation in the form of shape graphs and whose semantics is captured with a tractable notion of embedding of an RDF graph in a shape graph. When applied to pairs of shape graphs, an embedding is a sufficient condition for containment, and for a practical subclass of deterministic shape graphs, it is also a necessary one, thus yielding a subclass with tractable containment. Containment for general shape graphs is EXP-complete. Finally , we show that containment for arbitrary ShEx is decid-able. CCS CONCEPTS • Information systems → Graph-based database models ; Resource Description Framework (RDF); • Theory of computation → Database theory; Database interoper-ability.
Document type :
Conference papers
Complete list of metadata

Cited literature [39 references]  Display  Hide  Download

https://hal.inria.fr/hal-01959143
Contributor : Slawomir Staworko <>
Submitted on : Thursday, June 27, 2019 - 3:21:55 PM
Last modification on : Friday, December 11, 2020 - 6:44:06 PM

File

paper.pdf
Files produced by the author(s)

Identifiers

Collections

Citation

Slawomir Staworko, Piotr Wieczorek. Containment of Shape Expression Schemas for RDF. PODS 2019 - 38th ACM SIGMOD-SIGACT-SIGAI Symposium on PRINCIPLES OF DATABASE SYSTEMS, Jun 2019, Amsterdam, Netherlands. pp.303-319, ⟨10.1145/3294052.3319687⟩. ⟨hal-01959143⟩

Share

Metrics

Record views

179

Files downloads

448