Explainable Certain Answers

1 Introduction

Problems where AI and data management techniques meet are characterized by the need to compute answers to queries over many possible worlds, such as instances of a global schema in data integration [Cal`ı et al., 2003; Lenzerini, 2002] or solutions in data exchange [Arenas et al., 2014; Fagin et al., 2005] or results of chasing a database with ontology constraints [Calvanese et al., 2007; Cal`ı et al., 2012]. This is due to the fact that datasets one uses for query answering typically contain null values (i.e., unknown individuals), and thus they represent potentially many possible complete worlds (i.e., datasets without null values). Query answering that takes all of them into account is based on the notion of certain answers.

Intuitively, certain answers are those that are true in all possible worlds. However, defining this notion formally is not completely straightforward. There are two different approaches. One of them, applicable when databases are relations (sets or multisets of tuples), simply looks for tuples that are present in all answers [Imielinski and Lipski, 1984], i.e., the intersection of query answers in all possible worlds. We refer to this notion as intersection-based. In fact one often uses its slight generalization that also allows tuples with null values in the output [Lipski, 1984]. This is what one typically finds in the literature on querying incomplete information, or its applications such as data integration, data exchange, or ontology-based data access (OBDA).

While this notion looks rather natural, it comes with little justification, which led to an attempt [Libkin, 2016] to provide a systematic approach to defining certain answers; it generalized earlier approaches that utilized techniques from programming semantics [Buneman et al., 1991; Rounds, 1991]. Suppose we have an incomplete object x, and let JxK, the semantics of x, be the set of all of its possible worlds. To answer a query Q on x, we need to extract certain information from QpJxKq � tQpyq | y P JxKu, where Qpyq is the answer to Q on y. The key element of this approach is the assumption that we have an ordering on query answers: a / a1 means that a1 is at least as informative as a (i.e., a1 contains at least all information from a). This defines the notion of a candidate answer, which is an object a such that a / Qpyq for all y P JxK. In other words, a candidate answer is no more informative than any of query answers in possible worlds. A certain answer is the maximal candidate answer, i.e., the most informative answer consistent with answers in all possible worlds (formally, it is the greatest lower bound of the set QpJxKq). We refer to this notion as informativeness-based.

To compare this approach with the intersection-based approach for the relational data model, we need to explain what the incomplete objects are and how the informativeness ordering is interpreted. Most commonly, incompleteness is represented by marked nulls [Imielinski and Lipski, 1984] (this is in fact the model typically used in applications such as data integration and exchange and OBDA). In databases with marked nulls, some of the entries are nulls that represent currently unknown values. Possible worlds are obtained by assigning values to nulls; e.g., by means of a function v on nulls whose values are constants that can appear in complete databases.

Queries over relational databases produce relations as well. Let R and R1 be two relations that can appear as a query answers, and assume that R1 has no nulls, i.e., it is a query answer on a complete database. Then R1 is at least as informative as R if vpRq � R1 for some valuation v of nulls in R. That is, R1 provides additional information by instantiating nulls in R and adding some tuples. With these notions in place, we can now see how the two approaches to defining certainty compare.

Example 1. Consider an incomplete database D � tRp1, 1q,Rp2, 1q,Rp2,Kq, SpK, 1qu with three tuples in relation R and one tuple in relation S, where K denotes a null value. Let Qpx, yq � Rpx, yq ^ Spx, yq be the query computing the difference of R and S. Possible worlds of D could be of three kinds:

• D1 � tRp1, 1q, Rp2, 1q, Sp1, 1qu, if K is mapped to 1;
• D2 � tRp1, 1q, Rp2, 1q, Rp2, 2q, Sp2, 1qu, if K is mapped to 2, and
• Dc � tRp1, 1q, Rp2, 1q, Rp2, cq, Spc, 1qu, if K is mapped to some other value c � 1, 2.

This gives us the following sets of answers

• QpD1q � tp2, 1qu,
• QpD2q � tp1, 1q, p2, 2qu, and
• QpDcq � tp1, 1q, p2, 1q, p2, cqu, for c � 1, 2.

There are no tuples present in all these answers, and thus the standard intersection-based approach will return the empty set. Its generalization that permits nulls in answers will return the single tuple p2,Kq. Indeed, if K is mapped to 1, then p2, 1q P QpD1q; if K is mapped to 2, then p2, 2q P QpD2q; and if K is mapped to c � 1, 2, then p2, cq P QpDcq.

