Best Answers over Incomplete Data : Complexity and First-Order Rewritings

1 Introduction

Answering queries over incomplete databases is crucial in many different scenarios such as data integration [Lenzerini, 2002], data exchange [Arenas et al., 2014], inconsistency management [Bertossi, 2011], data cleaning [Geerts et al., 2013], ontology-based data access (OBDA) [Bienvenu and Ortiz, 2015], and many others. The common thread running through all these applications lies in computing certain answers [Amendola and Libkin, 2018; Libkin, 2018a], which is the standard way of answering queries over incomplete databases. Intuitively this produces answers that can be obtained from all the possible complete databases a given incomplete database represents. However, computing such query answers then relies on sophisticated algorithms that are often difficult to implement. It is well known that restricting to unions of conjunctive queries allows to overcome the difficulty by using na¨ıve evaluation [Imieli ´nski and Lipski, 1984]. This amounts to evaluating queries over incomplete databases as if nulls were usual data values, thus merely using the standard database query engine to compute certain answers.

In general though it is a common occurrence that few if any certain answers can be found. If there are no certain answers, it is still useful to provide a user with some answers, with suitable guarantees. To address this need, a framework to measure how close an answer is to certainty has recently been proposed [Libkin, 2018b], setting the foundations to both a quantitative and a qualitative approach. We focus on the qualitative notion of best answers. Those are a refinement of certain answers based on comparing query answers; one that is supported by a larger set of complete interpretations is better. Best answers are those answers for which there is no better one. They always exist and when certain answers exist the two notions simply coincide.

Best answers is a natural notion, but we still know little about it. Identifying the set of best answers among some given family of sets of answers is known to be complete in data complexity for the class P NP[logn] , which is considered as "mildly" harder than both NP and CONP. However this very formulation of the decision problem is non standard. Traditionally, in databases we rather focus on problems stating that some given result belongs to the set of answers, or that some given set is the set of answers. Certain answers as a decision problem is typically formulated in the first way. So do these variations matter ? We fully answer the question for both best and certain answers of first-order queries, showing significant differences in their computational behaviour.

Despite the high complexity of finding best answers in general, one gains tractability when restricting to unions of conjunctive queries. This is a common class of queries, usually well behaved computationally, even for certain answers. Finding best answers for them was shown to be tractable in [Libkin, 2018b] via an adaptation of techniques used in the context of certain answers [Gheerbrant and Libkin, 2015]. Those are essentially resolution based algorithms for firstorder formulas; this makes them hard to implement in the database context. To overcome this we develop new query rewriting techniques. In particular we show that best answers to any union of conjunctive queries can be computed by issuing a new first-order query directly on the incomplete database. Query rewritings are standard in the context of, e.g., consistent query answering, OBDA, query answering using views etc., i.e., all contexts where only partial information is available about the data to be queried [Calvanese et al., 2000; Calvanese et al., 2007; Cal`ı et al., 2013; Cal`ı et al., 2003b]. First-order rewritings are particularly useful, as they allow to use the power of standard database query engines. In fact when they exist, the rewritten queries can be implemented in any relational query engine by expressing them in SQL, with no need to implement ad-hoc algorithms.

2 Preliminaries

We represent missing information in relational databases in the standard way using nulls [Abiteboul et al., 1995; Imieli´nski and Lipski, 1984; van der Meyden, 1998]. Databases are populated by constants and nulls, coming respectively from two countably infinite sets Const and Null. We denote nulls by ⊥, sometimes with sub- or superscript. We also allow them to repeat, thus adopting the model of marked nulls, as customary in the context of applications such as OBDA or data integration and exchange. A relational schema, or vocabulary σ, is a set of relation names with associated arities. A database D over σ associates to each relation name of arity k in σ, a k-ary relation which is a finite subset of (Const ∪Null)k . Sets of constants and nulls occuring in D are denoted by Const(D) and Null(D). The active domain of D is adom(D) = Const(D) ∪ Null(D). A complete database has no nulls.

