Combining Existential Rules with the Power of CP-Theories

1 Introduction

From its inception, the Web has been centered around the idea of linking information to make it more accessible and useful for the users. Its fast growth, however, made it hard for end users to satisfy their information needs due to the issues related to information overload. Too much information is currently available on the Web, and new personalized information filtering techniques are needed that are able to retrieve documents/data/resources that best fit users' interests and preferences, i.e., that best match users' profiles.

Moreover, the Web has recently evolved at an increasing pace towards the so-called Web 3.0, where classical linked information lives together with ontological knowledge and social interactions of users. While the former may allow for more precise and rich results in search and query answering tasks, the latter can be used to enrich the user profile, and it paves the way to more sophisticated personalized access to information. This requires new techniques for ranking search results, fully exploiting ontological and user-centered data, i.e., user preferences. Such techniques are also very useful for computer applications (e.g., preferences over different data sources) and agents (e.g., planning with preferences).

Thomas Lukasiewicz

Department of Computer Science University of Oxford, UK thomas.lukasiewicz@cs.ox.ac.uk

Oana Tifrea-Marciuska

Department of Computer Science University of Oxford, UK oana.tifrea@cs.ox.ac.uk

The study of preferences has been carried out in many different areas, such as philosophy, economics, and choice theory. They can be modeled in both qualitative and quantitative ways, where quantitative preferences are associated with a number representing their worth, while qualitative preferences are related to each other via pairwise comparisons.

In this paper, we focus on ranking answers for conjunctive queries (CQs) to Datalog+/- ontologies, based on user preferences encoded in CP-theories [Wilson, 2004], which generalize CP-nets [Boutilier et al., 1999]. We chose CPtheories for their natural, concise, and flexible representation of qualitative preferences - along with their subclasses, they are widely used to represent and reason with qualitative preferences. We chose the Datalog+/- ontology language for its expressive power and intuitive nature - its fragments generalize many other ontology languages, such as the DL-Lite family [Calvanese et al., 2007] of description logics (DLs) [Cal`ı et al., 2012a]. The integration between the ontology and the CP-theory is tight: on the one hand, CP-theory outcomes are constrained by the ontology, and, on the other hand, they directly inform how answers to CQs are ranked.

The main contributions of this paper are briefly as follows:

• We introduce ontological CP-theories (OCP-theories), which combine Datalog+/- with CP-theories, modeling preferences over ground atoms in Datalog+/- ontologies.
• We define skyline and k-rank answers for CQs to OCPtheories. We also provide an algorithm for computing such answers based on the preferences encoded in an OCP-theory.
• We analyze the computational complexity of deciding consistency, dominance, and CQ skyline membership for OCPtheories, providing (generic and concrete) precise complexity results for different types of combined complexity.
• We also provide several tractability results in the data complexity for the case where query answering in the underlying classical ontology is tractable in the data complexity.

2 Preliminaries

Before introducing OCP-theories, we recall the basics on Datalog+/- and classical CP-theories.

2.1 Datalog+/-

We now recall the basics of Datalog+/- [Cal`ı et al., 2012a], namely, relational databases, dependencies, (Boolean) conjunctive queries ((B)CQs), and ontologies.

General. Consider the following sets: a set ∆ of constants, a set ∆N of labeled nulls, and a set V of regular variables. A term t is a constant, null, or variable. 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 : ∆ ∪ ∆N ∪ V → ∆ ∪ ∆N ∪ V that is the identity on ∆. We assume the reader is familiar with conjunctive queries (CQs). The answer to a CQ q over an instance I is denoted q(I). A Boolean CQ (BCQ) q has a positive answer over I, denoted I |= q, if q(I) ̸= ∅.