The informativeness-based notion of certain answer results in the set A � tpK1, 1q, p2, K2qu. Indeed, one can see that for each c, there is v such that vpAq � QpDcq, and it is not hard to show that A is the greatest lower bound of all QpDcqs.

Thus, the informativeness-based notion of certainty may be different from the intersection-based notion. We do not yet understand the informativeness-based notion well, however. For example, we do not know whether the certain answer defined as the greatest lower bound always exists, nor do we know how large it can be when it does exist. The latter question was partially answered in [Arenas et al., 2017]: even for unions of conjunctive queries with inequalities, it can be of super-polynomial size under the open-world interpretation of incomplete databases. We complete the picture. First we show that for open-world, even for first-order queries, such certain answers need not exist. For closed-world semantics, certain answers exist for queries expressible in any reasonable logical language, but could still be of super-polynomial size. So suddenly the informativeness-based approach to defining certain answers faces a very serious obstacle of either non-existence or infeasible sizes of answers.

The reason for this bad behavior lies in the excessive permissiveness of the definition of certain answers with respect to information content. If y P JxK, there must be a specific explanation as to why y is a possible world. However, we only require a / Qpyq if a is candidate answer: that is, such an answer is less informative than Qpyq but for reason that may have nothing to do with the fact that y is a possible world for x. This may lead to bizarre candidate answers. Indeed, returning to Example 1, consider the tuple p1,K1q. It matches QpD1q, obtained by interpreting K as 1, when K1 is mapped to 2, and it matches QpD2q, obtained by interpreting K as 2, when K1 is mapped to 1. Thus, there is no connection between how a possible world is obtained, and why the tuple is in the answer to Q in that possible world.

Instead of the very permissive definition of candidate and certain answers, it seems much more natural to require, for a candidate answer a, that a / Qpyq for the same reason that y is in JxK: that is, whatever explanation is given to y P JxK, it should also explain why a / Qpyq. This idea gives us the notion of explainable candidate answers, and maximal such answer is the explainable certain answer.

Our main contribution is to extend the theory of informativeness-based notion of certainty to include explanations of why tuples appear in the answer, and to relate explainable certain answers to the classical intersection-based approach. As the first step, we develop a general, datamodelindependent, framework to reason about explanations applied to incomplete objects, and to query answers. Essentially, explanations are viewed as operations that can be applied to objects to make them more informative; such explanations compose, and naturally lead to notions of explainable candidate and certain answers.

We then see how these notions look in the familiar relational model, under both open- and closed-world semantics of incompleteness. Our main result in this case is that for both semantics, explainable certain answers always exist, are of at most polynomial size in the size of the input, and are, essentially, the intersection-based answers (to be more precise, their slight extension that allows nulls in the output: the one that produced the answer p2, Kq in Example 1). Thus, the standard notion so common in data management and reasoning literature is well justified after all, by applying the concept of explanations to both database objects and query answers.

Organization. Basic definitions are in Section 2. Existence and size of answers as greatest lower bounds is studied in Section 3. Section 4 compares the intersection- and informativeness-based notions of certainty. Section 5 introduces the framework of explanations, and Section 6 shows what explainable certain answers are for common semantics.

2 Preliminaries

Incomplete databases. An incomplete database D represents many possible worlds, or complete databases, known as its semantics JDK. As a concrete model of incompleteness we look at relational databases with marked nulls that dominate applications such as data integration, OBDA, and data exchange [Arenas et al., 2014; Lenzerini, 2002; Bienvenu and Ortiz, 2015]. Entries in databases come from the sets of constants and nulls, denoted by Const and Null. We use the symbol K for nulls. A database D is a set of relations over Const YNull;

a k-ary relation is a finite subset of pConstYNullqk . Sets of constants and nulls that occur in D are denoted by ConstpDq and NullpDq. Its domain is dompDq � ConstpDq YNullpDq. A complete database has no nulls.

A homomorphism h : D � D1 is a mapping from dompDq to dompD1 q such that hpcq � c for c P ConstpDq, and for each tuple ¯a in relation R of D, the tuple hp¯aq is in relation R of D1 . The image of h is denoted by hpDq.