A valuation v : Null(D) → Const on a database D is a map that assigns constant values to nulls occurring in D. By v(D) [resp. v(¯a)] we denote the result of replacing each null ⊥ by v(⊥) in D [resp. in the tuple ¯a]. The semantics [[D]] of an incomplete database D is the set {v(D) | v is a valuation on D} of all complete databases it can represent. V(D) denotes the set of all valuations defined on D.

An m-ary query of active domain C ⊆ Const is a map that associates with a database D a subset of (adom(D) ∪ C)m. The active domain of a query will be denoted as adom(Q). To answer a query Q over an incomplete database D we follow [Lipski, 1984; Libkin, 2018b] and adopt a slight generalisation of the usual intersection based certain answers notion. We define the set of certain answers to Q over D as ✷(Q,D) = {¯a over adom(D) ∪ adom(Q) | ∀v : v(¯a) ∈ Q(v(D))}. The only difference with the usual notion is that we allow answers to contain nulls.

Following [Libkin, 2018b], given a query Q, a database D, and a tuple ¯a over adom(D) ∪ adom(Q), we let the support of ¯a be the set of all valuations that witness it:

Supports thus measure how close a tuple is to certainty. We consider one answer to be better than another if it has more support. That is, given a database D, a k-ary query Q, and k-tuples ¯a, ¯b over adom(D) ∪ adom(Q), we let

The set of best answers to Q over D is defined as the set of answers for which there is no better one : Best(Q, D) = {¯a | ¬∃¯b : ¯a✁Q,D ¯b}.

We focus on first-order (FO) queries of vocabulary σ written here in the logical notation using Boolean connectives

∧, ∨, ¬ and quantifiers ∃, ∀. We write ϕ(¯x) for an FOformula ϕ with free variables ¯x. With slight abuse of notation, ¯x will denote both a tuple of variables and the set of variables occurring in it. The set of constants used by ϕ is as usual denoted by adom(ϕ), and gives the active domain of the associated query. We interpret FO-formulas under active domain semantics, i.e. we consider D as a relational structure with universe adom(D) ∪ adom(ϕ). Thus an FO formula ϕ(¯x) represents a query (of active domain adom(ϕ)) mapping each database D into the set of tuples {¯ t over adom(D) ∪ adom(ϕ) | D |= ϕ(¯ t)}.

To evaluate FO-formulas with free variables we use assignments ν from variables to constants in the active domain. Note that with a little abuse of notation we write D |= ϕ(¯ t) for D |=ν ϕ(¯x) under the assignment ν sending ¯x to ¯ t.

Here it is important to note that the query associated to ϕ is a mapping defined on all databases D, possibly with nulls. If D contains nulls, D |= ϕ(¯ t) is to be intended "na¨ıvely", i.e. nulls of D are treated as new constants in the domain of D, distinct from each other, and distinct from all the other constants in D and ϕ. For example the query ϕ(x, y) = ∃z (R(x, z) ∧ R(z, y)), on the database D = {R(1,⊥1),R(⊥1,⊥2),R(⊥3, 2)} selects only the tuple (1, ⊥2).

We consider the ∃, ∧, ∨-fragment of FO known as unions of conjunctive queries and its ∃, ∧-fragment known as conjunctive queries.

Example 2.1. Let Q(x) = ∃y(R(y) ∧ S(y, x)) and D = {R(⊥1),R(1), S(⊥2,⊥2)}. We have Supp(Q,D,⊥2) = {v ∈ V(D) | v(⊥2) = 1 or v(⊥1) = v(⊥2)}, Supp(Q,D, 1) = {v ∈ V(D) | v(⊥2) = 1} and Supp(Q,D,⊥1) = {v ∈ V(D) | v(⊥1) = v(⊥2)}. It follows that ✷(Q, D) = ∅ and Best(Q, D) = {(⊥2)}.

