# query_answering_in_ontologies_under_preference_rankings__ef673491.pdf

Query Answering in Ontologies under Preference Rankings

Ismail Ilkan Ceylan1, Thomas Lukasiewicz2, Rafael Pe naloza3, Oana Tifrea-Marciuska4

1Theoretical Computer Science, Technische Universit at Dresden, Germany 2Department of Computer Science, University of Oxford, UK 3KRDB Research Centre, Free University of Bozen-Bolzano, Italy 4The Alan Turing Institute, London, UK

We present an ontological framework, based on preference rankings, that allows users to express their preferences between the knowledge explicitly available in the ontology. Using this formalism, the answers for a given query to an ontology can be ranked by preference, allowing users to retrieve the most preferred answers only. We provide a host of complexity results for the main computational tasks in this framework, for the general case, and for EL and DL-Litecore as underlying ontology languages.

1 Introduction

Description logics (DLs) [Baader et al., 2007] are a family of knowledge representation formalisms that have been successfully used for modeling many real-world domains. Important recent applications include semantic search on the Web and ontology-based access to data, including Big Data [Giese et al., 2015]. One crucial reasoning task for the above areas and other knowledge domains is conjunctive query (CQ) answering, which corresponds to computing all tuples of individuals that satisfy some conceptual pattern. One of the issues related to CQ answering over ontologies is to be able to manage the large number of potential answers in a structured manner. Since in standard ontological CQ answering, all answers are qualitatively indistinguishable, it is, e.g., impossible to filter the most preferred answers to a given CQ. It is thus important to extend CQ answering over ontologies with preference criteria, such as preference rankings.

Example 1. A preference ranking may encode Bob s preferences over sources of information on the Web: Bob is not a fan of blogs; so, he prefers any non-blog source of information over blogs. But when reading blogs, Bob wants more subjective opinions, so, blogs written by a non-specialist are preferred over blogs written by a specialist. If Bob reads information from a non-blog source written by a non-specialist, then he prefers popular sources over non-popular ones, otherwise, non-popular sources over popular ones.

In this paper, preference modeling is done via very general preference rankings over a collection of possible choices, with the only restriction (for our computational complexity results) that the rank of each choice is computable in

polynomial time. Indeed, many rankings in information retrieval (IR) have this property (see, e.g., [Joachims, 2002]). Thus, the approach in this paper actually provides very general results for combining DLs with IR rankings. We consider preferences that are directly associated with the axioms and facts in a knowledge base. Such absolute rankings are actually quite common in practice, in particular, they are broadly used in Web applications; e.g., Google s Page Rank is also directly associated with Web pages. We implement this idea by annotating every piece of knowledge with a context, which intuitively describes the situations in which this knowledge holds, and by defining a unique preference ranking over these contexts. These preferences are then naturally extended to answers to CQs, allowing users to retrieve only the most preferred answers. Example 2. An ontological knowledge base extracted from information sources on the Web can be coupled with Bob s preferences in Example 1 by annotating ontological axioms with events, over which we define a suitable preference ranking. Thus, a travel ontology can be associated with contexts, e.g., to express that popular blogs (b p) recommend that an itinerary with a wine destination would work well with another wine destination, and that specialist blogs (b s) say that Sicily is a wine destination, each with a suitable rank. Then, the answers Florence , Sicily , and Bordeaux for an ontological query asking for wine and spa destination may then be ranked as 1, 0.35, and 0, respectively, depending on the underlying preference ranking.

Annotating the knowledge with contexts has been previously used successfully in, e.g., probabilistic logic programming [Poole, 1997] and probabilistic databases [Suciu et al., 2011]. The main benefit of using contexts, rather than providing a preference ranking directly to the knowledge is that they provide an easily accessible interface to the knowledge. Thus, if different users want to express different preferences, e.g., related to different query circumstances, then they only need to provide a new preference ranking over the same contexts, without modifying the underlying knowledge base. This paper s main contributions are briefly as follows: We propose ranked ontologies as a novel approach to modeling the preferences of a user relative to the knowledge in an ontology. They are based on unique preference rankings, which extend to query answers, so that only the most preferred answers are given, ordered via their ranks.

Proceedings of the Twenty-Sixth International Joint Conference on Artificial Intelligence (IJCAI-17)

We then provide generic complexity results for deciding k most preferred answers to a CQ for different types of complexities. We also provide complexity results for this problem for the lightweight DLs EL and DL-Litecore, which include especially also tractability and first-order rewritability results. We also give generic complexity results for other important reasoning problems, namely, for deciding k most preferred conditional answers, for deciding a lower bound for the preference degree of a Boolean CQ (BCQ), and for deciding k most preferred worlds. Moreover, we give complexity results for these problems for EL and DL-Litecore, which include further tractability and first-order rewritability results.

The rest of this paper is organized as follows. Section 2 defines preference rankings and recalls the basic concepts of description logics. In Section 3, we introduce ranked ontologies. Section 4 provides alternative characterizations for ranked ontologies and the ranks of BCQs. In Section 5, we define the main reasoning tasks for these ontologies, while Section 6 provides tight complexity results for these tasks. We conclude with a discussion on related work, a summary of the main results, and an outlook on future work. Due to space limitations, detailed proofs of all results in this paper will be given in an extended paper.

2 Preliminaries

