Preference-Based Query Answering in Datalog+/- Ontologies

1 Introduction

In the past two decades, there has been a rapid development in the research and elaboration of technologies to make an effective use of Web data. For instance, ontology languages, along with associated query answering algorithms, have been extensively studied with computational tractability in mind in order to guarantee their applicability on large-scale knowledge bases. However, there remains much work to be done in central areas, such as search, where the state of the art is still centered in receiving keywords from a user and returning a set of links to Web documents. The main drawback to this paradigm is that the quality of the set of answers is much more important to users than the quantity. The evolution that seeks to address these issues is called semantic search, and is focused on identifying objects on the Web instead of documents and keywords. The other revolution that has recently taken place in the Web is often referred to as the Social Web or Web 2.0, and is centered around a system composed of platforms that users adopt to share information and collaborate in a social environment. This makes the main tenets of semantic search ever more relevant for virtually all activities on the Web, since the fundamentally human component of these systems makes each user's personal preferences have a much more prevalent role than what was observed prior to this paradigm shift. The current challenge for Web search is thus inherently linked to leveraging the social components of Web content in order to develop some form of semantic search and query answering on the Web as a whole.

Preferences have long been studied as an important part of people's daily lives, and have thus received much attention in many areas of study such as philosophy (as early as Aristotle), choice theory (for instance, in rational decision making), and certain social sciences (such as certain areas dealing with voting, auctions, and other mechanisms for social choice). Though these and many other avenues of study have naturally led to the study of preferences in computer science, the most relevant to our work is that of their incorporation into query answering mechanisms. To date (and to our knowledge), the state of the art in this respect is centered around relational databases. The seminal work in preference-based query answering was that of [Lacroix and Lavency, 1987], in which the authors extend the SQL language to incorporate user preferences, showing that the resulting formalism could be translated into the domain relational calculus. Preference formulas were introduced in [Chomicki, 2003], where a logical formalism is proposed that allows an embedding of preference specifications into SQL through a winnow operator that is parameterized by a preference formula; the winnow operator is a generalization of the skyline operator, first introduced in [B¨orzs¨onyi et al., 2001]. Perhaps closest in nature to our approach is that of preference Datalog programs [Govindarajan et al., 2001], which are a restriction of preference logic programs [Govindarajan et al., 1995] that contain no uninterpreted function symbols and extend classical Datalog with constructs for determining which predicates must be optimized along with the optimization criteria (i.e., the set of preferences); the authors develop algorithms based on optimizations of the basic bottom-up evaluation approach to query answering based on the set of input preferences. Also related are efforts that incorporate preferences into answer set programming frameworks (see, for instance, [Brewka, 2006]). For a recent survey of preference-based query answering formalisms, see [Stefanidis et al., 2011]; finally, [Kießling et al., 2011] describes the Preference SQL system, which has been commercially available since 1999.

In this paper, we propose a novel integration of ontology languages with preference management mechanisms by developing an extension of the Datalog+/- family of ontology languages [Cal`ı et al., 2012] with preference specification languages that are closely related to those previously studied in the relational databases literature. The main contributions of this paper are: (i) the introduction of the PrefDatalog+/- framework, the first (to our knowledge) combination of ontology languages with preferences as in relational databases; (ii) the development of algorithms for answering both skyline and k-rank queries (the latter is a generalization of top-k queries) for disjunctions of atomic queries (based on a novel augmented chase procedure) and conjunctive queries (based on the classical chase procedure and leveraging algorithms from related work in relational databases), along with proofs of correctness and running times showing that answering disjunctions of atomic queries (DAQs) in PrefDatalog+/- can be done in polynomial time in the data complexity, i.e., within the same complexity bounds as in relational databases, as long as query answering in the underlying classical ontology can also be done in polynomial time in the data complexity; and (iii) a complexity result showing that CQ answering is intractable in general.

The rest of this paper is organized as follows. In Section 2, we present preliminary concepts on classical Datalog+/- and preference specification formalisms from relational databases. Section 3 introduces the syntax and semantics of PrefDatalog+/-, along with the two kinds of queries that we focus on in this work. Section 4 presents algorithms for skyline and k-rank queries to PrefDatalog+/- ontologies, focusing especially on DAQs; though an intractability result is proved for CQs, we also discuss how algorithms from relational databases can be leveraged for these queries as well. Finally, in Section 5, we conclude and discuss future work.

2 Preliminaries

We now briefly recall some necessary background concepts.

2.1 Datalog+/-

First, we briefly recall some basics on Datalog+/- [Cal`ı et al., 2012], namely, on relational databases, (Boolean) conjunctive queries ((B)CQs), tuple-generating dependencies (TGDs), negative constraints, the chase, and ontologies in Datalog+/-.

