Reasoning in Financial Settings with Harmful Joins Teodoro Baldazzi1 , Paolo Atzeni1 1 Università Roma Tre, Department of Computer Science and Engineering, Rome, Italy Abstract Warded Datalog+/- has recently emerged as a powerful logic language for ontological reasoning on large knowledge graphs, offering a very good trade-off between expressive power and data complexity. Achieving decidability and data tractability in practice, over complex recursive settings with existential quantification, requires reasoners to adopt specialized strategies that control the effects of recursion and ensure reasoning termination with small memory footprint. However, to enable these strategies, the Warded Datalog+/- settings must be in a “harmless” form, i.e., without joins on variables affected by existential quantification. We provide an algorithm to remove such “harmful” joins, supporting reasoning decidability and the full expressive power of the language while preserving the correctness of the task. The algorithm is integrated into the Vadalog system, a state-of-the-art Warded Datalog+/- -based reasoner. We employ it to solve the Strong Link problem, a relevant financial task to find possible links between pairs of companies, based on the existence of a person who owns a significant share of both their stocks. Solving this problem allows to investigate possibly malevolent shareholdings and ownerships. Keywords Datalog, Vadalog, ontological reasoning, existential quantification, harmful joins, financial scenarios 1. Introduction PTIME data complexity for the reasoning. The semantics of a set Σ of Warded rules over a database instance 𝐷 is Recent years have witnessed a growing interest, among defined via the chase procedure [6]. Intuitively, it adds companies of distinct size and scope, towards building new facts to 𝐷, possibly containing freshly generated and exploiting private corporate knowledge in the form symbols 𝜈 (technically, labelled nulls) [7] that act as place- of financial Knowledge Graphs (KG). This led to the ris- holders for the existentially quantified variables, until ing adoption of intelligent systems that allow to manage Σ is satisfied. Warded Datalog± is implemented in the such extensional knowledge and enrich it with new infor- Vadalog system [3], a state-of-the-art reasoner that allows mation, inferred via efficient ontological reasoning mech- to perform ontological reasoning in complex scenarios. anisms and modeled by logical rules and ontologies in Critical Aspects in Reasoning. When reasoning on specific formalisms [1, 2]. Employing modern languages Datalog± settings, in the presence of recursion and ex- for Knowledge Representation and Reasoning (KRR) [3] istential quantification, infinite labelled nulls could be enabled companies to solve relevant problems and tasks generated in the chase, causing the procedure not to ter- in distinct business domains, such as investment analysis, minate and inhibiting the decidability of the task [8]. In company ownership, shock propagation, fraud detection, this work, we tackle such issue in the context of Warded anti-money laundering, etc. Datalog± scenarios. Indeed, while the computational A Formalism for Ontological Reasoning. As main re- properties of the Warded fragment bode well for efficient quirements, KRR languages must exhibit full support for implementations, it is still required to apply specific tech- recursion and joins as well as existential quantification, niques (namely, termination strategies) that properly con- all aspects essential to guarantee the expressive power trol the interactions between recursion and existentials needed for ontological reasoning and KG traversal. At the in the chase. Consider the following example. same time, decidability and tractability of the reasoning must be sustained, basically limiting the data complexity Example 1. Scenario modeled with a Warded set Σ. to a polynomial degree [4]. Warded Datalog± [2] is a member (technically, a fragment) of the Datalog± fam- Bank(x) → ∃d Manager(x, d) (𝛼) ily [5] that recently rose among the logic languages for Acquires(x, y), Manager(x, d) → Manager(y, d) (𝛽) ontological reasoning on KGs. It covers these require- BankGroup(x, y) → ∃d Manager(x, d) (𝛾) ments, offering a very good trade-off between expres- sive power and computational complexity and capturing Manager(x, d), Manager(y, d) → BankGroup(x, y) (𝜌) Published in the Workshop Proceedings of the EDBT/ICDT 2022 Joint Σ represents a bank acquisition scenario. For each bank 𝑥 Conference (March 29-April 1, 2022), Edinburgh, UK there exists a manager 𝑑 (rule 𝛼). If 𝑥 acquires a bank 𝑦, $ teodoro.baldazzi@uniroma3.it (T. Baldazzi); 𝑑 also becomes manager of 𝑦 (rule 𝛽). If 𝑥 and 𝑦 have a paolo.atzeni@uniroma3.it (P. Atzeni) common manager, they are in the same bank group (rule 𝜌) © 2022 Copyright for this paper by its authors. Use permitted under Creative CEUR Commons License Attribution 4.0 International (CC BY 4.0). and vice versa (rule 𝛾). Workshop Proceedings http://ceur-ws.org ISSN 1613-0073 CEUR Workshop Proceedings (CEUR-WS.org) Consider the database instance 𝐷 = {Bank(Unicredit), The applicability of the isomorphism termination strat- Bank(MPS), Acquires(Unicredit, MPS)} and the query 𝑄: egy, to achieve reasoning decidability while preserving “what are all the BankGroups?” as ontological reasoning correctness of query answering, is essential in such com- task. It can be observed that the set of such bank groups plex domains. Therefore, reasoning settings that feature is finite, whereas the chase does not terminate. First, harmful joins and recursion require to be treated properly. we generate Manager(Unicredit,𝜈0 ) and Manager(MPS,𝜈1 ) Such is the case of the Strong Link problem [9], a high- by activating 𝛼 from the facts Bank(Unicredit) and interest scenario in the context of company ownership. Bank(MPS), respectively. Then, we obtain Man- It consists in determining possible links between pairs of ager(MPS,𝜈0 ) via 𝛽, BankGroup(Unicredit,MPS) via the companies, based on the existence of a person who owns join on 𝜈0 in 𝜌, Manager(Unicredit,𝜈2 ), Manager(MPS,𝜈2 ) a significant share of both their stocks. Solving this task by activating 𝛾 and so on. Indeed, the recursion involv- allows to investigate and monitor (possibly malevolent) ⋃︀ 𝛽, 𝛾 and 𝜌 causes the generation of an infinite set ing company shareholdings and ownerships. 𝑖=3,... {Manager(Unicredit, 𝜈𝑖 ), Manager(MPS, 𝜈𝑖 )}. Motivated by this, we apply our HJE algorithm to the ± Enabling Reasoning Termination in Vadalog. To Warded Datalog scenario of Strong Link, rewriting it achieve reasoning termination in practice, while uphold- into its Harmless Warded equivalent and enabling the ing the correctness of the task, the Vadalog system applies Vadalog system to solve the task in an efficient fashion, the isomorphism termination strategy in the chase: iso- while preserving correctness. morphic copies of previously generated facts (i.e., same In detail, the main contributions of this paper are: name, same constants in same position and bijection be- tween labelled nulls) are not explored, i.e., the chase steps • An integration of the theoretical bases for the starting from them are not performed and the derived Warded fragment. We introduce Harmless Warded facts are not generated. This strategy exploits the the- Datalog± and we discuss the role of harmful joins in ± Warded settings, with reference to expressive power oretical underpinning of Warded Datalog known as reasoning boundedness, which states that facts derived and reasoning termination. We define and solve the from isomorphic origins would be in turn isomorphic, disarmament problem, which consists in rewriting a thus uninformative for query answering [9]. set of Warded rules with harmful joins into a Harmless However, as a necessary condition for such exploita- Warded version, equivalent with respect to the chase. tion, the set of rules is required to be in a “harmless” • The Harmful Join Elimination algorithm, our rewrit- form, i.e., without a “harmful” type of joins between ing technique that exploits such bases to solve the variables affected by existential quantification (namely, disarmament problem and enable Vadalog’s termina- in Harmless Warded Datalog± ). This is due to the fact tion strategy in practice on recursive reasoning set- that rules with these harmful joins could activate on tings with harmful joins. We illustrate the procedure labelled nulls, propagated from the existentials: there- and we apply it to the program in Example 1. fore, the suppression of isomorphic facts carrying such nulls could hamper their activation and, consequently, • A real-world application of the HJE algorithm on the undermine the correctness of the reasoning task. For Strong Link problem. We discuss the financial task and instance, in Example 1 Manager(MPS,𝜈0 ) is isomorphic rewrite the corresponding setting with harmful joins to Manager(MPS,𝜈1 ), yet its suppression would prevent into its Harmless Warded equivalent. We provide an the join in 𝜌 with Manager(Unicredit,𝜈0 ) from generat- experimental evaluation of the now enabled reasoning ing BankGroup(Unicredit,MPS) and the query from being via the Vadalog system, extracting input data from the answered correctly. On the other hand, it is intuitive to open KG provided by DBpedia [12]. observe that precluding the use of harmful joins when modeling reasoning settings would affect the expressive Related Work. Harmful Join Elimination belongs to the power of the adopted KRR language. class of methodologies for Datalog rewriting. Among In this work, we investigate the role of harmful joins them, we mention its conversion into specific fragments, in Warded Datalog± settings and we enable reasoning such as Guarded [13], Linear [14], and Disjunctive [15]. termination in their presence by applying the Harmful Similarly, by interpreting the rules as queries, several ± Join Elimination (HJE) algorithm [10], a technique to methods have been devised to rewrite Datalog pro- rewrite a set of Warded rules with harmful joins into an grams with existential rules [16, 17] and from distinct equivalent Harmless Warded form. formalisms, such as Regular Path Queries [18] and De- A Financial Use Case. As a powerful Warded Datalog - scription Logics [19, 20]. ± ± The importance of achieving de- based reasoner, the Vadalog system is employed to ef- cidability of Datalog reasoning settings, in the presence ficiently solve relevant tasks in real-world scenarios, of recursion and existential quantification, determined mainly related to the financial and business realm [11]. the research and the development of novel approaches to sustain termination of reasoning tasks [21, 5, 7]. Yet, the HJE algorithm is, to the best of our knowledge, the generated from the application of the rules in Σ over first technique to rewrite Warded Datalog± rules into 𝐷 [6]. We denote chase graph 𝒢(𝐷, Σ) as the directed an equivalent Harmless Warded version, that allows to graph with the facts from chase(𝐷, Σ) as nodes and an achieve reasoning termination and decidability. edge from a node 𝑛 to a node 𝑚 if 𝑚 is obtained from Overview. This paper is organized as follows. In Sec- 𝑛 (and possibly other facts) via a chase step, i.e., a rule tion 2, we recall relevant background notions. In Sec- in Σ [5]. Given a pair 𝑄 = (Σ, Ans), where Ans is an tion 3, we discuss the disarmament problem and we illus- n-ary predicate, we define the evaluation of 𝑄 over 𝐷 as trate the HJE algorithm in action. In Section 4, we provide the set of tuples 𝑄(𝐷, Σ) = {𝑡¯ ∈ dom(𝐷)𝑛 | Ans(𝑡¯) ∈ the application of HJE on the Strong Link problem and chase(𝐷, Σ)}, where ¯𝑡 is a tuple of constants. We denote we present the experimental evaluation. We draw our reasoning task as the task of finding a database instance conclusions in Section 5. 𝐽 such that: (i) ¯𝑡 ∈ 𝐽 iff Ans(𝑡¯) ∈ 𝑄(𝐷, Σ) and (ii) for every other instance 𝐽 ′ such that ¯𝑡 ∈ 𝐽 ′ iff ¯𝑡 ∈ 𝑄(𝐷, Σ), there is a homomorphism from 𝐽 to 𝐽 ′ [3]. 2. Reasoning with Vadalog In this section, we briefly recall some relevant notions to 3. Harmful Join Elimination guide our discussion. Let 𝐶, 𝑁 , and 𝑉 be disjoint count- ably infinite sets of constants, (labelled) nulls and (regular) In this section, we present our rewriting technique and variables, respectively. A (relational) schema S is a finite we apply it to Example 1. As the goal of this paper is to set of relation symbols (or predicates) with associated enable reasoning with the Vadalog system on a real-world arity. A term is a either a constant or variable. An atom scenario with harmful joins, we refer to the extended over S is an expression of the form 𝑅(𝑣¯), where 𝑅 ∈ S versions of the work [10, 22] for an in-depth discussion is of arity 𝑛 > 0 and 𝑣¯ is an 𝑛-tuple of terms. A database of the algorithm and the theory behind. (instance) over S associates to each relation symbol in Without loss of generality (as more complex joins can S a relation of the respective arity over the domain of be broken into multiple steps [3]), we define a harmful constants and nulls. The members of the relations are join rule as a rule of the form: called tuples or facts [9]. 𝐴(𝑥1 , 𝑦1 , ℎ), 𝐵(𝑥2 , 𝑦2 , ℎ) → ∃𝑧 𝐶(𝑥, 𝑧) (𝜌) Existentials and Affectedness. The Vadalog system employs vadalog, a KRR language that implements where 𝐴, 𝐵 and 𝐶 are atoms, 𝐴[3] and 𝐵[3] are affected Warded Datalog± as its logical core. A Warded Datalog± positions, 𝑥1 , 𝑥2 ⊆ 𝑥, 𝑦1 , 𝑦2 ⊆ 𝑦 are disjoint tuples of program consists of a set of facts and rules. An existential harmless variables or constants, ℎ is a harmful variable. rule is a first-order sentence ∀𝑥 ¯ ∀𝑦¯(𝜙(𝑥 ¯ , 𝑦¯)→∃𝑧¯ 𝜓(𝑥¯ , 𝑧¯)), Harmless Warded Datalog± . As we have introduced, where 𝜙 (the body) and 𝜓 (the head) are conjunctions in order to exploit the reasoning boundedness property, of atoms, over the respective predicates, with constants Warded programs with recursion and existentials must and variables. For brevity, we may omit quantifiers and not contain harmful joins, that is, they belong to the denote conjunction by comma. Let Σ be a set of rules Harmless Warded fragment. A set of rules ∈ Harmless and 𝑝[𝑖] a position (i.e., the 𝑖-th term of a predicate 𝑝 with Warded Datalog± if the following conditions hold: (1) it is arity 𝑘, where 𝑖 = 1, . . . , 𝑘). We define 𝑝[𝑖] as affected if Warded, i.e., all the dangerous variables in its rules appear (i) 𝑝 appears in a rule in Σ with the 𝑖-th term that con- in a single body atom (the ward), which only shares harm- tains an existentially quantified variable or, (ii) there is less variables with the rest of the body; and (2) it does not a rule 𝜌 of Σ such that a universally quantified variable contain harmful join rules. Indeed, while the chase pro- is only in affected body positions and in position 𝑝[𝑖] in cedure remains potentially infinite in Harmless Warded the head of 𝜌. A variable 𝑥 is harmful, with respect to a settings due to the generation of infinite labelled nulls, rule, if 𝑥 appears only in affected positions, otherwise it the absence of joins activating on such nulls renders their is harmless. A rule that contains a harmful variable is a identity irrelevant in the evaluation [9]. harmful rule. In Example 1, 𝛼 and 𝛾 are existential rules, 𝛽 propagates the affected position Manager[2] and 𝜌 is a The Disarmament Problem. In presence of Harmless harmful join rule, i.e., a rule such that a harmful variable Warded programs, the isomorphism termination strat- is involved in a join (namely, harmful join). If the harmful egy can thus be applied without affecting the correct- variable appears in the head of the rule, it is dangerous. ness of the reasoning task: given two isomorphic facts A rule with a dangerous variable is a dangerous rule. 𝑡 and 𝑡′ , only 𝑡 is explored in the chase, whereas the Chase and Reasoning. Let 𝐷 be a database and Σ descending portions of the chase graph rooted in 𝑡′ are a set of rules. The chase procedure is a fundamental pruned. However, restricting vadalog to such fragment, algorithmic tool that enforces the satisfaction of Σ by while it preserves the computational qualities of Warded expanding 𝐷 into a new instance chase(𝐷, Σ) with facts Datalog± , limits the expressiveness of the KRR language to joins between harmless variables. To avoid such re- 𝐴′ be unifiable with 𝐴 by substitution 𝜃. The result of strictions, we define the disarmament problem for a set unfolding 𝜌 at 𝐴 with 𝜎 is the rule 𝜏 : (𝐵, 𝑅→𝐶)𝜃. If Σ of Warded Datalog± rules as the task of finding a set the head of 𝜎 contains an existentially quantified variable Σ′ of Harmless Warded rules that is equivalent to Σ. In ℎ, it replaces ℎ with a Skolem atom 𝑓ℎ𝜎 in 𝜏 , where 𝑓 is this context, two sets of rules are equivalent if they have an injective, deterministic and range disjoint function that the same meaning with respect to the chase [14], i.e., calculates the values for existentially quantified variables, chase(𝐷, Σ) = chase(𝐷, Σ′ ) modulo fact isomorphism to control the identity of labelled nulls. for each database 𝐷. It can be proved that the disarma- ment problem is always solvable, that is, for each Warded Moreover, to cover the activation of the harmful join in 𝜌 set Σ there is an equivalent Harmless Warded set Σ′ [22]. on nulls that are propagated from causes involved in a Disarming Warded Datalog± . Let Σ be a Warded set recursion, the following folding operation [14] is applied. with one or more harmful join rules. With the goal of Definition 3 (Folding). Let 𝜌 be a rule 𝐴, 𝐵→𝐶, where enabling the isomorphism termination strategy, while 𝐶 is an atom and 𝐴 and 𝐵 are (conjunctions of) atoms, preserving vadalog’s expressive power, we propose a and let 𝜎 be a rule 𝐴′ →𝑅, where 𝑅 is an atom and 𝐴′ technique to rewrite Σ into an equivalent Harmless form, is an atom or a conjunction of atoms. Let 𝐴′ be unifiable i.e., to solve the disarmament problem. with 𝐴 by substitution 𝜃. The result of folding 𝜌 into 𝜎 is We first provide some theoretical bases. By definition the rule 𝜏 : (𝐵, 𝑅→𝐶)𝜃. of harmful variables, we observe that Σ always contains one or more rules that propagate the affectedness of such To keep track of the composition for each harmful join variables (i.e., the nulls in the chase), from the existen- rule, we employ the harmful unfolding tree (hu-tree). tials to the harmful join. We define them as follows. Apart ⟨︀ ⟩︀from the more technical side [10], the hu-tree 𝑇 for Σ, 𝜌 can be defined as a rule-labelled tree-like structure Definition 1 (Causes of Affectedness). Let 𝜌 ∈ Σ be a where: (i) the root is labelled by 𝜌; (ii) for each 𝑋𝑖𝑗 , there harmful join rule and let 𝐻 ∈ {A,B} be an atom in the body exists a root-to-leaf path 𝑇𝑖𝑗 whose nodes are labelled by of 𝜌. We define causes of affectedness as the sequences of the result of unfolding their parent nodes with the causes rules Γ𝐻𝑖 = [𝜎𝑠 , . . . , 𝜎1 ] (𝑠 < |Σ|, 𝑖 ≥ 1) ∈ Σ, where: in 𝑋𝑖𝑗 (in order of appearance); (iii) for each 𝜎𝑘 ∈ 𝑋𝑖𝑗 (i) 𝜎1 : 𝐻1 (𝑥, 𝑦), 𝑅1 →∃ℎ 𝐻2 (𝑥, 𝑦, ℎ) is a direct cause, i.e., involved in a recursion, there exists a node labelled by the an existential rule that causes a position to be affected; and result of folding its parent node into 𝜎𝑘 . By definition of (ii) 𝜎𝑘 : 𝐻𝑘 (𝑥, 𝑦, ℎ), 𝑅𝑘 →𝐻𝑘+1 (𝑥, 𝑦, ℎ), 1 < 𝑘 ≤ 𝑠, are unfolding and folding, it can be proved that the leaves indirect causes, i.e., rules that propagate the affectedness of 𝑇 are harmless rules that cover the generation of all from 𝜎1 to 𝜌, such that 𝐻𝑠+1 = 𝐻. 𝐻1 , . . . , 𝐻𝑠 are atoms, the facts derived in the chase from the activation of 𝜌 on 𝑅1 , . . . , 𝑅𝑠 are (conjunctions of) atoms not containing ℎ labelled nulls [22]. With reference to Example 1, Figure 1 (as the rules are Warded). shows the path 𝑇21 , built by unfolding 𝜌 with the causes With reference to Example 1, the rules 𝛼 and 𝛾 are direct in 𝑋21 (atoms are renamed for space reasons). causes of affectedness, whereas 𝛽 is an indirect one. The Man(x,d),Man(y,d)→BGroup(x,y) sequences of causes for the atom 𝑀 𝑎𝑛𝑎𝑔𝑒𝑟 𝑀 𝑎𝑛1 (resp., βГMan 2 𝑀 𝑎𝑛2 in order of appearance in 𝜌) are: Γ𝑀 𝑎𝑛1 1 = [𝛼], 1 Γ𝑀 𝑎𝑛1 2 = [𝛽, 𝛼], Γ𝑀 𝑎𝑛1 3 = [𝛾], Γ𝑀 𝑎𝑛1 4 = [𝛽, 𝛾]. Let Acq(v1,v2),Man(v1,d), 𝑋𝑖𝑗 = Γ𝐴𝑖 ⌢ Γ𝐵𝑗 be the concatenation of the sequences Man(y,d)→BGroup(v2,y) Γ𝐴𝑖 and Γ𝐵𝑗 for the atoms 𝐴, 𝐵 in 𝜌: the causes in 𝑋𝑖𝑗 αГMan 2 1 are labelled after the sequence they belong to. In our Acq(v1,v2),Bank(v1),Man(y,d), example 𝑋21 = [𝛽Γ𝑀 𝑎𝑛1 2 , 𝛼Γ𝑀 𝑎𝑛1 2 , 𝛼Γ𝑀 𝑎𝑛2 1 ]. Intu- fdα(v1)→BGroup(v2,y) itively, our goal is to replace each 𝜌 with harmless rules αГMan 1 2 that cover the generation of all the facts derived in the Acq(v1,v2),Bank(v1),Bank(v3), chase from the activation of 𝜌. To learn how the propa- fdα(v1),fdα(v3)→BGroup(v2,v3) gated nulls that activate the harmful join affect the mean- ing, and to consequently build proper harmless rules, we Figure 1: Path 𝑇21 of hu-tree 𝑇 for ⟨︀Σ, 𝜌⟩︀ of Example 1. compose 𝜌 along all 𝑋𝑖𝑗 . Such composition is performed via the unfolding operation [14], defined as follows. Harmful Join Elimination. By exploiting these theo- Definition 2 (Unfolding). Let 𝜌 be a rule 𝐴, 𝐵→𝐶, retical bases, we now present our rewriting algorithm, where 𝐴 and 𝐶 are atoms and 𝐵 is an atom or a con- which we named Harmful Join Elimination. Given a junction of atoms, and let 𝜎 be a rule 𝑅→𝐴′ , where 𝐴′ Warded set Σ with one or more harmful join rules 𝜌, is an atom and 𝑅 an atom or a conjunction of atoms. Let HJE(Σ) = Σ′ ∈ Harmless Warded Datalog± such that chase(𝐷, Σ) = chase(𝐷, Σ′ ) modulo fact isomorphism Dom(d), Man(x, d) → Man′ (x, d) (𝛿1 ) for each 𝐷. HJE can be divided into two main phases, ′ Man (x, d) → Man(x, d) (𝛿2 ) which we describe by applying them to Example 1. ′ ′ In the back-composition phase, first HJE identifies the Man (x, d), Man (y, d) → BGroup(x, y) (𝛿3 ) sets 𝑋𝑖𝑗 of causes of affectedness for 𝜌. Then, it builds the Additionally, to preserve the propagation of ground facts hu-tree 𝑇 by composing back, via unfolding and folding, from rules 𝜋 ∈ Σ that are not causes of affectedness, if along each 𝑋𝑖𝑗 . With reference to Example 1, Figure 2 the head of 𝜋 unifies with: (i) the atom 𝐻 in 𝜌, a rule shows some of the sequences of unfolded causes (here 𝜋 ′ is added, which results from renaming 𝐻 with 𝐻 ′ ; not labelled) and the resulting leaves. (ii) the atom 𝐻𝑘 in the cause 𝜎𝑘 , a rule 𝜋 ′ is added, which results from unfolding 𝜎𝑘 with 𝜋. Finally, 𝜌 is removed Man(x,d),Man(y,d)→BGroup(x,y) from Σ′ and the procedure terminates. α β γ The resulting Σ′ is a set of Harmless Warded α β α γ β γ rules. Its equivalence to the original set Σ can be τ1 α τ easily derived as a generalization of proofs in the α β β γ γ 8 Datalog context [23]. The output facts of the rea- τ2 τ3 τ6 τ7 soning task on Example 1, via isomorphism termi- α γ nation strategy, are: BankGroup(Unicredit,Unicredit), τ4 τ5 BankGroup(MPS,MPS), BankGroup(Unicredit,MPS) and ⟨︀ ⟩︀ BankGroup(MPS,Unicredit). HJE shows an exponential Figure 2: Unfolded causes in 𝑇 for Σ, 𝜌 of Example 1. behaviour with respect to the number of causes, due to the worst-case generation of a distinct path in the hu-tree The rules labelling the resulting leaves are subject to an for each 𝑋𝑖𝑗 . Yet, such blowup is data independent and overall cleanup and deduplication. Rules that never acti- it does not affect reasoning performance [22]. vate are dropped. If the functions of the Skolem atoms in a rule (derived from unfolding a direct cause in 𝑇 ) respect injectivity and range disjointness, they are unified and 4. Financial Use Case removed, otherwise the rule is dropped. With reference In this section, we provide a real-world application of the to our running example, the following rules are added HJE algorithm. We employ it to enable reasoning with to Σ′ . Specifically, 𝜏 s derive from unfolding, whereas the Vadalog system on the Strong Link problem, which 𝜐s derive from folding: 𝜏3 labels the leaf of 𝑇21 from we then solve and empirically evaluate. Figure 1, after skolem unification during cleanup. The Strong Link Problem. Being able to determine and monitor the connections between companies and Bank(x) → BGroup(x, x) (𝜏1 ) shareholders, as well as to investigate possible felonious activities in company ownership scenarios, is of high- Bank(x), Acq(x, y) → BGroup(x, y) (𝜏2 ) interest in the financial and corporate realm. With such Bank(x), Acq(x, y) → BGroup(y, x) (𝜏3 ) goal in mind, we consider the Strong Link problem over Bank(x), Acq(x, y), Acq(x, z) → BGroup(y, z) (𝜏4 ) “significantly controlled companies”, that is, companies BGroup(x, y), Acq(x, w), Acq(x, z) → BGroup(w, z) (𝜏5 ) for which there exist “significant shareholders” who own BGroup(x, y), Acq(x, z) → BGroup(x, z) (𝜏6 ) more than 20% of their stocks [9]. Two distinct compa- BGroup(x, y), Acq(x, z) → BGroup(z, x) (𝜏7 ) nies 𝑥 and 𝑦 are involved in a strong link if they share (at least) one significant shareholder. The Strong Link BGroup(x, y) → BGroup(x, x) (𝜏8 ) scenario can be modeled in Warded Datalog± as follows. BGroup(x, y), Acq(x, z) → BGroup(y, z) (𝜐1 ) BGroup(x, y), Acq(x, z) → BGroup(z, y) (𝜐2 ) Example 2. Strong Link modeled with Warded rules. BGroup(x, y), Acq(y, z) → BGroup(x, z) (𝜐3 ) Company(x) → ∃p∃s Owns(p, s, x) (1) BGroup(x, y), Acq(y, z) → BGroup(z, x) (𝜐4 ) Owns(p, s, x) → Stock(x, s) (2) In the grounding phase, HJE adds new harmless rules Owns(p, s, x) → PSC(x, p) (3) to cover the activation of 𝜌 on ground values, propagated PSC(x, p), Controls(x, y) → ∃s Owns(p, s, y) (4) from the database. It employs the Dom(ℎ) [9] atom, to PSC(x, p), PSC(y, p), x ̸= y → StrongLink(x, y) (5) ensure that the harmful join variables bind only to con- stants in the domain, and an artificial atom 𝐻 ′ , where 𝐻 StrongLink(x, y) → ∃p∃s Owns(p, s, x) (6) ∈ {𝐴, 𝐵} of 𝜌. With reference to Example 1, the following StrongLink(x, y) → ∃p∃s Owns(p, s, y) (7) rules (namely, dom rules) are added to Σ′ . Stock(x, s) → Company(x) (8) (a) Reasoning times of Spec and All scenarios. (b) Strong Links discovered in All scenario. Figure 3: Results of the experiments performed for Spec and All scenarios, to vary the number of companies. 1K 5K 10K 15K 20K 25K 30K Spec Times 7993 9187 10156 10795 11473 12313 13186 All Times 3158 5519 8751 9334 10437 13501 15749 Spec Links 3 3 7 8 9 9 10 All Links 716 2917 5935 8434 11050 13857 16390 Figure 4: Times in msecs and # strong links collected in Spec and All scenarios, to vary the number of companies. For each company 𝑥 there exists a person 𝑝 who owns a certain share 𝑠 (rule 1), which is part of the company Dom(p), PSC(x, p) → PSC′ (x, p) (𝛿1 ) stock (rule 2). If 𝑝 owns a share 𝑠 (rule 3), 𝑝 is a “person PSC′ (x, p) → PSC(x, p) (𝛿2 ) with significant control” (psc) for 𝑥. For each company 𝑦 ′ ′ controlled by 𝑥, 𝑝 owns a certain share 𝑠 of 𝑦 (rule 4). If PSC (x, p), PSC (y, p), x ̸= y → SLink(x, y) (𝛿3 ) two distinct companies 𝑥 and 𝑦 share a common psc, they Comp(x), Contr(x, y) → SLink(x, y), SLink(y, x) (𝜏1,2 ) are involved in a strong link (rule 5). Vice versa, if there is Comp(x), Contr(x, y), Contr(x, z) → SLink(y, z) (𝜏3 ) a strong link between 𝑥 and 𝑦, there exists a person 𝑝 who SLink(x, y), Contr(x, w), Contr(x, z) → SLink(w, z) ( 𝜏4 ) owns a share of 𝑥 (rule 6) and 𝑦 (rule 7). If 𝑠 is a share of SLink(x, y), Contr(x, w), Contr(x, z) → SLink(z, w) ( 𝜏5 ) a stock for 𝑥, then 𝑥 is a company (rule 8). SLink(x, y), Contr(x, z) → SLink(x, z), SLink(z, x) (𝜏6,7 ) Indeed, reasoning on the Strong Link program does not SLink(x, y), Contr(x, z) → SLink(y, z) (𝜐1 ) terminate, as the existential quantification in rule 4, rule 6 SLink(x, y), Contr(x, z) → SLink(z, y) (𝜐2 ) and rule 7, and their recursion with rule 3 and rule 5, Experiments and Results. We extracted input data for cause the generation of an infinite set of 𝑃 𝑆𝐶 facts in the companies and ownership relations from the open KG chase. Moreover, the isomorphism termination strategy provided by DBpedia [12], which publishes information cannot be applied, due to the presence of the harmful join for around 67K companies. We adopted datasets of in- rule 5 that hampers the reasoning boundedness of the pro- creasing complexity, with 1K, 5K, 10K, 15K, 20K, 25K and gram. Therefore, we apply HJE to enable reasoning with 30K companies, respectively. The Vadalog system, with the Vadalog system. Note that rule 1, rule 6 and rule 7 HJE integrated as part of its logic optimizer [3], was used are direct causes of affectedness for the 𝑃 𝑆𝐶 atoms in as a “library” and invoked from specific Java test classes rule 5, whereas rule 3 and rule 4 are indirect ones. Due for end-to-end executions of the reasoning. We run the to the recursion on such causes, the back-composition experiments on a local installation of the Vadalog system, phase builds a hu-tree which consists of both unfolding with a MacBook Pro i7 with 2.5 GHz and 8 GB of RAM. and folding leaves. The harmless rules that replace rule 5 We first applied HJE to the program, with average time of in Example 2 are provided below (atoms are renamed under 1 second. Then, we built two reasoning scenarios: and some rules are merged for space reasons). As in Ex- ample 1, 𝛿s are added via grounding, whereas 𝜏 s and 𝜐s • SpecStrongLinks (Spec), to obtain all the strong links of label hu-tree leaves deriving from unfolding and folding, the company BBC, to vary the number of companies; respectively. Note that some rules were dropped during • AllStrongLinks (All), to obtain all the possible pairs of cleanup, as they would have never activated. strong links, to vary the number of companies. The tasks were analyzed both in terms of time required applications, in: 2010 25th Annual IEEE LICS, IEEE, for the reasoning to terminate and of number of strong 2010, pp. 228–242. links detected. Figure 3(a) illustrates the former perspec- [8] A. Calì, G. Gottlob, M. Kifer, Taming the infinite tive. The results prove the very good performance of chase: Query answering under expressive relational the Vadalog system, even if tested on a local installation. constraints, Journal of Artificial Intelligence Re- Indeed, the Spec scenario requires more time than the All search 48 (2013) 115–174. one for smaller datasets; when the number of companies [9] L. Bellomarini, E. Sallinger, G. Gottlob, The Vadalog increases, All tends to a steeper curve. On the other hand, System: Datalog-based reasoning for knowledge Figure 3(b) shows the strong links founds between pairs graphs, VLDB 11 (2018). of distinct companies in the All scenario. Finally, Figure 4 [10] T. Baldazzi, L. Bellomarini, E. Sallinger, P. Atzeni, provides all the numerical results of the experiments. Eliminating harmful joins in warded datalog+/-, in: International Joint Conference on Rules and Reasoning, Springer, 2021, pp. 267–275. 5. Conclusion [11] P. Atzeni, L. Bellomarini, M. Iezzi, E. Sallinger, A. Vlad, Weaving enterprise knowledge graphs: Employing powerful reasoning engines such as Warded ± The case of company ownership graphs., in: EDBT, Datalog -based Vadalog system allows companies to 2020, pp. 555–566. solve relevant tasks in the financial and corporate realm. [12] DBpedia, 2018. URL: http://wiki.dbpedia.org/ Among them, the Strong Link problem proved to be prob- services-resources/downloads/dbpedia-tables. lematic to tackle, due to the presence of harmful joins and [13] G. Gottlob, S. Rudolph, M. Simkus, Expressiveness recursion that hampered termination and decidability of of guarded existential rule languages, in: PODS, the reasoning in vadalog. In this work, we discussed 2014, pp. 27–38. the disarmament problem of rewriting Warded settings [14] F. Afrati, M. Gergatsoulis, F. Toni, Linearisability on with such problematic joins into an equivalent Harmless datalog programs, Theoretical Computer Science Warded form, while upholding the correctness of the task. 308 (2003) 199–226. We contributed the Harmful Join Elimination, a disarma- [15] M. Kaminski, Y. Nenov, B. C. Grau, Datalog ment algorithm integrated into the Vadalog system, and rewritability of disjunctive datalog programs and we applied it to enable reasoning on Strong Link. non-Horn ontologies, Artificial Intelligence 236 (2016) 90–118. References [16] M. Kónig, M. Leclere, M.-L. Mugnier, Query rewrit- ing for existential rules with compiled preorder, in: [1] M. Krötzsch, V. Thost, Ontologies for knowledge IJCAI, 2015, pp. 3006–3112. graphs: Breaking the rules, in: International Se- [17] Z. Wang, P. Xiao, K. Wang, Z. Zhuang, H. Wan, mantic Web Conference (1), volume 9981 of Lecture Query answering for existential rules via efficient Notes in Computer Science, 2016, pp. 376–392. datalog rewriting., in: IJCAI, 2020, pp. 1933–1939. [2] G. Gottlob, A. Pieris, Beyond SPARQL under OWL [18] N. Francis, L. Segoufin, C. Sirangelo, Datalog rewrit- 2 QL entailment regime: Rules to the rescue, in: ings of regular path queries using views, arXiv IJCAI, 2015. preprint arXiv:1511.00938 (2015). [3] L. Bellomarini, D. Benedetto, G. Gottlob, E. Sallinger, [19] G. Stefanoni, B. Motik, I. Horrocks, Small datalog Vadalog: A modern architecture for automated rea- query rewritings for el*, in: Proc. 25th Int’l Work- soning with large knowledge graphs, Information shop on Description Logics, Citeseer, 2012. Systems (2020) 101528. [20] S. Ahmetaj, M. Ortiz, M. Simkus, Polynomial data- [4] L. Bellomarini, G. Gottlob, A. Pieris, E. Sallinger, log rewritings for expressive description logics with Swift logic for big data and knowledge graphs, in: closed predicates., in: IJCAI, 2016, pp. 878–885. IJCAI, Springer, 2017, pp. 2–10. [21] G. Berger, G. Gottlob, A. Pieris, E. Sallinger, The [5] A. Calì, G. Gottlob, T. Lukasiewicz, A general space-efficient core of Vadalog, in: PODS, 2019, pp. datalog-based framework for tractable query an- 270–284. swering over ontologies, in: PODS, 2009, pp. 77–86. [22] T. Baldazzi, L. Bellomarini, E. Sallinger, P. Atzeni, [6] D. Maier, A. O. Mendelzon, Y. Sagiv, Testing impli- iwarded: A system for benchmarking datalog+/- cations of data dependencies, ACM Transactions reasoning (technical report), arXiv preprint on Database Systems 4 (1979) 455–468. arXiv:2103.08588 (2021). [7] A. Calì, G. Gottlob, T. Lukasiewicz, B. Marnette, [23] H. Tamaki, T. Sato, Unfold/fold transformation of A. Pieris, Datalog+/-: A family of logical knowl- logic programs, in: ICLP, Uppsala University, 1984, edge representation and query languages for new pp. 127–138.