  Knowledge graphs have emerged as expressive data structures for Web data.
Knowledge graph potential and the demand for ecosystems to facilitate their
creation, curation, and understanding, is testified in diverse domains, e.g.,
biomedicine. The Shapes Constraint Language (SHACL) is the W3C recommendation
language for integrity constraints over RDF knowledge graphs. Enabling quality
assements of knowledge graphs, SHACL is rapidly gaining attention in real-world
scenarios. SHACL models integrity constraints as a network of shapes, where a
shape contains the constraints to be fullfiled by the same entities. The
validation of a SHACL shape schema can face the issue of tractability during
validation. To facilitate full adoption, efficient computational methods are
required. We present Trav-SHACL, a SHACL engine capable of planning the
traversal and execution of a shape schema in a way that invalid entities are
detected early and needless validations are minimized. Trav-SHACL reorders the
shapes in a shape schema for efficient validation and rewrites target and
constraint queries for the fast detection of invalid entities. Trav-SHACL is
empirically evaluated on 27 testbeds executed against knowledge graphs of up to
34M triples. Our experimental results suggest that Trav-SHACL exhibits high
performance gradually and reduces validation time by a factor of up to 28.93
compared to the state of the art.
