# Re: NULLs: theoretical problems?

From: Brian Selzer <brian_at_selzer-software.com>
Date: Fri, 10 Aug 2007 11:47:20 GMT
Message-ID: <cfYui.44898\$Um6.30686_at_newssvr12.news.prodigy.net>

"David Portas" <REMOVE_BEFORE_REPLYING_dportas_at_acm.org> wrote in message news:NM-dncYFOuhqBybb4p2dnAA_at_giganews.com...
> "paul c" <toledobythesea_at_oohay.ac> wrote in message
> news:JXLui.45171\$rX4.26997_at_pd7urf2no...
>>
>> (even though I'm not sure in "s{X} = t{X} implies s{Y} = t{Y}" whether
>> "implies" stands for logical implication.)
>>
>
>
> Good catch. It seems that logical implication is not well defined for
> three-value logic. According to Lex de Haan and Toon Koppelaars' recent
> book:
>
> P | Q | P->Q
> --------------
> T | U | U
> F | U | T
> U | T | T
> U | F | U
> U | U | U or T?
>
> So possibly I have to modify what I said about no attribute with nulls
> satsifying any FD. Although some dependencies may be satisfied it won't be
> enough for 2NF or anything higher because {K}->{N} is never true where K
> is
> a key and N is an attribute which has nulls.

I would say instead that {K} --> {N} is indeterminate when N is an attribute that allows nulls, because just in case every tuple has a value for N, {K} --> {N} holds.

If a schema is in 5NF whenever every applicable value is present, then null can have one and only one interpretation: an applicable value is not present. What you have then is an incomplete relation: an irregular set of tuples. For example, a predicate P(a, b, c) for a relation R{A, B, C} where A is the key is equivalent to:

(a in dom(A)) /\ (b in dom(B)) /\ (c in dom(C)) /\ p

where p is a conjunction of the constraints for R.

Suppose that dom(C) = {1, 2, 3}, then an incomplete tuple,

{a = 15, b = 23} represents something like

(a = 15) /\ (b = 23) /\ (((c = 1) /\ ~(c = 2) /\ ~(c = 3)) \/

```                                   (~(c = 1) /\ (c = 2) /\ ~(c = 3)) \/
(~(c = 1) /\ ~(c = 2) /\ (c = 3))) /\ p

```

Note that c in dom(C) is equivalent to

```    ((c = 1) /\ ~(c = 2) /\ ~(c = 3)) \/
(~(c = 1) /\ (c = 2) /\ ~(c = 3)) \/
(~(c = 1) /\ ~(c = 2) /\ (c = 3)).

```

I would argue, therefore, that the FD A --> C holds, even if C allows nulls. Can't an FD X --> Y be expressed this way:

exists x exists! y (x in dom(X)) /\ (y in dom(Y))

where exists! is a quantifier that means "there is one and only one?" And doesn't

```    ((c = 1) /\ ~(c = 2) /\ ~(c = 3)) \/
(~(c = 1) /\ (c = 2) /\ ~(c = 3)) \/
(~(c = 1) /\ ~(c = 2) /\ (c = 3))
```

mean that C has at most one value?

>
> The fact that attributes with nulls don't satisfy join dependencies
> remains very solid and much more obvious.
>
> --
> David Portas
>
>
>
Received on Fri Aug 10 2007 - 13:47:20 CEST

Original text of this message