1use crate::NQuin;
30
31pub const RDF_TYPE: u64 = crate::q_hash("http://www.w3.org/1999/02/22-rdf-syntax-ns#type");
34pub const RDFS_SUBCLASS_OF: u64 = crate::q_hash("http://www.w3.org/2000/01/rdf-schema#subClassOf");
35pub const RDFS_SUBPROPERTY_OF: u64 =
36 crate::q_hash("http://www.w3.org/2000/01/rdf-schema#subPropertyOf");
37pub const RDFS_DOMAIN: u64 = crate::q_hash("http://www.w3.org/2000/01/rdf-schema#domain");
38pub const RDFS_RANGE: u64 = crate::q_hash("http://www.w3.org/2000/01/rdf-schema#range");
39pub const OWL_SAME_AS: u64 = crate::q_hash("http://www.w3.org/2002/07/owl#sameAs");
40pub const OWL_INVERSE_OF: u64 = crate::q_hash("http://www.w3.org/2002/07/owl#inverseOf");
41pub const OWL_EQUIVALENT_CLASS: u64 =
42 crate::q_hash("http://www.w3.org/2002/07/owl#equivalentClass");
43pub const OWL_EQUIVALENT_PROPERTY: u64 =
44 crate::q_hash("http://www.w3.org/2002/07/owl#equivalentProperty");
45pub const OWL_DISJOINT_WITH: u64 = crate::q_hash("http://www.w3.org/2002/07/owl#disjointWith");
46pub const OWL_SYMMETRIC_PROPERTY: u64 =
47 crate::q_hash("http://www.w3.org/2002/07/owl#SymmetricProperty");
48pub const OWL_TRANSITIVE_PROPERTY: u64 =
49 crate::q_hash("http://www.w3.org/2002/07/owl#TransitiveProperty");
50pub const OWL_FUNCTIONAL_PROPERTY: u64 =
51 crate::q_hash("http://www.w3.org/2002/07/owl#FunctionalProperty");
52pub const OWL_INVERSE_FUNCTIONAL_PROPERTY: u64 =
53 crate::q_hash("http://www.w3.org/2002/07/owl#InverseFunctionalProperty");
54
55#[derive(Debug, Clone, Copy, PartialEq, Eq)]
60pub struct RdfTriple {
61 pub s: u64,
62 pub p: u64,
63 pub o: u64,
64}
65
66impl RdfTriple {
67 pub const fn new(s: u64, p: u64, o: u64) -> Self {
69 Self { s, p, o }
70 }
71
72 pub const fn from_nquin(q: &NQuin) -> Self {
74 Self {
75 s: q.subject,
76 p: q.predicate,
77 o: q.object,
78 }
79 }
80}
81
82#[derive(Debug, Clone, Copy, PartialEq, Eq)]
85pub struct ChainAxiom {
86 pub composed: u64,
87 pub first: u64,
88 pub second: u64,
89}
90
91#[derive(Debug, Clone, Copy, PartialEq, Eq)]
94pub struct DisjointnessViolation {
95 pub individual: u64,
96 pub class_a: u64,
97 pub class_b: u64,
98}
99
100#[derive(Debug, Clone, Copy, PartialEq, Eq)]
101pub enum MaterializeError {
102 WorkingSetFull,
104 ContradictionBufferFull,
106}
107
108#[derive(Debug, Clone, Copy, PartialEq, Eq)]
109pub struct MaterializeSummary {
110 pub triple_count: usize,
112 pub inferred_count: usize,
114 pub contradiction_count: usize,
116 pub iterations: u32,
118 pub saturated: bool,
120}
121
122#[inline]
125fn contains(triples: &[RdfTriple], len: usize, t: RdfTriple) -> bool {
126 triples[..len].iter().any(|&x| x == t)
127}
128
129#[inline]
132fn try_push(
133 triples: &mut [RdfTriple],
134 len: &mut usize,
135 t: RdfTriple,
136) -> Result<bool, MaterializeError> {
137 if contains(triples, *len, t) {
138 return Ok(false);
139 }
140 if *len >= triples.len() {
141 return Err(MaterializeError::WorkingSetFull);
142 }
143 triples[*len] = t;
144 *len += 1;
145 Ok(true)
146}
147
148pub fn materialize_owl_rl(
158 triples: &mut [RdfTriple],
159 initial_len: usize,
160 chains: &[ChainAxiom],
161 max_iters: u32,
162 contradictions_out: &mut [DisjointnessViolation],
163) -> Result<MaterializeSummary, MaterializeError> {
164 let mut len = initial_len.min(triples.len());
165 let mut iterations = 0u32;
166 let mut saturated = false;
167
168 while iterations < max_iters {
169 iterations += 1;
170 let mut changed = false;
171 let n = len; for i in 0..n {
174 let t = triples[i];
175
176 if t.p == OWL_EQUIVALENT_CLASS {
178 changed |= try_push(
179 triples,
180 &mut len,
181 RdfTriple::new(t.s, RDFS_SUBCLASS_OF, t.o),
182 )?;
183 changed |= try_push(
184 triples,
185 &mut len,
186 RdfTriple::new(t.o, RDFS_SUBCLASS_OF, t.s),
187 )?;
188 } else if t.p == OWL_EQUIVALENT_PROPERTY {
189 changed |= try_push(
190 triples,
191 &mut len,
192 RdfTriple::new(t.s, RDFS_SUBPROPERTY_OF, t.o),
193 )?;
194 changed |= try_push(
195 triples,
196 &mut len,
197 RdfTriple::new(t.o, RDFS_SUBPROPERTY_OF, t.s),
198 )?;
199 }
200 else if t.p == OWL_SAME_AS && t.s != t.o {
202 changed |= try_push(triples, &mut len, RdfTriple::new(t.o, OWL_SAME_AS, t.s))?;
203 }
204 else if t.p == OWL_INVERSE_OF {
206 let (p1, p2) = (t.s, t.o);
207 for j in 0..n {
208 let u = triples[j];
209 if u.p == p1 {
210 changed |= try_push(triples, &mut len, RdfTriple::new(u.o, p2, u.s))?;
211 }
212 if u.p == p2 {
213 changed |= try_push(triples, &mut len, RdfTriple::new(u.o, p1, u.s))?;
214 }
215 }
216 }
217 }
218
219 for i in 0..n {
221 let a = triples[i];
222 if a.p != RDFS_SUBCLASS_OF && a.p != RDFS_SUBPROPERTY_OF {
223 continue;
224 }
225 for j in 0..n {
226 let b = triples[j];
227 if b.p == a.p && b.s == a.o && a.s != b.o {
228 changed |= try_push(triples, &mut len, RdfTriple::new(a.s, a.p, b.o))?;
229 }
230 }
231 }
232
233 for i in 0..n {
236 let inst = triples[i];
237 for j in 0..n {
238 let ax = triples[j];
239 if ax.p == RDFS_SUBCLASS_OF
240 && inst.p == RDF_TYPE
241 && inst.o == ax.s
242 && inst.o != ax.o
243 {
244 changed |= try_push(triples, &mut len, RdfTriple::new(inst.s, RDF_TYPE, ax.o))?;
245 } else if ax.p == RDFS_SUBPROPERTY_OF && inst.p == ax.s && ax.s != ax.o {
246 changed |= try_push(triples, &mut len, RdfTriple::new(inst.s, ax.o, inst.o))?;
247 }
248 }
249 }
250
251 for i in 0..n {
253 let ax = triples[i];
254 if ax.p != RDFS_DOMAIN && ax.p != RDFS_RANGE {
255 continue;
256 }
257 for j in 0..n {
258 let inst = triples[j];
259 if inst.p == ax.s {
260 let subj = if ax.p == RDFS_DOMAIN { inst.s } else { inst.o };
261 changed |= try_push(triples, &mut len, RdfTriple::new(subj, RDF_TYPE, ax.o))?;
262 }
263 }
264 }
265
266 for i in 0..n {
269 let inst = triples[i];
270 if inst.p == RDF_TYPE {
271 continue;
272 }
273 let is_symmetric = contains(
274 triples,
275 len,
276 RdfTriple::new(inst.p, RDF_TYPE, OWL_SYMMETRIC_PROPERTY),
277 );
278 if is_symmetric && inst.s != inst.o {
279 changed |= try_push(triples, &mut len, RdfTriple::new(inst.o, inst.p, inst.s))?;
280 }
281 let is_transitive = contains(
282 triples,
283 len,
284 RdfTriple::new(inst.p, RDF_TYPE, OWL_TRANSITIVE_PROPERTY),
285 );
286 if is_transitive {
287 for j in 0..n {
288 let next = triples[j];
289 if next.p == inst.p && next.s == inst.o && inst.s != next.o {
290 changed |=
291 try_push(triples, &mut len, RdfTriple::new(inst.s, inst.p, next.o))?;
292 }
293 }
294 }
295 }
296
297 for i in 0..n {
300 let a = triples[i];
301 if a.p == RDF_TYPE {
302 continue;
303 }
304 let functional = contains(
305 triples,
306 len,
307 RdfTriple::new(a.p, RDF_TYPE, OWL_FUNCTIONAL_PROPERTY),
308 );
309 let inv_functional = contains(
310 triples,
311 len,
312 RdfTriple::new(a.p, RDF_TYPE, OWL_INVERSE_FUNCTIONAL_PROPERTY),
313 );
314 if !functional && !inv_functional {
315 continue;
316 }
317 for j in 0..n {
318 let b = triples[j];
319 if b.p != a.p {
320 continue;
321 }
322 if functional && b.s == a.s && a.o != b.o {
323 changed |= try_push(triples, &mut len, RdfTriple::new(a.o, OWL_SAME_AS, b.o))?;
324 }
325 if inv_functional && b.o == a.o && a.s != b.s {
326 changed |= try_push(triples, &mut len, RdfTriple::new(a.s, OWL_SAME_AS, b.s))?;
327 }
328 }
329 }
330
331 for i in 0..n {
333 let a = triples[i];
334 if a.p != OWL_SAME_AS {
335 continue;
336 }
337 for j in 0..n {
338 let b = triples[j];
339 if b.p == OWL_SAME_AS && b.s == a.o && a.s != b.o {
340 changed |= try_push(triples, &mut len, RdfTriple::new(a.s, OWL_SAME_AS, b.o))?;
341 }
342 }
343 }
344
345 for chain in chains {
347 for i in 0..n {
348 let lhs = triples[i];
349 if lhs.p != chain.first {
350 continue;
351 }
352 for j in 0..n {
353 let rhs = triples[j];
354 if rhs.p == chain.second && rhs.s == lhs.o {
355 changed |= try_push(
356 triples,
357 &mut len,
358 RdfTriple::new(lhs.s, chain.composed, rhs.o),
359 )?;
360 }
361 }
362 }
363 }
364
365 if !changed {
366 saturated = true;
367 break;
368 }
369 }
370
371 let mut contradiction_count = 0usize;
373 for i in 0..len {
374 let dj = triples[i];
375 if dj.p != OWL_DISJOINT_WITH {
376 continue;
377 }
378 let (c1, c2) = (dj.s, dj.o);
379 for j in 0..len {
380 let tj = triples[j];
381 if tj.p != RDF_TYPE || tj.o != c1 {
382 continue;
383 }
384 let x = tj.s;
385 if !contains(triples, len, RdfTriple::new(x, RDF_TYPE, c2)) {
386 continue;
387 }
388 let dup = contradictions_out[..contradiction_count].iter().any(|e| {
389 e.individual == x
390 && ((e.class_a == c1 && e.class_b == c2)
391 || (e.class_a == c2 && e.class_b == c1))
392 });
393 if dup {
394 continue;
395 }
396 if contradiction_count >= contradictions_out.len() {
397 return Err(MaterializeError::ContradictionBufferFull);
398 }
399 contradictions_out[contradiction_count] = DisjointnessViolation {
400 individual: x,
401 class_a: c1,
402 class_b: c2,
403 };
404 contradiction_count += 1;
405 }
406 }
407
408 Ok(MaterializeSummary {
409 triple_count: len,
410 inferred_count: len - initial_len.min(triples.len()),
411 contradiction_count,
412 iterations,
413 saturated,
414 })
415}
416
417#[cfg(test)]
418mod tests {
419 use super::*;
420
421 fn h(s: &str) -> u64 {
423 crate::q_hash(s)
424 }
425
426 #[test]
427 fn subclass_transitivity_and_type_propagation() {
428 let (alice, student, person, agent) = (h("alice"), h("Student"), h("Person"), h("Agent"));
429 let mut triples = [RdfTriple::new(0, 0, 0); 64];
430 triples[0] = RdfTriple::new(alice, RDF_TYPE, student);
431 triples[1] = RdfTriple::new(student, RDFS_SUBCLASS_OF, person);
432 triples[2] = RdfTriple::new(person, RDFS_SUBCLASS_OF, agent);
433 let mut contra = [DisjointnessViolation {
434 individual: 0,
435 class_a: 0,
436 class_b: 0,
437 }; 4];
438
439 let s = materialize_owl_rl(&mut triples, 3, &[], 16, &mut contra).unwrap();
440 assert!(s.saturated);
441 let out = &triples[..s.triple_count];
442 assert!(out.contains(&RdfTriple::new(student, RDFS_SUBCLASS_OF, agent)));
444 assert!(out.contains(&RdfTriple::new(alice, RDF_TYPE, person)));
446 assert!(out.contains(&RdfTriple::new(alice, RDF_TYPE, agent)));
447 assert_eq!(s.contradiction_count, 0);
448 }
449
450 #[test]
451 fn domain_and_range_typing() {
452 let (knows, person, x, y) = (h("knows"), h("Person"), h("x"), h("y"));
453 let mut triples = [RdfTriple::new(0, 0, 0); 32];
454 triples[0] = RdfTriple::new(knows, RDFS_DOMAIN, person);
455 triples[1] = RdfTriple::new(knows, RDFS_RANGE, person);
456 triples[2] = RdfTriple::new(x, knows, y);
457 let mut contra = [DisjointnessViolation {
458 individual: 0,
459 class_a: 0,
460 class_b: 0,
461 }; 2];
462
463 let s = materialize_owl_rl(&mut triples, 3, &[], 16, &mut contra).unwrap();
464 let out = &triples[..s.triple_count];
465 assert!(out.contains(&RdfTriple::new(x, RDF_TYPE, person))); assert!(out.contains(&RdfTriple::new(y, RDF_TYPE, person))); }
468
469 #[test]
470 fn transitive_and_inverse_properties() {
471 let (anc, has_child, a, b, c) = (h("ancestorOf"), h("hasChild"), h("a"), h("b"), h("c"));
472 let mut triples = [RdfTriple::new(0, 0, 0); 32];
473 triples[0] = RdfTriple::new(anc, RDF_TYPE, OWL_TRANSITIVE_PROPERTY);
474 triples[1] = RdfTriple::new(a, anc, b);
475 triples[2] = RdfTriple::new(b, anc, c);
476 triples[3] = RdfTriple::new(anc, OWL_INVERSE_OF, has_child);
477 let mut contra = [DisjointnessViolation {
478 individual: 0,
479 class_a: 0,
480 class_b: 0,
481 }; 2];
482
483 let s = materialize_owl_rl(&mut triples, 4, &[], 16, &mut contra).unwrap();
484 let out = &triples[..s.triple_count];
485 assert!(out.contains(&RdfTriple::new(a, anc, c))); assert!(out.contains(&RdfTriple::new(b, has_child, a))); assert!(out.contains(&RdfTriple::new(c, has_child, b)));
488 }
489
490 #[test]
491 fn property_chain_unrolling() {
492 let (parent, brother, uncle, x, p, u) = (
494 h("parentOf"),
495 h("brotherOf"),
496 h("uncleOf"),
497 h("x"),
498 h("p"),
499 h("u"),
500 );
501 let mut triples = [RdfTriple::new(0, 0, 0); 16];
502 triples[0] = RdfTriple::new(x, parent, p);
503 triples[1] = RdfTriple::new(p, brother, u);
504 let chains = [ChainAxiom {
505 composed: uncle,
506 first: parent,
507 second: brother,
508 }];
509 let mut contra = [DisjointnessViolation {
510 individual: 0,
511 class_a: 0,
512 class_b: 0,
513 }; 2];
514
515 let s = materialize_owl_rl(&mut triples, 2, &chains, 16, &mut contra).unwrap();
516 assert!(triples[..s.triple_count].contains(&RdfTriple::new(x, uncle, u)));
517 }
518
519 #[test]
520 fn disjointness_isolation_does_not_halt() {
521 let (cat, dog, animal, fido, rex, pet, breed) = (
524 h("Cat"),
525 h("Dog"),
526 h("Animal"),
527 h("fido"),
528 h("rex"),
529 h("Pet"),
530 h("Breed"),
531 );
532 let mut triples = [RdfTriple::new(0, 0, 0); 64];
533 triples[0] = RdfTriple::new(cat, OWL_DISJOINT_WITH, dog);
534 triples[1] = RdfTriple::new(fido, RDF_TYPE, cat);
535 triples[2] = RdfTriple::new(fido, RDF_TYPE, dog);
536 triples[3] = RdfTriple::new(breed, RDFS_SUBCLASS_OF, pet);
537 triples[4] = RdfTriple::new(rex, RDF_TYPE, breed);
538 let _ = animal;
539 let mut contra = [DisjointnessViolation {
540 individual: 0,
541 class_a: 0,
542 class_b: 0,
543 }; 4];
544
545 let s = materialize_owl_rl(&mut triples, 5, &[], 16, &mut contra).unwrap();
546 assert_eq!(s.contradiction_count, 1);
548 assert_eq!(contra[0].individual, fido);
549 assert!(triples[..s.triple_count].contains(&RdfTriple::new(rex, RDF_TYPE, pet)));
551 }
552
553 #[test]
554 fn functional_property_implies_sameas() {
555 let (has_ssn, x, a, b) = (h("hasSSN"), h("x"), h("idA"), h("idB"));
557 let mut triples = [RdfTriple::new(0, 0, 0); 16];
558 triples[0] = RdfTriple::new(has_ssn, RDF_TYPE, OWL_FUNCTIONAL_PROPERTY);
559 triples[1] = RdfTriple::new(x, has_ssn, a);
560 triples[2] = RdfTriple::new(x, has_ssn, b);
561 let mut contra = [DisjointnessViolation {
562 individual: 0,
563 class_a: 0,
564 class_b: 0,
565 }; 2];
566
567 let s = materialize_owl_rl(&mut triples, 3, &[], 16, &mut contra).unwrap();
568 let out = &triples[..s.triple_count];
569 assert!(
570 out.contains(&RdfTriple::new(a, OWL_SAME_AS, b))
571 || out.contains(&RdfTriple::new(b, OWL_SAME_AS, a))
572 );
573 assert!(out.contains(&RdfTriple::new(a, OWL_SAME_AS, b)));
575 assert!(out.contains(&RdfTriple::new(b, OWL_SAME_AS, a)));
576 }
577
578 #[test]
579 fn working_set_full_is_reported() {
580 let (a, sub) = (h("a"), RDFS_SUBCLASS_OF);
581 let mut triples = [RdfTriple::new(0, 0, 0); 6];
583 triples[0] = RdfTriple::new(a, RDF_TYPE, h("C0"));
584 triples[1] = RdfTriple::new(h("C0"), sub, h("C1"));
585 triples[2] = RdfTriple::new(h("C1"), sub, h("C2"));
586 triples[3] = RdfTriple::new(h("C2"), sub, h("C3"));
587 let mut contra = [DisjointnessViolation {
588 individual: 0,
589 class_a: 0,
590 class_b: 0,
591 }; 2];
592 let r = materialize_owl_rl(&mut triples, 4, &[], 16, &mut contra);
593 assert_eq!(r, Err(MaterializeError::WorkingSetFull));
594 }
595}