Path: utzoo!attcan!uunet!wuarchive!zaphod.mps.ohio-state.edu!unix.cis.pitt.edu!dsinc!netnews.upenn.edu!grad2.cis.upenn.edu!aaron
From: aaron@grad2.cis.upenn.edu (Aaron Watters)
Newsgroups: comp.databases
Subject: nulls (RE: outerjoin)
Message-ID: <30481@netnews.upenn.edu>
Date: 3 Oct 90 13:32:56 GMT
Sender: news@netnews.upenn.edu
Reply-To: aaron@grad2.cis.upenn.edu.UUCP (Aaron Watters)
Organization: University of Pennsylvania
Lines: 41

David Masterson	writes:

:You seem to have been making the assumption that definitiveness and maybeness
:are distinct sets.  I contend that maybeness is a superset of definitiveness.
:What does that do to the NP-complete problem (I never really understood NP
:terminology). 

Well, technically you are right, but to really get this you have to
replace each maybe-tuple with a null value with a set of tuples where
the null is replaced with `all possible values' which it might
represent.  If you don't do this the two sets won't look like
superset/subset respectively.

The point I think you missed is that
I argue that the two sets must be kept separate and that the user
should be given two answers to any given query (unless s/he specified
s/he only wants maybe=not-known-not-true or definite=known-true).
To really handle this sort of thing in full generality is not a matter
of adding a feature or two to what are commonly called relational
systems -- it is in fact a complete rewrite (or a very elaborate
macro-substitution discipline).

Let's have some fun.  Suppose I have a relation R[Name] which
I know nothing about -- its definite set is empty and its maybe
set contains only the tuple [NULL].  I also have another relation
S[Name] containing exactly [John] and [Mary] (ie, its maybe set
is equal to its true set, both containing [John] and [Mary] only).
What are the maybe and definite sets for the following relational
algebra operations?
	R intersect S, R union S, R - S, S - R?
if anyone wants to know I'll provide answers and argue for their
correctness.  More advanced for 
maybeR[Name,Age]  defR[Name,Age]  maybeS[Name,Age] defS[Name,Age]
      [Mary, 23]      [Mary,NULL]       [Mary, 23]     [Mary, 23]
      [Mary, 41]      [NULL,  23]       [Pete,NULL]    [John,NULL]
      [John, NULL]    [John,NULL]       [Null, 41]
This last one contains some trickiness, but not much.  -aaron.

[PS: NP-hardness result I mentioned earlier (incorrectly saying
`NP-completeness') is derivable from a simple 3-colorability reduction
-- based on a proof by Imielinski.]