In order to study the complexity of best answer computation we shall need two classes in the second level of the polynomial hierarchy. Both of these contain NP and CONP, and are contained in Σp2 ∩ Πp2 . The class DP consists of languages L1 ∩ L2 where L1 ∈ NP and L2 ∈ CONP. This class has appeared in database applications [Fagin et al., 2005; Barcel´o et al., 2014]. The class P NP[logn] consists of problems that can be solved in polynomial time with a logarithmic number of calls to an NP oracle [Eiter and Gottlob, 1997]. Equivalently, it can be described as the class of problems solved in P with an NP oracle where calls to the oracle are done in parallel, i.e., independent of each other. This class has appeared in the context of AI, modal logic, OBDA [Gottlob, 1995; Eiter and Gottlob, 1997; Calvanese et al., 2006; Bienvenu and Bourgaux, 2016], data exchange [Arenas et al., 2013].

3 Complexity of Best and Certain Answers

A natural way to cast computing best answers as a decision problem would be to proceed along the lines of certain answers [Imieli´nski and Lipski, 1984] and ask whether a given tuple is a best answer :

PROBLEM: BESTANSWER

INPUT:

A query Q, a database D,

a tuple ¯a

QUESTION: Is ¯a ∈ Best(Q,D)?

Instead, [Libkin, 2018b] considers the following variant of the problem, asking whether the set of best answers belongs to a specified family of sets :

PROBLEM: BESTANSWER∈

INPUT:

A query Q, a database D,

a family X of sets of tuples

QUESTION: Is Best(Q,D) ∈ X?

This suggests yet another alternative formulation of the problem, asking if a given set is the best answer :

PROBLEM: BESTANSWER=

INPUT:

A query Q, a database D,

a set X of tuples,

QUESTION: Is Best(Q,D) =X?

BESTANSWER∈ was shown in [Libkin, 2018b] to be P NP[logn] -complete in data complexity. We show that the other alternatives are computationally equivalent. Interestingly, the situation is very different with certain answers, as we show next.

Theorem 3.1. For FO queries the problems BESTANSWER and BESTANSWER= are P NP[logn] -complete in data complexity.

Proof (sketch). The upper bound for BESTANSWER= immediately follows from the upper bound for BESTANSWER∈ (take the family X to be a singleton {X}). As for BESTANSWER we only need a slight modification of the upper bound proof in [Libkin, 2018b]. To check whether ¯a ∈ Best(Q,D) we proceed as follows. Since the query is fixed, and has therefore fixed arity k, in polynomial time we can enumerate all the k-tuples of adom(D). Then, using parallel calls to the NP oracle, we can check for each such tuple ¯b whether Supp(Q,D, ¯a) ⊆ Supp(Q,D,¯b) and whether Supp(Q,D,¯b) ⊆ Supp(Q,D, ¯a). With this information, in polynomial time we know whether ¯a ✁Q,D ¯b for some ¯b.

We prove the two remaining lower bounds, reducing from the same P NP[log n] -complete problem [Wagner, 1990]: given an undirected graph G, is its chromatic number χ(G) odd? With each undirected graph G = 〈N, E〉 with nodes N and edges E, we associate a database DG over binary relations L, E and unary relations C, O as follows. We use a null ⊥n in DG for each node n of G. For each edge {n, n′ } of G, we have pairs (⊥n,⊥n′) and (⊥n′ ,⊥n) in the relation E of DG. In relation C we have m constants {c1, . . . , cm} (intuitively representing possible colors), where m is the number of nodes of G. Relation O of DG is defined as {ci | i is odd} and L is a linear ordering on them, i.e., (ci, cj) ∈ L iff i ≤ j, for i, j ≤ m.

Remark that any valuation v of DG that maps each null into a constant of C represents an assignment of colours in

{c1, . . . , cm} to nodes of G. Then we define a query