A homomorphism v is a valuation if its range contains only constants, i.e., vpKq P Const for each null (we shall be using v for valuations, and h for arbitrary homomorphisms). Two most common semantics of incompleteness, under open- and closed-world assumptions (OWA and CWA) are given as follows [Abiteboul et al., 1995; Imielinski and Lipski, 1984]:

JDK OWA � tD1 complete | D valuation v : D�D1 u JDK CWA � tD1 complete | D valuation v : D1 � vpDqu

That is, under CWA, one just replaces nulls with constants, and under OWA, one can add extra tuples, cf. [Reiter, 1977].

Query answering. A relational query Q of arity k takes a complete database D and returns a set of k-tuples over ConstpDq. If such a query Q is asked on an incomplete database D, to answer it under semantics J K, one has to analyze QpJDKq � tQpD1 q | D1 P JDKu. The definition one sees most commonly in the literature is simply � QpJDKq �

�tQpD1 q | D1 P JDKu. We shall consider a slightly more permissive definition:

lOWApQ,Dq � t¯a | @v : D�D1 vp¯aq P QpD1 qu lCWApQ,Dq � t¯a | @v : vp¯aq P QpvpDqqu

where v ranges over valuations on D, and ¯a is a tuple over constants and nulls. The latter comes from [Lipski, 1984], and has often been used as a substitute for intersection-

• based definition since null-free tuples in lCWApQ,Dq and � QpJDK CWA q are exactly the same (and likewise for OWA). For Boolean (true/false) queries, where the standard representations of true and false are tpqu and H (i.e., the set containing the empty tuple pq, and the empty set), lpQ,Dq and � QpJDKq are the same for both OWA and CWA semantics. Otherwise lOWApQ, Dq and lCWApQ, Dq may produce informative tuples with nulls. For instance, if Q returns a relation R in D, then lOWApQ,Dq � lCWApQ,Dq � R, while both

� QpJDK OWA q and � QpJDK CWA q contain only null-free tuples in R.

Query languages. As our basic query language, we shall use first-order predicate logic (FO) over the relational vocabulary. Its formulae are built up from relational atoms Rp¯xq and equality atoms x � y, using Boolean connectives ^,_, , and quantifiers D, @. The D,^-fragment of FO is known as conjunctive queries. Their unions are denoted by UCQ (unions of conjunctive queries); in terms of their expressiveness, they correspond to the D,^,_-fragment of FO. If inequality atoms x � y are allowed in them, we have the class of unions of conjunctive queries with inequalities, denoted by UCQ�.

3 Query Answers as Greatest Lower Bounds

We now outline a general approach to viewing certain query answers as greatest lower bounds in orderings induced by information content, and then see what it yields for answering relational queries, under both OWA and CWA semantics.

A General Framework

We review the basics of the framework of [Libkin, 2016]. A database domain is a triple xD, C, J Ky where D is a set of database objects (e.g., all databases of a given schema), C � D is a set of complete objects, and J K is the semantic function that assigns complete objects (possible worlds) to an incomplete object, i.e., JxK � C. With such a domain, we associate its information ordering given by x / y iff JyK � JxK. The intuition is that the more possible worlds there are for x, the less information about x we have.

Given two database domains xD1 , C1 , J K 1 y and xD, C, J Ky, a query is a mapping Q : C1 � C, i.e., a mapping from complete objects (query inputs) to complete objects (query answers). This is consistent with the standard query languages. To extend Q to arbitrary elements of D in a correct way, we need to extract certain information from QpJxKq. We say that a is a candidate answer to Q on x if a / Qpcq for every c P JxK, and a is a certain answer to Q on x if it is maximal among candidate answers. In other words, the certain answer is the greatest lower bound of QpJxKq in ordering /, denoted by glb/QpJxKq. Depending on a concrete ordering / on D, certain answers may or may not exist. If certain answers do exist, then JyK 1 � JxK 1 implies glb/QpJxKq / glb/QpJyKq. That is, more informative query inputs yield more informative query answers.

The Framework for Relational Databases

When elements of database domains are relational databases, for query inputs we use either OWA or CWA semantics. For the semantics of answers, it is common to use OWA. Indeed, a partial query answer can be improved in two ways: either by finding more tuples, or by instantiating nulls with values. This is precisely what the OWA semantics does. The ordering it generates, D � D1 iff JD1 K OWA � JDK OWA , has a nice description: D � D1 iff there is a homomorphism h : D � D1 , see [Gheerbrant et al., 2014].

