Reasoning in Warded Datalog+/- with Harmful Joins

Abstract

Warded Datalog+/- is a powerful member of the Datalog+/- family of logic languages, featuring full support for recursion and existential quantification. As a result of the promising trade-of between expressive power and data complexity ofered, it recently rose as a relevant candidate for ontological reasoning on large knowledge graphs and is employed as logic core of the Vadalog system, a well-known state-of-the-art reasoner. To achieve decidability and data tractability in practice over recursive settings, reasoners such as Vadalog adopt specialized strategies that control the efects of recursion and ensure reasoning termination with small memory footprint. However, exploiting the theoretical underpinnings of the Warded fragment, to enable these strategies, requires the settings not to contain “harmful” joins, i.e., on variables afected by existential quantification. To support reasoning decidability and the full expressive power of the language, we developed the Harmful Join Elimination, an algorithm that removes such joins while preserving the correctness of the task, and we integrated it into the Vadalog system.

Keywords

• eol>Datalog
• Vadalog
• ontological reasoning
• existential quantification
• harmful joins

1. Introduction

Recent years’ widespread interest towards querying and exploiting large amounts of data in the form of knowledge graphs (KGs) has led to the rising development and adoption of intelligent systems that manage such extensional knowledge and infer new intensional one via eficient ontological reasoning mechanisms [ 1 ]. To achieve this, modern reasoning and KG navigation applications require to employ powerful formalisms and logic languages for knowledge representation [ 2 ], capable of providing full support for recursion and existential quantification as well as sustaining decidability and polynomial data complexity of the task [ 3 ].

Datalog± [ 4, 5, 6, 7 ] is one of the most commonly adopted families of logic languages (technically, fragments) for reasoning on KGs [ 6 ]. Among them, Warded Datalog± [ 8 ] efectively covers the above requirements. Indeed, it encompasses both a high expressiveness, capturing plain Datalog as well as SPARQL queries under OWL 2 QL entailment regime and set semantics, and a simple syntax that enable powerful knowledge-modeling. It also ofers a very good tradeof with computational complexity and captures PTIME for the reasoning [ 9 ]. Its semantics is defined via the chase [ 10 ], an algorithmic tool that takes as input a database and a set Σ of rules, and adds new tuples to until Σ is satisfied: such tuples may contain freshly generated symbols (technically, labelled nulls) that act as placeholders for the existentially quantified variables [ 6 ]. The Warded fragment is employed in the Vadalog system [ 11 ], a state-of-the-art reasoner that allows to perform ontological reasoning tasks in complex scenarios.

While such favourable characteristics of Warded Datalog± bode well for eficient implementations, the interplay between recursion and existential quantification may lead to the generation of infinite labelled nulls in the chase, causing the procedure not to terminate and thus inhibiting decidability of the reasoning task in practice [ 5 ]. To properly control such interactions, reasoners resort to specific techniques known as termination strategies. Specifically, the Vadalog system employs the isomorphism termination strategy, which consists in suppressing isomorphic copies of previously generated facts (i.e., same name, same constants in same positions and bijection between labelled nulls), hence the chase steps starting from them are not performed and the descending facts are not generated. The correctness of such strategy is corroborated by the reasoning boundedness property of the fragment, which states that facts derived from isomorphic origins are isomorphic, thus uninformative for the reasoning task [ 3 ]. However, as a necessary condition to exploit this property, the set of Warded rules in the scenario is required to be in a harmless form, i.e., without joins between variables afected by existential quantification. Indeed, during the chase rules with such harmful joins could activate on labelled nulls. Therefore, suppressing isomorphic facts that carry these nulls could inhibit rule activation and afect reasoning correctness. On the other hand, avoiding the use of these joins afects the expressive power of the fragment. Consider the following example. Example 1. Company merger scenario modeled with a set Σ of Warded Datalog± rules.

Company(x) → ∃c CEO(x, c) Merges(x, y), CEO(x, c) → CEO(y, c) Corp(x, y) → ∃c CEO(x, c), CEO(y, c) CEO(x, c), CEO(y, c) → Corp(x, y)

