LIAFA Élie Gheerbrant

L Libkin

C Sirangelo

A Naïve Evaluation of Queries over Incomplete Databases

Keywords: Descriptors: H.2.1 [Database Management]: Logical Design-Data Models, H.2.1 [Database Management]: Languages-Query Languages, H.2.4 [Database Management]: Systems-Query Processing Theory, Languages, Algorithms Incompleteness, naive tables/evaluation, certain answers, orderings, homomorphisms

The term naïve evaluation refers to evaluating queries over incomplete databases as if nulls were usual data values, i.e., to using the standard database query evaluation engine. Since the semantics of query answering over incomplete databases is that of certain answers, we would like to know when naïve evaluation computes them: i.e., when certain answers can be found without inventing new specialized algorithms. For relational databases it is well known that unions of conjunctive queries possess this desirable property, and results on preservation of formulae under homomorphisms tell us that within relational calculus, this class cannot be extended under the open-world assumption.

Our goal here is twofold. First, we develop a general framework that allows us to determine, for a given semantics of incompleteness, classes of queries for which naïve evaluation computes certain answers. Second, we apply this approach to a variety of semantics, showing that for many classes of queries beyond unions of conjunctive queries, naïve evaluation makes perfect sense under assumptions different from open-world.

Our key observations are: (1) naïve evaluation is equivalent to monotonicity of queries with respect to a semantics-induced ordering, and (2) for most reasonable semantics of incompleteness, such monotonicity is captured by preservation under various types of homomorphisms. Using these results we find classes of queries for which naïve evaluation works, e.g., positive first-order formulae for the closed-world semantics. Even more, we introduce a general relation-based framework for defining semantics of incompleteness, show how it can be used to capture many known semantics and to introduce new ones, and describe classes of first-order queries for which naïve evaluation works under such semantics.

INTRODUCTION

Database applications need to handle incomplete data; this is especially true these days due to the proliferation of data obtained as the result of integrating or exchanging data sets, or data found on the Web. At the same time, there is a huge gap between our theoretical knowledge and the handling of incompleteness in practice:

-In SQL, the design of null-related features is one of the most criticized aspects of the language [START_REF] Date | A Guide to the SQL Standard[END_REF], due to the oversimplification of the model. This even leads to paradoxical behavior: it is consistent with SQL's semantics that |X| ¡ |Y | and X ¡ Y r, if the set Y contains nulls. Indeed, this is what happens with queries like select R.A from R where R.A not in (select S.A from S) due to the 3-valued semantics of SQL. -In theory, we understand that the proper way of evaluating queries on incomplete databases is to find certain answers to them [START_REF] Imielinski | Incomplete information in relational databases[END_REF]. Unfortunately, for many classes of queries, even within first-order logic, this is an intractable

A:2
problem [START_REF] Abiteboul | On the representation and querying of sets of possible worlds[END_REF], and even when it is tractable, there is no guarantee the algorithms can be easily implementable on top of commercial DBMSs [START_REF] Gheerbrant | On the complexity of query answering over incomplete xml documents[END_REF].

Despite this seemingly enormous gap, there is one instance when theoretical approaches and functionalities of practical systems converge nicely. For some types of queries, evaluating them on the incomplete database itself (i.e. as if nulls were the usual data values) does produce certain answers. This is usually referred to as naïve evaluation [START_REF] Abiteboul | Foundations of Databases[END_REF][START_REF] Imielinski | Incomplete information in relational databases[END_REF]]. To give an example, consider databases with naïve nulls (also called marked nulls), that appear most commonly in integration and exchange scenarios, and that can very easily be supported by commercial RDBMSs. Two such relations are shown below, with nulls indicated by the symbol u with subscripts: R:

A B 1 u 1 u 2 u 3 S: B C u 1 4 u 3 5
Suppose we have a conjunctive (i.e., select-project-join) query π AC pR ' Sq or, equivalently, ϕpx, yq hz Rpx, zq Spz, yq ¨. Naïve evaluation says: evaluate the query directly on R and S, proceed as if nulls were usual values; they are equal only if they are syntactically the same (for instance u 1 u 1 but u 1 $ u 2 ). Then evaluating the above query results in two tuples: p1, 4q, and pu 2 , 5q. Tuples with nulls cannot be certain answers, so we only keep the tuple p1, 4q.

One does not need any new functionalities of the DBMS to find the result of naïve evaluation (in fact most implementations of marked nulls are such that equality tests for them are really the syntactic equality). This is good, but in general, naïve evaluation need not compute certain answers, depending on the semantics of incompleteness. A semantics of incompleteness establishes the possible complete databases represented by an incomplete one, and certain answers are answers which hold true in all such complete databases.

For the query above, the tuple p1, 4q is however the certain answer, under the common open-world semantics (to be properly defined later). This is true because [START_REF] Imielinski | Incomplete information in relational databases[END_REF] showed that if Q is a union of conjunctive queries, then naïve evaluation works for it (i.e., computes certain answers). This result is not so easy to extend: for instance, [START_REF] Libkin | Incomplete information and certain answers in general data models[END_REF] showed that under the open-world semantics, if naïve evaluation works for a Boolean FO query Q, then Q must be equivalent to a union of conjunctive queries. That result crucially relied on a preservation theorem from mathematical logic [START_REF] Chang | Model Theory[END_REF], and in particular on its version over finite structures [START_REF] Rossman | Homomorphism preservation theorems[END_REF]].

This observation suggests that the limits of naïve evaluation depend on the semantics of incompleteness, and that syntactic restrictions on queries admitting such evaluation might be obtained from preservation theorems in logic. This is the starting point of our investigation. In general we would like to understand how, for a given semantics of incompleteness, we can find the class of queries for which certain answers will be found naïvely.

In slightly more detail, we would like to answer the following three questions:

(1) What are the most general conditions on queries guaranteeing naïve evaluation, under different semantics of incompleteness? (2) When can naïve evaluation be characterized by preservation results?

(3) Most general conditions for naïve evaluation need not translate into interesting/relevant classes of queries, but can we provide concrete examples of interesting classes of queries admitting naïve evaluation?

We answer these three questions, by clarifying the relationship between semantics of incompleteness, naïve evaluation, preservation, and syntactic classes. Roughly, our results can be seen as establishing the following equivalences:

Naïve evaluation works for a query Q } Q is monotone with respect to the semantic ordering } Q is preserved under a class of homomorphisms together with syntactic classes of queries guaranteeing preservation under homomorphisms (and thus naïve evaluation).

We now explain the key ideas behind the main equivalences and the terminology we use.

Naïve evaluation and monotonicity. For the first group of results, we deal with a very abstract setting that can be applied to many data models (relational, XML, etc) under different semantics of incompleteness. We introduce the notion of database domain, i.e. a set of incomplete database objects. Each object x of the domain comes with a notion of semantics rrxss, which is the set of complete objects they describe. We define the semantic ordering in the standard way: x ¨y ô rryss rrxss (that is,

x is less informative if it describes more objects, i.e., has more incompleteness in it). In this setting we define queries, naïve evaluation, and certain answers and prove that under very mild conditions, naïve evaluation works for a query iff it is monotone with respect to the semantic ordering. In fact, under even milder conditions, naïve evaluation corresponds to a weak notion of monotonicity, that only considers going from an object x to a more informative object y rrxss.

Monotonicity and preservation. We next connect monotonicity with preservation. To start, we analyze multiple semantics of incompleteness, and come up with a uniform scheme for generating them. The key observation is that each semantics is obtained in two steps. In step one, common to all interpretations, we substitute constant values for nulls.

Step two, that essentially defines the semantics, is given by a relation R showing how the result of the substitution can be modified. For instance, under the open-world semantics, tuples can be added; under the strictest form of the closed-world semantics, nothing can be changed at all.

Having done that, we prove that under some very mild condition, monotonicity of a generic query Q corresponds to preservation under homomorphisms that respect relation R: that is, if Q is true in D (say, for a Boolean Q), and we have a homomorphism respecting R from D to D I , then Q is true in D I . Instances of such homomorphisms are the usual homomorphisms, under the open-world semantics, or onto homomorphisms, under (a version of) the closed-world semantics.

Preservation and syntactic classes. We have so far established that naïve evaluation is captured by preservation under a class of homomorphisms. Such preservation results are classical in mathematical logic [START_REF] Chang | Model Theory[END_REF], and thus we would like to use them to find syntactic classes of queries for which naïve evaluation works.

One immediate difficulty is that classical logic results are proved for infinite structures, and they tend to fail in the finite [START_REF] Ajtai | Monotone versus positive[END_REF][START_REF] Stolboushkin | Finitely monotone properties[END_REF], or are notoriously hard to establish (a well-known example is Rossman's theorem [START_REF] Rossman | Homomorphism preservation theorems[END_REF]], which answered a question opened for many years). Thus, we are in general happy with good sufficient conditions for preservation, especially if they are given by nice syntactic classes corresponding to meaningful classes of database queries. The key ideas behind the classes we use are restrictions to positive formulae (admitting d but disallowing 2) or existential positive formulae (i.e., unions of conjunctive queries), and extending some of them with universally quantified guarded formulae.

This gives us a good understanding of what is required to make naïve evaluation work. In Sections 3-5 we carry out the program outlined above and obtain classes of FO queries for which naïve evaluation works under standard relational semantics of incompleteness. Also, to keep notations simple initially, in these early sections we deal with Boolean queries (all results extend to arbitrary queries easily, as we show in Section 6). In Section 7 we conclude this basic study by providing characterizations of the semantic orderings, and giving their justification in terms of elementary updates increasing informativeness of the database.

Sections 3-7 constitute the first half of the paper, in which we present the general methodology for achieving naïve evaluation, and show how it works for relational queries under the standard open and closed world semantics.

In the second half of the paper, we show that the techniques extend to several others, more complex semantics. These fall into two categories. The first one puts restrictions on valuations of nulls, i.e., mappings assigning constants to nulls. The second one allows the use of multiple valuations to define semantics.

The key property of the semantics of incompleteness considered up to that point is what we call the saturation property: for each incomplete object, there is an isomorphic complete one in its semantics. For most standard semantics, this is trivially so, simply by substituting distinct constants for nulls. However, this assumes that arbitrary valuations of nulls are allowed, and there is a class of semantics, that originated in AI and found applications in data exchange (see [START_REF] Minker | On indefinite databases and the closed world assumption[END_REF][START_REF] Hernich | Answering non-monotonic queries in relational data exchange[END_REF]) for which this property fails.

To deal with them, we present a general tool for handling such non-saturated semantics in Section 8. It shows that the previous results apply as long as the database domain has a subdomain that possesses the saturation property, and for queries that do not distinguish database objects from objects of that subdomain. Then, in Section 9, we look at a concrete examples of non-saturated semantics: the minimal semantics that finds its justification in the study of various forms of the closed world assumption. We show that the database domain consisting of all possibly incomplete relational instances under this semantics has a saturated subdomain; it consists of all instances which are cores (i.e. instances having no homomorphism to a proper subinstance, see [Hell and Nesetȓil 1992]). In particular, previous results do apply, but only over cores.

We then turn our attention to semantics that can use multiple valuations; we refer to them as powerset semantics. We explain their justification via updates that incrementally improve informativeness of a database, and compare them with known orderings on Codd databases that model SQL's null features, showing that one particular powerset semantics fits in well with previously studied orderings for Codd databases. We then show how the methodology of obtaining naïve evaluation extends for powerset semantics, even including semantics that combine both multiple valuations and restrictions on such valuations (minimal powerset semantics).

Again, in Sections 8-10 we present results for Boolean queries; Section 11 shows how to adjust the lifting tool of Section 6 to obtain results for non-Boolean queries under non-saturated semantics and powerset semantics.

This article is an extended version of [START_REF] Gheerbrant | When is naïve evaluation possible?[END_REF].

Organization. In Section 2, we give the main definitions. In Section 3, we explain the connection between naïve evaluation and monotonicity, and in Section 4 we relate monotonicity to preservation. In Section 5 we deal with Boolean FO queries and provide sufficient conditions for naïve evaluation. In Section 6 we show how to lift results to arbitrary (non-Boolean) queries. Section 7 studies semantic orderings on incomplete databases. Section 8 deals with non-saturated semantics in general, and a concrete case of it, the minimal semantics, is handled in Section 9. In Section 10 we study semantics resulting from multiple valuations of nulls. Finally, Section 11 shows how to lift results to non-Boolean queries in non-saturated and powerset semantics.

PRELIMINARIES

Incomplete databases

We begin with some standard definitions. In incomplete databases there are two types of values: constants and nulls. The set of constants is denoted by Const and the set of nulls by Null. These are countably infinite sets. Nulls will normally be denoted by u, sometimes with sub-or superscripts.

A relational schema (vocabulary) is a set of relation names with associated arities. An incomplete relational instance (or incomplete database) D assigns to each k-ary relation symbol S from the vocabulary a k-ary relation over Const Null, i.e., a finite subset of pConst Nullq k . There are two types of such incomplete relational instances:

-In naïve databases, there are no restrictions on the appearance of nulls; in particular, a null u Null can appear multiple times in such an instance.

-In Codd databases, each null u Null appears at most once, i.e., repetitions are not allowed.

If we talk about single relations, it is common to refer to them as naïve tables and Codd tables.

We write ConstpDq and NullpDq for the sets of constants and nulls that occur in a database D. The active domain of D is adompDq ConstpDq NullpDq.

We called databases that contain no nulls complete, i.e., for such a database D we have adompDq Const. In particular, these are special cases of what we called incomplete databases earlier, and indeed incompleteness may manifest itself not only by the presence of nulls but also, for instance, by missing tuples.

In the remainder of the paper, we always assume that the schema is fixed and arbitrary.

Homomorphisms

Homomorphisms are crucial for us in two contexts: to define the semantics of incomplete databases, and to define the notion of preservation of logical formulae as a condition for naïve evaluation to work. In database literature, it is common to require that homomorphisms preserve elements of Const, i.e., the map h is also required to satisfy hpcq c for every c Const. Of course this can easily be cast as a special instance of the general notion of homomorphism, simply by extending the vocabulary with a constant symbol for each c Const.

Given two relational instances

In this article we shall refer to homomorphisms which are the identity on Const as database homomorphisms (whenever there is ambiguity). We will only deal with such homomorphisms to characterize semantic orderings and to work with a suitable notion of the core.

Given a homomorphism h and a database D, by hpDq we mean the image of D, i.e., the set of all tuples Sphpūqq where Spūq is in D. If h : D Ñ D I is a homomorphism, then hpDq is a subinstance of D I .

Semantics and valuations

We shall see many possible semantics for incomplete information, but first we review two common ones: open-world and closed-world semantics. We need the notion of a valuation, which assigns a constant to each null. That is, a valuation is a database homomorphism whose image contains only values in Const.

In general, the semantics rrDss of an incomplete database is a set of complete databases D I , i.e., databases D I with adompD I q Const. The semantics under the closed-world assumption (or CWA semantics) is defined as

rrDss CWA thpDq | h is a valuationu.
The semantics under the open-world assumption (or OWA semantics) is defined as rrDss OWA tD I | D I is complete and there is a valuation h : D Ñ D I u. Alternatively, D I rrDss OWA iff D I is complete and contains a database D P rrDss CWA as a subinstance.

Example 2.1. As an example, consider D 0 tpu, u I q, pu I , uqu. Then rrD 0 ss CWA consists of all instances tpc, c I q, pc I , cqu with c, c I Const (and possibly c c I ), and rrD 0 ss OWA has all complete instances containing tpc, c I q, pc I , cqu, for c, c I Const.

Certain answers and naïve evaluation

Relational query languages considered in this article are fragments of FO (first-order logic). The syntax of FO formulae is as follows:

ϕ : Rpxq | x y | ϕ ϕ | ϕ ϕ | 2ϕ | hxϕ | dxϕ ,
where R ranges over relational symbol, x refers to a tuple of variables and x and y to individual variables. The h, -fragment of FO is known as conjunctive queries (i.e., , 2, d are omitted). In terms of their expresiveness, they correspond to select-projectjoin queries of relational algebra. Unions of conjunctive queries have the same power as the h, , -fragment of FO, or the select-project-join-union fragment of relational algebra.

Note that for the sake of presentation, for now we deal with queries without constants. However our results can be easily extended to queries that can refer to finitely many constants, as will be explained in Section 11. Note also that in this article we assume the active domain semantics for relational first-order queries. That is, the semantics of quantification is with respect to the active domain: given a tuple ā over adompDq, the formula hx ϕpx, āq holds in D iff ϕpa, āq holds in D for some a adompDq, and dx ϕpx, āq holds in D iff ϕpa, āq holds in D for all a adompDq.

It is important to note that this is the semantics of FO queries also in the case that adompDq contains nulls: nulls are just considered as additional (pairwise distinct) domain elements, other than the constant elements.

Given an incomplete database D, a semantics of incompleteness rr ss, and a query Q, one normally computes certain answers under the rr ss semantics: certainpQ, Dq £ tQpD I q | D I rrDssu,

i.e., answers that are true regardless of the interpretation of nulls under the given semantics. When rr ss is rr ss OWA or rr ss CWA , we write certain OWA pQ, Dq or certain CWA pQ, Dq.

A:7

Even for first-order queries, the standard semantics of incompleteness are problematic in general: finding certain answers under the OWA semantics may be undecidable, and finding them under the CWA semantics may be CONP-hard [START_REF] Abiteboul | On the representation and querying of sets of possible worlds[END_REF]].

Definition 2.2 pNaïve evaluation for relational instancesq. Naïve evaluation of a query Q over an incomplete relational instance refers to a two-step procedure: first, evaluate Q on the incomplete instance itself, as if nulls were values (i.e., equal iff they are syntactically the same: e.g., u 1 u 1 , u 1 $ u 2 , u 1 $ c for every c Const), and then eliminate tuples with nulls from the result. Note that if Q is a Boolean query, the second step is unnecessary.

We say that naïve evaluation works for Q (under semantics rr ss) if its result is exactly the certain answers under rr ss, for every D.