This is a well-known and studied relation [Hell and Neˇsetˇril, 2004], and we now recall some basic notions related to it. It is a preorder, that is, reflexive and transitive. If both D � D1 and D1 � D hold, we say that D and D1 are homomorphically equivalent and write D � D1 ; note that � is an equivalence relation. A relational structure is a core if it has no proper substructure that is homomorphically equivalent to it. A substructure D1 of D is called a core of D if it is a core and D � D1 . It is known that up to isomorphism, there is only one core of D, and thus one speaks of the core of D, denoted by corepDq. Any two homomorphically equivalent structures will have the same core (up to isomorphism).

The certain answer to a relational query Q on an incomplete database D is glb�QpJDKq, where J K is either J K OWA or J K CWA , and the greatest lower bound is taken with respect to �. Since � is a preorder, glb� is defined up to homomorphic equivalence, and one typically takes the core of these homomorphically equivalent structures to represent glb�.

For structures D1 and D2, their greatest lower bound is any structure homomorphically equivalent to D1�D2 [Hell and Neˇsetˇril, 2004]. Thus, there is the smallest such structure, namely corepD1 �D2q. If homomorphisms are required to preserve constants, the definition of the product D1�D2 needs a small adjustment: if ai P dompDiq, for i � 1, 2, then we replace the pair pa1, a2q in the domain of D1�D2 by a1 if a1 � a2 P Const and by a fresh null otherwise [ten Cate and Dalmau, 2015; Libkin, 2011]).

While glb� exists for finite sets, our goal is to find it for infinite sets QpJDKq. That is what we analyze now.

Certain Answers for UCQs.

In the case of unions of conjunctive queries, there is an easy description of these greatest lower bounds. By QpDq we mean the na¨ıve evaluation of Q on D that treats nulls simply as new constant values. Then, if Q P UCQ,

see [Imielinski and Lipski, 1984; Gheerbrant et al., 2014; Libkin, 2016]. Thus, it is of interest to us what happens for more complex queries, e.g., UCQ� or FO queries.

Bounds under OWA.

Now we have a relational query Q and we want to compute glb�QpJDK OWA q for a database D. It was shown already in [Arenas et al., 2017] that its size could be exponential even for UCQ� queries. That is, glb�QpJDK OWA q always exists if Q P UCQ�, and, moreover, there exists a sequence Dn, n P N, of databases of increasing size and a UCQ� query Q such that the size of glb�QpJDnK OWA q is 2Op}Dn}q , where the size }D} of a database is measured as the number of tuples in it.

When we move to arbitrary FO queries, the situation is much worse.

Theorem 1. There is an FO query Q and a database D such that glb�QpJDK OWA q does not exist.

Proof idea. Let D contain a unary relation U with a single element, and an empty binary relation R. Let q state that for each element of R, its indegree and outdegree are 1, and let Q return R if q is true, and tpx, xq | x P Uu otherwise. A database D1 in JDK OWA contains a graph R and a set U; then Q returns R if it is a disjoint union of directed cycles, and single loops on elements of U otherwise.

Let Cn be a directed cycle of length n. From the above and the fact that Cn � Cn \ Cm (where \ denotes disjoint union) it is easy to derive that glb�QpJDK OWA q � glb�tCn | n ¡ 0u. Since Cmn � Cm, we then get that the latter equals glb�tCn! | n ¡ 0u. Now one can use techniques from [Hell and Neˇsetˇril, 2004] to show that such a greatest lower bound does not exist.

Bounds under CWA.

For CWA, we can recover the existence of greatest lower bounds for a large class of queries, but we still have very high bounds on their sizes. Recall that a query Q is generic [Abiteboul et al., 1995] if QpπpDqq � πpQpDqq for every permutation of the domain (i.e., for a bijection π : dompDq � dompDq). All queries in FO and many other logics over the relational vocabulary are such.

Theorem 2. If Q is a generic query, then glb�QpJDK CWA q always exists, and its size is bounded by 22Op}D}q .

Proof idea. Given a database D, a valuation v is admissible if its range is contained in ConstpDq together with | NullpDq|�1 new constants not present in D. Let ApQ, Dq � tQpvpDqq | v admissible valuationu. Note that ApQ,Dq � QpJDK CWA q, and ApQ,Dq is a finite set. The key lemma is to show that glb�pJDK CWA q � glb�ApQ, Dq.

