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
//! Property-combination lattice + data-driven SHACL shape induction (#36,
//! K-CAP 2025 Kastor).
//!
//! Two layers:
//!
//! 1. **`enumerate`** — pure combinatorial enumeration of property-subset
//! candidates up to `max_size`. Bounded at `2^max_size` to prevent
//! pathological blowup.
//!
//! 2. **`induce_shapes`** — Kastor-style data-driven induction. For each
//! candidate subset, evaluates against the loaded ontology's instance
//! data and computes `support` (fraction of class instances that have
//! ALL properties in the subset) and `confidence` (fraction of
//! instances-with-this-subset that are also instances of the class).
//! Ranks candidates by `support × confidence` and emits the top-k as
//! proposed SHACL `NodeShape`s with `sh:property` blocks.
use crate::graph::GraphStore;
use serde::Serialize;
use std::collections::BTreeSet;
use std::sync::Arc;
#[derive(Clone, Debug, Serialize)]
pub struct LatticeReport {
pub class_iri: String,
pub properties_found: usize,
pub max_size: usize,
pub subsets_total: usize,
/// Each subset is a sorted list of property IRIs. Sorted globally by
/// (size, lex) for stable output.
pub subsets: Vec<Vec<String>>,
}
/// One induced candidate shape with its quality scores.
#[derive(Clone, Debug, Serialize)]
pub struct CandidateShape {
/// Property IRIs the shape requires.
pub properties: Vec<String>,
/// Fraction of class instances that have every property in this subset
/// (in `[0, 1]`).
pub support: f64,
/// Fraction of instances-with-this-subset that are members of the class
/// (in `[0, 1]`). Higher confidence = more class-discriminative subset.
pub confidence: f64,
/// `support × confidence`, used to rank candidates.
pub score: f64,
/// Number of class instances covered by this shape.
pub instances_covered: u64,
/// SHACL NodeShape Turtle text proposing this constraint.
pub shape_ttl: String,
}
#[derive(Clone, Debug, Serialize)]
pub struct InductionReport {
pub class_iri: String,
pub class_instance_count: u64,
pub candidates_evaluated: usize,
pub shapes: Vec<CandidateShape>,
}
/// Enumerate property-combination subsets up to `max_size` for a class.
pub fn enumerate(graph: &Arc<GraphStore>, class_iri: &str, max_size: usize) -> anyhow::Result<LatticeReport> {
let max_size = if max_size == 0 { 3 } else { max_size };
let q = format!(
"SELECT DISTINCT ?p WHERE {{ ?p <http://www.w3.org/2000/01/rdf-schema#domain> <{}> }} LIMIT 100",
class_iri
);
// Every graph: see `count_query`. A property is declared on the class
// wherever the declaration sits.
let js = graph.sparql_select_union(&q)?;
let v: serde_json::Value = serde_json::from_str(&js)?;
let rows = v["results"].as_array().cloned().unwrap_or_default();
let mut props: Vec<String> = rows
.iter()
.filter_map(|r| {
r["p"]
.as_str()
.map(|s| s.trim_matches(|c| c == '<' || c == '>').to_string())
})
.collect();
props.sort();
props.dedup();
let k = props.len();
let cap = max_size.min(k);
// Guard the combinatorial blow-up BEFORE materialising anything. max_size is a
// caller-supplied usize with no upper bound, and a moderately wide class makes
// the subset count astronomical (C(100, 50) ≈ 1e29), each subset an allocated
// Vec — an out-of-memory kill from one tool call. Sum the binomials and refuse
// past a budget instead.
const SUBSET_BUDGET: u64 = 200_000;
let mut estimate: u64 = 0;
for size in 1..=cap {
estimate = estimate.saturating_add(binomial(k as u64, size as u64));
if estimate > SUBSET_BUDGET {
anyhow::bail!(
"shape enumeration for {class_iri} would produce more than {SUBSET_BUDGET} \
subsets ({k} properties up to size {cap}); lower max_size"
);
}
}
let mut subsets: Vec<Vec<String>> = vec![Vec::new()];
for size in 1..=cap {
for combo in combinations(&props, size) {
subsets.push(combo);
}
}
// Sort by (size, lex).
subsets.sort_by(|a, b| a.len().cmp(&b.len()).then_with(|| a.cmp(b)));
let total = subsets.len();
Ok(LatticeReport {
class_iri: class_iri.to_string(),
properties_found: k,
max_size,
subsets_total: total,
subsets,
})
}
/// C(n, k) with a u128 intermediate, saturating to u64::MAX so an enormous
/// binomial cannot overflow the budget check that guards enumeration.
fn binomial(n: u64, k: u64) -> u64 {
if k > n {
return 0;
}
let k = k.min(n - k);
let mut result: u128 = 1;
for i in 1..=k {
result = result.saturating_mul((n - k + i) as u128) / (i as u128);
if result > u64::MAX as u128 {
return u64::MAX;
}
}
result as u64
}
/// Enumerate k-subsets of `items` in lexicographic order. Iterative
/// implementation; no recursion-depth risk for k up to a handful.
fn combinations(items: &[String], k: usize) -> Vec<Vec<String>> {
let n = items.len();
if k == 0 || k > n {
return Vec::new();
}
let mut out: Vec<Vec<String>> = Vec::new();
let mut indices: Vec<usize> = (0..k).collect();
loop {
out.push(indices.iter().map(|&i| items[i].clone()).collect());
// Find the rightmost index that can be incremented.
let mut i = k;
while i > 0 && indices[i - 1] == n - k + (i - 1) {
i -= 1;
}
if i == 0 {
break;
}
indices[i - 1] += 1;
for j in i..k {
indices[j] = indices[j - 1] + 1;
}
}
out
}
/// Unused helper kept for completeness — exposes the underlying set type.
#[allow(dead_code)]
fn to_set(items: &[String]) -> BTreeSet<String> {
items.iter().cloned().collect()
}
/// Induce candidate SHACL shapes from data (#36 Kastor proper). For each
/// non-empty property subset enumerated up to `max_size`, evaluate support +
/// confidence against the loaded instance data, then return the top
/// `top_k` by `support × confidence` (default 10).
///
/// `min_support` and `min_confidence` filter weak candidates (default 0.1
/// and 0.5 respectively).
pub fn induce_shapes(
graph: &Arc<GraphStore>,
class_iri: &str,
max_size: usize,
top_k: usize,
min_support: f64,
min_confidence: f64,
) -> anyhow::Result<InductionReport> {
let lattice = enumerate(graph, class_iri, max_size)?;
// Count class instances.
let class_count = count_query(
graph,
&format!(
"SELECT (COUNT(?x) AS ?n) WHERE {{ ?x a <{}> }}",
class_iri
),
)?;
let mut candidates: Vec<CandidateShape> = Vec::new();
for subset in &lattice.subsets {
if subset.is_empty() {
continue;
}
// count_class_with_subset: instances of class that have all
// properties in subset.
let class_with = count_class_with_subset(graph, class_iri, subset)?;
// count_with_subset: instances ANYWHERE that have all properties.
let any_with = count_any_with_subset(graph, subset)?;
let support = if class_count == 0 {
0.0
} else {
class_with as f64 / class_count as f64
};
let confidence = if any_with == 0 {
0.0
} else {
class_with as f64 / any_with as f64
};
if support < min_support || confidence < min_confidence {
continue;
}
let score = support * confidence;
let shape_ttl = render_shape_ttl(class_iri, subset);
candidates.push(CandidateShape {
properties: subset.clone(),
support,
confidence,
score,
instances_covered: class_with,
shape_ttl,
});
}
candidates.sort_by(|a, b| b.score.partial_cmp(&a.score).unwrap_or(std::cmp::Ordering::Equal));
candidates.truncate(top_k);
let evaluated = lattice.subsets.iter().filter(|s| !s.is_empty()).count();
Ok(InductionReport {
class_iri: class_iri.to_string(),
class_instance_count: class_count,
candidates_evaluated: evaluated,
shapes: candidates,
})
}
/// Reads every graph: the instances of a class are the store's instances,
/// whichever graph they sit in. Over a dataset serialisation this counted
/// zero and induction returned an empty lattice, indistinguishable from a
/// class that genuinely has no instances (#108).
fn count_query(graph: &Arc<GraphStore>, q: &str) -> anyhow::Result<u64> {
let js = graph.sparql_select_union(q)?;
let v: serde_json::Value = serde_json::from_str(&js).unwrap_or(serde_json::Value::Null);
let n_str = v["results"][0]["n"].as_str().unwrap_or("0");
// SPARQL aggregate values come as literal strings like
// `"5"^^<http://www.w3.org/2001/XMLSchema#integer>`. Strip the typed
// wrapper, keep just the digits.
let digits: String = n_str.chars().take_while(|c| c.is_ascii_digit()).collect();
// If the leading char was a quote (Oxigraph string-encodes literals)
// skip it and read until the next quote.
let cleaned: String = if n_str.starts_with('"') {
n_str
.chars()
.skip(1)
.take_while(|c| c.is_ascii_digit())
.collect()
} else if !digits.is_empty() {
digits
} else {
n_str.chars().filter(|c| c.is_ascii_digit()).collect()
};
Ok(cleaned.parse::<u64>().unwrap_or(0))
}
fn count_class_with_subset(
graph: &Arc<GraphStore>,
class_iri: &str,
subset: &[String],
) -> anyhow::Result<u64> {
if subset.is_empty() {
return Ok(0);
}
let mut patterns: Vec<String> = vec![format!("?x a <{}>", class_iri)];
for (i, p) in subset.iter().enumerate() {
patterns.push(format!("?x <{}> ?o{}", p, i));
}
let q = format!(
"SELECT (COUNT(DISTINCT ?x) AS ?n) WHERE {{ {} }}",
patterns.join(" . ")
);
count_query(graph, &q)
}
fn count_any_with_subset(graph: &Arc<GraphStore>, subset: &[String]) -> anyhow::Result<u64> {
if subset.is_empty() {
return Ok(0);
}
let mut patterns: Vec<String> = Vec::new();
for (i, p) in subset.iter().enumerate() {
patterns.push(format!("?x <{}> ?o{}", p, i));
}
let q = format!(
"SELECT (COUNT(DISTINCT ?x) AS ?n) WHERE {{ {} }}",
patterns.join(" . ")
);
count_query(graph, &q)
}
/// Render a SHACL NodeShape proposing the subset's properties as
/// `sh:property` blocks with `sh:minCount 1`.
fn render_shape_ttl(class_iri: &str, subset: &[String]) -> String {
let mut out = String::new();
out.push_str("@prefix sh: <http://www.w3.org/ns/shacl#> .\n");
out.push_str(&format!(
"<{}-shape> a sh:NodeShape ;\n",
class_iri
));
out.push_str(&format!(" sh:targetClass <{}> ;\n", class_iri));
for (i, p) in subset.iter().enumerate() {
let prefix = if i + 1 == subset.len() { "" } else { " ;" };
out.push_str(&format!(
" sh:property [ sh:path <{}> ; sh:minCount 1 ]{}\n",
p, prefix
));
}
out.push_str(".\n");
out
}
#[cfg(test)]
mod tests {
use super::*;
fn graph_with_properties() -> Arc<GraphStore> {
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:Person a owl:Class .
ex:name a owl:DatatypeProperty ; rdfs:domain ex:Person .
ex:age a owl:DatatypeProperty ; rdfs:domain ex:Person .
ex:email a owl:DatatypeProperty ; rdfs:domain ex:Person .
"#,
None,
)
.unwrap();
g
}
#[test]
fn binomial_is_exact_and_saturates() {
assert_eq!(binomial(3, 2), 3);
assert_eq!(binomial(100, 2), 4950);
assert_eq!(binomial(52, 5), 2_598_960);
assert_eq!(binomial(5, 9), 0);
// A huge central binomial saturates rather than overflowing.
assert_eq!(binomial(100, 50), u64::MAX);
}
#[test]
fn enumerate_refuses_a_combinatorial_blowup() {
// A class wide enough that the requested max_size explodes the lattice.
let g = Arc::new(GraphStore::new());
let mut ttl = String::from(
"@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 ex:Wide a owl:Class .\n",
);
for i in 0..40 {
ttl.push_str(&format!(
"ex:p{i} a owl:DatatypeProperty ; rdfs:domain ex:Wide .\n"
));
}
g.load_turtle(&ttl, None).unwrap();
// C(40,20) alone is ~1.4e11: must refuse instead of allocating it.
let err = enumerate(&g, "http://ex.org/Wide", 20).unwrap_err();
assert!(
err.to_string().contains("more than"),
"must refuse the blow-up, got: {err}"
);
// A small max_size on the same wide class is fine.
assert!(enumerate(&g, "http://ex.org/Wide", 2).is_ok());
}
#[test]
fn enumerate_full_lattice_for_three_properties_max_3() {
let g = graph_with_properties();
let r = enumerate(&g, "http://ex.org/Person", 3).unwrap();
assert_eq!(r.properties_found, 3);
// Empty + 3 singletons + 3 pairs + 1 triple = 8 = 2^3.
assert_eq!(r.subsets_total, 8);
// First subset is the empty one.
assert_eq!(r.subsets[0], Vec::<String>::new());
}
#[test]
fn enumerate_capped_at_max_size() {
let g = graph_with_properties();
let r = enumerate(&g, "http://ex.org/Person", 1).unwrap();
// Empty + 3 singletons = 4.
assert_eq!(r.subsets_total, 4);
}
#[test]
fn enumerate_returns_just_empty_subset_for_no_properties() {
let g = Arc::new(GraphStore::new());
g.load_turtle(
"@prefix owl: <http://www.w3.org/2002/07/owl#> . @prefix ex: <http://ex.org/> . ex:Lonely a owl:Class .",
None,
)
.unwrap();
let r = enumerate(&g, "http://ex.org/Lonely", 3).unwrap();
assert_eq!(r.properties_found, 0);
assert_eq!(r.subsets_total, 1);
assert_eq!(r.subsets[0], Vec::<String>::new());
}
fn graph_with_class_and_instances() -> Arc<GraphStore> {
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:Person a owl:Class .
ex:name a owl:DatatypeProperty ; rdfs:domain ex:Person .
ex:age a owl:DatatypeProperty ; rdfs:domain ex:Person .
ex:email a owl:DatatypeProperty ; rdfs:domain ex:Person .
# 3 instances of Person, 2 with name+age, 1 with only name.
ex:alice a ex:Person ; ex:name "Alice" ; ex:age 30 .
ex:bob a ex:Person ; ex:name "Bob" ; ex:age 25 .
ex:charlie a ex:Person ; ex:name "Charlie" .
# 1 NON-Person instance with the same property — should lower
# confidence on {name}.
ex:nonperson_dog ex:name "Rex" .
"#,
None,
)
.unwrap();
g
}
#[test]
fn induce_shapes_returns_high_support_subsets() {
let g = graph_with_class_and_instances();
let r = induce_shapes(
&g,
"http://ex.org/Person",
3,
10,
0.1,
0.5,
)
.unwrap();
assert_eq!(r.class_instance_count, 3);
// {name} has support 3/3 = 1.0; confidence 3/4 = 0.75 (Rex is not
// a Person). Should be the top candidate.
let top = r
.shapes
.iter()
.find(|c| c.properties == vec!["http://ex.org/name".to_string()])
.expect("name subset should be in induced shapes");
assert!((top.support - 1.0).abs() < 1e-9);
assert!((top.confidence - 0.75).abs() < 1e-9);
assert_eq!(top.instances_covered, 3);
}
#[test]
fn induce_shapes_filters_by_min_support() {
let g = graph_with_class_and_instances();
// {email} has support 0 (no Person instance has it).
let r = induce_shapes(
&g,
"http://ex.org/Person",
3,
10,
0.5,
0.0,
)
.unwrap();
let email_in_shapes = r
.shapes
.iter()
.any(|c| c.properties == vec!["http://ex.org/email".to_string()]);
assert!(!email_in_shapes,
"email has zero support, should be filtered by min_support=0.5");
}
#[test]
fn induce_shapes_renders_valid_shacl_turtle() {
let g = graph_with_class_and_instances();
let r = induce_shapes(
&g,
"http://ex.org/Person",
2,
5,
0.1,
0.5,
)
.unwrap();
let top = r.shapes.first().expect("at least one shape");
assert!(top.shape_ttl.contains("sh:NodeShape"));
assert!(top.shape_ttl.contains("sh:targetClass"));
assert!(top.shape_ttl.contains("sh:property"));
assert!(top.shape_ttl.contains("sh:minCount 1"));
// Should parse as valid Turtle.
let test_graph = Arc::new(GraphStore::new());
let load_result = test_graph.load_turtle(&top.shape_ttl, None);
assert!(load_result.is_ok(),
"induced shape Turtle should parse: error: {:?}\nturtle:\n{}",
load_result.err(), top.shape_ttl);
}
#[test]
fn induce_shapes_ranks_by_score_descending() {
let g = graph_with_class_and_instances();
let r = induce_shapes(
&g,
"http://ex.org/Person",
3,
10,
0.1,
0.5,
)
.unwrap();
// Score must be monotonically non-increasing.
for w in r.shapes.windows(2) {
assert!(
w[0].score >= w[1].score,
"shapes not ranked: {} < {} (props {:?} vs {:?})",
w[0].score, w[1].score, w[0].properties, w[1].properties
);
}
}
#[test]
fn induce_shapes_handles_class_with_no_instances() {
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:Empty a owl:Class . ex:p a owl:DatatypeProperty ; rdfs:domain ex:Empty .",
None,
)
.unwrap();
let r = induce_shapes(
&g,
"http://ex.org/Empty",
3,
10,
0.1,
0.5,
)
.unwrap();
assert_eq!(r.class_instance_count, 0);
// No support for any subset → empty result.
assert!(r.shapes.is_empty());
}
#[test]
fn enumerate_zero_max_size_defaults_to_three() {
let g = graph_with_properties();
let r = enumerate(&g, "http://ex.org/Person", 0).unwrap();
// 0 is the sentinel for "use the default of 3" — enumeration
// produces the full 2^3 = 8 lattice.
assert_eq!(r.subsets_total, 8);
assert_eq!(r.max_size, 3);
}
}