Datalog+/- has recently emerged as a family of powerful languages for ontological reasoning on knowledge graphs (KGs). Yet, performing reasoning tasks on real-world scenarios that feature large inputs and recursions, e.g., answering Boolean Conjunctive Queries (BCQs), can be very onerous even for modern Datalog-based systems. To tackle this problem, we introduce a novel reasoning technique that adopts heuristic search strategies to guide the evaluation of Datalog+/- programs and optimize BCQ answering. We apply our methodology to eficiently solve time- and space-demanding tasks on financial KGs.
Recent years have witnessed a rising interest, both in academia and industry, towards querying
and exploiting large amounts of data in the form of knowledge graphs (KGs). This led to the
development of intelligent systems that manage such data as the extensional component of
KGs and infer new intensional knowledge via ontological reasoning mechanisms. To achieve
this, modern applications require powerful logic languages for knowledge representation [
Nonetheless, graph traversal remains a very time- and space-demanding task, especially in
the presence of large inputs, as it potentially involves a blowup of the generated facts [
In this work, we investigate the generation of superfluous facts in recursive settings when
answering BCQs. We contribute a novel reasoning approach that tackles this problem and
provides an optimized way to evaluate Datalog± rules. Let us consider the following example.
Example 1. A trafic volume scenario on a geographic knowledge graph [
Road(p1, p2, tv), p1 = A → Route(p1, p2, tv) Route(p1, p2, tv1), Road(p2, p3, tv2), p1 ̸= p3 → Route(p1, p3, tv1 + tv2)
Route(p1, p2, tv), ttv = (tv), ttv ≥ thold → HighTrafic (p1, p2) A road from city A to a city 2 identifies a route featuring a trafic volume (rule 1). If there is a route from 1 to 2 and a road from 2 to another city 3, then there is a route from 1 to 3. The resulting trafic volume is the sum of the one from 1 to 2 and from 2 to 3 (rule 2). The overall set of itineraries from 1 to 2 is highly traficated (HighTrafic) if the total trafic volume of all possible routes from 1 to 2 is greater than or equal to a threshold thold (rule 3).
sums all the trafic volumes of the routes from 1 to 2. Note that distinct routes may have one or more roads in common. Consider, as ontological reasoning task, the BCQ = HighTrafic (A, B) ∧ HighTrafic (A, L) to check whether the set of routes from A to B and the one from A to L are highly traficated, i.e., their trafic volume is greater than or equal to thold = 18. The graph in Figure 1, represents the roads (black edges, labelled with their daily average trafic volume in the order of thousands) that connect pairs of cities (nodes). Consider an input database containing an extensional fact of the form Road(x,y,tv) for each road in the graph. It can be observed that the answer to is indeed positive. However, there are (1) (2) (3)
B E 1 3 HighTraffic C
3 6 5
HighTraffic A D H 7 18 3
3 6 2 F 3 4 L
G
I
multiple ways to activate the above rules on to achieve such answer, causing the generation of
a distinct number of facts and, consequently, an impact on the performance of the computation.
For instance, by activating rule 2 from Route(A,E,3) and Road(E,G,1), we generate Route(A,G,4).
Similarly, Route(A,F,8) derives from Route(A,D,6) and Road(D,F,2). Then, by triggering again
rule 2 on such newly generated facts, we create Route(A,I,7) from Road(G,I,3), Route(A,H,8)
from Road(G,H,4), and Route(A,H,11) from Road(F,H,3). Finally, the aggregated trafic volume of
Route(A,L,15) and Route(A,L,18) exceeds 18, thus HighTrafic (A,L) is produced via rule 3. Indeed,
such approach generates both facts that are not used to answer (e.g. Route(A,I,7), and facts
that provide an unnecessary contribution to pass the threshold (e.g. Route(A,L,15)).
Informed Search and Reasoning. With this work, we propose a novel reasoning methodology
to eficiently solve BCQ answering tasks in the presence of large inputs and recursive Datalog ±
settings, limiting the generation of superfluous facts in the chase. To achieve this, we consider
the task as an informed search problem and we optimize the reasoning process by injecting
into the program specific heuristics that prioritize the selection of facts for rule evaluation.
We focus on Warded Datalog± [
More in detail, our contributions can be summarized as follows.
• We present heuristic-based reasoning, a novel approach to optimize the evaluation of
BCQ answering tasks. We formalize ontological reasoning to answer BCQs as a search
problem and we exploit informed search techniques to evaluate Warded Datalog± TGDs in
an eficient fashion, guiding rule activation according to fitting heuristics.
• We discuss real-world KG applications of our methodology to solve two computationally
hard scenarios in the financial domain, namely Close Link and Company Control, by employing
empirically-defined heuristics [
Specifically, we compare our ad-hoc implementation, based on Best-First and A* search algorithms, with state-of-the-art BCQ answering techniques for Close Link and Company Control. We show that our approach exhibits superior performance in BCQ evaluation. Overview. The remainder of this paper is organized as follows. In Section 2 we provide the preliminary notions. In Section 3 we present our novel heuristic-based reasoning methodology. Section 4 is dedicated to the experimental evaluation. In Section 5 we discuss the related work and we draw our conclusions in Section 6.
Relational Foundations. Let C, N, and V be disjoint countably infinite sets of constants, (labelled) nulls and variables, respectively. A (relational) schema S is a finite set of relation symbols (or predicates) with associated arity. A term is either a constant or a variable. An atom over S is an expression of the form (¯) , where ∈ S is of arity > 0 and ¯ is an -tuple of terms. A database (instance) over S associates to each symbol in S a relation of the respective arity over the domain of constants and nulls. The members of the relations are called tuples or facts. Given two conjunctions of atoms ς1 and ς2, we define a homomorphism from ς1 to ς2 as a mapping ℎ : C ∪ N ∪ V → C ∪ N ∪ V s.t. ℎ() = if ∈ C, ℎ() ∈ C ∪ N if ∈ N and for each atom (1, . . . , ) ∈ ς1, then ℎ((1, . . . , )) = (ℎ(1), . . . , ℎ()) ∈ ς2. Two facts are isomorphic if they refer to the same predicate, feature the same constants in the same positions, and there is a bijection between labelled nulls.
Rules and Existentials. Warded Datalog± extends Datalog by introducing existential
quantifiers and other features to make it suitable for ontological reasoning, while employing
specific syntactic restrictions for tractability [
Ontological Reasoning and Query Answering. Intuitively speaking, an ontological
reasoning task consists in answering a conjunctive query (CQ) over a database , augmented
with a set of logical rules Σ . More formally, given a database over S and a set of TGDs Σ ,
we name the models of and Σ as the set B of all databases (and we write B |= ∪ Σ ) such
that B ⊇ , and B |= Σ . The answer to a Boolean CQ (BCQ) ← (¯, ¯) over under Σ is
positive if there exists a homomorphism h: ∪ → ∪ s.t. h( (¯, ¯) ) ⊆ .
Chase Procedure. The semantics of a Datalog± program can be operationally defined via
chase-based procedures [
In this section, we first introduce a novel formalization of BCQ answering as an informed search problem, then we delve into how informed search methodologies can be efectively adopted to optimize BCQ evaluation over Warded Datalog± .
BCQ Answering as Search Problem. Consider an instance of the BCQ answering problem , i.e., answering a BCQ over a database under a set of warded TGDs Σ . We formalize it as an informed search problem as follows. A chase state of , denoted as =chase(,Σ ), is a set of facts comprising the extensional ones in the initial database and the intensional ones generated after the application of a sequence of > 0 chase steps. Observe that chase(,Σ ) is not a unique set, as it depends on the order of applicable homomorphisms triggered in the chase procedure. The chase state space for is the power set (chase(, Σ)) , i.e., all the sets of facts generated after the application of all the possible sequences of chase steps. Consider a state =chase(,Σ ). The set of applicable homomorphisms from Σ to chase(,Σ ) is the set of actions that can be performed at . The application of a homomorphism ℎ ∈ over =chase(,Σ ) to generate +1=chase+1(,Σ ) represents a transition from to +1. The initial chase state 0 is the state where no chase step has been applied yet, i.e., the input database =chase0(,Σ ). If the BCQ has a positive answer, then the goal states of are the set of states where has a positive answer, i.e., chase(,Σ ) |= . If has a negative answer instead, then the goal state of is the state where no further homomorphism is applicable, i.e., chase(,Σ ). A solution = 0, . . . , for represents a sequence of chase step applications from the initial database to =chase(,Σ ) such that chase(,Σ )) |= . The evaluation function : (chase(, Σ)) → R≥ 0 assigns to each state a weight according to a given heuristic. The highest weight represents an estimation of the lowest cost path from to a goal state . In the presence of an ideal , the optimal solution for (i.e., the sequence of chase step applications with the lowest cost path) guarantees that no superfluous facts are generated in the chase procedure when answering . Intuitively, given a state =chase(,Σ ), the evaluation function represents the strategy to select the most suitable applicable homomorphism in . Heuristic-based Reasoning. The most efective approach to define the evaluation function is to enrich the program with external knowledge of the reasoning setting, provided by a domain expert. We represent such external knowledge as a semantic constraint on , expressed via a heuristic function defined as follows.
Definition 1 ( Ground Heuristic Function). Consider a database over a relational schema . A Ground Heuristic Function (GHF) : → R≥ 0 is a user-defined function that maps each tuple of to a weight ∈ R≥ 0.
We exploit such a priori knowledge of the ground facts in the chase procedure to produce a more general heuristic function that also considers the inferred facts and how they are derived. Intuitively, the priority assigned to ground facts can be combined and propagated to the facts that directly descend from them.
Definition 2 ( Chase Heuristic Function). Consider a database over a relational schema , a set Σ of warded TGDs and a GHF . A Chase Heuristic Function (CHF) : chase(, Σ) → R≥ 0 is a function that maps each fact of chase(, Σ) to a weight ∈ R≥ 0 such that ⊆ . An Extended tuples ⊆
chase(, Σ) weights assigned by to each ∈ .
Chase Heuristic Function (ECHF) Γ : (chase(, Σ)) to a weight ′ such that ′ = →∑︀R≥ 0 is a function that maps a set of ∀∈ (), where ′ is the sum of the Based on such definitions, we now introduce the heuristic chase step, which represents the evaluation function of the BCQ answering problem. In fact, it allows us to select and apply, at each step in the chase, the best applicable homomorphism according to the heuristic provided by the domain expert. the homomorphism ∈ whose images (i.e., tuples) maximise Γ .
Definition 3 ( Heuristic Chase Step Application). Consider a set Σ of warded TGDs, an intermediate instance chase(,Σ ) and an ECHF Γ . Let be the set of applicable homomorphisms from Σ
to chase(,Σ ). A Heuristic chase step consists in the application of ℎ = [Γ( ℎ( (¯, ¯)))] ∀ℎ∈ over chase(,Σ ), where (¯, ¯) is a warded TGD ∈ Σ and ℎ is Based on such a revised form of the chase step application, we devise a new reasoning methodology, which we name heuristic-based reasoning. In Section 4 we show how such methodology efectively enables the generation of less unavailing facts in the chase when answering BCQs and consequently optimizes the program evaluation. As stated by Definition 2, the heuristic chase step requires a defined for the facts generated in the chase. The process for defining can be performed dynamically during the chase as follows: (1) initialize = by employing the knowledge provided by the domain expert before starting the chase; (2) after applying a chase step, update with a weight for the generated fact . The strategies to define such a weight depend on the informed search employed. Indeed, () has to properly consider the evaluation components of the informed search method (e.g., the heuristic ℎ and the function for A* ). • Best-First: in this case, () is the sum of the priorities assigned to parents() (i.e., the facts where directly derived from), since best-first only considers the heuristic function ℎ to select the next node ( () = ℎ()). This way () inherits and combines the heuristic estimation Γ (parents()). • A* : in this case, () is the combination of the heuristic estimation ℎ from the current state to a goal state and the cost required to reach the current state from the initial state, i.e., the ground facts where originally derived from. Essentially, such distance is incorporated in the derivation level of (denoted as depth()) which can be inductively defined as follows: (i) a fact ∈ has depth() = 0; (ii) a fact derived from a chase step application inherits the maximum derivation level of parents() + 1. Thus, A* considers () as the diference between the heuristic estimation Γ (parents()) of the last heuristic chase step application (i.e., ℎ()) and depth() (i.e., ()).
Note that, to practically ensure uniformity of the dimensions considered in the ECHF, the values associated with () are always normalized between 0 and 1.
Heuristic Chase Procedure. Algorithm 1 provides the pseudocode of the chase procedure that employs heuristics chase steps. A description of the algorithm follows.
The algorithm takes as input a database , a set Σ of Warded TGDs and a BCQ . Additionally, it requires the GHF and the selected informed search strategy. The output of the algorithm is the answer to . First of all, the CHF is initialized to (line 2), since it only considers extensional facts during the first chase step. Similarly, the chase instance ℎ that stores the Algorithm 1 Heuristic Chase Algorithm. facts generated during the procedure is initialized to and corresponds to the initial chase state (line 3). A data structure is employed to store, at each step of the procedure, all the applicable homomorphisms. Such homomorphisms are sorted according to a weight that is assigned via , representing their priority with respect to the heuristic and the search strategy (line 4). While is not empty, the applicable homomorphism ℎ with the highest weight is extracted (line 6). The result of applying ℎ is a new fact that also contains chase metadata, such as about its parents and its derivation level (line 7). If is not isomorphic with a fact already present in ℎ, then it is added to the chase instance (lines 8-9). After such update, the algorithm checks whether the query has a positive answer, in which case it terminates (lines 10-11). Otherwise, it derives the weight for by employing its chase metadata, with respect to the search strategy, and it updates accordingly (lines 12-13). Finally, the new applicable homomorphisms, derived from and Σ , are weighted according to the new and are added to (line 14). If is empty, that is, all the homomorphisms have been applied, then the answer to is negative (line 15).
In this section, we adopt and validate our novel methodology to eficiently solve real-world KG
tasks known to be computationally demanding even for state-of-art reasoning techniques.
Financial Use Cases. We work in the context of Central Bank of Italy’s company KG [
Close Link Problem. This scenario consists in determining whether there exists a (direct
or indirect) link between two companies, based on a high overlap of shares. Formally, two
companies 1 and 2 are close links if: (i) 1 (resp. 2) owns directly or indirectly, through one
or more other companies, 20% or more of the share of 2 (resp. 1); or (ii) a third-party owns
directly or indirectly, through one or more other companies, 20% or more of the share of 1 and
2. Determining whether two companies are closely-linked is extremely important for banking
supervision since a company cannot act as a guarantor for loans to another company if they
share such a relationship [
Own(1, 2, s) → MCl(1, 2, s) MCl(1, 2, 1), Own(2, 3, 2) → MCl(1, 3, 1 · 2)
MCl(1, 2, ), ts = msum(), ts ≥ 0.2 → 1(1, 2) 1(1, 2), 1(1, 3), ¬ 1(2, 3), 2 ̸= 3 → 2(2, 3) 1(1, 2) → Cl(1, 2) 2(1, 2) → Cl(1, 2) Two companies 1 and 2, connected by an ownership edge with a share , are possible close links (rule 1). If 1 and 2 are possible close links with a share 1 and there exists an ownership edge from 2 to a company 3 with a share 2, then also 1 and 3 are possible close links with a total share of 1 · 2 (rule 2). If the sum of all the partial shares of 2 owned (directly or indirectly) by 1 is greater than or equal to 0.2, then 1 and 2 are close links (rule 3). The third-party case is modeled according to point (ii) of the definition (rule 4).
Consider, as ontological reasoning task, answering the BCQ = Cl(,) to check whether two companies and are close links.
Company Control Problem. This scenario consists in determining who takes decisions in a
company network, that is, who controls the majority of votes for each company [
Own(1, 2, s), ts = msum() → MControl(1, 2, ts) Control(1, 2), Own(2, 3, s), 1 ̸= 3, ts = msum() → MControl(1, 3, ts)
MControl(1, 2, ts), ≥ 0.5 → Control(1, 2) A company 1 might control a company 2 if 1 owns an amount of shares of 2 (rule 1). If 1 controls 2 and 2 owns an amount of shares of a company 3, then 1 might control 3 (rule 2). A company 1 controls a company 2 if the amount of shares that 1 owns of 2, directly of indirectly (i.e., through other controlled companies), is greater than or equal to 0.5 (rule 3). Consider, as ontological reasoning task, answering the BCQ = Control(,) to check whether a company controls a company .
Heuristic-based Reasoning Implementation. We implemented an ad-hoc system that performs our heuristic-based reasoning approach to solve the Close Link and the Company Control problems. From empirical evidence, we observed that prioritizing the exploration of nodes in the KG with a higher in-degree allows us to discover a greater number of ownership (1) (2) (3) paths and, consequently, possible close links and control relationships. Thus, we defined the following 3 GHFs mapping the extensional facts: (i) rand with random weights; (ii) 1 with weights directly proportional to the in-degree of the target nodes; and (iii) 2 with weights that consider both the in-degree and the share of the ownership. Based on such heuristics, the system implements: (i) a standard streaming approach (Std), which applies rules according to a round-robin strategy and does not employ a priority for the applicable homomorphisms; and (ii) a heuristic-based approach, which applies the heuristic chase step guided by Best-First or A* with the above GHFs as input (BF- 1, BF- rand, A* - 1, A* - 2, respectively). The system has as input the set of TGDs for the scenario, the company KG, the BCQ, the GHF and the informed search method to employ, and it provides as output whether pairs of companies are close links or are involved in a control relationship. Moreover, it adopts a streaming architecture with a pull-based pipeline of the facts for rule activation, according to the priority of the corresponding applicable homomorphisms. Such priority is based on a queue, ordered by the ECHF that employs the selected heuristic: each time a new fact is generated, the queue is updated with the resulting set of applicable homomorphisms.
Experiments and Results. We run the experiments on a cloud instance of our system in an AWS EC2 Ubuntu machine with 64 vCPU and 128 GB of RAM. We compared the approaches discussed above to solve Close Link and Company Control over 100 pairs of companies in the company KG, selected randomly among the ones that are known to be close links or in a control relationship. We adopted a time limit of 10 minutes for each BCQ. We collected both the execution times in seconds and nFacts/nPaths, i.e., the ratio between the number of generated facts and the number of discovered paths for each pair of companies in the BCQ. Intuitively, it provides an indication of the average number of facts to generate for discovering a new path between the candidates. Figure 2(a) and Figure 2(b) illustrate the average values of the measures over the 100 pairs in log10 scale. Many evaluations with Std did not terminate and we considered 600 seconds as their execution time. Then, we focus on the resulting times and ratios for 5 random pairs of the 100 close links (Figure 2(c) and Figure 2(d), resp.) and as many companies in a control relationship (Figure 2(e) and Figure 2(f), resp.). The experiments confirm the validity of the heuristic-based reasoning we propose, both in terms of the time required to evaluate the BCQs and the ability to prevent the generation of superfluous facts for the answers. Indeed, exploiting fitting heuristics such as 1 and 2 ensures much better results than the random-based one, which in some instances behaves worse than Std. Combining them with the A* search proved to be particularly efective, being on average over 3 times faster than Std.
Current literature includes a variety of optimization techniques that exploit external knowledge
to eficiently solve query-answering tasks. For instance, in the database realm, hint operators
are employed to statically guide the optimizer in the creation of the query execution plan, by
enforcing specific directives (e.g., join order, choice of physical operators for joins, etc.) [
Reasoning over large knowledge graphs, especially in the presence of recursive settings, can be very time- and space-demanding even for state-of-the-art Datalog± -based reasoning systems. However, when answering Boolean Conjunctive Queries, a subset of the generated facts is often superfluous for the result. To tackle this problem, we presented heuristic-based reasoning, a novel reasoning approach that optimizes query evaluation by exploiting external domain knowledge in the form of a heuristic function. We provided experimental evaluation and applied such methodology to eficiently solve computationally demanding scenarios over large KGs in the financial domain. Future work includes extending heuristic-based reasoning with more advanced informed search strategies, as well as adaptive approaches to select the most suitable ground heuristic function depending on the use case and the KG.
The work on this paper was partially supported by the Vienna Science and Technology Fund (WWTF) grant VRG18-013.