In this section, we define preference rankings and briefly recall description logics (DLs) [Baader et al., 2007]. Preference Rankings. Given a nonempty finite set V of Boolean variables, a valuation W of V assigns to each X V a truth value among true and false, also abbreviated as X and X, respectively. A valuation U for a set of variables U V assigns to each X U a truth value among true and false. We denote by Ωthe set of all valuations of V . A preference ranking over Ωis a function rank: Ω [0, 1], which is extended to any Γ Ωby rank(Γ) = supω Γ rank(ω), where sup is the supremum (i.e., the least upper bound). Intuitively, rank(Γ) represents the degree of preference in Γ. Here, we only consider rankings on valuations where each rank is computable in polynomial time, which is a property that is shared by many rankings in IR (see, e.g., [Joachims, 2002]). Such a polynomial preference ranking is also naturally defined via possibilistic networks (PNs), which compactly encode possibility distributions via (possibilistic) independencies encoded in a directed acyclic graph (DAG) [Benferhat et al., 1999] in a similar way as Bayesian networks [Pearl, 1988; Darwiche, 2009] compactly encode probability distributions. Note that despite these similarities, PNs are semantically and computationally very different from Bayesian networks (see also Section 7). Note also that PNs are only one example of encoding polynomial preference rankings.

Example 3. A possibilistic network (PN) P = (G, Φ) over V consists of a DAG G = (V, E) and a set Φ containing a conditional possibility distribution rank P(x | pa(x)) for every x V given pa(x), where pa(x) denotes the parents of x in G (i.e., the immediate predecessors of x in G). Note that each conditional possibility distribution rank P(x | pa(x)) consists of one conditional possibility value rank P(x | pa(x))

for each pair of valuations x and pa(x) of x and pa(x), respectively. Such a PN defines a unique (joint) possibility distribution over the valuations W of V (where x and pa(x) are matching valuation of x and pa(x), respectively): rank P(W) = Q x V rank P(x | pa(x)). For example, Figure 1 shows a possibilistic network P0 over the variables V0 = {b, s, p}. The tables associated with each node contain the conditional possibility distributions for this node given its parents. For example, the node b is associated with an unconditional possibility distribution, since it has no parents, while p is associated with a distribution conditional on b and s. Here, the possibility of, e.g., the valuation {b, s, p} (i.e., b = s= true and p = false) is rank P0({b}) rank P0({s}|{b}) rank P0({ p}|{b, s}) = 0.7 0.5 1 = 0.35.

Note also that PNs can be used to compactly encode the conditional preferences of a user (i.e., statements of the form if x holds, then y is preferred over y ) over a finite set of events [Ben Amor et al., 2014]. Intuitively, for each conditional event, the user provides a possibility degree (i.e., a rank) that is proportional to the user s preference of its occurrence. The joint possibility distribution then combines the ranks of all conditional events to a ranking over the valuations of the variables in V . The following example shows that the above possibilistic network from Figure 1 in fact represents the conditional preferences described in Example 1. For further (and larger) examples of how finite sets of conditional preferences can be encoded as possibilistic networks, see, e.g., [Ben Amor et al., 2014; Amor et al., 2015].

Example 4. The PN P0 from Figure 1 expresses the preferences of Bob over sources of information on the Web when planning his trips. Bob is not a fan of blogs, therefore, he (unconditionally) prefers any other source of information than blogs ( b) over blogs (b). Bob wants more subjective opinions when reading blogs (b), therefore, he prefers a blog written by a non-specialist ( s) over a blog written by a specialist (s). Note that these are examples of conditional preferences, where the order between s and s depends on the choice made for the evaluation of the variable b before. If Bob reads information not from a blog written by a non-specialist ( b s), then he prefers a popular source (p) over a nonpopular source ( p), otherwise, the non-popular source ( p) is preferred over popular ones (p). Overall, e.g., {b, s, p} is preferred over {b, s, p} (since 0.7 0.5 1 > 0.7 0.5 0.5).

Description Logics. We briefly sketch some basics in description logics (DLs) [Baader et al., 2007]. In DLs, the knowledge of an application domain is represented through an ontology O, which is a finite set of axioms that restrict the possible interpretations that can be given to the terms used. Ontologies are usually partitioned into a set of terminological axioms (called TBox) that encode the relations between the different terms used in the knowledge domain, and a set of assertional axioms (called ABox) that express the knowledge about specific individuals. The semantics of DLs is given via interpretations I = ( I, I), where I is a nonempty set, called domain, and I is the interpretation function that describes how the terms of the ontology are interpreted. A satisfaction relation |= defines which interpretations I satisfy which axioms A, denoted I |= A. We say that I satisfies (or

Proceedings of the Twenty-Sixth International Joint Conference on Artificial Intelligence (IJCAI-17)

s s b 0.5 1 b 1 0.3

p p b s 0.5 1 b s 1 1 b s 0.6 1 b s 1 0

Figure 1: Preference ranking P0 encoded via a possibilistic network (PN) over V0 = {b, s, p}.

is a model of) an ontology O, if I satisfies all axioms in O. An important reasoning task for DLs is conjunctive query answering. A conjunctive query (CQ) q(x) is of the form y Vn i=1 pi(x, y), where the pi(x, y) s are atoms over individual names and two disjoint sets of variables x and y. A Boolean CQ (BCQ) q is a CQ of the form q(). An answer θ for a CQ q(x) to an ontology O maps each variable in x to an individual name such that q(xθ) holds in all models of O. The answer for a BCQ q to O is true (resp., false), denoted O |= q, if θ = is an (resp., not an) answer for q to O.