FACT 1. (see [START_REF] Imielinski | Incomplete information in relational databases[END_REF][START_REF] Libkin | Incomplete information and certain answers in general data models[END_REF]) Let Q be a union of conjunctive queries. Then naïve evaluation works for Q under both OWA and CWA. Moreover, if Q is a Boolean FO query and naïve evaluation works for Q under OWA, then Q is equivalent to a union of conjunctive queries.

The last equivalence result only works under the OWA semantics, as discussed in the following example Example 2.3. Consider again the instance D 0 defined in Example 2.1 and a query hx, y pDpx, yq Dpy, xqq. The certain answer to this query is true under both OWA and CWA, and indeed it evaluates to true naïvely over D 0 . On the other hand, a query Q given by dxhy Dpx, yq (not equivalent to a union of conjunctive queries) evaluated naïvely, returns true on D 0 . In fact recall that x and y range over the active domain of D 0 , and it is true that every domain element of D 0 occurs in the first column. But under OWA the certain answer to Q is false. In fact Q evaluates to false for example over the complete instance tpc, cq, pc, dqu which belongs to rrD 0 ss OWA . This shows that naïve evaluation does not work for Q under the OWA.

However note that, under CWA, the certain answer to Q is true, and therefore coincides with the result of Q naïvely evaluated over D. Indeed Q evaluates to true over all instances in rrD 0 ss CWA , since these can only be of the form tpc, c I q, pc I , cqu with c, c I Const, and possibly c c I . The case shown in Example 2.3 is not an isolated phenomenon: we will later see that the query Q of Example 2.3 belongs to a class, extending unions of conjunctive queries, for which naïve evaluation works under CWA on all databases.

NA ÏVE EVALUATION AND MONOTONICITY

The goal of this section is twofold. First we present a very general setting for talking about incompleteness and its semantics, as well as orderings representing the notion of "having more information". We formulate the notion of naïve evaluation in this setting, and show that it guarantees to compute certain answers for monotone queries.

Database domains, semantics, and ordering

We now define a simple abstract setting for handling incompleteness. We operate with just four basic concepts: the set of instances, the set of complete instances, their isomorphism, and their semantics.

Definition 3.1 pDatabase domainq. A database domain is a structure D xD, C, rr ss, y, where D is a set, C is a subset of D, the function rr ss is from D to nonempty subsets of C, and is an equivalence relation on D.

The interpretation is as follows:

A:8 -D is a set of database objects -C is the set of complete objects rrxss C is the semantics of an incomplete database object x, i.e., the set of all complete objects that x can represent; and -is the structural equivalence relation, that we need to describe the notion of generic queries;

For instance in the relational setting, D represents the set of all possible incomplete relational databases, C the ones without nulls, the semantics rr ss could be for instance rr ss OWA or rr ss CWA , and is the isomorphism relation of relational instances. More precisely we define: Definition 3.2 pRelational database domainq. We say that D is a relational database domain if D xD, C, rr ss, y, where D is the set of (possibly incomplete) relational instances over some schema, C is the set of complete relational instances over this schema, and is the isomorphism relation between instances (i.e. D D I iff there exists an injective mapping π on adompDq such that πpDq D I ).

Of course there could be many non-relational database domains of interest, for instance, all XML documents of a given schema or all graph databases over a fixed labeling alphabet.

The semantic function of a database domain lets us describe the degree of incompleteness via an ordering defined as

x ¨y ô rryss rrxss.

Indeed, the less we know about an object, the more other objects it can potentially describe. As an example, if D 0 tpu, u I q, pu I , uqu and D 1 tpu, uqu, then D 0 ¨D1 under both OWA and CWA, since D 1 describes fewer instances than D 0 . This setting is reminiscent of the ideas in programming semantics, where partial functions are similarly ordered [START_REF] Gunter | Semantics of Programming Languages: Structures and Techniques[END_REF]], and such orderings have been used to provide semantics of incompleteness in the past [START_REF] Buneman | Using Powerdomains to Generalize Relational Databases[END_REF][START_REF] Libkin | A semantics-based approach to design of query languages for partial information[END_REF]2011;[START_REF] Ohori | Semantics of types for database objects[END_REF][START_REF] Rounds | Situation-theoretic aspects of databases[END_REF]]. Note that ¨is a preorder.

Queries and certain answers. For now we look at Boolean queries in the most abstract setting (we will generalize them later). Outputs of Boolean queries are 0 or 1, with 0 representing false and 1 representing true. Note that in the relational setting Boolean queries are queries of arity 0, where we associate the value 0 to the empty set and the value 1 to the query result tpqu, containing a single tuple.

Definition 3.3 pQueries, certain answers, and naïve evaluationq. For a database domain D xD, C, rr ss, y, a query is a mapping Q : D Ñ t0, 1u.

A query is generic if Qpxq Qpyq whenever x y.

For each x D, the certain answer under the semantics rr ss is certainpQ, xq

© tQpcq | c rrxssu

We say that naïve evaluation works for Q if Qpxq certainpQ, xq for every x. We say that naïve evaluation works over D I D if Qpxq certainpQ, xq for every x D I .

We remark that for a relational database domain and a Boolean relational query, the above definition of certain answers coincides with the usual intersection-based relational definition of certain answers given in Section 2.4.

Note also that in this abstract setting queries are defined on all database objects, both complete and possibly incomplete. We have already remarked in Section 2.4 that an FO query is evaluated over a relational instance with nulls by considering nulls as additional (pairwise distinct) domain elements. Thus if Q is an FO Boolean query and D is an incomplete relational instance, QpDq is precisely the result of evaluating Q naïvely over D in the sense of Definition 2.2. Therefore when considering relational database domains, Definition 3.3, specifying when naïve evaluation works, coincides with Definition 2.2. Saturation property. We now impose an additional property on database domains saying, essentially, that there are enough complete objects. Definition 3.4 pSaturationq. A database domain D xD, C, rr ss, y is saturated if every object has in its semantics a complete object that is isomorphic to it: that is, for each x D there is y rrxss such that x y.

In the case of the usual relational semantics of incompleteness, this property trivially holds: if we have an instance D with nulls u 1 , . . . , u n , we simply replace them with distinct constants c 1 , . . . , c n that do not occur elsewhere in D, to obtain a complete database isomorphic to D. Nonetheless, there are other semantics, primarily motivated by AI considerations, that are not saturated; we shall deal with them in Section 8.

Naïve evaluation and monotonicity

We now relate naïve evaluation to some monotonicity properties of queries in the most general setting of arbitrary database domains.

We say that a query Q over a database domain is weakly monotone if for all x D and y C y rrxss ñ Qpxq ¤ Qpyq.

That is, if y is a complete object representing x, and Q is already true on x, then Q must be true on y. This property characterizes naïve evaluation over saturated database domains.

THEOREM 3.5. Let D be a database domain with the saturation property, and Q a generic Boolean query. Then naïve evaluation works for Q iff Q is weakly monotone.

PROOF. The statement follows immediately from the more general Theorem 8.2 which will be proved in Section 8. However we provide a direct simple proof here for completeness.

Let Q be a Boolean generic query. Assume that naïve evaluation works for Q over D;

i.e., Qpxq tQpcq | c rrxssu for all x. Now let Qpxq 1 and let y rrxss. If Qpyq 0, then tQpcq | c rrxssu 0, and by the assumption Qpxq is 0 as well. This contradiction shows that Qpyq 1 and thus Q is weakly monotone.

Conversely assume that Q is weakly monotone, and let x D. By weak monotonicity we have Qpxq ¤ certainpQ, xq. To prove that certainpQ, xq ¤ Qpxq, assume certainpQ, xq 1. By the saturation property there exists c rrxss such that c x. We know Qpcq 1; then by genericity Qpxq 1. Hence certainpQ, xq Qpxq for all x D, i.e. naïve evaluation works for Q.

Of course one can also look at the natural definition of monotonicity: a query Q is monotone if x ¨y implies Qpxq ¤ Qpyq. Recall that x ¨y means that rryss rrxss. This condition turns out to be equivalent to weak monotonicity in database domains that satisfy one additional property. To state it, note that there is a natural duality between preorders (i.e., transitive reflexive binary relations) and semantics: each semantics rr ss gives rise to the ordering x ¨y ô rryss rrxss, and conversely any preorder ¤ on D gives a semantics rrxss ¤ ty C | x ¤ yu. We say that a database domain is fair if rr ss and its ordering ¨agree: that is, the semantics that the ordering ¨gives rise to is rr ss itself. Fair domains can be easily characterized: PROPOSITION 3.6. A database domain D is fair iff the following conditions hold:

(1) c rrcss for each c C;

(2) if c rrxss, then rrcss rrxss.

PROOF. Let D xD, C, rr ss, y be a database domain and let ¨be the preorder obtained from it.

First assume that (1) and (2) hold of D. Recall that by definition for all x, y D, x ¨y iff rryss rrxss and so rrxss ¨ tc C | rrcss rrxssu. We want to show that D is fair, i.e., for all x D, rrxss rrxss ¨. So let x D and c C such that c rrxss. By condition 2, rrcss rrxss. But then c rrxss ¨and so for all x, rrxss rrxss ¨. Now let x D, c C such that c rrxss ¨. So rrcss ¨rrxss. By condition 1, c rrcss, which yields c rrxss and so for all x, we have rrxss ¨ rrxss.

Conversely assume D is fair, i.e., for all x D, rrxss rrxss ¨ tc C | rrcss rrxssu. So in particular for all c C, rrcss tc I C | rrc I ss rrcssu. As rrcss rrcss, it follows that c rrcss, that is, condition (1) holds. Condition (2) follows immediately from rrxss tc C | rrcss rrxssu.

The standard relational semantics of incompleteness -including all those seen in the previous section -satisfy these conditions. The first condition says that the semantics of a complete object should contain at least that object. The second says that by removing incompleteness from an object, we cannot get one that denotes more objects. Note also that in a fair domain, y rrxss implies x ¨y, so weak monotonicity is indeed weaker than monotonicity.

In fair database domains, we can extend Theorem 3.5: PROPOSITION 3.7. Let D be a fair database domain with the saturation property, and Q a generic Boolean query. Then the following are equivalent:

(1) Naïve evaluation works for Q;

(2) Q is monotone;

(3) Q is weakly monotone.

PROOF. We need to prove that in a fair database domain naive evaluation works for Q iff Q is monotone. Assume that naïve evaluation works for Q, and consider objects x, y D such that x ¨y and Qpxq 1. We prove Qpyq 1. We have Qpxq certainpQ, xq 1 and rryss rrxss, therefore certainpQ, yq Qpyq 1.

Conversely assume that Q is monotone. Let x be in D, we prove that Qpxq certainpQ, xq. Let c rrxss. Since the database domain is fair, x ¨c. Then the monotonicity of Q implies Qpxq ¤ Qpcq, and therefore Qpxq ¤ certainpQ, xq. In order to prove certainpQ, xq ¤ Qpxq, assume certainpQ, xq 1; by the saturation property there exists c I rrxss such that c I x. We know Qpc I q 1, then by genericity, Qpxq 1.

This shows Qpxq certainpQ, xq -i. e. naïve evaluation works for Q -and concludes the proof of the proposition.

Theorem 3.5 and Proposition 3.7 establish the promised connection between monotonicity and naïve evaluation. Extension to non-Boolean queries is given in Section 6.

SEMANTICS, RELATIONS, AND HOMOMORPHISMS

We have seen that characterizing cases in which naïve evaluation work, at least for Boolean queries, is equivalent to requiring (weak) monotonicity of queries. To apply this strategy to concrete semantics of incompleteness, we need to understand how different semantics can be defined. In the most general setting we explain that most of them are obtained by composing two types of relations between database objects. In the relational setting the first relation corresponds to applying valuations to nulls, and the other to specific semantic assumptions such as open or closed-world. After we clarify this point, we then move to relational database domains and we show a connection between naïve evaluation and preservation under a class of homomorphisms.

Semantics via relations

We have already seen two concrete relational semantics: the OWA semantics rrDss OWA and the CWA semantics rrDss CWA . What is common to them is that they are all defined in two steps. First, valuations are applied to nulls (i.e., nulls are replaced by values). Second, the resulting database may be modified in some way (left as it was for CWA, or expanded arbitrarily for OWA). Our idea is then to capture this via two relations. We now define them in the setting of arbitrary database domains and then show how they behave in concrete cases.

Given a database domain D xD, C, rr ss, y, we consider a pair R pR val , R sem q of relations:

-The valuation relation R val D ¢ C between arbitrary databases and complete databases. Intuitively, a pair px, cq is in R val if c is obtained from x by replacing nulls by constants. The restriction of R val to C is the identity: R val pC ¢ Cq tpc, cq | c Cu (if there are no nulls, there is no substitution). And since for every object there is some way to replace nulls by constants, R val is total.

-The semantic relation R sem is a reflexive binary relation on

C (i.e., R sem C ¢ C).
Intuitively, this corresponds to the modification step such as extending complete relations by new tuples. Since, at the very least, one can do nothing with the result of the substitution of nulls by constants, such a relation must be reflexive.

Definition 4.1 pSemantics given by Rq. For R pR val , R sem q satisfying the above conditions, we say that rr ss is given by R if y rrxss ô px, yq R val ¥ R sem for every x D and y C. In other words, y rrxss iff for some z C we have px, zq R val and pz, yq R sem .

PROPOSITION 4.2. Let D be a database domain whose semantics rr ss is given by a pair R pR val , R sem q. Then D is fair iff R sem is transitive.

PROOF. Assume first that R sem is transitive, and take arbitrary x D and c C. We have (1) c rrcss. Indeed we know pc, cq R val and pc, cq R sem (recall from Definition 4.1 that R sem is always reflexive), then c rrcss.

(2) c rrxss implies rrcss rrxss.

Indeed if c rrxss then there exists y C such that px, yq R val and py, cq R sem . Moreover if c I rrcss then pc, c I q R sem (because R val is the identity when restricted to C). By transitivity of R sem we then have py, c I q R sem . This implies px, c I q R val ¥ R sem , and therefore c I rrxss.

By Proposition 3.6, D is fair.

Conversely assume that D is fair, and assume there exist pc, dq and pd, eq in R sem . Now recall that pc, cq and pd, dq are in R val , thus pc, dq and pd, eq are in R val ¥ R sem , i.e., d rrcss and e rrdss. By item (2) of Proposition 3.6, e rrcss. Then pc, eq R sem . This proves that R sem is transitive.

A:12

Relational databases. When we deal with relational database domains, the most natural valuation relation is R rdb val defined as follows:

pD, D I q R rdb val ô D I vpDq for some valuation v.

So we assume, for now, that in relational semantics of incompleteness, the valuation relation is R rdb val . Thus such semantics are completely specified by relation R sem . More precisely, we define them as follows.

Definition 4.3 pRelational semantics given by R sem q. We say that a relational semantics rr ss is given by relation R sem if it is given by the pair pR rdb val , R sem q. That is, for all databases D, D I D I rrDss ô there is a valuation v such that pvpDq, D I q R sem .

The OWA and CWA semantics are given by particularly easy relations R sem :

-For CWA, R sem is the identity (i.e., ); -For OWA, R sem is the subset relation (i.e., ).

The special form of relation R rdb val , and the reflexivity of R sem , imply the saturation property. Indeed R rdb val does allow us to replace nulls by distinct constants that do not occur elsewhere in the instance. Therefore, by Theorem 3.5 we have: PROPOSITION 4.4. For an arbitrary relational semantics given by relation R sem , and an arbitrary generic Boolean query Q, naïve evaluation works for Q iff Q is weakly monotone.

Naïve evaluation over relational databases via homomorphism preservation

We shall now relate weak monotonicity and preservation under homomorphisms for relational semantics. We deal with general relational semantics given by relations R sem .

Definition 4.5 pR sem -homomorphism and preservationq. For complete databases D and D I , a mapping h defined on the active domain adompDq of D is an R sem - homomorphism from D to D I if phpDq, D I q R sem .

A query Q is preserved under R sem -homomorphisms if for every pair of databases

D, D I and every R sem -homomorphism h from D to D I , if Q is true in D, then Q is true in D I .
PROPOSITION 4.6. If a relational semantics is given by a relation R sem and Q is a generic Boolean query, then Q is weakly monotone iff it is preserved under R semhomomorphisms.

Although the proposition deals with relational semantics given by R sem , we will prove a slightly more general result (namely Corollary 4.11 below) holding for arbitrary relational semantics given by a pair pR val , R sem q, and will obtain Proposition 4.6 as a special case where R val R rdb val . Moreover some of the intermediate results needed to prove Proposition 4.6 hold for arbitrary database domains (not necessarily relational) and will therefore be stated in their full generality.

For stating these general results we need the following additional definitions on arbitrary database domains.

Definition 4.7. If D xD, C, rr ss, y is a database domain, Q : D Ñ t0, 1u is a query, and R D ¢ D, we say that Q is preserved under R if Qpxq 1 implies Qpyq 1 whenever px, yq R.

A:13

Definition 4.8 p-equivalenceq. If D xD, C, rr ss, y is a database domain and R and R I are subsets of D ¢ C, we say that R I is -equivalent to R if the following two conditions are satisfied:

(1) if px, cq R then there exists x I D such that x I x and px I , cq R I ;

(2) if px, cq R I then there exists x I D such that x I x and px I , cq R.

We say that R I is strongly -equivalent to R if moreover x I in the definition ofequivalence only depends on x (and not on c).

PROOF OF PROPOSITION 4.6. We first relate weak monotonicity and preservation for arbitrary database domains. Intuitively weak monotonicity corresponds to preservation under any relation which is -equivalent to the semantics : LEMMA 4.9. Let D xD, C, rr ss, y be an arbitrary database domain and let R I D ¢C be -equivalent to the graph of rr ss. Then a generic Boolean query over D is weakly monotone iff it is preserved under R I .

PROOF. Assume that Q is a generic Boolean query over D, and Q is weakly monotone. Consider a pair px, cq R I and assume that Qpxq 1. By the fact that R I is -equivalent to the graph of rr ss, there exists y D, such that y x and c rryss. Since Q is generic Qpyq 1, and since Q is weakly monotone Qpcq 1. This proves that Q is preserved under R I . The converse is proved symmetrically.