( ) ( ) ( ) ( ) For each company there exists a CEO (rule ). If merges with a company , also becomes CEO of (rule ). If and have a common CEO, they are in the same corporation (rule ) and vice versa (rule ). Consider the database instance = {Company(Hsb), Company(Iba), Merges(Hsb, Iba)} and the query : “what are all the entailed Corporations?” as ontological reasoning task. It can be observed that the set of corporations is finite, whereas the chase does not terminate. By following the procedure without termination strategy, we first generate CEO(Hsb, 0) and CEO(Iba, 1) by activating from the facts Company(Hsb) and Company(Iba), respectively. Next, we obtain CEO(Iba, 0) from , Corp(Hsb,Iba) via the join on 0 in , then CEO(Hsb, 2) and CEO(Iba, 2) by activating , and so on. Due to the existential quantification in rule and its interplay with the recursions in rules and , an infinite set ⋃︀=3,...{CEO(Hsb, ), CEO(Iba, )} is generated. On the other hand, employing the isomorphism termination strategy is not feasible either, due to the harmful join in rule . Indeed, CEO(Iba, 0) is isomorphic with CEO(Iba, 1), yet its pruning would prevent the join in with CEO(Hsb, 0) from generating Corp(Hsb,Iba) and the query in Example 1 from being answered correctly.

In this discussion paper, we illustrate how we enabled reasoning termination and decidability in practice over Warded Datalog± programs with harmful joins while preserving the expressive power of the fragment. First, we introduce the disarmament problem, which consists in rewriting such programs into a version without harmful joins (namely, in the newly defined fragment Harmless Warded Datalog± ) that is equivalent with respect to the chase. Then, we present Harmful Join Elimination (HJE) [ 12, 13 ], the first, to the best of our knowledge, rewriting technique to solve the disarmament problem. Finally, we discuss HJE integration into the Vadalog system and its reasoning application over the scenario in Example 1. Related Work. The importance of achieving reasoning decidability in Datalog± fragments and handling the interplay between recursion and existential quantification acted as catalysts for the development of novel approaches for reasoning termination [ 14, 7, 6 ]. More in general, HJE belongs to the class of methodologies for Datalog rewriting. Among them, we mention its conversion into fragments such as Guarded [ 15 ], Linear [ 16 ], and Disjunctive [ 17 ]. Furthermore, by interpreting the rules as queries, distinct techniques were proposed to rewrite Datalog± programs with existentials [ 18 ] from Regular Path Queries [ 19 ] and Description Logics [ 20 ]. Overview. The remainder of this paper is organized as follows. In Section 2, we provide an overview of Warded Datalog± . In Section 3, we illustrate the HJE algorithm as well as its application over Example 1 in the Vadalog system. We draw our conclusions in Section 4.

2. Syntax and Semantics of Warded Datalog±

A Warded Datalog± program consists of a set of facts and rules. An existential rule is a first-order sentence ∀¯∀¯( (¯, ¯)→∃¯ (¯, ¯)), where (the body) and (the head) are conjunctions of atoms, over the respective predicates, with constants and variables. For brevity, we may omit quantifiers and denote conjunction by comma. Let Σ be a set of rules and [] a position (i.e., the -th term of a predicate with arity , where = 1, . . . , ). We define [] as afected if (i) appears in a rule in Σ with an existentially quantified variable ( ∃-variable) in the -th term or, (ii) there is a rule in Σ such that a universally quantified variable ( ∀-variable) is only in afected body positions and in [] in the head. A ∀-variable is harmful, wrt a rule in Σ, if appears only in afected positions in , otherwise it is harmless. In Example 1, and are existential rules, while is a harmful join rule, i.e., a rule such that a harmful variable is involved in a join (namely, harmful join). If the harmful variable is in head( ), it is dangerous [ 1 ].

Chase-based procedures enforce the satisfaction of Σ over a database , incrementally expanding into new instances with facts derived from the application of the rules, until Σ is satisfied ( = ℎ(, Σ)). Consider an instance ′ ⊇ and a rule : (¯, ¯)→∃¯ (¯, ¯) ∈ Σ. In the version of the chase we refer to (known as oblivious [ 5 ]), a chase step ⟨︀ ,ℎ⟩︀ is applicable to ′ if there exists a homomorphism ℎ that maps the atoms of (¯, ¯) to facts of (i.e., ℎ( (¯, ¯)) ⊆ ). When the chase step is applicable, the atom ℎ′( (¯, ¯)) is added to ′, where ℎ′ is obtained by extending ℎ so that ℎ′() is a fresh labelled null, ∀ ∈ ¯. The chase graph (, Σ) is the directed graph with the facts from chase(, Σ) as nodes and an edge from a node to a node if is obtained from (and possibly other facts) via a chase step [ 7 ].

