We're sorry but this page doesn't work properly without JavaScript enabled. Please enable it to continue.
Feedback

Containment of Shape Expression Schemas for RDF

Formal Metadata

Title
Containment of Shape Expression Schemas for RDF
Title of Series
Number of Parts
155
Author
License
CC Attribution 3.0 Germany:
You are free to use, adapt and copy, distribute and transmit the work or content in adapted or unchanged form for any legal purpose as long as the work is attributed to the author in the manner specified by the author or licensor.
Identifiers
Publisher
Release Date
Language

Content Metadata

Subject Area
Genre
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 decidable.