=Paper=
{{Paper
|id=Vol-3135/EcoFinKG_2022_paper13
|storemode=property
|title=Warded Datalog+/- Reasoning in Financial Settings with Harmful Joins
|pdfUrl=https://ceur-ws.org/Vol-3135/EcoFinKG_2022_paper13.pdf
|volume=Vol-3135
|authors=Teodoro Baldazzi,Paolo Atzeni
|dblpUrl=https://dblp.org/rec/conf/edbt/BaldazziA22
}}
==Warded Datalog+/- Reasoning in Financial Settings with Harmful Joins==
https://ceur-ws.org/Vol-3135/EcoFinKG_2022_paper13.pdf
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.