For any valuation v, ϕ(c) holds in v(DG) iff 1) c = cj for some j = 1..m (ensured by the first conjunct). 2) For such a cj, the valuation v maps each null into {c1, . . . , cj} (second conjunct), i.e. v represents an assignment of colours to nodes of G, using at most the first j colours. 3) Each color {c1, . . . , cj} is used by v, i.e. v represents an assignment of colours to nodes of G, using precisely the first j colours (third conjunct). 4) There are no loops in E (fourth conjunct).

Thus, for a valuation v, the formula ϕ(cj) is true in v(DG) iff v represents a colouring of G using precisely the first j colours {c1, . . . , cj} (which in the sequel we refer to as an exact j-colouring of G).

Next we define :

For a valuation v, we have that Q(ci) holds in v(DG) iff either v represents an exact i-coloring of G; or v represents an exact j-coloring of G with j odd, and i ≤ j. In other words valuations representing exact j-colorings, with j even, support only the maximal color cj ; while valuations representing exact j-colorings, with j odd, support all colors {c1...cj}.

With this in place we can conclude the reduction for the BESTANSWER problem :

Claim. c1 ∈ Best(Q,DG) iff the chromatic number of G is odd.

An adaptation of this encoding can be used to reduce the odd chromatic number problem to BESTANSWER= as well.

Now that we showed that all three formulations of best answers actually collapse computationally, another natural question arises. Does a similar result hold for certain answers ? We obtain the decision problems CERTAINANSWER, CERTAINANSWER= and CERTAINANSWER∈ by replacing everywhere in the statements of the above decision problems BESTANSWER by CERTAINANSWER and Best(Q,D) by ✷(Q,D). It is well known that data complexity of CERTAINANSWER is CONP-complete for FO-queries [Abiteboul et al., 1991]. We complete the picture as follows.

Theorem 3.2. For FO queries, CERTAINANSWER= is DPcomplete and CERTAINANSWER∈ is P NP[logn] -complete in data complexity.

Proof. To prove membership of CERTAINANSWER= in DP , notice that for a query Q, this problem is the intersection of two languages L1 ∩ L2 where L1 = {(D,X) | X ⊆ ✷(Q, D)} and L2 = {(D, X) | X ⊆ ✷(Q, D)}. L1 is known to be in CONP : we guess a tuple ¯a ∈ X and a valuation v ∈ V (D) with v(¯a) ̸∈ Q(v(D)). Similarly, L2 is in NP : we guess a tuple ¯b ∈ X and a valuation v′ ∈ V (D) with v′ (¯b) ∈ Q(v(D)).

To prove membership of CERTAINANSWER∈ in P NP[log n] , suppose the query Q is k-ary, and we are given a family of sets of k-ary tuples X = {X1, . . . ,Xn} and a database D. For each Xi ∈ X , we use the NP oracle to decide in parallel whether Xi = ✷(Q,D) (for each Xi the two calls to the oracle do not depend on each other and they can also be done in parallel).

For DP-hardness, we reduce from the problem of checking whether χ(G), the chromatic number of an undirected graph G, equals 4 [Rothe, 2003] and for P NP[logn] -hardness, we reduce from the related problem of checking whether χ(G) is odd. With such a graph G, we associate the same database DG as in the proof of Theorem 3.1. Using the exact coloring formula ϕ in the proof of Theorem 3.1, we define a query

We claim that ✷(Q,D) = {c1, . . . , cn} iff χ(G) = n, which entails ✷(Q,D) = {c1, . . . , c4} iff χ(G) = 4 and ✷(Q,D) ∈ {{c1, . . . , cj} | j is odd and 1 ≤ j ≤ |G|} iff χ(G) is odd. Recall that v(DG) |= ϕ(ci) iff ci is a color in {c1, ..., c|G|} and v represents an exact i-coloring of the graph. Now v(DG) |= Q(cj) iff cj is a color and there is no i < j such that v represents an exact i-coloring of the graph, which holds exactly whenever cj ∈ {c1, ..., cχ(G)}.

4 First-Order Rewritings for Best Answers

