When reasoning over large knowledge graphs, Datalog+/- languages ofer a good trade-of between expressive power and computational complexity. However, in case of considerably large inputs and in the presence of recursive rules, even state-ofthe-art reasoners struggle to accomplish reasoning tasks, e.g. answering Boolean Conjuctive Queries (BCQs). To address this problem, we introduce the notion of heuristic-based reasoning, that is, evaluating Datalog+/- rules according to an order of the facts determined via a user-defined heuristic. We show that adopting a fitting heuristic that guides the reasoning process provides an optimized way to answer a BCQ. To achieve this behaviour in practice, we enrich Datalog+/- programs with a context-aware operator, which we name Dynamic Hint Operator. We apply our new methodology to eficiently solve the Close Link problem on the knowledge graph of Italian companies, a relevant financial problem that estimates the risk to grant a specific loan to a company that is backed by collateral issued by another company.
The growing need of enriching financial and corporate knowledge and delivering AI-enhanced applications is pushing companies to adopt data-intensive intelligent systems with reasoning capabilities. Under the rising paradigm of Knowledge Graphs (KGs), modern reasoners support the augmentation of extensional data with logical representations of knowledge as ontologies and programs (i.e., sets of facts and rules) [1].
real-world application scenarios, navigational capabilities, empowered by recursion in combination with arbiOntological Reasoning on KGs. As a main require- trary joins, are vital for expressing complex reasoning ment, languages for knowledge representation and rea- tasks over KGs. At its essence, graph navigation represoning must exhibit high expressive power, being able sents the most time and space demanding computation, to model complex real domains with full recursion and as it may consider the whole KG as input for an indefinite existential quantification. At the same time, they must number of chase steps. Additionally, when answering achieve low computational complexity, enabling scalabil- a Boolean Conjuctive Query (BCQ) – i.e., a query where ity in practice [2]. The Datalog± family [3, 4, 5, 6, 7, 8, 9] the answer is a boolean value – under a set of (recursive) is one of the commonly adopted families of logic lan- TGDs, in most of the cases, not all the generated facts guages (technically, fragments) for reasoning on KGs [10]. actually contribute to the result. As an example, consider It covers these requirements, ofering a good trade-of the following set of Datalog± TGDs. between expressive power and complexity. It guarantees decidability and, in some fragments [11], tractability of Example 1. An example of knowledge graph navigation.
Failure(b), b = BNP → Shock(b)
Shock(b1), Credit(b1, b2) → Shock(b2)
(
The bank BNP experiences a shock due to failure (rule 1).
If 1 is a bank that undergoes a shock and 2 is a bank in a credit exposure constraint with 1, then the shock is propagated to 2 (rule 2).
Consider, as ontological reasoning task, the BCQ
= Shock(Barclays) ∧ Shock(UBS) to check whether Barclays and UBS may experience a credit shock, and the database instance = {Failure(BNP), Credit(Deutsche, Barclays), Credit(MPS, Unicredit), Credit(BNP, MPS), Credit(Barclays, UBS), Credit(BNP, Deutsche)}. Observe that there are many possible ways to activate rule 2, causing the generation of a distinct number of facts that do not actually contribute to the query result. In fact, by activating rule 2 from the facts Shock(BNP) and Credit(BNP, Deutsche), we generate Shock(Deutsche). Then, we can use the latter fact and Credit(Deutsche, Barclays) to trigger again rule 2 and produce Shock(Barclays). Finally, we generate Shock(UBS) by applying rule 2 over the facts Credit(Barclays, UBS) • A novel scalable approach to tackle the BCQ answerand Shock(Barclays). On the other hand, if we activated ing problem in recursive settings. We introduce the rule 2 via diferent facts, additional tuples would be gen- notion of heuristic-based reasoning, that is, evaluating erated that, while not providing any contribution to the Datalog± rules according to an established order of the result, would afect the performance of the computation facts, guided by a user-defined heuristic. Specifically, (Shock(MPS), Shock(Unicredit)). we enrich Datalog± programs with a context-aware op
In this work, we investigate the generation of super- erator, which we name Dynamic Hint Operator (DHint). lfuous facts in recursive settings when answering BCQs. This allows the reasoning engine to prioritize specific We contribute a novel reasoning approach that tackles tuple bindings in the evaluation of a Datalog± rule, in this problem by adopting a tuple-binding prioritization order to eficiently answer a specific BCQ. strategy for the evaluation of Datalog± rules. Specifically, we employ a user-defined heuristic as a guideline for TGDs activation in the chase. issued by another company [13]. As per European Central Bank’s directive [15, 16], a company cannot act as guarantor for a diferent one if they are close links.
It can be empirically shown that, to determine whether and are close links, adopting a heuristic that prioritizes the exploration of nodes with a higher in-degree allows to reach the query result in an eficient fashion and limits the generation of unavailing facts. Motivated by this, we eficiently solve the Close Link problem on the ICKG by introducing a new reasoning methodology that enriches the semantics of TGDs with context-awareness.
Specifically, we evaluate Datalog ± rules according to an order of the input facts that is determined by employing the aforementioned heuristic. In detail, the main contributions of this paper are: • A relevant application of the Dynamic Hint Operator to solve the Close Link problem on the enterprise KG of Italian companies. In particular, we provide an ad-hoc solution that exploits an empirically-defined heuristic as a guideline for the TGDs activation.
A Financial Use Case. Financial Knowledge Graphs are central objects in corporate economics and are of high importance for central banks, financial authorities and national statistical ofices, to solve relevant problems • An evaluation of the performance of the DHintin distinct areas: banking supervision, credit-worthiness based approaches in recursive settings. In particuevaluation, anti-money laundering, insurance fraud de- lar, we compare the ad-hoc DHint implementation tection, economic and statistical research and many more. with state-of-the-art BCQ evaluation techniques for In particular, in the Central Bank of Italy’s enterprise the Close Link problem and we show that a fitting KG of Italian companies (ICKG) [13, 14], ownership is heuristic applied via DHint provides an optimized way a core concept: nodes are companies and persons, and to evaluate a BCQ. ownership edges are labelled with the fraction of shares that a company or person owns of a company . The Related Work. To outline the related work for this paICKG consists of 4.059M companies and people as nodes per, we distinguish the following two perspectives. From and 3.960M shareholdings as edges. a financial point of view, distinct reasoning-based ap
Producing facts that do not contribute to the BCQ re- proaches have been adopted to tackle and solve relevant sult becomes particularly relevant on such large inputs, business problems. Among them, we mention the efecespecially in the presence of recursive TGDs, since their tive application of “Golden Powers” (i.e., the possibility evaluation might cause a blowup of the unavailing facts. of the central Government to veto specific acquisition These complications heavily afect the resolution of a transactions) to prevent hostile company takeovers [17]. high interest scenario in the financial context, that is, the Other use cases exploit rule-based reasoning to counterClose Link problem. It consists of determining whether act money laundering processes [18] and to determine there exists a (direct or indirect) link between a company whether a company or a person exerts control, through and a company based on a high overlap of shares, and the majority of voting rights, on another company, i.e., it can be modeled with a set of recursive TGDs. Solving the Company Control problem [13]. From a technical this problem allows us to estimate the risk to grant a standpoint, we refer to approaches that exploit external specific loan to a company that is backed by collateral knowledge to eficiently solve query-answering tasks. Specifically, in the context of DBMSs, there exist multi- the satisfaction of a set of dependencies Σ over . It ple alternatives to inject specific criteria that guide the expands with facts derived via the application of rules query plan creation. Standard hint operators provide a ∈ Σ over , with the chase steps into a new database mechanism that instructs the optimizer on how to de- chase(,Σ ), possibly containing labelled nulls as placetermine the execution plan for a certain query, based holders for the existentially quantified objects. Starting on specific directives (e.g., join order, choice of physical from , the chase incrementally applies chase steps and operators for joins, etc.) [19, 20]. Additionally, ad-hoc builds new database instances, denoted as . Given a techniques to enhance the optimizer in the plan com- TGD (¯, ¯) →∃¯ (¯, ¯) , a TGD chase step is applicable putation have been proposed: for instance, “Phint”, a to if there exists a homomorphism h that maps the hinting language that introduces specific constraints to atoms of (¯, ¯) to atoms of (i.e., h( (¯, ¯) ) ⊆ I ) and guide the optimizer in the evaluation of the most suitable there does not exist any extension ℎ′ ⊇ ℎ, such that query plan, with the lowest estimated cost [21]. Such ℎ′( (¯, ¯))) ⊆ . When the chase step is applicable, approaches act statically in the query evaluation, modify- the atom ℎ′′ ( (¯, ¯))) ⊆ is added to , where ℎ′′ is ing how the query is structured and how the query plan obtained by extending ℎ so that ℎ′′ (¯) ∈ is a fresh is created. Alternatively, there exist techniques that ex- labelled null, for each ∈ ¯. clude the non-relevant derivations in the query execution via an eager computation: such approaches cannot be Boolean Conjunctive Queries (BCQs). An answer to a generally adopted in any query, but they only take place BCQ is defined via homomorphisms, which are constantin the presence of monotonic aggregations [22]. Yet, in preserving mappings h from variables in ¯ and ¯ to elthe context of ontological reasoning, the DHint operator ements of ∪ , s.t. ∀¯∀¯ (¯, ¯) ⊆ and ℎ(¯) = is, to the best of our knowledge, the first technique that is a tuple of the query answer. The answer to a BCQ enriches the semantics of the TGDs with a heuristic to ← ∃ ¯ (¯) over an instance is positive if there guide reasoning and optimize BCQ answering. exists a homomorphism h: ¯ → ∪ s.t. h( (¯) ) ⊆ . Overview. This paper is organized as follows. We start by laying out the background notions in Section 2. In 3. Dynamic Hint Operator Section 3, we define the notion of heuristic-based reasoning and we introduce the DHint operator. In Section 4, In this section, we discuss the theoretical aspects of our we discuss the application of DHint for the Close Link new reasoning methodology. As the goal of this paper is problem and we provide the experimental evaluation. We to highlight how our approach improves the performance draw our conclusions in Section 5. of a real-world scenario, here we only provide the main notions required to achieve such purpose.
The standard chase step definition, addressed in Sec2. Reasoning with TGDs tion 2, lacks a specific strategy to choose among all the applicable homomorphisms that map the variables of a certain atom. Indeed, such choice impacts on the number of chase steps required to generate a certain fact.
Moreover, while the order of the chase steps does not afect correctness of query answering (as the same final instance chase(,Σ ) is always produced), in case of BCQs selecting a suitable homomorphism favours the eficiency of the reasoning task, as it allows to produce less facts that do not contribute to answering the query.
Let , , and be disjoint countably infinite sets of constants, (labeled) nulls and (regular) variables, respectively.
A (relational) schema S is a finite set of relation symbols (or predicates) with associated arity. A term is a either a constant or 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 (or simply database) over S associates to each relation symbol in S a relation of the respective arity over the domain of constants and nulls. The members of relations are called tuples or, alternatively, facts.
Datalog± languages generalize standard Datalog rules by introducing existential quantifiers in rule heads. A Datalog± program consists of a set of existential rules, or tuple-generating dependencies (TGDs), of the form ∀¯∀¯( (¯, ¯) →∃¯ (¯, ¯)) , where (the body) and (the head) are conjunctions of atoms with constants and variables. For brevity, we omit quantifiers and denote the conjunction ∧ by comma.
The Chase Procedure. The chase [12] is a fundamental algorithmic tool that modifies a database to enforce Heuristic-based Reasoning. To apply a strategy that selects such favorable homomorphisms, eficiently solving the task at hand, we enrich the program by injecting an external knowledge of the reasoning setting, provided by a domain expert. To better understand this concept, we refer to Example 1. Assume, as external knowledge in a non-realistic scenario, that every Italian bank only grants credit to other Italian banks. Therefore, it is intuitive to observe that, when answering the BCQ , not all the applicable homomorphisms from rule 2 are required.
Indeed, we only need to consider the ones whose images (tuples) correspond to Credit facts that do not involve Italian banks, as to answer in this domain the only contributing facts refer to shock events of non-Italian banks. We represent this external knowledge via a heuristic function, defined as follows.
Definition 1 ( Ground Heuristic Function). Consider a database over a relational schema and a set of tuples = {| ∈/ }. A Ground Heuristic Function (GHF) : → R>0 ∪ → 0 is a user-defined function that maps each tuple of to a weight ∈ R>0 and each tuple of to 0. We define Extended Ground Heuristic Function (EGHF) ∆ : () → R>0 ∪ ( ) → 0 as a function that maps a set of tuples ⊆ ∪ to a weight ¯ such that ¯= ∑︀∀∈ (), i.e., ¯ is the sum of the weights assigned by to each ∈ .
Note that, when the input of the GHF is not a ground fact (i.e., a tuple not in ), the output is always 0, as our heuristic function does not consider facts that are generated in the chase. This statement also holds for the EGHF, as the contributions of input non-ground facts are irrelevant. We exploit the EGHF as a guideline in the chase to determine which homomorphism is the most suitable at each chase step. We define them as follows.
Failure(b), b = BNP → Shock(b) (
In this section, we provide an experimental evaluation of our heuristic-based reasoning approach. We apply our novel reasoning methodology to solve the Close Link problem over the ICKG.
Definition 2 ( Heuristic Chase Step Application).
Consider a TGD : (¯, ¯) →∃¯ (¯, ¯) , an
intermediate chase instance and an EGHF ∆ . Let be the The Close Link Problem. Per European Central Bank’s
set of possible homomorphisms applicable from to directive, a company 1 cannot act as guarantor for a
. A Heuristic chase step consists of the application of company 2 if 1 and 2 are close links [15, 16].
Specifℎ = [∆( ℎ( (¯, ¯)))] ∀ℎ∈ over , i.e., ℎ is the ically, two companies 1 and 2 are close links if: (i) 1
homomorphism in whose images (tuples) maximise ∆ . (resp. 2) owns directly or indirectly, through one or more
other companies, 20% or more of the share of 2 (resp. 1),
Intuitively, the heuristic chase step exploits the knowl- or (ii) a third-party owns directly or indirectly, through
edge of the domain expert by prioritizing the homomor- one or more other companies, 20% or more of the share of 1
phism whose images (i.e., tuples) have the highest EGHF and 2. Given these settings, the problem can be modeled
value. Based on such revised form of the chase step appli- via the set of recursive TGDs we provide in Example 3.
cation, we devise a new reasoning methodology, which
we name heuristic-based reasoning. It enables the genera- Example 3. Close Link modeled with a set of TGDs.
tion of less unavailing facts, with respect to the standard
chase, when answering BCQs in the presence of TGDs, Own(1, 2, s) → MCl(1, 2, s) (
MCl(1, 2, ), ts = sum(), ts ≥ 0.2 → 1(1, 2) (
Every partial share of 2 owned (directly or indirectly) by 1 is summed to compute the total share that 1 owns of 2; as stated by (i) of the close link definition, if the total share is greater or equal than 0.2, then 1 and 2 are close links (rule 3). The third-party case is modeled according to (ii) of the definition (rule 4).
DHint Implementation. We implemented the Close Link Solver (CLS), an ad-hoc system that allows us to answer under the TGDs of Example 3, i.e., it is able to determine whether two companies are close links. CLS adopts a streaming architecture such that each iteration produces a new tuple representing a path between two companies 1 and 2 with weight . Such corresponds to the partial share that 1 owns of 2 and it is calculated as the product of all the shares of the ownership edges in the traversed path. Whenever the new tuple represents a path between the companies and involved in the BCQ , the system checks whether the sum of the partial shares of owned (directly or indirectly) by exceeds 0.2, in which case and are close links and the task terminates successfully.
We integrated CLS with two distinct approaches:
BCQ = Cl(,) and the TGDs of Example 3 to check whether the companies and are close links. When we consider a high number of input Ownership edges, as in the case of ICKG, even state-of-the-art query evaluation techniques struggle to eficiently answer . Modern reasoners encode chase-based procedures by adopting two main approaches: (i) a materialization technique that consists of producing and storing all the facts for each predi- • a Standard one (Std), which essentially consists in a cate by adopting the so-called semi-naive evaluation [23]. classic transitive closure evaluation, which adopts a In this case, the rules are evaluated according to bottom- nested-loop join and a FIFO strategy to guide the genup strategies, starting from the initial database and re- eration of the facts; peatedly applying the rules until a fixpoint is reached; • a DHint-based one (DHint), which employs the EGHF (ii) a streaming technique that adopts reasoning query ∆ defined above to order the applicable homomorgraphs [24], where nodes correspond to relational al- phisms. As a result, it prioritizes the generation of the gebra operators (select, project and join) and edges are tuple whose provenance (namely, the facts it derives dependency connections between the rules. Such graph from) maximises ∆ . forms an active pipeline and the data flows through its nodes, each receiving input data from the previous nodes Experiments and Results. We compared the two apand performing the required transformations. Both these proaches over 100 pairs of companies in the ICKG. We approaches may cause the creation of facts that do not selected them randomly among a set of companies that contribute to answering the BCQ, as the fact generation are known to be close links. We run our system on a cloud process is independent from the query itself. For instance, instance of CLS in a running Ubuntu Standard E8s V4 the materialization approach creates all the facts corre- Linux machine, with 8 virtual v4 cores, 64 GB of RAM and sponding to a predicate, which may be unavailing to 64 GB SSD. For 84 pairs of companies, both approaches answer the BCQ. On the other hand, in the streaming terminated in less than two minutes. For the remaining approach the sequence of the generated facts depends on 16 pairs, we extended the execution time up to 10 minutes the order in which the input facts flow in the pipeline. and we ran our system again with both approaches. We A Heuristic for Close Links. We empirically observed collected the number of facts generated and the number that prioritizing the exploration of nodes with a higher of paths found between the close link candidates. As in-degree allows us to find a greater number of owner- a metric of comparison, we adopted the ratio between ship paths between the close link candidates, compared the total number of facts generated and the number of to standard graph visiting techniques. Motivated by paths between the close link candidates discovered by the how the limitations of BCQ evaluation techniques af- two approaches: we name this metric nFacts/nPaths ratio. fect the detection of close links between companies on Intuitively, this ratio represents the average number of the ICKG [13], we exploit such intuition and build an ad- facts to generate in order to find a new ownership path hoc EGHF ∆ to assign a weight to the ownership edges between the close link candidates. Figure 2 illustrates in input that is directly proportional to the in-degree of that, for all the 16 candidate pairs, the DHint approach the target nodes. With reference to Example 3, we enrich discovers a much higher number of paths than the Stanrule 2 with our DHint operator with such ∆ as follows: dard one in the same time. Moreover, our heuristic-based @hint2(∆ ) MCl(1, 2, 1), Own(2, 3, 2) approach allows us to prevent the generation of many → MCl(1, 3, 1 · 2) unavailing facts. Indeed, a considerably smaller number of facts are generated in order to achieve an answer to the Intuitively, rule 2 represents a graph navigation guided query, i.e., to determine whether the candidates are close by the EGHF ∆ , where the edges whose target nodes links. Hence, our novel approach achieves an inferior have a higher in-degree are prioritized. nFacts/nPaths ratio, as shown in Figure 1. (a) Ratio comparison on log10 scale.
(b) Actual ratio values.
Reasoning over large knowledge graphs, especially in the presence of recursive settings, can be extremely demanding even for state-of-the-art reasoners. However, when answering Boolean Conjuctive Queries (BCQs), not all the generated facts actually contribute to the result. For this reason, we introduced the heuristic-based reasoning, a novel reasoning approach that injects external domain knowledge, in the form of a heuristic function, into the program to prevent the generation of such unavailing facts and solve the task at hand in an eficient fashion.
To achieve this behaviour in practice, we presented the Dynamic Hint Operator, a context-aware operator that guides the reasoning process to optimize BCQ answering according to such heuristic. We employed our heuristicbased method to eficiently solve the Close Link problem on the ICKG and we laid the foundations for a domainaware approach to Datalog-based reasoning. constraints, J. Artif. Intell. Res. 48 (2013) 115–174. gence units: experience and vision, in: RuleML+ [6] A. Calì, G. Gottlob, T. Lukasiewicz, A general RR (Supplement), 2020.
Datalog-based framework for tractable query an- [19] V. Leis, A. Gubichev, A. Mirchev, P. Boncz, A. Kemswering over ontologies, J. Web Sem. 14 (2012) per, T. Neumann, How good are query optimizers, 57–83. really?, Proceedings of the VLDB Endowment 9 [7] A. Calì, G. Gottlob, T. Lukasiewicz, B. Marnette, (2015) 204–215.
A. Pieris, Datalog+/-: A family of logical knowl- [20] S. Chaudhuri, Query optimizers: time to rethink edge representation and query languages for new the contract?, in: Proceedings of the 2009 ACM applications, in: LICS, 2010, pp. 228–242. SIGMOD International Conference on Management [8] A. Calì, G. Gottlob, A. Pieris, Towards more ex- of data, 2009, pp. 961–968.
pressive ontology languages: The query answering [21] N. Bruno, S. Chaudhuri, R. Ramamurthy, Power problem, Artificial Intelligence 193 (2012) 87–128. hints for query optimization, in: 2009 IEEE 25th In[9] A. Calì, G. Gottlob, T. Lukasiewicz, A general ternational Conference on Data Engineering, IEEE, datalog-based framework for tractable query an- 2009, pp. 469–480. swering over ontologies, in: Proceedings of the [22] C. Zaniolo, A. Das, J. Gu, Y. Li, M. Li, J. Wang, DevelTwenty-Eighth ACM SIGMOD-SIGACT-SIGART oping big-data application as queries: an aggregateSymposium on Principles of Database Systems, based approach (2021).
PODS ’09, Association for Computing Machinery, [23] S. Abiteboul, R. Hull, V. Vianu, Foundations of New York, NY, USA, 2009, p. 77–86. URL: https: databases, volume 8, Addison-Wesley Reading, //doi.org/10.1145/1559795.1559809. doi:10.1145/ 1995.
1559795.1559809. [24] G. Graefe, W. J. McKenna, The volcano optimizer [10] A. Calì, G. Gottlob, T. Lukasiewicz, B. Marnette, generator: Extensibility and eficient search, in: A. Pieris, Datalog+/-: A family of logical knowl- Proceedings of IEEE 9th International Conference edge representation and query languages for new on Data Engineering, IEEE, 1993, pp. 209–218. applications, in: 2010 25th Annual IEEE LICS, IEEE, 2010, pp. 228–242. [11] G. Gottlob, A. Pieris, E. Sallinger, Vadalog: recent advances and applications, in: JELIA, Springer, 2019, pp. 21–37. [12] D. Maier, A. O. Mendelzon, Y. Sagiv, Testing implications of data dependencies, ACM Transactions on Database Systems 4 (1979) 455–468. [13] P. Atzeni, L. Bellomarini, M. Iezzi, E. Sallinger,
A. Vlad, Weaving enterprise knowledge graphs: The case of company ownership graphs., in: EDBT, 2020, pp. 555–566. [14] P. Atzeni, L. Bellomarini, M. Iezzi, E. Sallinger,
A. Vlad, Augmenting logic-based knowledge graphs: The case of company graphs (2021). [15] GUIDELINE (EU) 2011/14 OF THE ECB, https://www.ecb.europa.eu/ecb/legal/pdf/l_ 33120111214en000100951.pdf, 2014. [Online; accessed 14-Gen-2022]. [16] GUIDELINE (EU) 2018/570 OF THE ECB, https://www.ecb.europa.eu/ecb/legal/pdf/celex_ 32018o0003_en_txt.pdf, 2018. [Online; accessed 14-Gen-2022]. [17] L. Bellomarini, M. Benedetti, A. Gentili, R. Laurendi,
D. Magnanimi, A. Muci, E. Sallinger, Covid-19 and company knowledge graphs: assessing golden powers and economic impact of selective lockdown via ai reasoning, arXiv preprint arXiv:2004.10119 (2020). [18] L. Bellomarini, E. Laurenza, E. Sallinger, Rulebased anti-money laundering in financial intelli