News
KR Paper Accepted
Our paper Common Foundations for Recursive Shape Languages was accepted to KR 2026.
This is a paper with many co-authors and is the result of many weekly zoom meetings where we tried to get an understanding of recursion mechanisms in the schema languages ShEx and SHACL for RDF data. It is a follow-up of our paper Common Foundations for SHACL, ShEx, and PG-Schema (WWW 2025). Both papers grew out of the great Dagstuhl Seminar 24102.
Whereas ShEx had recursion from the beginning, SHACL didn't, but the W3C seems to be planning to add it. The hot candidate for SHACL recursion is least fixpoint semantics (LFP). The paper takes a look at three canonical candidates, namely LFP, supported model semantics (SMS), and greatest fixpoint semantics (GFP), which is what ShEx uses.
The conclusion is that LFP makes total sense. Although it is different in philosophy from ShEx's GFP, it is very compatible. Both LFP and GFP have the same expressiveness, and there exists an easy translation between them. Furthermore, the evaluation problems for LFP and GFP are in polynomial time, which is good. Evaluation for SMS is NP-hard, which makes this a trickier candidate.