In particular, when the semantics of the arbitrary database domain is given by a pair pR val , R sem q, we have: LEMMA 4.10. Let D xD, C, rr ss, y be a database domain whose semantics rr ss is given by a pair pR val , R sem q and let R I D ¢ C be -equivalent to R val , then R I ¥ R sem is -equivalent to the graph of rr ss (i.e. to R val ¥ R sem ). In particular, a generic Boolean query over D is weakly monotone iff it is preserved under R I ¥ R sem .

PROOF. Assume that px, cq R val ¥ R sem . Then there exists e C such that px, eq R val and pe, cq R sem . We know that there exists x I D such that x I x and px I , eq R I . Then px I , cq R I ¥ R sem . Symmetrically we prove that for all px I , cq R I ¥ R sem there exists x D such that x I x and such that px, cq R val ¥ R sem . We conclude by Lemma 4.9.

We are now ready to move to relational database domains and finish the proof of the proposition.

If M is a function associating to each complete relational instance D a class of mappings adompDq Ñ Const, we say that M is a mapping type. If M is a mapping type, we denote by R M the set of pairs tpD, hpDqq | D is a complete relational instance and h

MpDqu. Given two complete relational instances D and D I , an M-R sem -homomorphism

from D to D I is an R sem -homomorphism h from D to D I such that h MpDq.
The following claim follows directly from definitions:

CLAIM 1. If M is a mapping type then pD, D I q R M ¥ R sem iff there exists an M-R sem -homomorphism from D to D I .
By combining the above claim with Lemma 4.10 we have:

COROLLARY 4.11. Let D xD, C, rr ss, y be a relational database domain whose semantics rr ss is given by a pair pR val , R sem q and let M be a mapping type. Assume that R M is -equivalent to R val . Then a generic Boolean query over D is weakly monotone iff it is preserved under M-R sem -homomorphisms.

Proposition 4.6 will be obtained as a special case of Corollary 4.11. To prove it, we consider the mapping type M all, associating with each complete relational instance D the set of all mappings adompDq Ñ Const, and we prove the following lemma: LEMMA 4.12. If M all and is the isomorphism relation between relational instances, then R M is strongly -equivalent to R rdb val . PROOF. Let D be a (possibly incomplete) relational instance. We prove that there exists a complete relational instance E such that 1) D E and 2) pD, D I q R rdb val implies pE, D I q R M .

The instance E is obtained from D by replacing nulls of D with new distinct constants not occurring in ConstpDq. Clearly there exists an isomorphism i : E Ñ D, thus E D. Now let pD, D I q R rdb val . Then D I vpDq for some valuation v. Let h v ¥i; then hpEq vpDq D I and hence pE, D I q R M (because M all). This proves 1) and 2) above.

Conversely let E be a complete relational instance. We prove that there exists a relational instance D such that 1) D E and 2) pE, D I q R M implies pD, D I q R rdb val . The instance D is obtained from E by replacing each element of adompEq with a new distinct null. Clearly this replacement defines an isomorphism i : D Ñ E and therefore E D. Now let pE, D I q R M . We know that D I hpEq where h is an arbitrary mapping adompEq Ñ Const. Let v h ¥i. Then v is a valuation on D (because adompDq contains no constants, and D I is complete) and hence pD, D I q R rdb val . Now remark that with M all, M-R sem -homomorphisms coincide with R semhomomorphisms. Then Proposition 4.6 follows immediately from Corollary 4.11 with M all. l

Putting together Proposition 4.4 and Proposition 4.6, we have our first key result for naïve evaluation over incomplete databases. THEOREM 4.13. For a relational incompleteness semantics given by a semantic relation R sem , and a generic Boolean query Q, naïve evaluation works for Q iff Q is preserved under R sem -homomorphisms.

Homomorphisms for specific relational semantics

Theorem 4.13 connects naïve evaluation with homomorphism preservation. We now investigate what these R sem -homomorphisms are in some specific cases.

-CWA semantics. In this case R sem is the identity, and the definition states that h is an R sem -homomorphism from D to D I if D I hpDq. That is, under CWA, R semhomomorphisms are the strong onto homomorphisms, i.e., homomorphisms from D to hpDq.

-OWA semantics. In this case R sem is , and the definition states that h is an R semhomomorphism from D to D I if hpDq D I . That is, under OWA, R sem -homomorphisms are just the usual homomorphisms.

Another well known notion of homomorphisms is that of onto homomorphisms.

When used in the database context, an onto homomorphism h from D to D I is a ho- momorphism between D and D I so that hpadompDqq adompD I q. For instance, if D tp1, 2qu, and hp1q 3, hp2q 4, then h is a strong onto homomorphism from D to D 1 tp3, 4qu, and an onto homomorphism from D to D 2 tp3, 4q, p4, 3qu. Note that while D 2 contains more than hpDq, all the tuples in D 2 only use elements that occur in hpDq. However h is only a usual homomorphism from D to D 3 tp3, 4q, p3, 5qu.

A semantics of incompleteness that corresponds to the notion of onto homomorphism, that we refer to as weak CWA, or WCWA semantics, was actually previously studied [START_REF] Reiter | On closed world data bases[END_REF]] (in a slightly different, deductive-database context). We define it as follows:

rrDss WCWA 4 D I § § § §
D I is complete and there is a valuation h : D Ñ D I so that adompD I q adomphpDqq B .

In other words, it is not completely closed world: a database can be extended, but still in a rather limited fashion, only with the tuples that use values already stored in the database.

For this semantics, R sem contains all pairs pD, D I q so that D D I and adompDq adompD I q. That is, D can be expanded only within its active domain. Thus, R semhomomorphisms are exactly onto homomorphisms.

For this relation R sem , the notion of preservation under R sem -homomorphisms is exactly the notion of preservation under onto homomorphisms. Thus, the WCWA semantics, defined long time ago, also corresponds to a very natural logical notion of preservation.

Note that rrDss CWA rrDss WCWA rrDss OWA , and in general inclusions can be strict. For instance, if D tpu, u I qu, then tp1, 2qu is in rrDss CWA , while tp1, 2q, p2, 1qu is not in rrDss CWA but is in rrDss WCWA , since it added a tuple p2, 1q that uses elements already present in t1, 2u.

Naïve evaluation and relational semantics. We can finally state the equivalence of naïve evaluation and homomorphism preservation for three concrete semantics of incomplete relational databases: COROLLARY 4.14. Let Q be a Boolean generic query. Then:

-Under OWA, naïve evaluation works for Q iff Q is preserved under homomorphisms.

-Under CWA, naïve evaluation works for Q iff Q is preserved under strong onto homomorphisms. -Under WCWA, naïve evaluation works for Q iff Q is preserved under onto homomorphisms.

NA ÏVE EVALUATION AND PRESERVATION FOR FIRST-ORDER QUERIES

Corollary 4.14 reduces the problem of checking whether naïve evaluation works under the most common relational semantics to preservation under homomorphisms. Thus, for FO queries, we deal with a very well known notion in logic [START_REF] Chang | Model Theory[END_REF]. However, what we need is preservation on finite structures, and those notions are well known to behave differently from their infinite counterpart. In fact, it was only proved recently by Rossman that for FO sentences, preservation under arbitrary homomorphisms in the finite is equivalent to being an existential positive formula [START_REF] Rossman | Homomorphism preservation theorems[END_REF]. In database language, this means being a union of conjunctive queries, which led to an observation [START_REF] Libkin | Incomplete information and certain answers in general data models[END_REF]] that naïve evaluation works for a Boolean FO query Q iff Q is equivalent to a union of conjunctive queries. The difficulty in establishing preservation results in the finite is due to losing access to classical logical tools such as compactness. Rossman's theorem, for instance, was a major open problem for many years. To make matters worse, even some existing infinite preservation results [Keisler 1965b] have holes in their proofs.

Thus, it is unrealistic for a single paper to settle several very hard problems concerning preservation results in the finite (sometimes even without infinite analogs!). What we shall do instead is settle for classes of queries that imply preservation under different notions of homomorphism, and at the same time are easy to describe syntactically.

Positive and existential positive formulae. Recall that positive formulae use all the FO connectives except negation (i.e., , , d, h). Formally, the class Pos of positive formulae is defined inductively as follows:

true and false are in Pos;

-every positive atomic formula (i.e., Rpxq or x y) is in Pos; -if ϕ, ψ Pos, then ϕ ψ and ϕ ψ are in Pos; -if ϕ is in Pos, then hxϕ and dxϕ are in Pos.

If only hxϕ remains in the class, we obtain the class hPos of existential positive formulae. Formulae from hPos, as was mentioned earlier, have the same power as unions of conjunctive queries.

Observe that the Pos fragment disallows logical implication as well, since it hides a form of negation. Extensions of Pos which will be introduced later will allow a limited form of implication.

Rossman's theorem [START_REF] Rossman | Homomorphism preservation theorems[END_REF]] says that an FO sentence ϕ is preserved under homomorphisms over finite structures iff ϕ is equivalent to a sentence from hPos.

Lyndon's theorem [START_REF] Chang | Model Theory[END_REF] says that an FO sentence ϕ is preserved under onto homomorphisms (over arbitrary structures) iff ϕ is equivalent to a sentence from Pos. Lyndon's theorem fails in the finite [START_REF] Ajtai | Monotone versus positive[END_REF][START_REF] Stolboushkin | Finitely monotone properties[END_REF] but the implication from being positive to preservation is still valid. A characterization of preservation under strong onto homomorphisms was stated in [Keisler 1965a;1965b], but the syntactic class had a rather messy definition and was limited to a single binary relation. Even worse, we discovered a gap in one of the key lemmas in [Keisler 1965b]. So instead we propose a simple extension of positive formulae that gives preservation under strong onto homomorphisms.

The class Pos is a very natural logical class, and indeed it has been studied extensively by logicians. From the database perspective, however, unrestricted universal quantification is not that common: indeed, most of universal queries say "for every tuple in a relation" or "for every value appearing as a value of an attribute". We now define an extension of Pos capturing such queries. It turns out that this extension matches the commonly used closed-world semantics.

Extensions with universal guards. The fragment Pos dG, whose definition is inspired by [START_REF] Compton | Some useful preservation theorems[END_REF]], extends Pos with universal guards. It is defined as follows:

true and false are in Pos dG; -every positive atomic formula (i.e., Rpxq or x y) is in Pos dG; -if ϕ, ψ Pos dG, then ϕ ψ and ϕ ψ are in Pos dG; -if ϕ is in Pos, then hxϕ and dxϕ are in Pos dG.

-if ϕpx, ȳq is in Pos dG, and R is an n-ary relation symbol, then the formula dx 1 , . . . , x n Rpx 1 , . . . , x n q Ñ ϕpx 1 , . . . , x n , ȳq ¨is in Pos dG if x 1 , . . . , x n are pairwise distinct variables; -if ϕpx, z, ȳq is in Pos dG, and x, z are distinct variables, then the formula dx, z x z Ñ ϕpx, z, ȳq ¨is in Pos dG.

Note that the last rule is redundant, since the formula is equivalent to dx ϕpx, x, ȳq ẅhich is already expressible in the fragment (the fragment allows arbitrary universal quantification). However it will be useful later for defining restrictions of Pos dG.

Note also that the first four rules are the same as for Pos, so we have hPos Pos Pos dG.

The difference between Pos and Pos dG is emphasized in the following example, which also witnesses the strict inclusions hPos Pos Pos dG.

Example 5.1. Consider a relational schema consisting of a binary relation R and a unary relation S, and sentences ϕ dx Spxq and ψ dx, y pRpx, yq Ñ Spxqq. Clearly ϕ is both in Pos and Pos dG, while ψ is in Pos dG. First remark that ϕ is not in hPos because it is clearly not preserved under homomorphisms (it is non-monotone w.r.t inclusion). We now show that ψ is not in Pos, since it is not preserved under onto homomorphisms (while all formulae of Pos are). In fact consider databases D and D I so that R is interpreted as tp1, 2qu in D, as tp1, 2q, p2, 1qu in D I , and S is interpreted as tp1qu in both. Clearly D has an onto homomorphism h to D I (which is the identity In order to prove preservation for sentences, we need to prove it for arbitrary formulas of the fragment and then proceed by structural induction. To this end we need first to define what it means for a formula with free variables to be preserved under (strong onto) homomorphisms.

Definition 5.3. If Q is a k-ary relational query over complete instances (i.e. a mapping associating to each complete relational instance D a k-ary relation over adompDq), we say that Q is preserved under (strong onto) homomorphisms if, whenever h is a (strong onto) homomorphism from an instance D to an instance D I , and ā QpDq then hpāq QpD I q.

Proposition 5.2 is a corollary of the following lemma (which incidentally will be crucial when extending all our results to the case of non-Boolean queries) LEMMA 5.4. Formulas in Pos dG are preserved under strong onto homomorphisms.

PROOF.

We proceed by structural induction on the formula ϕ. If ϕ false or ϕ true, it is clearly preserved under strong onto homomorphisms.

Assume now that ϕpxq is a positive atom Rpȳq (including the case of an equality atom), where variables occurring in ȳ are precisely x. It follows from the definition of homomorphism that if an instance D | ù ϕpāq then hpDq | ù ϕphpāqq, for every homomorphism h.

It is also easy to verify that if ϕ 1 and ϕ 2 are preserved under strong onto homomorphisms, so are ϕ 1 ϕ 2 and ϕ 1 ϕ 2 . Now assume ϕpxq hyϕ I py, xq, where ϕ I is preserved under strong onto homomorphisms. Assume that an instance D | ù ϕpāq, and that h is a strong onto homomorphism from D to D I hpDq. We next assume that ϕpx, ȳq Pos dG is preserved under strong onto homomorphisms and show that dx pRpxq Ñ ϕq is, where x px 1 , . . . , x n q is a tuple of pairwise distinct variables. Let D | ù dxpRpx 1 , . . . , x n q Ñ ϕpx, āqq and let D I hpDq where h is a homomorphism. We must show D I | ù dxpRpx 1 , . . . , x n q Ñ ϕpx, hpāqq. Let b pb 1 , . . . , b n q be a tuple such that D I | ù Rp bq. As D I hpDq, there are c 1 , . . . , c n in adompDq such that b hpcq (i.e., b i hpc i q for each i t1, . . . , nu) and D | ù Rpc 1 , . . . , c n q. Since the x i s are pairwise distinct, this means that D | ù Rpx 1 , . . . , x n q under any valuation sending x i to c i for each i ¤ n. By D | ù dxpRpx 1 , . . . , x n q Ñ ϕpx, āqq, we conclude that D | ù ϕpc, āq and so, by the inductive hypothesis, D I | ù ϕphpcq, hpāqq, which implies D I | ù dxpRpx 1 , . . . , x n q Ñ ϕpx, hpāqq.

The case of the equality atom in the guarded formula is exactly the same as the above case of the relational atom. This concludes the proof of Proposition 5.2. By Proposition 4.6 sentences of Pos dG define weakly monotone queries under CWA.

We remark that this notion of weak monotonicity is different from the usual notion of monotonicity of relational queries, as witnessed by the sentence ϕ Pos dG defined in Example 5.1, which is clearly non-monotone.

Note that the condition that the variables x i s of guards be pairwise distinct in the syntax of Pos dG is essential, as shown by the following example.

Example 5.5. Consider a formula ϕ dx pRpx, xq Ñ Spxqq, and databases D and D I so that R is interpreted as tp1, 2qu in D, as tp3, 3qu in D I , and S is empty in both. Then D | ù ϕ, while D I | ù 2ϕ, even though D I hpDq under the homomorphism h that sends both 1 and 2 to 3.

The following example witnesses that the condition that variables of guards are all universally quantified is also essential in the syntax of Pos dG.

Example 5.6. Consider a formula ϕ hxdy pRpx, yq Ñ Spyqq. It does not conform to the syntax of Pos dG since the variable x of the guard Rpx, yq is not universally quantified. We show that ϕ is not preserved under strong onto homomorphisms (and therefore naïve evaluation does not work for ϕ under the CWA).

Consider databases D and D I so that R is interpreted as tp1, 2q, p3, 4qu in D, as tp1, 2q, p1, 4qu in D I , and S is interpreted as tp2qu in both. Clearly D | ù ϕ; moreover D I hpDq where hp3q 1 and h is the identity elsewhere, so h is a strong onto homomorphism from D to D I . However D I | ù 2ϕ since Sp4q does not hold in D I . This problem is avoided if all variables of guards are universally quantified, as for instances in the sentence hxdypSpyq Ñ Rpx, yqq which is in Pos dG, and is satisfied both in D and D I .

We now combine all the previous implications (preservation Ñ monotonicity Ñ naïve evaluation) to show that naïve evaluation can work beyond unions of conjunctive queries under realistic semantic assumptions. THEOREM 5.7. Let Q be a Boolean FO query. Then:

-If Q is in hPos, then naïve evaluation works for Q under OWA.

-If Q is in Pos, then naïve evaluation works for Q under WCWA.

-If Q is in Pos dG, then naïve evaluation works for Q under CWA.

Contrast this with the result of [START_REF] Libkin | Incomplete information and certain answers in general data models[END_REF]] saying that under OWA, the first statement is 'if and only if ', i.e., one cannot go beyond hPos. Now we see that, under other semantics of incompleteness, one can indeed go well beyond that class, essentially limiting only unrestricted negation, and still use naïve evaluation.

One immediate question is what happens with non-Boolean queries. There is a simple answer: all results extend to non-Boolean queries. This is what we show next.

LIFTING TO NON-BOOLEAN QUERIES

As promised, we now show how to lift our results to the setting of arbitrary k-ary relational queries. We do it for relational database domains, and then apply results to specific relational semantics. The basic idea is to consider a new database domain where objects are pairs consisting of a database and a k-tuple of constants. This turns queries into Boolean, and we apply our results. This requires more technical development than seems to be implied by the simple idea, but it can be carried out for all the semantics. We explain now how the extension works.

A k-ary query Q maps a database D to a subset of adompDq k . It is generic if, for each one-to-one map f : adompDq Ñ Const Null, we have Qpf pDqq f pQpDqq.

Given a semantics rr ss, certain answers to Q are defined as certainpQ, Dq tQpD I q | D I rrDssu. Naïve evaluation works for Q if certainpQ, Dq is precisely the set

Q C pDq QpDq Const k
of tuples in QpDq that do not have nulls.

