On Querying Incomplete Information in Databases under Bag Semantics

1 Introduction

In many problems lying at the intersection of AI and data management, one tries to recast key tasks as evaluation of database queries, in an attempt to leverage existing database technology. Examples include data integration and data exchange, where finding answers over integrated and exchanged data is often achieved by first rewriting a query and then running it against a constructed database or data source [Arenas et al., 2014; Cal`ı et al., 2003b; Lenzerini, 2002]. Another example is ontology-based query answering, where one attempts to rewrite a query in a standard query language and run it on the original or modified database [Calvanese et al., 2007; Gottlob et al., 2014; Kontchakov et al., 2011].

There are two features common to all these approaches. First, they try to take advantage of decades of research into efficient evaluation of SQL queries over relational databases. Second, the databases on which queries are executed are typically incomplete: for example, they often have null values added to them by applying a version of the chase procedure. Thus, one ends up using techniques for answering queries on databases with nulls. Such techniques usually produce correct answers for positive queries (i.e., unions of conjunctive queries) and quickly descend into intractability outside this class [Abiteboul et al., 1995; Imielinski and Lipski, 1984], partly explaining the prevalence of positive queries in this line of research.

Despite many visible successes of applying traditional database technology in the above tasks, there is one notable mismatch between theoretical work and what happens in real life. Real SQL databases use bag, or multiset semantics. That is, database relations and query results may contain duplicates; query evaluation algorithms apply special rules that correctly count occurrences of tuples in their results. However, the standard notions of query answering over incomplete databases, such as certain answers, have been primarily worked out under the set semantics.

It is well known that the set/bag mismatch can have a profound effect on many results about query evaluation and reasoning about queries. For example, the standard problem of conjunctive query containment - which is essentially testing for the existence of a homomorphism, or a solution to a non-uniform CSP instance; cf. [Chandra and Merlin, 1977; Kolaitis, 2003] - is NP-complete under set semantics, but its exact complexity under bag semantics remains a major open problem [Chaudhuri and Vardi, 1993; Jayram et al., 2006]. The complexity of basic query languages such as relational algebra remains tractable but moves up to a different complexity class, which requires new techniques for analyzing its expressiveness [Grumbach and Milo, 1996; Libkin and Wong, 1997]. And, when it comes to answering queries over bag-based databases with nulls, there is still no understanding of how the problem behaves even for positive queries.

Keeping track of the number of occurrences of a record is important in many real-life applications, in particular those where data from multiple independent sources is integrated or merged. But the need for bag semantics is more basic than that, for at least two reasons. The first is efficiency; to leverage existing technology, the vast majority of the approaches to handling data rely on commercial DBMSs as a backend (this is true for data integration, data exchange, OBDA, etc.). As prescribed by the SQL Standard, these systems use bag semantics in query evaluation. Set semantics in SQL can be enforced, but at a high computational cost and thus it is normally avoided. The second reason is that query results are often used as input for further data analytics; in these cases, preserving duplicates is essential for correctly computing aggregates over them. Thus, if certain answers over incomplete databases are to be used in further processing, we ought to ensure that they retain information about record occurrences.

In light of these observations, our primary goal is to initiate the study of answering queries on incomplete databases under bag semantics, to move it closer to real-life applications that use SQL queries in relational DBMSs. At first it might seem that at least for positive queries there should be no problem in lifting results from sets to bags. We show that this is not so.

An incomplete database defines a set of possible worlds. When we evaluate a query over an incomplete database, for each candidate answer tuple we want to know how it occurs in query answers over possible worlds: for example, in all of them (certainty) or in some of them (possibility). When we deal with bags, we need to look at the number of occurrences. This gives us an interval between the minimum and the maximum numbers of occurrences. For sets, these numbers could be only zero or one, but for bags these could be arbitrary natural numbers. What we show is that, for positive queries, the minimum can be computed efficiently, by modifying set-based techniques appropriately, but finding the maximum becomes intractable. In fact it is already intractable in very simple settings.

In essence, our results say that for unions of conjunctive queries, which dominate many applications that require dealing with incomplete information, one can rely on query evaluation provided by commercial DBMSs and be certain about the minimum number of occurrences of tuples in the result. But getting additional information about such numbers is computationally intractable.

These results also shed some light on handling queries that go beyond unions of conjunctive queries. Finding answers to such queries that come with correctness guarantees is known to be coNP-hard [Abiteboul et al., 1991], so it is natural to look at approximations. The idea was already pursued in [Reiter, 1986; Vardi, 1986] in the context of databases represented as logical theories, but recently it was shown that it can be made to work in the context of standard relational DBMSs [Libkin, 2016; Guagliardo and Libkin, 2016]. The key idea was to devise approximation schemes that, unlike the native evaluation of SQL queries, come with correctness guarantees. Two such schemes were developed under set semantics; one of their features is that for positive queries, they can rely on the standard query evaluation. Here we look at these schemes under bags and show that one of them requires computing an intractable query, while the other remains tractable. This observation provides a theoretical justification for results empirically observed in [Guagliardo and Libkin, 2016].

Organization Section 2 introduces basic notations. In Section 3 we give the semantics of bag relational algebra. Section 4 proves that minimal numbers of occurrences can be found efficiently for positive queries under bag semantics, and Section 5 shows that for maximal numbers the problem is intractable. In Section 6 we discuss implications for approximating certain answers; Section 7 gives concluding remarks.

2 Preliminaries

Incomplete databases An incomplete database D is a way to represent many complete databases (i.e., possible worlds); the set of those is referred to as the semantics of D, denoted by JDK. The model of incompleteness that we use here is the very common model of marked or labeled nulls. It is not only common in databases [Abiteboul et al., 1995; Imielinski and Lipski, 1984] but naturally occurs in the applications we mentioned before. For instance, the chase procedure - which is heavily used in data integration, exchange, as well as ontology-based querying - populates databases with both known constants and marked nulls, cf. [Arenas et al., 2014; Kontchakov et al., 2011; Lenzerini, 2002].

In this model databases are populated by constants and nulls, coming from two disjoint countably infinite sets denoted by Const and Null, respectively. Nulls are denoted by ⊥, sometimes with sub- or superscripts. A database D is then a set of relations over Const ∪Null; a k-ary relation is a finite subset of (Const∪Null)k . We write Const(D) and Null(D) for the set of constants and nulls that occur in D. A database is complete if Null(D) = ∅.

The semantics JDK is defined via valuations v which are mappings v : Null(D) → Const. Then

where v(D) is the complete database obtained by replacing each null ⊥ with v(⊥). This is usually referred to as the closed-world semantics of incompleteness [Reiter, 1977].

In the applications we mentioned, both closed and open world semantics are used [Arenas et al., 2014; Lenzerini, 2002; Lutz et al., 2015]. In the study of incompleteness in databases, closed world semantics is more common. It has better complexity for more expressive queries, and under set semantics makes no difference for answering positive queries [Imielinski and Lipski, 1984]; thus we use it in this study.

Query answering A relational query Q of arity k takes a complete database D and returns a set of k-tuples over Const(D). If such a query Q is asked on an incomplete database D, to answer it one has to analyze the behavior of Q on the elements of JDK. Using the characteristic function of a tuple ¯ c in a relation R

we define

The cases of interest to us are:

• minQ(D, ¯ c) = 1. Then we know that ¯ c is always in Q(D′ ) for D′ ∈ JDK and thus it is a certain answer.

For a large class of queries, namely positive queries (or, equivalently, unions of conjunctive queries) calculating minQ and maxQ can be done efficiently. We define this class of queries using the positive operations of relational algebra:

• maxQ(D, ¯ c) = 1. Then we know that ¯ c is in Q(D′ ) for some D′ ∈ JDK and thus it is a possible answer.
• Selection σi=j , when applied to a k-ary relation R with k ≥ i, j, returns the set of tuples (a1, . . . , ak) ∈ R such that ai = aj .
• Projection π¯ı (omitting the ith component), when applied to a k-ary relation R with k ≥ i, returns the set of tuples (a1, . . . , ai-1, ai+1, . . . , ak) for (a1, . . . , ak) ∈ R.
• Cartesian product ×, when applied to a k-ary relation R and an m-ary relation S produces a k + mary relation with tuples (a1, . . . , ak, b1, . . . , bm) where (a1, . . . , ak) ∈ R and (b1, . . . , bm) ∈ S.
• Union R∪S can be applied to two relations of the same arity.

Queries of positive relational algebra (RA+) are built from relations and these operation, e.g., (σ2=3(R) × π¯3(S)) ∪ T . Note that often RA+ expressions are presented by allowing selections with a conjunction of equalities or projections on a group of attributes, but these are easily expressed in the version we have.

Full relational algebra (RA) adds the difference operation: R - S contains tuples in R but not in S. In terms of expressiveness, RA has precisely the power of first-order logic (FO), while RA+ corresponds to existential positive FO, i.e., formulae built from atoms using ∃, ∧, ∨. These have the same power as unions of conjunctive queries (which are the ∃, ∧- fragment of FO).

The following is well known [Abiteboul et al., 1991; Imielinski and Lipski, 1984].

Fact 1. For every RA+ query Q, checking each of the conditions minQ(D, ¯ c) = 1 and maxQ(D, ¯ c) = 1 can be done in polynomial time in the size of D.

For full RA, these problems are in coNP and NP respectively, and there are RA queries for which they are coNPcomplete and NP-complete in terms of data complexity. Data complexity [Vardi, 1982] refers to the computational complexity of the problem with query Q fixed, and D, ¯ c given as the input. In what follows all the complexity results will be stated in terms of data complexity.

3 Bag Semantics

Real-life databases are not based on sets but rather on bags (multisets): each tuple can occur multiple times in a database relation and consequently in query results [Date and Darwen, 1996]. We extend the notion of #(¯a,R) from sets to bags: now for a tuple ¯a and a relation R, the expression #(¯a,R) denotes the number of occurrences of ¯a in R; if ¯a does not occur in R, we set #(¯a, R) = 0.

For RA queries, the syntax of basic operations does not change, but they are given bag semantics, and some operations that were derivable under set semantics are added. The interpretations of selection, projection, product, and union are changed as follows:

• Selection σi=j: for each tuple ¯a,

• Projection π¯ı:

with summation over all elements a that occur in R.

• Cartesian product: #((¯a, ¯b), R×S)=#(¯a, R)·#(¯b, S).
• Union: #(¯a, R ∪ S) = #(¯a, R) + #(¯a, S)

For relational algebra on sets, intersection is easily expressible with σ, π, and ×. This is not the case for bags [Libkin and Wong, 1997] so we shall add this operation explicitly, under the standard semantics:

• Intersection: #(¯a,R∩S) =min(#(¯a,R), #(¯a, S)).

We further add the operation ε of duplicate elimination (which in the case of sets is simply the identity):

• Duplicate elimination: #(¯a, ε(R)) = min(#(¯a, R), 1).

These operations, σ, π, ×, ∪, ∩, and ε, constitute RA+ for bags. Full RA adds the operation - (difference) with the semantics #(¯a, R - S) = max(#(¯a, R) - #(¯a, S), 0).

When it comes to query answering, the definition (1) still applies: minQ(¯ c,D) is the minimum number of occurrences of ¯ c in Q(D′ ) for D′ ∈ JDK, and maxQ(¯ c,D) is the maximum such number. That is, we know with certainty that every query answer must contain at least minQ(¯ c,D) occurrences of ¯ c, and no answer will contain more than maxQ(¯ c, D).

In what follows, we look at data complexity of query answering: that is, for a fixed query Q, we want to compute minQ(D, ¯ c) or maxQ(D, ¯ c) on the input that consists of a database D and a tuple ¯ c. When we talk about complexity in terms of complexity classes, especially hardness results, we view these as decision problems, i.e., comparing minQ(D, ¯ c) and maxQ(D, ¯ c) with a given number m.

Firstly, we note that these problems are in the first level of the polynomial hierarchy.

Proposition 1. For every RA query Q interpreted under bag semantics, and for every m ∈ N, checking whether minQ(D, ¯ c) > m or whether maxQ(D, ¯ c) < m can be done in coNP with respect to data complexity.

Furthermore, there are queries Q and numbers m ∈ N such that the above problems are coNP-complete in data complexity.

Of course this means that complements, minQ(D, ¯ c) ≤ m and maxQ(D, ¯ c) ≥ m, are in NP and can be NP-complete for some Q and m. These bounds follow from the fact that, like in the set case, it suffices to consider valuations v on D whose range consists of Const(D) and a new distinct constant for each null in Null(D), and that relational algebra, under bag semantics, can be evaluated in DLOGSPACE in data complexity. For hardness, the same proofs as in [Abiteboul et al., 1991] apply, since RA under set semantics can be simulated.

4 Bag Semantics: Positive Results

While Proposition 1 tells us that computing minQ(D, ¯ c) and maxQ(D, ¯ c) may require superpolynomial time (assuming that NP ̸= PTIME), under set semantics these are computable efficiently for positive queries Q in RA+. We now see what happens under bag semantics. In this section we show the positive result: minQ(D, ¯ c) can be computed efficiently.

Theorem 1. Under bag semantics, for each fixed RA+ query Q, computing minQ(D, ¯ c) can be done in DLOGSPACE with respect to data complexity.

Proof sketch. The proof is based on the following observation. Let Q(D) mean the naive evaluation of Q on D (under bag semantics). That is, selection conditions evaluate as follows: if Null(D) = {⊥1, . . . ,⊥k}, then ⊥i = ⊥j is true iff i = j, and ⊥i ̸= c for every c ∈ Const.

We call a valuation v on D canonical if v(⊥i) = ci, for 1 ≤ i ≤ k, where c1, . . . , ck are distinct constants and none of them belongs to Const(D). Then we prove the following by induction on RA+ queries Q. For every tuple ¯a ∈ Q(D):

1. #(¯a, Q(D)) ≤ #(v(¯a), Q(v(D))) for every valuation v on D;
2. #(¯a,Q(D)) = #(v0(¯a),Q(v0(D))) for every canonical valuation v0.

For a constant tuple ¯ c this implies that minQ(¯ c,D) = #(¯ c, Q(D)), and the latter can be computed in DLOGSPACE due to known bounds on the complexity of RA under bag semantics [Grumbach and Milo, 1996; Libkin and Wong, 1997].

Before proving 1 and 2 above, first observe that if v is a canonical valuation on D, then for every two tuples ¯a and ¯b over Const(D) ∪Null(D), the condition v(¯a) = v(¯b) implies ¯a = ¯b. Now proceed with the proof by induction on expressions. The base case is when Q is R, a database relation. If ¯a ∈ R, then v(¯a) ∈ v(R) and thus 1 holds. If v0 is canonical and v0(¯a) ∈ v0(R), then v0(¯a) = v0(¯b) for some ¯b ∈ R, which implies ¯a = ¯b and thus #(¯a, R) = #(v0(¯a), v0(R)), proving the base case.

For the induction case we need to look at queries obtained by applying operations σ, π, ×, ∪, ∩, and ε. As an example, we consider the case of selection. Assume Q′ = σi=j(Q). If 0 < #(¯a, Q′ (D)) = m, then #(¯a, Q(D)) = m and ai = aj . By the hypothesis, #(v(¯a),Q(v(D))) ≥ m for every v, and since v(ai) = v(aj) we have #(v(¯a),Q′ (v(D))) ≥ m, proving 1. Next assume that v is canonical and m = #(¯a,Q′ (D)). If ai ̸= aj, then m = 0, but since v is canonical, v(ai) ̸= v(aj) and thus #(v(¯a),Q′ (v(D))) = 0 as well. So assume ai = aj. Then m = #(¯a,Q(D)) and by the induction hypothesis m = #(v(¯a), v(Q(D))) = #(v(¯a), v(Q′ (D))) since v(¯a) satisfies the selection condition. This proves 2.

The remaining cases of π, ×, ∪, ∩, and ε are similarly obtained by induction.

Theorem 1 also provides information about tuples containing nulls. It is often important to keep them in the answers, as they provide valuable information. For instance, if we have a relation R = {((1, ⊥)} and a query Q returning R itself, then there are no constant tuples with minQ(R, ¯ c) > 0; this however loses certain information that R contains a tuple whose first component is 1. An alternative to overcome this, known as certain answers with nulls [Lipski, 1984], suggests, in the set case, looking for tuples ¯a such that v(¯a) ∈ Q(v(D)) for every valuation v. For constant tuples this is the same as saying minQ(D, ¯a) = 1.

For RA+ queries under set semantics, it is well known [Lipski, 1984; Libkin, 2016] that ¯a ∈ Q(D) if and only if #(v(¯a),Q(v(D))) = 1 for every valuation v; or, equivalently, #(¯a, Q(D)) = minv #(v(¯a), Q(v(D))). We now see that the situation is identical for bag semantics.

Corollary 1. For every RA+ query Q interpreted under bag semantics, every database D and an arbitrary tuple ¯a, we have #(¯a,Q(D)) = minv #(v(¯a),Q(v(D))).

5 Bag Semantics: Negative Results

We saw that, under bag semantics, minQ(D, ¯ c) can be computed efficiently. We now show that the situation is drastically different for max: computing maxQ(D, ¯ c) is intractable, in data complexity, even for very simple queries that just return a relation from the database (that is, SQL queries of the form SELECT * FROM R).

To state the result, we need to cast this problem as a decision problem. For this, we define the problem LEASTOCCUR that takes as input a k-ary relation R over Const∪Null, a k-ary tuple ¯ c over Const, and an integer m > 0, and asks whether there exists a valuation v on Null(R) such that ¯ c occurs at least m times in v(R), i.e., #(¯ c, v(R)) ≥ m. Clearly the problem is in NP: it suffices to guess a valuation that only uses elements of Const(R) and ¯ c. The problem is also NPhard.

Theorem 2. The problem LEASTOCCUR is NP-complete.

Corollary 2. There is an RA+ query Q (in fact a query returning a relation in the database) such that checking, for given D, ¯ c, and m whether maxQ(D, ¯ c) < m is coNPcomplete.

Proof sketch. To show that LEASTOCCUR is NP-hard we reduce to it fromMaximum 2-Satisfiability (MAX2SAT), which is NP-complete [Garey and Johnson, 1979]. Given a set Σ of propositional clauses, each consisting of exactly two literals, and a positive integer m ≤ |Σ|, MAX2SAT is the problem of deciding whether there exists a truth assignment that satisfies at least m clauses in Σ.

Let Σ be a set of clauses of two literals. With each propositional variable p occurring in Σ we associate a distinct null value ⊥p and the following two pairs: ¯utp = (0,⊥p) and ¯ufp = (⊥p, 1). Observe that (0, 1) unifies with each of these pairs, but there is no valuation v for which v(¯utp ) = v(¯ufp ).

With each clause σ ∈ Σ we then associate a quaternary relation Rσ defined as follows:

where p and q range over the propositional variables mentioned in Σ. Intuitively, the tuples in Rσ represent the truth assignments that satisfy σ. Note that (0, 1, 0, 1) unifies with each of the tuples in Rσ, but there is no valuation v for which it would occur more than once in v(Rσ). This is an immediate consequence of the fact that v(¯utp ) ̸= v(¯ufp ) for every propositional variable p and every valuation v.

Now, let RΣ = ⋃σ∈Σ Rσ. Clearly, by construction, there is a bijective correspondence between the nulls in RΣ and the propositional variables in Σ. Thus, for each truth assignment α we can define a valuation vα with vα(⊥p) = 1 if α(p) = t, and vα(⊥p) = 0 otherwise; and for each valuation v we can define a truth assignment αv with αv(p) = t if v(⊥p) = 1, and αv(p) = f otherwise.

Claim 1. Let Σ be a set of clauses of two literals, let α be a truth assignment to the propositional variables of Σ, and let σ ∈ Σ. Then, α satisfies σ if and only if (0, 1, 0, 1) occurs exactly once in vα(Rσ).

We illustrate one case. Let ¯ c = (0, 1, 0, 1), and let p and q be the propositional variables occurring in σ. Assume p occurs positively and q occurs negatively. Then,

α |= σ iff exactly one of the following holds:

#(¯ c, vα(Rσ)) = 1 iff exactly one of the following holds:

The claim then follows by the definition of vα. The remaining cases, when both variables occur positively, or both occur negatively, are analogous.

Similarly, but using the definition of αv, we also obtain:

Claim 2. Let Σ be a set of clauses of two literals, let v be a valuation of the nulls in RΣ, and let σ ∈ Σ. Then, (0, 1, 0, 1) occurs exactly once in v(Rσ) if and only if αv satisfies σ.

The above claims now apply to show the following:

Claim 3. Let (Σ,m) be instance of MAX2SAT. There exists a truth assignment α that satisfies at least m clauses in Σ if and only if there exists a valuation v such that (0, 1, 0, 1) occurs at least m times in v(RΣ).

Given Σ, the construction of RΣ is polytime and gives the desired reduction from MAX2SAT to LEASTOCCUR.

In some restricted cases maxQ(D, ¯ c) can be calculated efficiently. Consider, for example, queries of the form ε(Q), with duplicate elimination applied as the outermost operation. They correspond to SQL queries SELECT DISTINCT . . ., where the remainder of the query is arbitrary and is interpreted under bag semantics.

Proposition 2. For RA+ queries of the form ε(Q), where Q is interpreted under bag semantics, maxQ(D, ¯ c) can be computed in polynomial time with respect to data complexity.

Proof sketch. For a query Q, let Qb (D) and Qs (D) denote their outputs under bag and set semantics on complete databases D; also ε(D) refers to D in which duplicate elimination was applied to every relation. We then show by induction that for queries Q in RA+, we have ε(Qb (D)) = Qs (ε(D)) for every D (of course ε is the identity on set-based databases). Then maxε(Qb )(D, ¯ c) = maxQs(ε(D), ¯ c) and the latter can be computed in polynomial time by [Abiteboul et al., 1991].

6 Approximations under Bag Semantics

Our results shed some light on approximating answers to queries over incomplete databases: we can explain why some approximation schemes work in real-life DBMSs while others do not. As is well known (see Fact 1), computing certain and possible answers to relational algebra (and thus firstorder) queries over incomplete databases is an intractable problem. It is thus natural to try to approximate such answers by tractable queries. The idea is not new: first solutions were proposed long ago [Reiter, 1986; Vardi, 1986] but in the context of databases viewed as logical theories which made them unimplementable in real DBMSs.

The first approximation scheme designed to work with the standard relational database technology appeared in [Libkin, 2016]. It still used set semantics; its idea was to modify an RA query Q into a query Qt that returns a subset of certain answers. More precisely, for a tuple ¯a that can contain constants and nulls, define

where v ranges over valuations. Note that if ¯a contains only constants, this is the same as (1), and for arbitrary tuples, minQ(D, ¯a) is efficiently computable for RA+ queries, by Corollary 1.

The scheme showed how to transform Q into queries Qt ,Qf such that

where ¯Q computes the complement of Q. These queries, giving us certainly true and certainly false answers, were defined by mutual recursion (i.e., Qf was necessary to define Qt ).

How does one extend such definitions to bags? To see this, we restate (5) as follows. Let ⊕ be the addition in the twoelement field F2.

Proposition 3. Under set semantics of queries, conditions (5) are equivalent to

for every tuple ¯a.

This suggests a natural extension of the translation scheme (Qt ,Qf ) to bags: one uses (6) but replaces ⊕ with the usual addition, as now occurrences can be arbitrary natural numbers. But this is suddenly very problematic, as maxQ(D, ¯a) is hard computationally, for all queries, since we cannot even compute it efficiently for base relations! Thus, implementing this approximation scheme in a real-life RDBMS (which is bag-based) is infeasible.

It was observed in [Guagliardo and Libkin, 2016] that the translation Q ↦→ (Qt ,Qf ), while enjoying good theoretical complexity, is unlikely to work well in a real-world setting because rewritten queries require very large joins even in the set case. The results of the previous section show that even good theoretical complexity is lost if one uses bag semantics.

Based on the size of the rewritten queries that the translation Q ↦→ (Qt , Qf ) produces, [Guagliardo and Libkin, 2016] proposed a different translation, again for the set case. It transforms a query Q into two queries Q+ and Q? such that

for all valuations v. This, over sets, implies that Q+(D) ⊆ {¯a | minQ(D, ¯a) = 1} ⊆ Q? (D). In other words, we have lower and upper approximations of certain answers.

Again, all the development of [Guagliardo and Libkin, 2016] was done under the set semantics of queries, but (7) makes it easy to extend the framework to bags. We take (7) to be the requirement for queries Q+ and Q? , where ⊆ now has bag-theoretic meaning: for two bags B1,B2, we write B1 ⊆ B2 iff #(b, B1) ≤ #(b, B2) for every element b.

Proposition 4. Assume that for an RA query Q, we have two queries Q+ and Q? that satisfy (7), under bag semantics. Then #(¯a,Q+(D)) ≤ minQ(¯a,D) ≤ #(¯a,Q? (D)), for every database D and every tuple ¯a of elements of D.

In fact Proposition 4 is true for any query that is invariant under isomorphisms, which includes queries expressible in logics such as first-order and its extensions. It recasts the approximation approach of [Guagliardo and Libkin, 2016] in a way that makes no reference to maxQ. This gives a strong indication that it can be adapted to bag semantics.

This is indeed so. To show this, we use the translation Q ↦→ (Q+, Q? ) below:

The selection condition i ∼ j used in (σi=j(Q))? is a disjunction (i = j) ∨ null(i) ∨ null(j), checking that either the ith and the jth component of a tuple are the same, or one of them belongs to Null. The translations (Q1 ∩ Q2)? and (Q1 - Q2)+ use the semijoin operation ⋉⇑ defined as follows. We write ¯a ⇑ ¯b if there exists a valuation v such that v(¯a) = v(¯b). Then, for two relations of the same arity, R⋉⇑S contains tuples ¯a in R such that ¯a ⇑ ¯b for some ¯b ∈ S, and #(¯a, R ⋉⇑ S) = #(¯a, R).

This is essentially the same translation of [Guagliardo and Libkin, 2016] but now all operations, including semijoin, are interpreted under bag semantics. It turns out that it provides an approximation of certain answers in the following sense.

Theorem 3. The translation Q ↦→ (Q+,Q? ) satisfies (7) when queries are interpreted under bag semantics. Furthermore, queries Q+ and Q? can be evaluated in DLOGSPACE with respect to data complexity.

It was previously empirically observed that the translation Q ↦→ (Q+,Q? ) is efficient on real-life benchmark queries, while Q ↦→ (Qt , Qf ) is not. Now using our complexity results for answering queries on incomplete databases under bag semantics we provided a theoretical justification for this observation, based on the fact that one scheme can be expressed in terms of minQ alone, while the other needs maxQ, which cannot even be computed efficiently for base relations.

7 Conclusions

Much of the theoretical work on query answering in databases, including handling incomplete information, assumes set-based semantics [Abiteboul et al., 1995], leading to a mismatch with what happens in real-life DBMSs [Date and Darwen, 1996]. This also applies to many scenarios that reduce problems combining reasoning and data to answering relational database queries.

In this paper we showed that even for the well-behaved class of positive relational algebra queries (or unions of conjunctive queries), bag semantics complicates query answering with incomplete information considerably, as some of the problems easily solvable under set semantics become intractable. This is not just bad news however: this observation provided a theoretical justification for an approximation of query answers on incomplete databases that was known to behave well in practice.

Our results open up a new line of work on understanding incompleteness in real-life databases, and on using it in applications that combine data with knowledge and metainformation such as ontologies or schema mappings. One needs to devise and optimize approximation schemes, look into interaction with constraints [Cal`ı et al., 2003a], extend results to open-world assumption, and look into new applications such as querying inconsistent data, where reliance on database technology [Bertossi, 2011] and the use of approximations [Bienvenu and Rosati, 2013] is common.

Acknowledgments

We thank the anonymous referees for their comments. Work supported by EPSRC grants N023056 and M025268.