3 Ranked Ontologies

In this section, we introduce ranked ontologies, which are a novel combination of preference rankings with ontologies. We consider an arbitrary description logic (DL) [Baader et al., 2007] as underlying ontology language. Syntax. A ranked ontology associates every axiom in an ontology with a context, encoded by a propositional formula over a set of variables V , which intuitively describes the situation in which the axiom is guaranteed to hold. Additionally, a preference ranking over these contexts is given. In the sequel, let V be a finite nonempty set of Boolean variables, and L be a DL. A V -context ϕ is a propositional formula over V . A V -axiom λ : ϕ in L consists of an axiom λ in L and a V -context ϕ. A V -ontology in L is a finite set of V -axioms in L. A ranked ontology K = (P, O) in L over V consists of a preference ranking P over V and a V -ontology O in L. We often omit the prefix V . As in the classical case, V -ontologies are partitioned into a (V -)TBox and a (V -)ABox. Note that classical ontologies are a special case of V -ontologies, where all V -axioms are of the form λ : with denoting true. The restriction of a ranked ontology K = (P, O) to a valuation W of the variables in V is the classical ontology OW = {λ | λ : ϕ O, W |= ϕ} in L.

Example 5. A ranked ontology K0 = (P0, O0) is given by the preference ranking P0 encoded in the PN of Figure 1 and O0 below. Intuitively, it says, e.g., that popular blogs (b p) recommend that an itinerary with a wine destination would work well with another wine destination, and that specialist blogs (b s) say that Sicily is a wine destination:

O0 = { works Well With.Wine Dest Wine Dest: b p , Wine Dest Relax Dest: b s , works Well With.Relax Dest Spa Dest: s , Relax Dest Spa Dest: p } { Spa Dest(florence): s , Wine Dest(sicily): b s , Wine Dest(bordeaux): b s }.

Semantics. We next extend the classical interpretations of L to additionally evaluate contexts. A contextual interpretation is a pair (I, W), where I = ( I, I) is a classical interpretation for L, and W is a valuation of V . We say that (I, W) satisfies (or is a model of) the axiom λ : ϕ , denoted (I, W) |= λ : ϕ , if either (a) W |= ϕ, or (b) I |= λ. Notice that (a) or (b) is equivalent to W |= ϕ implies I |= λ : intuitively, λ is only required to hold within the context ϕ. We say that (I, W) satisfies (or is a model of) a V -ontology O over L, denoted (I, W) |= O, if it satisfies all axioms in O. We now define ranked interpretations over contextual ones, and the satisfaction of ranked ontologies K = (P, O) in them. Intuitively, the contexts connect the preference ranking P to the V -ontology O and thus define a set of ranked interpretations represented by K. Formally, a ranked interpretation P = (J, rank) consists of a finite set of contextual interpretations J and a ranking rank over I (which assigns a rank rank((I, W)) to each (I, W) J). We say that P is a model of a V -ontology O, if every (I, W) J satisfies O; it is a model of P, if for each valuation W, max(I,W) J rank((I, W)) = rank P(W). We say P is a model of K = (P, O), denoted P |= K, if it is a model of O and P. We say K is consistent, if it has at least one model.

Example 6. Consider again the ranked ontology K0 = (P0, O0) of Example 5. Let I0 = ({d, e, f}, I0) be a DL interpretation with florence I0 = d, sicily I0 = e, bordeaux I0 = f, Wine Dest I0 = Relax Dest I0 = {d, e, f}, Spa Dest I0= , and works Well With I0= . Then, the contextual interpretation (I0, { b, s, p}) is a model of O0, since florence I Wine Dest I and Wine Dest I Relax Dest I, while (I0, { b, s, p}) is not a model of O0, as it does not satisfy Relax Dest Spa Dest: p . A ranked interpretation P = (J, rank) that satisfies the KB K0 is then given by the singleton set J = {(I0, { b, s, p})} with rank((I0, { b, s, p})) = 0.6.

We next define the rank of BCQs q under ranked ontologies K = (P, O), which is intuitively the most strict rank of q under all ranked interpretations P = (I, rank) that satisfy K. Formally, the rank of q under P = (I, rank), denoted rank P(q), is defined by rank P(q) = max(I,W) I, I|=q rank((I, W)), while the rank of q under K is then defined by: rank K(q) = inf P|=K rank P(q). In general, we are not only interested in the rank of a given BCQ, but also in its rank given some partial knowledge of the current context. Conversely, given a BCQ, we are also interested in the most preferred source that entails it. For these two tasks, we extend ranks to contexts. The rank of q and a context ϕ under P = (I, rank), denoted rank P(q ϕ), is defined as follows: rank P(q ϕ) = max(I,W) I, I|=q, W|=ϕ rank((I, W)), while the rank of q and ϕ under K, denoted rank K(q ϕ), is defined by rank K(q ϕ) = inf P|=K rank P(q ϕ). We define the conditional rank of a query given a context, and of a context given a query, using the standard product conditioning rule, as follows:

