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
//! OWL 2 EL classification by completion (#30, #324).
//!
//! The axioms are read by the tableau's own OWL parser
//! ([`crate::tableaux::parse_owl`]), normalised into the four EL normal forms
//! (`A ⊑ B`, `A₁ ⊓ A₂ ⊑ B`, `A ⊑ ∃r.B`, `∃r.A ⊑ B`, with `B` possibly `⊥`),
//! and saturated with the completion rules of Baader, Brandt and Lutz,
//! *Pushing the EL Envelope* (IJCAI 2005): CR1-CR4 for told subsumption,
//! conjunction and existentials, ⊥-propagation, the role hierarchy, and
//! transitive roles as the chain `r ∘ r ⊑ r`. Ranges are compiled into the
//! existential's filler (`A ⊑ ∃r.B` becomes `A ⊑ ∃r.(B ⊓ ran(r))`), which is the
//! treatment in *Pushing the EL Envelope Further* (OWLED 2008).
//!
//! ## What it guarantees
//!
//! Every subsumption it reports is entailed: each normalised axiom is entailed
//! by the original or is a definition of a fresh name, and an axiom it cannot
//! normalise is dropped, which only loses entailments. The table between named
//! classes is COMPLETE, and the report says `complete: true`, only when nothing
//! was dropped: no axiom outside EL, no inverse or functional role, and none of
//! the constructs the parser does not read at all (`owl:propertyChainAxiom`,
//! nominals, datatype restrictions, and the rest of
//! [`DlReasoner::unmodelled_constructs`]). Otherwise `complete` is false and
//! `incompleteness` names what was set aside.
//!
//! ## Why it is not OWL-RL any more
//!
//! Until #324 this module ran the `owl-rl-ext` rules and read back
//! `rdfs:subClassOf`, under a header saying that was "sufficient for the EL
//! fragment". It is not: RL derives through a left-hand conjunction or
//! existential only for an individual (`cls-int1`, `cls-svf1`), never at TBox
//! level, so `A ⊑ B, A ⊑ C, B ⊓ C ⊑ D` came back without `A ⊑ D`, and so did
//! `A ⊑ ∃r.B, B ⊑ C, ∃r.C ⊑ D`. The read-back also stopped at 100,000 rows
//! without saying so. The RL rules still run, but only on input outside EL,
//! where they can add sound subsumptions the EL fragment does not see (through
//! `owl:allValuesFrom`, for instance); their answer is unioned in, read from the
//! store directly with no row cap.
//!
//! For a complete classification of input outside EL, use `onto_reason` with
//! `owl-dl`, which reports its own `complete` flag.
use crate::graph::GraphStore;
use crate::reason::Reasoner;
use crate::tableaux::{Concept, DlReasoner, ParseResult, parse_owl};
use serde::Serialize;
use std::collections::{BTreeMap, BTreeSet, HashMap, HashSet};
use std::sync::Arc;
const RDFS_SUBCLASS: &str = "<http://www.w3.org/2000/01/rdf-schema#subClassOf>";
const OWL_THING: &str = "<http://www.w3.org/2002/07/owl#Thing>";
#[derive(Clone, Debug, Serialize)]
pub struct ClassificationReport {
/// `el-completion` when the EL saturation alone produced the table,
/// `el-completion+owl-rl-ext` when the RL rules were unioned in because the
/// input is outside EL.
pub profile: String,
/// True only when the table is every subsumption between named classes
/// that the ontology entails (see the module docs for the conditions).
pub complete: bool,
/// Why `complete` is false, one entry per cause. Empty when complete.
pub incompleteness: Vec<String>,
/// False when the saturation derived `⊤ ⊑ ⊥` or an individual in `⊥`. An
/// inconsistent ontology entails every subsumption, and the table lists
/// only those derived, so `complete` is then false.
pub consistent: bool,
/// Always false: there is no row cap. Kept so a consumer can check for a
/// cut-off table instead of assuming there is none; the old read-back
/// stopped at 100,000 rows and had no way to say so.
pub truncated: bool,
/// Named classes classified, `owl:Thing` excluded.
pub class_count: usize,
pub subsumption_count: usize,
/// `[sub, super]` pairs between named classes, `owl:Thing` and `X ⊑ X`
/// left out. Sorted by sub then super for stable output. An unsatisfiable
/// class is under every class and its pairs are not listed; it is in
/// `unsatisfiable` instead, as HermiT reports it.
pub subsumptions: Vec<(String, String)>,
pub unsatisfiable: Vec<String>,
}
/// Node 0 is `⊤` and node 1 is `⊥` in every normalised TBox.
const TOP: usize = 0;
const BOTTOM: usize = 1;
/// The construct that keeps a concept out of EL on the side it occurs.
fn construct(c: &Concept) -> &'static str {
match c {
Concept::ForAll(..) => "owl:allValuesFrom",
Concept::Or(..) => "owl:unionOf",
Concept::NegAtom(..) => "owl:complementOf",
Concept::MaxCard(..) => "max cardinality",
Concept::MinCard(..) => "min cardinality above 1",
_ => "a class expression",
}
}
/// The first sub-expression that cannot stand on the LEFT of an EL axiom.
fn lhs_offender(c: &Concept) -> Option<&'static str> {
match c {
Concept::Top | Concept::Bottom | Concept::Atom(_) | Concept::MinCard(_, 0, _) => None,
Concept::And(cs) | Concept::Or(cs) => cs.iter().find_map(lhs_offender),
Concept::Exists(_, f) | Concept::MinCard(_, 1, f) => lhs_offender(f),
other => Some(construct(other)),
}
}
/// Whether a concept can stand on the RIGHT, possibly after the Horn rewrite
/// `X ⊑ ¬N ⊔ D` into `X ⊓ N ⊑ D` (`add_horn`).
fn rhs_el(c: &Concept) -> bool {
match c {
Concept::Top | Concept::Bottom | Concept::Atom(_) | Concept::MinCard(_, 0, _) => true,
Concept::And(cs) => cs.iter().all(rhs_el),
Concept::Exists(_, f) | Concept::MinCard(_, _, f) => rhs_el(f),
other => horn_split(other).is_some(),
}
}
/// `D₁ ⊔ … ⊔ Dₙ` as (the negated disjuncts that are EL left-hand sides, the
/// one remaining positive disjunct), or `None` when more than one disjunct is
/// positive or the positive one is not EL. NNF writes `A ⊑ ¬B` and `A ⊑ ¬∃r.B`
/// as `¬B` and `∀r.¬B`, so disjointness reaches this module in that form and
/// has to be read back out of it.
fn horn_split(c: &Concept) -> Option<(Vec<Concept>, Option<&Concept>)> {
let disjuncts: Vec<&Concept> = match c {
Concept::Or(cs) => cs.iter().collect(),
other => vec![other],
};
let mut negs = Vec::new();
let mut pos = None;
for d in disjuncts {
// `x ⊑ D ⊔ R` is `x ⊓ ¬D ⊑ R` exactly, so any disjunct whose
// negation is an EL left-hand side can move across.
let n = d.negate();
if lhs_offender(&n).is_none() {
negs.push(n);
// The positive disjunct must be one `add_rhs` takes directly: the four
// forms excluded here are the ones it sends back to this function.
} else if pos.is_none()
&& !matches!(d, Concept::Or(_) | Concept::ForAll(..) | Concept::NegAtom(_) | Concept::MaxCard(..))
&& rhs_el(d)
{
pos = Some(d);
} else {
return None;
}
}
Some((negs, pos))
}
/// A TBox in EL normal form over dense node ids.
struct Normalised {
told: Vec<Vec<usize>>,
/// `conj[a]` holds `(b, c)` for every `a ⊓ b ⊑ c`, stored under both conjuncts.
conj: Vec<Vec<(usize, usize)>>,
/// `ex_rhs[a]` holds `(r, b)` for every `a ⊑ ∃r.b`.
ex_rhs: Vec<Vec<(u32, usize)>>,
/// `∃r.a ⊑ b`, keyed by `(r, a)` and by `r`.
ex_lhs: HashMap<(u32, usize), Vec<usize>>,
ex_lhs_by_role: HashMap<u32, Vec<(usize, usize)>>,
ranges: HashMap<u32, Vec<usize>>,
atom_node: HashMap<u32, usize>,
lhs_cache: HashMap<Concept, usize>,
rhs_cache: HashMap<Concept, usize>,
thing: u32,
nothing: u32,
/// Constructs set aside, with how many axioms (or parts of one) each cost.
dropped: BTreeMap<String, usize>,
}
impl Normalised {
fn new(thing: u32, nothing: u32) -> Self {
let mut n = Self {
told: Vec::new(),
conj: Vec::new(),
ex_rhs: Vec::new(),
ex_lhs: HashMap::new(),
ex_lhs_by_role: HashMap::new(),
ranges: HashMap::new(),
atom_node: HashMap::new(),
lhs_cache: HashMap::new(),
rhs_cache: HashMap::new(),
thing,
nothing,
dropped: BTreeMap::new(),
};
n.fresh();
n.fresh();
n
}
fn len(&self) -> usize {
self.told.len()
}
fn fresh(&mut self) -> usize {
self.told.push(Vec::new());
self.conj.push(Vec::new());
self.ex_rhs.push(Vec::new());
self.told.len() - 1
}
fn atom(&mut self, a: u32) -> usize {
if a == self.thing {
return TOP;
}
if a == self.nothing {
return BOTTOM;
}
if let Some(&n) = self.atom_node.get(&a) {
return n;
}
let n = self.fresh();
self.atom_node.insert(a, n);
n
}
fn drop_part(&mut self, why: String) {
*self.dropped.entry(why).or_default() += 1;
}
fn add_conj(&mut self, a: usize, b: usize, c: usize) {
self.conj[a].push((b, c));
if a != b {
self.conj[b].push((a, c));
}
}
fn add_ex_lhs(&mut self, r: u32, a: usize, b: usize) {
self.ex_lhs.entry((r, a)).or_default().push(b);
self.ex_lhs_by_role.entry(r).or_default().push((a, b));
}
/// A node `n` with `c ⊑ n`. The caller has checked `lhs_offender(c)`.
fn name_lhs(&mut self, c: &Concept) -> usize {
match c {
Concept::Top | Concept::MinCard(_, 0, _) => return TOP,
Concept::Bottom => return BOTTOM,
Concept::Atom(a) => return self.atom(*a),
_ => {}
}
if let Some(&n) = self.lhs_cache.get(c) {
return n;
}
let n = match c {
Concept::And(cs) => {
let parts: Vec<usize> = cs.iter().map(|p| self.name_lhs(p)).collect();
let mut acc = parts[0];
for &p in &parts[1..] {
let f = self.fresh();
self.add_conj(acc, p, f);
acc = f;
}
acc
}
// `C₁ ⊔ C₂ ⊑ n` is `C₁ ⊑ n` and `C₂ ⊑ n`: two EL axioms, no
// disjunction left to reason with.
Concept::Or(cs) => {
let f = self.fresh();
for p in cs {
let pn = self.name_lhs(p);
self.told[pn].push(f);
}
f
}
Concept::Exists(r, filler) | Concept::MinCard(r, _, filler) => {
let fn_ = self.name_lhs(filler);
let f = self.fresh();
self.add_ex_lhs(*r, fn_, f);
f
}
other => unreachable!("lhs_offender admitted {other:?}"),
};
self.lhs_cache.insert(c.clone(), n);
n
}
/// A node `n` with `n ⊑ c`, as far as `c` is EL.
fn name_rhs(&mut self, c: &Concept) -> usize {
match c {
Concept::Top => return TOP,
Concept::Bottom => return BOTTOM,
Concept::Atom(a) => return self.atom(*a),
_ => {}
}
if let Some(&n) = self.rhs_cache.get(c) {
return n;
}
let n = self.fresh();
self.rhs_cache.insert(c.clone(), n);
self.add_rhs(n, c);
n
}
/// `x ⊑ c`, keeping every EL part of `c` and dropping the rest. Dropping a
/// conjunct on the right weakens the axiom, which is sound.
fn add_rhs(&mut self, x: usize, c: &Concept) {
match c {
Concept::Top | Concept::MinCard(_, 0, _) => {}
Concept::Bottom => self.told[x].push(BOTTOM),
Concept::Atom(a) => {
let a = self.atom(*a);
self.told[x].push(a);
}
Concept::And(cs) => {
for p in cs {
self.add_rhs(x, p);
}
}
Concept::Exists(r, f) | Concept::MinCard(r, 1, f) => {
let fnode = self.name_rhs(f);
self.ex_rhs[x].push((*r, fnode));
}
// `≥n r.F` entails `∃r.F`, so reading it as that is sound; what is
// lost is the count.
Concept::MinCard(r, _, f) => {
self.drop_part("min cardinality above 1 on the right-hand side, read as owl:someValuesFrom".into());
let fnode = self.name_rhs(f);
self.ex_rhs[x].push((*r, fnode));
}
other => self.add_horn(x, other),
}
}
/// `x ⊑ ¬N₁ ⊔ … ⊔ ¬Nₖ ⊔ D` is `x ⊓ N₁ ⊓ … ⊓ Nₖ ⊑ D` (D may be absent,
/// then `⊥`). Anything with two positive disjuncts is outside EL.
fn add_horn(&mut self, x: usize, c: &Concept) {
let Some((negs, pos)) = horn_split(c) else {
self.drop_part(format!("{} on the right-hand side", construct(c)));
return;
};
let mut acc = x;
for n in &negs {
let nn = self.name_lhs(n);
let f = self.fresh();
self.add_conj(acc, nn, f);
acc = f;
}
match pos {
Some(d) => self.add_rhs(acc, d),
None => self.told[acc].push(BOTTOM),
}
}
fn add_axiom(&mut self, sub: &Concept, sup: &Concept) {
if let Some(why) = lhs_offender(sub) {
self.drop_part(format!("{why} on the left-hand side"));
return;
}
let x = self.name_lhs(sub);
self.add_rhs(x, sup);
}
}
/// The reflexive-transitive closure of `rdfs:subPropertyOf` from `r`.
fn role_sups(sub_to_super: &HashMap<u32, HashSet<u32>>, r: u32) -> Vec<u32> {
let mut seen = BTreeSet::from([r]);
let mut stack = vec![r];
while let Some(x) = stack.pop() {
for &y in sub_to_super.get(&x).into_iter().flatten() {
if seen.insert(y) {
stack.push(y);
}
}
}
seen.into_iter().collect()
}
enum Step {
Add(usize, usize),
Link(usize, u32, usize),
}
/// The completion sets: `s[x]` is every node `x` is subsumed by, and the
/// `(x, r, y)` edges are the derived `x ⊑ ∃r.y`.
struct Saturation<'a> {
t: &'a Normalised,
sups: HashMap<u32, Vec<u32>>,
sub_to_super: &'a HashMap<u32, HashSet<u32>>,
transitive: &'a HashSet<u32>,
s: Vec<HashSet<usize>>,
context: Vec<bool>,
edges: HashSet<(usize, u32, usize)>,
pred: Vec<Vec<(usize, u32)>>,
succ: Vec<Vec<(u32, usize)>>,
queue: Vec<Step>,
}
impl<'a> Saturation<'a> {
fn new(t: &'a Normalised, p: &'a ParseResult) -> Self {
let n = t.len();
Self {
t,
sups: HashMap::new(),
sub_to_super: &p.sub_to_super,
transitive: &p.transitive_roles,
s: vec![HashSet::new(); n],
context: vec![false; n],
edges: HashSet::new(),
pred: vec![Vec::new(); n],
succ: vec![Vec::new(); n],
queue: Vec::new(),
}
}
fn init(&mut self, x: usize) {
if !self.context[x] {
self.context[x] = true;
self.queue.push(Step::Add(x, x));
self.queue.push(Step::Add(x, TOP));
}
}
fn sups_of(&mut self, r: u32) -> Vec<u32> {
let sts = self.sub_to_super;
self.sups.entry(r).or_insert_with(|| role_sups(sts, r)).clone()
}
fn run(&mut self) {
while let Some(step) = self.queue.pop() {
match step {
Step::Add(x, a) => self.add(x, a),
Step::Link(x, r, y) => self.link(x, r, y),
}
}
}
fn add(&mut self, x: usize, a: usize) {
if !self.s[x].insert(a) {
return;
}
let t = self.t;
// CR1: a ⊑ b.
for &b in &t.told[a] {
self.queue.push(Step::Add(x, b));
}
// CR2: a ⊓ o ⊑ c.
for &(o, c) in &t.conj[a] {
if self.s[x].contains(&o) {
self.queue.push(Step::Add(x, c));
}
}
// CR3: a ⊑ ∃r.b.
for &(r, b) in &t.ex_rhs[a] {
self.init(b);
self.queue.push(Step::Link(x, r, b));
}
// CR4 and ⊥: every predecessor of x learns what x's new subsumer gives it.
for i in 0..self.pred[x].len() {
let (p, r) = self.pred[x][i];
if a == BOTTOM {
self.queue.push(Step::Add(p, BOTTOM));
}
for &b in t.ex_lhs.get(&(r, a)).into_iter().flatten() {
self.queue.push(Step::Add(p, b));
}
}
}
fn link(&mut self, x: usize, r: u32, y: usize) {
let t = self.t;
for s in self.sups_of(r) {
if !self.edges.insert((x, s, y)) {
continue;
}
self.pred[y].push((x, s));
self.succ[x].push((s, y));
if self.s[y].contains(&BOTTOM) {
self.queue.push(Step::Add(x, BOTTOM));
}
// CR4: ∃s.a ⊑ b with a ⊑ y's subsumers; walk whichever side is shorter.
if let Some(rules) = t.ex_lhs_by_role.get(&s) {
if rules.len() <= self.s[y].len() {
for &(a, b) in rules {
if self.s[y].contains(&a) {
self.queue.push(Step::Add(x, b));
}
}
} else {
for &a in &self.s[y] {
for &b in t.ex_lhs.get(&(s, a)).into_iter().flatten() {
self.queue.push(Step::Add(x, b));
}
}
}
}
// A transitive role is the chain s ∘ s ⊑ s.
if self.transitive.contains(&s) {
for &(s2, z) in &self.succ[y] {
if s2 == s {
self.queue.push(Step::Link(x, s, z));
}
}
for &(w, s2) in &self.pred[x] {
if s2 == s {
self.queue.push(Step::Link(w, s, y));
}
}
}
}
}
}
/// Classify the loaded ontology. Works on a copy of the triples, so the
/// graph is not mutated.
pub fn classify(graph: &Arc<GraphStore>) -> anyhow::Result<ClassificationReport> {
let triples = graph.all_triples()?;
let p = parse_owl(triples.clone());
let mut t = Normalised::new(p.thing_id, p.nothing_id);
for (sub, sup) in &p.axioms {
t.add_axiom(sub, sup);
}
for (a, b) in &p.disjoint_pairs {
t.add_axiom(&Concept::And(vec![a.clone(), b.clone()]), &Concept::Bottom);
}
for (r, c) in &p.role_domains {
t.add_axiom(&Concept::Exists(*r, Box::new(Concept::Top)), c);
}
for (r, c) in &p.role_ranges {
let n = t.name_rhs(c);
t.ranges.entry(*r).or_default().push(n);
}
// Ranges into fillers: `a ⊑ ∃r.b` becomes `a ⊑ ∃r.(b ⊓ ran(s))` for every
// `s ⊒ r`. Done once over the TBox's existentials, which is all of them:
// the saturation derives edges, never new existential axioms.
let mut range_of: HashMap<u32, Vec<usize>> = HashMap::new();
let mut ranged: HashMap<(usize, u32), usize> = HashMap::new();
for a in 0..t.len() {
for i in 0..t.ex_rhs[a].len() {
let (r, b) = t.ex_rhs[a][i];
let rans = range_of
.entry(r)
.or_insert_with(|| {
role_sups(&p.sub_to_super, r)
.iter()
.flat_map(|s| t.ranges.get(s).into_iter().flatten().copied())
.collect()
})
.clone();
if rans.is_empty() {
continue;
}
let node = match ranged.get(&(b, r)) {
Some(&n) => n,
None => {
let n = t.fresh();
t.told[n].push(b);
t.told[n].extend(rans);
ranged.insert((b, r), n);
n
}
};
t.ex_rhs[a][i] = (r, node);
}
}
// The ABox, each individual as its own node. An assertion `a r b` is
// `a ⊑ ∃r.b` with the ranges put on `b` itself, not on a filler copy: the
// r-successor IS `b`, and a range that only reached a copy would miss
// `∃s.(C ⊓ E) ⊑ ⊥` when `C` comes from the range and `E` from `b`'s type.
// It matters only for consistency: no ABox fact changes a TBox subsumption
// of a consistent ontology.
let mut individuals: BTreeSet<usize> = BTreeSet::new();
for (&ind, types) in &p.individual_types {
let i = t.atom(ind);
individuals.insert(i);
for &c in types {
let c = t.atom(c);
t.told[i].push(c);
}
}
for (&ind, cs) in &p.individual_anon_types {
let i = t.atom(ind);
individuals.insert(i);
for c in cs {
t.add_rhs(i, c);
}
}
for &(a, r, b) in &p.role_assertions {
let (ia, ib) = (t.atom(a), t.atom(b));
individuals.insert(ia);
individuals.insert(ib);
t.ex_rhs[ia].push((r, ib));
for s in role_sups(&p.sub_to_super, r) {
if let Some(rans) = t.ranges.get(&s).cloned() {
t.told[ib].extend(rans);
}
}
}
let classes: Vec<(u32, usize)> = {
let mut v: Vec<(u32, usize)> = p
.named_classes
.iter()
.filter(|&&c| c != p.thing_id && c != p.nothing_id)
.map(|&c| (c, t.atom(c)))
.collect();
v.sort_unstable();
v
};
let mut sat = Saturation::new(&t, &p);
sat.init(TOP);
for &(_, n) in &classes {
sat.init(n);
}
for &i in &individuals {
sat.init(i);
}
sat.run();
let consistent = !sat.s[TOP].contains(&BOTTOM)
&& individuals.iter().all(|&i| !sat.s[i].contains(&BOTTOM));
let node_class: HashMap<usize, u32> = classes.iter().map(|&(c, n)| (n, c)).collect();
let name = |c: u32| p.interner.resolve(c).trim_matches(|ch| ch == '<' || ch == '>').to_string();
let mut unsat: BTreeSet<String> = BTreeSet::new();
let mut subs: BTreeSet<(String, String)> = BTreeSet::new();
for &(c, n) in &classes {
if sat.s[n].contains(&BOTTOM) {
unsat.insert(name(c));
continue;
}
for d in &sat.s[n] {
if let Some(&dc) = node_class.get(d)
&& dc != c
{
subs.insert((name(c), name(dc)));
}
}
}
let mut incompleteness: Vec<String> = t
.dropped
.iter()
.map(|(why, n)| format!("{why}: {n} axiom part(s) outside OWL 2 EL not used"))
.collect();
if !p.inverse_roles.is_empty() {
incompleteness.push(format!(
"inverse or symmetric roles ({} role(s)): outside OWL 2 EL, each read as an unrelated role",
p.inverse_roles.len()
));
}
let functional = p.functional_roles.len() + p.inv_functional_roles.len();
if functional > 0 {
incompleteness.push(format!(
"functional or inverse-functional roles ({functional}): outside OWL 2 EL, not used"
));
}
for (construct, n) in DlReasoner::unmodelled_constructs(graph) {
incompleteness.push(format!("{construct} ({n} occurrence(s)): not read by the parser"));
}
if !consistent {
incompleteness.push(
"the ontology is inconsistent: it entails every subsumption, and only the derived ones are listed"
.into(),
);
}
let complete = incompleteness.is_empty();
// Outside EL the RL rules can still find sound subsumptions the EL part
// does not reach, so they are unioned in. On EL input they could add
// nothing: the table is already every entailed subsumption.
let profile = if complete {
"el-completion"
} else {
let sandbox = Arc::new(GraphStore::new());
if !triples.is_empty() {
let mut nt = String::with_capacity(triples.len() * 64);
for (s, p, o) in &triples {
nt.push_str(s);
nt.push(' ');
nt.push_str(p);
nt.push(' ');
nt.push_str(o);
nt.push_str(" .\n");
}
sandbox.load_ntriples(&nt)?;
}
Reasoner::run(&sandbox, "owl-rl-ext", true)?;
let named: HashSet<String> = classes.iter().map(|&(c, _)| name(c)).collect();
for (s, pr, o) in sandbox.all_triples()? {
if pr != RDFS_SUBCLASS || o == OWL_THING || s == o {
continue;
}
let (s, o) = (s.trim_matches(|c| c == '<' || c == '>'), o.trim_matches(|c| c == '<' || c == '>'));
if named.contains(s) && named.contains(o) && !unsat.contains(s) {
subs.insert((s.to_string(), o.to_string()));
}
}
"el-completion+owl-rl-ext"
};
let subsumptions: Vec<(String, String)> = subs.into_iter().collect();
Ok(ClassificationReport {
profile: profile.to_string(),
complete,
incompleteness,
consistent,
truncated: false,
class_count: classes.len(),
subsumption_count: subsumptions.len(),
subsumptions,
unsatisfiable: unsat.into_iter().collect(),
})
}
#[cfg(test)]
mod tests {
use super::*;
#[test]
fn classify_emits_transitive_closure_of_subclassof() {
let g = Arc::new(GraphStore::new());
g.load_turtle(
r#"
@prefix owl: <http://www.w3.org/2002/07/owl#> .
@prefix rdfs: <http://www.w3.org/2000/01/rdf-schema#> .
@prefix ex: <http://ex.org/> .
ex:A a owl:Class .
ex:B a owl:Class ; rdfs:subClassOf ex:A .
ex:C a owl:Class ; rdfs:subClassOf ex:B .
"#,
None,
)
.unwrap();
let r = classify(&g).unwrap();
// Transitive: C ⊑ A must be derived.
let has_c_a = r.subsumptions.iter().any(|(s, o)| {
s == "http://ex.org/C" && o == "http://ex.org/A"
});
assert!(has_c_a, "transitive subsumption not derived; got: {:?}", r.subsumptions);
assert!(r.subsumption_count >= 3);
}
#[test]
fn classify_excludes_trivial_self_subsumptions() {
let g = Arc::new(GraphStore::new());
g.load_turtle(
"@prefix owl: <http://www.w3.org/2002/07/owl#> . @prefix ex: <http://ex.org/> . ex:A a owl:Class .",
None,
)
.unwrap();
let r = classify(&g).unwrap();
for (s, o) in &r.subsumptions {
assert_ne!(s, o, "self-subsumption emitted");
}
}
#[test]
fn classify_does_not_mutate_original() {
let g = Arc::new(GraphStore::new());
g.load_turtle(
"@prefix owl: <http://www.w3.org/2002/07/owl#> . @prefix rdfs: <http://www.w3.org/2000/01/rdf-schema#> . @prefix ex: <http://ex.org/> . ex:A a owl:Class . ex:B a owl:Class ; rdfs:subClassOf ex:A .",
None,
)
.unwrap();
let pre = g.triple_count();
let _ = classify(&g).unwrap();
assert_eq!(pre, g.triple_count());
}
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 classify_ttl(body: &str) -> ClassificationReport {
let g = Arc::new(GraphStore::new());
g.load_turtle(&format!("{PREFIXES}{body}"), None).unwrap();
classify(&g).unwrap()
}
fn has(r: &ClassificationReport, sub: &str, sup: &str) -> bool {
r.subsumptions
.iter()
.any(|(s, o)| s == &format!("http://ex.org/{sub}") && o == &format!("http://ex.org/{sup}"))
}
/// #324, first example: CR2 (a conjunction on the left-hand side).
#[test]
fn conjunction_on_the_left_is_derived() {
let r = classify_ttl(
"ex:A rdfs:subClassOf ex:B , ex:C .
[ owl:intersectionOf ( ex:B ex:C ) ] rdfs:subClassOf ex:D .",
);
assert!(has(&r, "A", "D"), "A ⊑ D missing; got {:?}", r.subsumptions);
}
/// #324, second example: CR3 + CR4 (an existential on the left-hand side).
#[test]
fn existential_on_the_left_is_derived() {
let r = classify_ttl(
"ex:r a owl:ObjectProperty .
ex:A rdfs:subClassOf [ a owl:Restriction ; owl:onProperty ex:r ; owl:someValuesFrom ex:B ] .
ex:B rdfs:subClassOf ex:C .
[ a owl:Restriction ; owl:onProperty ex:r ; owl:someValuesFrom ex:C ] rdfs:subClassOf ex:D .",
);
assert!(has(&r, "A", "D"), "A ⊑ D missing; got {:?}", r.subsumptions);
}
/// The issue's second example does come back from OWL-RL — `scm-svf1`
/// turns `B ⊑ C` into `∃r.B ⊑ ∃r.C` because both restrictions are in the
/// graph — so it does not separate the two engines. These do: a filler
/// reached through a conjunction, a domain, and a transitive role. Measured
/// on the RL read-back before #324, none of the three `A ⊑ D` came back.
#[test]
fn existential_through_a_conjunctive_filler_is_derived() {
let r = classify_ttl(
"ex:r a owl:ObjectProperty .
ex:A rdfs:subClassOf [ a owl:Restriction ; owl:onProperty ex:r ; owl:someValuesFrom ex:B ] .
ex:B rdfs:subClassOf ex:C , ex:E .
[ a owl:Restriction ; owl:onProperty ex:r ;
owl:someValuesFrom [ owl:intersectionOf ( ex:C ex:E ) ] ] rdfs:subClassOf ex:D .",
);
assert!(has(&r, "A", "D"), "A ⊑ D missing; got {:?}", r.subsumptions);
assert!(r.complete, "{:?}", r.incompleteness);
}
#[test]
fn the_domain_of_an_existential_is_derived() {
let r = classify_ttl(
"ex:r a owl:ObjectProperty ; rdfs:domain ex:D .
ex:A rdfs:subClassOf [ a owl:Restriction ; owl:onProperty ex:r ; owl:someValuesFrom ex:B ] .",
);
assert!(has(&r, "A", "D"), "A ⊑ D missing; got {:?}", r.subsumptions);
assert!(r.complete, "{:?}", r.incompleteness);
}
#[test]
fn an_existential_through_a_transitive_role_is_derived() {
let r = classify_ttl(
"ex:r a owl:ObjectProperty , owl:TransitiveProperty .
ex:A rdfs:subClassOf [ a owl:Restriction ; owl:onProperty ex:r ; owl:someValuesFrom ex:B ] .
ex:B rdfs:subClassOf [ a owl:Restriction ; owl:onProperty ex:r ; owl:someValuesFrom ex:C ] .
[ a owl:Restriction ; owl:onProperty ex:r ; owl:someValuesFrom ex:C ] rdfs:subClassOf ex:D .",
);
assert!(has(&r, "A", "D"), "A ⊑ D missing; got {:?}", r.subsumptions);
assert!(r.complete, "{:?}", r.incompleteness);
}
/// A range reaches the filler: `A ⊑ ∃r.B`, `range(r) = C`, `∃r.(B ⊓ C) ⊑ D`.
#[test]
fn a_range_reaches_the_existential_filler() {
let r = classify_ttl(
"ex:r a owl:ObjectProperty ; rdfs:range ex:C .
ex:A rdfs:subClassOf [ a owl:Restriction ; owl:onProperty ex:r ; owl:someValuesFrom ex:B ] .
[ a owl:Restriction ; owl:onProperty ex:r ;
owl:someValuesFrom [ owl:intersectionOf ( ex:B ex:C ) ] ] rdfs:subClassOf ex:D .",
);
assert!(has(&r, "A", "D"), "A ⊑ D missing; got {:?}", r.subsumptions);
}
/// Disjointness reaches an existential's filler and makes `A` unsatisfiable.
#[test]
fn bottom_propagates_back_through_an_existential() {
let r = classify_ttl(
"ex:r a owl:ObjectProperty .
ex:B owl:disjointWith ex:C .
ex:A rdfs:subClassOf [ a owl:Restriction ; owl:onProperty ex:r ;
owl:someValuesFrom [ owl:intersectionOf ( ex:B ex:C ) ] ] .",
);
assert_eq!(r.unsatisfiable, vec!["http://ex.org/A".to_string()]);
assert!(r.complete && r.consistent, "{:?}", r.incompleteness);
}
/// Input outside EL says so and names why, and still gets the sound part.
#[test]
fn input_outside_el_is_marked_incomplete() {
let r = classify_ttl(
"ex:r a owl:ObjectProperty .
ex:A rdfs:subClassOf ex:B , [ owl:unionOf ( ex:C ex:E ) ] .
ex:F rdfs:subClassOf [ a owl:Restriction ; owl:onProperty ex:r ; owl:allValuesFrom ex:B ] .",
);
assert!(!r.complete);
assert_eq!(r.profile, "el-completion+owl-rl-ext");
assert!(r.incompleteness.iter().any(|w| w.contains("owl:unionOf")), "{:?}", r.incompleteness);
assert!(r.incompleteness.iter().any(|w| w.contains("owl:allValuesFrom")), "{:?}", r.incompleteness);
assert!(has(&r, "A", "B"));
}
/// A property chain is EL but the parser does not read it, so the table
/// cannot be called complete.
#[test]
fn an_unread_construct_is_marked_incomplete() {
let r = classify_ttl(
"ex:r a owl:ObjectProperty . ex:s a owl:ObjectProperty . ex:t a owl:ObjectProperty .
ex:t owl:propertyChainAxiom ( ex:r ex:s ) .
ex:A rdfs:subClassOf ex:B .",
);
assert!(!r.complete);
assert!(r.incompleteness.iter().any(|w| w.contains("owl:propertyChainAxiom")), "{:?}", r.incompleteness);
}
/// An individual in two disjoint classes makes the ontology inconsistent,
/// and an inconsistent ontology entails every subsumption.
#[test]
fn an_inconsistent_abox_is_reported() {
let r = classify_ttl(
"ex:B owl:disjointWith ex:C .
ex:a a ex:B , ex:C .",
);
assert!(!r.consistent);
assert!(!r.complete);
}
/// #324: the read-back used to stop at 100,000 rows and say nothing. A
/// chain of 460 classes has 460·459/2 = 105,570 strict subsumptions.
#[test]
fn a_table_over_one_hundred_thousand_pairs_is_not_cut() {
let n = 460;
let mut body = String::new();
for i in 1..n {
body.push_str(&format!("ex:C{i} rdfs:subClassOf ex:C{} .\n", i - 1));
}
let r = classify_ttl(&body);
assert_eq!(r.subsumption_count, n * (n - 1) / 2);
assert_eq!(r.subsumptions.len(), r.subsumption_count);
assert!(r.complete && !r.truncated);
}
}