Dependencies. A tuple-generating dependency (TGD) or existential rule σ is a first-order formula ∀Xϕ(X) → ∃Y p(X, Y), where X∪Y ⊂ V, ϕ(X) is a conjunction of atoms, and p(X, Y) is an atom; ϕ(X) is the body of σ, denoted body(σ), while p(X,Y) is the head of σ, denoted head(σ). For clarity, we consider single-atom-head TGDs; however, our results can be extended to TGDs with a conjunction of atoms in the head. An instance I satisfies σ, written I |= σ, if the following holds: whenever there exists a homomorphism h such that h(ϕ(X)) ⊆ I, then there exists h′ ⊇ h|X, where h|X is the restriction of h on X, such that h′ (p(X,Y)) ∈ I. A negative constraint (NC) ν is a first-order formula of the form ∀Xϕ(X) → ⊥, where X ⊂ V, ϕ(X) is a conjunction of atoms and is called the body of ν, denoted body(ν), and ⊥ denotes the truth constant false. An instance I satisfies ν, written I |= ν, if there is no homomorphism h such that h(ϕ(X)) ⊆ I. Given a set Σ of TGDs and NCs, I satisfies Σ, written I |= Σ, if I satisfies each TGD and NC of Σ. For brevity, we omit the universal quantifiers in front of TGDs and NCs, and use a comma instead of ∧ to denote conjunction. As another component, Datalog+/- allows for special types of equality-generating dependencies (EGDs). Since they can also be modeled via NCs, we omit them here and refer to [Cal`ı et al., 2012a] for their details.

Conjunctive Query Answering. Given a database D and a set Σ of TGDs and NCs, the answers we consider are those that are true in all models of D and Σ. Formally, the models of D and Σ, denoted mods(D,Σ), is the set of instances {I | I ⊇D, I |=Σ}. The answer to a CQ q w.r.t. D and Σ is the set of tuples ans(q, D, Σ) = ⋂I∈mods(D,Σ){t | t ∈ q(I)}. The answer to a BCQ q is positive, denoted D ∪ Σ |= q, if ans(q,D,Σ) ̸= ∅. The problem of CQ answering is defined as follows: given a database D, a set Σ of TGDs and NCs, a CQ q, and a tuple of constants t, decide whether t ∈ ans(q,D,Σ). Following Vardi's taxonomy (1982), the combined complexity of CQ answering is calculated by considering all the components, i.e., the database, the set of dependencies, and the query, as part of the input. The data complexity is calculated by only considering the database as part of the input. The bounded-arity combined complexity review

(or ba-combined complexity) is calculated by assuming that the arity of the underlying schema is bounded by an integer constant. Notice that in the context of DLs, whenever we refer to the combined complexity in fact we refer to the bacombined complexity, as the arity of the underlying schema is at most two. The fixed-program combined complexity (or fp-combined complexity) is calculated by considering the set of TGDs and NCs as fixed.

Datalog+/- Ontologies. A Datalog+/- ontology O=(D, Σ), where Σ=ΣT ∪ ΣNC, consists of a finite database D over ∆, a finite set ΣT of TGDs, and a finite set ΣNC of NCs.

Example 1 A simple Datalog+/- ontology O=(D, Σ) is as follows: the database D is shown in Fig. 1, modeling the domain of an online hotel booking service, integrated with a social network. The hotel relation contains information about the hotel, such as its location, if it has WiFi or cable connection, and its class; the review relation is used to register the users' feedback after their stay. Intuitively, D encodes, e.g., that h1, h2, and h3 are three hotels, and p (positive) and n (negative) represent users' feedback, w (WiFi) and c (cable) are available internet connections, and hotels are either e (economy) or l (luxury) class. In our example, Alice (a) is planning her holidays and looking for a hotel in Rome. She is connected to John (j) and Bob (b) in the social network. Both John and Bob are active users, as they already booked and reviewed some hotels. The set Σ encodes relationships among predicates, e.g., that a reviewer always has friends (if s/he has no friends, then he is not allowed to review).

2.2 CP-Theories

We now recall CP-theories from [Wilson, 2004]. We assume a finite set of variables X∈X, each having a finite set of values x, denoted Dom(X), also called the domain of X. A value u for U ⊆X associates with every X ∈ U a value of X. The set of all values u for U is denoted Dom(U), also called the domain of U. We denote with ⊤ the only value of U = ∅. A conditional preference ϕ on X has the form u: x≻x′ [W], where U ⊆X, u∈Dom(U), X∈X -U, x, x′ ∈Dom(X), and W ⊆X -(U ∪{X}); intuitively, it means that given u and t∈Dom(Tϕ), where Tϕ=X -(U ∪{X}∪W), we prefer x to x′ , irrespective of the value of W. A conditional preference theory (or CP-theory) on X is a finite set of conditional preferences on X .

An outcome is any value o∈Dom(X). Interpretations of CP-theories are strict total orders on Dom(X), i.e., irreflexive and transitive binary relations π on Dom(X) that are total (i.e., for any two distinct o, o′ ∈Dom(X), either (o, o′ )∈π or (o′ , o)∈π). For conditional preferences ϕ=u: x≻x′ [W], let ϕ⋆ ={(tuxw, tux′w′ ) | t∈Dom(Tϕ), w,w′ ∈Dom(W)}. An interpretation π satisfies (or is a model of) ϕ, denoted π |= ϕ, if π⊇ϕ⋆ . We say π satisfies (or is a model of) a CP-theory Γ if it satisfies all ϕ ∈ Γ. A CP-theory is consistent if it has a model. For two outcomes o and o′ , we say o is dominated by o′ in Γ, denoted o′ ≻ o, if (o′ , o) belongs to all models π of Γ. An outcome o is undominated in Γ if there is no outcome o′ such that o′ ≻ o. Let Γ⋆ denote the transitive closure of ∪ϕ∈Γϕ⋆ . Then, for all outcomes o and o′ , it holds that o≻o′ iff (o, o′ )∈Γ⋆ .

CP-nets [Boutilier et al., 2004] (resp., TCP-nets [Brafman et al., 2006]) can be represented via conditional preferences of the form u : x ≻ x′ [W] with W = ∅ (resp., |W| ⩽1).

Example 2 Alice would like to be online during the holidays to share pictures and comments, so she always prefers a WiFi connection to a cable one (statement (1) below), even though she can live also with the latter. When choosing a hotel, Alice also looks at what her friends already did, and she checks the feedback that they left on the social network. Her preference always goes to hotels with a positive feedback irrespective of who left the feedback and the hotel's connection type (2). Alice knows that Bob is usually very objective in his opinions so, for positive feedbacks, she prefers Bob's reviews to John's (3). She also knows that Bob cannot live without being online with his phone, so Bob does not consider a WiFi connection optional. This is why when there is no WiFi connection, Bob's feedback is biased and tends to be negative. Hence, for hotels without WiFi, Alice prefers John's review (4). For the same reason, for hotels with WiFi, she prefers Bob's feedback to John's (5).

Based on the above description of Alice's preferences, we introduce three variables C (connection), R (reviewer), and F (feedback) with the domains Dom(C)={w, c}, Dom(R) = {b, j}, and Dom(F) = {p, n}, respectively, and we model Alice's preferences by the CP-theory

which has the following two models:

For example, the outcome o=pwb represents wireless connection and positive feedback from reviewer Bob.

3 OCP-Theories

We now introduce ontological CP-theories (or OCP-theories), which extend CP-theories by ontologies. They informally define preferences between conjunctions of atoms relative to an ontology. W.l.o.g., the set ∆N of nulls is the set of all ground terms constructed from the set ∆ of constants and a set F of functions used to skolemize all existential variables in TGDs.

Definition 1 (OCP-Theory) Let O be a Datalog+/- ontology O over ∆. Let X be a finite set of variables, each X∈X being associated with a predicate p from O, denoted pred(X), and as domain Dom(X) with a finite set of at least two different ground atoms p(c1, . . . , ck), with c1, . . . , ck ∈∆ ∪ ∆N. Let Dom+(X) be the set of all (non-ground) atoms p(t1, . . . , tk) with terms t1, . . . , tk over ∆, V, and F. Then, an ontological conditional preference over X has the form

where (i) υ∈Dom+(U) for some U ⊆X, (ii) ξ, ξ ′ ∈ Dom+(X) for some X∈X -U, and (iii) W ⊆X -(U ∪ {X}). We say υθ : ξθ ≻ ξ ′ θ [W], where θ is a substitution, is a ground instance of (1), if υθ∈Dom(U) and ξθ, ξ ′ θ ∈ Dom(X). Let Γ be a finite set of preferences of the form (1). Then, (O, Γ) is an ontological CP-theory (or OCP-theory).

The following example illustrates OCP-theories.

Example 3 (Hotel Booking cont'd) Consider OCP-theory (O, Γ) given by ontology O of Example 1 and the following set Γ of ontological conditional preferences:

It is defined over the variables CO, RO, and FO with the predicates pred (CO) = hotel, pred (RO) = reviewer, and pred (FO) = review, and the domains Dom(CO)={hotel(t1), hotel(t2), hotel(t3)}, Dom(RO)={reviewer(t10), reviewer(t11)}, and Dom(FO)={review(t7), review(t8), review(t9)} (see Fig. 1), respectively.

Note that the notion of outcome for OCP-theories is inherited from CP-theories (Section 2.2), i.e., a mapping that associates with every variable X ∈ X a value x ∈ Dom(X). Observe that every outcome o of an OCP-theory can be seen as a conjunction of ground atoms over ∆ ∪ ∆N (e.g., in the above example, the outcome o with o(CO) = hotel(t1), o(RO) = reviewer(t10), and o(FO) = review(t9) can be seen as the conjunction hotel(t1) ∧ reviewer(t10) ∧ review(t9)).

As a consequence of the underlying ontology, some of these outcomes may be inconsistent, and some other outcomes may be equivalent. We thus have to ensure that the preference relation encoded in an OCP-theory is welldefined, which is expressed in the notion of consistency of an OCP-theory. To define it, we need some preparatory definitions as follows.

An outcome o of (O, Γ) is consistent if O∪{o(X) |X ∈ X}̸|=⊥. Two outcomes o and o′ of (O, Γ) are equivalent, denoted o∼o′ , if O∪{o(X) |X∈X} ≡ O∪{o′ (X) |X ∈ X}. An interpretation π for (O, Γ) is a total order over the outcomes of (O, Γ). We say π satisfies (or is a model of) O, denoted π |= O, if (i) o and o′ are consistent, for all (o, o′ )∈π, and (ii) (o, o′ )∈π for any two equivalent outcomes o and o′ . We say π satisfies (or is a model of) a ground conditional preference ϕ, denoted π |= ϕ, if πs ⊇ ϕ⋆ , where πs denotes the strict part of π. We say π satisfies (or is a model of) a set of conditional preferences Γ, denoted π |= Γ, if it satisfies all ground instances of ϕ∈Γ. We say π satisfies (or is a model of) an OCP-theory (O, Γ), denoted π |= (O, Γ), if it satisfies both O and Γ. The notion of consistency of OCPtheories is then defined as the existence of a model.

Definition 2 (Consistency) An OCP-theory (O, Γ) is consistent if it has a model.

We next give an alternative characterization of this notion of consistency. Given an OCP-theory (O, Γ), let Γ⋆ ∼ denote the transitive closure of the set of all ([a]∼, [b]∼) such that (i) (a, b) ∈Γ⋆ and (ii) a and b are both consistent, where [s]∼ denotes the ∼-equivalence class of s. Then, the consistency of OCP-theories describes the acyclicity of Γ⋆ ∼ .

Theorem 1 OCP-theory (O,Γ) is consistent iff Γ⋆ ∼ is acyclic.

The notions of dominance between consistent outcomes and of undominance of consistent outcomes are as follows.

Definition 3 (Dominance) Let (O, Γ) be a consistent OCPtheory, and o and o′ be consistent outcomes. Then, o dominates o′ in (O, Γ), denoted o≻o′ , if (o, o′ )∈π for all models π of (O, Γ). A consistent outcome o is undominated in (O, Γ), if no consistent outcome o′ exists with o′ ≻o.

The next theorem shows that the notion of dominance between consistent outcomes is exactly expressed by Γ⋆ ∼ .

Theorem 2 Let (O,Γ) be a consistent OCP-theory, and o and o′ be consistent outcomes. Then, o≻o′ iff ([o]∼, [o′ ]∼)∈Γ⋆ ∼ .

4 CQAnswering for OCP-Theories

In this section, we define skyline and k-rank answers for CQs to consistent OCP-theories. We also provide an algorithm for computing their answers.

4.1 Semantics

The following definition formalizes answers for CQs q(X) = ∃YΦ(X, Y) to O as usual, and relates them to the consistent outcomes of (O, Γ). Here, we assume a bijection β from a set Φβ(X,Y)⊆Φ(X,Y) of atoms in q to a set of variables of (O, Γ) (and so their values in consistent outcomes) such that every atom a∈Φβ(X,Y) has the same predicate as the variable β(a). Intuitively, β relates query atoms in q to preference atoms in (O, Γ). Note that when β is empty, the answers for q to O are unrelated to the consistent outcomes of (O, Γ), i.e., they are (unordered) standard answers to CQs.

Definition 4 (Answer) Let (O, Γ), with O=(D,Σ), be a consistent OCP-theory, and let q(X)=∃YΦ(X,Y) be a CQ. Then, the set of all answers for q to (O, Γ) under the consistent outcome o of (O, Γ), denoted ans(q, Γ,O, o), is the set of all tuples a over ∆ ∪ ∆N for which a homomorphism µ: X∪Y→∆ ∪ ∆N exists such that (i) D ∪ Σ |=

µ(Φ(X,Y)), (ii) µ(X)=a, and (iii) µ(a)=o(β(a)) for all a∈Φβ(X,Y). An answer for q to (O, Γ) is an answer for q to (O, Γ) under some consistent outcome o of (O, Γ).

Note that nulls are included in answers, since they actually represent prototypical constants. The following example illustrates the notion of answer for CQs to OCP-theories.

Example 4 Consider the consistent OCP-theory (O, Γ) of Example 3 and the CQ q(A,B,C,D)=∃Y hotel(A, rome, C, Y ) ∧ review(A, B, D). Then, 〈h2, b, w, p〉 is an answer for q under the consistent outcome o = hotel(h2, rome, w, l) review(h2, b, p) reviewer(b, 20). Let a = hotel(A, rome,C, Y ) and β(a) = Co; once we fix the outcome o, then we have that o(β(a)) = hotel(h2, rome, w, l).

We next sort these answers based on the preferences of the user. We do this via skyline answers [B¨orzs¨onyi et al., 2001], a well-known class of answers for preference-based formalisms, and the iterated computation of skyline answers that allows us to assign a rank to every answer (via the CPtheory); we refer to these as k-rank answers. We first define skyline answers; note that they are not unique. Indeed, we may have more than one undominated consistent outcome o, and also more than one homomorphism µ that satisfies the conditions (i) and (ii) of Definition 4 for the same undominated consistent outcome o.

Definition 5 (Skyline Answer) Let (O, Γ) be a consistent OCP-theory, and let q(X) = ∃YΦ(X,Y) be a CQ. A skyline answer for q to (O, Γ) is any tuple a∈ans(q, Γ,O, o) for some consistent outcome o such that there is no consistent outcome o′ with (i) o′ ≻ o and (ii) ans(q, Γ, O, o′ ) ̸=∅.

We next define k-rank answers for CQs to OCP-theories via iteratively applying the notion of skyline answer. The definition is technically involved, as answers are obtained by projecting away existentially quantified arguments, thus distinct outcomes may be associated with the same answer, and so distinct levels of the skyline iteration may contain the same answers. We handle this in each iteration step by removing all answers computed in previous iteration steps.

Definition 6 (k-Rank Answer) Let (O, Γ) be a consistent OCP-theory, and q(X) = ∃YΦ(X,Y) be a CQ. A k-rank answer for q to (O, Γ) outside a set of ground atoms S is a sequence 〈a1, . . . , ak〉 such that either:

• (a) a1, . . . , ak are k different skyline answers for q to (O, Γ) not belonging to S, if at least k such answers exist; or
• (b) (1) a1, . . . , ai are all i different skyline answers for q to (O, Γ) that do not belong to S, and (2) 〈ai+1, . . . , ak〉 is a (k-i)-rank answer for q to (O, Γ-{o}) outside S ∪ {a1, . . . , ai}, where o is an undominated outcome relative to ≻, otherwise.

A k-rank answer for q to (O, Γ) is a k-rank answer for q to (O, Γ) outside ∅.

Note that when no answer for q to (O, Γ) exists, then 〈〉 is its unique k-rank answer. Informally, a k-rank answer is a sequence of k answers for a CQ to an OCP-theory ranked by following the order among consistent outcomes induced by the OCP-theory. Clearly, as skyline answers are in general not unique, also k-rank answers are in general not unique.

4.2 Algorithm

Algorithm 1 computes, given a consistent OCP-theory (O, Γ), a CQ q, and k⩾0 as input, a k-rank answer for q to (O, Γ). It exploits the preference order of consistent outcomes to iteratively compute skyline answers for q to (O, Γ). It stops when it reaches k different answers to q. The most preferred answers are the ones related to the undominated consistent outcomes o; thus, the computation starts by adding such o to Outcomes (line 4). There are two sources of nondeterminism: in line 7, we may choose arbitrarily among different incomparable outcomes; then, in line 10, we may have multiple equivalent µ's, and after selecting some of them, we reach length(Result )=k. Note that the set of all skyline answers for q to (O, Γ) can be computed by setting k-reached to true in line 2 and by stopping the algorithm after the set of all answers associated with all undominated outcomes in Outcomes are computed, once this set of answers is non-empty.

5 Computational Complexity

We now analyze the computational complexity of deciding consistency, dominance, and CQ skyline membership for OCP-theories. We also delineate some tractable special cases. We assume some familiarity with complexity classes PSPACE (resp.,P, EXP, 2EXP) containing all decision problems that can be solved in polynomial space (resp., polynomial, exponential, double exponential time) on a deterministic Turing machine; see [Johnson, 1990; Papadimitriou, 1994].

5.1 Decidability Paradigms

The main (syntactic) conditions on TGDs that guarantee the decidability of CQ answering are guardedness [Cal`ı et al., 2013], stickiness [Cal`ı et al., 2012b], and acyclicity. Interestingly, each of them has its "weak" counterpart: weak guardedness [Cal`ı et al., 2013], weak stickiness [Cal`ı et al., 2012b] and weak acyclicity [Fagin et al., 2005], respectively.

A TGD σ is guarded if an atom a∈body(σ) exists that contains (or "guards") all the body variables of σ. The class of guarded TGDs, denoted G, is defined as the family of all possible sets of guarded TGDs. A key subclass of guarded TGDs are linear TGDs with just one body atom (which is automatically a guard), and the corresponding class is denoted L. Weakly guarded TGDs extend guarded TGDs by requiring only "harmful" body variables to appear in the guard, and the associated class is denoted WG. Notice that L ⊂ G ⊂ WG.

Stickiness is inherently different from guardedness, and its central property is as follows: variables that appear more than once in a body (i.e., join variables) are always propagated (or "stick") to the inferred atoms. A set of TGDs that enjoys the above property is called sticky, and the corresponding class is denoted S. Weak stickiness is a relaxation of stickiness where only "harmful" variables are taken into account. A set of TGDs that enjoys weak stickiness is weakly sticky, and the associated class is denoted WS. Observe that S ⊂ WS.

A set Σ of TGDs is acyclic if its predicate graph is acyclic, and the underlying class is denoted A. In fact, an acyclic set of TGDs can be seen as nonrecursive. We say Σ is weakly acyclic if its dependency graph enjoys a certain acyclicity condition, which guarantees the existence of a finite canonical model; the associated class is denoted WA. Clearly, A ⊂ WA.

Another key fragment of TGDs are full TGDs, i.e., TGDs without existentially quantified variables, and the corresponding class is denoted F. If we further assume that full TGDs enjoy linearity, guardedness, stickiness, or acyclicity, then we obtain the classes LF, GF, SF, and AF, respectively.

5.2 Combined Complexity

For complexity classes C ⊆ PSPACE (resp., deterministic complexity classes C⊇EXP), the following theorem shows the generic results that (i) deciding consistency of OCP-theories (O, Γ) and (ii) deciding dominance between two outcomes of OCP-theories (O, Γ) are both complete for PSPACE (resp., C) when BCQN answering in O is complete for C, and hardness holds even for ground atomic BCQs. Here, BCQN s denote BCQs with elements from∆∪∆N (where ∆N is as defined in Section 3) and variables as arguments in atoms.

Theorem 3 Let T be a class of OCP-theories (O, Γ) where BCQN answering in O is complete for a complexity class C ⊆ PSPACE (resp., deterministic complexity class C ⊇ EXP), and hardness holds even for ground atomic BCQs. Then, deciding whether (a) some given (O, Γ)∈T is consistent and (b) o dominates o′ in (O, Γ), given (O, Γ)∈T and two outcomes o and o′ , are both complete for PSPACE (resp., C).

Proof (sketch). (a) For membership, by Theorem 1 it is sufficient to decide whether Γ⋆∼ is acyclic. This can be done by deciding whether [o]∼ ≻ [o]∼ for some consistent outcome o, which can be done (despite the number of outcomes of (O, Γ) being exponential) by storing at most two outcomes, while exploring all the paths in Γ⋆∼. This requires both deciding BCQN s to O (for deciding if an outcome is consistent, and whether two consistent outcomes are equivalent), which is in C, and deciding dominance between two outcomes in a standard CP-theory, which is in PSPACE [Goldsmith et al.,

2008]. Overall, this is possible in PSPACE (resp., C).

Hardness for PSPACE follows from the more specialized problem of deciding consistency in a standard CP-theory being PSPACE-hard. Hardness for C holds by a reduction from the C-hard problem of answering ground atomic BCQs, since O |=a iff (O∪{a′}, {a′ ≻a}) over X ={X} with Dom(X)={a, a′} is inconsistent.

(b) For membership, by Theorem 2 it is sufficient to decide whether o and o′ are consistent and whether [o]∼≻[o′ ]∼. As argued in (a), this is overall possible in PSPACE (resp., C).

PSPACE-hardness follows from the PSPACE-hardness of the more specialized problem of deciding dominance between two outcomes in standard CP-theories [Goldsmith et al., 2008]. Hardness for C holds by a reduction from the same problem as in (a), since O |= a′ iff a′′ ≻ a holds in (O ∪ {a′′}, {a′ ≻a}) over X ={X} with Dom(X)={a, a′ , a′′}. □

As a corollary, by the known complexity results for Datalog+/- (see, e.g., [Lukasiewicz et al., 2015]), deciding consistency and dominance for OCP-theories when the underlying ontology is in L, LF, AF, G, WG, S, F, GF, SF, WF, or WA, is complete for the complexity classes shown in Table 1 in the combined, ba-combined, and fp-combined complexity.

Corollary 4 Given an OCP-theory (O, Γ), where O is defined in L, LF, AF, G, WG, S, F, GF, SF, WS, or WA, deciding whether (a) (O, Γ) is consistent and (b) o dominates o′ , given (O, Γ) and two outcomes o and o′ , is both complete for the complexity classes shown in Table 1 in the combined, ba-combined, and fp-combined complexity.

We next show that the complexity of deciding whether a tuple over ∆ is in the skyline answer for a CQ to an OCP-theory (O, Γ) is complete for PSPACE (resp., C) when BCQN answering in O is complete for the complexity class C ⊆ PSPACE (resp., deterministic complexity class C ⊇ EXP).

Theorem 5 Let T be a class of consistent OCP-theories (O, Γ) where BCQN answering in O is complete for a complexity class C⊆PSPACE (resp., deterministic complexity class C ⊇ EXP). Then, given (O, Γ) ∈T , a CQ q, and a tuple a over ∆∪∆N, deciding whether a is in the skyline answer for q to (O, Γ) is complete for PSPACE (resp., C).

Proof (sketch). For membership, it is sufficient to decide if a∈ans(q, Γ,O, o) for some consistent outcome o such that no consistent outcome o′ exists with (i) o′ ≻o and (ii) ans(q, Γ, O, o′ ) ̸=∅. By a similar argument as in the proof of Theorem 3, this is overall possible in PSPACE (resp., C).

Hardness for C follows from the more specialized problem of BCQN answering being C-hard. Hardness for PSPACE follows by a reduction from the PSPACE-hard problem of deciding dominance between two outcomes o=o1 . . . on and o′ =o′1 . . . o′n in standard CP-theories Γ, as o≻o′ in Γ iff (o1, . . . , on) is in the skyline answer for ⋃ni=1{qi(Xi)} to (⋃ni=1{qi(oi)}∪ ⋃ni=1{qi(o′i )}, Γ′ ), where Γ′ is obtained from Γ by consistently replacing values vi by qi(vi). □

By the known complexity results for Datalog+/- (see, e.g., [Lukasiewicz et al., 2015]), we obtain as a corollary that deciding CQ skyline membership for OCP-theories when the underlying ontology is in L, LF, AF, G, WG, S, F, GF, SF, WF, or WA, is complete for the complexity classes in Table 1 in the combined, ba-combined, and fp-combined complexity.

Corollary 6 Given a consistent OCP-theory (O, Γ), where O is defined in L, LF, AF, G, WG, S, F, GF, SF, WS, or WA, a CQ, and a tuple a over ∆ ∪ ∆N, deciding if a is in the skyline answer for q to (O, Γ) is complete for the classes in Table 1 in the combined, ba-combined, and fp-combined complexity.

5.3 Data Complexity

We now delineate special cases where deciding consistency, dominance, and CQ skyline membership for OCP-theories are all tractable in the data complexity. The following result shows that deciding consistency and dominance for OCPtheories (O, Γ), with O=(D, Σ), is data tractable when BCQN answering in O is data tractable. Here, data complexity means that Σ and the variables and preferences of Γ are fixed, while D and the domains of Γ are part of the input.

Theorem 7 Let T be a class of OCP-theories (O, Γ) where BCQN answering in O is possible in polynomial time in the data complexity. Then, deciding whether (a) some given (O, Γ) ∈ T is consistent and (b) o dominates o′ , given (O, Γ) ∈ T and outcomes o and o′ , are both possible in polynomial time in the data complexity.

Proof (sketch). (a) In the data complexity, the number of all outcomes of (O, Γ) is polynomial in the number of domain values. As deciding BCQs in O is possible in data polynomial time, deciding if an outcome is consistent, and whether two consistent outcomes are equivalent as well. So, computing Γ⋆∼ and deciding whether Γ⋆∼ is acyclic can also be done in data polynomial time. Overall, by Theorem 1, deciding consistency of (O, Γ) is possible in data polynomial time.

(b) By Theorem 2, it is sufficient to decide whether o and o′ are consistent and whether [o]∼ ≻ [o′ ]∼. As argued in (a), this is overall possible in data polynomial time. □

As a corollary, deciding consistency and dominance for OCP-theories is data tractable when the underlying ontology is formulated in L, LF, AF, G, S, F, GF, SF, WF, or WA, which all allow for data tractable BCQN answering.

Corollary 8 Given an OCP-theory (O, Γ), where O is defined in L, LF, AF, G, S, F, GF, SF, WF, or WA, deciding whether (a) (O, Γ) is consistent and (b) o dominates o′ , given (O, Γ) and outcomes o and o′ , are all possible in polynomial time in the data complexity.

The next result shows that deciding membership to skyline answers for CQs to consistent OCP-theories is data tractable when BCQN answering in O is data tractable.

Theorem 9 Let k⩾0 be fixed. Let T be a class of consistent OCP-theories (O, Γ) where BCQN answering in O can be done in polynomial time in the data complexity. Then, given (O, Γ)∈T , a CQ q, and a tuple a over ∆ ∪ ∆N, deciding whether a is in the skyline answer for q to (O, Γ) is possible in polynomial time in the data complexity.

Proof (sketch). As argued in the proof of Theorem 7, computing Γ⋆∼ can be done in data polynomial time. Hence, by Theorem 1, computing iteratively undominated outcomes can also be done in data polynomial time. Since BCQN answering in O is data tractable, deciding whether a is in the skyline answer for q to (O, Γ) is possible in data polynomial time. □

A corollary is that membership to skyline answers for CQs to consistent OCP-theories is data tractable when the ontology is formulated in L, LF, AF, G, S, F, GF, SF, WF, or WA, which all allow for data tractable BCQN answering.

Corollary 10 Given a consistent OCP-theory (O, Γ), a CQ q, where O is defined in L, LF, AF, G, S, F, GF, SF, WF, or WA, and a tuple a over ∆∪∆N , deciding whether a is in the skyline answer for q to (O, Γ) is possible in polynomial time in the data complexity.

The above data tractability results do not carry over to WG, where BCQN answering in O is data complete for EXP, and data hardness holds even for ground atomic BCQs: so, data completeness for EXP can be proved similarly to Theorem 5.

6 RelatedWork

Modeling and dealing with preferences in databases has been studied for almost three decades, since the seminal work of Lacroix and Lavency [1987]; see [Stefanidis et al., 2011] for a survey of notable works in this line. Work has also been carried out in the intersection with databases and knowledge representation and reasoning, such as preference logic programs [Govindarajan et al., 1995], incorporation of preferences into formalisms such as answer set programs [Brewka, 2007], and answering k-rank queries in ontological languages [Lukasiewicz et al., 2013].

In the philosophical tradition, preferences are usually expressed over mutually exclusive "worlds", such as truth assignments to formulas. Bienvenu et al.'s work [2010] is framed in this interpretation of preferences, aiming at bridging the gap between several formalisms in AI, such as CP-nets and those studied traditionally in philosophy. In this regard, CP-nets [Boutilier et al., 2004] are one of the most widely known formalisms. Most work on CP-nets has focused on the computation of optimal outcomes and dominance testing, i.e., to check if one outcome of the CP-net is preferred to another. More recently, Wang et al. [2012] propose an efficient algorithm and indexing scheme for top-k retrieval in CP-nets.

Recently, there has been some interest in the combination of Semantic Web technologies with preference representation and reasoning. A combination of conditional preferences (very different from CP-theories) with DL reasoning for ranking objects is presented in [Lukasiewicz and Schellhase, 2007]. There, conditional preferences are exploited in the definition of 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 preference management formalisms closely related to those previously studied for relational databases. The paper also considers skyline and k-rank queries, but the allowed preference statements are more general first-order statements, which are not related to CP-theories. This also comes at the price of higher complexity and data tractability results that hold only for disjunctions of atomic queries and not for CQs like here.

Closest in spirit to this paper is perhaps the preference formalism that combines CP-nets and DLs in [Di Noia et al., 2013], where variable values of CP-nets are satisfiable DL formulas. The main difference with this paper lies in the use of CP-theories here rather than CP-nets, and (more importantly) in the relationship between the ontology and the CPnet/theory. While Di Noia et al. [2013] use ontological axioms to restrict CP-net outcomes, here we use the preference information contained in a CP-theory to inform how answers to queries over the ontology should be ranked. Finally, in the context of information retrieval, in [Boubekeur et al., 2007] Wordnet is used to add semantics to CP-net variables. Another interesting approach to mixing qualitative preferences with Semantic Web technology is presented in [Siberski et al., 2006], where an extension of SPARQL is studied that can encode user preferences in the query. Santhanam et al. [2010] reduce dominance testing in CP-nets to reachability analysis in a graph of outcomes. Mindolin and Chomicki [2011] explore the p-skyline framework, which extends skylines with the notion of attribute importance in preference relations.

7 Summary and Outlook

We have introduced ontological CP-theories (OCP-theories), which are a novel combination of Datalog+/- ontologies with CP-theories. We have defined skyline and k-rank answers for CQs to OCP-theories. We have also provided an algorithm for computing such skyline and k-rank answers. Furthermore, we have provided a host of precise complexity (including several data tractability) results for deciding consistency, dominance, and CQ skyline membership for OCP-theories.

Interesting topics of ongoing and future research include the implementation and experimental evaluation of the presented approach, as well as the investigation and development of optimized special-case and/or approximation algorithms, and the exploration of further tractable cases of OCP-theories.

Acknowledgments This work was supported by the UK EPSRC grant EP/J008346/1 ("PrOQAW"), by a Google European Doctoral Fellowship, by the EU (FP7/2007-2013) ERC grant 246858 ("DIADEM"), by a Yahoo! Research Fellowship, by the grant PON02 00563 3470993 ("VINCENTE"), and funds provided by CONICET and UNSur.