rank K(q|ϕ) = rank K(q ϕ) / rank K(ϕ), if rank K(ϕ) > 0,

rank K(ϕ|q) = rank K(q ϕ) / rank K(q), if rank K(q) > 0.

Proceedings of the Twenty-Sixth International Joint Conference on Artificial Intelligence (IJCAI-17)

4 Semantic Results We now provide alternative semantic characterizations for the consistency of ranked ontologies and for the rank of BCQs and contexts in consistent ranked ontologies. Consistency. The following informally shows that a ranked ontology K over V is consistent iff, for every valuation W of V with positive rank, the restriction of K to W is consistent. Theorem 1. A ranked ontology K = (P, O) in L over V is consistent iff, for every valuation W of V , if rank P(W) > 0, then OW is consistent. Thus, the consistency of ranked ontologies in L can be reduced to the consistency of classical ontologies in L. As every ontology in EL is consistent [Baader et al., 2005], the theorem implies that every ranked ontology in EL is consistent. Example 7. Consider the ranked ontology K1 = (P0, O1) built in DL-Litecore, where P0 is defined by the PN from Figure 1, and O1 = { Wine Dest Wine Dest: b p , Wine Dest(florence): s }. For W1 = { b, s, p}, it holds that rank P0(W1) = 1 > 0 (see Figure 1 above). Moreover, the ontology OW1 = {Wine Dest Wine Dest, Wine Dest(florence)} is inconsistent. Hence, K1 is also inconsistent. However, for O2 = { Wine Dest Wine Dest: b p , Wine Dest(florence): s }, the ranked ontology K2 = (P0, O2) is consistent, although for W2 = { b, s, p}, the restriction OW2 is inconsistent. Indeed, for the DL-Lite interpretation I2 = ({d}, I2), where Wine Dest I2 = and florence I2 = d, the ranked interpretation P = (J, rank) given by J = {(I2, W) | W = W2}, and for all W = W2, rank((I2, W)) = rank P0(W) satisfies K2.

Rank. Informally, the next theorem shows that, for consistent ranked ontologies K, the rank of a BCQ q can be determined by looking at the restrictions of K that entail q, and that this result can also be extended to contexts. Theorem 2. For every consistent ranked ontology K = (P, O) in L over V , BCQ q, and context ϕ over V :

rank K(q) = max OW |=q rank P(W), and rank K(q ϕ) = max W|=ϕ, OW |=q rank P(W).

Note that the precondition that the ranked ontology K is consistent is fundamental for this theorem to hold. Consider, e.g., the inconsistent ranked ontology K1 from Example 7, and let q1 = {A(b)}. Then, by definition, since K1 has no models, rank K1(q1) = 1 (since it is the infimum of an empty subset of [0, 1]). However, max OW|=q1 rank P0(W) = 0. A direct consequence of Theorem 2 is that there are finitely many (at most 2|V | + 2) possible ranks: the rank of a BCQ q corresponds to rank P(W) for some valuation W of V , or 0 if q is not entailed by any restriction OW, or 1, if the ranked ontology is inconsistent.

5 Reasoning Tasks In this section, we formally define the main reasoning tasks for ranked ontologies, namely deciding whether the rank of a BCQ is above a threshold (called p-entailment), top-k CQ answering, top-k conditional CQ answering, and computing the k most preferred worlds for a BCQ.

Table 1: Most preferred answers (resp., worlds) for the CQ q2(χ) (resp., BCQ q2(χθ0)) to K0 from Example 8.

Worlds θ0 θ1 θ2 rank P0(W) rank P0(W|q2(χθ0))

W0 = {b, s, p} 0.175 - W1 = {b, s, p} 0.35 0.35 W2 = {b, s, p} 0.7 - W3 = {b, s, p} 0.7 - W4 = { b, s, p} 0.6 - W5 = { b, s, p} 1 1 W6 = { b, s, p} 0.3 - W7 = { b, s, p} 0 -

p-Entailment. The p-entailment problem is informally the problem of deciding whether the entailed rank of a BCQ under a ranked ontology is above a given threshold. Formally, given a ranked ontology K, a BCQ q, a context ϕ, and some p (0, 1], decide whether rank K(q ϕ) p holds.

Top-k Answers. As for more general CQs q(x) to ranked ontologies K = (P, O), since P represents preferences, we are especially interested in most preferred answers, which are the ones with highest ranks. A top-k answer, where k N is fixed, for q(x) to K is a tuple (θ1, . . . , θk) of different answers θi for q(x) to K such that either (a) θ1, . . . , θl with l k are the only answers for q(x) to K, or (b) the following conditions i) and ii) hold: i) for all i, 1 i < k: rank K(q(xθi)) rank K(q(xθi+1)); ii) for no other answer θ: rank K(q(xθk)) < rank K(q(xθ)). As different answers may have the same rank, top-k answers are not unique, i.e., there may be different tuples satisfying the properties of a top-k answer, and they may also be empty.