As before, Q is weakly monotone if Q C pDq Q C pD I q whenever D I rrDss.

We will need a stronger form of saturation property. A relational database domain is strongly saturated if every database has "sufficiently" many complete instances in its semantics that are isomorphic to it. More precisely, Definition 6.1. A relational database domain is strongly saturated if for each database D, and each finite set C Const, there is an isomorphic instance D I rrDss such that both the isomorphism from D to D I and its inverse are the identity on C.

We also need a "weak" notion of preservation: Definition 6.2. We say that a k-ary query is weakly preserved under a class of R sem -homomorphisms if for every database D, a k-tuple t of constants, and an R semhomomorphism h : D Ñ D I from the class that is the identity on t, the condition t QpDq implies t QpD I q.

Note that for Boolean queries this is the same as preservation under R semhomomorphisms.

Then the main connections continue to hold.

LEMMA 6.3. Let D be a relational database domain with the strong saturation property, and Q a k-ary generic query. Then the following are equivalent:

(1) naïve evaluation works for Q;

(2) Q is weakly monotone; and

(3) (if the semantics is given by a relation R sem ): Q is weakly preserved under R semhomomorphisms.

We postpone the proof of Lemma 6.3 until Section 11 where it will be proved together with its analog for minimal semantics.

In addition, for all the classes of FO formulae considered here, preservation results hold when extended to formulae with free variables. One can then conclude that all the results remain true for non-Boolean queries. THEOREM 6.4. Let Q be a k-ary FO query, k ¥ 0. Then:

A:20 -If Q is in hPos, then naïve evaluation works for Q under OWA.
-If Q is in Pos, then naïve evaluation works for Q under WCWA.

-If Q is in Pos dG, then naïve evaluation works for Q under CWA.

PROOF. One can easily verify that all relational semantics given by a relation R sem have the strong saturation property. Moreover every k-ary FO query is generic. Then using Lemma 6.3 we have: CLAIM 2. If Q is a k-ary FO query, naïve evaluation works for Q iff Q is weakly preserved under -homomorphisms, under OWA, -strong onto homomorphisms, under CWA, -onto homomorphisms, under WCWA. By Lemma 5.4 k-ary formulae of Pos dG are preserved under strong onto homomorphisms. Moreover it is known that k-ary formulae of hPos (respectively Pos) are preserved under homomorphisms (respectively onto homomorphisms) in the sense of Definition 5.3, see [START_REF] Chang | Model Theory[END_REF]. Now notice that, for all these notions of homomorphism, preservation of k-ary formulae implies weak preservation. Then the statement of Theorem 6.4 immediately follows.

SEMANTIC ORDERINGS

In this section we study semantic orderings arising from the usual relational semantics of incompleteness. Firstly we show what the semantic orderings ¨OWA , ¨CWA , and ¨WCWA are. It turns out they are characterized via database homomorphisms as follows (the first item was already shown in [START_REF] Libkin | Incomplete information and certain answers in general data models[END_REF]). Let rr ss be the semantics given by the pair pR rdb val , R sem q (this semantics is OWA, CWA, and WCWA, respectively), and let ¨r r ss be the ordering arising from rr ss.

Assume D and D I are two relational instances and D ¨r r ss D I . Let E rrD I ss be an instance having a bijection i : adompEq Ñ adompD I q which is the identity on ConstpDq and such that ipEq D I . We know E rrDss therefore pE, Dq R rdb val ¥ R sem , or in other words there exists a valuation h : adompDq Ñ Const such that phpDq, Eq R sem . Let h I i ¥ h. We prove that h I pDq and D I are in the same relationship as hpDq and E, i.e., -Under OWA: hpDq E, therefore h I pDq iphpDqq ipEq D I ; -Under CWA: hpDq E, therefore h I pDq iphpDqq ipEq D I ; -Under WCWA: hpDq E and adomphpDqq adompEq, therefore h I pDq iphpDqq ipEq D I and adomph I pDqq ipadomphpDqqq ipadompEqq adompD I q. Moreover h I is the identity on ConstpDq, because both h and i are, and h I pDq and D I are related according to R sem .

This implies that:

-Under OWA, h I is a database homomorphism D Ñ D I ; -Under CWA, h I is a database strong onto homomorphism D Ñ D I ; -Under WCWA, h I is a database onto homomorphism D Ñ D I . Conversely assume that there exists a database ¦-homomorphism D Ñ D I , where by ¦-homomorphism we mean -arbitrary homomorphism, if rr ss rr ss OWA ; -strong onto homomorphism, if rr ss rr ss CWA ; -onto homomorphism, if rr ss rr ss WCWA . Note that database ¦-homomorphisms compose, i.e. if there exists a database ¦homomorphism from D to D I and a database ¦-homomorphism from D I to D P , then there composition is a database ¦-homomorphism from D to D P . Note also that rrD I ss is precisely the set of complete relational instance E such that there exists a database ¦-homomorphism from D I to E.

Then, by transitivity, there exists a database ¦-homomorphism from D to each E rrD I ss. Hence E rrDss for all E rrD I ss. In other words, rrD I ss rrDss, and therefore D ¨r r ss D I .

Codd databases and update justification. Orderings capturing the degree of incompleteness were studied in the context of Codd databases about two decades ago [START_REF] Buneman | Using Powerdomains to Generalize Relational Databases[END_REF][START_REF] Libkin | A semantics-based approach to design of query languages for partial information[END_REF][START_REF] Ohori | Semantics of types for database objects[END_REF][START_REF] Rounds | Situation-theoretic aspects of databases[END_REF]]. Results about such orderings are often of two kinds: they connect orderings based on incompleteness with wellknown orderings from the field of programming semantics, and they describe those via elementary updates that increase the information content of an instance. We now review them briefly.

Recall that SQL uses a single value null for missing information. As comparisons of a null with other values in SQL do not evaluate to true (technically, they evaluate to unknown, as SQL uses three-valued logic), this is properly modeled by a special kind of naïve databases, called Codd databases, in which nulls do not repeat.

For tuples t pa 1 , . . . , a n q and t I pa I 1 , . . . , a I n q over Const Null in which no null occurs more than once, we write t t I if a i Const implies a I i a i . The meaning is that t I is at least as informative as t. There are two standard ways of lifting to sets: D H D I ô dt D ht I D I : t t I D P D I ô dt I D I ht D : t t I and D H D I Superscripts H and P stand for Hoare and Plotkin, who first studied these orderings in the context of the semantics of concurrent processes, cf. [START_REF] Gunter | Semantics of Programming Languages: Structures and Techniques[END_REF]]. These had been previously accepted as the correct orderings to represent the OWA and the CWA semantics over Codd databases [START_REF] Buneman | Using Powerdomains to Generalize Relational Databases[END_REF][START_REF] Libkin | A semantics-based approach to design of query languages for partial information[END_REF][START_REF] Ohori | Semantics of types for database objects[END_REF][START_REF] Rounds | Situation-theoretic aspects of databases[END_REF]]. This can be justified by considering updates that affect informativeness of incomplete databases. Consider, for example, two tuples p1, 2q and p2, 2q, and assume that we somehow lose the value of the first attribute. SQL has a unique null value, so both tuples become pnull, 2q, which thus must represent the instance tp1, 2q, p2, 2qu even under CWA, since no tuples were lost, only individual values. Alternatively, one can view this as an allowed update, under CWA, from pnull, 2q, that produces a more informative instance tp1, 2q, p2, 2qu by replacing the null twice. In the case of OWA, one can have updates that add arbitrary new tuples.

Let D be a database, R a relation in it, t a tuple, and i a position in that tuple that contains a null u. Update justification for naïve databases. Using Codd database results as a motivation, we now provide update justification for OWA and CWA orderings on naïve databases. OWA updates just add tuples as before; we denote them by OWA . CWA updates are different, to account for repetition of nulls. In particular, once a null is replaced by some value v, all its occurrences must be replaced. Formally, if u is a null that occurs in D, then Drv{us is D in which v Const Null replaces u everywhere.

The CWA update is now an update D CWA Drv{us.

THEOREM 7.2. The transitive-reflexive closure of CWA is ¨CWA ; and the transitive- reflexive closure of CWA OWA is ¨OWA .

In other words, D is less informative than D I iff D I is obtained from D by a sequence of CWA updates, under CWA, and both CWA and OWA updates, under OWA.

Theorem 7.2 will be shown inside the proof of Theorem 10.1 in Section 10 which shows a more general result subsuming Theorem 7.2.

What are the orderings ¨OWA and ¨CWA when we restrict them to Codd databases? One would expect them to be H and P , corresponding to OWA and CWA for the Codd semantics, but this is only partly true. In fact, [START_REF] Libkin | Incomplete information and certain answers in general data models[END_REF]] proved that over Codd databases, -¨OWA and H coincide; -D ¨CWA D I iff D P D I and relation , viewed as a bipartite graph between the tuples of D and the tuples of D I , has a perfect matching (in the standard graph-theoretic sense) from D I to D.

So this leads to a question: is there a "natural" semantic ordering over naïve databases that, when restricted to Codd databases, coincides precisely with P ? We shall give such an ordering, when we study more complex "powerset" semantics of incompleteness in Section 10.

MOVING BEYOND THE STANDARD SEMANTICS: GIVING UP SATURATION

In the previous sections we have developed our approach to naïve evaluation for standard semantics such as OWA and CWA. While these are the most common semantics of incompleteness, they are not the only ones, and in the second half of the paper, we show that there are many other possible semantics for which the approach works. Such semantics, in general, are obtained by using (separately, or together) two ideas.

(1) The first idea is giving up saturation, i.e., the condition that every object x must have an isomorphic object y in its semantics: y rrxss and y x. Since the standard semantics allow arbitrary valuations of nulls, we can view giving up saturation as restricting valuations of nulls which are allowed.

(2) The second idea is giving up uniqueness of valuation of nulls. Thus, multiple valuations can be applied to an incomplete object, and complete objects are obtained by combining outcomes of such multiple valuations.

In this section we start the first line of investigation, by showing that, even with restricted sets of valuations applied to nulls, there is a way to recover results, under some extra conditions. Here we present results in the abstract model, that is, the case of arbitrary database domains, and in the next section we study a concrete relational case, namely a minimal semantics of incompleteness.

The key idea for working with non-saturated domains is to impose two conditions:

-the existence of a saturated subdomain, which we shall call a representative set, and -the existence of a canonical function selecting a representative for each element of the domain.

Jumping ahead a little bit, we shall see that for some of the natural non-saturated semantics the canonical transformation will be the one that associates with an instance its core [Hell and Nesetȓil 1992]: a construction used in various subfields of database theory such as optimization of conjunctive queries [START_REF] Chandra | Optimal implementation of conjunctive queries in relational data bases[END_REF] and constructing small instances in data exchange [START_REF] Fagin | Data exchange: getting to the core[END_REF].

Recall that a database domain was defined as a structure D xD, C, rr ss, y, where D is a set and C one of its subsets, rr ss -C S (it contains all complete objects); -S is saturated, i.e., for each x S there is y rrxss such that x y (every object in S has a complete object in its semantics that is isomorphic to it); and -there is a function χ S : D Ñ S such that rrxss rrχ S pxqss for every x D (each object has a representation in S with the identical semantics).

Over relational database domains, if moreover S is strongly saturated, we say that S is a strong representative set.

In all the examples encountered so far we had S D, but as we just said (and will study in detail in the following section) this need not always be the case.

If S $ D, the equivalence between naïve evaluation and weak monotonicity need not work any more. However, we have the following generalization. For all x D I , we have rrxss rrχ S pxqss; moreover naïve evaluation works for Q on both x and χ S pxq (because D I S). Then we have Qpxq certainpQ, xq certainpQ, χ S pxqq Qpχ S pxqq.

Conversely assume that Q is weakly monotone over D I and Qpxq Qpχ S pxqq for all x D I . Let x D I . By weak monotonicity over D I (and because D I S C) we have Qpxq ¤ certainpQ, xq. To prove certainpQ, xq ¤ Qpxq, assume certainpQ, xq 1. Recall that rrxss rrχ S pxqss and χ S pxq S. Therefore there exists c rrxss such that c χ S pxq. We know Qpcq 1; then by genericity Qpχ S pxqq 1 Qpxq. Hence certainpQ, xq Qpxq for all x D I .

We have thus proved that naïve evaluation works for Q over D I if and only if Q is weakly monotone over D I and Qpxq Qpχ S pxqq for all x D I . Now if in particular S D we can always assume χ S to be the identity mapping D Ñ D. In this case then naïve evaluation works for Q if and only if Q is weakly monotone. This ends the proof of Theorem 8.2. l Thus, our recipe for finding out when naïve evaluation works continues to apply, but with one extra condition: the query (Boolean, in this case), should not distinguish between an object x and its representative χ S pxq in S.

Immediately from the above theorem, we have: COROLLARY 8.4. Let D be a database domain with a representative set S, and Q a generic Boolean query. Then naïve evaluation works for Q over S iff Q is weakly monotone over S.

Thus, for instances restricted to those in the representative set, our previous recipe applies without any changes.

MINIMAL VALUATIONS SEMANTICS

We now look at a concrete relational semantics of incompleteness that restricts the set of valuations. Essentially, the idea is to look at valuations that produce the smallest possible instances. Consider, for instance, an incomplete table D tpu, uq, pu, u I qu and a valuation vpuq 1, vpu I q 2. The result vpDq is not the smallest possible: take for instance v I puq v I pu I q 1 and we have v I pDq vpDq. The set v I pDq is minimal, i.e., not a proper subset of any other valuation.

This can be viewed as a very strong form of the closed-world assumption. Alternatively, it can be viewed as a building block of a more relaxed notion of closed world, in which different minimal valuations can be combined. Such semantics, in fact, was used in the data exchange scenario [START_REF] Hernich | Answering non-monotonic queries in relational data exchange[END_REF]], and it was based on earlier work in the area of logic programming [START_REF] Minker | On indefinite databases and the closed world assumption[END_REF]]. In data exchange, it appeared in the context of searching for the right balance between open and closed world assumptions, so as to avoid anomalies that the OWA may lead to, without restricting the setting too much.

We now give formal definitions. For now we deal with database homomorphisms, i.e., hpcq c for each c Const. We say that a homomorphism h defined on an instance D is D-minimal if no proper subinstance of hpDq is a homomorphic image of D; equivalently, there is no other homomorphism h I so that h I pDq hpDq. If h is a valuation, then we talk about a D-minimal valuation.

The semantics we deal with now is

rrDss min CWA thpDq | h is a D-minimal valuationu.
It can be viewed as the semantics given by a pair pR min val , R sem q, where R min val tpD, hpDqq | h is a D-minimal valuationu R rdb val . and R sem is the identity relation. Note that combining R min val with the subset relation (playing the role of R sem for OWA) gives us the usual OWA semantics.

We start studying the rr ss min CWA semantics by looking at the connection between minimal homomorphisms and the closely related notion of cores.

The fact that we no longer allow all valuations makes the equivalence of naïve evaluation and preservation of R sem -homomorphisms invalid. However, we can apply the results of the previous section to recover results on naïve evaluation. The main goal is then to find out what the representative sets are. This is what we do next.

Minimal homomorphisms and cores

Recall that a core of a structure D (in our case, a relational database of vocabulary σ) is a substructure D I D such that D I is a homomorphic image of D but no proper subinstance of D I is. In other words, there is a homomorphism h : D Ñ D I but there is no homomorphism g : D Ñ D P for D P D I . It is known that a core is unique up to isomorphism, so we can talk of the core of D, and denote it by corepDq. A structure is called a core if D corepDq. The cores are commonly used over graphs [Hell and Nešetřil 2004]; here we use them with the database notion of homomorphism that preserves constants (for which all results about cores remain true [START_REF] Fagin | Data exchange: getting to the core[END_REF]).

Even if minimal homomorphisms are related to cores, their images cannot be described precisely in terms of cores, as shown next. We strengthen results given in several examples in [START_REF] Hernich | Answering non-monotonic queries in relational data exchange[END_REF]] (where constants were used in an essential way): PROPOSITION 9.1. If h is D-minimal, then hpDq is a core and hpDq hpcorepDqq.

However, there is a core D and a homomorphism h defined on it so that hpDq is a core, but h is not D-minimal. This also holds if both D and hpDq contain only nulls, and if D is a graph.

PROOF. Let D be a relational instance and let h be a D-minimal database homomorphism. Assume by contradiction that hpDq is not a core. Then there exists a database homomorphism h I on hpDq such that h I phpDqq hpDq. Clearly h I ¥ h is a database homomorphism on D, then this contradicts the D-minimality of h. Now assume by contradiction that hpcorepDqq hpDq, and let h core be the database homomorphism from D onto corepDq. Clearly h ¥ h core is a database homomorphism on D and h core phpDqq hpcorepDqq hpDq. Again this contradicts the D-minimality of h.

We now prove that there exists a core D and a database homomorphism h : adompDq Ñ Null such that hpDq is a core, but h is not D-minimal.

Fix a schema with a single 4-ary relation, and consider instances

D u 1 u 1 u 2 u 3 u 4 u 5 u 2 u 2 hpDq u 6 u 6 u 7 u 7 u 6 u 7 u 7 u 7 where h : u 1 Ñ u 6 , u 2 Ñ u 7 , u 3 Ñ u 7 , u 4 Ñ u 6 , u 5 Ñ u 7
It is easy to check that both D and hpDq are cores. However h is not D-minimal. In fact there exists a mapping h I : u 1 Ñ u 6 , u 2 Ñ u 7 , u 3 Ñ u 7 , u 4 Ñ u 6 , u 5 Ñ u 6 such that h I pDq hpDq.

In fact one can produce a pure graph example (below, we shall assume that the nodes in graphs are distinct nulls, so we use the standard graph homomorphisms).

Let C n be the directed cycle on n vertices. Let G C 4 C 6 , where stands for disjoint union. Note that each C n is a core. Moreover, G is a core, since there is no homomorphism from C 6 to C 4 . Let H C 3 C 2 . Likewise, it is a core, and there is a

