2020/12/04 by Conrad Indiono, Indiono, Conrad, Stefanie Rinderle‐Ma +1
Computer Science · Decision Sciences · #Advanced Database Systems and Queries #Data Quality and Management #Databases (cs.DB) #FOS: Computer and information sciences #Graph Theory and Algorithms
paper · pdf · doi:10.48550/arxiv.2012.02710
openalex publication_date 2020/12/04 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
The Rete forward inference algorithm forms the basis for many rule engines deployed today, but it exhibits the following problems: (1) the caching of all intermediate join results, (2) the processing of all rules regardless of the necessity to do so (stemming from the underlying forward inference approach), (3) not defining the join order of rules and its conditions, significantly affecting the final run-time performance, and finally (4) pointer chasing due to the overall network structure, leading to inefficient usage of the CPU caches caused by random access patterns. The Hiperfact approach aims to overcome these shortcomings by (1) choosing cache efficient data structures on the primary rank 1 fact index storage and intermediate join result storage levels, (2) introducing island fact processing for determining the join order by ensuring minimal intermediate join result construction, and (3) introducing derivation trees to allow for parallel read/write access and lazy rule evaluation. The experimental evaluations show that the Hiperfact prototype engine implementing the approach achieves significant improvements in respect to both inference and query performance. Moreover, the proposed Hiperfact engine is compared to existing engines in the context of a comprehensive benchmark.