Top-k Conditional Answers. In some cases, we have some information about the context in which we are currently. Thus, it is also important to find the answers that are most preferred, given a context ϕ. A top-k answer, where k N is fixed, for q(x) under a context ϕ to K is a tuple (θ1, . . . , θl) of l {0, . . . , k} different answers θi for q(x) to K such that either (a) θ1, . . . , θl with l k are the only answers for q(x) to K, or (b) the following conditions i) and ii) hold: i) for all i, 1 i<k: rank K(q(xθi)|ϕ) rank K(q(xθi+1)|ϕ); ii) for no other answer θ: rank K(q(xθk)|ϕ)<rank K(q(xθ)|ϕ). As rank K(ϕ) is a constant factor for all rank K(q(xθi)|ϕ), it is sufficient to compare the ranks of all rank K(q(xθi) ϕ).

k Most Preferred Worlds. Similarly to finding k most preferred answers to a CQ, we may also be interested in finding k most preferred valuations for a BCQ. Intuitively, they are the best k sources for a BCQ, i.e., they are the k most preferred arguments for justifying a BCQ. Given a BCQ q, a ranked ontology K over V , a fixed k N, and different propositional valuations Wi, 1 i k over V , we say that W1, . . . , Wk are k most preferred worlds for q to K, if i) and ii) hold:

i) for all i, 1 i < k: rank K(Wi|q) rank K(Wi+1|q);

ii) for no other valuation W: rank K(Wk|q)<rank K(W|q).

Example 8. Consider again the ranked ontology K0 = (P0, O0) of Example 5 and the CQ q2(χ) = Wine Dest(χ) Spa Dest(χ). Then, three possible answers for q2 to K0 exist: θ0 = {χ/florence}, θ1 = {χ/sicily}, and θ2 = {χ/bordeaux},

Proceedings of the Twenty-Sixth International Joint Conference on Artificial Intelligence (IJCAI-17)

Table 2: Complexity of the ranked extension of EL (all entries without in are completeness results).

Problem data KB ranking combined

p-entailment in P in P NP NP

top-k (conditional) answers in P in P p 2 p 2 k most preferred worlds in P in P CONP CONP

Table 3: Complexity of the ranked extension of DL-Litecore (all entries without in are completeness results).

Problem data KB ranking combined

p-entailment in AC0 NLOGSPACE NP NP

top-k (conditional) answers in AC0 in P p 2 p 2 k most preferred worlds in AC0 in co NLOGSPACE CONP CONP

having the ranks

rank P0(q2(χθ0)) = max {rank P0(W1), rank P0(W5)} = 1, rank P0(q2(χθ1)) = rank P0(W1) = 0.35, and rank P0(q2(χθ2)) = rank P0( ) = 0,

respectively; see Table 1. Note that θ2 has the rank 0, as K0 does not entail q2(χθ2) in any valuation. It is easy to see from the table that (θ0, θ1) is a top-2 answer, and that W5 and W1 are the two most preferred worlds for q2(χθ0).

6 Complexity Results

In this section, we provide complexity results for ranked ontologies, both generic ones and for the special cases of the lightweight DLs EL [Baader et al., 2005] and DL-Litecore [Calvanese et al., 2007; Artale et al., 2009]. As for the complexity of query answering in DLs, one usually considers some parts of the input as fixed. In particular, one speaks of the data (resp., KB) complexity when only the size of the ABox (resp., the whole ontology) is considered, and of the combined complexity when also the query is part of the input. Note that, in our framework, the ontology is enriched with a ranking, but the two are rather decoupled by the use of contexts. In fact, the size of the ranking does not usually grow proportionally in the size of the data/KB, i.e., the same annotations can be coupled with many axioms of the ontology. Therefore, the ranking is fixed in both the data and the KB complexity. We also consider the ranking complexity when only the size of the preference ranking is relevant. In the sequel, the combined complexity refers to the whole input, including the preference ranking. For an arbitrary but fixed DL L, we denote by Cd, Ck, and Cc, the data, KB, and combined complexity of BCQ answering in L, respectively. We recall that in EL, BCQ entailment is polynomial in the data and KB complexity, but NP-complete in the combined complexity [Rosati, 2007]; in DL-Litecore, these complexities are membership in AC0, NLOGSPACE-completeness, and NP-completeness, respectively [Artale et al., 2009]. The results for the ranked extensions of EL and DL-Litecore are summarized in Tables 2 and 3, respectively: reasoning in these DLs is in general tractable in the data and KB complexity, but intractable in the ranking and combined complexity.

p-Entailment. The following theorem provides complexity results for p-entailment; its proof is based on Theorem 2.

Theorem 3. The p-entailment problem for ranked ontologies in L is in Cd, Ck, and NPCc in the data, KB, and combined complexity, respectively, and is NP-complete in the ranking complexity. Furthermore, if Cc is contained in NP, then it is NP-complete in the combined complexity.

In particular, for ranked ontologies in EL, p-entailment is polynomial in the data and KB complexity, and NP-complete in the ranking and combined complexity. For DL-Litecore, this problem is in AC0, NLOGSPACE-complete, and NPcomplete in the respective complexities. Note that these complexity results do not necessarily hold for conditional p-entailments, i.e., deciding whether rank K(q|ϕ) p, which is in fact harder in the network complexity. Assuming that rank P(ϕ) > 0, we have rank K(q|ϕ) = rank K(q ϕ) / rank P(ϕ). Thus, before we can decide whether rank K(q|ϕ) p, it is necessary to compute rank P(ϕ), whose associated decision problem is already hard for the second level of the polynomial hierarchy. This is stated in the following theorem, which follows from a reduction from the problem of finding the maximum satisfying assignment of a set of weighted clauses [Krentel, 1988].