A:26 strong onto homomorphism h : G Ñ H that sends C 4 to C 2 and C 6 to C 3 (as in general we have C 2n Ñ C n ). Hence, H, G are cores, but h is not G-minimal since G Ñ C 2 , as G is 2-colorable.
This also provides an example of D such that rrDss min CWA $ rrcorepDqss CWA . Indeed, take D to be C 6 C 4 consisting of all nulls; note that corepDq D. Let C C n be the cycle C n whose nodes are distinct constants. Then C C 3 C C 2 is in rrDss CWA . However, it is not in rrDss min CWA .

Indeed, if it were, there would be an onto homomorphism h :

C 6 C 4 Ñ C C 3 C C 2 .
Since we have no homomorphism C 4 Ñ C 3 , then C 4 ought to be mapped by h to C C 2 , and hence C 6 will be mapped by h to C C 3 as h is onto. But we already saw that such a homomorphism cannot be minimal, since we have a homomorphism g :

C 6 C 4 Ñ C C 2 . Thus, C C 3 C C 2 rrDss min CWA .
Proposition 9.1 also shows that rrDss min CWA need not be the same as rrcorepDqss CWA . Nevertheless, cores do play a crucial role in the study of minimal semantics.

THEOREM 9.2. For the semantics rr ss min CWA , the set of cores is a representative set. In fact, this is true for every semantics given by R pR min val , R sem q.

PROOF. In order to easily work with minimal homomorphisms we extend the Dminimality notion to arbitrary mappings, and prove some technical facts about Dminimal mappings.

For an arbitrary mapping h : adompDq Ñ Const Null we define, fixph, Dq tc ConstpDq | hpcq cu.

Given a relational instance D and a mapping h : adompDq Ñ Const Null we say that h is D-minimal if there is no mapping g : adompDq Ñ Const Null with fixph, Dq fixpg, Dq and gpDq hpDq.

Notice that a D-minimal database homomorphism (D-minimal valuation, resp.) is a database homomorphism (valuation, resp.) which is also a D-minimal mapping.

We now prove a technical lemma about minimal mappings.

I ¥ h ¥ µ is E-minimal. PROOF. Let h I µ I ¥ h ¥ µ.
First notice that h I is a mapping over adompEq such that h I pEq E I , and h I is the identity on fixph, Dq. Now assume by contradiction that there exists a mapping g : adompEq Ñ ConstNull such that fixph I , Eq fixpg, Eq and gpEq h I pEq. Then gpEq E I and g is the identity on fixph, Dq. Let g I µ I¡ ¥ g ¥ µ ¡ ; clearly g I is a mapping over adompDq and is the identity on fixph, Dq; therefore fixph, Dq fixpg I , Dq. We now show that g I pDq hpDq. In fact g I pDq µ I¡ pgpEqq. Recall that gpEq E I , therefore µ I¡ pgpEqq µ I¡ pE I q D I hpDq This contradicts the assumption that h is D-minimal.

We are now ready to prove the theorem. More precisely we prove the following proposition : PROPOSITION 9.4. If a relational semantics is given by a pair pR min val , R sem q, the set S of cores is a strong representative set, and χ S pDq corepDq for every instance D.

PROOF. Let rr ss be given by pR min val , R sem q. Clearly the set of cores contains all complete instances (recall that cores are defined w.r.t. database homomorphisms here).

We now prove that if D is a core and K Const, there exists a D-minimal valuation v such that D and vpDq are isomorphic in the way required by the definition of strong representative set. We observe that this property indeed follows from [START_REF] Hernich | Answering non-monotonic queries in relational data exchange[END_REF]] (Proposition 6.11 (1) and ( 2)), but we prove it here directly for completeness.

If D is a core and K Const, let v be an arbitrary injective valuation adompDq Ñ ConstzK. Clearly v is an isomorphism between D and vpDq and both v and v ¡ are the identity on ConstpDq K, and therefore the identity on K, as required by the definition of strong representative set. We need to prove that vpDq rrDss. Now notice that the identity mapping over adompDq is D-minimal, because D is a core. Moreover v and v ¡ are the identity on ConstpDq, which is precisely the set of constants fixed by the identity mapping on D. Then we can apply Lemma 9.3 with D D I E and conclude that v is D-minimal.

Thus pD, vpDqq R min val and, since R sem contains the identity, vpDq rrDss. It remains to prove that rrDss rrcorepDqss. This will show that one can define χ S pDq corepDq for every instance D.

Let D be a relational instance. We prove that D and corepDq have the same minimal images, i.e. pD, D I q R min val iff pcorepDq, D I q R min val , for all D I . This will imply rrDss rrcorepDqss. We observe that this property has been proved in [START_REF] Hernich | Answering non-monotonic queries in relational data exchange[END_REF]] (Lemma 6.9) restricted to the canonical solution in data exchange and its core.

Assume first that pD, D I q R min val , then there exists a D-minimal valuation h such that D I hpDq. We know by Proposition 9.1 that hpcorepDqq hpDq D I . Moreover h has to be a corepDq-minimal valuation. In fact assume by contradiction that there exists a valuation h I on corepDq such that h I pcorepDqq hpcorepDqq D I . Let h core be the database homomorphism from D to corepDq. Then h I ¥ h core is a valuation on D and h I ¥ h core pDq h I pcorepDqq D I . This contradicts the assumption that h is D-minimal. Then h is a corepDq-minimal valuation and thus pcorepDq, D I q R min val .

Conversely assume that pcorepDq, D I q R min val , then there exists a corepDq-minimal valuation h such that hpcorepDqq D I . Therefore h ¥ h core is a valuation and hph core pDqq hpcorepDqq D I . We prove that h ¥ h core is D-minimal. Assume by contradiction that there exists a valuation h I on D such that h I pDq D I . Then, since corepDq D I we have h I pcorepDqq h I pDq D I , contradicting the fact that h is corepDqminimal.

We have thus shown that the set S of cores is a representative set and χ S pDq corepDq for all relational instances D.

This ends the proof of Proposition 9.4 and of Theorem 9.2.

Recall that a generic Boolean query Q is weakly monotone under rr ss min CWA if QpDq 1 and D I rrDss min CWA imply QpD I q 1. Immediately from Theorem 9.2 and Theorem 8.2, we obtain: COROLLARY 9.5. Let Q be a generic Boolean relational query. Then naïve evaluation works for Q under the rr ss min CWA semantics iff Q is weakly monotone and QpDq QpcorepDqq for every D.

Hence, the crucial new condition for minimal semantics is that Q cannot distinguish a database from its core.

Preservation and naïve evaluation

We now relate weak monotonicity to homomorphism preservation for the minimal valuations semantics. For this, we consider minimality for instances D over Const. For such an instance, and a homomorphism h, we let fixph, Dq tc ConstpDq | hpcq cu.

In the same way as for arbitrary mappings, h is called D-minimal if there is no homomorphism g with fixph, Dq fixpg, Dq and gpDq hpDq. Note that database homomorphisms fix precisely the set of constants in D, so the first condition was not necessary.

Given a Boolean query Q, we say that it is preserved under minimal homomorphisms if, whenever D is a database over Const and h is a D-minimal homomorphism, then QpDq 1 implies QphpDqq 1. PROPOSITION 9.6. Let Q be a Boolean generic query. Then it is weakly monotone under rr ss min CWA iff it is preserved under minimal homomorphisms. PROOF. We derive the relationship between weak monotonicity and preservation for general semantics based on R min val . The proposition will follow as a special case.

Recall the notion of mapping type and -equivalence used to prove Proposition 4.6. We now consider the mapping type M min which associates to each complete relational instance D the set of all D-minimal mappings adompDq Ñ Const.

We prove the following lemma: LEMMA 9.7. If M min and is the isomorphism relation between relational instances, then R M is -equivalent to R min val .

PROOF. Let pD, vpDqq R min val , where v is a D-minimal valuation; we prove that there exists a complete relational instance E D such that pE, vpDqq R M .

The instance E is obtained from D by replacing nulls of D with new distinct constants not occurring in ConstpDq. Clearly there exists an isomorphism i : E Ñ D, thus E D. Note that both i and i ¡ are the identity on ConstpDq. Let h v ¥ i, then hpEq vpDq. Note that i and i ¡ are the identity on fixpv, Dq ConstpDq. Hence by Lemma 9.3 h is an E-minimal mapping. As a consequence pE, vpDqq R M (because M min). This proves one direction.

Conversely assume pE, hpEqq R M , where h is an E-minimal mapping; we prove that there exists a relational instance D E such that pD, hpEqq R min val . The instance D is obtained from E by replacing each element of adompEqzfixph, Eq with a new distinct null. Clearly this replacement defines an isomorphism i : D Ñ E and therefore E D. Note that both i and i ¡ are the identity on fixph, Eq. Then the mapping v h¥i is also the identity on fixph, Eq; moreover vpDq hpEq. But ConstpDq fixph, Eq, then v is a valuation on D. Moreover by Lemma 9.3, v is D-minimal, and hence pD, hpEqq R min val .

M-R sem -homomorphisms with M min will be also referred to as minimal R semhomomorphisms. Notice that minimal homomorphisms are precisely minimal R semhomomorphisms where R sem is the identity.

Using Corollary 4.11 with M min we then have: COROLLARY 9.8. If a relational semantics is given by a pair pR min val , R sem q and Q is a generic Boolean relational query, then Q is weakly monotone iff it is preserved under minimal R sem -homomorphisms. Moreover naïve evaluation works for Q iff Q is preserved under minimal R semhomomorphisms and QpDq QpcorepDqq for every D.

Proposition 9.6 is a special case of Corollary 9.8 where R sem is the identity.

Combining this with Corollary 9.5 and results in Section 5, and observing that minimal homomorphisms are a special case of strong onto homomorphisms, we obtain: COROLLARY 9.9. Let Q be a Boolean Pos dG query such that QpDq QpcorepDqq for all D. Then naïve evaluation works for Q under the rr ss min CWA semantics.

The precondition QpDq QpcorepDqq is essential for the result to work. To see this, consider an incomplete instance D tpu, uq, pu, u I qu. Every D-minimal valuation h must satisfy hpuq hpu I q, i.e., their images are precisely the instances tpc, cqu for c Const. Hence, under rr ss min CWA , the certain answer to dx Dpx, xq is true, while evaluating this formula on D produces false. The reason naïve evaluation does not return certain answers is that QpDq $ QpcorepDqq, since corepDq tpu, uqu.

Thus, the extra condition is essential, but it is not fully satisfactory, as we do not know how to check for this condition in relevant FO fragments. We present two ways to deal with this issue.

First, by Corollary 8.4, if we only need to compute queries on cores, then the condition is not necessary. More precisely, recall that we say that naïve evaluation works for Q over a class K of instances, under a given semantics of incompleteness, if for each D K, certain answer to Q over D is the same as QpDq. Then COROLLARY 9.10. Let Q be a Boolean Pos dG query. Then naïve evaluation works for Q over cores under the rr ss min CWA semantics.

A second corollary states that for the above classes of queries, even without the extra condition we can conclude that if naïve evaluation returns true, then so will the certain answer. In other words, we can run Q naïvely on D, not on corepDq. If the result is true, then the certain answer is true; but if the result is false, we cannot conclude anything. That is, naïve evaluation provides an approximation of certain answers. PROPOSITION 9.11. Let Q be a Boolean Pos dG query. If QpDq 1, then the certain answer to Q over D under the rr ss min CWA semantics is true. PROOF. From Proposition 5.2 and the fact that minimal homomorphisms are a special case of strong onto homomorphisms, we have that queries in Pos dG are weakly monotone under the rr ss min CWA semantics. By definition of weak monotonicity , if QpDq 1 then QpD I q 1 for all D I in the semantics of D. Therefore the certain answer to Q over D is true.

POWERSET SEMANTICS

So far all our relational semantics of incompleteness were based on applying a single valuation to an incomplete database. This need not always be the case however. For example, minimal valuations and homomorphisms, studied in the previous section, were used in the context of the following semantics in data exchange applications [START_REF] Hernich | Answering non-monotonic queries in relational data exchange[END_REF]]:

|D| ¨min

CWA th 1 pDq . . . h n pDq | h 1 , . . . , h n are D-minimal valuations, n ¥ 1u.u.

That is, not one, but multiple valuations can be applied to a database, and then the results are combined, in this case by the union operation.

Semantics obtained from several valuations will be referred to as powerset semantics, since they start with producing a set of instances, and then combine them into a single one. Notationally, we distinguish them by using | | ¨brackets.

If we do not restrict valuations to be minimal, we obtain the following powerset semantics:

|D| ¨CWA th 1 pDq . . . h n pDq | h 1 , . . . , h n are valuations, n ¥ 1u.
That is, D I |D| ¨CWA iff there exists a set of valuations h 1 , . . . , h n on D so that D I th i pDq | 1 ¤ i ¤ nu.

Note that in both cases we use the CWA subscript, as no tuples can be added to the result of the union (under such an addition, we would have gotten the usual OWA semantics).

Our study of powerset semantics proceeds as follows.

(1) We start by looking at the semantic ordering associated with | | ¨CWA and show that it comes from very natural updates; besides, it happens to coincide with the Plotkin ordering P when restricted to Codd databases, thus filling the gap from Section 7.

(2) We then study naïve evaluation under | | ¨CWA and show that, with appropriate adjustment, the approach of the earlier sections applies, and produces a class of queries that extends hPos for which naïve evaluation works.

(3) After that we provide a similar study for the minimal semantics | | ¨min CWA , using results from the previous section to show that all the results extend to cores, rather than arbitrary databases.

Powerset semantics and orderings

We now describe the ordering CWA induced by the | | ¨CWA semantics: that is,

D CWA D I ô |D I | ¨CWA |D| ¨CWA .
We describe it, as in Section 7, using the idea of updates that increase informativeness of objects. We now take updates from Section 7, and add a new type of an update to them. A copying CWA update is of the form