Databases and Queries. We assume (i) an infinite universe of (data) constants Δ (which constitute the "normal" domain of a database), (ii) an infinite set of (labeled) nulls ΔN (used as "fresh" Skolem terms, which are placeholders for unknown values, and can thus be seen as variables), and (iii) an infinite set of variables V (used in queries, dependencies, and constraints). Different constants represent different values

(unique name assumption), while different nulls may represent the same value. We assume a lexicographic order on Δ ∪ ΔN, with every symbol in ΔN following all symbols in Δ. We denote by X sequences of variables X1, . . . ,Xk with k⩾0. We assume a relational schema R, which is a finite set of predicate symbols (or simply predicates). 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 database (instance) D for a relational schema R is a (possibly infinite) set of atoms with predicates from R and arguments from Δ. A conjunctive query (CQ) over R has the form Q(X)=∃YΦ(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. 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∈Δ implies μ(c)=c, (ii) c∈ΔN implies μ(c)∈Δ∪Δ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) = ∃Y Φ(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 |=Q, iff Q(D) ̸=∅.

Given a relational schema R, a tuple-generating dependency (TGD) σ is a first-order formula ∀X∀YΦ(X,Y) → ∃ZΨ(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 h′ of h that maps the atoms of Ψ(X, Z) to atoms of D. All sets of TGDs are finite here. Since TGDs can be reduced to TGDs with only single atoms in their heads, 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 σ. The leftmost such atom is the guard (atom) of σ.

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 σ∈Σ 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 ∈Q(B) for all B ∈mods(D, Σ). The answer for a BCQ Q to D and Σ is Yes, denoted D ∪ Σ |=Q, iff ans(Q,D,Σ) ̸=∅. Note that query answering under general TGDs is undecidable [Beeri and Vardi, 1981], even when the schema and TGDs are fixed [Cal`ı et al., 2008]. Decidability of query answering for the guarded case follows from a bounded tree-width property. The data complexity of query answering in this case is P-complete.

Negative constraints (or simply constraints) γ are firstorder formulas ∀XΦ(X)→⊥, where Φ(X) (called the body of γ) is a conjunction of atoms (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 ∀XΦ(X)→⊥, we only have to check that the BCQ Φ(X) evaluates to false in D under Σ; if one of these checks fails, then the answer to the original BCQ Q is false, otherwise the constraints can simply be ignored when answering the BCQ Q.

As another component, the Datalog+/- language allows for special types of equality-generating dependencies (EGDs). Since they can also be modeled via negative constraints, we omit them here, and we refer to [Cal`ı et al., 2012] for their details. We usually omit the universal quantifiers in TGDs and negative constraints, and we implicitly assume that all sets of dependencies and/or constraints are finite.

The Chase. The chase was first introduced to enable checking implication of dependencies, and later also for checking query containment. By "chase", we refer both to the chase procedure and to its output. The TGD chase works on a database via so-called TGD chase rules.

TGD Chase Rule. Let D be a database, and σ be a TGD of the form Φ(X,Y) → ∃ZΨ(X, Z). Then, σ is applicable to D if there exists a homomorphism h that maps the atoms of Φ(X,Y) to atoms of D. Let σ be applicable to D, and h1 be a homomorphism that extends h as follows: for each Xi ∈X, h1(Xi)=h(Xi); for each Zj ∈Z, h1(Zj)=zj, where zj is a "fresh" null, i.e., zj ∈ΔN, zj does not occur in D, and zj lexicographically follows all other nulls already introduced. The application of σ on D adds to D the atom h1(Ψ(X, Z)) if not already in D.

The chase algorithm for a database D and a set of TGDs Σ consists of an exhaustive application of the TGD chase rule in a breadth-first (level-saturating) fashion, which outputs a (possibly infinite) chase for D and Σ. Formally, the chase of level up to 0 of D relative to Σ, denoted chase0 (D,Σ), is defined as D, assigning to every atom in D the (derivation) level 0. For every k⩾1, the chase of level up to k of D relative to Σ, denoted chasek (D,Σ), is constructed as follows: let I1, . . . , In be all possible images of bodies of TGDs in Σ relative to some homomorphism such that (i) I1, . . . , In⊆chasek-1 (D,Σ) and (ii) the highest level of an atom in every Ii is k - 1; then, perform every corresponding TGD application on chasek-1 (D,Σ), choosing the applied TGDs and homomorphisms in a (fixed) linear and lexicographic order (resp.), and assigning to every new atom the level k. The chase of D relative to Σ, denoted chase(D, Σ), is defined as the limit of chasek (D,Σ) for k→∞.

The (possibly infinite) chase relative to TGDs is a universal model, i.e., there exists a homomorphism from chase(D,Σ) onto every B∈mods(D,Σ) [Cal`ı et al., 2012]. This implies that BCQs Q over D and Σ can be evaluated on the chase for D and Σ, i.e., D∪Σ |=Q is equivalent to chase(D, Σ) |= Q. For guarded TGDs Σ, such BCQs Q can be evaluated on an initial fragment of chase(D,Σ) of constant depth k · |Q|, which is possible in polynomial time in the data complexity.

Datalog+/- Ontologies. A Datalog+/- ontology KB =(D, Σ), where Σ=ΣT ∪ ΣNC, consists of a database D, a set of TGDs ΣT , and a set of negative constraints ΣNC. We say KB

is guarded (resp., linear) iff ΣT is guarded (resp., linear). Example 1 (used in the sequel as a running example) illustrates a simple Datalog+/- ontology.

Example 1 Let O=(D, Σ) be a simple ontology describing gift ideas for friends:

This ontology considers two kinds of book and video game genres, and states that books and puzzles are categorized under an "educational" label. The database D provides some instances for each of these genres. ■

2.2 Preference Relations via Preference Formulas

Though the PrefDatalog+/- formalism introduced in Section 3 allows essentially any preference framework to be used, in this paper, we adopt a formalism slightly generalizing the preference formulas approach that was proposed in [Chomicki, 2003] to develop the concrete approaches to query answering discussed in Section 4.

In the following, let ΔPref be a finite set of constants, RPref be a finite set of predicate names, and VPref be an infinite set of variables; we denote with HPref the Herbrand base relative to these sets, respectively. A preference relation is any binary relation ≻⊆HPref×HPref. Note that, slightly generalizing the framework in [Chomicki, 2003], preference relations can be defined between atoms corresponding to different predicates, and that formulas are not "iff" statements.

Definition 2 Let a1 and a2 be atoms over RPref, VPref, and ΔPref. A preference formula pf is of the form "a1 ≻ a2 if C(a1, a2)", where C(a1, a2) is a first-order formula. We call C(a1, a2) the condition of pf, denoted cond(pf).

Intuitively, a preference formula pf : a1 ≻ a2 if C(a1, a2) defines a preference relation ≻pf such that a1 ≻pf a2 whenever C(a1, a2) holds. The preference relation defined via a set of preference formulas P is denoted by ≻P .

Example 3 Following the same topic of Example 1, the following formulas may represent a specific friend's preferences for children's gifts:

For instance, the formula C1 states that educational gifts are preferable to video games (unconditionally), while C4 states that an educational gift that is a puzzle is preferable to one that is a fantasy book. ■

3 PrefDatalog+/-: Syntax and Semantics

Considering the basic setup from Section 2, we now present the PrefDatalog+/- language.

Syntax. Recall that we have (as discussed in Section 2), the logical languages for ontologies and preferences. For the former, we have an infinite universe of constants ΔOnt, an infinite set of variables VOnt, and a finite set of predicate names ROnt; analogously for the latter, we have a finite set of constants ΔPref, an infinite set of variables VPref, and a finite set of predicate names RPref. In the following, we assume w.l.o.g. that RPref ⊆ ROnt, ΔPref ⊆ ΔOnt, and VPref ⊆ VOnt. These sets give rise to corresponding Herbrand bases consisting of all possible ground atoms that can be formed, which we denote by HOnt and HPref, respectively. Clearly, we have HPref ⊆ HOnt, meaning that preference relations are defined over a subset of the possible ground atoms.

Definition 4 Let O be a Datalog+/- ontology and P be a set of preference formulas with Herbrand bases HOnt and HPref, respectively. A preference-based Datalog+/- ontology (PrefDatalog+/- ontology, or knowledge base) is of the form KB = (O, P ), where HPref ⊆ HOnt.

If O is a guarded Datalog+/- ontology, we say that KB is a guarded PrefDatalog+/- ontology.

Semantics. The semantics of PrefDatalog+/- arises as a direct combination of the semantics of Datalog+/- and that of preference formulas. A knowledge base KB =(O, P) satisfies a1 ≻P a2, denoted KB |=a1 ≻P a2, iff (i) O |=a1 and O |=a2, and (ii) |= ∨pfi∈P cond(pfi )(a1, a2). Intuitively, the consequences of KB are computed in terms of the chase for the classical Datalog+/- ontology O, and the set of preference formulas P describes the preference relation over pairs of atoms in HOnt. The following is a simple example.

Example 5 Let KB =(O, P) be a PrefDatalog+/- ontology, with the ontology O from Example 1 and the set of preference formulas P from Example 3. Then, KB |=educ(b1) ≻P vidGame(v1), since O |=educ(b1), O |=vidGame(v1), and C1 ∈P allows us to conclude that educ(b1) ≻P vidGame(v1). On the other hand, KB ̸|= educ(b1) ≻P educ(b2), since condition (ii) is not satisfied. ■

Queries. In this paper, we are interested in two kinds of preference-based queries that can be issued over PrefDatalog+/- ontologies: skyline and k-rank. To define answers to such queries, we adopt the following definitions from classical logic. A substitution is a function from variables to variables or constants. Two sets S and T unify via a substitution θ iff θS = θT , where θA denotes the application of θ to all variables in all elements of A (here, θ is a unifier). A most general unifier (mgu) is a unifier θ such that for all other unifiers ω, a substitution σ exists such that ω=σ ◦ θ. We consider two kinds of classical queries: conjunctive queries (CQs) and disjunctive atomic queries (disjunctions of atoms - DAQs).

Definition 6 Consider the PrefDatalog+/- ontology KB = (O, P), k ⩾ 0, and DAQ Q(X) = q1(X1) ∨ · · · ∨ qn(Xn), where the qi's are atoms and X1 ∪ · · · ∪Xn = X. The set of skyline answers to Q is defined as: {θqi |O |=θqi and ∄θ′ such that O |=θ′ qj and θ′ qj ≻P θqi, with 1 ⩽ i, j ⩽ n}, where θ, θ′ are mgu's for the variables in Q(X). A k-rank answer to Q(X) is defined for transitive relations ≻P as a sequence of maximal length of mgu's for X: S = (θ1, . . . , θk′ ) such that O |= θiQ for 1 ⩽ i ⩽ k′ ⩽ k, and S is built by subsequently appending the skyline answers to Q, removing these atoms from consideration, and repeating the process until either S = k or no more answers to Q remain.

In Definition 6, note that k-rank answers are only defined when the preference relation is transitive; this kind of answer can be seen as a generalization of traditional top-k answers [Stefanidis et al., 2011] that are still defined when ≻P is not a weak order, and their name arises from the concept of rank introduced in [Chomicki, 2003].

Intuitively, for DAQs, both kinds of answers can be seen as atomic consequences of O that satisfy the query: the skyline answers can be seen as sets of atoms that are not dominated by any other such atom, while k-rank answers are k-tuples sorted according to the preference relation. We refer to these as answers in atom form.

Example 7 Consider again the ontology KB =(O, P) from Example 5 and the queries Q1(X, Y )=book(X, Y ), and Q2(X)=educ(X); the ≻P relation is depicted in Figure 1 (dotted lines). Then, the set of skyline answers to Q1 is {book(b1, asimov)}, while for Q2 it is {educ(p1), educ(b1), educ(b2)}. A 3-rank answer to Q1 is (book(b1, asimov), book(b2, asimov), book(b3, tolkien)). For Q2, a 3-rank answer is (educ(p1), educ(b1), educ(b2)). Finally, the query Q3 = puzzle(X) ∨ vidGame(X) yields {puzzle(p1), vidGame(v2)} as skyline answers, and a 3-rank answer is {puzzle(p1), vidGame(v2), vidGame(v1)}. ■

Finally, we have a result relating k-rank to the traditional top-k queries (cf. [Stefanidis et al., 2011]).

Proposition 8 Let KB = (O, P ) be a PrefDatalog+/- ontology, Q be a DAQ or a CQ, and k ⩾ 0. If ≻P is a weak order, then k-rank answers are equal to top-k answers (modulo ordering of incomparable elements).

Conjunctive Queries. In the case of (non-atomic) conjunctive queries, the substitutions in answers no longer yield single atoms but rather sets of atoms; therefore, to answer such queries relative to a preference relation, we must extend the preference specification framework to take into account sets of atoms instead of individual ones. One such approach was proposed in [Zhang and Chomicki, 2011], where a mechanism to define a preference relation over tuple sets ≻PS: 2HPref × 2HPref is introduced. Though this is not the focus of this paper, in Section 4.2 we treat their complexity and briefly discuss how methods from the relational databases literature can be applied to answer them.

4 Preference-Based Query Answering

In this section, we propose algorithms for answering queries to PrefDatalog+/- ontologies; we start with DAQs and then move on to the conjunctive case.

4.1 Disjunctive Atomic Queries

We begin by introducing a structure that is used in preferencebased query answering. Next, we investigate algorithms for skyline and k-rank query answering for DAQs.

The Preference-Augmented Chase (prefChase). To compute skyline and k-rank answers to queries over a PrefDatalog+/- ontology KB =((D,Σ), P), we make use of a data structure called the chase forest for D, Σ, and the query Q [Cal`ı et al., 2012], which is defined as the directed graph consisting of (i) for every a∈D, one node labeled with a, and (ii) for every node labeled with a∈chase(D,Σ) and for every atom b∈chase(D,Σ) that is obtained from a and possibly other atoms by a one-step application of a TGD σ∈Σ with a as guard, one node labeled with b along with an edge from the node labeled with a. Here, we propose an augmented chase forest, comprised of the necessary finite part of the chase forest relative to a given query that is augmented with an additional kind of edge that we call preference edges, which occur between nodes labeled with a, b∈chase(D,Σ) iff a ≻P b. Finally, when an edge is introduced between nodes whose labels satisfy Q, the node with the incoming edge is marked. Figure 1 shows prefChase(KB, Q) for the PrefDatalog+/- ontology from Example 5; for illustrative reasons, markings for three different queries have been included in the figure: book(X, Y ) (check mark), educ(X) (star), and vidGame(X) (diamond).

Theorem 9 If KB =((D,Σ), P) is a guarded PrefDatalog+/- ontology and Q a DAQ, prefChase(KB,Q) can be computed in polynomial time in the data complexity.

Proof sketch. The prefChase(KB,Q) structure consists of the chase forest for (D,Σ) with additional preference edges between nodes labeled with atoms in the ≻P relation. The construction of the classical chase forest can be done in polynomial time in the data complexity for guarded TGDs [Cal`ı et al., 2012]. Now, computing the preference edges and node markings is done by iterating through all pairs (ai, aj) of nodes, testing in turn all formulas pf ∈P to see if |=

Algorithm 1: Skyline(KB = ((D, Σ), P ), Q) Input: PrefDatalog+/- ontology KB and DAQQ(X). Output: Set of skyline answers {a1, . . . , ak} to Q. 1. Initialize Res as an empty set of ground atoms; 2. C:= prefChase(KB, Q); 3. For each atom a labeling node v in C do begin 4. If a |= Q and v is unmarked then 5. Res:= Res ∪ {a}; 6. end; 7. return Res.

Algorithm 2: k-Rank(KB = ((D, Σ), P ), Q, k) Input: PrefDatalog+/- ontology KB, DAQQ(X), k ⩾ 0. Output: k-rank answer (a1, . . . , ak′ ) to Q. 1. Initialize Res as an empty vector of ground atoms; 2. C:= prefChase(KB, Q); 3. i:= k; 4. While i > 0 do begin 5. S:= Skyline(KB,Q); 6. Append S to Res (arbitrary order); 7. Remove S fromC along with all associated edges; 8. Identify marked nodes that no longer have incoming preference edges and change them to unmarked; 9. i:= i - |S|; 10. End; 11. Return truncate(Res, k).

Cond(pf)(ai, aj), which, since P is fixed in the data complexity, is possible in quadratic time in the size of the chase forest in the data complexity. ✷

Skyline Queries. Algorithm Skyline (Figure 2) begins by computing the preference-augmented chase forest relative to the input ontology and query and then simply analyzing the set of marked nodes (i.e., those that are dominated by other tuples relative to the query). As we can see, the node markings have done almost all of the work towards answering the skyline query; all the algorithm needs to do is go through the structure and find the nodes whose labels satisfy the query and, if unmarked, add them to the output.

Example 10 Consider again the setup in Example 7 and Figure 1. For query Q1, the only unmarked atom is book(b1, a), and so the skyline answer is the singleton set with this atom. For Q2, we get all the educ atoms except educ(b3). ■

Theorem 11 Let KB be a PrefDatalog+/- ontology, Q be a DAQ, and k ⩾ 0. Then, (i) Algorithm Skyline correctly computes the skyline answers to Q, and (ii) Algorithm Skyline runs in time O(k2 ) in the data complexity, where k is the time needed to compute prefChase(KB, Q) in the data complexity.

As a consequence of the above result, we have the following corollary.

Corollary 12 Let KB = (O, P) be a PrefDatalog+/- ontology, Q be a DAQ, and k ⩾ 0. If O is a guarded Datalog+/- ontology, then the set of skyline answers to Q can be computed in polynomial time in the data complexity.

k-Rank Queries. Algorithm k-Rank (Figure 3) also begins by computing the preference-augmented chase forest. The main while loop iterates through the process of computing the skyline answers to Q by using the Skyline algorithm, updating the result by appending these answers in arbitrary order, and removing the nodes and edges involved in the result from the chase forest; the loop finally prepares for the next iteration by updating the markings in the forest. Once the loop is finished, the algorithm returns the first k results, since the last iteration might add superfluous elements.

Example 13 Consider the setup in Example 7 and the structure in Figure 1. The node book(b1, a) is the first skyline answer; Algorithm k-Rank then proceeds to update Res with (book(b1, a)) and to remove this node (and associated edges) from the forest; according to Line 8, node book(b2, a) now becomes unmarked. The algorithm continues until the three book atoms are processed. ■

Theorem 14 Let KB be a PrefDatalog+/- ontology, Q be a DAQ, and k ⩾ 0. Then, (i) Algorithm k-Rank correctly computes a k-rank answer to Q, and (ii) Algorithm k-Rank runs in time O(k2 ) in the data complexity, where k is the time needed to compute prefChase(KB, Q) in the data complexity.

As a consequence of Theorem 14, we have the following:

Corollary 15 Let KB = (O, P) be a PrefDatalog+/- ontology, Q be a DAQ, and k ⩾ 0. If O is a guarded Datalog+/- ontology, then a k-rank answer to Q can be computed in polynomial time in the data complexity.

4.2 Conjunctive Queries

As discussed at the end of Section 3, non-atomic conjunctive queries require a preference relation that is defined between sets of tuples. Unfortunately, the following result tells us that this change has a direct impact on the complexity of both skyline and k-rank query answering.

Theorem 16 Let KB =((D,Σ), PS) be a guarded PrefDatalog+/- ontology, where PS describes a preference relation ≻PS: 2HPref × 2HPref such that membership can be tested in polynomial time, and Q be a CQ. If the relational schema and Σ are fixed, deciding if the set of skyline answers or a k-rank answer to Q are non-empty is Σp2 -complete.

Proof sketch. Membership in Σp2 is straightforward: answers can be guessed in nondeterministic polynomial time, and verified to be skyline answers with a call to an NP oracle. The k-rank case is analogous, adding an extra check for the order of the answers given.

Σp2 -hardness: Given QBF ∃X∀YF(X,Y) in 3CNF, we build a PrefDatalog+/- ontology KB =(O, PS): we have binary predicates exists and forall, and database D with ground atoms exists(x, t) and exists(x, f) for every X∈X, and forall(y, t) and forall(y, f) for every Y ∈Y. Now, ≻PS is defined so that sets of forall atoms with exactly one atom per variable can be preferred to sets of exists atoms, also with exactly one atom per variable, and in the following manner: SY ≻PS SX iff F evaluates to false with the values of the variables in SX and SY . Therefore, CQ ∃V1...V|X| exists(x1, V1) ∧ ... ∧ exists(x|X|, V|X|) has a nonempty set of skyline answers iff F is satisfiable. The k-rank case is analogous (we simply let k = 1). ✷

The heuristic algorithms presented in [Zhang and Chomicki, 2011] for relational databases can be applied to PrefDatalog+/- by computing the prefChase relative to the query and thus materializing the necessary part of the ontology into a database. The following result provides a way to leverage tools developed for relational databases for firstorder (FO) rewritable fragments; we use prefQ-DPM to denote either Skyline or k-Rank, and prefQ-RDB the corresponding algorithm for relational databases.

Theorem 17 Let KB =((D,Σ), PS) be a PrefDatalog+/- ontology and Q a CQ. If (D,Σ) belongs to an FOrewritable fragment of Datalog+/- and all F ∈PS are such that cond(F) are conjunctions of atoms, then we can compute PS′ and Q′ in PTIME such that prefQ-DPM(KB,Q) = prefQ-RDB(D, PS′ , Q′ ).

Intuitively, the theorem is a consequence of the fact that for each F ∈PS, cond(F) can be treated like a BCQ and thus rewritten relative to ΣT . This result is important since it identifies conditions under which preference-based queries can be answered using highly optimized relational database management systems, such as Postgres or MySQL.

5 Summary and Outlook

In this work, we have presented an extension of the Datalog+/- family of ontology languages for preference-based query answering, a topic that has recently become central in dealing with data related to the Social Semantic Web. We focused on two well-known kinds of preference-based queries, namely, skyline and k-rank (a generalization of traditional top-k queries), and studied algorithms and complexity of computing their answers when the underlying classical queries are either DAQs or CQs. For DAQs, we proposed an augmented version of the chase forest, and showed how this structure can be used to answer both kinds of preferencebased queries in polynomial time in the data complexity whenever classical query answering is PTIME in the underlying Datalog+/- ontology. For CQs, we showed that this desirable property is lost, and note that related work in relational databases can however be applied in order to leverage heuristics. Current and future work involves implementing and testing the PrefDatalog+/- framework, and exploring specific heuristics and other approximation techniques that can be applied to answer preference-based CQs scalably.

Acknowledgments. This work was supported by the UK EPSRC grant EP/J008346/1 ("PrOQAW"), the ERC grant 246858 ("DIADEM"), and a Yahoo! Research Fellowship.