Reliance-Based Optimization of Existential Rule Reasoning

Diplom thesis by Alex Ivliev

Supervisor Markus Krötzsch
Wissensbasierte Systeme
1 April 2021 – 9 Dezember 2021
Download

Existential rules are a powerful formalism for describing implicit knowledge contained within a knowledge base. Extracting such knowledge can be achieved with the chase, which is a well-known algorithm for computing universal models. This is done by exhaustively calculating the consequences of each given rule. However, the order in which the rules are selected can have a significant impact on the run time of the procedure as well as the number of derived facts. It was discovered in recent work that core-stratified rule sets allow for a selection strategy that is guaranteed to produce so-called core models, which correspond to the smallest possible universal models if they are finite. The strategy is based on considering certain syntactic relationships between the rules called reliances. These indicate whether it is possible for a rule to produce facts used by another or if selecting a rule in the wrong order may introduce redundant facts into the result.

In this work, we utilize these reliances to devise rule application strategies that optimize the chase procedure based on the following criteria: First, we try to minimize the number of times rules are applied during the chase, aiming to improve run times. Second, we want to avoid applying rules in a way which introduces redundant facts. The goal here is to minimize the size of the resulting model, ideally producing a core. While it is always possible to derive a core model in core-stratified rule sets, we show situations where our approach is guaranteed to produce cores even if the rule set is not stratified. Moreover, we give a detailed description of the algorithms necessary for detecting a reliance relationship between two given rules as well as prove their correctness. We implement our approach into the rule reasoning engine VLog and evaluate its effectiveness on several knowledge bases used for benchmarking as well as some real-world data sets. We find a significant improvement in the run times for a small portion of the considered knowledge bases and are able to match VLog in the remaining ones.