aaron@grad2.cis.upenn.edu (Aaron Watters) (10/03/90)
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.]