Given a pair = (Σ, Ans), where Ans is an n-ary predicate, the evaluation of over is the set of tuples (, Σ) = {¯ ∈ dom() | Ans(¯) ∈ chase(, Σ)}, where ¯ is a tuple of constants. A reasoning task consists in finding an instance st: (i) ¯ ∈ if Ans(¯) ∈ (, Σ); and (ii) for every other ′ st ¯ ∈ ′ if ¯ ∈ (, Σ), there is a homomorphism from to ′ [ 11 ].

3. Enabling Reasoning in Warded Datalog±

To achieve reasoning termination and decidability over recursive Warded Datalog± settings, especially in the presence of existential quantification, the oblivious chase is enriched with the isomorphism termination strategy, which acts as a firing condition that limits the activation of applicable chase steps [ 11 ]. With reference to the definitions in Section 2, such isomorphic chase variant causes an applicable step ⟨︀ ,ℎ⟩︀ to activate, wrt ′ ⊇ , if there is no isomorphism of h(head( )) with ′. Therefore, given two isomorphic facts and ′, only is explored in the isomorphic chase, whereas the descending portions of the chase graph rooted in ′ are pruned because isomorphic to the ones rooted in , thus uninformative for the reasoning task. Harmless Warded Datalog± . However, as we have introduced, in order to exploit such reasoning boundedness property and sustain decidability of the task while preserving correctness, Warded programs with recursion and existentials must not contain harmful join rules [3, Theorem 2], that is, they belong to Harmless Warded Datalog± [ 12 ]. Without loss of generality (as more complex joins can be broken into multiple steps [ 11 ]), a harmful join rule is a warded rule : (1, 1, ℎ), (2, 2, ℎ) → ∃ (, ), where , and are atoms, [ 3 ] and [ 3 ] are afected positions, 1, 2 ⊆ , 1, 2 ⊆ are disjoint tuples of harmless variables or constants and ℎ is a harmful variable. A set of rules ∈ Harmless Warded Datalog± if: (1) it is warded, i.e., all the dangerous variables in its rules appear in a single body atom (the ward), which only shares harmless variables with the rest of the body; and (2) it does not contain harmful join rules. Disarming the Warded Fragment. While in presence of programs without harmful joins the isomorphic chase can be employed without afecting the correctness nor the computational properties of the reasoning, restricting the Warded fragment to its Harmless Warded counterpart afects the expressive power available to reasoners such as the Vadalog system implementing it. With the goal of preventing such syntactic limitations, we developed a technique to solve the disarmament problem, that is, to rewrite a set Σ of Warded Datalog± rules in input to the reasoners into an equivalent set Σ′ of Harmless Warded rules. In this context, two sets of rules are considered equivalent if they have the same meaning with respect to the chase [ 16 ], i.e., chase(, Σ) = chase(, Σ′) modulo fact isomorphism for each database . Such technique, which we named Harmful Join Elimination (HJE), also allowed us to operationally prove that for each Warded set there exists an equivalent Harmless Warded one [ 13 ].

Intuitively, the HJE algorithm replaces each harmful join rule with a set of harmless rules that cover the generation of all the facts derived from activating , thus preserving correctness. To achieve this, it operates by considering the rules involved in the propagation of the afectedness (i.e., the labelled nulls in the chase) from the existentials to the harmful join variables in . Definition 1 ( Causes of Afectedness ). Let ∈ Σ be a harmful join rule and let ∈ {A,B} be an atom in the body of . We define causes of afectedness as the sequences of rules Γ = [ , . . . , 1] ( < |Σ|, ≥ 1) ∈ Σ, where: (i) 1: 1(, 1), 1→∃ℎ 2(, 2, ℎ) is a direct cause, i.e., an existential rule that causes a position to be afected; and (ii) : (, , ℎ), →+1(, +1, ℎ), 1 < ≤ , are indirect causes, i.e., rules that propagate the afectedness from 1 to , such that +1 = . 1, . . . , are atoms, 1, . . . , are atoms or conjunctions of atoms not containing ℎ (as the rules are Warded). Let = Γ⌢Γ be the concatenation of the sequences Γ and Γ with the same direct cause: the causes in are labelled after the sequence they belong to. With reference to Example 1, the rules and are direct causes of afectedness, whereas is an indirect one. The sequences of causes for the atom CEO (k ∈ {1,2}, in order of appearance in ) are: ΓCEO1 = [ ], ΓCEO2 = [, ], ΓCEO3 = [ ], ΓCEO4 = [, ]. For instance, 21 = [ ΓCEO12 , ΓCEO12 , ΓCEO21 ] is a concatenation, as ΓCEO12,ΓCEO21 contain the same direct cause .

