Reliance-Based Optimization of Existential Rule Reasoning

Reliance-Based Optimization of Existential Rule Reasoning

Vortrag von Alex Ivliev

• Veranstaltungsort: Online
• Beginn: 9. Dezember 2021 um 09:45
• Ende: 9. Dezember 2021 um 10:45
• Event series: Research Seminar Logic and AI
• iCal

Existential rules is a powerful formalism for describing implicit knowledge contained within a dataset. 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, in the finite case, correspond to the smallest possible universal models. 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 datasets. 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.

This is a diploma defense, the talk is online.

Link: https://bbb.tu-dresden.de/b/ali-zgz-l8d-52n