Theorem 4. Given a preference ranking P, p [0, 1], and a propositional formula ϕ, deciding whether rank P(ϕ) = p is p 2-hard.

Top-k Answers. If the size of the CQ q(x) and the preference ranking P are fixed, then there are polynomially many possible answers for q(x) to K = (P, O). For each such answer θ, by Theorem 2, we can compute rank K(q(xθ)) by performing constantly many BCQ entailment tests in L. If P is in the input, the problem becomes p 2-hard, even for simple instance queries, by Theorem 4. But it remains in p 2 in the combined complexity if classical BCQ entailment is in the first level of the polynomial hierarchy.

Theorem 5. Let A = (θ1, . . . , θk) be a tuple of answers for a CQ q(x) to a ranked ontology K. If Cd contains P, then deciding whether A is a top-k answer is in Cd, Ck, and ( P 2 )Cc in the data, KB, and combined complexity, respectively, and P 2 -complete in the ranking complexity. If Cc is contained in NP, then it is P 2 -complete in the combined complexity.

In particular, for ranked ontologies in EL, top-k query answering is in P in the data and KB complexity, and P 2 - complete in the ranking and combined complexity. Note that the complexity results in Table 3 for ranked ontologies in DL-Litecore are obtained via separate proofs. In particular, in the data complexity, one can build a first-order query verifying that A is already a top-k answer, which is in AC0. Most Preferred Worlds. As we are interested in valuations, rather than arbitrary contexts, computing conditional ranks is easier. Indeed, rank P(W) is computable in polynomial time. Hence, if BCQ answering in L is polynomial, one can decide in polynomial time whether rank K(W|q) rank K(W |q) for any two valuations W and W . Hardness follows, if P is part of the input, from the fact that deciding the existence of some W with rank P(W) p is already NP-hard.

Proceedings of the Twenty-Sixth International Joint Conference on Artificial Intelligence (IJCAI-17)

Theorem 6. Deciding whether W1, . . . , Wk are k most preferred worlds for the BCQ q is in Cd, Ck, and co NPCc in the data, KB, and combined complexity, resp., and co NP-complete in the ranking complexity. If Cc is contained in NP, then it is co NP-complete in the combined complexity.

In particular, for ranked ontologies in EL, deciding k most preferred worlds is in P in the data and KB complexity, and co NP-complete in the ranking and combined complexity. For DL-Litecore, this problem is in AC0, in NLOGSPACE, and co NP-complete in the respective complexities.

7 Related Work

A different combination of DLs with preferences for ranking objects is presented in [Lukasiewicz and Schellhase, 2007], where conditional preferences define a ranking function that allows to perform a semantic personalized search and ranking over a set of resources annotated via an ontological description. In [Lukasiewicz et al., 2013], Datalog+/ is extended with preferences closely related to those previously studied for relational databases. A similar combination of DLs with purely qualitative preferences is the approach in [Di Noia et al., 2013], which combines DLs with CP-nets in such a way that variable values of CP-nets are satisfiable DL formulas, and that ontological axioms are used to restrict CP-net outcomes. The work [Di Noia et al., 2015], like ours, also deals with computing k most preferred answers to CQs, but differently from ours, it is again based on CP-nets and existential rules. Although CP-nets are also graphical models for describing preferences, they differ greatly from polynomial preference rankings (and even possibilistic networks), both in their expressivity and in their computational complexity (in CP-nets, deciding dominance is PSPACE-complete, rather than polynomial). Another interesting approach to mixing qualitative preferences with Semantic Web technology is [Siberski et al., 2006], where SPARQL is extended to encode user preferences in the query. Generalizing possibilistic logic [Dubois and Prade, 2004], Hollunder [1995], Dubois et al. [2006], and Liau and Yao [2001] define possibilistic extensions of DLs, with applications in information retrieval. Similarly, a model for information retrieval based on possibilistic directed networks is proposed in [Brini et al., 2005]. Possibilistic extensions of DLs are also used for handling inconsistencies in ontologies [Qi et al., 2011]. All these approaches generalize standard first-order interpretations to possibilistic ones and interpret pairs of ontological axioms and possibilistic weights in them. Here, instead, we connect DLs under standard firstorder interpretations via contexts to unique preference rankings, which may be encoded as possibilistic networks. Borgwardt et al. [2016] use possibilistic networks to define a ranking on all answers to an ontological query, rather than an absolute ranking on the knowledge base; their framework and complexity results are based on existential rules, rather than on EL and DL-Litecore. In [Hadj Ali et al., 2011; Dubois et al., 2013], preferences are handled via possibilistic logic, while our work is on preference-based ontological query answering, combining ontologies and preference rankings (potentially encoded as possibilistic networks).

Less closely related, probabilistic DLs [d Amato et al., 2008; Ceylan and Pe naloza, 2017; Ceylan and Pe naloza, 2015] may similarly be context-based combinations of DLs with unique probability distributions, such as those in Bayesian networks. In [Lukasiewicz et al., 2014], probabilistic preference logic networks allow for dealing with preferences under probabilistic uncertainty in Markov random fields. However, polynomial preference rankings are very different from probability distributions. In particular, the rank of an event is the maximum of the ranks of all satisfying worlds, while its probability is the sum of their probabilities. Therefore, inference with preference rankings is computationally much easier than in Bayesian networks or other probabilistic graphical models (see also [Borgelt and Kruse, 2003]).

