💬 NLP

Denotational Semantics for ODRL: Knowledge-Based Constraint Conflict Detection

This paper proposes a denotational semantics framework that enables sound, three-valued conflict detection for ODRL policies across heterogeneous knowledge bases by mapping constraints to KB concepts, proving that conflicts are preserved under alignment while gracefully degrading unknowns, and validating the approach with 154 benchmarks across diverse taxonomies and structural domains.

Original authors: Daham Mustafa, Diego Collarana, Yixin Peng, Rafiqul Haque, Christoph Lange-Bever, Christoph Quix, Stephan Decker

Published 2026-02-24

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Daham Mustafa, Diego Collarana, Yixin Peng, Rafiqul Haque, Christoph Lange-Bever, Christoph Quix, Stephan Decker

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 are trying to organize a massive, global digital library where different countries and organizations want to share books, but they all speak different "languages" of rules.

In this story, ODRL is the universal rulebook for digital rights. It's like a form you fill out to say, "You can read this book if you are in Europe, you are a student, and you won't sell it."

However, there's a big problem: The form has blank spaces that require external knowledge.

If the rule says "Must be in Europe," how does the computer know that France counts?
If the rule says "Must be French," how does it know that German is different?
If the rule says "Must be Non-Commercial," how does it know if "Scientific Research" fits that category?

Without a dictionary (a Knowledge Base) to explain these connections, the computer just shrugs and says, "I don't know." This leads to a "Default Deny" situation where nothing ever gets shared because the computer is too scared to make a guess.

The Paper's Solution: The "Semantic Translator"

This paper introduces a smart system that acts like a super-smart translator and logic checker. It doesn't just look at the words; it looks at the meaning behind them using a "Knowledge Base" (a structured map of facts).

Here is how it works, broken down into simple concepts:

1. The Three-Valued Verdict (The Traffic Light System)

Instead of just saying "Yes" or "No," this system uses a three-way traffic light to be safe:

🟢 Compatible (Green): The rules definitely work together. (e.g., "France" is inside "Europe," so a rule for Europe covers France).
🔴 Conflict (Red): The rules definitely clash. (e.g., A rule says "Must be French," but the request is "German." They can never be the same).
🟡 Unknown (Yellow): The system doesn't have enough info to decide. (e.g., The rule says "Research," but the knowledge base doesn't know if "Scientific Research" counts as "Commercial" or not).
- Crucial Point: The system prefers to be Unknown rather than guessing wrong. It's better to pause and ask a human than to accidentally block a legitimate request or allow a forbidden one.

2. The "Map" Analogy (Knowledge Bases)

Think of the Knowledge Base as a family tree or a geographic map.

Taxonomic (Family Tree): If "Dog" is a child of "Animal," and the rule says "Must be an Animal," the system knows a "Dog" fits.
Mereological (Puzzle Pieces): If "France" is a piece of the "Europe" puzzle, the system knows France is part of Europe.
Nominal (Name Tags): If the rule says "Must be Device A," and the request is "Device B," and they are just different names with no hierarchy, they clash.

3. The "X-ONE" Trap (The Strict Gatekeeper)

The paper discovered a tricky rule called XONE (Exclusive OR). This means "You can have Rule A OR Rule B, but NOT both."

The Problem: In a world where we might not know everything (Open World), it's very hard to prove that two things are mutually exclusive.
The Analogy: Imagine a bouncer saying, "You can enter if you are wearing a Hat OR a Scarf, but not both."
- If you see someone with a Hat, can you be 100% sure they don't also have a Scarf hidden under their coat?
- The paper shows that unless the "Knowledge Base" has very strict rules saying "Hats and Scarves are totally incompatible," the system must stay Yellow (Unknown) rather than guessing "Green." It requires stronger proof to say "No" than to say "Yes."

4. Speaking Different Dialects (Cross-Dataspace Alignment)

Imagine the German library uses a map called GeoNames, but the French archive uses a map called ISO 3166. They both have "France," but they might list it differently.

The paper creates a translation bridge between these maps.
The Safety Guarantee: If the German map says "Conflict," the French map must also say "Conflict." But if the French map is missing a detail, it shouldn't invent a fake conflict; it should just say "Unknown." This ensures that moving data between different systems doesn't break things or create false alarms.

5. The "Proof" (Why we can trust it)

The authors didn't just write this down; they built a mathematical robot (using tools called Vampire and Z3) to test 154 different scenarios.

They tested tricky edge cases, like "What if the map is incomplete?" or "What if the rules are nested inside each other?"
The result? The robot agreed with the math 100% of the time. They proved that their system is sound: if it says "Conflict," it is impossible for the rules to ever work together, no matter what future information you find.

The Big Takeaway

This paper solves the "Default Deny" problem in digital rights. Instead of blocking everything because the computer is unsure, it gives us a safe, logical way to say "Unknown" and a rigorous way to say "Conflict."

It allows different digital worlds (dataspaces) to talk to each other without needing a human to manually re-write every single rule. It's like giving every digital library a universal translator that understands the meaning of the rules, not just the words, ensuring data can flow safely and freely.

1. Problem Statement

The Open Digital Rights Language (ODRL) is a W3C standard for expressing digital policies, widely adopted in European data ecosystems (e.g., Gaia-X, IDSA). However, ODRL relies on six set-based operators (isA, isPartOf, hasPart, isAnyOf, isAllOf, isNoneOf) whose semantics depend on external domain knowledge (Knowledge Bases or KBs) that the specification leaves undefined.

Core Challenges:

