Static Analysis of Recursive SHACL
This paper investigates the decidability of SHACL document containment, proving that the problem is undecidable under supported and stable model semantics but decidable in single exponential time under well-founded semantics via a novel translation to hybrid mu-calculus.
Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer
Imagine you have a massive, messy library of information where books (data) are connected by strings (relationships) rather than sitting in neat, pre-defined shelves. This is how modern "Knowledge Graphs" work. To keep this library organized, we need a set of rules called SHACL (Shape Constraint Language). These rules act like a librarian's checklist, saying things like, "Every book about cats must have an author," or "No book can be both a novel and a textbook."
Usually, librarians just check if a specific book follows the rules (Validation). But this paper asks a much harder question: Can we compare two different rulebooks to see if one is "stronger" than the other? In other words, if a book passes the rules in Rulebook A, will it automatically pass the rules in Rulebook B? This is called "implication" or "containment."
The researchers discovered that the answer depends entirely on how we handle loops (recursion) in the rules.
The Three Librarian Philosophies
The paper tests three different ways of interpreting these rules when they get tricky (like a rule that says "A book is valid only if it references a book that is not valid").
The "Supported" and "Stable" Librarians (The Chaos):
These librarians try to find a consistent way to label every book. However, when rules get recursive, they might find multiple valid ways to label the library, or sometimes no way at all.- The Result: The researchers found that trying to compare rulebooks under these philosophies is impossible to solve. It's like asking a computer to predict the outcome of a game of chess where the rules of chess can change mid-game based on the players' thoughts. No matter how powerful the computer is, it will eventually get stuck in an infinite loop. Even if the rules are relatively simple, the math proves there is no algorithm that can always give a "Yes" or "No" answer.
The "Well-Founded" Librarian (The Pragmatist):
This librarian takes a different approach. Instead of trying to find a perfect, all-encompassing truth, they say: "If we can't prove a book is valid, we'll assume it's invalid. If we can't prove it's invalid, we'll assume it's valid. If we're truly stuck, we just leave the label blank."- The Result: This approach is a game-changer. Under this philosophy, the problem of comparing rulebooks is solvable. Not only is it solvable, but it can be done relatively quickly (specifically, in "single exponential time," which is fast enough for computers to handle even for large documents).
The Magic Trick: The "Hybrid µ-Calculus"
How did they prove the "Well-Founded" librarian could solve the problem? They used a clever translation trick.
Imagine the SHACL rules are written in a complex, messy dialect. The researchers built a translator that converts these rules into a different, highly structured language called the Full Hybrid µ-calculus.
- The Analogy: Think of SHACL rules as a tangled ball of yarn. The researchers found a way to untangle that yarn and weave it into a perfect, rigid net (the µ-calculus).
- The Discovery: Once the rules are in this "net" format, we know exactly how to check them because mathematicians have already figured out how to solve problems in this specific language.
- The Twist: The translation isn't just a simple copy-paste. It involves a specific type of logic that allows for "loops" (fixed points) but keeps them under control. The paper shows that the "Well-Founded" approach naturally fits into this controlled loop structure, whereas the other approaches create loops that are too wild to tame.
The "Grid" Problem
To prove that the other methods (Supported/Stable) are impossible to solve, the researchers used a classic math puzzle called the "Tiling Problem."
- The Analogy: Imagine you have a set of square tiles with patterns on them. You want to know if you can cover an infinite floor with them without any gaps or mismatches. Mathematicians already proved that for some sets of tiles, no computer can ever tell you if it's possible.
- The Connection: The researchers showed that the "Supported" and "Stable" rulebooks are so powerful that they can simulate this infinite tiling puzzle. If you could solve the rulebook comparison problem, you could also solve the tiling puzzle. Since the tiling puzzle is unsolvable, the rulebook comparison must be unsolvable too.
The Bottom Line
- The Problem: Comparing two sets of data rules is usually impossible if the rules are recursive and we use standard "multiple truth" logic.
- The Solution: If we use the "Well-Founded" logic (which accepts uncertainty and leaves some things undefined), the problem becomes solvable and efficient.
- The Method: They achieved this by translating the messy rules into a clean, mathematical "net" (the Hybrid µ-calculus) and using a specialized machine (an automaton) to check the net.
In short, the paper tells us that to make sense of complex, self-referencing data rules, we need to be a bit more humble (accepting that some things might be undefined) rather than trying to force a perfect, all-encompassing truth. This humility makes the math workable.
Drowning in papers in your field?
Get daily digests of the most novel papers matching your research keywords — with technical summaries, in your language.