8 Summary and Outlook

We have introduced ranked ontologies as a general framework for extending DLs with a unique preference ranking, where each rank is computable in polynomial time, as a method for representing and reasoning about users conditional preferences about ontological knowledge. Using this approach, users may retrieve only the most preferred answers to a given query, instead of being overwhelmed by a large number of potentially irrelevant answers. We have provided a host of complexity results for different reasoning tasks in ranked ontologies in general, as well as in the lightweight DLs EL and DL-Litecore. Note that our generic complexity results can also be applied to other DLs, such as Horn SHIQ, or even other logics beyond DLs. All results can also be easily extended to non-Boolean variables with finite domains. All semantic results (but not the computational complexity results) also hold for non-polynomial preference rankings. Another natural application of our approach, especially when considering data sources from the Web and Big Data, is handling trust on the obtained answers. As knowledge and data may be extracted from sources with different reputation (e.g., Wikipedia, different newspapers, or experts), a user may want to prioritize those answers that arise from the most preferred sources, potentially conditioned on additional factors (e.g., when speaking of politics or sports). Naturally, these preferences may be different for distinct users of the system. An interesting topic for future work is to adapt specific query answering techniques to produce effective algorithms that can be used in practice, e.g., starting from the EL and DLLite families of DLs for which query answering techniques, mostly based on rewriting, have been largely studied.

Acknowledgments

This work was supported by the DFG under Ro SI (GRK 1907), by the UK EPSRC grants EP/J008346/1, EP/L012138/1, and EP/M025268/1, and by The Alan Turing Institute under the EPSRC grant EP/N510129/1.

[Amor et al., 2015] Nahla Ben Amor, Didier Dubois, H ela Gouider, and Henri Prade. Possibilistic conditional preference networks. In Proc. ECSQARU, pp. 36 46, 2015.

Proceedings of the Twenty-Sixth International Joint Conference on Artificial Intelligence (IJCAI-17)

[Artale et al., 2009] Alessandro Artale, Diego Calvanese, Roman Kontchakov, and Michael Zakharyaschev. The DL-Lite family and relations. J. Artif. Intell. Res., 36:1 69, 2009.

[Baader et al., 2005] Franz Baader, Sebastian Brandt, and Carsten Lutz. Pushing the EL envelope. In Proc. IJCAI, 2005.

[Baader et al., 2007] Franz Baader, Diego Calvanese, Deborah L. Mc Guinness, Daniele Nardi, and Peter F. Patel-Schneider (eds.). The Description Logic Handbook: Theory, Implementation, and Applications. Cambridge University Press, 2nd edition, 2007.

[Ben Amor et al., 2003] Nahla Ben Amor, Salem Benferhat, and Khaled Mellouli. Anytime propagation algorithm for min-based possibilistic graphs. Soft Comput., 8(2):150 161, 2003.

[Ben Amor et al., 2014] Nahla Ben Amor, Didier Dubois, H ela Gouider, and Henri Prade. Possibilistic networks: A new setting for modeling preferences. In Proc. SUM, pp. 1 7, 2014.

[Benferhat et al., 1999] Salem Benferhat, Didier Dubois, Laurent Garcia, and Henri Prade. Possibilistic logic bases and possibilistic graphs. In Proc. UAI, pp. 57 64, 1999.

[Benferhat et al., 2001] Salem Benferhat, Didier Dubois, and Henri Prade. Towards a possibilistic logic handling of preferences. Appl. Intell., 14(3):303 317, 2001.

[Benferhat et al., 2002] Salem Benferhat, Didier Dubois, Laurent Garcia, and Henri Prade. On the transformation between possibilistic logic bases and possibilistic causal networks. Int. J. Approx. Reason., 29(2):135 173, 2002.

[Borgelt and Kruse, 2003] Christian Borgelt and Rudolf Kruse. Operations and evaluation measures for learning possibilistic graphical models. Artif. Intell., 148(1/2):385 418, 2003.

[Borgwardt et al., 2016] Stefan Borgwardt, Bettina Fazzinga, Thomas Lukasiewicz, Akanksha Shrivastava, and Oana Tifrea Marciuska. Preferential query answering over the Semantic Web with possibilistic networks. In Proc. IJCAI, pp. 994 1000, 2016.

[Boutilier et al., 2004] Craig Boutilier, Ronen I. Brafman, Carmel Domshlak, Holger H. Hoos, and David Poole. CP-nets: A tool for representing and reasoning with conditional ceteris paribus preference statements. J. Artif. Intell. Res., 21:135 191, 2004.

[Brini et al., 2005] Asma H. Brini, Mohand Boughanem, and Didier Dubois. A model for information retrieval based on possibilistic networks. In Proc. SPIRE, pp. 271 282, 2005.

[Calvanese et al., 2007] Diego Calvanese, Giuseppe De Giacomo, Domenico Lembo, Maurizio Lenzerini, and Riccardo Rosati. Tractable reasoning and efficient query answering in description logics: The DL-Lite family. J. Autom. Reasoning, 39(3), 2007.