Undefined Semantics: Without external KBs, ODRL engines cannot compute set operators, defaulting to "Unknown" for cross-dataspace comparisons.
Interoperability: Different dataspace stakeholders use different KB standards (e.g., GeoNames vs. ISO 3166 for spatial data; BCP 47 vs. ISO 639-3 for languages). Existing approaches either ignore set operators or hardcode logic that fails to generalize.
Conflict Detection: Determining if two policies (e.g., a permission and a prohibition) can coexist is difficult when constraints involve incomplete knowledge. Current tools often default to "deny," blocking legitimate data sharing.
Policy Quality: Policies may contain internal contradictions (e.g., requiring a purpose to be both commercial and academic) or redundancies that go undetected without formal verification.

2. Methodology

The authors propose a Semantic Grounding Framework that maps ODRL constraints to denotations (sets of KB concepts) and performs conflict detection using three-valued logic (Conflict, Compatible, Unknown).

A. Formal Definitions

Knowledge Base (KB): Defined as a structure $(C, \leq, \perp, \gamma)$ , where $C$ is a set of concepts, $\leq$ is a reflexive/transitive ordering (subsumption or part-whole), $\perp$ is a disjointness relation, and $\gamma$ maps values to concepts.
Semantic Domains: The framework unifies three domains:
1. Taxonomic: Class subsumption ( $\sqsubseteq$ ) for purposes, languages, industries.
2. Mereological: Part-whole containment ( $\preceq$ ) for spatial locations.
3. Nominal: Identity ( $=$ ) for devices, channels, and systems.
Denotational Semantics: Each constraint $c = (\ell, \triangleright, v)$ $c = (ℓ, ▹, v)$ is mapped to a set of concepts $[[c]]_{KB}$ $[[c]]_{K B}$ .
- If the value $v$ is unmapped in the KB, the denotation is $\top$ (indeterminate/Unknown).
- Operators like isA and isPartOf are interpreted via downward closure in the KB hierarchy; hasPart via upward closure.
Conflict Detection:
- Conflict: The intersection of denotations is provably empty ( $\emptyset$ ).
- Compatible: The intersection is non-empty.
- Unknown: The intersection cannot be determined due to incomplete KB information (denotation is $\top$ ).

B. Composition and Alignment

Logical Composition: The framework handles ODRL's three composition modes (and, or, xone) using Kleene three-valued logic.
- Key Insight: Exclusive composition (xone) requires strictly stronger KB axioms (provable disjointness) than and or or. Under open-world semantics, xone often defaults to "Unknown" unless negative axioms explicitly prove non-overlap.
Cross-Dataspace Alignment: To handle different KBs (e.g., GeoNames vs. ISO 3166), the authors define order-preserving alignments (injective partial functions).
- Guarantees: Conflicts detected in one KB are preserved in aligned KBs. Unmapped concepts degrade gracefully to "Unknown" rather than causing false conflicts.
- Witness Completeness: Ensures that if a concept is mapped, all its sub-concepts are also mapped to prevent "witness loss" that could fabricate conflicts.

C. Decidability and Verification

EPR Fragment: The encoding stays within the Effectively Propositional (EPR) fragment of First-Order Logic, ensuring decidability.
Mechanical Verification: All meta-theorems (soundness, composition, alignment preservation) are mechanically verified using Isabelle/HOL.
Runtime Soundness: The framework proves that design-time conflict verdicts hold for all possible runtime execution contexts.

3. Key Contributions

Unified Denotational Semantics: A formal framework covering all 8 ODRL KB-dependent operators across taxonomic, mereological, and nominal domains, supporting conflict detection, redundancy identification, and refinement verification.
Three-Valued Reasoning: A sound approach for incomplete knowledge where "Unknown" represents epistemic incompleteness, ensuring that "Conflict" verdicts are never false positives.
Cross-Standard Alignment: A formal proof that conflicts are preserved across different KB standards, and unmapped concepts degrade safely to "Unknown," enabling interoperability without manual re-encoding.
Discovery on xone: The framework reveals that exclusive composition (xone) is significantly harder to satisfy than conjunction/disjunction in open-world settings, requiring explicit negative axioms in the KB.

4. Results and Evaluation

The framework was validated using a comprehensive benchmark suite:

Scale: 154 benchmark problems across 19 categories.
Knowledge Bases: Six families including GeoNames, ISO 3166, W3C DPV, GDPR-derived taxonomies, BCP 47, and ISO 639-3, plus structural KBs for edge cases.
Provers: Encoded in both TPTP and SMT-LIB formats and evaluated by two independent provers: Vampire (superposition calculus) and Z3 (SMT solver).
Outcome: 100% agreement between Vampire and Z3 on all 154 verdicts.
Specific Findings:
- Confirmed that xone fails to resolve to "Compatible" without explicit disjointness axioms, often resulting in "Unknown."
- Demonstrated that alignment preserves conflicts and prevents false positives even with partial mappings.
- Verified that runtime constraints cannot satisfy a pair of constraints deemed "Conflict" at design time.

5. Significance

Interoperability: Solves the "default deny" problem in cross-dataspace policy exchange by providing a formal mechanism to reason about policies using different underlying standards.
Safety: Ensures that policy conflicts are detected soundly; a "Conflict" verdict guarantees that no execution context can satisfy both policies, preventing policy violations at runtime.
Scalability: By restricting logic to the EPR fragment, the approach remains decidable and computationally tractable.
Foundation for Automation: Provides the theoretical basis for automated policy authoring tools that can detect contradictions and redundancies before policies are deployed, moving ODRL from a syntactic standard to a semantically grounded one.

This work bridges the gap between the abstract ODRL specification and practical, knowledge-driven policy enforcement, enabling secure and interoperable data sharing across heterogeneous data ecosystems.