D CWA Drv{us D fresh ,
where D fresh is a copy of D in which all nulls are replaced by fresh ones. This is a relaxation of CWA: we can add tuples in an update, but only in a very limited way, if they mimic the original database. For instance, if D contains one tuple p1, uq, the result of such an update could be tp1, 2q, p1, u I qu, which evaluates u to 2, and adds a copy p1, u I q of p1, uq with the null replaced.

It turns out that the ordering CWA can be seen as a sequence of regular and copying CWA updates, and that when restricted to Codd databases, it coincides precisely with P , which was traditionally used as the CWA ordering on Codd databases. That is, we have the following.

THEOREM 10.1.

-D CWA D I iff there exists a set of database homomorphisms h 1 , . . . , h n defined on D so that D I th i pDq | 1 ¤ i ¤ nu. -The transitive-reflexive closure of CWA CWA is CWA .

-Over Codd databases, CWA and P coincide.

PROOF. We first show the first item of the Theorem. Let D and D I be two relational instances such that D CWA D I , i.e., |D I | ¨CWA |D| ¨CWA . Let E |D I | ¨CWA be an instance having a bijection b : adompEq Ñ adompD I q which is the identity on ConstpDq and such that bpEq D I . By E |D| ¨I CWA , also E |D| ¨CWA and so there exists a set of valuations h 1 , . . . , h n with n ¥ 1 such that We will show the second item of the Theorem last and so we show now its last item.

E th i pDq | 1 ¤ i ¤ nu. It follows that D I tb ¥ h i pDq | 1 ¤ i ¤ nu
Let D and D I be two Codd databases. Assume D CWA D I , i.e., there exists a set of A:31 homomorphisms h 1 , . . . , h n from D so that D I th i pDq | 1 ¤ i ¤ nu. So for every tuple pa 1 , . . . , a m q D, there is some 1 ¤ i ¤ n such that ph i pa 1 q, . . . , h i pa m qq D I , i.e., pa 1 , . . . , a m q ph i pa 1 q, . . . , h i pa m qq. It follows that D H D I . Similarly for every tuple pb 1 , . . . , b m q D I , there exists i such that pb 1 , . . . , b m q h i pDq, which entails that there is pa 1 , . . . , a m q D such that for every 1 ¤ j ¤ m, h i pa j q b j and so pa 1 , . . . , a m q pb 1 , . . . , b m q. It follows that D P D I .

Conversely, assume D P D I . For every tuple t D, consider the set tt I D I | t t I u and observe that it is both finite and non empty. Now for every tuple t D, let H t t I 1 , . . . , t I k be a finite arbitrarily ordered sequence of tuples such that for every 1 ¤ i ¤ k:

t I i H t iff t I i tt I D I | t t I u.
Note that nothing prevents tuples to be repeated in the H t 's. So without loss of generality we can assume that there is some m big enough so that for every t D,

H
¤ i ¤ k: D i ¤ xSi D i¡1 rx{u i s.
Without loss of generality we can assume that there is some m big enough so that for every 1 ¤ i ¤ k there exist some x i 1 , . . . , x i m such that S i x i 1 , . . . , x i m . Indeed, take m to be the length of the longest S i sequence. If there is some S j x j 1 , . . . , x j n with n m, then we can simply add to S j a sequence of identical elements x j n 1 , . . . , x j m A:32 all equal to x j n without altering the construction, i.e., we will obtain exactly the same database D j by replacing multiple times the null u j by the same element x j n . The reason for that is simply that D j¡1 rx j n {u j s D j¡1 rx j n {u j s D j¡1 rx j n {u j s.

Out of this sequence of CWA -updates of length k, we will now construct for every 0 ¤ i ¤ k and for every 1 ¤ j ¤ m i a family of homomorphisms h i j 's from D to D i so that D i 1¤j¤m i h i j pDq, which will entail in particular that D I 1¤j¤m k h k j pDq, i.e., D CWA D I and will achieve the proof of ¦ CWA CWA .

We construct the h i j 's by induction on k, first ordering them in a sibling-ordered tree of depth k and rank m to ease the construction. We start by defining h 0 1 and use it to label the root of the tree. We then label the rest of the nodes so that each homomorphism h i j lies at depth i and labels the j th node according to the left to right ordering in the tree. This will conveniently allow us to define each h i j in function of some previously defined homomorphism lying at depth i ¡ 1. Now for each h i j with i $ 0, observe that there is a unique r and a unique s such that h i j is the r th child of h i¡1 s . We can now proceed to defining the h i j 's. We let h 0 1 be the identity and for all i $ 0 we let h i j be exactly as its parent h i¡1 s , except that it assigns the value x i r to all the preimages of u i by h i¡1 s . We now show the correctness of the construction. Assume as inductive hypothesis that for all i k, the following property holds:

-for every 1 ¤ j ¤ m i , h i j : D Ñ D i is a homomorphism and moreover D i 1¤j¤m i h i j pDq. (Notice in particular that the property holds trivially for i 0.) We now derive that it also holds for i k. For each 1 ¤ j ¤ m k , the fact that h CWA ¨CWA . Showing ¦ CWA ¨CWA amounts to restricting in the first direction of the proof to the special case where n 1 for every D i 1¤j¤n D i¡1 rh j pu i q{u i s, while showing ¦ CWA ¨CWA amounts to restricting in the second direction to the special case where the length of the longest S i sequence is m 1. The fact that p OWA CWA q ¦ ¨OWA now follows from ¦ CWA ¨CWA . Consider indeed D ¨OWA D I . So there is a homomorphism h such that hpDq is a subinstance of D I and D ¦ CWA hpDq. But then there is also a sequence of OWA updates hpDq OWA . . . OWA D I and so Dp OWA CWA q ¦ D I . Conversely let Dp OWA CWA q ¦ D I . So there is a homomorphism h from D and a sequence of p OWA CWA q ¦ updates D CWA . . . CWA hpDq OWA . . . OWA D I where all the OWA updates are performed last. Adding new tuples to hpDq does not alter the tuples in it and so hpDq is a subinstance of D I , i.e., D ¨OWA D I . Finally it can be shown using a similar reasoning that p OWA CWA q ¦ p OWA CWA q ¦ , which achieves the proof of the Theorem.

Naïve evaluation for the powerset semantics

We now explain how to achieve naïve evaluation under powerset semantics. The ideas are the same as before: we relate naïve evaluation to monotonicity and preservation.

-conjunction, disjunction, existential quantification, and -the following rule: if x is a tuple of distinct variables, ϕpȳq is a formula in hPos dG bool , where all ȳ variables are contained in x, and R is a relation symbol (possibly the equality relation), then dx pRpxq Ñ ϕpȳqq is in hPos dG bool . Note that the formula dx pRpxq Ñ ϕpȳqq in the last rule is a sentence, i.e., it has no free variables.

PROPOSITION 10.10. Sentences in hPos dG bool are preserved under unions of strong onto homomorphisms.

In order to prove the proposition we first define the notion of preservation under unions of strong onto homomorphisms for non-Boolean queries. This will allow us to prove the preservation property by structural induction on formulas in hPos dG bool . Definition 10.11. If Q is a k-ary query over complete relational instances (i.e. Q associates to each complete relational instance D a k-ary relation over adompDqq, we say that Q is preserved under unions of strong onto homomorphisms if, whenever there exists a union of strong onto homomorphisms th 1 . . . h n u from an instance D to an instance D I , and ā QpDq, then h i pāq QpD I q, for all i 1, . . . , k.

Proposition 10.10 immediately derives from the following lemma: LEMMA 10.12. Formulas in hPos dG bool are preserved under unions of strong onto homomorphisms.

PROOF. We proceed by structural induction on the formula ϕ. If ϕ false or ϕ true, it is clearly preserved under unions of strong onto homomorphisms.

Assume now that ϕpxq is a positive atom Rpȳq (including the case of an equality atom), where variables occurring in ȳ are precisely x. It follows from the definition of homomorphism that if an instance D | ù ϕpāq then hpDq | ù ϕphpāqq, for every homomorphism h. Then if D I h 1 pDq ¤ ¤ ¤ h k pDq one has that D I | ù ϕph i pāqq for all i 1, . . . , k.

It is also easy to verify that if ϕ 1 and ϕ 2 are preserved under unions of strong onto homomorphisms, so are ϕ 1 ϕ 2 and ϕ 1 ϕ 2 . Now assume ϕpxq hyϕ I py, xq, where ϕ I is preserved under unions of strong onto homomorphisms. Assume that an instance D | ù ϕpāq, and that D I h 1 pDq¤ ¤ ¤h k pDq. This concludes the proof of Lemma 10.12.

Combining with Proposition 10.5, we get the following result. COROLLARY 10.13. If Q is a Boolean query from the class hPos dG bool , then naïve evaluation works for Q under the | | ¨CWA semantics.

A:37

Naïve evaluation for the minimal powerset semantics

Recall that the semantics we are considering (that was previously used in data exchange applications [START_REF] Hernich | Answering non-monotonic queries in relational data exchange[END_REF]

]) is |D| ¨min CWA t hH hpDq | H is a nonempty set of D-minimal valuationsu.
This is a powerset-based semantics, and the semantic relation it uses is the union relation R , the same as in subsection 10.2. However the valuation relation is no longer R rdb val , allowing all valuations, but rather R min val containing all pairs pD, thpDq | h Huq with H ranging over nonempty sets of D-minimal valuations.

Similarly to Theorem 9.2, we can show the following. THEOREM 10.14. For the semantics | | ¨min CWA , the set of cores is a representative set.

In fact, this is true for every semantics given by pairs R pR min val , R sem q.

PROOF. As in the proof of Theorem 9.2, we establish a slightly stronger result.

Namely, we show that for a relational semantics is given by a pair pR min val , R sem q, the set S of cores is a strong representative set, and χ S pDq corepDq for every instance D.

Recall that we write R PpRq if R consists of precisely the pairs px, X q such that X $ r and px, yq R for all y X . Note that R min val PpR min val q. We then have: CLAIM 4. If a powerset semantics rr ss R is given by a pair pR val , R sem q where R val PpR val q. The following holds: -For all x, x I D, if x and x I are related by R val to the same set of instances (i.e px, cq

R val iff px I , cq R val for all c C) then rrxss R rrx I ss R . -R val ¥ R sem R val PROOF.
The first item immediately follows from the fact that R val PpR val q.

As for the second item, assume px, cq R val then px, tcuq R val . Since R sem contains id r , we have that ptcu, cq R sem . Hence px, cq R val ¥ R sem .

The following lemma easily follows: LEMMA 10.15. Let id be the identity relation over complete relational instances. Assume that S is a strong representative set under a relational semantics given by a pair pR val , idq. Then S is a strong representative set also under any powerset semantics given by pPpR val q, R sem q.

PROOF. Since S is a strong representative set under a semantics, S C. Moreover there exists a function χ S : D Ñ S, such that D and χ S pDq are related by R val to precisely the same instances. Then by Claim 4, D and χ S pDq have the same semantics under pPpR val q, R sem q.

We further know that for all D S and for all K Const there exists D I with pD, D I q R val and a bijection i : adompDq Ñ adompD I q with ipDq D I such that i and i ¡ are the identity on K. Again by Claim 4, pD, D I q PpR val q ¥ R sem . This proves that S is a strong representative set under the semantics pPpR val q, R sem q.

This lemma, together with Theorem 9.2, implies that the set of cores is a strong representative set also under any powerset semantics given by pR min val , R sem q, proving Theorem 10.14. Preservation and naïve evaluation. We now relate weak monotonicity to homomorphism preservation. Recall that for an instance D over Const and a homomorphism h, we write fixph, Dq for tc ConstpDq | hpcq cu, and say that h is D-minimal if there is no homomorphism g with fixph, Dq fixpg, Dq and gpDq hpDq.

Given a Boolean query Q, we say that it is preserved under unions of minimal homomorphisms, if for any nonempty set H of D-minimal homomorphisms such that fixph, Dq fixpg, Dq whenever f, g H, we have that QpDq 1 implies Qp thpDq | h Huq 1.

We then have an analog of Proposition 9.6. PROPOSITION 10.17. Let Q be a Boolean generic query. Then it is weakly monotone under | | ¨min CWA iff it is preserved under unions of minimal homomorphisms.

PROOF. Recall the notion of mapping type and -equivalence from the proof of Proposition 10.5. We say that a set H th 1 , . . . h k u of mappings over adompDq is Dminimal if each h i is D-minimal and fixph i , Dq fixph j , Dq for all i, j t1, . . . , ku. We now consider the powerset mapping type M min which associates to each D the class consisting of all non-empty finite D-minimal sets of mappings adompDq Ñ Const.

LEMMA 10.18. If M min and is relational isomorphism, then R M isequivalent to R min val PROOF. Let pD, X q R min val ; we prove that there exists a complete relational instance E D such that pE, X q R M . Let ConstpX q be the union of ConstpD I q, for all D I X .

The instance E is obtained from D by replacing nulls of D with new distinct constants not occurring in ConstpDq ConstpX q. Clearly there exists an isomorphism i : E Ñ D, thus E D. Note that both i and i ¡ are the identity on ConstpDq ConstpX q.

For each D I X there exists a D-minimal valuation v such that vpDq D I . Let h v ¥ i, then hpEq D I and, by Lemma 9.3 h is E-minimal. Note also that fixph, Eq ConstpDq. Since such an h exists for all D I X , we have pE, X q R M . This proves one direction.

Conversely assume pE, X q R M , then X th 1 pEq, . . . h k pEqu where where th 1 , . . . h k u is E-minimal; we prove that there exists a relational instance D E such that pD, X q R min val . Let K fixph i , Eq (which is the same for all i t1, . . . , ku).

The instance D is obtained from E by replacing each element of adompEqzK with a new distinct null. Clearly this replacement defines an isomorphism i : D Ñ E and therefore E D. Note that both i and i ¡ are the identity on K. Then the mappings v j h j ¥ i, for j t1, . . . , ku are all D-minimal, by Lemma 9.3. Moreover notice that ConstpDq K, then v j is a D-minimal valuation on D, and v j pDq h j pEq, for all j t1, . . . , ku. It follows that pD, X q R min val .

M-R sem -homomorphisms with M min will be also referred to as minimal R semhomomorphisms. Notice that unions of minimal homomorphisms are precisely mini- -If Q is in Pos dG, then naïve evaluation works for Q under the rr ss min CWA semantics.

-If Q is in hPos dG bool , then naïve evaluation works for Q under the | | ¨min CWA semantics. PROOF. The statement follows directly from Lemma 11.2, by recalling that R sem is the identity for rr ss min CWA and therefore minimal R sem -homomorphisms are just usual minimal homomorphisms. Similarly R sem is R for | | ¨min CWA , and minimal R semhomomorphisms are unions of minimal homomorphisms. By Lemma 5.4 and Lemma 10.12 the above fragments guarantee these preservation properties, and therefore the corresponding weak preservation properties.

SUMMARY AND FUTURE WORK

The table in Figure 1 summarizes results on naïve evaluation for fragments of FO queries. The first line of course is the classical result of [START_REF] Imielinski | Incomplete information in relational databases[END_REF], proved to be optimal in [START_REF] Libkin | Incomplete information and certain answers in general data models[END_REF]]. Other results were shown using the methodology established here, that reduced naïve evaluation to monotonicity and preservation under homomorphisms.

There are several directions in which we would like to extend this work.

Other data models. So far we looked at either a very general setting, which can subsume practically every data model, or at relational databases. We would like to get concrete results for other data models. For two of them we actually know quite a bit about the semantics of incompleteness and the complexity of queries: these are nested relations [START_REF] Levene | Semantics for null extended nested relations[END_REF] and XML [START_REF] Abiteboul | Representing and querying XML with incomplete information[END_REF]Barceló et al. 2010;[START_REF] Gheerbrant | On the complexity of query answering over incomplete xml documents[END_REF]; these papers can serve as a good starting point. For others, e.g., graph databases and RDF, we know much less, but some initial work in understanding incompleteness has been done [Barceló et al. 2014;[START_REF] Nikolaou | Incomplete information in RDF[END_REF].

Other languages. When we dealt with relations, we studied FO as the main query language. However, our structural results are in no way limited to FO. In fact it is known that naïve evaluation works for datalog (without negation). Given the toolkit of this paper, we would like to consider queries in languages that go beyond FO and admit naïve evaluation.

Preservation results.

There are open questions related to preservation results in both finite and infinite model theory. We already mentioned that the results of [Keisler 1965b] about preservation under strong onto homomorphisms are limited to a simple vocabulary, and even then appear to be problematic. We would like to establish a precise characterization in the infinite case, and see whether it holds or fails in the finite. We also want to look at preservation on restricted classes of structures, following [START_REF] Atserias | On preservation under homomorphisms and unions of conjunctive queries[END_REF]] which looked at bounded treewidth (but does not capture XML with data). We note in passing that [START_REF] Atserias | On preservation under homomorphisms and unions of conjunctive queries[END_REF] does not apply directly to the study of XML since models of documents with data generate relational structures of arbitrary treewidth.

The impact of constraints. Constraints (e.g., keys and foreign keys) have a huge impact on the complexity of finding certain answers [START_REF] Calì | On the decidability and complexity of query answering over inconsistent and incomplete databases[END_REF][START_REF] Vardi | On the integrity of databases with incomplete information[END_REF]], so it is thus natural to ask how they affect good classes we described in this paper. Constraints appear in another model of incompleteness -conditional tables [START_REF] Imielinski | Incomplete information in relational databases[END_REF] -that in general have higher complexity of query evaluation [START_REF] Abiteboul | On the representation and querying of sets of possible worlds[END_REF] but are nonetheless useful in several applications [START_REF] Arenas | Data exchange beyond complete data[END_REF].

Applications. In applications such as data integration and exchange, finding certain answers is the standard query answering semantics [START_REF] Arenas | Relational and XML Data Exchange[END_REF][START_REF] Lenzerini | Data integration: a theoretical perspective[END_REF]]. In fact one of our semantics of incompleteness came from data exchange literature [START_REF] Hernich | Answering non-monotonic queries in relational data exchange[END_REF]]. We would like to see whether our techniques help find classes of queries for which query answering becomes easy in exchange and integration scenarios.

Bringing back the infinite. We have used a number of results from infinite model theory to get our syntactic classes. Another way of appealing to logic over infinite structures to handle incompleteness was advocated by Reiter [START_REF] Reiter | On closed world data bases[END_REF]1982] three decades ago. In that approach, an incomplete database D is viewed as a logical theory T D , and finding certain answers to Q amounts to checking whether T D entails Q. This is in general an undecidable problem, and entailment in the finite is known to be more problematic than unrestricted one. This is reminiscent of the situation with homomorphism preservation results, but we saw that we can use infinite results to obtain useful sufficient conditions. Motivated by this, we would like to revisit Reiter's proof-theoretic approach and connect it with our semantic approach.

New approaches to certainty. Recently the traditional approach to defining certainty by means of intersecting query answers has been criticized and shown to lead to some inconsistencies [Libkin 2014a;2014b]. Alternatives proposed [Libkin 2014a;2014b] expand applicability of naïve evaluation to different classes of queries as long as some semantic conditions are met. It is still open how to handle these conditions for full relational algebra/calculus though. have rrpD, tqss ¦ tpE, tq | E rrDssu, and since D is fair rrDss rrD I ss. Thus rrpD, tqss ¦ tpE, tq | E rrD I ssu rrpD I , tqss ¦ . By Proposition 3.6, D ¦ is fair.

2). We know Q is C-generic. Consider two objects pD, tq, pD I , t I q D ¦ such that pD, tq ¦ pD I , t I q. We prove Q ¦ pD, tq Q ¦ pD I , t I q, i.e. t I QpD I q iff t QpDq.

We know there exists an bijection i : adompDq t Ñ adompD I q t I such that ipDq D I , iptq t I , and both i and i ¡ are the identity on C. Note that i can be extended to a bijection f : adompDq t C Ñ adompD I q t I C which is the identity on C and such that f pDq D I and f ptq t I .

Since f is injective on adompDq C, it is the identity on C, and Q is C-generic, QpD I q f pQpDqq. Thus t I QpD I q iff t I f pQpDqq. Since f is injective over adompDq t and f ptq t I , we have that t I f pQpDqq iff t QpDq. Then t I QpD I q iff t QpDq.

3). Consider D D ¦ and a k-tuple t over Const. We have certainpQ ¦ , D, tq 1 iff Q ¦ pD I , tq 1 for all pD I , tq rrpD, tqss ¦ . This is equivalent to saying that t QpD I q for all D I rrDss, i.e that t certainpQ, Dq.

4). We recall that naïve evaluation works for Q ¦ iff certainpQ ¦ , D, tq Q ¦ pD, tq for every D D and every k-tuple t over Const. By using the previous item, certainpQ ¦ , D, tq Q ¦ pD, tq is equivalent to say that t certainpQ, Dq iff t QpDq. In other words naïve evaluation works for Q ¦ iff certainpQ, Dq Q C pDq, for every D D iff naïve evaluation works for Q.

5).

Assume that Q ¦ is weakly monotone and consider D, D I D such that D I rrDss. We prove that Q C pDq Q C pD I q. By definition of rr ss ¦ we know that pD I , tq rrpD, tqss ¦ , for all k-tuples t over Const. Since Q ¦ is weakly monotone, Q ¦ pD, tq ¤ Q ¦ pD I , tq, i.e. t QpDq implies t QpD I q for all k-tuples t over Const. Then Q C pDq Q C pD I q.

Assume now that Q is weakly monotone and consider pD, tq and pD I , t I q in D ¦ such that pD I , t I q rrpD, tqss ¦ . Then t I t and D I rrDss. Since Q is monotone, Q C pDq Q C pD I q; then Q ¦ pD, tq ¤ Q ¦ pD I , tq Q ¦ pD I , t I q. 6). It immediately follows from the definition of Q ¦ .

7)

. Assume D has a strong representative set S, and take S ¦ tpD, tq|D S and t is a k-tuple over Constu. We prove that S ¦ is representative for D ¦ .

Notice that for all pD, tq C ¦ we have that D C, therefore D S. Thus pD, tq S ¦ . Now consider pD, tq S ¦ , then D S; therefore for K C t there exists D I rrDss and a bijection i : adompDq Ñ adompD I q such that ipDq D I and both i and i ¡ are the identity on K. Then pD I , tq rrpD, tqss ¦ . We let i I be the mapping obtained by extending i with the identity mapping on t. It is easy to see that i I is a bijection adompDq t Ñ adompD I qt, such that i I pEq D and i I ptq t. Moreover both i I and i I ¡ are the identity on C. Therefore pD, tq ¦ pD I , tq. Now we define χ S ¦pD, tq pχ S pDq, tq, for all pD, tq D ¦ . Clearly rrχ S ¦pD, tqss ¦ tpD I , tq | D I rrχ S pDqssu, for all pD, tq D ¦ . Therefore rrχ S ¦pD, tqss ¦ tpD I , tq | D I rrDssu rrpD, tqss ¦ . Using this claim in addition to the known relationship between naïve evaluation and weak monotonicity over D ¦ and Q ¦ , we immediately get the following corollaries.

