Efficient Dependency Analysis for Rule-Based Ontologies
This work addresses the gap between theoretical dependency analysis and practical implementation for rule-based ontologies, enabling more efficient reasoning applications in fields like knowledge representation and query answering, though it is incremental as it builds on existing dependency concepts.
The paper tackled the problem of implementing rule dependencies for static analysis of existential rule ontologies, which were rarely implemented despite their potential for practical applications like ontology-based query answering. The result was the design and implementation of optimized algorithms for computing positive reliances and restraints, showing scalability on real-world ontologies with over 100,000 rules and enabling practical case studies such as analyzing redundancy-free knowledge graphs.
Several types of dependencies have been proposed for the static analysis of existential rule ontologies, promising insights about computational properties and possible practical uses of a given set of rules, e.g., in ontology-based query answering. Unfortunately, these dependencies are rarely implemented, so their potential is hardly realised in practice. We focus on two kinds of rule dependencies -- positive reliances and restraints -- and design and implement optimised algorithms for their efficient computation. Experiments on real-world ontologies of up to more than 100,000 rules show the scalability of our approach, which lets us realise several previously proposed applications as practical case studies. In particular, we can analyse to what extent rule-based bottom-up approaches of reasoning can be guaranteed to yield redundancy-free "lean" knowledge graphs (so-called cores) on practical ontologies.