Shapes from Examples: Foundations of Shape Learning in Recursive SHACL
Bente Gortworst, Cem Okulmus, Magdalena Ortiz, Anni-Yasmin Turhan
Abstract
SHACL shapes enable data graph validation, making automatic shape learning essential for knowledge graph applications. We investigate the well-known fitting approach to this task: given sets P and N of positive and negative example nodes from an input graph, compute a shape expression C, possibly using shape names defined in a recursive shape catalogue, that validates at every node in P and none in N. We focus on the case where C is written in a core fragment of SHACL corresponding to the Description Logic ELI. For the catalogue, we consider the well-founded, stable, and supported semantics. We address fitting existence and most specific fitting computation, establish tight exponential-time upper bounds for both problems, and obtain polynomial bounds for relevant special cases.
Topics
Classified with taxonomy v2 on Wed, 2 Sept 2026.