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
//! Does adding these axioms change anything I could already say?
//!
//! [`crate::closure_diff`] already computes `closure(G) \ closure(P)` for a
//! `P ⊆ G`, with the rule and the premises behind every row and the
//! monotonicity gate running for free. Conservativity is that computation
//! pointed the other way: take `G` to be the EXTENDED ontology and `P` to be
//! the one that was there before, and the difference is exactly the set of
//! consequences the extension introduced. Restrict it to the old signature and
//! the finding is "this change alters what the ontology says about terms that
//! already existed".
//!
//! Nothing here recomputes a closure, a certificate or a verdict word:
//! [`crate::closure_diff::SourceClosure`] does all of it, so there is still
//! exactly ONE place in this crate where `checked` is produced.
//!
//! # What this is NOT, said once here and again in the payload
//!
//! Deductive conservativity in a description logic is a different problem from
//! the one this file solves, and it is a hard one: ExpTime-complete for `EL`,
//! 2ExpTime-complete for `ALC` (Ghilardi, Lutz and Wolter, KR 2006, "Did I
//! Damage My Ontology?"), and UNDECIDABLE for `ALCQIO` (Lutz, Walther and
//! Wolter, IJCAI 2007). Model conservativity is stronger again and is
//! undecidable already for `EL` (Lutz and Wolter, JSC 2010).
//!
//! What is computed here is conservativity WITH RESPECT TO THE RULE TABLE the
//! engine evaluates, which is a Horn approximation of OWL and derives only
//! positive ground triples. It is sound in one direction only and the report
//! says so in a field, not a doc comment: a new consequence found IS a real
//! change to what the ontology derives, while finding none does NOT establish
//! that the extension is conservative in any description logic. The field is
//! called `conservative_under_rule_table` and there is deliberately no
//! `conservative` anywhere in the payload.
use crate::closure_diff::{CertificateVerdict, DiffOptions, NtTriple, SourceClosure, Warrant};
use crate::graph::GraphStore;
use crate::projection_entailment as pe;
use serde::{Deserialize, Serialize};
use std::collections::BTreeSet;
use std::sync::Arc;
/// Skolem prefix for the BASE graph.
///
/// The base is skolemised before the extension is merged in, so that the merged
/// store has blank nodes from the extension only and the base is a literal
/// subset of it. A distinct prefix is what stops `_:b0` in the base and `_:b0`
/// in the extension mapping onto the same IRI, which would silently identify
/// two different existentials. `/` cannot occur in an N-Triples blank node
/// label, so no default-prefix skolem IRI can collide with one of these.
const BASE_SKOLEM_PREFIX: &str = "https://open-ontologies.org/.well-known/genid/base/";
/// Namespaces whose IRIs are logical vocabulary rather than names of the
/// ontology's own things. A conclusion is "over the old signature" when every
/// IRI in it is either one of these or a name the base already used: otherwise
/// `ex:Old rdfs:subClassOf ex:Older` would count as outside the signature
/// because `rdfs:subClassOf` is not a class the base declared.
const LOGICAL_NAMESPACES: &[&str] = &[
"http://www.w3.org/1999/02/22-rdf-syntax-ns#",
"http://www.w3.org/2000/01/rdf-schema#",
"http://www.w3.org/2002/07/owl#",
"http://www.w3.org/2001/XMLSchema#",
];
pub const WHAT_THIS_IS_NOT: &str =
"this is conservativity WITH RESPECT TO THE RULE TABLE named in rule_table, and nothing else. \
It is computed as closure(base ∪ extension) minus closure(base) under that table, restricted \
to triples every name of which the base already used. It is NOT deductive conservativity in a \
description logic (ExpTime-complete for EL, 2ExpTime-complete for ALC, and UNDECIDABLE for \
ALCQIO) and it is NOT model conservativity (undecidable already for EL). The asymmetry is the \
point: a new consequence reported here IS a real change to what this engine derives over the \
old names, while finding none establishes only that this rule table derives nothing new, and \
never that the extension is conservative in any logic.";
pub const FINDING_NOT_AN_ERROR: &str =
"a non-conservative extension is a FINDING, not a failure. Adding axioms that change what the \
ontology says about existing terms is often exactly the intended change; the point of \
reporting it is that it should be intended rather than discovered later. Each row names the \
rule that produced it and the premises the base did not have, so the decision can be made on \
the derivation rather than on the verdict word.";
/// Five words, never collapsed into a boolean and never into each other.
pub const CONSERVATIVE: &str = "conservative_under_rule_table";
pub const NOT_CONSERVATIVE: &str = "not_conservative_under_rule_table";
pub const UNDECIDED_TRUNCATED: &str = "undecided_scan_truncated";
pub const UNDECIDED_NOT_AN_EXTENSION: &str = "undecided_not_an_extension";
/// The engine derived something for the base that it did not derive for the
/// EXTENDED graph. The base is a subset by construction and the rule table is
/// monotone, so that cannot happen unless the engine is wrong, and no answer
/// computed from those two closures means anything. It is never folded into
/// `not_conservative`, because a soundness bug and a finding about the ontology
/// go to opposite teams.
pub const UNDECIDED_ENGINE_UNSOUND: &str = "undecided_engine_soundness_violation";
// ───────────────────────────────────────────────────────────────────────────
// Options
// ───────────────────────────────────────────────────────────────────────────
/// How to read the turtle the caller supplied.
///
/// Guessing it is not an option. A delta that happens to restate one triple of
/// the base looks exactly like a replacement that dropped everything else, and
/// the two answers are opposite, so the caller says which it meant.
#[derive(Clone, Copy, Debug, PartialEq, Eq, Serialize, Deserialize)]
#[serde(rename_all = "snake_case")]
pub enum ExtensionMode {
/// The turtle holds the axioms being ADDED. The result is an extension by
/// construction and nothing can be dropped.
Delta,
/// The turtle is the WHOLE proposed graph, as `onto_plan` receives it. Any
/// asserted triple of the base it does not contain is a removal, and a
/// change that removes is not an extension.
Replacement,
}
impl ExtensionMode {
pub fn parse(s: &str) -> anyhow::Result<ExtensionMode> {
match s {
"delta" | "added" => Ok(ExtensionMode::Delta),
"replacement" | "full" => Ok(ExtensionMode::Replacement),
other => anyhow::bail!(
"unknown extension mode {other:?}: pass \"delta\" (the turtle holds only what is \
being added) or \"replacement\" (the turtle is the whole proposed graph)"
),
}
}
pub fn name(self) -> &'static str {
match self {
ExtensionMode::Delta => "delta",
ExtensionMode::Replacement => "replacement",
}
}
}
#[derive(Clone, Debug)]
pub struct ConservativityOptions {
pub mode: ExtensionMode,
/// `rdfs`, `owl-rl` or `owl-rl-ext`. `owl-dl` is refused upstream, because
/// the tableaux path emits no rule trace.
pub profile: String,
/// Where both certificates land. A run is reproducible by hand from what it
/// leaves behind.
pub out: std::path::PathBuf,
/// How many new consequences are examined for signature membership. The
/// verdict is `undecided_scan_truncated` when the difference is larger,
/// because a verdict computed from a prefix of the difference is not a
/// verdict.
pub scan_rows: usize,
/// Rows rendered. Totals are always exact.
pub max_rows: usize,
}
impl Default for ConservativityOptions {
fn default() -> Self {
ConservativityOptions {
mode: ExtensionMode::Delta,
profile: "owl-rl".into(),
out: std::path::PathBuf::from("conservativity"),
scan_rows: 200_000,
max_rows: 100,
}
}
}
// ───────────────────────────────────────────────────────────────────────────
// Findings
// ───────────────────────────────────────────────────────────────────────────
/// A conclusion the extended ontology reaches and the base does not.
/// Serialise only. `Warrant` deliberately has no `Deserialize` (decision in
/// `src/verdict.rs`): parsing the word "checked" out of somebody's JSON is not
/// the same act as earning it, and a derive here would be a public constructor
/// for a certified state. Nothing reads this struct back; the server parses
/// into `serde_json::Value`.
#[derive(Clone, Debug, Serialize)]
pub struct NewConsequence {
pub triple: NtTriple,
/// True when every name in the triple is one the base already used, so this
/// row changes what the ontology says about terms that already existed.
/// That is the conservativity finding; the rest are the ordinary effect of
/// adding new terms.
pub over_old_signature: bool,
pub warrant: Warrant,
pub warrant_word: &'static str,
/// Named only where a machine-checked theorem stands behind the row.
pub theorem: Option<&'static str>,
/// The rule that first derived it in the extended ontology. `None` when the
/// extension ASSERTED it outright rather than deriving it.
pub rule: Option<String>,
/// The premises of that derivation the base's own closure does not hold:
/// what the extension had to add for this conclusion to appear. The
/// actionable half.
pub premises_the_base_lacked: Vec<NtTriple>,
}
#[derive(Clone, Debug, Serialize)]
pub struct ConservativityReport {
pub format: &'static str,
/// One sentence the reader cannot miss, first after `format`.
pub headline: String,
/// `conservative_under_rule_table`, `not_conservative_under_rule_table`,
/// `undecided_scan_truncated`, `undecided_not_an_extension` or
/// `undecided_engine_soundness_violation`.
pub conservativity_verdict: &'static str,
/// `null` when the verdict is one of the undecided words. Never a bare
/// `conservative`, and never `false` standing in for "we could not tell".
pub conservative_under_rule_table: Option<bool>,
/// What the verdict is about. Not a decoration: the verdict means nothing
/// without it.
pub rule_table: String,
pub what_this_is_not: &'static str,
pub finding_not_an_error: &'static str,
/// How the supplied turtle was read: `delta` or `replacement`.
pub mode: &'static str,
/// True when the proposed graph contains every asserted triple of the base,
/// so applying it is a pure addition. False means the change also REMOVES,
/// and removal is not what conservativity is about: the verdict is then
/// undecided and the removals are counted.
pub is_an_extension: bool,
pub base_triples_the_proposal_drops: usize,
pub dropped_examples: Vec<String>,
/// Base triples whose blank nodes could not be matched against the
/// proposal, so `base_triples_the_proposal_drops` was decided over the
/// ground ones only. Counted, never folded into the denominator.
pub not_compared_blank_node_bearing: usize,
pub base_signature_size: usize,
/// Names the extension introduces that the base never used.
pub signature_added: Vec<String>,
pub signature_added_total: usize,
pub new_consequences_over_old_signature: Vec<NewConsequence>,
pub new_consequences_over_old_signature_total: usize,
/// Every new consequence, including those that mention a new name. Bigger
/// by construction and NOT the headline: a new class brings new conclusions
/// about itself, which is what adding a class is.
pub new_consequences_total: usize,
/// New consequences the scan did not examine, because the difference was
/// larger than `scan_rows`. Non-zero forces the undecided verdict.
pub not_examined: usize,
/// The engine's own soundness gate, run for free by the closure diff: a
/// conclusion the BASE reaches that the EXTENDED ontology does not. The
/// rule table is monotone and the base is a subset, so this must be empty,
/// and a non-empty list is an engine bug rather than a finding about the
/// ontology.
pub engine_soundness_violations: Vec<String>,
/// Non-null when the monotonicity gate did NOT run, with the reason, so an
/// empty violation list can never mean "we did not look".
pub engine_soundness_gate_skipped: Option<String>,
pub base_certificate: CertificateVerdict,
pub extended_certificate: CertificateVerdict,
pub seconds: f64,
/// 0 conservative under the rule table, 1 a finding, 2 undecided.
pub exit_code: i32,
}
// ───────────────────────────────────────────────────────────────────────────
// The check
// ───────────────────────────────────────────────────────────────────────────
fn iri_of(term: &str) -> Option<&str> {
term.strip_prefix('<').and_then(|t| t.strip_suffix('>'))
}
fn is_logical(iri: &str) -> bool {
LOGICAL_NAMESPACES.iter().any(|ns| iri.starts_with(ns))
}
fn names_of<'a>(triples: impl Iterator<Item = &'a (String, String, String)>) -> 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_logical(i)
{
out.insert(i.to_string());
}
}
}
out
}
fn nt_of(triples: &[(String, String, String)]) -> String {
triples.iter().map(|(s, p, o)| format!("{s} {p} {o} .\n")).collect()
}
/// Does adding `extension_ttl` to `base` change any consequence over the names
/// the base already used?
///
/// `extension_ttl` is read as the graph to MERGE IN, so the extended ontology
/// is `base ∪ extension` and the subset precondition the monotonicity gate
/// needs holds by construction. When the caller's turtle is a full REPLACEMENT
/// rather than a delta — which is what `onto_plan` receives — the triples it
/// drops are reported in `base_triples_the_proposal_drops` and the verdict
/// becomes `undecided_not_an_extension`, because a change that removes is not
/// an extension and this question is not the one to ask about it.
pub fn conservativity_check(
base: &Arc<GraphStore>,
extension_ttl: &str,
opts: &ConservativityOptions,
) -> anyhow::Result<ConservativityReport> {
let started = std::time::Instant::now();
// ── Ground both sides so every comparison is exact ───────────────────
let (base_sk, _) = pe::skolemise_with_prefix(base, BASE_SKOLEM_PREFIX)?;
let base_triples = base_sk.all_triples()?;
let base_nt = nt_of(&base_triples);
let extended = Arc::new(GraphStore::new());
extended.load_ntriples(&base_nt)?;
extended.load_turtle(extension_ttl, None).map_err(|e| {
anyhow::anyhow!("the proposed extension is not readable as Turtle: {e}")
})?;
// ── Is it an extension at all? Decided over the ORIGINAL base ────────
//
// Only in `Replacement` mode is the question meaningful. A delta says
// nothing about the triples it does not mention, so counting them as
// removals would report every delta as a removal of the entire ontology.
let proposed = Arc::new(GraphStore::new());
proposed.load_turtle(extension_ttl, None)?;
let original = base.all_triples()?;
let bn = |t: &(String, String, String)| {
pe::is_blank(&t.0) || pe::is_blank(&t.1) || pe::is_blank(&t.2)
};
let (dropped, not_compared_blank_node_bearing) = match opts.mode {
ExtensionMode::Delta => (Vec::new(), 0),
ExtensionMode::Replacement => {
let proposed_set: BTreeSet<(String, String, String)> =
proposed.all_triples()?.into_iter().collect();
let unmatched = original.iter().filter(|t| bn(t)).count()
+ proposed_set.iter().filter(|t| bn(t)).count();
let gone: Vec<String> = original
.iter()
.filter(|t| !bn(t) && !proposed_set.contains(*t))
.map(|(s, p, o)| format!("{s} {p} {o}"))
.collect();
(gone, unmatched)
}
};
let is_an_extension = dropped.is_empty();
let mut dropped_examples: Vec<String> = dropped.iter().take(10).cloned().collect();
dropped_examples.sort();
// ── One closure diff, in the extension direction ─────────────────────
let diff_opts = DiffOptions {
profile: opts.profile.clone(),
out: opts.out.clone(),
checker: None,
// The base is already ground and the extension's blank nodes are
// skolemised by the diff itself, under the DEFAULT prefix, which cannot
// collide with BASE_SKOLEM_PREFIX.
skolemise_source: true,
max_rows: opts.scan_rows,
seed_iris: Vec::new(),
};
let ext_closure = SourceClosure::build(&extended, &diff_opts)?;
let report = ext_closure.diff(&base_nt, &diff_opts)?;
// ── Partition the difference by the OLD signature ────────────────────
let base_names = names_of(base_triples.iter());
let extension_names = names_of(proposed.all_triples()?.iter());
let signature_added: Vec<String> =
extension_names.difference(&base_names).cloned().collect();
let over_old = |t: &NtTriple| -> bool {
[&t.0, &t.1, &t.2].into_iter().all(|term| match iri_of(term) {
Some(i) => is_logical(i) || base_names.contains(i),
// A literal is a value, not a name. A blank node has no name that
// survives a graph boundary and is never waved through.
None => term.starts_with('"'),
})
};
let mut rows: Vec<NewConsequence> = Vec::new();
let mut over_old_total = 0usize;
for lost in &report.entailments_lost {
let is_over = over_old(&lost.triple);
if !is_over {
continue;
}
over_old_total += 1;
if rows.len() < opts.max_rows {
rows.push(NewConsequence {
triple: lost.triple.clone(),
over_old_signature: true,
warrant: lost.warrant.clone(),
warrant_word: lost.warrant_word,
theorem: lost.theorem,
rule: lost.rule.clone(),
premises_the_base_lacked: lost.blocking_premises.clone(),
});
}
}
let not_examined = report.lost_total.saturating_sub(report.entailments_lost.len());
let engine_soundness_violations: Vec<String> = report
.monotonicity_violations
.iter()
.map(|v| format!("{} {} {}", v.triple.0, v.triple.1, v.triple.2))
.collect();
// ── The verdict, never a bare boolean, and never collapsed ───────────
//
// The engine check comes FIRST. A monotonicity violation means the two
// closures this answer was computed from cannot both be right, so every
// count below it is meaningless, and reporting "not conservative" would
// send a soundness bug to the ontology's author.
let (verdict, flag, exit_code) = if !engine_soundness_violations.is_empty() {
(UNDECIDED_ENGINE_UNSOUND, None, 2)
} else if !is_an_extension {
(UNDECIDED_NOT_AN_EXTENSION, None, 2)
} else if not_examined > 0 {
(UNDECIDED_TRUNCATED, None, 2)
} else if over_old_total > 0 {
(NOT_CONSERVATIVE, Some(false), 1)
} else {
(CONSERVATIVE, Some(true), 0)
};
let headline = format!(
"{verdict}: {over_old_total} new consequence(s) over the {} name(s) the base already used, \
out of {} new consequence(s) in total, under the {} rule table. Extended certificate: \
{}{}. {}",
base_names.len(),
report.lost_total,
opts.profile,
report.source_certificate.verdict,
match report.source_certificate.theorem {
Some(t) => format!(" ({t})"),
None => String::new(),
},
WHAT_THIS_IS_NOT,
);
Ok(ConservativityReport {
format: "oo-conservativity/1",
headline,
conservativity_verdict: verdict,
conservative_under_rule_table: flag,
rule_table: opts.profile.clone(),
what_this_is_not: WHAT_THIS_IS_NOT,
finding_not_an_error: FINDING_NOT_AN_ERROR,
mode: opts.mode.name(),
is_an_extension,
base_triples_the_proposal_drops: dropped.len(),
dropped_examples,
not_compared_blank_node_bearing,
base_signature_size: base_names.len(),
signature_added_total: signature_added.len(),
signature_added: signature_added.into_iter().take(opts.max_rows).collect(),
new_consequences_over_old_signature: rows,
new_consequences_over_old_signature_total: over_old_total,
new_consequences_total: report.lost_total,
not_examined,
engine_soundness_violations,
engine_soundness_gate_skipped: report.monotonicity_gate_skipped.clone(),
base_certificate: report.projection_certificate.clone(),
extended_certificate: report.source_certificate.clone(),
seconds: started.elapsed().as_secs_f64(),
exit_code,
})
}
#[cfg(test)]
mod tests {
use super::*;
#[test]
fn a_logical_namespace_is_not_a_name() {
assert!(is_logical("http://www.w3.org/2000/01/rdf-schema#subClassOf"));
assert!(is_logical("http://www.w3.org/2002/07/owl#Thing"));
assert!(!is_logical("http://ex.org/Cat"));
}
#[test]
fn the_base_skolem_prefix_cannot_collide_with_the_default_one() {
// The default prefix maps `_:label` to `<PREFIX + label>` and an
// N-Triples blank node label cannot contain `/`, so no default-prefix
// skolem IRI can ever spell a base-prefix one.
assert!(BASE_SKOLEM_PREFIX.starts_with(pe::SKOLEM_PREFIX));
let tail = &BASE_SKOLEM_PREFIX[pe::SKOLEM_PREFIX.len()..];
assert!(tail.contains('/'), "the discriminator must be unspellable as a label: {tail:?}");
}
#[test]
fn five_verdict_words_and_no_bare_conservative() {
let words = [
CONSERVATIVE,
NOT_CONSERVATIVE,
UNDECIDED_TRUNCATED,
UNDECIDED_NOT_AN_EXTENSION,
UNDECIDED_ENGINE_UNSOUND,
];
for w in words {
assert_ne!(w, "conservative", "a bare word is the one spelling that may not appear");
}
let distinct: BTreeSet<&str> = words.into_iter().collect();
assert_eq!(distinct.len(), words.len(), "two verdicts must never share a spelling");
}
}