To construct glb�ApQ,Dq, we have to find the core of the product of the elements of ApQ,Dq; since the number of admissible valuations is exponential, the product size is at most doubly exponential.

As for the lower bound, we can adapt the construction of [Arenas et al., 2017] to show the following:

Proposition 1. There exists a family of incomplete databases Dn, for n P N, of increasing size, and a UCQ� query Q such that the size of glb�QpJDnK CWA q is 2Op}Dn}q .

This still leaves a gap between the exponential lower bound and the double exponential upper bound. To give an idea why it is very hard to close the gap, note that lower bound proofs are based on constructing, for each n, a polynomialsize family of cores of size up to n that are closed under product; this results in an exponential size greatest lower bound. For a double-exponential bound, we would need to find an exponential-size family of cores closed under product. However the existence of such a family is not known.

A double exponential lower bound can be produced for monadic second-order logic, MSO (the fragment of secondorder where all second-order quantification is over sets, and both first- and second-order free variables are allowed).

Proposition 2. There is a family of incomplete databases Dn, for n P N, of increasing size, and an MSO query Q such that the size of glb�QpJDnK CWA q is 22Ωp}Dn}q .

Proof idea. We first show how with an MSO query, we can generate, on JDnK CWA , outputs which are directed cycles of lengths up to 2n , where Dn has Opnq tuples. Thus, glb�QpJDnK CWA q must contain corep�i/2n Ciq, which is known to be CN, where N is the least common multiplier of numbers up to 2n . Thus, N ¥ -tp / 2n | p primeu, and lnN ¥ θp2n q, where θpxq is the sum of lnp over prime p / x. It is known that θpxq ¥ x for sufficiently large x, see [Rosser and Schoenfeld, 1962], and thus N ¥ e2n , from which the bound is easily derived. l

4 Comparing Certainty Notions

We have defined certain answers as greatest lower bounds glb�QpJDK � q when � is OWA or CWA. On the other hand, we have standard notions of certain answers in the literature, namely lCWApQ,Dq and lOWApQ,Dq. How do they compare?

We know that lCWApQ,Dq and lOWApQ,Dq are candidate answers, under the appropriate semantics; that is, l�pQ,Dq � QpD1 q for each D1 P JDK � . However, they are not in general informativeness-based certain answers: we already saw, in Example 1, that glb�QpJDK CWA q and lCWApQ, Dq can be different. In that example, lCWApQ,Dq � tp2,Kqu, while glb�QpJDK CWA q � tpK1, 1q, p2, K2qu. A similar example can be constructed under OWA as well.

In fact Example 1 showed that the intersection-based notion can miss some of the answers justified under the informativeness-based notion. On the other hand, the informativeness-based notion of certainty does not behave well computationally: it may not exist, or may be prohibitively large. To reconcile good properties of the two notions, it would thus be nice to produce proper justifications for answers of the form l�pQ,Dq. To do so, we observe the following: in Example 1, each of the possible worlds for D is explained by means of a valuation v. If we take, in that example, the tuple ¯a � pK1, 1q which belongs to glb�QpJDK CWA q but not to lCWApQ,Dq, we shall always have some valuation v1 so that v1 p¯aq P QpvpDqq, but we cannot ensure that v1 always equals v. In other words, we cannot ensure that the same explanation accounts for a possible world for an incomplete database, and for the tuple being an answer in that possible world.

This is an informal description of why the notions of l�pQ,Dq are justified: they appear to be the most informative answers under the assumption that the same explanation accounts for a possible world and the query answer in that possible world. We next formalize the notion of explanations.

5 Explanations: The Framework

We now present an abstract framework to reason about explanations applied to incomplete database objects, while providing analogies with the common OWA and CWA relational semantics. This is done to keep the intuition clear; detailed treatment of these semantics will be presented in Section 6.

Assume that we have a set D of database objects, as in Section 3. On this set we have an oblivious preorder ¤ε; intuitively, x ¤ε y means that we know that y is at least as informative as x without having to provide additional information. For example, under OWA, this will be the subset ordering D � D1 (tuples can be added freely), and under CWA, it is just the identity D �D1 .