Considering arbitrary FO-queries brought us an intrinsic intractability result for all variants of best answers. This motivates restricting to unions of conjunctive queries, for which a polynomial time evaluation algorithm (in data complexity) already exists [Libkin, 2018b]. The resolution based procedure is however in sharp contrast with na¨ıve evaluation, which allows to compute certain answers to unions of conjunctive queries via usual model checking. We thus initiate a descriptive complexity analysis of the best answers problem, showing that for unions of conjunctive queries, it can essentially be reduced - modulo a preprocessing of the query - to (na¨ıve) evaluation of an FO-formula.

Given a union of conjunctive queries Q, our starting point towards an FO-rewriting for best answers is finding an FO-formula Q⊆(¯x, ¯ y) encoding the inclusion of supports, i.e. selecting tuples ¯ s, ¯ t over adom(D) ∪ adom(Q) iff Supp(Q, D, ¯ s) ⊆ Supp(Q, D, ¯ t). From Q⊆ one can easily define an FO-formula selecting precisely all best answers to Q on D:

We start by putting each conjunctive query in a normal form which eliminates repetition of variables, by introducing new equality atoms.

Definition 4.1 (NRV normal form). A conjunctive query Q is in non repeating variable normal form (NRV normal form) if it is of the form Q(¯x) = ∃¯ y, ¯ z (q(¯ y, ¯ z) ∧ e(¯ y, ¯ z) ∧ ¯x = ¯ z) where variables in ¯x¯ y¯ z are pairwise distinct, ¯x and ¯ z have the same length, and:

• q(¯ y, ¯ z) is a conjunction of relational atoms, where each free variable in ¯ y, ¯ z has at most one occurrence in q,
• e(¯ y, ¯ z) is a conjunction of equality atoms, possibly using constants.

We say that q(¯ y, ¯ z) is the relational subquery of Q, and e(¯ y, ¯ z) ∧ ¯x = ¯ z is the equality subquery of Q.

Example 4.2. The query Q(x) from Example 2.1 is equivalent to ∃y1y2z(R(y1) ∧ S(y2, z) ∧ y1 = y2 ∧ z = x), which is in NRV normal form.

Clearly every conjunctive query Q is equivalent to a query in NRV normal form; moreover Q can be easily rewritten in NRV normal form (in linear time in the size of the query). Thus in what follows we assume w.l.o.g. that conjunctive queries are given in NRV normal form. Intuitively the NRV normal form allows us to separate the two ingredients of a conjunctive query : the existence of facts in some relations of the database on the one side, and a set of equality conditions on data values occurring in these facts, on the other side. The existence of facts does not depend on the valuation of nulls, and thus can be directly tested on the incomplete database. Instead equality atoms in an NRV normal form imply conditions that valuations need to satisfy in order for the query to hold. We can thus first concentrate on the support of equality subqueries. This will be encoded in FO and then integrated in the rewriting of the whole conjunctive query.

We introduce a notion of equivalence of database elements w.r.t. to a set of equalities. Intuitively equivalent elements of a tuple ¯ t are the ones which should be collapsed into a single value in order for a valuation of ¯ t to satisfy all the given equalities.

Definition 4.3. Given a database D, a conjunction of equality atoms γ(¯ y) and an assignment ν : ¯ y ∪ adom(γ) → adom(D)∪adom(γ) preserving constants, we say that u, u′ ∈ adom(D) ∪ adom(γ) are equivalent w.r.t. γ and ν and write u ≡νγ u′ , if either u = u′ or (u, u′ ) belongs to the reflexive symmetric transitive closure of {(ν(x), ν(w)) | x = w ∈ γ}.

The relation ≡νγ is clearly an equivalence relation over adom(D) ∪ adom(γ), where each element outside the range of ν forms a singleton equivalence class.

