Practical Rule-Based Qualitative Temporal Reasoning for the Semantic Web

Abstract

We present an approach for practical rule-based temporal reasoning over RDF/OWL using Allen’s Interval Algebra (IA). Reasoning in Allen’s IA is only tractable for certain subalgebras and is done through path-consistency, a constraint propagation algorithm whose rule-based implementation requires 𝑂(𝑛2) rules for a subalgebra with n relations. Our approach uses custom built-ins to implement path-consistency using a constant number of rules (just 6) and in a way that is subalgebra-agnostic. In the paper, we present the approach, its implementation in Apache Jena, and an experimental evaluation against traditional rule-based implementations. The evaluation shows a considerable speed-up when backward-chaining is used. A further contribution of the paper is the problem set used in the evaluations.