Next, we need actions; these are functions on objects that return objects. Some actions with special properties will be viewed as explanations of incomplete information. The set of actions Ω is a monoid: actions can be composed, and there is the identity (unit) action. This is captured by:

Definition 1 (Action Structure). An action structure A consists of:

• a set D of database objects with an oblivious preorder ¤ε;
• a monoid Ω with an associative composition operation denoted by ωω1 and unit ε (i.e., εω � ωε � ω); and
• a function D � Ω � D, whose result on x P D and ω P Ω is denoted by xω , such that xε � x and xωω1 � pxω qω1 , and furthermore x ¤ε y implies xω ¤ε yω for all x, y P D and ω, ω1 P Ω.

The intuition, in the case of relational databases, is as follows. Actions are functions that can modify database entries, i.e., they are functions f : ConstYNull � ConstYNull. They can provide us with additional knowledge (e.g., by replacing a null with a constant), or to the contrary decrease our knowledge (by doing the reverse). The unit of the monoid of functions is the identity function. Then xω is the result of applying an action to an object. In case of relational databases, if we have a database D and a function f as above, the result of applying this action is simply fpDq. The last condition says that if x is obliviously at most as informative as y, then changing information in both x and y in the same way does not change that.

We extend ¤ε to all elements of Ω by defining x ¤ω y iff xω ¤ y. It says that by applying the action ω, object x is at most as informative as y.

Explanations are special kinds of actions. A relational intuition for actions is replacing some values in relational databases by others. When we replace nulls by other values, this explains why one object is more informative than another. In particular, we can replace all nulls by constants, resulting in a complete object, to which no further explanations apply. The following definition captures this distinction between arbitrary actions and explanations.

Definition 2 (Explanation Structure). An explanation structure E is a restriction of an action structure A to a submonoid Σ of Ω, whose elements are called explanations, so that for each x P D, there is σ P Σ, called x-complete, such that pxσ qσ1 � xσ , for all σ1 P Σ. If ε is x-complete, then x is called a complete object, and the set of such objects is denoted by C.

If σ is x-complete, then no other explanation changes xσ , i.e., σ already explained all the incompleteness of x. A complete object in C is one for which ε is x-complete, i.e., there is no incompleteness to explain, and xσ � x for all σ P Σ. In the relational case, explanations are maps f : ConstYNull � ConstYNull that are the identity on constants (i.e., homomorphisms). For a relational database D, an explanation is D-complete if it is a valuation on D, i.e., it maps D to a complete database. Complete databases, under this definition, will be those without nulls.

Given an explanation structure E, we define the semantics of an object x P D with respect to an explanation σ P Σ as the set of all complete objects which are at least as informative as x with the help of explanation σ, i.e.,

The semantics of an object is the set of complete objects that can be explained to be at least as informative as x:

We also write x ¤ y if x ¤σ y for some σ P Σ. Below we summarize basic properties of these notions.

Proposition 3. · ¤ is a preorder.

• If xσ is a complete object, then xσ P JxK Eσ .
• If x ¤σ y, then JyK Eσ1 � JxK Eσσ1 , for each σ1 P Σ.

Semantics and Ordering

It is standard to define information ordering on objects by comparing their semantics, i.e., x ¤ y iff JyK � JxK. Here we took a different path and defined both the semantics and the ordering based on the actions of explanations on objects. Does the connection between them continue to hold?

The answer is positive in the presence of canonical explanations. These are analogous, in the case of relational databases, to replacing null values with new distinct constants. These are important for defining na¨ıve evaluation of queries, when nulls are treated as constants. Crucially such explanations are invertible: one can change these new constants back into nulls, and apply this inverse to other objects that use the same constants. The following definition captures this intuition. First, we say that ω P Ω is explainable on x if xω � xσ for some σ P Σ. That is, the action of ω may not always be an explanation, but on x it is.

Definition 3 (Canonical explanation). For an object y P D, a y-complete τ P Σ is a canonical explanation for y if two conditions hold. (1) There is τ 1 P Ω such that yττ 1 � y. (2) If σ P Σ is a y-complete explanation, and x P D satisfies x ¤σ1 yσ for some σ1 P Σ, then σ1 τ 1 is explainable on x.

Theorem 3. Given an explanation structure E, let y P D be such that there is a canonical explanation for it. Then, for x P D, we have x ¤ y if and only if JyK E � JxK E .