Example 4.4. Let γ be x1 = x2 ∧ x2 = x3 ∧ x4 = x5 ∧ x6 = 1. Let ν assign ⊥i to xi for i ≤ 5, and ⊥5 to x6. The equivalence classes of ≡νγ are {⊥i | i ≤ 3} and {1, ⊥4, ⊥5}, plus one singleton for each other domain element.

In what follows we denote by ∼γ the reflexive symmetric transitive closure of {(x,w) | x = w ∈ γ}. Note that this is an equivalence relation among variables and constants of γ.

We will be using the following formula to provide a syntactic characterisation of ≡νγ , where m is the number of equivalence classes of ∼γ : 1

Proposition 4.5. Given an incomplete database D, a conjunction of equality atoms γ(¯ y) and an assignment ν(¯ y) = ¯ t over adom(D)∪adom(γ), given s, s′ in ¯ t∪adom(γ), we have that D |= equivγ(¯ t, s, s′ ) if and only if s ≡νγ s′ .

Intuitively this holds because each disjunct of equivγ (¯ t, s, s′ ) corresponds to a possible derivation of (s, s′ ) in the reflexive symmetric transitive closure of {(ν(x), ν(w)) | x = w ∈ γ}, and one can prove that there is a bound only depending on γ on the number of steps of this derivation.

Example 4.6. Let γ := y1 = y2 ∧ z = x be the equality subquery of the query Q(x) in Example 4.2. Up to logical equivalence, equivγ(y1, y2, z, x, w, w′ ) contains precisely the disjuncts w = w′ , w = y1 ∧ w′ = y2, w = z ∧ w′ = x, w = y1 ∧ w′ = x ∧ y2 = z, plus all disjuncts obtained from them by applying one or more of the following transformations : switch w and w′ , switch y1 and y2, switch x and z. Let D be the database from Example 2.1, then we have for instance D |= equivγ(1,⊥2,⊥2, 1, a, a′ ) and D |= equivγ(1,⊥2,⊥2,⊥2, a, a′ ) for all a, a′ ∈ {1,⊥2}. Similarly D |= equivγ(⊥1,⊥2,⊥2, 1, a, a′ ) for all a, a′ ∈ {1, ⊥1, ⊥2}.

As a consequence of Proposition 4.5, for fixed γ and ¯ t, the relation {(s, s′ ) | D |= equivγ(¯ t, s, s′ )} is an equivalence relation over adom(D) ∪ adom(γ) where each element of adom(D) neither in ¯ t nor in adom(γ) forms a singleton equivalence class.

The formula equivγ is a key ingredient towards a rewriting of a conjunctive query; in fact, as formalized in the following lemma, it selects precisely the pairs of elements of a tuple that a valuation needs to collapse to satisfy a set of equalities.

Lemma 4.7. Let γ(¯ y) be a conjunction of equality atoms, D a database and ν(¯ y) = ¯ t an assignment over adom(D) ∪ adom(γ). Assume v is a valuation of nulls. Then v(D) |= γ(v(¯ t)) if and only if v(s) = v(s′ ) for all s, s′ such that D |= equivγ (¯ t, s, s′ ).

Example 4.8. Let γ and ν be as in Example 4.4, then Lemma 4.7 implies that a valuation v(D) |= γ(v(¯ t)) iff v(⊥i) = v(⊥j) for all i, j = 1..3, and v(⊥i) = 1 for all i = 4, 5.

Formulas we write in the remainder of this section are over signature σ ∪Null, where σ is the database schema. In any incomplete database D over σ ∪ Null, Null is always interpreted by the set of nulls occurring in D (in accordance with the semantics of the SQL construct IS NULL). I.e. we allow rewritings to test whether a database element is null or not.

1 Queries we write in the sequel can be domain dependent. So it is important to recall that we always use active domain semantics.

For γ(¯ y) a conjunction of equality atoms, using equivγ we define a new formula compγ(¯ y) stating the existence of a valuation that collapses all equivalent elements of a tuple:

