Efficiency of Analysis of Transitive Relations using Query-Driven, Ground-and-Solve, and Fact-Driven Inference
It provides the first comparative efficiency analysis of all three inference methods for transitive relations, aiding practitioners in choosing the best method for their data.
The paper analyzes the efficiency of query-driven, ground-and-solve, and fact-driven inference methods for transitive relations, providing optimal time complexities and comparative analysis across rule variants and graph types, confirmed by experiments and a discovered performance bug.
Logic rules allow analysis of complex relationships to be expressed easily, especially for transitive relations in critical applications. However, understanding and predicting the efficiency of different inference methods remain challenging, even for simplest rules given different kinds of input data. This paper analyzes the efficiency of all three types of well-known inference methods -- query-driven, ground-and-solve, and fact-driven -- along with their respective optimizations, and compares with optimal complexities for the first time, for analyzing transitive graph relations. We also experiment with rule systems widely considered to have the best performance. We analyze all well-known rule variants and widely varying input graphs. The results include precisely calculated optimal time complexities; comparative analysis across different inference methods, rule variants, and graph types; confirmation with performance experiments; as well as discovery of a performance bug.