Plan, apply and roll back changes to a production ontology, with a blast radius report and a proof an auditor can re-check.
Rust ai-nativedescription-logicsformal-verificationinfrastructure-as-codeisabelle-languageknowledge-graphleanlean4mcpmcp-serverontologyowlowl2reasoningrustshaclsparqltheorem-proving
//! Syntactic locality modules: `⊥`, `⊤`, and the iterated `⊥⊤*`.
//!
//! [`crate::segment_retrieve`] produces a SLICE, and [`crate::closure_diff`]
//! measures what a slice lost. This module produces a MODULE, which is a
//! different kind of object: a subset of the axioms carrying a coverage
//! theorem, so there is nothing left to measure afterwards.
//!
//! # The theorem, and whose it is
//!
//! For a signature `Σ`, an axiom is `⊥`-local when replacing every class and
//! property name outside `Σ` by `⊥` turns it into a tautology, and `⊤`-local
//! when the same replacement with `⊤` does. A module is extracted by repeatedly
//! taking every axiom that is NOT local with respect to `Σ ∪ sig(M)`, until the
//! set stops growing. Cuenca Grau, Horrocks, Kazakov and Sattler (JAIR 31,
//! 2008, "Modular Reuse of Ontologies: Theory and Practice") prove that the
//! result `M` satisfies `O ⊨ α iff M ⊨ α` for every axiom `α` over `Σ`, and
//! that alternating the two extractions (`⊥⊤*`) preserves that property while
//! shrinking the result.
//!
//! THAT THEOREM IS CITED, NOT CHECKED HERE. Nothing under `lean/` is about
//! syntactic locality, and this file does not pretend otherwise: the report
//! names a paper and never names a Lean theorem, and [`verify_module`] is
//! supplied so the guarantee can be EXERCISED against the engine's own closure
//! rather than asserted. `tests/module_extract_test.rs` runs that verification
//! over the shipped pizza ontology, which is the difference between "we
//! implemented an algorithm out of a paper" and "we ran it and nothing over the
//! signature was lost".
//!
//! # Conservative wherever it cannot classify
//!
//! An RDF graph is not a list of OWL axioms, so the axioms have to be recovered
//! from triples, and every recovery step has a failure mode. Each one resolves
//! the same way: an axiom this file cannot classify is NEVER local, so it is
//! INCLUDED. That direction is free, because any `M'` with `M ⊆ M' ⊆ O` still
//! has the coverage property — a superset entails everything `M` entails, and
//! `O` entails everything `M'` entails. Including too much costs size.
//! Excluding too much costs the theorem.
//!
//! The counts are in the report and the kinds are named, so "the module is
//! small" and "the module is small because half the file was unreadable" cannot
//! render the same.
use crate::graph::GraphStore;
use crate::projection_entailment::{SKOLEM_PREFIX, Spelled};
use serde::{Deserialize, Serialize};
use std::collections::{BTreeMap, BTreeSet, HashMap, HashSet};
use std::sync::Arc;
// ───────────────────────────────────────────────────────────────────────────
// Vocabulary
// ───────────────────────────────────────────────────────────────────────────
const RDF: &str = "http://www.w3.org/1999/02/22-rdf-syntax-ns#";
const RDFS: &str = "http://www.w3.org/2000/01/rdf-schema#";
const OWL: &str = "http://www.w3.org/2002/07/owl#";
const XSD: &str = "http://www.w3.org/2001/XMLSchema#";
/// Predicates OWL 2 fixes as annotation properties, plus the RDFS ones. A
/// triple over one of these carries no logical content — UNLESS the ontology
/// itself gives the property a domain, a range, a superproperty or an
/// equivalent, which is legal RDF and makes the assertion load-bearing again.
/// That case is detected in [`Index::build`] rather than assumed away.
const ANNOTATION_PREDICATES: &[&str] = &[
"http://www.w3.org/2000/01/rdf-schema#label",
"http://www.w3.org/2000/01/rdf-schema#comment",
"http://www.w3.org/2000/01/rdf-schema#seeAlso",
"http://www.w3.org/2000/01/rdf-schema#isDefinedBy",
"http://www.w3.org/2002/07/owl#versionInfo",
"http://www.w3.org/2002/07/owl#deprecated",
"http://www.w3.org/2002/07/owl#priorVersion",
"http://www.w3.org/2002/07/owl#backwardCompatibleWith",
"http://www.w3.org/2002/07/owl#incompatibleWith",
];
/// `rdf:type` objects that DECLARE a term rather than assert membership of a
/// user class.
///
/// `owl:Thing` and `rdfs:Resource` are in this list, and the reason is measured
/// rather than aesthetic. `x rdf:type owl:Thing` is a TAUTOLOGY in the OWL 2
/// direct semantics, so the locality test says it is `⊤`-local and drops it,
/// and the paper's theorem is untouched. The OWL 2 RL rule table this engine
/// evaluates does not REGENERATE it, so dropping it removes a member of the
/// closure, and the verification then reports an entailment loss over the
/// signature that is not one. Reading it as a declaration keeps it whenever the
/// individual is in the signature, which makes the DL guarantee and the
/// measured one hold at the same time. Found on
/// `benchmark/reference/pizza-reference.owl`, where five individuals are
/// asserted this way.
const DECLARATION_TYPES: &[&str] = &[
"http://www.w3.org/2002/07/owl#Thing",
"http://www.w3.org/2000/01/rdf-schema#Resource",
"http://www.w3.org/2002/07/owl#Class",
"http://www.w3.org/2000/01/rdf-schema#Class",
"http://www.w3.org/2002/07/owl#ObjectProperty",
"http://www.w3.org/2002/07/owl#DatatypeProperty",
"http://www.w3.org/2002/07/owl#AnnotationProperty",
"http://www.w3.org/2002/07/owl#OntologyProperty",
"http://www.w3.org/1999/02/22-rdf-syntax-ns#Property",
"http://www.w3.org/2002/07/owl#NamedIndividual",
"http://www.w3.org/2002/07/owl#Ontology",
"http://www.w3.org/2000/01/rdf-schema#Datatype",
"http://www.w3.org/2002/07/owl#DataRange",
];
fn iri_of(term: &str) -> Option<&str> {
term.strip_prefix('<').and_then(|t| t.strip_suffix('>'))
}
fn is_bnode(term: &str) -> bool {
term.starts_with("_:")
}
fn is_literal(term: &str) -> bool {
term.starts_with('"')
}
fn is_builtin(iri: &str) -> bool {
iri.starts_with(RDF) || iri.starts_with(RDFS) || iri.starts_with(OWL) || iri.starts_with(XSD)
}
/// Allocation-free "is this exactly `owl:<local>`".
fn owl_is(iri: &str, local: &str) -> bool {
iri.strip_prefix(OWL) == Some(local)
}
fn rdfs_is(iri: &str, local: &str) -> bool {
iri.strip_prefix(RDFS) == Some(local)
}
fn rdf_is(iri: &str, local: &str) -> bool {
iri.strip_prefix(RDF) == Some(local)
}
// ───────────────────────────────────────────────────────────────────────────
// Expressions
// ───────────────────────────────────────────────────────────────────────────
/// Which symbol a name outside the signature is replaced by.
#[derive(Clone, Copy, Debug, PartialEq, Eq)]
pub enum Side {
/// `⊥`-locality: an external class becomes `owl:Nothing`, an external
/// property the empty property.
Bottom,
/// `⊤`-locality: an external class becomes `owl:Thing`, an external
/// property the universal property.
Top,
}
/// A class expression, as far as it could be read off the RDF.
#[derive(Clone, Debug)]
enum Ce {
Named(String),
Thing,
Nothing,
/// A datatype or data range. NOT a class name and NOT replaceable, so it is
/// neither `⊥`-equivalent nor `⊤`-equivalent under any signature. Treating
/// `xsd:integer` as an external class name and replacing it by `⊥` would
/// make `∃hasAge.xsd:integer` look local and drop the axiom: unsound, and
/// invisible, because the module still parses.
DataRange,
And(Vec<Ce>),
Or(Vec<Ce>),
Not(Box<Ce>),
/// `owl:oneOf`, carrying only the length: `{a₁ … aₙ}` is `⊥` exactly when
/// the list is empty, and is never `⊤`.
OneOf(usize),
Exists(Pe, Box<Ce>),
Forall(Pe, Box<Ce>),
HasValue(Pe),
HasSelf(Pe),
Min(u32, Pe, Box<Ce>),
/// `≤n R.C`. The number is deliberately NOT carried: `≤n R.C` is `⊤`
/// exactly when `R` is empty or `C` is empty, for EVERY `n`, and it is
/// never `⊥`, so the bound contributes nothing a locality test can read.
Max(Pe, Box<Ce>),
Exact(u32, Pe, Box<Ce>),
/// A term whose shape this file does not recognise. Neither `⊥` nor `⊤`,
/// which makes every axiom mentioning it non-local.
Unreadable,
}
/// A property expression.
#[derive(Clone, Debug)]
enum Pe {
Named(String),
/// `owl:inverseOf` applied to a named property. The locality of `R⁻` is the
/// locality of `R`.
Inverse(String),
TopProperty,
BottomProperty,
Unreadable,
}
#[derive(Clone, Copy, Debug, PartialEq, Eq)]
enum Characteristic {
Transitive,
Symmetric,
Asymmetric,
Reflexive,
Irreflexive,
Functional,
InverseFunctional,
}
impl Characteristic {
fn name(self) -> &'static str {
match self {
Characteristic::Transitive => "transitive_property",
Characteristic::Symmetric => "symmetric_property",
Characteristic::Asymmetric => "asymmetric_property",
Characteristic::Reflexive => "reflexive_property",
Characteristic::Irreflexive => "irreflexive_property",
Characteristic::Functional => "functional_property",
Characteristic::InverseFunctional => "inverse_functional_property",
}
}
}
/// The OWL 2 axiom a root triple was read as.
#[derive(Clone, Debug)]
enum Form {
SubClassOf(Ce, Ce),
EquivalentClasses(Vec<Ce>),
DisjointClasses(Vec<Ce>),
DisjointUnion(Ce, Vec<Ce>),
SubPropertyOf(Pe, Pe),
PropertyChain(Vec<Pe>, Pe),
EquivalentProperties(Vec<Pe>),
DisjointProperties(Vec<Pe>),
Domain(Pe, Ce),
Range(Pe, Ce),
InverseProperties(Pe, Pe),
Characteristic(Characteristic, Pe),
HasKey(Ce),
ClassAssertion(Ce),
PropertyAssertion(Pe),
NegativePropertyAssertion(Pe),
/// `owl:sameAs`, `owl:differentFrom`, `owl:AllDifferent`. These mention no
/// class and no property name, so NO replacement can make them tautologies
/// and they are never local.
IndividualIdentity(&'static str),
/// `X rdf:type owl:Class` and friends. Vacuous in the OWL 2 direct
/// semantics; NOT vacuous for the OWL 2 RL rule table this engine
/// evaluates, where `scm-cls` reads it as a premise. Kept whenever the
/// declared term is in the working signature, which is the conservative
/// reading of the two.
Declaration(String),
Annotation,
Unclassified(String),
}
impl Form {
fn kind(&self) -> &'static str {
match self {
Form::SubClassOf(..) => "sub_class_of",
Form::EquivalentClasses(..) => "equivalent_classes",
Form::DisjointClasses(..) => "disjoint_classes",
Form::DisjointUnion(..) => "disjoint_union",
Form::SubPropertyOf(..) => "sub_property_of",
Form::PropertyChain(..) => "property_chain",
Form::EquivalentProperties(..) => "equivalent_properties",
Form::DisjointProperties(..) => "disjoint_properties",
Form::Domain(..) => "property_domain",
Form::Range(..) => "property_range",
Form::InverseProperties(..) => "inverse_properties",
Form::Characteristic(k, _) => k.name(),
Form::HasKey(..) => "has_key",
Form::ClassAssertion(..) => "class_assertion",
Form::PropertyAssertion(..) => "property_assertion",
Form::NegativePropertyAssertion(..) => "negative_property_assertion",
Form::IndividualIdentity(w) => w,
Form::Declaration(..) => "declaration",
Form::Annotation => "annotation",
Form::Unclassified(..) => "unclassified",
}
}
}
/// One axiom: the triples that spell it, the form it was read as, and the
/// non-logical names it mentions.
struct Axiom {
triples: Vec<Spelled>,
form: Form,
signature: BTreeSet<String>,
/// The root triple, rendered, for the unclassified report.
root: String,
}
// ───────────────────────────────────────────────────────────────────────────
// Locality
// ───────────────────────────────────────────────────────────────────────────
type Sig = BTreeSet<String>;
fn c_bottom(c: &Ce, sig: &Sig, side: Side) -> bool {
match c {
Ce::Named(a) => side == Side::Bottom && !sig.contains(a),
Ce::Thing => false,
Ce::Nothing => true,
Ce::DataRange => false,
// An empty intersection is `owl:Thing`, so `any` is right: false on the
// empty list.
Ce::And(v) => v.iter().any(|x| c_bottom(x, sig, side)),
// An empty union is `owl:Nothing`, so `all` is right: true on the empty
// list.
Ce::Or(v) => v.iter().all(|x| c_bottom(x, sig, side)),
Ce::Not(x) => c_top(x, sig, side),
Ce::OneOf(n) => *n == 0,
Ce::Exists(p, f) => p_bottom(p, sig, side) || c_bottom(f, sig, side),
// `∀R.⊥` is "has no R-successor", which is satisfiable, so a universal
// restriction is never bottom-equivalent.
Ce::Forall(..) => false,
Ce::HasValue(p) => p_bottom(p, sig, side),
Ce::HasSelf(p) => p_bottom(p, sig, side),
Ce::Min(n, p, f) => *n >= 1 && (p_bottom(p, sig, side) || c_bottom(f, sig, side)),
Ce::Max(..) => false,
Ce::Exact(n, p, f) => *n >= 1 && (p_bottom(p, sig, side) || c_bottom(f, sig, side)),
Ce::Unreadable => false,
}
}
fn c_top(c: &Ce, sig: &Sig, side: Side) -> bool {
match c {
Ce::Named(a) => side == Side::Top && !sig.contains(a),
Ce::Thing => true,
Ce::Nothing => false,
Ce::DataRange => false,
Ce::And(v) => v.iter().all(|x| c_top(x, sig, side)),
Ce::Or(v) => v.iter().any(|x| c_top(x, sig, side)),
Ce::Not(x) => c_bottom(x, sig, side),
Ce::OneOf(_) => false,
Ce::Exists(p, f) => p_top(p, sig, side) && c_top(f, sig, side),
Ce::Forall(p, f) => c_top(f, sig, side) || p_bottom(p, sig, side),
Ce::HasValue(p) => p_top(p, sig, side),
Ce::HasSelf(p) => p_top(p, sig, side),
// `≥0 R.C` is `⊤`, and `≥1 ⊤.⊤` is `⊤` because the domain is non-empty.
// `≥2 ⊤.⊤` is NOT, in a one-element domain, so it is left non-top.
Ce::Min(n, p, f) => *n == 0 || (*n == 1 && p_top(p, sig, side) && c_top(f, sig, side)),
Ce::Max(p, f) => p_bottom(p, sig, side) || c_bottom(f, sig, side),
Ce::Exact(n, p, f) => *n == 0 && (p_bottom(p, sig, side) || c_bottom(f, sig, side)),
Ce::Unreadable => false,
}
}
fn p_bottom(p: &Pe, sig: &Sig, side: Side) -> bool {
match p {
Pe::Named(x) | Pe::Inverse(x) => side == Side::Bottom && !sig.contains(x),
Pe::TopProperty => false,
Pe::BottomProperty => true,
Pe::Unreadable => false,
}
}
fn p_top(p: &Pe, sig: &Sig, side: Side) -> bool {
match p {
Pe::Named(x) | Pe::Inverse(x) => side == Side::Top && !sig.contains(x),
Pe::TopProperty => true,
Pe::BottomProperty => false,
Pe::Unreadable => false,
}
}
/// Is this axiom a tautology once every name outside `sig` has been replaced?
fn is_local(a: &Axiom, sig: &Sig, side: Side) -> bool {
let cb = |c: &Ce| c_bottom(c, sig, side);
let ct = |c: &Ce| c_top(c, sig, side);
let pb = |p: &Pe| p_bottom(p, sig, side);
let pt = |p: &Pe| p_top(p, sig, side);
match &a.form {
Form::SubClassOf(c, d) => cb(c) || ct(d),
Form::EquivalentClasses(v) => v.iter().all(cb) || v.iter().all(ct),
// `Disjoint(C₁ … Cₙ)` is a tautology when at most one operand is
// non-empty: nothing overlaps `⊥`.
Form::DisjointClasses(v) => v.iter().filter(|c| !cb(c)).count() <= 1,
Form::DisjointUnion(a, v) => cb(a) && v.iter().all(cb),
Form::SubPropertyOf(p, q) => pb(p) || pt(q),
Form::PropertyChain(chain, q) => pt(q) || chain.iter().any(pb),
Form::EquivalentProperties(v) => v.iter().all(pb) || v.iter().all(pt),
Form::DisjointProperties(v) => v.iter().filter(|p| !pb(p)).count() <= 1,
Form::Domain(p, c) => pb(p) || ct(c),
Form::Range(p, c) => pb(p) || ct(c),
Form::InverseProperties(p, q) => (pb(p) && pb(q)) || (pt(p) && pt(q)),
Form::Characteristic(k, p) => match k {
// The universal property is transitive and symmetric; the empty one
// vacuously is.
Characteristic::Transitive | Characteristic::Symmetric => pb(p) || pt(p),
// Only the universal property is reflexive.
Characteristic::Reflexive => pt(p),
// The universal property is none of these; the empty one is all of
// them, vacuously.
Characteristic::Asymmetric
| Characteristic::Irreflexive
| Characteristic::Functional
| Characteristic::InverseFunctional => pb(p),
},
Form::HasKey(c) => cb(c),
Form::ClassAssertion(c) => ct(c),
Form::PropertyAssertion(p) => pt(p),
Form::NegativePropertyAssertion(p) => pb(p),
Form::IndividualIdentity(_) => false,
// The empty name belongs to a declaration whose subject is not an IRI,
// which is not a shape this file reads. `!sig.contains("")` would be
// true against EVERY signature, so the empty case is spelled out rather
// than left to fall through to "local".
Form::Declaration(iri) => !iri.is_empty() && !sig.contains(iri),
Form::Annotation => true,
Form::Unclassified(_) => false,
}
}
// ───────────────────────────────────────────────────────────────────────────
// Reading axioms out of RDF
// ───────────────────────────────────────────────────────────────────────────
/// How deep a class expression is followed before it is declared unreadable. A
/// cyclic blank-node structure is illegal OWL and legal RDF, so this is a
/// termination guard rather than an expressiveness limit.
const MAX_DEPTH: usize = 40;
/// Longest `rdf:List` followed. Beyond it the list is unreadable, which makes
/// the axiom non-local, which includes it.
const MAX_LIST: usize = 5_000;
struct Index {
triples: Vec<Spelled>,
by_subject: HashMap<String, Vec<usize>>,
object_terms: HashSet<String>,
/// Annotation predicates this ontology has given logical force, by
/// declaring a domain, a range, a superproperty or an equivalent for them.
/// Assertions over these are read as property assertions, not annotations.
loaded_annotation_predicates: BTreeSet<String>,
}
impl Index {
fn build(store: &Arc<GraphStore>) -> anyhow::Result<Index> {
let triples = store.all_triples()?;
let mut by_subject: HashMap<String, Vec<usize>> = HashMap::new();
let mut object_terms: HashSet<String> = HashSet::new();
for (i, (s, _, o)) in triples.iter().enumerate() {
by_subject.entry(s.clone()).or_default().push(i);
object_terms.insert(o.clone());
}
// An annotation property with a domain, a range, a superproperty or an
// equivalent is not an annotation property any more, whatever OWL 2
// says: the rule table will read assertions over it.
let mut loaded_annotation_predicates = BTreeSet::new();
for (s, p, _) in &triples {
let (Some(si), Some(pi)) = (iri_of(s), iri_of(p)) else { continue };
let loading = rdfs_is(pi, "domain")
|| rdfs_is(pi, "range")
|| rdfs_is(pi, "subPropertyOf")
|| owl_is(pi, "equivalentProperty");
if loading && ANNOTATION_PREDICATES.contains(&si) {
loaded_annotation_predicates.insert(si.to_string());
}
}
Ok(Index { triples, by_subject, object_terms, loaded_annotation_predicates })
}
/// Triple indices with this subject. Elision ties the borrow to `&self`,
/// not to `subject`, which is what lets the results be returned.
fn rows(&self, subject: &str) -> &[usize] {
self.by_subject.get(subject).map(Vec::as_slice).unwrap_or(&[])
}
/// The first object of `subject <predicate> ?`, where `predicate` is
/// matched by a closure so no IRI has to be allocated to look one up.
fn object_where(&self, subject: &str, matches: impl Fn(&str) -> bool) -> Option<&str> {
self.rows(subject)
.iter()
.map(|i| &self.triples[*i])
.find(|t| iri_of(&t.1).is_some_and(&matches))
.map(|t| t.2.as_str())
}
fn owl_object(&self, subject: &str, local: &'static str) -> Option<&str> {
self.object_where(subject, move |p| owl_is(p, local))
}
fn has_type(&self, subject: &str, is_type: impl Fn(&str) -> bool) -> bool {
self.rows(subject).iter().any(|i| {
let t = &self.triples[*i];
iri_of(&t.1).is_some_and(|p| rdf_is(p, "type"))
&& iri_of(&t.2).is_some_and(&is_type)
})
}
/// Follow an `rdf:List`. `None` when the structure is not a well-formed
/// list, which makes the containing axiom unreadable and therefore
/// non-local.
fn list(&self, head: &str) -> Option<Vec<String>> {
let mut out = Vec::new();
let mut cur = head.to_string();
let mut seen: HashSet<String> = HashSet::new();
while !iri_of(&cur).is_some_and(|i| rdf_is(i, "nil")) {
if out.len() > MAX_LIST || !seen.insert(cur.clone()) {
return None;
}
let f = self.object_where(&cur, |p| rdf_is(p, "first"))?.to_string();
out.push(f);
cur = self.object_where(&cur, |p| rdf_is(p, "rest"))?.to_string();
}
Some(out)
}
/// True when the term denotes a data range rather than a class.
fn is_data_range(&self, term: &str) -> bool {
if is_literal(term) {
return true;
}
if let Some(i) = iri_of(term) {
return i.starts_with(XSD) || rdfs_is(i, "Literal");
}
if is_bnode(term) {
return self.has_type(term, |t| rdfs_is(t, "Datatype"))
|| self.owl_object(term, "onDatatype").is_some()
|| self.owl_object(term, "datatypeComplementOf").is_some()
|| self.owl_object(term, "withRestrictions").is_some();
}
false
}
fn property_expr(&self, term: &str) -> Pe {
if let Some(i) = iri_of(term) {
if owl_is(i, "topObjectProperty") || owl_is(i, "topDataProperty") {
return Pe::TopProperty;
}
if owl_is(i, "bottomObjectProperty") || owl_is(i, "bottomDataProperty") {
return Pe::BottomProperty;
}
return Pe::Named(i.to_string());
}
if is_bnode(term)
&& let Some(inner) = self.owl_object(term, "inverseOf")
&& let Some(i) = iri_of(inner)
{
return Pe::Inverse(i.to_string());
}
Pe::Unreadable
}
fn class_expr(&self, term: &str, depth: usize) -> Ce {
if depth > MAX_DEPTH {
return Ce::Unreadable;
}
if self.is_data_range(term) {
return Ce::DataRange;
}
if let Some(i) = iri_of(term) {
if owl_is(i, "Thing") {
return Ce::Thing;
}
if owl_is(i, "Nothing") {
return Ce::Nothing;
}
return Ce::Named(i.to_string());
}
if !is_bnode(term) {
return Ce::Unreadable;
}
for (pred, wrap) in [
("intersectionOf", true),
("unionOf", false),
] {
if let Some(head) = self.owl_object(term, pred) {
let Some(items) = self.list(head) else { return Ce::Unreadable };
let v: Vec<Ce> = items.iter().map(|t| self.class_expr(t, depth + 1)).collect();
return if wrap { Ce::And(v) } else { Ce::Or(v) };
}
}
if let Some(c) = self.owl_object(term, "complementOf") {
return Ce::Not(Box::new(self.class_expr(c, depth + 1)));
}
if let Some(head) = self.owl_object(term, "oneOf") {
return match self.list(head) {
Some(items) => Ce::OneOf(items.len()),
None => Ce::Unreadable,
};
}
// A restriction. `owl:onProperties` is the n-ary data form and is not
// read here, so it falls through to Unreadable and is included.
let Some(on_property) = self.owl_object(term, "onProperty") else {
return Ce::Unreadable;
};
let p = self.property_expr(on_property);
if let Some(f) = self.owl_object(term, "someValuesFrom") {
return Ce::Exists(p, Box::new(self.class_expr(f, depth + 1)));
}
if let Some(f) = self.owl_object(term, "allValuesFrom") {
return Ce::Forall(p, Box::new(self.class_expr(f, depth + 1)));
}
if self.owl_object(term, "hasValue").is_some() {
return Ce::HasValue(p);
}
if self.owl_object(term, "hasSelf").is_some() {
return Ce::HasSelf(p);
}
let qualifier = self
.owl_object(term, "onClass")
.or_else(|| self.owl_object(term, "onDataRange"))
.map(|f| self.class_expr(f, depth + 1))
.unwrap_or(Ce::Thing);
let card = |local: &'static str| -> Option<u32> {
let raw = self.owl_object(term, local)?;
raw.strip_prefix('"')?.split('"').next()?.parse::<u32>().ok()
};
for (unqualified, qualified, build) in [
("minCardinality", "minQualifiedCardinality", 0u8),
("maxCardinality", "maxQualifiedCardinality", 1),
("cardinality", "qualifiedCardinality", 2),
] {
let found = card(unqualified)
.map(|n| (n, Ce::Thing))
.or_else(|| card(qualified).map(|n| (n, qualifier.clone())));
if let Some((n, f)) = found {
return match build {
0 => Ce::Min(n, p, Box::new(f)),
1 => Ce::Max(p, Box::new(f)),
_ => Ce::Exact(n, p, Box::new(f)),
};
}
}
Ce::Unreadable
}
/// Every triple the axiom rooted at `root_index` spells: the root, plus the
/// transitive blank-node structure it reaches.
fn axiom_triples(&self, root_index: usize) -> Vec<Spelled> {
let mut out: BTreeSet<Spelled> = BTreeSet::new();
let root = &self.triples[root_index];
out.insert(root.clone());
let mut seen: HashSet<String> = HashSet::new();
let mut stack: Vec<String> = [&root.0, &root.2]
.into_iter()
.filter(|t| is_bnode(t))
.cloned()
.collect();
while let Some(b) = stack.pop() {
if !seen.insert(b.clone()) {
continue;
}
for i in self.rows(&b) {
let t = &self.triples[*i];
out.insert(t.clone());
if is_bnode(&t.2) {
stack.push(t.2.clone());
}
}
}
out.into_iter().collect()
}
}
/// The non-logical names a set of triples mentions.
fn signature_of(triples: &[Spelled]) -> BTreeSet<String> {
let mut out = BTreeSet::new();
for (s, p, o) in triples {
for t in [s, p, o] {
if let Some(i) = iri_of(t)
&& !is_builtin(i)
{
out.insert(i.to_string());
}
}
}
out
}
fn render(t: &Spelled) -> String {
format!("{} {} {}", t.0, t.1, t.2)
}
/// Read the store as a list of axioms.
fn axioms_of(ix: &Index) -> Vec<Axiom> {
let mut out = Vec::new();
for i in 0..ix.triples.len() {
let (s, p, o) = &ix.triples[i];
// A blank node some other triple points at is part of the axiom that
// points at it, not an axiom of its own.
if is_bnode(s) && ix.object_terms.contains(s) {
continue;
}
let Some(pi) = iri_of(p) else { continue };
let form = if is_bnode(s) {
bnode_rooted_form(ix, s, pi, o, i)
} else {
let mut f = iri_rooted_form(ix, pi, o);
if let Some(f) = f.as_mut() {
finish_subject(ix, f, s);
}
f
};
let Some(form) = form else { continue };
let triples = ix.axiom_triples(i);
let signature = signature_of(&triples);
out.push(Axiom { triples, form, signature, root: render(&ix.triples[i]) });
}
out
}
/// A blank-node-rooted axiom: `owl:AllDisjointClasses` and friends.
///
/// Exactly ONE triple of the structure becomes the axiom — the `rdf:type` one —
/// so the structure is not read once per triple. A structure with no
/// `rdf:type` at all is rooted at its first triple and reported unclassified,
/// which includes it.
fn bnode_rooted_form(ix: &Index, s: &str, pi: &str, o: &str, row: usize) -> Option<Form> {
if !rdf_is(pi, "type") {
if ix.has_type(s, |_| true) {
return None;
}
if ix.rows(s).first() != Some(&row) {
return None;
}
return Some(Form::Unclassified(format!("orphan blank-node structure on <{pi}>")));
}
let oi = iri_of(o).unwrap_or("");
let members = || ix.owl_object(s, "members").and_then(|h| ix.list(h));
if owl_is(oi, "AllDisjointClasses") {
return Some(match members() {
Some(v) => Form::DisjointClasses(v.iter().map(|t| ix.class_expr(t, 0)).collect()),
None => {
Form::Unclassified("owl:AllDisjointClasses with an unreadable member list".into())
}
});
}
if owl_is(oi, "AllDisjointProperties") {
return Some(match members() {
Some(v) => Form::DisjointProperties(v.iter().map(|t| ix.property_expr(t)).collect()),
None => {
Form::Unclassified("owl:AllDisjointProperties with an unreadable member list".into())
}
});
}
if owl_is(oi, "AllDifferent") {
return Some(Form::IndividualIdentity("different_individuals"));
}
if owl_is(oi, "NegativePropertyAssertion") {
return Some(match ix.owl_object(s, "assertionProperty") {
Some(p) => Form::NegativePropertyAssertion(ix.property_expr(p)),
None => Form::Unclassified(
"owl:NegativePropertyAssertion with no owl:assertionProperty".into(),
),
});
}
if owl_is(oi, "Axiom") {
// Axiom reification annotates an axiom that is also asserted in its own
// right, so it carries no consequence of its own.
return Some(Form::Annotation);
}
Some(Form::Unclassified(format!("blank-node-rooted structure of type <{oi}>")))
}
fn iri_rooted_form(ix: &Index, pi: &str, o: &str) -> Option<Form> {
let ce = |t: &str| ix.class_expr(t, 0);
let pe = |t: &str| ix.property_expr(t);
if rdfs_is(pi, "subClassOf") {
return Some(Form::SubClassOf(Ce::Unreadable, ce(o)));
}
if owl_is(pi, "equivalentClass") {
return Some(Form::EquivalentClasses(vec![Ce::Unreadable, ce(o)]));
}
if owl_is(pi, "disjointWith") {
return Some(Form::DisjointClasses(vec![Ce::Unreadable, ce(o)]));
}
if owl_is(pi, "disjointUnionOf") {
return Some(match ix.list(o) {
Some(v) => Form::DisjointUnion(Ce::Unreadable, v.iter().map(|x| ce(x)).collect()),
None => Form::Unclassified("owl:disjointUnionOf with an unreadable list".into()),
});
}
if rdfs_is(pi, "subPropertyOf") {
return Some(Form::SubPropertyOf(Pe::Unreadable, pe(o)));
}
if owl_is(pi, "propertyChainAxiom") {
return Some(match ix.list(o) {
Some(v) => Form::PropertyChain(v.iter().map(|x| pe(x)).collect(), Pe::Unreadable),
None => Form::Unclassified("owl:propertyChainAxiom with an unreadable list".into()),
});
}
if owl_is(pi, "equivalentProperty") {
return Some(Form::EquivalentProperties(vec![Pe::Unreadable, pe(o)]));
}
if owl_is(pi, "propertyDisjointWith") {
return Some(Form::DisjointProperties(vec![Pe::Unreadable, pe(o)]));
}
if rdfs_is(pi, "domain") {
return Some(Form::Domain(Pe::Unreadable, ce(o)));
}
if rdfs_is(pi, "range") {
return Some(Form::Range(Pe::Unreadable, ce(o)));
}
if owl_is(pi, "inverseOf") {
return Some(Form::InverseProperties(Pe::Unreadable, pe(o)));
}
if owl_is(pi, "hasKey") {
return Some(Form::HasKey(Ce::Unreadable));
}
if owl_is(pi, "sameAs") {
return Some(Form::IndividualIdentity("same_individual"));
}
if owl_is(pi, "differentFrom") {
return Some(Form::IndividualIdentity("different_individuals"));
}
if rdf_is(pi, "type") {
return Some(type_form(ix, o));
}
if ANNOTATION_PREDICATES.contains(&pi) && !ix.loaded_annotation_predicates.contains(pi) {
return Some(Form::Annotation);
}
// Anything left in the RDF, RDFS, OWL or XSD namespaces is OWL vocabulary
// this file does not classify. It is NOT read as a property assertion,
// because an unrecognised `owl:` predicate could carry logical force, and
// reading it as an assertion would make it `⊤`-local and drop it.
if is_builtin(pi) {
return Some(Form::Unclassified(format!("unclassified built-in predicate <{pi}>")));
}
Some(Form::PropertyAssertion(Pe::Named(pi.to_string())))
}
/// `X rdf:type Y`: a declaration, a property characteristic, or a class
/// assertion.
fn type_form(ix: &Index, o: &str) -> Form {
let Some(oi) = iri_of(o) else {
return Form::ClassAssertion(ix.class_expr(o, 0));
};
if DECLARATION_TYPES.contains(&oi) {
// The declared term is the subject, filled in by `finish_subject`.
return Form::Declaration(String::new());
}
for (local, k) in [
("TransitiveProperty", Characteristic::Transitive),
("SymmetricProperty", Characteristic::Symmetric),
("AsymmetricProperty", Characteristic::Asymmetric),
("ReflexiveProperty", Characteristic::Reflexive),
("IrreflexiveProperty", Characteristic::Irreflexive),
("FunctionalProperty", Characteristic::Functional),
("InverseFunctionalProperty", Characteristic::InverseFunctional),
] {
if owl_is(oi, local) {
return Form::Characteristic(k, Pe::Unreadable);
}
}
// `owl:Restriction` and the other structural types reached at a ROOT mean a
// blank node nothing points at, or an IRI used as one: not a shape this
// file reads, so it is included rather than guessed at.
if oi.starts_with(OWL) && !owl_is(oi, "Thing") && !owl_is(oi, "Nothing") {
return Form::Unclassified(format!("rdf:type <{oi}> at an axiom root"));
}
Form::ClassAssertion(ix.class_expr(o, 0))
}
/// Fill in the subject side of a form parsed from the object side only.
/// Splitting it this way keeps ONE place where the subject is read.
fn finish_subject(ix: &Index, form: &mut Form, subject: &str) {
match form {
Form::SubClassOf(c, _) => *c = ix.class_expr(subject, 0),
Form::EquivalentClasses(v) | Form::DisjointClasses(v) => v[0] = ix.class_expr(subject, 0),
Form::DisjointUnion(c, _) | Form::HasKey(c) => *c = ix.class_expr(subject, 0),
Form::SubPropertyOf(p, _) => *p = ix.property_expr(subject),
Form::PropertyChain(_, q) => *q = ix.property_expr(subject),
Form::EquivalentProperties(v) | Form::DisjointProperties(v) => {
v[0] = ix.property_expr(subject)
}
Form::Domain(p, _) | Form::Range(p, _) => *p = ix.property_expr(subject),
Form::InverseProperties(p, _) => *p = ix.property_expr(subject),
Form::Characteristic(_, p) => *p = ix.property_expr(subject),
Form::Declaration(name) => *name = iri_of(subject).unwrap_or_default().to_string(),
_ => {}
}
}
// ───────────────────────────────────────────────────────────────────────────
// Extraction
// ───────────────────────────────────────────────────────────────────────────
/// Which module to extract.
#[derive(Clone, Copy, Debug, PartialEq, Eq, Serialize, Deserialize)]
#[serde(rename_all = "snake_case")]
pub enum Locality {
Bottom,
Top,
/// The iterated `⊥⊤*`: alternate the two until the set stops shrinking.
/// Never larger than either, and usually smaller than both.
Star,
}
impl Locality {
pub fn parse(s: &str) -> anyhow::Result<Locality> {
match s {
"bottom" | "⊥" => Ok(Locality::Bottom),
"top" | "⊤" => Ok(Locality::Top),
"star" | "bottom-top-star" | "⊥⊤*" => Ok(Locality::Star),
other => anyhow::bail!(
"unknown locality {other:?}: pass \"bottom\", \"top\" or \"star\" (the iterated ⊥⊤*)"
),
}
}
pub fn name(self) -> &'static str {
match self {
Locality::Bottom => "bottom",
Locality::Top => "top",
Locality::Star => "star",
}
}
pub fn symbol(self) -> &'static str {
match self {
Locality::Bottom => "⊥",
Locality::Top => "⊤",
Locality::Star => "⊥⊤*",
}
}
}
/// One extraction pass, run to a fixpoint.
///
/// The fixpoint is not an optimisation, it is the SOUNDNESS CONDITION. The
/// working signature grows with every axiom taken, and an axiom that looked
/// local against `Σ` stops being local once a name it mentions has been pulled
/// in. Stopping after one sweep would drop `a p₁ b` from a module that kept
/// `p₁ ⊑ p₂`, and so lose `a p₂ b` over a signature containing `p₂`, `a` and
/// `b`. `the_top_pass_iterates_rather_than_sweeping_once` pins the case.
/// An axiom's locality depends only on which of the names IT MENTIONS are in
/// the signature, so it can only stop being local when one of those names is
/// added. That is what makes the index below correct and the naive rescan
/// unnecessary: re-sweeping every axiom after every addition is quadratic, and
/// an ontology of a hundred thousand axioms is not a hypothetical.
fn extract_once(axioms: &[Axiom], over: &[usize], sigma: &Sig, side: Side) -> Vec<usize> {
let candidates: HashSet<usize> = over.iter().copied().collect();
let mut by_symbol: HashMap<&str, Vec<usize>> = HashMap::new();
for &i in over {
for s in &axioms[i].signature {
by_symbol.entry(s.as_str()).or_default().push(i);
}
}
let mut work = sigma.clone();
let mut taken: HashSet<usize> = HashSet::new();
// Everything is tested once; after that, only what a newly admitted name
// could have changed.
let mut queue: Vec<usize> = over.to_vec();
while let Some(i) = queue.pop() {
if !candidates.contains(&i) || taken.contains(&i) || is_local(&axioms[i], &work, side) {
continue;
}
taken.insert(i);
for s in &axioms[i].signature {
if work.insert(s.clone())
&& let Some(v) = by_symbol.get(s.as_str())
{
queue.extend(v.iter().copied());
}
}
}
let mut out: Vec<usize> = taken.into_iter().collect();
out.sort_unstable();
out
}
// ───────────────────────────────────────────────────────────────────────────
// Options and report
// ───────────────────────────────────────────────────────────────────────────
#[derive(Clone, Debug)]
pub struct ModuleOptions {
/// The IRIs the module must cover.
pub signature: Vec<String>,
pub locality: Locality,
/// Re-attach `rdfs:label`, `rdfs:comment` and the other annotation
/// assertions for terms the module keeps. They are NOT part of the logical
/// module and are counted separately, so the reported module size stays the
/// logical one.
pub include_annotations: bool,
/// Rows rendered per list. Totals are always exact.
pub max_rows: usize,
}
impl Default for ModuleOptions {
fn default() -> Self {
ModuleOptions {
signature: Vec::new(),
locality: Locality::Star,
include_annotations: false,
max_rows: 200,
}
}
}
/// An axiom taken into the module because this file could not classify it.
#[derive(Clone, Debug, Serialize)]
pub struct UnclassifiedAxiom {
pub root_triple: String,
pub why: String,
pub triples: usize,
}
#[derive(Clone, Debug, Serialize)]
pub struct ModuleReport {
pub format: &'static str,
/// One sentence the reader cannot miss, first after `format`.
pub headline: String,
pub locality: &'static str,
pub locality_symbol: &'static str,
/// What the module guarantees, and whose theorem it is.
pub guarantee: &'static str,
/// The word that is NOT used, spelled out so it cannot be inferred.
pub guarantee_is_not_machine_checked: &'static str,
/// Axiom kinds whose locality was decided by a test written for that kind.
pub guarantee_covers: Vec<&'static str>,
/// Axiom kinds taken into the module WITHOUT a locality test, because no
/// replacement could make them tautologies or because they could not be
/// classified. Including is the safe direction; the counts are here so that
/// a small module and an unreadable one cannot render the same.
pub included_conservatively: BTreeMap<String, usize>,
pub unclassified_axioms: Vec<UnclassifiedAxiom>,
pub unclassified_total: usize,
pub signature_requested: Vec<String>,
/// Names in `signature_requested` that occur nowhere in the ontology. A
/// module over a misspelled IRI is empty and correct, which is the most
/// expensive way to learn about a typo.
pub signature_not_in_ontology: Vec<String>,
/// `Σ ∪ sig(M)`: everything the module's guarantee actually ranges over.
pub signature_closure: Vec<String>,
pub signature_closure_size: usize,
pub ontology_axioms: usize,
pub module_axioms: usize,
pub ontology_triples: usize,
pub module_triples: usize,
/// `module_triples / ontology_triples`, for reading only. It is NOT a
/// quality score: a module is not better for being smaller, it is correct
/// or it is not, and the size is what the signature costs.
pub module_fraction: f64,
pub axioms_by_kind: BTreeMap<String, usize>,
pub annotation_triples_added: usize,
/// The predicates this run treated as carrying no logical content, so a
/// reader can see exactly what "annotation" meant here. An annotation
/// predicate the ontology gave a domain, a range, a superproperty or an
/// equivalent is NOT in this list: it was read as a property assertion
/// instead, because the rule table will read it as one.
pub annotation_predicates_treated_as_vacuous: Vec<String>,
/// `⊥⊤` rounds. One for a plain `⊥` or `⊤` extraction.
pub rounds: usize,
pub module_ttl: String,
pub seconds: f64,
}
pub const GUARANTEE: &str =
"every axiom over the requested signature that the whole ontology entails, the module entails, \
and nothing else: M ⊨ α iff O ⊨ α for every α over Σ. That is the locality theorem of Cuenca \
Grau, Horrocks, Kazakov and Sattler (JAIR 31, 2008, 'Modular Reuse of Ontologies: Theory and \
Practice'), which holds for OWL 2 DL and therefore for every profile inside it. It is a \
COVERAGE guarantee and not a MINIMALITY one: a locality module is the smallest set the \
syntactic test can justify, not the smallest set that would do.";
pub const NOT_MACHINE_CHECKED: &str =
"the locality theorem is CITED, not checked: nothing under lean/ is about syntactic locality, \
so this report names a paper and never names a Lean theorem. What can be checked here is the \
consequence rather than the theorem, and that is what verify_out_dir does — it reasons the \
whole ontology and the module to a fixpoint under one rule table and reports every conclusion \
over the signature the module does not reach, which must be none.";
/// Axiom kinds with a locality test written for them.
pub const CLASSIFIED_KINDS: &[&str] = &[
"sub_class_of",
"equivalent_classes",
"disjoint_classes",
"disjoint_union",
"sub_property_of",
"property_chain",
"equivalent_properties",
"disjoint_properties",
"property_domain",
"property_range",
"inverse_properties",
"transitive_property",
"symmetric_property",
"asymmetric_property",
"reflexive_property",
"irreflexive_property",
"functional_property",
"inverse_functional_property",
"has_key",
"class_assertion",
"property_assertion",
"negative_property_assertion",
"declaration",
"annotation",
];
/// Axiom kinds that are never local, so they are always in the module.
pub const ALWAYS_INCLUDED_KINDS: &[&str] =
&["same_individual", "different_individuals", "unclassified"];
// ───────────────────────────────────────────────────────────────────────────
// The entry point
// ───────────────────────────────────────────────────────────────────────────
pub fn extract_module(
store: &Arc<GraphStore>,
opts: &ModuleOptions,
) -> anyhow::Result<ModuleReport> {
let started = std::time::Instant::now();
if opts.signature.is_empty() {
anyhow::bail!(
"the signature is empty. The module over the empty signature is the set of axioms no \
replacement can turn into a tautology, which is a real answer and never the one \
anybody wanted: pass the IRIs the module has to cover"
);
}
let ix = Index::build(store)?;
let axioms = axioms_of(&ix);
let sigma: Sig = opts.signature.iter().cloned().collect();
let present: BTreeSet<String> = signature_of(&ix.triples);
let signature_not_in_ontology: Vec<String> =
sigma.iter().filter(|s| !present.contains(*s)).cloned().collect();
let all: Vec<usize> = (0..axioms.len()).collect();
let (module, rounds) = match opts.locality {
Locality::Bottom => (extract_once(&axioms, &all, &sigma, Side::Bottom), 1),
Locality::Top => (extract_once(&axioms, &all, &sigma, Side::Top), 1),
Locality::Star => {
let mut current = all;
let mut rounds = 0usize;
loop {
rounds += 1;
let b = extract_once(&axioms, ¤t, &sigma, Side::Bottom);
let t = extract_once(&axioms, &b, &sigma, Side::Top);
// Each pass only ever removes, so the length strictly decreases
// until the fixpoint and this terminates.
let done = t.len() == current.len();
current = t;
if done {
break;
}
}
(current, rounds)
}
};
let mut module_triples: BTreeSet<Spelled> = BTreeSet::new();
let mut by_kind: BTreeMap<String, usize> = BTreeMap::new();
let mut conservative: BTreeMap<String, usize> = BTreeMap::new();
let mut unclassified: Vec<UnclassifiedAxiom> = Vec::new();
let mut unclassified_total = 0usize;
let mut closure: BTreeSet<String> = sigma.clone();
for &i in &module {
let a = &axioms[i];
module_triples.extend(a.triples.iter().cloned());
closure.extend(a.signature.iter().cloned());
let kind = a.form.kind();
*by_kind.entry(kind.to_string()).or_default() += 1;
if ALWAYS_INCLUDED_KINDS.contains(&kind) {
*conservative.entry(kind.to_string()).or_default() += 1;
}
if let Form::Unclassified(why) = &a.form {
unclassified_total += 1;
if unclassified.len() < opts.max_rows {
unclassified.push(UnclassifiedAxiom {
root_triple: a.root.clone(),
why: why.clone(),
triples: a.triples.len(),
});
}
}
}
let mut annotation_triples_added = 0usize;
if opts.include_annotations {
for a in &axioms {
if !matches!(a.form, Form::Annotation) {
continue;
}
let kept = a
.triples
.first()
.and_then(|t| iri_of(&t.0))
.is_some_and(|s| closure.contains(s));
if kept {
for t in &a.triples {
if module_triples.insert(t.clone()) {
annotation_triples_added += 1;
}
}
}
}
}
let module_ttl: String = module_triples.iter().map(|t| format!("{} .\n", render(t))).collect();
let ontology_triples = ix.triples.len();
let module_fraction = if ontology_triples == 0 {
0.0
} else {
module_triples.len() as f64 / ontology_triples as f64
};
let headline = format!(
"the {} module over {} requested name(s) is {} of {} axioms and {} of {} triples. {} \
axiom(s) were taken in WITHOUT a locality test because they could not be classified. {}",
opts.locality.symbol(),
opts.signature.len(),
module.len(),
axioms.len(),
module_triples.len(),
ontology_triples,
unclassified_total,
GUARANTEE,
);
Ok(ModuleReport {
format: "oo-locality-module/1",
headline,
locality: opts.locality.name(),
locality_symbol: opts.locality.symbol(),
guarantee: GUARANTEE,
guarantee_is_not_machine_checked: NOT_MACHINE_CHECKED,
guarantee_covers: CLASSIFIED_KINDS.to_vec(),
included_conservatively: conservative,
unclassified_axioms: unclassified,
unclassified_total,
signature_requested: opts.signature.clone(),
signature_not_in_ontology,
signature_closure_size: closure.len(),
signature_closure: closure.into_iter().collect(),
ontology_axioms: axioms.len(),
module_axioms: module.len(),
ontology_triples,
module_triples: module_triples.len(),
module_fraction,
axioms_by_kind: by_kind,
annotation_triples_added,
annotation_predicates_treated_as_vacuous: ANNOTATION_PREDICATES
.iter()
.filter(|p| !ix.loaded_annotation_predicates.contains(**p))
.map(|p| p.to_string())
.collect(),
rounds,
module_ttl,
seconds: started.elapsed().as_secs_f64(),
})
}
// ───────────────────────────────────────────────────────────────────────────
// Exercising the guarantee instead of asserting it
// ───────────────────────────────────────────────────────────────────────────
/// What the closure diff said about a module, filtered to the signature the
/// module is supposed to cover.
#[derive(Clone, Debug, Serialize)]
pub struct ModuleVerification {
pub format: &'static str,
pub headline: String,
pub profile: String,
/// The one number that matters. A locality module may not lose ANY of
/// these, so a non-zero value is a defect in the extractor rather than a
/// property of the ontology.
pub lost_over_signature_total: usize,
pub lost_over_signature: Vec<crate::closure_diff::LostEntailment>,
/// Triples over the signature whose predicate is one of
/// `annotation_predicates_treated_as_vacuous`. They ARE gone from the
/// module and they are NOT entailment losses: the extractor drops them
/// deliberately, and it only calls a predicate vacuous after checking that
/// the ontology gives it no domain, range, superproperty or equivalent, so
/// no rule in the table can read one as a premise. Counted separately
/// rather than filtered out, because a silent filter is how a real loss
/// would eventually hide here.
pub lost_over_signature_annotation_only: usize,
pub annotation_losses_are_not_entailment_losses: &'static str,
/// Conclusions the module does not reach whose terms are NOT all in the
/// signature closure. Expected and unremarkable: that is what a module is
/// for.
pub lost_outside_signature_total: usize,
/// The BLIND SPOT, counted rather than left to be discovered. A subset of
/// `lost_outside_signature_total`, and one that could not have landed
/// anywhere else: a conclusion carrying a blank node or a Skolem IRI has no
/// term whose name means the same thing on both sides, so the signature
/// question cannot be ASKED of it, let alone answered. A large number here
/// means a `lost_over_signature_total: 0` covers less of the ontology than
/// it looks.
pub not_decided_blank_node_bearing: usize,
pub blind_spot_means: &'static str,
/// Conclusions the diff did not look at, because it renders at most
/// `max_rows` of them. Non-zero means this verification is a SAMPLE and
/// `lost_over_signature_total: 0` does not mean "nothing was lost".
pub not_examined: usize,
/// The engine's own soundness gate, run for free by the closure diff.
pub engine_soundness_violations: usize,
pub source_certificate: crate::closure_diff::CertificateVerdict,
pub means: &'static str,
pub seconds: f64,
}
pub const ANNOTATION_LOSSES_MEAN: &str =
"an rdfs:label or rdfs:comment the module drops is not a lost entailment: no rule in the table \
reads one as a premise, which is checked rather than assumed — a predicate the ontology gives \
a domain, a range, a superproperty or an equivalent is NOT counted here and is kept as a \
property assertion instead. Pass include_annotations to carry them into the module for \
reading; the logical module is the same either way.";
pub const BLIND_SPOT_MEANS: &str =
"the module is serialised with the source store's own blank node labels, and the closure diff \
skolemises the source before comparing, so a conclusion carrying a blank node or a Skolem IRI \
has no name that means the same thing on both sides and is NOT decided against the signature. \
That is the same complexity decision 0007 documents and declines to close: deciding subgraph \
containment up to blank-node renaming is simple entailment, NP-complete in general. \
Skolemising the store before extracting the module empties this bucket, and until something \
does, the number is here so the coverage of a clean result can be read.";
pub const VERIFICATION_MEANS: &str =
"this is the CONSEQUENCE of the locality theorem, measured; it is not the theorem. It reasons \
the whole ontology and the module to a fixpoint under one rule table and subtracts, so it can \
only ever speak about that rule table: a clean run says the module lost nothing this engine \
could derive over the signature, and says nothing about entailments the engine cannot reach. \
A non-zero lost_over_signature_total is a defect in the extractor.";
/// Run the closure diff between the whole ontology and the module, and report
/// the part the module's guarantee is about.
///
/// This is deliberately the same machinery `onto_closure_diff` runs. A second
/// implementation of "what did this subset lose" would be a second place for
/// the answer to be wrong.
pub fn verify_module(
store: &Arc<GraphStore>,
module: &ModuleReport,
opts: &crate::closure_diff::DiffOptions,
scan_rows: usize,
) -> anyhow::Result<ModuleVerification> {
let started = std::time::Instant::now();
let module_ttl = module.module_ttl.as_str();
let sig: BTreeSet<&str> = module.signature_closure.iter().map(String::as_str).collect();
let vacuous: BTreeSet<&str> =
module.annotation_predicates_treated_as_vacuous.iter().map(String::as_str).collect();
// The diff renders `max_rows` of the difference and counts the rest, but
// the signature partition has to see EVERY row: a verification computed
// from the first two hundred conclusions is a sample, and a clean sample
// is not a clean result. `scan_rows` bounds it so a pathological graph
// cannot exhaust memory, and `not_examined` says when the bound bit.
let scan = crate::closure_diff::DiffOptions { max_rows: scan_rows, ..opts.clone() };
let report = crate::closure_diff::closure_diff(store, module_ttl, &scan)?;
let over_signature = |t: &Spelled| -> bool {
[&t.0, &t.1, &t.2].into_iter().all(|term| match iri_of(term) {
Some(i) => is_builtin(i) || sig.contains(i),
// A literal is a value, not a name, so it never takes a triple out
// of the signature. A blank node has no name at all and cannot be
// decided, so it does.
None => is_literal(term),
})
};
let over: Vec<&crate::closure_diff::LostEntailment> =
report.entailments_lost.iter().filter(|l| over_signature(&l.triple)).collect();
let annotation_only = over
.iter()
.filter(|l| iri_of(&l.triple.1).is_some_and(|p| vacuous.contains(p)))
.count();
let lost: Vec<crate::closure_diff::LostEntailment> = over
.iter()
.filter(|l| !iri_of(&l.triple.1).is_some_and(|p| vacuous.contains(p)))
.map(|l| (*l).clone())
.collect();
let unnameable = |t: &Spelled| -> bool {
[&t.0, &t.1, &t.2].into_iter().any(|term| {
is_bnode(term)
|| iri_of(term).is_some_and(|i| i.starts_with(SKOLEM_PREFIX))
})
};
let blind = report.entailments_lost.iter().filter(|l| unnameable(&l.triple)).count();
let scanned = report.entailments_lost.len();
let lost_over = lost.len();
let headline = format!(
"{lost_over} conclusion(s) over the signature closure are reachable from the whole \
ontology and not from the module, out of {scanned} examined of {} lost in total, plus \
{annotation_only} annotation triple(s) the module drops by design and {blind} carrying a \
blank node or a Skolem IRI, which cannot be decided against the signature at all. A \
locality module may not lose any of the first kind.",
report.lost_total
);
Ok(ModuleVerification {
format: "oo-module-verification/1",
headline,
profile: report.profile.clone(),
lost_over_signature_total: lost_over,
lost_over_signature: lost.into_iter().take(opts.max_rows).collect(),
lost_over_signature_annotation_only: annotation_only,
annotation_losses_are_not_entailment_losses: ANNOTATION_LOSSES_MEAN,
lost_outside_signature_total: scanned - lost_over - annotation_only,
not_decided_blank_node_bearing: blind,
blind_spot_means: BLIND_SPOT_MEANS,
not_examined: report.lost_total.saturating_sub(scanned),
engine_soundness_violations: report.monotonicity_violations.len(),
source_certificate: report.source_certificate.clone(),
means: VERIFICATION_MEANS,
seconds: started.elapsed().as_secs_f64(),
})
}
#[cfg(test)]
mod tests {
use super::*;
fn loaded(ttl: &str) -> Arc<GraphStore> {
let g = Arc::new(GraphStore::new());
g.load_turtle(ttl, None).unwrap();
g
}
const PREFIXES: &str = "@prefix owl: <http://www.w3.org/2002/07/owl#> .\n\
@prefix rdfs: <http://www.w3.org/2000/01/rdf-schema#> .\n\
@prefix ex: <http://ex.org/> .\n";
fn chain() -> Arc<GraphStore> {
loaded(&format!(
"{PREFIXES}
ex:Cat rdfs:subClassOf ex:Mammal .
ex:Mammal rdfs:subClassOf ex:Animal .
ex:Animal rdfs:subClassOf ex:LivingThing .
ex:Plant rdfs:subClassOf ex:LivingThing ."
))
}
fn opts(sig: &[&str], locality: Locality) -> ModuleOptions {
ModuleOptions {
signature: sig.iter().map(|s| s.to_string()).collect(),
locality,
..Default::default()
}
}
#[test]
fn a_bottom_module_keeps_the_chain_and_drops_the_sibling() {
let r = extract_module(
&chain(),
&opts(&["http://ex.org/Cat", "http://ex.org/LivingThing"], Locality::Bottom),
)
.unwrap();
assert_eq!(r.module_axioms, 3, "{}", r.module_ttl);
assert!(r.module_ttl.contains("Cat"));
assert!(r.module_ttl.contains("Animal"));
assert!(!r.module_ttl.contains("Plant"), "the sibling is ⊥-local: {}", r.module_ttl);
}
/// The fixpoint IS the soundness condition, and this is the case that shows
/// it: the first sweep of the ⊤ pass finds `Cat ⊑ Mammal` and `Mammal ⊑
/// Animal` local, and only the signature growth from `Animal ⊑ LivingThing`
/// pulls them back in.
#[test]
fn the_top_pass_iterates_rather_than_sweeping_once() {
let r = extract_module(
&chain(),
&opts(&["http://ex.org/Cat", "http://ex.org/LivingThing"], Locality::Star),
)
.unwrap();
assert_eq!(r.module_axioms, 3, "{}", r.module_ttl);
for term in ["Cat", "Mammal", "Animal", "LivingThing"] {
assert!(r.module_ttl.contains(term), "{term} missing from {}", r.module_ttl);
}
}
/// `⊥⊤*` is strictly smaller than `⊥` here: the `⊥` pass keeps an ABox
/// assertion over an external property, and the `⊤` pass removes it.
#[test]
fn star_is_strictly_smaller_than_bottom_on_an_external_assertion() {
let g = loaded(&format!(
"{PREFIXES}
ex:Cat rdfs:subClassOf ex:LivingThing .
ex:tom ex:eats ex:fish ."
));
let sig = ["http://ex.org/Cat", "http://ex.org/LivingThing"];
let bottom = extract_module(&g, &opts(&sig, Locality::Bottom)).unwrap();
let star = extract_module(&g, &opts(&sig, Locality::Star)).unwrap();
assert_eq!(bottom.module_axioms, 2, "{}", bottom.module_ttl);
assert_eq!(star.module_axioms, 1, "{}", star.module_ttl);
assert!(!star.module_ttl.contains("eats"));
}
#[test]
fn an_unclassified_builtin_predicate_is_included_not_dropped() {
let g = loaded(&format!(
"{PREFIXES}
ex:Cat rdfs:subClassOf ex:LivingThing .
ex:Cat owl:members ex:Nonsense ."
));
let r = extract_module(
&g,
&opts(&["http://ex.org/Cat", "http://ex.org/LivingThing"], Locality::Star),
)
.unwrap();
assert_eq!(r.unclassified_total, 1, "{:?}", r.axioms_by_kind);
assert!(r.module_ttl.contains("members"), "{}", r.module_ttl);
}
#[test]
fn same_as_is_never_local() {
let g = loaded(&format!("{PREFIXES}\nex:a owl:sameAs ex:b ."));
let r = extract_module(&g, &opts(&["http://ex.org/Unrelated"], Locality::Star)).unwrap();
assert_eq!(r.module_axioms, 1);
assert_eq!(r.included_conservatively.get("same_individual"), Some(&1));
}
#[test]
fn a_datatype_filler_is_not_treated_as_an_external_class_name() {
let g = loaded(&format!(
"{PREFIXES}
@prefix xsd: <http://www.w3.org/2001/XMLSchema#> .
ex:Person rdfs:subClassOf
[ a owl:Restriction ; owl:onProperty ex:age ; owl:someValuesFrom xsd:integer ] ."
));
// `xsd:integer` is not a class name, so `∃age.xsd:integer` is not
// ⊥-equivalent and the axiom is not ⊥-local over {Person}.
let r = extract_module(&g, &opts(&["http://ex.org/Person"], Locality::Bottom)).unwrap();
assert_eq!(r.module_axioms, 1, "{}", r.module_ttl);
assert!(r.module_ttl.contains("someValuesFrom"));
}
#[test]
fn an_empty_signature_is_an_error_not_an_empty_module() {
let e = extract_module(&chain(), &opts(&[], Locality::Star)).unwrap_err();
assert!(e.to_string().contains("signature is empty"), "{e}");
}
#[test]
fn a_signature_name_absent_from_the_ontology_is_named() {
let r = extract_module(&chain(), &opts(&["http://ex.org/Typo"], Locality::Star)).unwrap();
assert_eq!(r.signature_not_in_ontology, vec!["http://ex.org/Typo".to_string()]);
}
#[test]
fn a_declaration_survives_for_a_term_in_the_signature() {
let g = loaded(&format!("{PREFIXES}\nex:Cat a owl:Class .\nex:Dog a owl:Class ."));
let r = extract_module(&g, &opts(&["http://ex.org/Cat"], Locality::Star)).unwrap();
assert_eq!(r.module_axioms, 1, "{}", r.module_ttl);
assert!(r.module_ttl.contains("Cat"));
assert!(!r.module_ttl.contains("Dog"));
}
/// An annotation property the ontology has given a domain is not an
/// annotation property any more, and its assertions carry consequences.
#[test]
fn a_loaded_annotation_predicate_stops_being_vacuous() {
let g = loaded(&format!(
"{PREFIXES}
rdfs:label rdfs:domain ex:Named .
ex:thing rdfs:label \"x\" ."
));
let r = extract_module(&g, &opts(&["http://ex.org/Named"], Locality::Bottom)).unwrap();
assert!(
r.module_ttl.contains("label"),
"a label assertion under a declared domain is a property assertion: {}",
r.module_ttl
);
}
#[test]
fn locality_names_round_trip() {
for (word, l) in
[("bottom", Locality::Bottom), ("top", Locality::Top), ("star", Locality::Star)]
{
assert_eq!(Locality::parse(word).unwrap(), l);
assert_eq!(l.name(), word);
}
assert!(Locality::parse("sideways").is_err());
}
}