Notice that if D |= compγ(¯ t) then for each s ∈ adom(D)∪adom(γ) there exists at most one constant c such that D |= equivγ(¯ t, s, c). In fact if for constants c1 and c2, D |= equivγ(¯ t, s, c1) and D |= equivγ(¯ t, s, c2), by transitivity D |= equivγ(¯ t, c1, c2), implying c1 = c2.

Example 4.9. Let D and γ be as in Example 4.6. Consider compγ(y1, y2, z, x). Given the tuples selected by equivγ in Example 4.6, we can conclude that D |= compγ (1, ⊥2, ⊥2, 1).

Proposition 4.10. Let γ(¯ y) be a conjunction of equality atoms, D a database and ν(¯ y) = ¯ t an assignment over adom(D)∪adom(γ), thenD |= compγ(¯ t) if and only if there exists a valuation v of nulls such that v(D) |= γ(v(¯ t)).

We are now ready to define a formula capturing the inclusion of supports between two conjunctions of equality atoms, which will be a crucial ingredient in our rewriting. Let γ(¯x) and γ ′ (¯ y) be conjunctions of equality atoms with adom(γ) = adom(γ ′ ). We define :

Example 4.11. Let γ and D be as in Example 4.6. Let γ ′ := y′1 = y′2 ∧ z′ = x′ , then it follows from Example 4.6 that D |= implyγγ ′(⊥1⊥2⊥21, 1⊥2⊥2⊥2) and D |= implyγγ ′ (1⊥2⊥21, 1⊥2⊥2⊥2).

Using Proposition 4.10 and Lemma 4.7 we obtain :

Proposition 4.12. Let γ(¯x), γ ′ (¯ y) be conjunctions of equality atoms with adom(γ) = adom(γ ′ ), D a database and ν(¯ y) = ¯ t, ν ′ (¯ y) = ¯ t′ assignments over adom(D) ∪ adom(γ). Then D |= implyγ,γ ′(¯ t, ¯ t′ ) ∨ ¬compγ(¯ t) iff for all valuations v, v(D) |= γ(v(¯ t)) implies v(D) |= γ ′ (v(¯ t′ )).

By combining Propositions 4.12 and 4.10 we also get :

Corollary 4.13. Let γ(¯ y), γ ′ (¯ y) be conjunctions of equality atoms with adom(γ) = adom(γ ′ ), D a database and ν(¯ y) = ¯ t, ν ′ (¯ y) = ¯ t′ assignments over adom(D) ∪ adom(γ). If D |= compγ (¯ t) ∧ implyγ,γ ′ (¯ t, ¯ t′ ), then D |= compγ ′ (¯ t′ ).

We now go back to an arbitrary union of conjunctive queries of vocabulary σ in NRV-normal form :

where each Qi is in NRV-normal form with relational subquery qi(¯ yi, ¯ zi) and equality subquery eqi(¯x, ¯ yi, ¯ zi).

Lemma 4.14. Let D be a database, v a valuation of D and Q(¯x) a union of conjunctive queries in NRV-normal form, then v ∈ Supp(Q, D, ¯ r) if and only there exists i, ¯ s and ¯ t such that D |= qi(¯ s, ¯ t) ∧ compeqi (¯ r¯ s¯ t) and v(D) |= eqi(v(¯ r¯ s¯ t)).

We are now ready to define the FO-formula encoding the inclusion of supports.

Combining Lemmas 4.7, 4.14, Propositions 4.10, 4.12 and Corollary 4.13 we get :

Recall that from Q⊆ one can easily define a first order rewriting bestQ(¯x) for best answers as in (1).

Theorem 4.16. Given Q a union of conjunctive queries over schema σ and an incomplete database D, ¯ t ∈ Best(Q, D) iff D |= bestQ(¯ t).

Example 4.17. For Q,D, γ, γ ′ as in Example 2.1 and 4.11 :

→

