Complexity of Approximate Query Answering under Inconsistency in Datalog

Abstract

Several semantics have been proposed to query inconsistent ontological knowledge bases, including the intersection of repairs and the intersection of closed repairs as two approximate inconsistency-tolerant semantics. In this paper, we analyze the complexity of conjunctive query answering under these two semantics for a wide range of Datalog languages. We consider both the standard setting, where errors may only be in the database, and the generalized setting, where also the rules of a Datalog knowledge base may be erroneous.

Introduction

Description logics (DLs) and existential rules from the context of Datalog are popular

ontology languages. In real-world ontology-based applications involving large amounts of data (such as ontology-based data extraction and/or integration), it is very likely that the data are inconsistent with the ontology, and thus inconsistency-tolerant semantics for ontology-based query answering are urgently needed.

Consistent query answering, first developed for relational databases [1] and then

generalized as the AR semantics for several DLs [ 12 ], is the most widely accepted semantics for querying inconsistent ontologies. Query answering under the AR semantics is known to be a hard problem, even for very simple languages [ 12 ]. For this reason, several other semantics have been recently developed with the aim of approximating consistent query answering [ 12,2,17,4 ].

In particular, in [12], besides the AR semantics, three other inconsistency-tolerant

query answering semantics are proposed, including the approximate intersection of repairs (IAR) semantics, in which an answer is considered to be valid, if it can be inferred from the intersection of the repairs (and the ontology). The intersection of closed repairs (ICR) [ 2 ] is another approximate semantics, in which an answer is valid, if it can be inferred from the intersection of the closure of the repairs (and the ontology).

The complexity of query answering under the AR semantics when the ontology is described using one of the central DLs is well-understood. The data and combined complexity were studied by [20] for a wide spectrum of DLs, while [2] identified cases

for simple ontologies (within the DL-Lite family) for which tractable data complexity results can be obtained. In [ 17,19,16 ], the data and different types of combined complexity, respectively, of the AR semantics have been studied for ontologies described via existential rules and negative constraints. [ 3 ] analyzed the data and combined complexity of query answering under the AR and IAR semantics for different notions of maximal repairs over the language DL-LiteR. Recently, the AR semantics was extended to the generalized repair semantics (GAR) and its computational complexity analyzed [ 8 ]. In the GAR semantics, also ontological rules may be removed, and some database atoms and rules are assumed to be non-removable.

This paper continues this line of research and analyzes the complexity of inconsistencytolerant query answering as follows:

B We consider different popular inconsistency-tolerant semantics, namely, the IAR

and the ICR semantics, in both their standard and their generalized repair variants.

B We consider the most popular Datalog languages: linear, guarded, sticky, and

acyclic existential rules, along with “weak” generalizations, as well as full restrictions, and full (i.e., non-existential) rules in general.

B Our analysis concerns the data, fixed-program combined, bounded-arity combined,

and combined complexity. 2

Datalog

We briefly recall some basics on existential rules from the context of Datalog [6].