To determine how the propagated nulls activating the harmful join in afect the meaning in the chase, and to consequently build proper harmless rules, we compose along all its concatenations of causes of afectedness via the unfolding and folding operations [ 16 ]. Definition 2 ( Unfolding and Folding). Let be a rule , →, where and are atoms and is an atom or a conjunction of atoms, and let be a rule →′, where ′ is an atom and an atom or a conjunction of atoms. Let ′ be unifiable with by substitution . The result of unfolding at with is the rule : (, →) . If the head of contains an ∃-variable ℎ, it replaces ℎ with a Skolem atom ℎ in , where is an injective, deterministic and range disjoint function that calculates the values for ∃-variables, to control the identity of labelled nulls. Now, let ′ be a rule ′→, where is an atom and ′ is an atom or a conjunction of atoms. Let ′ be unifiable with by substitution ′. The result of folding into ′ is the rule : (, →) ′. The results of the compositions for each harmful join rule are represented via the harmful unfolding tree (hu-tree). Apart from the more technical side [ 12 ], the hu-tree for ⟨︀ Σ, ⟩︀ can be defined as a rule-labelled tree-like structure where: (i) the root is labelled by ; (ii) for each , there exists a root-to-leaf path whose nodes are labelled by the result of unfolding their parent nodes with the causes in (in order of appearance); (iii) for each ∈ involved in a recursion, there exists a leaf labelled by result of unfolding its parent node with and then folding it into . By definition of unfolding and folding, the leaves in are harmless rules that cover the generation of all the facts derived in the chase from activating on labelled nulls [ 13 ]. α

CEO(x,c),CEO(y,c)⟶Corp(x,y)

β Algorithm 1 Back-Composition in Harmful Join Elimination. HJE in Vadalog System. HJE is integrated into the logic optimizer of the Vadalog system, the component responsible for applying the required rewriting steps to the program before the reasoner processes it [ 11 ]. This enables reasoning termination and decidability over recursive Warded settings with harmful joins without afecting the expressive power of the Warded fragment. Thus, we are now able to reason over the scenario in Example 1. We run the experiments on a local installation of the Vadalog system, with a MacBook Pro i7 with 2.5 GHz and 16 GB of RAM. The rules listed below are added via HJE to Σ′ (some are merged for space reasons): 3 labels the leaf of 21 and 3 labels the folded node over ΓCEO24 from Figure 1, after skolem cleanup. We adjusted input data from the DBpedia [ 3 ] company KG, adopting datasets of increasing complexity, with 1K, 5K, 10K, 15K, 20K, 25K and 30K companies. We built two reasoning tasks: (i) Spec, to obtain all the corporations of the company CBS, and (ii) All, to obtain all the corporations, to vary the number of companies. Figure 2(a) illustrates the reasoning times, all under 16 seconds, which proves the very good performance of the Vadalog system. Spec requires more time than All for smaller datasets; when the number of companies increases, All tends to a steeper curve. Figure 2(b) shows the number of corporations discovered in All.

Company(x) → Corp(x, x)

Company(x), Merges(x, y) → Corp(x, y), Corp(y, x) Company(x), Merges(x, y), Merges(x, z) → Corp(y, z) Corp(x, y), Merges(x, w), Merges(x, z) → Corp(w, z) Corp(x, y), Merges(x, z) → Corp(x, z), Corp(z, x)

Corp(x, y) → Corp(x, x) Corp(x, y), Merges(x, z) → Corp(y, z), Corp(z, y) Corp(x, y), Merges(y, z) → Corp(x, z), Corp(z, x) ( 1) ( 2,3) ( 4) ( 5) ( 6,7)

( 8) ( 1,2) ( 3,4)

4. Conclusion

