The Incomplete Database

1 Introduction

The relational database model has in recent years been extended to cope with missing data ([Codd, 1979]). A relation may contain incomplete tuples, because for some objects an attribute is inapplicable (name-of-spouse) or because it is unknown (blood-group). Absent data are un­ problematic from a theoretical point of view (see [Lien, 1979]), and will not be discussed here. The mathematical properties of unknown data, however, are insufficiently known. As a consequence, the treatment of unknown values in relational databases tends to be illogical or un­ natural (see [Date, 1989],[Codd, 1990]). This paper deals with the theoretical foundation of nulls in a relational database.

1.1 Unknown values

Let nulls (w1,w2, ... ) represent the unknown values in a relational database. Indices are used to distinguish between different unknown values and multiple occur­ rences of the same unknown value. These indices will be hidden from the user, but they are essential to preserve basic algebraic laws such as

The main problem with nulls is that they lack iden­ tity criteria: there is no way to decide whether 'w = 5' or rather 'w f. 5', except by revealing w's identity. This means that 'w = 5' is neither true nor false, and thus contradicts the Law of the Excluded Middle. Unfortu­ nately, the relational database model is firmly rooted in classical logic, so the introduction of nulls calls for major changes. The following sequence of equivalent terms, for instance, must be relinquished, since in the presence of nulls the first term is but a part of the last one:

The precise point at which this sequence breaks down will depend on the type of logic that is adopted.

1.2 Choice of logic