Explainable Answers to Queries

Let D and D1 be two sets of database objects, and let Σ be a monoid of explanations that gives rise to explanation structures E and E1 on these sets. We use notations with 1 for all the concepts in E1 , i.e., C1 for complete objects, ¤1σ and ¤1 .

Definition 4 (Explainable answers). A query Q is a map from C to C1 . Given x P D and a P D1 , we say that a is an explainable candidate answer to Q on x if for every c P JxK σ we have a ¤1σ Qpcq. A maximal, with respect to ¤1 , explainable candidate answer is called an explainable certain answer.

That is, for explainable candidate answers, the same explanation has to account for c being a possible world of x, and for a being at most as informative as the answer in that world. Certain answers, as before, are maximal candidate answers. These behave in the expected way.

Theorem 4. Let Q : C�C1 be a query.

• Assume that x ¤σ y for x, y P D. If a is an explainable candidate answer to Q on x, then aσ is an explainable candidate answer to Q on y.
• If glb¤1QpJxKq exists, then it is an explainable certain answer to Q on x.
• If x ¤ y and a, b are explainable certain answers to Q on x and y respectively, then a ¤1 b.

These say that query answers are still more informative on more informative inputs, but extra information in query answers is not arbitrary: instead it is added according to the way in which information was added to the inputs.

6 Explainable Certain Answers in Open and Closed Worlds

We now look at action and explanation structures for the common OWA and CWA semantics. These are easy to construct.

Their elements are relational databases, complete objects are databases without nulls, actions are functions on database entries, and explanations are those actions that preserve constants (i.e., they either assign a constant to a null, or equate two nulls). The only difference between them is the oblivious ordering, which is subset for OWA (to account for adding tuples), and identity for CWA. We then prove that in both of these explanation structures, lOWA and lCWA are exactly the explainable certain answers.

6.1 Explainable Answers under OWA

Let ρ be a relational vocabulary. We define action and explanation structures AOWApρq and EOWApρq for relational databases over ρ. In AOWApρq:

• the domain Dpρq is the set of all databases of vocabulary ρ over Const Y Null;
• the oblivious preorder ¤ε is the subset relation �;
• the monoid Ω contains all functions f : ConstYNull � Const YNull, with the identity function as its unit element, and composition of functions as its binary operation.

The relation D ¤f D1 is thus given by fpDq � D1 .

For the explanation structure EOWApρq, the submonoid of Ω is H, the set of all homomorphisms, which are maps h P Ω such that hpcq � c for every c P Const. Recall that a homomorphism h is called a valuation if hpNullq � Const.

Let J K EOWApρq be the semantics defined by EOWApρq, and let ¤ be the associated preorder, as shown in the previous section. The theorem below summarizes properties of the structures, the preorder, and the semantics.

Theorem 5. For each relational vocabulary ρ:

• AOWApρq is an action structure and EOWApρq is an explanation structure;
• every valuation v P H is a complete explanation;
• complete objects are exactly ρ-databases without nulls;
• J K EOWApρq coincides with J K OWA ;
• the preorder ¤ is � (the existence of a homomorphism);
• for D P Dpρq, canonical explanations are valuations that are bijections with the range disjoint from ConstpDq.

The existence of canonical explanations implies that D ¤ D1 iff JD1 K EOWApρq � JDK EOWApρq , which also follows from [Gheerbrant et al., 2014].

A relational k-ary query Q takes a complete database from Dpρq and produces a complete database in Dpρ1 q, where ρ1 consists of a single k-ary relation A (for answer). To define the notion of explainable candidate and certain answers on arbitrary databases, we need explanation structures on Dpρq and Dpρ1 q. As mentioned earlier, query answers are always interpreted in EOWApρ1 q. When query inputs are interpreted in EOWApρq, we can view Q as a map from complete objects in EOWApρq to complete objects in EOWApρ1 q. This, by Definition 4, gives us the notions of explainable candidate and certain answers under OWA. The result below provides their precise characterization.

Theorem 6. If Q is a k-ary relational query defined on complete databases, and D is an arbitrary database, then

• the explainable certain answer under OWA is lOWApQ,Dq;
• explainable candidate answers under OWA are exactly the subsets of lOWApQ, Dq.

This justifies the use of lOWA and its approximations for finding certain answers under the OWA semantics.