To achieve reasoning termination and decidability over Warded Datalog± in practice, the settings must not contain harmful joins. In this work, we discussed the disarmament problem of rewriting such joins into an equivalent Harmless Warded form that upholds the expressiveness of the fragment and the correctness of the task. We then presented the Harmful Join Elimination, the disarmament algorithm integrated into the Warded Datalog± -based reasoner Vadalog system.

References

[1] G. Gottlob , A. Pieris , Beyond SPARQL under OWL 2 QL entailment regime: Rules to the rescue , in: IJCAI , 2015 .

[2] M. Krötzsch , V. Thost , Ontologies for knowledge graphs: Breaking the rules , in: International Semantic Web Conference (1) , volume 9981 of LNCS , 2016 , pp. 376 - 392 .

[3] L. Bellomarini , E. Sallinger, G. Gottlob, The Vadalog System: Datalog-based reasoning for knowledge graphs , VLDB 11 ( 2018 ).

[4] P. Barceló , R. Pichler , Datalog in Academia and Industry: Second International Workshop, Datalog 2.0, Vienna, Austria, September 11 -13, Proceedings, volume 7494 , Springer, 2012 .

[5] A. Calì , G. Gottlob, M. Kifer, Taming the infinite chase: Query answering under expressive relational constraints , Journal of Artificial Intelligence Research 48 ( 2013 ) 115 - 174 .

[6] A. Calì , G. Gottlob, T. Lukasiewicz , B. Marnette , A. Pieris , Datalog+/ -: A family of logical knowledge representation and query languages for new applications , in: 2010 25th Annual IEEE LICS, IEEE , 2010 , pp. 228 - 242 .

[7] A. Calì , G. Gottlob, T. Lukasiewicz , A general datalog-based framework for tractable query answering over ontologies , Journal of Web Semantics 14 ( 2012 ) 57 - 83 .

[8] G. Gottlob , A. Pieris , E. Sallinger, Vadalog: recent advances and applications , in: JELIA, Springer, 2019 , pp. 21 - 37 .

[9] L. Bellomarini , G. Gottlob , A. Pieris , E. Sallinger, Swift logic for big data and knowledge graphs , in: IJCAI , Springer, 2017 , pp. 2 - 10 .

[10] D. Maier , A. O. Mendelzon , Y. Sagiv , Testing implications of data dependencies , ACM Transactions on Database Systems 4 ( 1979 ) 455 - 468 .

[11] L. Bellomarini , D. Benedetto , G. Gottlob , E. Sallinger, Vadalog: A modern architecture for automated reasoning with large knowledge graphs , Information Systems ( 2020 ) 101528 .

[12] T. Baldazzi , L. Bellomarini , E. Sallinger, P. Atzeni , Eliminating harmful joins in warded datalog+/- , in: International Joint Conference on Rules and Reasoning , Springer, 2021 , pp. 267 - 275 .

[13] T. Baldazzi , L. Bellomarini , E. Sallinger, P. Atzeni, iwarded: A system for benchmarking datalog+/-reasoning (technical report) , arXiv preprint arXiv:2103.08588 ( 2021 ).

[14] G. Berger , G. Gottlob , A. Pieris , E. Sallinger, The space-eficient core of Vadalog , in: PODS, 2019 , pp. 270 - 284 .

[15] G. Gottlob , S. Rudolph , M. Simkus , Expressiveness of guarded existential rule languages , in: PODS , 2014 , pp. 27 - 38 .

[16] F. Afrati , M. Gergatsoulis , F. Toni , Linearisability on datalog programs, Theoretical Computer Science 308 ( 2003 ) 199 - 226 .

[17] M. Kaminski , Y. Nenov , B. C. Grau , Datalog rewritability of disjunctive datalog programs and non-Horn ontologies , Artificial Intelligence 236 ( 2016 ) 90 - 118 .

[18] Z. Wang , P. Xiao , K. Wang , Z. Zhuang , H. Wan , Query answering for existential rules via eficient datalog rewriting ., in: IJCAI , 2020 , pp. 1933 - 1939 .

[19] N. Francis , L. Segoufin , C. Sirangelo , Datalog rewritings of regular path queries using views , arXiv preprint arXiv:1511.00938 ( 2015 ).

[20] S. Ahmetaj , M. Ortiz , M. Simkus , Polynomial datalog rewritings for expressive description logics with closed predicates ., in: IJCAI , 2016 , pp. 878 - 885 .