From Theorem 8.2 on D ¦ and Q ¦ , we have: Moreover naïve evaluation works for Q iff Q is weakly preserved under minimal R semhomomorphisms (respectively minimal R sem -homomorphisms) which are the identity on C, and Q C pDq Q C pcorepDqq for all relational instances D.

The characterization of naïve evaluation in the above two corollaries is obtained by using Corollary A.1 and the fact that semantics based on R rdb val as well as on R rdb val are strongly saturated. Similarly semantics based on minimal valuations have a representative set, which is the set of cores (Proposition 9.4). The proof of that proposition applies even if we fix a finite set of constants, meaning that it is also a strong representative set.

Corollary A.2 with C r completes the proof of Lemma 6.3 and of Lemma 11.1. Similarly Corollary A.3 with C r completes the proof of Lemma 11.2. l

  D and D I , a homomorphism h : D Ñ D I is a map from the active domain of D to the active domain of D I so that for every relation symbol S, if a tuple ū is in relation S in D, then the tuple hpūq is in the relation S in D I .

  ) and D | ù ψ. However D I | ù 2ψ because Sp2q does not hold in D I . Intuitively this is due to the fact that an onto homomorphism from D to D I "pre- serves" the domain of D but not its facts: new facts (such as Rp2, 1q) can be present in D I . Thus if the guard is satisfied in D I , it need not be satisfied in D, and this is why satisfaction of ψ may fail in D I . Indeed observe that if the fact Rp2, 1q were in D then Sp2q would hold in D as well (by satisfaction of ψ) and therefore in D I (since D I hpDq and h is the identity). In view of this example, the fact that strong onto homomorphisms disallow new facts in the target instance intuitively explains the following proposition. PROPOSITION 5.2. Sentences in Pos dG are preserved under strong onto homomorphisms.

  Then D | ù ϕ I pb, āq for some value b adompDq. Since ϕ I is preserved under strong onto homomorphisms, D I | ù ϕ I phpbq, hpāqq. Thus D I | ù hyϕ I py, hpāqq, i.e. D I | ù ϕphpāqq. Assume now that ϕpxq dyϕ I py, xq. Assume that an instance D | ù ϕpāq and D has a strong onto homomorphism h to D I . We prove D I | ù ϕphpāqq. Let b adompD I q, we have to prove D I | ù ϕ I pb, hpāqq. Since D I hpDq, there exists a adompDq such that hpaq b; moreover D | ù ϕ I pa, āq. Now, by the induction hypothesis ϕ I py, xq is preserved under strong onto homomorphism, therefore D I | ù ϕ I phpaq, hpāqq ϕ I pb, hpāqq.

  PROPOSITION 7.1. D ¨OWA D I (respectively D ¨CWA D I or D ¨WCWA D I ) iff there is a database homomorphism (respectively, strong onto, or onto database homomorphism) from D to D I . PROOF. Let R sem belong to one of the following semantic relations -OWA: tpD, D I q | D is a complete relational instance and D D I u; -CWA: tpD, Dq | D is a complete relational instanceu; -WCWA: tpD, D I q | D is a complete relational instance, D D I and adompDq adompD I qu.

  is a function from D to nonempty subsets of C, and is an equivalence relation on D. Definition 8.1. If D xD, C, rr ss, y is a database domain, a set S D is representative if

  THEOREM 8.2. Let D be a database domain with a representative set S, and Q a generic Boolean query. Then naïve evaluation works for Q iff Q is weakly monotone and Qpxq Qpχ S pxqq for every x D.PROOF. Theorem 8.2 follows immediately from the lemma below. LEMMA 8.3. Let D xD, C, rr ss, y be a database domain, and Q a generic Boolean query. Assume that D has a representative set S, and let D I be a set S D I D. Then naïve evaluation works for Q over D I iff Q is weakly monotone over D I and Qpxq Qpχ S pxqq for every x D I . In particular if S D (i.e. if D is saturated) then naïve evaluation works for Q iff Q is weakly monotone. A:24 PROOF. Let Q be a Boolean generic query. Assume that naïve evaluation works for Q over D I ; then weak monotonicity of Q over D I immediately follows.

LEMMA 9. 3 .

 3 Let D and D I be relational instances and assume there exists a D- minimal mapping h : adompDq Ñ Const Null with D I hpDq. Let E and E I be relational instances with isomorphisms µ : E Ñ D and µ I : D I Ñ E I , such that µ, µ I and their inverses are the identity on fixph, Dq. Then the mapping µ

  where the b ¥ h i 's are database homomorphisms. Conversely assume that there exists a set of database homomorphisms h 1 , . . . , h n defined on D so that D I th i pDq | 1 ¤ i ¤ nu. Note that database homomorphisms compose, and that |D I | ¨CWA is precisely the set of complete relational instances E such that there exists a set of database homomorphisms from D I to E. Then, by transitivity, there exists a set of database homomorphisms from D to each E |D I | ¨CWA . Hence E |D| ¨CWA for all E |D I | ¨CWA . In other words, |D I | ¨CWA |D I | ¨CWA , and therefore D CWA D I .