This allows to derive for instance Supp(Q,D, 1) ⊆ Supp(Q,D,⊥2) (as observed in Example 2.1). In fact the subquery R(y1) ∧ S(y2, z) ∧ compγ(y1, y2, z, x) with free variables y1, y2, z, x selects on D tuples (1,⊥2,⊥2, 1), (⊥1,⊥2,⊥2, 1), and no other tuple with last element 1. Moreover as shown in Example 4.11

Thus D |= Q⊆(1,⊥2). Similarly one can show D |= Q⊆(⊥1, ⊥2) and therefore D |= bestQ(⊥2).

As a corollary of Theorem 4.16, for a union of conjunctive queries Q one can compute Best(Q,D) by first computing the formula bestQ(¯x) from Q, then evaluating bestQ on D. Since data complexity of FO query evaluation is DLOGSPACE (and in particular AC0 ), this gives the following corollary :

Corollary 4.18. For each fixed union of conjunctive queries Q, the data complexity of BESTANSWER is DLOGSPACE.

Note that it was known from [Libkin, 2018b] that the data complexity of computing best answers for unions of conjunctive queries is polynomial time. In terms of combined complexity (i.e. when either Q, D and ¯a are in the input), the rewriting approach (i.e. the procedure of computing bestQ from Q and then evaluating bestQ on D), can be easily shown to be in PSPACE. In fact it is well known that a first order query ϕ can be evaluated on a database D in space at most qr(ϕ) log |D| + log|ϕ|, where qr(ϕ) is the quantifier rank of ϕ. Note that although bestQ has size exponential in Q, the quantifier rank of bestQ is linear in the size of Q. Thus whether ¯a ∈ best(Q,D) can be checked using space O(|Q|, |D|). Moreover one can easily check that bestQ can be computed from Q in space polynomial in the size of |Q|. Since space bounded computations can be composed without storing the intermediate output, computing bestQ from Q and then evaluating bestQ on D can be done overall in PSPACE in the size of |Q| and |D|. The rewriting approach thus implies a PSPACE upper bound for the combined complexity of BESTANSWER for unions of conjunctive queries. However we can show that the problem actually stands in the third level of the polynomial hierarchy.

Theorem 4.19. For unions of conjunctive queries, combined complexity of BESTANSWER is Πp3 -complete. Hardness already holds for conjunctive queries.

Therefore under standard complexity theoretic assumptions, our rewriting approach is not optimal in terms of combined complexity, as it is often the case with generic approaches. However it has the advantage of exploiting standard FO query evaluation, which despite the PSPACE combined complexity, is highly optimised in database systems and works well in practice.

5 FutureWork

Constraints (e.g., keys and functional dependencies) are known to raise the complexity of finding certain answers [Cal`ı et al., 2003a]. They appear in another model of incompleteness - conditional tables [Imieli´nski and Lipski, 1984] - that in general leads to higher complexity of query evaluation [Abiteboul et al., 1995] but are nonetheless useful in several applications [Arenas et al., 2013]. We would like to explore how our rewriting techniques interact with integrity constraints.

In another direction, while we focused on FO-rewritings, we could consider more expressive rewriting languages such as Datalog or fixed point logics, as it is common in the context of OBDA, query answering using views, or consistent query answering [Bienvenu and Ortiz, 2015; Francis et al., 2015; Bertossi, 2011]. These more expressive logics are likely to be able to express rewritings of larger classes of queries than unions of conjunctive queries.

We would also like to investigate how our techniques can be extended to different semantics of incompleteness. We used here the closed-world semantics [Abiteboul et al., 1995; Imieli ´nski and Lipski, 1984; van der Meyden, 1998], in which data values are the only missing information, but there are other possible semantics, e.g. needed in order to cope with data inconsistencies [Cal`ı et al., 2003a], where query rewritings could still be found.

Finally, we would like to investigate how techniques developed in this paper could be extended to study rewritings of certain answers.

Acknowledgements

We thank the anonymous referees and Leonid Libkin for their useful feedback. This work was supported by contract ANR18-CE40-0031 QUID.