6.2 Explainable Answers under CWA

We define action and explanation structures ACWApρq and ECWApρq just as we did for the OWA case, with a single change: now the oblivious preorder, which we denote by �ε to distinguish it from the OWA case, is the identity (i.e., only D �ε D is true). This reflects the fact that under CWA, no information is added to an incomplete database except by applying a map to its nulls. This extends to relations �h for for h P H, where D �h D1 iff D1 � hpDq. Let � be the union of all such relations, and let J K ECWApρq be the semantics associated with ECWApρq. The following is an analog of Theorem 5 for CWA.

Theorem 7. For each relational vocabulary ρ:

• ACWApρq is an action structure and ECWApρq is an explanation structure;
• every valuation h P H is a complete explanation;
• complete objects are exactly ρ-databases without nulls;
• J K ECWApρq coincides with J K CWA ;
• D �D1 iff hpDq �D1 for some homomorphism h.

Let Q be a query from complete databases in Dpρq to complete databases in Dpρ1 q, where again ρ1 consists of a single k-ary relation A. We consider inputs as elements of the explanation structure ECWApρq and outputs, as before, as elements of the explanation structure EOWApρ1 q. Then again Definition 4 gives us notions of explainable candidate and certain answers, this time under CWA. They can be characterized as follows.

Theorem 8. If Q is a k-ary relational query defined on complete databases, and D is an arbitrary database, then

• the explainable certain answer under CWA is lCWApQ,Dq;
• explainable candidate answers under CWA are exactly the subsets of lCWApQ, Dq.

Thus, similarly to the OWA case, this result justifies the use of lCWA for finding certain answers under the CWA semantics.

6.3 Justification for Intersection-Based Certain Answers

Theorems 6 and 8 allow us to provide justifications for the commonly used intersection-based certain answers, i.e., lX� pQ,Dq � �tQpD1 q | D1 P JDK � u, where � is OWA or CWA. We say that a tuple ¯a is an explainable answer to Q on D under semantics � if it belongs to the explainable certain answer under �. Then:

Corollary 1. Let Q be a k-ary relational query, D a database, and ¯ c a k-tuple over ConstpDq. Then ¯ c is an explainable answer to Q on D under � iff ¯ c P lX� pQ, Dq, where � is OWA or CWA.

Thus, lX� pQ, Dq is the maximal explainable candidate answer containing only constant tuples, under both OWA and CWA. Also, Corollary 1 implies that for Boolean queries, lX� pQ,Dq is precisely the explainable certain answer, under both OWA and CWA, thereby providing justification for the notions of certainty most commonly found in query answering literature.

7 Conclusions

Our goal was to bridge the gap between two existing ways of defining certainty of query answers over incomplete data. We have done it by introducing the notion of explanations in semantics of incompleteness, and defining certainty by saying that it is the same explanation that has to account for a possible world and the query answer in it. This way, we justified the most commonly used (although hitherto without proper justification) notion of certainty in the literature.

As the outcome of this work, we believe that the right notions of certainty to use, in the case of relational data, are intersection-based; that is lCWA or lOWA, depending on the semantics of data. Now these notions come with a proper justification. If one is only interested in tuples of constants, the classical definition of �tQpD1 q | D1 P JDK � u is the right notion. The informativeness-based definition is still more general and can capture answers that intersection-based notions would miss, but pragmatically one should use intersectionbased notions due to their computational properties.

In the future, we plan to extend the ideas of this paper in three ways. One extension is to other semantics of incompleteness (e.g., weaker notions of CWA, cf. [Reiter, 1980; Minker, 1982]). Another direction is to look for notions of explanations as they directly arise in applications such as data integration, data exchange, OBDA, and others. Finally, we would like to consider other data models, in particular graph models and RDF, where the study of querying incomplete data (such as blank nodes) and certain answers has recently received attention [Ahmetaj et al., 2015; Gheerbrant and Fontaine, 2014; Hogan et al., 2014; Nikolaou and Koubarakis, 2016].

Acknowledgments

Part of this work was done while the first author was visiting the University of Edinburgh. The first author was supported by MISE under projects PIUCultura and S2BDW, and by the EU Horizon 2020 programme under project MIREL, grant agreement 690974. The second author is supported by EPSRC grants M025268 and N023056. We are grateful to anonymous referees for their comments.