[Ceylan and Pe naloza, 2015] Ismail Ilkan Ceylan and Rafael Pe naloza. Probabilistic query answering in the Bayesian description logic BEL. In Proc. SUM, pp. 1 15, 2015.

[Ceylan and Pe naloza, 2017] Ismail Ilkan Ceylan and Rafael Pe naloza. The Bayesian ontology language BEL. J. Autom. Reasoning, 58(1):67 95, 2017.

[Chandra and Merlin, 1977] Ashok K. Chandra and Philip M. Merlin. Optimal implementation of conjunctive queries in relational data bases. In Proc. STOC, pp. 77 90, 1977.

[d Amato et al., 2008] Claudia d Amato, Nicola Fanizzi, and Thomas Lukasiewicz. Tractable reasoning with Bayesian description logics. In Proc. SUM, pp. 146 159, 2008.

[Darwiche, 2009] Adnan Darwiche. Modeling and Reasoning with Bayesian Networks. Cambridge University Press, 2009.

[Di Noia et al., 2013] Tommaso Di Noia, Thomas Lukasiewicz, and Gerardo I. Simari. Reasoning with semantic-enabled qualitative preferences. In Proc. SUM, pp. 374 386, 2013. [Di Noia et al., 2015] Tommaso Di Noia, Thomas Lukasiewicz, Maria Vanina Martinez, Gerardo I. Simari, and Oana Tifrea Marciuska. Combining existential rules with the power of CPtheories. In Proc. IJCAI, pp. 2918 2925, 2015. [Dubois and Prade, 2004] Didier Dubois and Henri Prade. Possibilistic logic: A retrospective and prospective view. Fuzzy Sets and Systems, 144(1):3 23, 2004. [Dubois et al., 2006] Didier Dubois, J erˆome Mengin, and Henri Prade. Possibilistic uncertainty and fuzzy features in description logic: A preliminary discussion. In Fuzzy Logic and the Semantic Web, Capturing Intelligence, pages 101 114. Elsevier, 2006. [Dubois et al., 2013] Didier Dubois, Henri Prade, and Fayc al Touazi. Conditional preference nets and possibilistic logic. In Proc. ECSQUARU, pp. 181 193, 2013. [Giese et al., 2015] Martin Giese, Ahmet Soylu, Guillermo Vega Gorgojo, Arild Waaler, Peter Haase, Ernesto Jim enez-Ruiz, Davide Lanti, Mart ın Rezk, Guohui Xiao, Ozg ur L. Ozc ep, and Riccardo Rosati. Optique: Zooming in on Big Data. IEEE Computer, 48(3):60 67, 2015. [Hadj Ali et al., 2011] Allel Hadj Ali, Souhila Kaci, and Henri Prade. Database preference queries A possibilistic logic approach with symbolic priorities. AMAI, 63(3/4): 357 383, 2011. [Hollunder, 1995] Bernhard Hollunder. An alternative proof method for possibilistic logic and its application to terminological logics. Int. J. Approx. Reason., 12(2):85 109, 1995. [Joachims, 2002] Thorsten Joachims. Optimizing search engines using clickthrough data. In Proc. SIGKDD, pp. 133 142, 2002. [Krentel, 1988] Mark W. Krentel. The complexity of optimization problems. J. Comput. Syst. Sci., 36(3):490 509, 1988. [Liau and Yao, 2001] Churn-Jung Liau and Y. Y. Yao. Information retrieval by possibilistic reasoning. In Proc. DEXA, 2001. [Lukasiewicz and Schellhase, 2007] Thomas Lukasiewicz and J org Schellhase. Variable-strength conditional preferences for ranking objects in ontologies. J. Web Sem., 5(3):180 194, 2007. [Lukasiewicz et al., 2013] Thomas Lukasiewicz, Maria V. Martinez, and Gerard I. Simari. Preference-based query answering in Datalog+/ ontologies. In Proc. IJCAI, pp. 501 518, 2013. [Lukasiewicz et al., 2014] Thomas Lukasiewicz, Maria Vanina Martinez, and Gerardo I. Simari. Probabilistic preference logic networks. In Proc. ECAI, pp. 561 566, 2014. [Pearl, 1988] Judea Pearl. Probabilistic Reasoning in Intelligent Systems: Networks of Plausible Inference. 1988. [Poole, 1997] David Poole. The independent choice logic for modelling multiple agents under uncertainty. Artif. Intell., 94, 1997. [Qi et al., 2011] Guilin Qi, Qiu Ji, Jeff Z. Pan, and Jianfeng Du. Extending description logics with uncertainty reasoning in possibilistic logic. Int. J. Intell. Syst., 26(4):353 381, 2011. [Rosati, 2007] Riccardo Rosati. On conjunctive query answering in EL. In Proc. DL, CEUR-WS.org, 2007. [Siberski et al., 2006] Wolf Siberski, Jeff Z. Pan, and Uwe Thaden. Querying the Semantic Web with preferences. In Proc. ISWC, pp. 612 624, 2006. [Suciu et al., 2011] Dan Suciu, Dan Olteanu, Christopher R e, and Christoph Koch. Probabilistic Databases. Synthesis Lectures on Data Management. Morgan & Claypool Publishers, 2011.

Proceedings of the Twenty-Sixth International Joint Conference on Artificial Intelligence (IJCAI-17)