Since the relational database model is set in classical logic, attempts have been made to incorporate nulls into classical logic. The simplest solution is to use defaults, reserved values like xxx or 999, l?roviding no system sup­ port of nulls at all ([Date, 1989J). The relational tuples have been extended with additional attributes to encode the level of uncertainty ([Biskup, 1981], [Ola, 1989]). This does not suffice to preserve classical tautologies, such as 'w = 5 V w f. 5', so equations have been inter­ preted through uniform null substitution ([Grant, 1979]) or normal form transformation ([Lipski, 1977], [Vassil­ iou, 1979]). There is no formal justification for the re­ striction of these variants of supervaluation to equational expressions. Moreover, supervaluation leads to an inter­ pretation that is not compositional, so:

In recognition of w = 5's being neither true nor false, there have been proposals that use many-valued logic ([Codd, 1979],[Codd, 1986], [Zaniola, 1984]) or partial logic ([Demolombe et al., 1988]). The missing data create a gap in the truth value assignment, not only for equations but for relational literals as well. Unfor­ tunately, this implies that classical tautologies are no longer valid, in that they have no truth value for tuples with nulls. Since query optimization heavily depends on term rewriting, this will have all sorts of unexpected side-effects:

The third approach, the one I advocate for nulls in a relational database, is to change to modal logic ([Lip­ ski, 1977],[Lipski, 1979], [Lipski, 1981], [Imielinski and Lipski, 1984b], [Levesque, 1984]). Modal logic is a con­ servative extension of classical logic, so all classical laws are preserved, and the correct inequivalence emerges:

A drawback of modal logic is its computational com­ plexity. Nevertheless, it is the only approach that is consistently intuitive and easy to comprehend.

1.3 Choice of paradigm

Under the database-as-theory paradigm (see [Reiter, 1984], [Demolombe et al., 1988]) nulls are Skolem con­ stants and part of the language. This leads to 'extended relational theories' for which the Unique Names Axioms, which specify the identity criteria for constants and nulls, are no longer complete. As a consequence, the query evaluation algorithm is only sometimes complete ([Re­ iter, 1986], [Vardi, 1986], [Demolombe et al., 1988]). This paper adheres to the database-as-model paradigm, but all results can be translated to the database-as­ theory paradigm (see [Vardi, 1986]). The choice between the two paradigms is irrelevant, as is illustrated by De­ molombe & Farinas del Cerro in [1988], where they dis­ cuss the 'extended Herbrand model'. One advantage of the database-as-model approach is that nulls need not be added to the query language, but may remain in the realm of the database implementation.

1.4 Outline of this paper

It is well-known that the meaning of an incomplete rela­ tion is the set of its completions ([Biskup, 1981], [Vardi, 1986]). The main innovation of the present proposal is to use a set of revelations to represent those completions, and to incorporate them explicitly into the interpretation of relational queries (§ 2). Query evaluation will be hard to compute inductively, and is therefore linked to -by way of example- a partial interpretation (§ 3). Working with a modal interpretation ensures that the limitations of using nulls can be established with greater ease and precision (§ 4). The intuitive correctness of employing modal logic to represent unknown values is illustrated in a discussion of database integrity (§ 5 ).

2 A relational model for nulls

After all is said and done, a complete relational database DB is just a set of tables, an instance of a database scheme :E, acceptable if it satisfies some set of constraints X. As such it is a model< V,I >,with V the domain of relevant objects and I the interpretation of relation names as relations over V.

Each constant c E CON will denote a unique object f E V, and each object d E V must have a name. These assumptions are reasonable in a database context; if in addition all objects have different names, as required by the Unique Names Axioms, then the identity = is inter­ pretedas{<d,d> ldEV} = {<f,f> lfECON}.

2.1 Extend the model, not the language

Suppose the database is provided with a finite set of nulls n = {w1, ... , wk}. Then the model contains relations over the extended domain v u n, but the interpretation of= can not be { < d, d > I d E V U n }, since that would make 'w = 5' false instead of unknown. Especially when w ranges over a finite domain, such as days in the week, we cannot pretend that w is different to them ~ll.

There is no need to extend the query language w1th names for nulls. Queries that refer to nulls should be reformulated by means of existential quantification, ad­ dressing the null through its context, a partial tuple in an incomplete relation.

The identifying index is not relevant to external users. Indices are analogous to the surrogates used for tuple identification; they are there for the sake of the system, but the external user cannot address them. In other words, nulls are part of the incomplete relational model, not part of any relational query language.

2.2 Revelations

The ultimate meaning of the null is modeled by a set G of revelations. The term 'revelation' is chosen to indi­ cate that the unknown identity of the nulls is revealed eventually, but we want to reason over the incomplete database without waiting for revelations ( cf symbolic constraint solving, see [Denneheuvel et al., 1991]). Al­ ternative terms would be 'null-assignment' or even 'sub­ stitution', though the latter term sounds more innocent than is justified by its elusive denotation.

A revelation g : n -+ V is a function that assigns a proper value to each null, thus resolving the nulls in the relations, and completing the database: For each g E G and R in DB, g[BJ is a complete relation over V.

Th.; revelations G represent all possible completions of the database. Partial knowledge of the identity of the nulls can be encoded in G's structure. The database in­ tegrity constraints, for instance, may resolve some nulls, and rule others unequal (see § 5 below).

2.3 Truth definition

Queries to the database will be formulated in a Codd­ complete query language, such as the relational algebra. Any query can be translated into first order predicate logic, however, so the truth definition is here recursive over logical connectives and quantifiers, extended -for the sake of the nulls- with the modal operators K for 'it is known that' and M for 'it is conceivable that'.

In the clauses below the assignment h is a standard assignment h E H: VAR-+ V, to resolve free variables. Existential quantification is interpreted by means of x­ cylindrification:

The symbol =x denotes the equality of two assignments on all variables, with the possible exception of x.

Definition 1 incomplete instance

A model< 'Dun, I, G > is an incomplete modal instance of a relational database scheme E iff every n-ary relation name R in E is interpreted by I(R) = R ~ ('V u n)n and every formula t,o by I(t,o) ~ G x H, as follows:

Definition 1 can be explained as follows. The interpre­ tation of formulas is presented in an algebraic manner, to emphasize the connection with the relational algebra. Equivalently, it can be given as a modal truth definition, since the revelations G represent a set of possible worlds W = { w 9 I g E G }, and the incomplete instance repre­ sents a Kripke model, which is of course an appropriate model for unknown values.

Lemma 1 < 'V u n,I, G > =: < 'V,I', W >, in such a way that

• w = { Wg I g E G }
• I'(w 9 )(R) = g[E]
• < 'V,I', w >, Wg F t,o[h] iff < g, h >E I(t,o)

The model < 'V, I', W > is a connected S5 Kripke model, which yields a very simple modal logic.

Nulls are modeled as parameters, and only through the revelations G are they existentially quantified. To describe the incomplete model, one can replace every w by an existentially quantified variable, but '3wt,o' makes no sense, since w is not a variable in the query language.

Given lemma 1 it is easy to see that< g, h > E I(t,o) has the intuitive meaning that the restriction of h to FV( t,o) denotes a tuple for which t,o is true, provided that g is the correct revelation ofunknown values.

Example 1 Let R(ABC) be interpreted as

If the unknown B value happens to bee, then '< e, f >' is a correct answer to the query 'xy such that Rdxy'; f is a solution to the query 'y such that 3x Rdxy' inde­ pendent of the unknown value of the tuple. ·

The correct revelation g is not known, but by adding a modal operator K or M it becomes superfluous.

Example 2 The query 'Is it true that Rdef!' is not very satisfactory answered by the condition 'w 1-+ e', that is 'yes, provided Rdef. The modalized versions do make sense: the query 'Is it known that Rdef!' yields 'No ... ', and 'Is it possible that Rdef!' receives a final 'Yes !'. ·

I(Kt,o) does not depend on g, and the answer to an open query is

and if necessary the dual J*(t,o), the projection ofi(M<p) on H. Unfortunately, it is not possible to compute I. by independent induction, that is, without first computing I.

Example 3 Let R(ABC) be interpreted as before.

I.(Rdxy) = 0 I.(3x Rdxy) = {hE H I h(y) =!} I.(-,Rdxy) ={hE H I h(y) #!}

No tuple xy is known to satisfy Rdxy. Still, it is known that y 1-+ f satisfies 3x Rdxy, and it is known that h satisfies -,Rdxy as long as y fj+ f, regardless of h(x). ·

3 Safe queries

The only drawback of modal logic is its computational complexity. In comparison it is very easy to compute a partial interpretation, namely by a finite induction. Queries t,o on which these interpretations agree will be called safe.

3.1 Partiallogic

A partial interpretation of open queries will either im­ plicitly or explicitly make use of extended assignments H+: VAR-+ 'V u n. The positive answers :J+(IP) are computed by straightforward induction, with an accom­ panying set of negative answers :J_ ( t,o ). This guarantees that all the de Morgan duality laws are validated, so each formula can be transformed into prenex normal form.

Definition 2 partial instance

A model< 'Dun, :1 > is a partial instance of a relational database scheme E iff every n-ary relation name R in E is interpreted by .:1 {R) = 11. ~ (1J U n)n and every formula t,o is interpreted by a pair J+(IP), :J_(<p) ~ H+ , as follows:

The cylindrifications c; and Vt are over the extended domain 1J u n. Inequality is defined over 1J alone, so if h(x) :f h(y), then h(x), h(y) E 1J. Two tuples are inequal, < d1 ..· dn >#< e1 ... en >, if there is at least one place at which they disagree: for some i: d; f:- e;.

3.2 Comparison on H

To compare the modal and the partial interpretations we need to restrict the latter to H, see figure 1. This can be done without loss of expressibility, since any reference to nulls can be avoided by additional quantification.

Both the modal and the partial interpretation cannot be computed on H directly. The intersection of :J+(<p) with H interferes with quantification, but otherwise :1. can itself be computed by induction over the structure of the query. For modal logic, answers are lost in case of disjunction and existential quantification.

Theorem 2 Comparison of the 2 interpretations 1. answers known to be true

:J. ( <p) ~ :J* ( <p)

:1.(-.<p) = H \ :J*(<p)

:J.(<p 1\ t/J) = :J.(<p) n :J.(t/J)

:J.(<p v t/;) = :J.(<p) u :J.(tf;)

:J.(3x <p) 2 Cx(:J.(<p))

:J.(Vx <p) ~ Vx(:J.(<p))

2. answers that may be true

:1*(-.<p) = H \ :J.(<p)

:J* ( <p 1\ t/J) = :J* ( <p) n :J* ( t/J)

:J* ( <p v tP) = :J* ( <p) u :J* ( tP)

:J*(3x <p) 2 Cx(:J*(rp))

:J*(Vx rp) ~ Vx(:J*(<p))

Theorem 2 can be found in several places in the literature ([Lipski, 1977], [Reiter, 1986], [Demolombe et al., 1988]), though the precise details will depend on the details of the particular model. Consider for instance the set of answers (see [Reiter, 1986]) deducible from the database:

The evaluation algorithm proposed is :1+; completeness is guaranteed if I.-inequalities do not arise.

All classes of unproblematic queries suggested in the literature are safe under the present definition.

Definition 3 A formula rp is safe

iff for every partial :1 and modal I: :1. ( rp) = I. ( rp ), provided that :J(R) = I(R) for every relation name R.

3.3 Unsafe queries

Before searching for classes of safe queries, first an ex­ ample of an unsafe query, which is incorrectly answered under the partial interpretation :J ·.

Example 4 Any comparison expression F is safe, but F cannot be safely combined with a relational atom. If R = { < a, b, w >} :

The partial instance as defined here does not make use of the set of revelations G, so any query that depends indirectly on the structure of this G cannot be correctly evaluated. To avoid this unfairness it will be assumed that G is the full set V 0 . The next example shows that, unless some sort of fairness condition is laid on G, even a relational atom may be unsafe.

Example5 LetR = {<a,w1,c>,<a,b,w2>}. Suppose that for all g E G either g(w1) = b or g(w2) =c. Then :J.(Rxbc) = 0 -:f. {x 1--+ a} = I.(Rxbc). ·

3.4 Classes of safe queries

Positive selections in combination with union, join and projection can be evaluated over incomplete relations (see [Imielinski and Lipski, 1984b]). These relational terms correspond roughly with positive queries as de­ fined by Reiter (see below), and with formulas without negation. The translation of positive selections is of the format rp 1\ E, with E an equational expression.

Definition 4 positive

A relational atom is positive.

If rp and tjJ are positive, then 3x rp, Vx rp, rp 1\ E, rp 1\ tjJ, and <p V tjJ, are all positive.

Reiter allows restricted quantification only, to avoid un­ reasonable queries. He defines positive queries accord­ ingly ([Reiter, 1986]):

Definition 5 Reiter's positive

An atomic formula is positive.

If rp and tjJ are positive and Tis a finite type, then <p 1\ tjJ, rp V t/J, 3x E T: <p, and Vx E T: rp, are all po.sitive.

One would like to see that all literals are safe. Since con­ junction and universal quantification are unproblematic, then so are conjunctive queries:

Definition 6 Reiter's conjunctive

A formula rp is conjunctive iff rp is of the format Vx E T : tPl 1\ ... 1\ tPn, where each conjunct t/;; is a lit­ eral, an atom or negated atom.

Demolombe & Farinas del Cerro ((1988]) define a larger set of conjunctive queries.

Definition 7 A formula rp is conjunctive

iff <p is a conjunction of [-.][3 x] t/J, with tjJ a disjunction of atoms and x free in one of the disjuncts.

In order to prove that a negated atom such as -.Rxab is safe, we need to sharpen the basic clause :J_ a little, as can be seen from the following example.

To counter this example it suffices to redefine the notion of tuple inequality:

Definition 8 uniform tuple inequality

< d1 .. . dn >-:f.< e1 .. . en>:=

Vg E V 0 : < g(dl) ... g(dn) >#< g(e1) ... g(en) >

This is a generalization of strong tuple inequality, since di f; ei implies that di , ei E 1J, so for all revelations g(di) f; g(ei).

The change is significant. Apparently we need a little modal information even for a simple literal. It is not much, just the set of all possible revelations 1J 0 , but it is a clear indication that modal logic will become indis­ pensable when queries get more complex.

Once the partial interpretation is adapted in this man­ ner, we can prove that all given sets of queries are safe:

Theorem 3 If r.p is a positive or conjunctive query, then :J.(r.p) = I.(r.p).

The set of semantically safe queries can easily be ex­ tended using modal equivalences, leading to larger syn­ tactic sets of queries (see [Kwast, 1999]).

Definition 9 OK, XDE

OK --+positive I OK 1\ OK I 'v'xOK I ·XDE XDE --+rei. atom I XDE V XDE I 3xXDE I --,QK

Theorem 4 Let r.p be OK, then I.(r.p) = :J.(r.p).

4 Interpretation versus computation

There are two ways to appreciate safety. On the one hand, safe queries are queries for which the modal in­ terpretation gives the intuitive meaning of the partial interpretation. This feeling is strengthened by the fact that the partial interpretation of an unsafe query equals the modal interpretation of a modalized version of the query, as in the following example.

Example 7 Let R = {< a,wu1 >,< b,w111 >}. :1.(3:~: -,Rax) = I.(3x K-,Rax) f; I.(3:c -,Rax). .J.(3:c: (Rax 1\ X= 5) V (Rbx 1\ X "f; 5)) = I.(K(3x Rax 1\ x = 5) V K(3x Rbx 1\ x f; 5)) f; I.(3x (Rax 1\ x = 5) V (Rbx 1\ x f; 5)).

·

As is suggested by the second query, there is, unfor­ tunately, no uniform translation from the one logic to the other. Every partial answer can be expressed by a modalized formula, of course, but it cannot be predicted by which particular formula. It must be concluded that there remains a class of queries for which the partial in­ terpretation is inappropriate. Some answer is computed, but there is no intuitive idea about what it might be.

4.1 Finite domains

Obviously, the definition of a partial model can be changed, for instance by the addition of G into the inter­ pretation of J+ and/or :J_. To be sure, in [Demolombe et al., 1988] the partial induction has access to G to de­ termine the basic clauses.

In this manner the partial interpretation is set on a modal base. This does not suffice to make it modal logic, of course. For one thing, partial logic cannot cope with finite domains:

Example 8 Let 1J = {a, b,c} and R = {< w,c >}. :J.(Rac V Rbc V Rcc) = 0 =f. H = :J.(3xRxc) I.(Rac V Rbc V Rcc) = I.(3xRxc) = H

·

In a database context many nulls will refer to a finite do­ main, such as day-in-the-week or blood-group. A partial interpretation, even when set on a modal base, is not ad­ equate for queries in which finite domains are involved.

4.2 Reasonable queries

If there is no uniform translation from partial logic into modal logic, we may turn in the opposite direction and use partial logic to compute the modal interpreta­ tion. Obviously, this only works for safe and 'reasonable' queries, queries which can be finitely computed if the database is complete. If there is no other simple way to compute the modal interpretation, then that is a good reason to forbid the query. It might be cheaper to try and find out what the missing data should have been by using the telephone or a nationwide poll .

4 .3 Supervaluation

A good example of a computation method for a distinct class of queries is normal form transformation used to evaluate projection-selection queries. Imielinski & Lip­ ski prove in ((1984b] ) that < @-tables, Rep, {II a} > is a representation system. This means that projection­ selection queries can be correctly represented by func­ tions on @-tables, relations with unindexed nulls. In our terminology: PS-queries are safe, on the assumption that all nulls occur uniquely in the tables, to guarantee that two nulls need never be identified. As was shown before (see example 4) , PS-queries are not safe with respect to the partial interpretat ion, but they are safe with respect to supervaluation of the normalized form.

5 Nulls and integrity

The effect of nulls on integrity has not drawn as much attention as the problems of query evaluation. The tra­ ditional definition of a database satisfying its constraints is not adequate (see [Reiter , 1988]). Codd's suggestion ([1979] , [1986]) that nulls should just be ignored, sus­ pending judgement to the time of their revelation, is no solution either. Not every incomplete tuple may be added to the database.

The model for nulls presented here is well suited to describe database integrity.

Definition 10 An incomplete database is acceptable iff there exists an acceptable revelation, that is, one that yields a database that satisfies all its constraints.

This simple definition can be compared to the defini­ tions proposed in literature (see [Reiter, 1988]): It is not enough if the atomic facts plus constraints are satisfiable; they must be satisfied by a completion deriving from a revelation. Still, the atomic facts could never imply the constraints. So definition 10 is a suitable adaptation of the Closed World Assumption.

5.1 What should hold

The set of constraints will divide the set of revelations in two: acceptable and unacceptable revelations. Relative to the former set we define a modal operator X with the intended meaning what should hold, that is, what holds in all acceptable completions.

Definition 11 DB f= X r.p iff 3g E G: g acceptable, and 'v'g E G: g acceptable => DB, g f= r.p.

This definition, being based on Kripke semantics, cap­ tures the interaction of integrity constraints with un­ known values in an intuitive manner (see [Kwast, 1999]).

Example 9 Suppose R(ABCD): A- B, C-D and let J1 ={<a, b,w1, d >, < a,w2,p,q > }.

DB f= XVx : Rabxd :::) x :f:. p

The insertion of the tuple< e, f, w1 , r > into R will make the database unacceptable. ·

5.2 Queries versus constraints

To distinguish formulas that denote constraints, such as R : X - Y, from relational facts and queries, the former will contain a leading X operator:

Queries are practically never formulated with the help of X, or any analogous operator. Evaluated over total relations X is vacuous, of course, but in the presence of nulls the interpretation of a query t.p which does not involve X will contain answers that contradict the rela­ tional dependencies, and it will miss others that should have been there. Unfortunately, it cannot be hoped that integrity considerations are actually employed in answer­ ing queries, on account of the ensuing complexity.

6 Conclusion

The overall conclusion of this paper is that any sound model-theoretic foundation of nulls in a relational database must be based on modal logic. That modal logic is appropriate is obvious, but it is necessary as well, as there is no other way to assess the intuitive correctness of an evaluation method for wide classes of queries.