General. We assume a set C of constants, a set N of labeled nulls, and a set V of regular variables. A term t is a constant, null, or variable. We also assume a set of predicates, each associated with an arity, i.e., a non-negative integer. An atom has the form p(t1; : : : ; tn), where p is an n-ary predicate, and t1; : : : ; tn are terms. Conjunctions of atoms are often identified with the sets of their atoms. An instance I is a (possibly infinite) set of atoms p(t), where t is a tuple of constants and nulls. A database D is a finite instance that contains only constants. A homomorphism is a substitution h : C [ N [ V ! C [ N [ V that is the identity on C and that maps N to C [ N. A conjunctive query (CQ) q has the form 9Y (X; Y), where (X; Y) is a conjunction of atoms without nulls. The answer to q over an instance I, denoted q(I), is the set of all tuples t over C for which there is a homomorphism h such that h( (X; Y)) I and h(X) = t. A Boolean CQ (BCQ) q is a CQ 9Y (Y), i.e., all variables are existentially quantified; q is true over I, denoted I j= q, if q(I) 6= ;, i.e., there is a homomorphism h with h( (Y)) I.

Dependencies. A tuple-generating dependency (TGD) is a first-order formula

8X8Y '(X; Y) ! 9Z p(X; Z), where X [ Y [ Z V, '(X; Y) is a conjunction of atoms, and p(X; Z) is an atom, all without nulls. An instance I satisfies , written I j= , if the following holds: whenever there exists a homomorphism h such that h('(X; Y)) I, then there exists h0 hjX, where hjX is the restriction of h on X, such that h0(p(X; Z)) 2 I. A negative constraint (NC) is a first-order formula 8X '(X) ! ?, where X V, '(X) is a conjunction of atoms without nulls and ? denotes the truth constant false. An instance I satisfies , written I j= , if there is no homomorphism h such that h('(X)) I. Given a set of TGDs and NCs, I satisfies , written I j= , if I satisfies each TGD and NC of . Given a class of TGDs C, we denote by C? the formalism obtained by combining C with arbitrary NCs. Finite sets of

TGDs and NCs are also called programs, and TGDs are also called existential rules.

Knowledge Bases. A knowledge base is a pair (D; ), where D is a database, and is a program. For programs , T and NC are the subsets of containing the TGDs and NCs of , respectively. The set of models of KB = (D; ), denoted mods(KB ), is the set of instances fI j I D ^ I j= g. We say that KB is consistent, if mods(KB ) 6= ;, otherwise KB is inconsistent. The answer to a CQ q relative to KB is the set of tuples ans(q; KB ) = Tfq(I) j I 2 mods(KB )g. The answer to a BCQ q is true, denoted KB j= q, if ans(q; KB ) 6= ;. The decision version of the CQ answering problem is as follows: given a knowledge base KB , a CQ q, and a tuple of constants t, decide whether t 2 ans(q; KB ). Since CQ answering can be reduced in LOGSPACE to BCQ answering, we focus on BCQs. The combined complexity of BCQ answering considers the database, the set of dependencies, and the query as part of the input. The bounded-arity combined (or ba-combined) complexity assumes that the arity of the underlying schema is bounded by an integer constant. The fixed-program combined (or fp-combined) complexity considers the sets of TGDs and NCs as fixed; the data complexity also assumes the query fixed.

The Datalog languages that we consider to guarantee decidability are among the most frequently analyzed in the literature, namely, linear (L) [ 6 ], guarded (G) [ 5 ], sticky (S) [ 7 ], and acyclic TGDs (A), along with their “weak” (proper) generalizations weakly guarded (WG) [ 5 ], weakly sticky (WS) [ 7 ], and weakly acyclic TGDs (WA) [ 9 ], as well as their “full” (proper) restrictions linear full (LF), guarded full (GF), sticky full (SF), and acyclic full TGDs (AF), respectively, and full (i.e., existential-free) TGDs (F) in general. We also recall the following further inclusions: L G, F WA WS, and

F WG. We refer to, e.g., [8] for a more detailed overview and complexity results.

3

Approximate Inconsistency Semantics

We now recall three prominent inconsistency-tolerant semantics for ontology-based

query answering, namely, the ABox repair (AR) semantics and its approximation by the intersection of repairs (IAR) and the intersection of closed repairs (ICR) semantics [ 12,2 ]; all three are based on the notion of repair, which is a maximal consistent subset of the given database. Furthermore, we newly define generalized repair variants [ 8 ] of the two intersection-based approximate repair semantics.

Classically, errors leading to inconsistencies are assumed to be only in the database,

and not in the ontology. [ 8 ] have introduced the generalized inconsistency semantics allowing for errors also in the ontology, and for parts of the database and the ontology to be without errors. More specifically, for a knowledge base (D; ), the generalized semantics allows also (i) to minimally remove TGDs from , and (ii) to partition both D and into a hard and a soft part of non-removable and removable elements, respectively.

The so partitioned database (resp., program) is called flexible database (resp., program).

A flexible database is a pair (Dh; Ds) of databases, called the hard and soft database, respectively. A flexible program is a pair ( h; s) consisting of a finite set h of TGDs and NCs and a finite set s of TGDs, called the hard and soft program, respectively.

A flexible knowledge base is a pair ((Dh; Ds); ( h; s)), where (Dh; Ds) is a flexible

database, and ( h; s) is a flexible program. Note that a (standard) knowledge base (D; ) is a special case of a flexible one ((Dh; Ds); ( h; s)), where Dh = ;, Ds = D, h = , and s = ;. Below, we provide definitions for flexible knowledge bases that generalize the ones for (standard) knowledge bases.

For knowledge bases KB 0 = (D0; 0) and KB 00 = (D00; 00), we write KB 0 KB 00, if D0 D00 and 0 00. A selection of a flexible knowledge base ((Dh; Ds); ( h; s)) is a knowledge base (D0; 0) such that Dh D0 (Dh[Ds) and h 0 ( h[ s).

A repair of a flexible knowledge base FKB is an inclusion-maximal consistent selection

of FKB . We denote by Rep(FKB ) the set of all repairs of FKB . Notice that for (standard) knowledge bases, a repair is usually defined as a maximal consistent subset of the database. However, when a flexible knowledge base models a standard one (i.e., Dh = ; and s = ;), the definition above coincides with the classical one.

Example 1. Consider the flexible database (Dh;Ds) given by

Dh = fPostdoc(p); Researcher (p); leaderOf (p0; g0)g and Ds = fProf (p); leaderOf (p; g)g; asserting that p is a postdoc, a researcher, a professor, and the leader of the research group g, and that p0 is the leader of g0. Consider also the flexible program ( h; s) defined as h = fProf (X) ! Researcher (X);

Postdoc(X) ! Researcher (X); Prof (X); Postdoc(X) ! ?; leaderOf (X; Y ) ! Group(Y )g; s = fleaderOf (X; Y ) ! Prof (X)g; expressing that professors and postdocs are researchers, professors and postdocs form disjoint sets, and leaderOf has Prof as domain and Group as range. It is easy to see that mods(D; ) = ;, since p violates the disjointness constraint.

The flexible knowledge base ((Dh; Ds); ( h; s)) has two repairs (D0; 0) and

(D00; 00):

D0 = Dh [ fleaderOf (p; g)g ; D00 = Dh ; 0 = 00 = h ; h [ s : In both, the atom Prof (p) is removed; in the first one, also the rule leaderOf (X; Y ) !

Prof (X) is removed, while in the second one, the atom leaderOf (p; g) is removed.

We now define the inconsistency-tolerant semantics considered. For a knowledge

base KB = (D; ), the closure Cn(KB ) of KB is the set of all ground atoms, built from constants in D and , entailed by D and the TGDs of . Let FKB be a flexible knowledge base, and let q be a BCQ.

– FKB entails q under the generalized ABox repair (GAR) semantics, if, for all

KB 0 2 Rep(FKB ), KB 0 j= q. – FKB entails q under the generalized intersection of repairs (GIAR) semantics, if (D ; ) j= q, where D = TfD0 j (D0; 0) 2 Rep(FKB )g and = Tf 0 j (D0; 0) 2 Rep(FKB )g.

In the definition above, observe that if FKB is a standard knowledge base, then = , and thus the definition above generalizes the AR, IAR, and ICR semantics for standard knowledge bases to the case of flexible knowledge bases. We talk of BCQ answering under the GAR, GIAR, and GICR semantics when flexible knowledge bases can be arbitrary, and we talk of BCQ answering under the AR, IAR, and ICR semantics when flexible knowledge bases model standard knowledge bases (i.e., Dh = ; and s = ;). 4

Complexity Results

We give a precise picture of the complexity of BCQ answering from existential rules

under the IAR, ICR, GIAR, and GICR semantics, which is summarized in Fig. 1. 4.1

Membership Results

IAR semantics. The following theorem proves all upper bounds equal to and above

co-NP in Fig. 1, left side, excluding the 2P memberships.

Theorem 1. If BCQ answering from databases under programs over some Datalog

language L is in C in the data (resp., fp-combined, ba-combined, and combined) complexity, then IAR-BCQ answering from databases under programs over L is in coNPC in the data (resp., fp-combined, ba-combined, and combined) complexity.

Consider now the Datalog fragments whose BCQ answering in the data complexity

is in AC0, i.e., L?, S?, A?, LF?, AF?, and SF?. In such cases, the following theorem states the upper bound in the fp-combined complexity.

Theorem 2. IAR-BCQ answering for L?, S?, and A? (and LF?, AF?, and SF?) is in

NP in the fp-combined complexity.

The following theorem proves all 2P upper bounds in Fig. 1, left side. Theorem 3. IAR-BCQ answering for WS? and G? (and WA?, F?, and GF?) is in 2P in the fp-combined complexity.

ICR semantics. The following theorem proves all upper bounds in Fig. 1, right side,

including the PNEXP = co-NPNEXP membership for A?, excluding memberships in 2P and the combined complexity.

Theorem 4. If BCQ answering from databases under programs over some Datalog

language L is in C in the data (resp., fp- and ba-combined) complexity, then ICR-BCQ answering from databases under programs over L is in co-NPC in the data (resp., fpand ba-combined) complexity.

BCQ answering under the ICR semantics for all the considered Datalog fragments

but WG? is in 2P in the fp-combined complexity.

Theorem 5. ICR-BCQ answering for all the considered Datalog fragments but WG? is in 2P in the fp-combined complexity.

As for the combined complexity, we get the following theorem.

Theorem 6. If BCQ answering from databases under programs over some Datalog

language L is in the deterministic complexity class C in the combined complexity, then ICR-BCQ answering from databases under programs over L is in PSPACE C in the combined complexity.

The membership results above can be extended to the generalized semantics case [15].

4.2

Hardness Results

As BCQ answering under the IAR and ICR semantics for Datalog fragments L

coincides with BCQ answering for L when there are no inconsistencies, we immediately obtain hardness for all NP, PSPACE, EXP, and 2EXP entries in Fig. 1.

IAR semantics. Hardness for co-NP of BCQ answering under the IAR semantics in the

data complexity is shown by a reduction from deciding unsatisfiability of 3CNF formulas (UNSAT). It produces a knowledge base with a fixed GF? program and fixed query. This proves all open co-NP-hardness results in Fig. 1, left side.

Theorem 7. IAR-BCQ answering for GF? (and F?) is co-NP-hard in the data complexity.

We can show that IAR-BCQ answering for A? is PNEXP-hard in the ba-combined complexity, proving all PNEXP-hardness results in Fig. 1, left side. Intuitively, the reduction for the PNEXP-hardness proof in [ 8 ] for AR-BCQ answering for A? in the ba-combined complexity is turned into a PNEXP-hardness proof for IAR-BCQ answering in this case. Theorem 8. IAR-BCQ answering for A? is PNEXP-hard in the ba-combined complexity.

BCQ answering under IAR semantics for GF? (and thus also for F?, G?, WA?, and WS?) in the fp-combined complexity can be shown to be 2P-hard via a reduction from the 2P-complete problem COMP-SAT: Given two sets A and B of Boolean formulas, decide whether A contains more satisfiable formulas than B [ 13,14 ].

Theorem 9. IAR-BCQ answering for GF? (and F?, G?, WA?, and WS?) is in the fp-combined complexity. 2P-hard

ICR semantics. ICR-BCQ answering in the data complexity is co-NP-hard by a reduction from UNSAT. This proves all open co-NP-hardness results in Fig. 1, right side.

Theorem 10. ICR-BCQ answering for LF?, AF?, and SF? (and GF?, F?, and A?) is co-NP-hard in the data complexity.

BCQ answering under ICR semantics is 2P-hard in the fp-combined complexity, by a reduction from COMP-SAT, for all remaining entries in Fig. 1, right side, but for WG?.

Theorem 11. ICR-BCQ answering in the fp-combined complexity is

the considered Datalog fragments. 2P-hard for all

BCQ answering under the ICR semantics for AF? (and thus also for F?) is 2P-hard in the ba-combined complexity, by a reduction from NQBF 2;8, which is a variant of quantified Boolean formulas with two quantifiers starting with a universal one [ 10,21 ].

Theorem 12. ICR-BCQ answering is

AF? (and F?).

2P-hard in the ba-combined complexity for

The following result shows that ICR-BCQ answering for A? is PNEXP-hard in the ba-combined complexity, proving all PNEXP-hardness results in Fig. 1, right side. Theorem 13. ICR-BCQ answering for A? is PNEXP-hard in the ba-combined complexity.

The following shows all 2P-hardness results in Fig. 1, right side. The results in Fig. 1, left side, are proved similarly. 2P-hardness Theorem 14. ICR-BCQ answering for L?, LF?, AF?, S?, SF?, F?, and GF? is hard in the ba-combined complexity. 2P

Also for the hardness results, it is possible to show that they extend to the generalized semantics case [15].

5

Summary and Outlook

We have given a precise picture of the complexity of BCQ answering under different

approximate inconsistency-tolerant semantics for the most popular Datalog languages and complexity measures. In addition to the standard setting, we have also considered the more general setting where also ontological rules may be removed.

Future research lines include considering other classes of existential rules and to

define other semantics for inconsistency-tolerant ontological query answering. Another interesting direction for future work is to carry out a complexity analysis of the local generalized semantics [ 8 ]. Also, a more fine-grained way to analyze the complexity of query answering would be a non-uniform approach, looking at the complexity of a single ontology or a single ontology-mediated query (see, e.g., [ 11 ]).

Acknowledgements. This work was supported by The Alan Turing Institute under the

UK EPSRC grant EP/N510129/1, and by the EPSRC grants EP/R013667/1, EP/L012138/1, and EP/M025268/1.

References

1. Marcelo Arenas , Leopoldo E. Bertossi , and Jan Chomicki . Consistent query answers in inconsistent databases . In Proc. PODS , pages 68 - 79 , 1999 .

2. Meghyn Bienvenu . On the complexity of consistent query answering in the presence of simple ontologies . In Proc. AAAI , pages 705 - 711 , 2012 .

3. Meghyn Bienvenu , Camille Bourgaux, and François Goasdoué . Querying inconsistent description logic knowledge bases under preferred repair semantics . In Proc. AAAI , pages 996 - 1002 , 2014 .

4. Meghyn Bienvenu and Riccardo Rosati . Tractable approximations of consistent query answering for robust ontology-based data access . In Proc. IJCAI , pages 775 - 781 , 2013 .

5. Andrea Calì , Georg Gottlob, and Michael Kifer . Taming the infinite chase: Query answering under expressive relational constraints . J. Artif. Intell. Res. , 48 : 115 - 174 , 2013 .

6. Andrea Calì , Georg Gottlob, and Thomas Lukasiewicz . A general Datalog-based framework for tractable query answering over ontologies . J. Web Sem ., 14 : 57 - 83 , 2012 .

7. Andrea Calì , Georg Gottlob, and Andreas Pieris . Towards more expressive ontology languages: The query answering problem . Artif . Intell., 193 : 87 - 128 , 2012 .

8. Thomas Eiter , Thomas Lukasiewicz, and Livia Predoiu . Generalized consistent query answering under existential rules . In Proc. KR , pages 359 - 368 , 2016 .

9. Ronald Fagin , Phokion G. Kolaitis, Renée J . Miller , and Lucian Popa . Data exchange: semantics and query answering . Theor. Comput. Sci. , 336 ( 1 ): 89 - 124 , 2005 .

10. Gianluigi Greco , Enrico Malizia, Luigi Palopoli, and Francesco Scarcello . On the complexity of core, kernel, and bargaining set . Artificial Intelligence , 175 ( 12 -13): 1877 - 1910 , 2011 .

11. André Hernich , Carsten Lutz, Fabio Papacchini, and Frank Wolter . Dichotomies in ontologymediated querying with the guarded fragment . In Proc. PODS , pages 185 - 199 , 2017 .

12. Domenico Lembo , Maurizio Lenzerini, Riccardo Rosati, Marco Ruzzi, and Domenico Fabio Savo. Inconsistency-tolerant semantics for description logics . In Proc. RR , pages 103 - 117 , 2010 .

13. Thomas Lukasiewicz and Enrico Malizia . On the complexity of mCP-nets . In Proc. AAAI , pages 558 - 564 , 2016 .

14. Thomas Lukasiewicz and Enrico Malizia . A novel characterization of the complexity class kP based on counting and comparison . Theor. Comput. Sci. , 694 : 21 - 33 , 2017 .

15. Thomas Lukasiewicz , Enrico Malizia, and Cristian Molinaro . Complexity of approximate query answering under inconsistency in datalog+/- . In International Joint Conference on Artificial Intelligence (IJCAI) , pages 1921 - 1927 , 2018 .

16. Thomas Lukasiewicz , Maria Vanina Martinez, Andreas Pieris, and Gerardo I. Simari. From classical to consistent query answering under existential rules . In Proc. AAAI , pages 1546 - 1552 , 2015 .

17. Thomas Lukasiewicz , Maria Vanina Martinez, and Gerardo I. Simari . Inconsistency handling in Datalog+/- ontologies. In Proc. ECAI , pages 558 - 563 , 2012 .

18. Thomas Lukasiewicz , Maria Vanina Martinez, and Gerardo I. Simari . Inconsistency-tolerant query rewriting for linear Datalog+/- . In Proc. Datalog 2.0 , pages 123 - 134 , 2012 .

19. Thomas Lukasiewicz , Maria Vanina Martinez, and Gerardo I. Simari. Complexity of inconsistency-tolerant query answering in Datalog+/- . In Proc. OTM , pages 488 - 500 , 2013 .

20. Riccardo Rosati . On the complexity of dealing with inconsistency in description logic ontologies . In Proc. IJCAI , pages 1057 - 1062 , 2011 .

21. Marcus Schaefer . Graph Ramsey theory and the polynomial hierarchy . Journal of Computer and System Sciences , 62 ( 2 ): 290 - 322 , 2001 .