The tastes of a user can be represented in a natural way by using qualitative preferences. In this paper, we describe how to combine ontological knowledge with CP-nets to represent preferences in a qualitative way and enriched with domain knowledge. Specifically, we focus on conjunctive query (CQ) answering under CP-net-based preferences. We define k-rank answers to CQs based on the user's preferences encoded in an ontological CP-net and we provide an algorithm for k-rank answering CQs.
From its inception, the Web has been centered around the idea of linking information to make it more accessible and useful for users. Recently, however, the Web has 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 allows for more precise and rich results in search and query answering tasks, the latter can be used to provide a personalized access to information. This requires new techniques for ranking results based not only on the link structure of documents but also on ontological and user-centred data, i.e., user preferences. These techniques cannot only be used for users but also for computer applications (e.g., preferences over different data sources) and agents (e.g., planning with preferences).
The study of preferences has been carried out in many different areas, such as philosophy, economics, and choice theory. They can be modeled in a qualitative and in a quantitative way, where quantitative preferences are associated with a number representing their worth, while qualitative preferences are related to each other via pairwise comparisons. Users are more comfortable assessing their preferences qualitatively, therefore this work uses qualitative preferences.
In this paper, we focus on the problem of ranking answers for conjunctive queries
(CQs) to Datalog+/– ontologies, based on user preferences encoded in CP-nets [
The main contributions of this paper are briefly as follows: – We introduce ontological CP-nets, which are a novel combination of Datalog+/– with CP-nets, modeling preferences over ground atoms in Datalog+/– ontologies. – We define CP-net-based CQs and their skyline and k-rank answers. We also provide an algorithm for computing k-rank answers to CQs based on the preferences encoded in an ontological CP-net. – We analyze the complexity of k-rank answering CP-net-based CQs, providing precise complexity and tractability results. In detail, we have data tractability, as long as query answering in the underlying classical Datalog+/– ontology is data tractable, the CP-net is a polytree, and the query is fixed-width, bounded, or atomic.
The rest of this paper is organized as follows. In Section 2, we briefly recall Datalog+/– and CP-nets. Section 3 introduces ontological CP-nets, where preferences are expressed over ground atoms from a Datalog+/– ontology, as well as the syntax and the semantics of conjunctive queries (CQs) based on such CP-nets. In Section 4, we describe how to compute k-rank answers to CP-net-based CQs. Section 5 provides general complexity and tractability results. In Section 6, we discuss related work. Finally, Section 7 summarizes the main results and gives an outlook on future work. 2
2.1
Before introducing ontological CP-nets, we recall the basics on Datalog+/– and
CPnets. We first introduce the Datalog+/– ontology language used in our formalism.
We now recall the main concepts of Datalog+/– [
A term t is a constant, null, or variable. An atomic formula (or atom) a has the form P (t1; :::; tn), where P is an n-ary predicate, and t1; :::; tn are terms. A term or atom is ground iff it contains no nulls and no variables. A database (instance) D for a relational schema R is a (possibly infinite) set of atoms with predicates from R and arguments from [ N . A conjunctive query (CQ) over R has the form Q(X) = 9Y (X; Y), where (X; Y) is a conjunction of atoms (possibly equalities, but not inequalities) with the variables X and Y, and possibly constants, but without nulls. We use sign(Q) to denote the set of predicates appearing in . A Boolean CQ (BCQ) over R is a CQ of the form Q(), often written as the set of all its atoms, without quantifiers. Answers to CQs and BCQs are defined via homomorphisms, which are mappings : [ N [ V ! [ N [ V such that (i) c 2 implies (c) = c, (ii) c 2 N implies (c) 2 [ N , and (iii) is naturally extended to atoms, sets of atoms, and conjunctions of atoms. The set of all answers to a CQ Q(X) = 9Y (X; Y) over a database D, denoted Q(D), is the set of all tuples t over for which there exists a homomorphism : X [ Y ! [ N such that ( (X; Y)) D and (X) = t. The answer to a BCQ Q() over a database D is Yes, denoted D j= Q, iff Q(D) 6= ;.
Given a relational schema R, a tuple-generating dependency (TGD) is a firstorder formula of the form 8X8Y (X; Y) ! 9Z (X; Z), where (X; Y) and (X; Z) are conjunctions of atoms over R (without nulls), called the body and the head of , denoted body ( ) and head ( ), respectively. Such is satisfied in a database D for R iff, whenever there exists a homomorphism h that maps the atoms of (X; Y) to atoms of D, there exists an extension h0 of h that maps the atoms of (X; Z) to atoms of D. Since TGDs can be reduced to TGDs with only single atoms in their heads (producing an equivalent set of TGDs), in the sequel, every TGD has w.l.o.g. a single atom in its head. A TGD is guarded iff it contains an atom in its body that contains all universally quantified variables of . A TGD is linear iff it contains only a single atom in its body. As set of TGDs is guarded (resp., linear) iff all its TGDs are guarded (resp., linear).
Query answering under TGDs, i.e., the evaluation of CQs and BCQs on databases
under a set of TGDs is defined as follows. For a database D for R, and a set of TGDs
on R, the set of models of D and , denoted mods(D; ), is the set of all (possibly
infinite) databases B such that (i) D B and (ii) every 2 is satisfied in B. The set
of answers for a CQ Q to D and , denoted ans(Q; D; ), is the set of all tuples a
such that a 2 Q(B) for all B 2 mods(D; ). The answer for a BCQ Q to D and is
Yes, denoted D [ j= Q, iff ans(Q; D; ) 6= ;. Query answering under general TGDs
is undecidable [
A negative constraint (or simply constraint) is a first-order formula of the form 8X (X) ! ?, where (X) (called the body of ) is a conjunction of atoms over R (without nulls). Under the standard semantics of query answering of BCQs in Datalog+/– with TGDs, adding negative constraints is computationally easy, as for each constraint 8X (X) ! ?, we only have to check that the BCQ 9X (X) evaluates to false in D under ; if one of these checks fails, then the answer to the original BCQ Q is true, otherwise the constraints can simply be ignored when answering the BCQ Q.
As another component, the Datalog+/– language allows for special types of
equalitygenerating dependencies (EGDs). Since they can also be modeled via negative
constraints, we omit them here, and we refer to [
Datalog+/– Ontologies. A Datalog+/– ontology O = (D; ), where = T [ E [
NC, consists of a finite database D over , a set of TGDs T , a set of non-conflicting EGDs E , and a set of negative constraints NC. We say O is guarded (resp., linear) iff T is guarded (resp., linear).
Example 1. Consider the following relational schema R representing booking information about airlines and their flights: flight(id; d-airport; a-airport; dTime; aTime; plane-id; company); plane(id; capacity); dPlace(city; airport); book(flight-id; departure-date; class): For example, the flight relation contains information about the flight such as the departure airport, plane id and the company that is responsible; A simple Datalog+/– ontology O = (D; ) for flights is given below. Intuitively, the database D encodes that for example f1, f2 and f3 are 3 flights and ma,na are arrival times, etc. The set of constraints encodes the domain and range of flights, the fact that a flight cannot have the same departure and arrival city, and an inverse relation between flight and hasFlight.
D =fflight(f1; l2; l3; nd; na; p2; a1); book(f1; d1; e); aTime(ma);
flight(f2; l2; l1; md; ma; p1; a2); book(f2; d1; b); aTime(na);
flight(f3; l3; l2; nd; na; p3; a2); book(f3; d1; b); dTime(nd);
dTime(md); class(b); class(e); dPlace(c1; l1); airline(a1);
dPlace(c1; l2); dPlace(c2; l3); airline(a2)g;
= fflight(A; B; C; D; E; F; G) ! 9Y dPlace(Y; B)
flight(A; B; C; D; E; F; G) ! dTime(D) ^ aTime(E)
flight(A; B; C; D; E; F; G) ! 9Y plane(F; Y )
flight(A; B; C; D; E; F; G) ! 9X airline(G; X)
flight(A; B; B; D; E; F; G) ! ?
flight(A; B; C; D; E; F; G) ! hasFlight(G; A)
book(A; B; C) ! 9X hasFlight(X; A)
book(A; B; C) ! class(C)g:
Conditional preferences networks (CP-nets) [
We assume a set of variables V, where each variable Xi 2 V is associated with a domain of values, denoted dom(Xi). The domain of values x of a set of variables X = fX1; : : : ; Xkg V, denoted dom(X), is defined as dom(X1) dom(Xk). If X = V, then x is a complete assignment (outcome), otherwise it is a partial assignment. If x and y are assignments to disjoints sets X and Y, then we denote the combination of x and y by xy.
A preference relation is a total pre-order over the set of outcomes. We write o1 o2 to state that o1 is strictly preferred over o2 while we write o1 o2 if o1 is strictly or equally preferred to o2. We say that o2 is dominated by o1 if o1 o2 and that o2 is directly dominated by o1, o1 d o2 if o2 is dominated by o1 and there is no outcome o such that o1 o and o o2. If there is no outcome o such that o o1 we say that o1 is undominated. If both o1 o2 and o2 o1 hold, we say there is an indifference situation.
A conditional preference is represented as (x x0 j z) meaning that “given z, I prefer x over x0”. Let X, Y and Z be nonempty sets that partition V and a preference relation over dom(V). X is conditionally preferentially independent (CPI) of Y given Z iff for all x, x’ 2 dom(X); y; y0 2domY), z 2dom(Z), we have xyz x0yz iff xy0z x0y0z. Using CP-nets, one can model CPI statements. Formally, a CP-net N over V consists of an annotated directed graph G over fX1; : : : ; Xng in which nodes stand for problem variables and edges represent conditioning among variables Xi. Each node Xi is annotated with a conditional preference table CP T (Xi), that associates a total order
Xiju with each instantiation u of Xi’s parents P a(Xi), i.e., u 2 dom(P a(Xi)). In the sequel, we use o 2 N to denote that o is an outcome of N . The following are the two main computational tasks for CP-nets: – Dominance query: given a CP-net and two outcomes o1 and o2, decide whether o1 o2.
– Outcome optimization: given a CP-net, compute an undominated outcome. Example 2. The CP-net in Figure 1 encodes that the morning departure (md) is preferred over night departure (nd), and morning arrival (ma) is preferred over night arrival (na). Business class (b) is preferred over economy class (e) when there is a night departure and a morning arrival, and the other way around, otherwise.
To establish an order among possible outcomes of a CP-net, we introduce the notion of worsening flip. This is a change in the value of a variable that worsens the satisfaction of the user’s preferences. For example, in Figure 1, we have that md ma e md na e. Based on the notion of worsening flip, we can derive a preference graph representing the transitive reduction of the preference relations among possible outcomes. In Figure 2, the preference graph related to the CP-net in Figure 1 is represented. Given two outcomes o1 and o2, an edge going from o1 to o2 means that o1 o2. md nd class In this section, we introduce CP-Datalog+/–, which is an extension of Datalog+/– by CP-net based preferences. We first introduce the syntax and then the semantics of CPDatalog+/–. We first define CP-net-based conjunctive queries, which are conjunctive queries along with a CP-net for defining a preference relation among the ground instances of the queries’ atoms and thus among the queries’ answers. To this end, we introduce ontological CP-nets, which informally define preference relations between conjunctions of ground atoms (which have as arguments constants from as well as the special constant , which is a placeholder for any null). The preference relation is defined relative to an underlying ontology.
Definition 1 (Ontological CP-Net). Let O be a Datalog+/– ontology over the set of constants . An ontological CP-net over O is a CP-net N , which has as set of variables V a set of predicates from O, and as the domain of each P 2 V, denoted dom(P ), a finite set of at least two different atoms P (t1; : : : ; tk) with t1; : : : ; tk 2 [ f g. dP lace airline class
Observe that every outcome o of an ontological CP-net is a conjunction of grounded atoms. The following example illustrates the concept of ontological CP-net. Example 3. Given the ontology O in Example 1, an ontological CP-net N over O is shown in Figure 3, where V = fdPlace; airline; dTime; aTime; classg and, for instance, dom(aTime) = fairline(a1); airline(a2)g. For clarity, in the CPT associated with the variable P , we use ti to denote P (ti). Then, for instance, ti tj means P (ti) P (tj).
The CP-net shown encodes that the departure place (dPlace) that maps city c1 with airport location l1 is more preferred than (c1; l2), that is more preferred than (c3; l3) (this might be dependent on where the user lives). Now, given the departure place, there are preferences on the departure time (how long it takes to reach the place, etc.). Thus, if the departure place is (c1; l1) or (c3; l3), then a night departure (nd) is preferred over a morning departure (md). If the departure place is (c1; l2), then a morning departure is preferred over a night departure. Business class (b) is preferred over economy class (e) when there is a night departure and a morning arrival, and the other way around, otherwise. Airline a1 is preferred over a2.
As a consequence of the underlying ontology, some of the outcomes of an ontological CP-net may be inconsistent, and some other outcomes may be ontologically equivalent. We thus have to assure that the preference relation encoded in an ontological CP-net is well-defined, which is expressed in the notion of consistency of ontological CP-nets. In the sequel, let + denote the transitive closure of the preference relation induced by the ontological CP-net for its outcomes, and + its restriction to the classes of equivalent consistent outcomes. The notion of consistency of CP-nets then describes the acyclicity of this preference relation + and the +-incomparability of any two equivalent consistent outcomes. That is, to obtain +, we remove from + all inconsistent outcomes relative to the ontology O, and we do not admit equivalent outcomes relative to O.
over , and let N be an ontological CP-net over O. Then, N is consistent iff (i) + is acyclic, and (ii) o1 under O.
+ o2 for no two outcomes o1 and o2 of N that are equivalent
We next define CP-Net-based conjunctive queries, which are informally conjunctive queries along with an ontological CP-net for defining a preference relation among the queries’ answers.
Then, a CP-net-based conjunctive query (CP-net-based CQ) (Q; N ) consists of a conjunctive query Q and a consistent ontological CP-net N over O such that all variables in N occur in Q.
W.l.o.g., all the atoms in Q have different predicates (which can be easily achieved by a predicate renaming), and thus there exists a bijection from atoms in Q to the vertices of N . 3.2
We next define the semantics of CP-net-based CQs (Q; N ). The following definition formalizes answers to Q in the usual way and relates these answers to the outcomes of the CP-net N .
Definition 4 (Answer to a CP-Net-based CQ). Let O = (D; ) be a Datalog+/– ontology, and let (Q; N ) be a CP-net-based CQ with Q(X) = 9Y (X; Y). Then, the set of all answers for (Q; N ) to O under the outcome o of N , denoted ans(Q; N ; O; o), is the set of all tuples a over for which there exists a homomorphism : X [ Y ! [
N such that (i) ( (X; Y)) chase(D; ) and (X) = a, and (ii) o 0( (X; Y)), where (a) 0jX = jX, (b) 0(Y ) = (Y ) for all Y 2 Y such that (Y ) 62 N and (c) 0(Y ) = for all Y 2 Y such that (Y ) 2 N . The set of all answers for (Q; N ) to O, denoted ans(Q; N ; O), is the set of all answers for (Q; N ) to O under some outcome o of N .
Example 4. Consider again Example 3, which describes a consistent ontological CP-net N , and let Q(B; A; Z; C) =
9X; Y dPlace(X; B) ^ airline(A) ^ dTime(Z) ^ aTime(Y ) ^ class(C): Then, (Q; N ) is a CP-net-based CQ, and hl1; a1; nd; bi is an answer to Q – note that its outcome in N is o = fdPlace(c1; l1); airline(a1); dTime(nd); aTime(ma); class(b)g.
We now focus on how to order these answers based on the preferences of the user.
We concentrate on skyline queries [
We next define skyline and k-rank answers to CP-net-based CQs.
Definition 6 (Skyline Answer). Let O = (D; ) be a Datalog+/– ontology, and let (Q; N ) be a CP-net-based CQ with Q(X) = 9Y (X; Y). A skyline answer for (Q; N ) to O is any tuple a in ans(Q; N ; O; o) for some undominated outcome o of N .
Observe that skyline answers are not unique. Indeed, we may have more than one undominated outcome o of N , and we may also have more than one homomorphism that satisfies the conditions (i) and (ii) of Definition 4 for the same undominated outcome o of N .
Definition 7 (k-Rank Answer). Let O = (D; ) be a Datalog+/– ontology, and let (Q; N ) be a CP-net-based CQ with Q(X) = 9Y (X; Y). A k-rank answer for (Q; N ) to O outside a set of ground atoms S is a sequence ha1; : : : ; aki such that either: (a) a1; : : : ; ak are k different skyline answers for (Q; N ) to O that do not belong to S, if m > k such answers exist; or (b) (1) a1; : : : ; ai are all i different skyline answers for (Q; N ) to O that do not belong to S, and (2) hai+1; : : : ; aki is a k i-rank answer for (Q; N fog) to O outside S [ fa1; : : : ; aig, where o is an undominated outcome of N , otherwise. A k-rank answer for (Q; N ) to O is a k-rank answer for (Q; N ) to O outside ;.
Note that when no answer for (Q; N ) to O exists, then hi is its unique k-rank answer. A k-rank answer is a sequence of k answers to a CP-net-based CQ ranked by following the order among outcomes induced by the ontological CP-net. Given two following answers in the sequence, they can be related to the same outcome (as for the skyline situation, the answer related to a single outcome may not be unique) or to two different outcomes in directly dominated relation. Finally, the computed answer is not deterministic. Indeed, a CP-net induces a partial order over the set of possible outcomes. 4
We now present an algorithm to compute k-rank answers in an ontological CP-netbased setting. The procedure in Algorithm 1 exploits + (the transitive closure of outcomes restricted to the class of equivalent consistent outcomes) to incrementally compute ordered answers to a conjunctive query Q over an ontology O and an ontological CP-net N for O. The algorithm stops the computation of answers when it reaches k different answers to Q. The most preferred solutions are the ones related to the undominated outcome of N . This is the reason why the computation starts by adding ou to the set Outcomes (line 7). Then, the algorithm incrementally adds directly dominated outcomes to Outcomes and finds answers to Q that are related to them. To preserve the preference order in +, in line 9, there is a check needed to avoid that an outcome in Outcomes is selected before we have answers related to other better outcomes.
For a better understanding of line 9, we refer to the preference graph in Figure 2. Suppose that Outcomes = fmd ma e, md ma b, nd ma b, md na b, nd ma b, nd na b, Input: O is a Datalog+/– ontology, (Q; N ) is a CP-net-based CQ, and k > 0.
Output: k-rank answers fa1; : : : ; akg to (Q; N ). md na eg and Checked = fmd ma e, md ma b, nd ma b, md na bg. Then, we have to select an outcome in fnd ma b; nd na b; md na eg. By Figure 2, nd na b is the worst choice. Indeed, although it is directly dominated by nd ma b, it is also dominated (not directly) by md na e.
Note that we may have two sources of non-determinism in the algorithm. In particular, in line 9, we may choose arbitrarily among different incomparable outcomes. In the situation that we have just discussed, we can select either nd ma b or md na e. The other source of non-determinism is in line 11. Here, we may have multiple equivalent (from the outcomes ordering point of view) , and after selecting some of them, we reach length(Result ) = k.
Finally, an algorithm to compute skyline answers can be easily modeled by stopping the computation of answers to the ones related to the undominated outcome ou. 5
In this section, we analyze the computational complexity of skyline and k-rank answering CP-net-based CQs (Q; N ) to Datalog+/– ontologies. We also delineate some tractable special cases. 5.1
The following theorem shows that k-rank answering CP-net-based CQs (Q; N ) to
linear (resp., guarded) Datalog+/– ontologies is both complete for PSPACE (resp.,
2EXPTIME) and that hardness holds even when Q has a bounded width, is fixed, or is an
atom. The lower complexity bounds follow from the result that the more specialized
problem of answering BCQs to linear (resp., guarded) Datalog+/– ontologies is
complete for PSPACE (resp., 2EXPTIME) [
Theorem 1. Let k > 0 be fixed. Given a linear (resp., guarded) Datalog+/– ontology O and a CP-net-based CQ (Q; N ), computing the k-rank answer for (Q; N ) is complete for PSPACE (resp., 2EXPTIME). Hardness holds even when Q has a bounded width, is fixed, or is an atom.
The next theorem shows that k-rank answering CP-net-based CQs (Q; N ) to
linear (resp., guarded) Datalog+/– ontologies in the data complexity (where is fixed) is
both complete for PSPACE. The lower complexity bounds follow from the result that
the more specialized problem of deciding dominance between two outcomes in a
standard CP-net is PSPACE-complete [
Theorem 2. Let k > 0 be fixed. Given a linear or guarded Datalog+/– ontology O, and a CP-net-based CQ (Q; N ), computing the k-rank answer for (Q; N ) is data complete for PSPACE. 5.2
We now delineate special cases where skyline and k-rank answering CP-net-based CQs
(Q; N ) to Datalog+/– ontologies O = (D; ) is tractable in the data complexity (where
is fixed). More precisely, the following result shows that these two problems are
tractable in the data complexity, when (i) O is linear or guarded, (ii) N is a polytree,
and (iii) Q has a bounded width, is fixed, or is an atom (which also implies that N is
bounded). It follows from the results (1) that answering bounded-width, fixed, or atomic
BCQs to linear or guarded Datalog+/– ontologies can be done in polynomial time [
Theorem 3. Let k > 0 be fixed. Given a linear or guarded Datalog+/– ontology O, and a CP-net-based CQ (Q; N ), where N is a polytree, and Q has a bounded width, is fixed, or is an atom, computing the skyline and the k-rank answer for (Q; N ) can both be done in polynomial time in the data complexity. 6
Modeling and dealing with preferences in databases has been studied for almost three
decades, since the seminal work of [
In the philosophical tradition, preferences are usually expressed over mutually
exclusive “worlds”, such as truth assignments to formulas. The work of [
Recently, there has been some interest regarding the combination of Semantic Web
technologies with preference representation and reasoning. A combination of
conditional preferences (very different from CP -nets) with description logic (DL) reasoning
for ranking objects is presented in [
Closest in spirit to this paper is perhaps the preference formalism that combines
CP-nets and DLs in [
We have introduced ontological CP-nets, which are a novel combination of Datalog+/– ontologies with CP-nets. We have defined CP-net-based CQs and their skyline and krank answers on top of ontological CP-nets. We have also provided an algorithm for computing k-rank answers to CP-net-based CQs. Furthermore, we have provided precise complexity and tractability results for this problem.
Interesting topics of ongoing and future research include the implementation and experimental evaluation of the approach, as well as a more complete complexity analysis for other Datalog+/– variants and ontology languages as well as other special cases of CP-nets.
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, and by the grant PON02 00563 3470993 (“VINCENTE”).