Regular path query languages for data graphs are essentially . The lack of type information greatly limits the optimization opportunities for query engines and makes application development more complex. In this paper we discuss a simple, yet expressive, schema language for edge-labelled data graphs. This schema language is, then, used to define a query type inference approach with good precision properties.
SheX @cite_11 is a schema language for RDF data. As in TSL, in SheX it is possible to describe complex node structures, and, unlike in TSL, outgoing edges can be defined by using regular expressions. However, just as in TSL, there is no way to specify constraints on incoming edges. This means that, for instance, in a schema describing cars and car owners, one can impose the constraint that a single person can own at most @math cars, but not the constraint that a car can have one single owner at a time. This makes impossible to define empty SheX schemas, but it limits the expressivity of the language.
@cite_11
2167961018
We study the expressiveness and complexity of Shape Expression Schema (ShEx), a novel schema formalism for RDF currently under development by W3C. 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.