Reliance-based Static Analysis of Existential Rules

Nils KüchenmeisterNils Küchenmeister

Nils Küchenmeister
Reliance-based Static Analysis of Existential Rules
Diploma Thesis, TU Dresden, August 2025

Details
Bibtex

KurzfassungAbstract
Cores are universal models of existential rules knowledge bases that have no redundant facts. They can be determined with the core chase, but this is expensive. Recent work suggested special positive and restraint reliance relations between rules to assess whether applying a rule can activate another and whether a rule should be preferred over another to avoid introducing unnecessary facts into the chase result. They give rise to core-stratifiable rulesets, which are susceptible to a rule-based selection strategy for the restricted chase that does not violate restraints and thus produces a core with certainty. However, there are still many practically relevant rulesets which are not core-stratifiable whilst still supporting core computation with a specialized selection strategy for the restricted chase.

We examine such cases to propose a new class of rulesets, which we call SCC-contraction core-stratifiable, that broadens the applicability of the restricted chase to compute cores. It is based on deputizing positive reliances by sets of contracted rules, which are formed by syntactically intersecting unifiable parts of the second rule’s body and the first rule’s head to attain the combined effect of applying two respective triggers in succession. Then, rulesets are contraction core-stratifiable iff they have no cycle in the restraints of the contracted reliance graph. We evaluate a prototype implementation on a subset of the Oxford Ontology Repository, revealing that a significant portion is covered by our analysis.
Weitere Informationen unter:Further Information: Link
Forschungsgruppe:Research Group: Wissensbasierte SystemeKnowledge-Based Systems

@misc{K2025,
  author = {Nils K{\"{u}}chenmeister},
  title  = {Reliance-based Static Analysis of Existential Rules},
  year   = {2025},
  month  = {August}
}