Query Answering in Ontologies under Preference Rankings

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 PageRank 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.

• 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 rankP(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 rankP(x | pa(x)) consists of one conditional possibility value rankP (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): rankP(W)= ∏x∈V rankP(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 rankP0 ({b}) · rankP0 ({s}|{b}) · rankP0 ({¬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 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 ∧ni=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:

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)) = rankP(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 florenceI0 = d, sicilyI0 = e, bordeauxI0 = f, WineDestI0 =RelaxDestI0 ={d, e, f}, SpaDestI0 =∅, and worksWellWithI0 =∅. Then, the contextual interpretation (I0, {¬b, s, p}) is a model of O0, since florenceI ∈ WineDestI and WineDestI ⊆RelaxDestI , while (I0, {¬b, s, ¬p}) is not a model of O0, as it does not satisfy 〈RelaxDest ⊑ SpaDest : ¬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 rankP(q), is defined by rankP(q) = max(I,W)∈I, I|=q rank((I,W)), while the rank of q under K is then defined by: rankK(q) = infP|=K rankP(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 rankP(q ∧ ϕ), is defined as follows: rankP(q ∧ ϕ) = max(I,W)∈I, I|=q,W|=ϕ rank((I,W)), while the rank of q and ϕ under K, denoted rankK(q∧ϕ), is defined by rankK(q∧ ϕ) = infP|=K rankP(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:

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 valuationW of V , if rankP(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 = {〈WineDest ⊑ ¬WineDest : ¬b ∧ ¬p〉, 〈WineDest(florence): s〉}. For W1 ={¬b, s, ¬p}, it holds that rankP0 (W1)=1 > 0 (see Figure 1 above). Moreover, the ontology OW1 ={WineDest ⊑ ¬WineDest, WineDest(florence)} is inconsistent. Hence, K1 is also inconsistent. However, for O2 = {〈WineDest ⊑ ¬WineDest : ¬b ∧ ¬p〉, 〈WineDest(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 WineDestI2 =∅ and florenceI2 =d, the ranked interpretation P=(J, rank) given by J={(I2,W) |W ̸= W2}, and for all W ̸=W2, rank((I2, W)) = rankP0 (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 :

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, rankK1 (q1)=1 (since it is the infimum of an empty subset of [0, 1]). However, maxOW|=q1 rankP0 (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 rankP(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.

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 rankK(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:

1. for all i, 1≤i<k: rankK(q(xθi))≥rankK(q(xθi+1));
2. ii) for no other answer θ: rankK(q(xθk))<rankK(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: rankK(q(xθi)|ϕ)≥rankK(q(xθi+1)|ϕ); ii) for no other answer θ: rankK(q(xθk)|ϕ)<rankK(q(xθ)|ϕ). As rankK(ϕ) is a constant factor for all rankK(q(xθi)|ϕ), it

is sufficient to compare the ranks of all rankK(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:

1. for all i, 1≤i<k: rankK(Wi|q) ≥ rankK(Wi+1|q);
2. ii) for no other valuationW: rankK(Wk|q)<rankK(W|q).

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

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 AC 0 , 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 AC 0 , 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 rankK(q|ϕ)≥p, which is in fact harder in the network complexity. Assuming that rankP(ϕ)>0, we have rankK(q|ϕ) = rankK(q ∧ϕ) / rankP(ϕ). Thus, before we can decide whether rankK(q|ϕ)≥p, it is necessary to compute rankP(ϕ), 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 rankP(ϕ) = p is ∆p2 -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 rankK(q(xθ)) by performing constantly many BCQ entailment tests in L. If P is in the input, the problem becomes ∆p2 -hard, even for simple instance queries, by Theorem 4. But it remains in ∆p2 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 (∆P2 )Cc in the data, KB, and combined complexity, respectively, and ∆P2 -complete in the ranking complexity. If Cc is contained in NP, then it is ∆P2 -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 ∆P2 - 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 AC 0 .

Most Preferred Worlds. As we are interested in valuations, rather than arbitrary contexts, computing conditional ranks is easier. Indeed, rankP(W) is computable in polynomial time. Hence, if BCQ answering in L is polynomial, one can decide in polynomial time whether rankK(W|q) ≥ rankK(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 rankP(W) ≥p is already NP-hard.

Theorem 6. Deciding whether W1, . . . ,Wk are k most preferred worlds for the BCQ q is in Cd, Ck, and coNPCc in the data, KB, and combined complexity, resp., and coNP-complete in the ranking complexity. If Cc is contained in NP, then it is coNP-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 coNP-complete in the ranking and combined complexity. For DL-Litecore, this problem is in AC 0 , in NLOGSPACE, and coNP-complete in the respective complexities.

7 RelatedWork

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 [HadjAli 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 RoSI (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.