¦D

  CWA CWA . ñ Let D CWA D I , i.e., there exists a set of homomorphisms h 1 , . . . , h n from D so that D I 1¤j¤n h j pDq. Now let tu 1 , . . . , u k u be the set of nulls occurring in D. We inductively define a sequence D 0 CWA D 1 CWA . . . CWA D k of CWA -updates of length k where D 0 D and for all 1¤ i ¤ k: D i ¤ 1¤j¤n i¡1 rh j pu i q{u i s Observe that D k D I entails D ¦CWA D I and assume as inductive hypothesis that D k D I whenever k ¤ m. Now let k m 1 be the number of nulls occurring in D. Let also D c Drc{u m 1 s be the result of substituting a fresh constant c for u m 1 everywhere in D and let D c I 1¤j¤n h j pD c q. Homomorphisms being always the identity on constants, each h j : D c Ñ h j pD c q is also a homomorphism and so D c CWA D c I . Now by inductive hypothesis, D c I D c m , where D c m 1¤j¤n D c m¡1 rh j pu m q{u m s. It follows immediately that 1¤j¤n h j pD c ru m 1 {csq 1¤j¤n D c m rh j pu m 1 q{cs. Finally, as 1¤j¤n h j pD c ru m 1 {csq 1¤j¤n h j pDq D I and as 1¤j¤n D c m rh j pu m 1 q{cs D m 1 , it follows that D m 1 D I . ð Assume D ¦ CWA D I . So there is a set of nulls tu 1 , . . . , u k u, a set of ordered sequences of constants and nulls tS 1 , . . . , S k u (i.e., sequences over Const Null) and a sequence D 0 CWA D 1 CWA . . . CWA D k of CWA -updates of length k where D 0 D, D I D k and for all 1

  k j : D Ñ D k is a homomorphism follows from the fact that h k¡1 s : D Ñ D k¡1 is a homomorphism (recall that h k j is the r th child of h k¡1 s). Indeed, h k j is exactly as its parent h k¡1 s , except that it assigns the value x k r to all the preimages of u k by h k¡1 s . So h k j pDq D k¡1 rx k r {u k s, which by assumption is a subinstance of D k . But given that D k¡1 1¤j¤m k¡1 h k¡1 j pDq, this also implies that D k 1¤j¤m k h k j pDq. Observe now that a CWA update D CWA Drv{us can be seen as a special case of multiple CWA update D CWA tDrv{us | v Su where S is a singleton. The proof of ¦ CWA CWA then adapts immediately to a proof of ¦

  Then D | ù ϕ I pb, āq for some value b adompDq. Since ϕ I is preserved under unions of strong onto homomorphisms, D I | ù ϕ I ph i pbq, h i pāqq for each i 1, . . . , k. Thus D I | ù hyϕ I py, h i pāqq, i.e. D I | ù ϕph i pāqq, for each i 1, . . . , k. Now assume that ϕ is a sentence of the form dxpRpxq Ñ ϕ I pxqq where variables x are pairwise distinct. Assume that an instance D | ù ϕ and that D I h 1 pDq ¤ ¤ ¤ h k pDq. We prove D I | ù ϕ. Assume that D I | ù Rp bq for some tuple b; then h i pDq | ù Rp bq for some i 1, . . . , k. Thus there exists a tuple ā over adompDq such that D | ù Rpāq and h i pāq b. Since D | ù ϕ one has that D | ù ϕ I pāq. Now, by the induction hypothesis, ϕ I pxq is preserved under union of strong onto homomorphisms, therefore D I | ù ϕ I ph i pāqq ϕ I p bq. Since this holds for all b such that D I | ù Rp bq, we have that D I | ù ϕ.

l

  Then, just as for Corollary 9.5, we obtain: COROLLARY 10.16. Let Q be a generic Boolean relational query. Then naïve evaluation works for Q under the | | ¨min CWA semantics iff Q is weakly monotone and QpDq QpcorepDqq for every D.

Fig. 1 .

 1 Fig. 1. Summary of naïve evaluation results for FO queries Using Lemma 11.2, we can achieve the desired lifting result for minimal semantics, i.e. we can show that Corollary 9.9 continues to hold for k-ary FO queries. THEOREM 11.4. Let Q be a k-ary FO query such that Q C pDq Q C pcorepDqq for all D.

COROLLARY A. 1 .

 1 Let D be a relational database domain that has a strong representative set S and let Q be a C-generic k-ary query. Then naïve evaluation works for Q if and only if -Q is weakly monotone and -Q C pDq Q C pχ S pDqq for all D D homomorphisms (respectively minimal R sem -homomorphisms) which are the identity on C.

  Then by Drv{Rpt.iqs we mean D in which that occurrence of u is replaced by v Const Null, and by D rv{Rpt.iqs we mean D to which a tuple obtained from t by replacing the occurrence of u in the ith position with v is added (i.e., the original t is retained). Now we consider updates D codd D I of two kinds: -Codd CWA updates: D codd CWA Drv{Rpt.iqs and D codd Rptq adds a tuple to a relation in a database; here D Rptq stands for D in which tuple t was added to relation R. is exactly P , over Codd databases. In other words, two Codd databases are in the P relation iff one can be obtained from the other by a finite sequence of Codd CWA updates, and they are in the H relation iff one can be obtained from the other by a finite sequence of Codd CWA and OWA updates.

	It is known [Libkin 1995] that the reflexive-transitive closure
	-of codd CWA codd OWA is exactly H ; and
	-of codd

CWA D rv{Rpt.iqs;

-OWA update: D codd OWA D CWA

  t t I D I . For every 1 ¤ i ¤ m, we can now put: tt I D I | ht D such that H t t I 1 , . . . , t I i , . . . , t I m and t I t I i u. Observe that by D P D I , D I . Now for every 1 ¤ i ¤ m let h i : D Ñ D i be as follows. For every x Null Const occurring as the j th component in a tuple t D, we define h i pxq as the j th component of the i th tuple in H t . As nulls are repeated neither in D nor in D I and by D P D I , h i is a homomorphism and moreover h i pDq D i . It follows that D CWA D I .We finally show the last item of the Theorem. We first show

	1 , . . . , t I m for some t I 1 , . . . , t I

m D I i 1¤i¤m D I i

  mal R sem -homomorphisms where R sem R .Using Corollary 10.7 with M min we then have: COROLLARY 10.19. If a relational semantics is given by a pair pR min val , R sem q and Q is a generic Boolean relational query, then Q is weakly monotone iff it is preserved under minimal R sem -homomorphisms.

	Semantics open world weak closed-world closed world: powerset closed-world minimal closed-world minimal, powerset closed-world	symbol rr ss OWA rr ss WCWA rr ss CWA | | ¨CWA rr ss min CWA | | ¨min CWA	Naïve evaluation works for hPos unions of CQs Pos Pos dG hPos dG bool Pos dG, over cores; result always contained in certain answers hPos dG bool , over cores; result always contained in certain answers

Acknowledgments. We are very grateful to the referees for their suggestions that helped improve the presentation; we are also grateful to the reviewers of the conference version whose comments too are reflected in this paper. This work was done when Amélie Gheerbrant was at the University of Edinburgh. Work partly supported by EP-SRC grants G049165 and J015377.

ELECTRONIC APPENDIX

The electronic appendix for this article can be accessed in the ACM Digital Library.

However, semantics are no longer given by pairs pR val , R sem q, so we need to reconsider the framework of abstract database domains in order to define proper analogs of R semhomomorphisms and formulate an appropriate notion of preservation. This is what we do now.

Abstract framework for powerset semantics. We now cast the powerset semantics in our general relation-based framework, which enables us to establish when naïve evaluation works for it. For a set D of database objects and a set C of complete objects, we have a pair R pR val , R sem q of relations with R val D ¢2 C and R sem 2 C ¢C. The first relation corresponds to applying multiple valuations (e.g., relating D with sets th 1 pDq, . . . , h n pDqu). The second relation, in our example, is R tpX, Xq | X X u. The semantics given by R is again the composition of two relations: D I rrDss R iff D I pR val ¥ R sem qD.

The basic conditions on these relations are essentially the same as we used before for non-powerset semantics except that we need to deal with relations between C and 2 C . Let id C ¢ 2 C contain precisely all pairs pc, tcuq and id r 2 C ¢ C contain precisely all pairs ptcu, cq for c C. We say that a semantics rr ss R is given by R if both relations are total, relation R val equals id when restricted to C, relation R sem contains id r , and D I rrDss R iff DpR val ¥R sem qD I . Previously we just used identity instead of id and id r .

We say that R sem is transitive if R sem ¥id ¥R sem R sem . Note that R is transitive. Now we have an analog of Proposition 4.2.

PROPOSITION 10.2. A pair R pR val , R sem q gives rise to a fair database domain if R sem is transitive.

PROOF. We prove a more general necessary and sufficient condition for fairness:

LEMMA 10.3. A powerset semantics given by R pR val , R sem q gives rise to a fair database domain iff R val ¥ R sem ¥ id ¥ R sem R val ¥ R sem . In particular if R sem is transitive then the database domain is fair.

PROOF. Assume first that R val ¥R sem ¥id ¥R sem R val ¥R sem , and take an arbitrary x D and c C. We have (1) c rrcss R .

Indeed we know pc, tcuq R val and ptcu, cq R sem , then c rrcss R . (2) c rrxss R implies rrcss R rrxss R .

Indeed if c rrxss R there exists y C such that px, yq R val and py, cq R sem . Moreover if c I rrcss R then pc, c I q id ¥ R sem (because R val is id when restricted to C). Hence px, c I q R val ¥ R sem ¥ id ¥ R sem . This implies px, c I q R val ¥ R sem , and therefore c I rrxss R .

By Proposition 3.6, the database domain is fair.

Conversely assume that the database domain is fair, and px, cq R val ¥ R sem ¥ id ¥ R sem , then there exist c I such that px, c I q R val ¥ R sem and pc I , cq id ¥ R sem . Then c I rrxss R and c rrc I ss R (because R val coincides with id over C). Then by fairness, c rrxss R , and hence px, cq R val ¥ R sem .

Proposition 10.2 immediately follows from the lemma above. l Preservation for powerset semantics. Our next goal is to understand how we can make naïve evaluation work under the powerset semantics. For this we go back to relational database domains. For the standard semantics of incompleteness, we related naïve evaluation to preservation of queries under homomorphisms in the relational setting. We shall do the same here, but the setting for homomorphisms will be a bit different.

A:34

Recall that before we looked at relational semantics defined by two relations, relation R rdb val tpD, vpDqq | v is a valuationu and relation R sem between complete databases. Now we deal with relations R val and R sem . The natural powerset-based analog of R rdb val is the relation

Hence, we now look at the semantics where the valuation relations are R rdb val , and thus the semantics is determined by R sem (e.g., by R tpX, Xq | X X u). In this case, as we did before for relations R sem , we shall refer to semantics given by relation R sem .

Definition 10.4 pR sem -homomorphisms and preservationq.

An R semhomomorphism between complete databases D and D I is a set th 1 , . . . , h n u of mappings defined on adompDq so that th 1 pDq, . . . , h n pDquR sem D I . A Boolean query Q is preserved under R sem -homomorphisms if QpDq 1 and the existence of an R sem -homomorphism between D and D I implies QpD I q 1.

Note that if n 1, this is exactly the notion of R sem -homomorphisms seen earlier.

The connection between naïve evaluation and homomorphism preservation now extends to powerset semantics.

PROPOSITION 10.5. For every relational powerset semantics given by a relation R sem , naïve evaluation works for a generic Boolean query Q iff Q is preserved under R sem -homomorphisms.

PROOF. We prove the proposition by proving some slightly more general results which will be useful later, when dealing with other forms of powerset semantics. These intermediate results hold for powerset semantics on arbitrary database domains, and will therefore be stated in their full generality. Later on in the proof we will restrict our attention to relational database domains.

We start by defining a notion of -equivalence for powerset semantics over arbitrary database domains. This is the analog of the notion of -equivalence (and strongequivalence) introduced for proving Proposition 4.6.

If D xD, C, rr ss, y is a database domain, R and R I are subsets of D ¢ 2 C , we say that R I is -equivalent to R if the following two conditions are satisfied:

(1) if px, X q R then there exists x I D such that x I x and px I , X q R I ;

(2) if px, X q R I then there exists x I D such that x I x and px I , X q R.

When the semantics is given by a pair pR val , R sem q, we have the exact analog of Lemma 4.10:

LEMMA 10.6. Let D xD, C, rr ss, y be a database domain whose semantics rr ss is given by a pair pR val , R sem q and let R I D ¢2 C be -equivalent to R val , then R I ¥R sem is -equivalent to the graph of rr ss (i.e. to R val ¥ R sem q. In particular a generic Boolean query over D is weakly monotone iff it is preserved under R I ¥ R sem .

We can now move to relational database domains. A powerset mapping type M is a function which associates to each complete relational instance D a class tH 1 , . . . H n , . . . u, where each H i is a finite non-empty set of mappings adompDq Ñ

Const.

If M is a powerset mapping type, we denote by R M the set of pairs pD, th 1 pDq, . . . h k pDquq such that D is a complete instance and th 1 , . . . h k u MpDq.

Given two complete relational instances D and D I , an M-R sem -homomorphism from D to D I is an R sem -homomorphism th 1 , . . . h k u from D to D I which belongs to MpDq.

The following claim follows directly from definitions: CLAIM 3. If M is a powerset mapping type then pD, D I q R M ¥R sem iff there exists an M-R sem -homomorphism from D to D I By combining the above claim with Lemma 10.6 we have:

COROLLARY 10.7. Let D xD, C, rr ss, y be a relational database domain whose semantics rr ss is given by a pair pR val , R sem q and let M be a powerset mapping type. Assume that R M is -equivalent to R val . Then a generic Boolean query is weakly monotone iff it is preserved under M-R sem -homomorphisms.

We say that R PpRq if R consists of precisely the pairs px, X q such that X $ r and px, yq R for all y X .

Similarly if M is a mapping type, we denote as PpMq the powerset mapping type associating to each instance D the set consisting of all possible finite non-empty H MpDq. It is easy to check that if M PpMq then R M PpR M q.

We now consider a special case when R val PpR val q.

LEMMA 10.8. On an arbitrary database domain, assume R D ¢C and R PpRq.

If a powerset relational semantics rr ss is based on R val PpR val q and R M is strongly -equivalent to R val , for some mapping type M, then a generic Boolean query is weakly monotone iff it is preserved under M-R sem -homomorphisms, where M PpMq.

PROOF. Assume R I is strongly -equivalent to R. Let px, X q be in R. Note that px, cq R for all c X . Since R I is strongly -equivalent to R, there exists y x such that py, cq R I for all c X . Thus py, X q PpR I q. Symmetrically we prove that if py, X q is in PpR I q then there exists x y such that px, X q R. This proves that PpR I q is -equivalent to R. Now assume a powerset relational semantics is based on R val PpR val q, and R M is strongly -equivalent to R val . The PpR M q is -equivalent to R val . But PpR M q R M for M PpMq. Then by Corollary 10.7, a generic Boolean query is weakly monotone iff it is preserved under M-R sem -homomorphisms.

We are now ready to prove Proposition 10.5. Remark that R rdb val PpR rdb val q. Moreover by Lemma 4.12, if M all, then R M is strongly -equivalent to R rdb val . Remark also that for M all, PpMq-R sem -homomorphisms are precisely R sem -homomorphisms.

It follows then from Lemma 10.8 that, for every powerset semantics given by a relation R sem , a generic Boolean query is weakly monotone iff it is preserved under R sem -homomorphisms. Now note that, under all relational semantics given by a relation R sem the database domain has the saturation property. Then the statement of Proposition 10.5 follows from Theorem 3.5. l Let us now look at the semantics | | ¨CWA given by relation R . The notion of preservation under R -homomorphisms is preservation under union of strong onto homo- morphisms: if Q is true in D, and h 1 , . . . , h n are homomorphisms defined on D, then Q is true in h 1 pDq . . . h n pDq.

For previous preservation results among FO queries, we looked at classes Pos and hPos of positive and existential positive queries, and the class Pos dG of positive queries with universal guards. We now give a fragment of FO preserved under unions of strong onto homomorphisms.

Definition 10.9 pClass hPos dG bool q. hPos dG bool is defined as the class of existential positive queries extended with Boolean universal guards, i.e., universally guarded formulae which are sentences. More precisely, the class contains atomic formulae Rpxq and x y, and is closed under:

Moreover naïve evaluation works for Q iff Q is preserved under minimal R semhomomorphisms, and QpDq QpcorepDqq for every D.

The proposition is now a special case of Corollary 10.19 where R sem R . l

This gives us the following corollaries, in exactly the same way as they were obtained in Section 9.

LIFTING TO NON-BOOLEAN QUERIES FOR MINIMAL AND POWERSET SEMANTICS

In this section we lift results to non-Boolean queries for powerset as well as nonsaturated (e.g., minimal) relational semantics. We use a uniform technique which also proves Lemma 6.3 from Section 6.

For the saturated powerset semantics | | ¨CWA , we can show that the third item in Lemma 6.3 can be replaced by weak preservation under R sem -homomorphisms, i.e.

LEMMA 11.1. Let D be a relational database domain with the strong saturation property, and Q a k-ary generic query. Then the following are equivalent:

(1) naïve evaluation works for Q;

(2) Q is weakly monotone; and

(3) (if the semantics is given by a relation R sem ): Q is weakly preserved under R semhomomorphisms.

Recall from Definition 8.1 that, over a relational database domain, a representative set S is called strong if S is also strongly saturated.

For minimal semantics we have a similar lifting result:

LEMMA 11.2. Let D be a relational database domain, and Q a k-ary generic query. If D has a strong representative set, then the following are equivalent:

(1) Naïve evaluation works for Q;

(2) Q is weakly monotone and Q C pxq Q C pχ S pxqq for every x D. Furthermore, for semantics given by pR min val , R sem q (respectively, pR min val , R sem q), naïve evaluation works for Q iff Q is weakly preserved under minimal R sem -homomorphisms (respectively, minimal R sem -homomorphisms) and

The proofs of these two lemmas, together with Lemma 6.3, are in the electronic appendix.

Using Lemma 11.1 we can prove the desired result for saturated powerset semantics.

THEOREM In order to relate the notions of naïve evaluation, weak monotonicity and preservation for k-ary queries, we proceed as follows. For each relational database domain D and k-ary query Q over D, we define a new database domain D ¦ and a Boolean query Q ¦ over D ¦ . These are defined so that the "Boolean" notions of certain answers , naïve evaluation and weak monotonicity for Q ¦ over D ¦ are precisely equivalent to the cor- responding notions for Q over D. We then apply results from the Boolean case to Q ¦ over D ¦ , and so derive corresponding results for Q over D.

In what follows, if t is a tuple over Const, with a little abuse of notation, we denote as t also the set of constants occurring in the tuple t Given a relational database domain D xD, C, rr ss, y, and a C-generic k-ary query Q over D, we define D ¦ xD ¦ , C ¦ , rr ss ¦ , ¦ y, and Q ¦ over D ¦ as follows: -D ¦ is the set of pairs pD, tq where D D and t is a k-tuple over Const; -C ¦ is the set of pairs of D ¦ where the instance D is in C -for all pairs pD, tq D ¦ the semantics rrpD, tqss ¦ is defined as the set of pairs pD I , tq such that D I rrDss. -pD, tq ¦ pD I , t I q iff there exists a bijection i : adompDq t Ñ adompD I q t I such that D I ipDq and t I iptq (as tuples), and both i and i ¡ are the identity on C. -Q ¦ pD, tq 1 iff t QpDq.

Note that D ¦ and Q ¦ depend on D and Q.

The following claim easily follows from definitions: CLAIM 5.

1) If D is fair, D ¦ is also fair;

2) Q ¦ is generic (i.e. it does not distinguish ¦ -equivalent objects); 3) certainpQ ¦ , D, tq 1 iff t certainpQ, Dq, for every pD, tq D ¦ ; 4) Naïve-evaluation works for Q ¦ iff naïve-evaluation works for Q ; 5) Q ¦ is weakly monotone iff Q is weakly monotone; 6) Q C pDq Q C pD I q iff for every k-tuple t over Const one has Q ¦ pD, tq Q ¦ pD I , tq; 7) If D has a strong representative set S, then D ¦ has a representative set S ¦ with χ S ¦pD, tq pχ S pDq, tq. PROOF. 1). Assume D is fair and consider pD, tq C ¦ . Since D is fair, D rrDss. Then pD, tq rrpD, tqss ¦ . Assume now that pD, tq rrpD I , tqss ¦ . Then D rrD I ss. We also

In particular if the whole set D is strongly saturated, then naïve evaluation works for Q if and only if Q is weakly monotone. This proves that (1) ô (2) in Lemma 11.2, as well as in Lemma 6.3. We now need to prove the relationship between weak monotonicity and preservation for relational semantics based on R rdb val and on R min val (as well as their powerset versions). In the sequel we use the following additional notation.

If H th 1 , . . . h n u is a set of mappings over adompDq, we say that H is the identity on a set of constants K if h i is the identity on K for all i 1, . . . , n. Moreover we let HpDq denote the set th 1 pDq, . . . h n pDqu.

If t is a tuple over Const and X tD 1 . . . D n u is a set of instances we let pX, tq denote the set tpD 1 , tq, . . . pD n , tqu.

Let D xD, C, rr ss, y be a relational database domain where rr ss is given by a pair pR val , R sem q (respectively pR val , R sem q), and let Q be a C-generic k-ary query over D.

Recall the definition of D ¦ and Q ¦ based on D and Q. Recall that Q ¦ is generic over D ¦ and remark that rr ss ¦ is given by the pair pR ¦

where R ¦ val tppD, tq, pD I , tqq | pD, D I q R val and t is a k-tuple over Constu R ¦ sem tppD, tq, pD I , tqq | pD, D I q R sem and t is a k-tuple over Constu Similarly R ¦ val tp pD, tq, pX, tq q | pD, X q R val and t is a k-tuple over Constu and R ¦ sem tp pX, tq, pD, tq q | pX, Dq R sem and t is a k-tuple over Constu.

Recall now the notions of mapping type and M-R sem -homomorphism, as well as the notions of powerset mapping type, and M-R sem -homomorphism, already used in the proofs of Proposition 4.6 and Proposition 10.5.

If M is a mapping type, we let R ¦ M tpx, yq C ¦ ¢ C ¦ | x pD, tq, y phpDq, tq, the mapping h MpDq and h is the identity on C tu.

, tq, X pHpDq, tq, the set of mappings H MpDq and H is the identity on C tu.

The above notion

sem ) if and only if there exists an M-R sem -homomorphism (respectively an M-R semhomomorphism) from D to D I which is the identity on C t.

Recall that given a class T of R sem -homomorphisms (respectively R semhomomorphisms), we say that a k-ary query Q over D is weakly preserved under T if t QpDq implies t QpD I q whenever t is a k-tuple over Const, and in T there exists an R sem -homomorphism (respectively an R sem -homomorphism) from D to D I which is the identity on t.

From the above claim it follows that weak preservation of Q can be characterized as follows:

We now use the above claim and apply Lemma 4.10 and Lemma 10.6 to the database domain D ¦ and the generic query Q ¦ . We obtain the following corollary CLAIM 8. If the semantics rr ss in D is given by pR val , R sem q and R ¦

M is ¦ - equivalent to R ¦ val , then Q is weakly monotone iff it is weakly preserved under M-R semhomomorphisms which are the identity on C.

App-4

If rr ss is given by pR val , R sem q and R ¦ M is ¦ -equivalent to R ¦ val , then Q is weakly monotone iff it is weakly preserved under M-R sem -homomorphisms which are the identity on C.

We now consider mapping types M all and M min, as well as M all (defined as Ppall)) and M min for powerset semantics. CLAIM 9.

val for M all (respectively M min).

PROOF.

We first prove 1). Consider a pair ppD, tq, pD I , tqq where pD, D I q R rdb val and t is a k-tuple over Const. We prove that there exists pE, tq C ¦ such that pD, tq ¦ pE, tq and ppE, tq, pD I , tqq R ¦ M . The instance E is obtained from D by replacing nulls of D with new distinct constants not occurring in ConstpDq C t. Clearly there exists an isomorphism i : E Ñ D such that both i and i ¡ are the identity on C t. We let i I be the mapping obtained by extending i with the identity mapping on t. It is easy to see that i I is a bijection adompEq t Ñ adompDq t, such that i I pEq D and i I ptq t. Moreover both i I and i I ¡ are the identity on C. Therefore pE, tq ¦ pD, tq.

We know that there exists a valuation v on D such that vpDq D I . Let h v ¥i; then hpEq vpDq D I and h is the identity on C t (because both v and i are). This implies ppE, tq, pD I , tqq R ¦ M , for M all. Remark that pE, tq only depends on pD, tq (and not on v).

Conversely consider a pair ppE, tq, pD I , tqq R ¦ M . Let D I hpEq where h is the identity on C t. We prove that there exists pD, tq D ¦ such that pD, tq ¦ pE, tq and pD, D I q R rdb val . The instance D is obtained from E by replacing each element of adompEq not occurring in C t with a new distinct null. Clearly this replacement defines an isomorphism i : D Ñ E such that both i and i ¡ are the identity on C t. As in the previous case i can be extended to show pE, tq ¦ pD, tq.

Let v h ¥ i. Remark that v is the identity on ConstpDq (because ConstpDq C t and both i and h are the identity on C t). Then v is a valuation on D, and hence pD, D I q R rdb val . Note that D depends only on pE, tq (and not on h).

Thus R ¦

M is strongly -equivalent to pR rdb val q ¦ , for M all. Next we prove 2). Consider a pair ppD, tq, pD I , tqq where pD, D I q R min val and t is a ktuple over Const. We then know that D I hpDq where h is a D-minimal valuation. We prove that there exists pE, tq C ¦ such that pD, tq ¦ pE, tq and ppE, tq, pD I , tqq R ¦ M .

The instance E is obtained from D by replacing nulls of D with new distinct constants not occurring in ConstpDq C t. Clearly there exists an isomorphism i : E Ñ D such that both i and i ¡ are the identity on ConstpDq C t. It is easy to check that i can be extended over t to show pE, tq ¦ pD, tq. Now using Lemma 9.3, the mapping h I h ¥ i is E-minimal. Moreover h I pEq D I and h I is the identity on C t. It follows that ppE, tq, pD I , tqq R ¦ M for M min. Conversely consider a pair ppE, tq, pD I , tqq R ¦ M (where M min). Let D I hpEq, where h is E-minimal and h is the identity on C t. We prove that there exists pD, tq D ¦ such that pD, tq ¦ pE, tq and pD, D I q R min val . The instance D is obtained from E by replacing each element of adompEq not occurring in fixph, Eq with a new distinct null.

Clearly this replacement defines an isomorphism i : D Ñ E such that both i and i ¡ are the identity on fixph, Eq. Remark that i and i ¡ are also the identity on C t. Indeed i is the identity on all constants, and i ¡ is the identity on C t because pCtqadompEq fixph, Eq. Thus as in the previous case, i can be extended to show pE, tq ¦ pD, tq. Now let h I h ¥i. By Lemma 9.3 h I is D-minimal. Moreover h I pDq hpEq D I , and h I is the identity on fixph, Eq. Now remark that ConstpDq fixph, Eq, therefore h I is a valuation on D. We then conclude that pD, D I q pD, h I pDqq R min val .

Finally we prove 3). We fist prove that if rr ss is based on

val for M all. Recall the notation Pp q for powerset semantics. Notice that pR rdb val q ¦ PppR rdb val q ¦ q.

We also know by the first item that R ¦

M is strongly ¦ -equivalent to pR rdb val q ¦ for M all. Then by Lemma 10.8, PpR ¦ M q, for M all, is ¦ -equivalent to pR rdb val q ¦ . Now remark that for M all we have PpR ¦ M q R ¦ M , where M all. We now prove that If rr ss is based on

Let ppD, tq, pX, tqq pR min val q ¦ ; then pD, X q R min val . We prove that there exists a complete relational instance E such that pE, tq ¦ pD, tq and ppE, tq, pX, tqq R ¦

M (where M min). Let ConstpX q be the union of ConstpD I q, for all D I X . The instance E is obtained from D by replacing nulls of D with new distinct constants not occurring in ConstpDq ConstpX q C t. Clearly there exists an isomorphism i : E Ñ D. Note that both i and i ¡ are the identity on ConstpDq ConstpX q C t. Therefore i can be extended to show pE, tq ¦ pD, tq.

For each D I X there exists a D-minimal valuation v such that vpDq D I . Let h v ¥ i, then hpEq D I and, by Lemma 9.3, h is E-minimal. Note also that fixph, Eq ConstpDq, and h is the identity on C t. Since such an h exists for all D I X , the set of all h mappings, when D I ranges over X , is E-minimal, as well as the identity on C t. Then ppE, tq, pX, tqq R ¦ M (for M min). pE, X q R M . This proves one direction. Conversely assume ppE, tq, pX, tqq R ¦ M for M min, then X th 1 pEq, . . . h n pEqu where th 1 , . . . h n u is E-minimal and the identity on C t. We prove that there exists a relational instance D such that pD, tq ¦ pE, tq and pD, X q R min val . Let K fixph i , Eq (which is the same for all i 1, . . . , n).

The instance D is obtained from E by replacing each element of adompEqzK with a new distinct null. Clearly this replacement defines an isomorphism i : D Ñ E. Note that both i and i ¡ are the identity on K; thus they are the identity on C t. Indeed i is the identity on all constants; moreover pC tq adompEq K, then i ¡ is the identity on C t. Then we can extend i to show pD, tq ¦ pE, tq.

The mappings v j h j ¥i, for j 1, . . . , n are all D-minimal, by Lemma 9.3. Moreover notice that ConstpDq K, then v j is the identity on ConstpDq, and therefore a Dminimal valuation on D. Moreover v j pDq h j pEq, for all j 1, . . . , n. It follows that pD, X q R min val . We now combine the above two claims and get a characterization of weak monotonicity under both standard an minimal semantics: COROLLARY A.2. Assume that a relational semantics is given by a pair pR rdb val , R sem q, (respectively pR rdb val , R sem q) and let Q be a C-generic k-ary relational query.

Then Q is weakly monotone iff Q is weakly preserved under R sem -homomorphisms (respectively R sem -homomorphisms) which are the identity on C. Moreover naïve evaluation works for Q iff Q is weakly preserved under R semhomomorphisms (respectively R sem -homomorphisms) which are the identity on C. COROLLARY A.3. Assume that a relational semantics is given by a pair pR min val , R sem q, (respectively pR min val , R sem q) and let Q be a C-generic k-ary relational query. Then Q is weakly monotone iff Q is weakly preserved under minimal R sem -