A different definition of MINUS, Part 2 -
12-16-2008
, 11:51 AM
Part Two
In Part One, I took the Tutorial D MINUS definition, substituted names
that seem a little more evocative to me, then removed the "same heading"
proviso, then made the headings explicit, then made some precedence and
associativity assumptions for readability purposes only, then assumed
that R = A <AND> B, then showed (I hope) that an algebraic
interpretation of the equation R' = R <AND> <NOT> D implies:
R' = R{HA} <AND> R <AND> D <AND> <NOT> (D <AND> D{S#})
and
R'{S#} <AND> R'{HR} = R{HA} <AND> R <AND> D <AND> <NOT> (D <AND> D{S#})
In hindsight, the last paragraph in Part One seems a little murky to me,
so let me postpone talking about a different definition to a 'Part
Three' and in this Part Two, try to clarify that last paragraph of Part One.
The above are two of many possible equations that are implied by the
MINUS definition. Perhaps there are simpler ones that I haven't thought
of that make the same point, but part of my point is that ALL of those
equations are implied by the definition, they are all true by definition
and any term x in any of them always has the same value v in all off
them. For example, R'{S#} has the same value in all possible equations.
Because the last operator applied to form both sides in these first
two equations is <AND>, any S# triple that appears in D will not appear
in the complement <NOT> (D <AND> D{S#}) and so it will not appear in R'
in the first equation above and so it will not appear in R'{HR} in the
second equation and so it will not appear in R'{S#} and so it will not
appear in ANY R'{S#} in ANY equation.
So far so good, that seems to be what I would expect, however the MINUS
definition also implies this third equation:
R'{P#} <AND> R'{HR} = R{HA} <AND> R <AND> D <AND> <NOT> (D <AND> D{P#})
('P#' replaces 'S#' from the second definition)
Regarding a possible P# triple, just as for the S# triple, if that P#
triple appears in D, it will not appear in R'{P#} in any equation. If
HR includes both S# and P#, the left-hand side of this third equation
could also be re-written giving another LHS in a fourth equation:
LHS =
R'{P#} <AND> R'{HR} =
R'{S#} <AND> R'{P#} <AND> R'{S#, P#} <AND> R'{HR}
The 'LHS' of this fourth equation is now mentioning several overlapping
projections of R'{HR}. By the second and third equations, we know that
R'{S#} omits any S# triple in D, similarly for a P# triple and R'{P#}.
Therefore, in the fourth equation, R'{S#, P#} omits both triples and so
must R'{HR}. In other words, if the value of any term in any equation
omits this triple, so does the value of that omit it in any other equation.
If the triples <S# S# 'S1'> and <P# P# 'P1'> are in D, the former won't
be in R'{S#} and the latter won't be in R'{P#} so neither will be in
R'{S#,P#}. If the original value of R includes a tuple containing the
triples <S# S# 'S2'> and <P# P# 'P1'>, the triple <P#, P#,'P1'> won't
appear in the value of any possible left-hand side equation term,
notably R'{S#, P#} and because R'{S#} is by definition a projection of
R'{S#,P#} on S#, so the triple <S# S# 'S2'> won't appear in R'{S#}.
This result is possible even if D does not mention such a triple <S# S#
'S2'>, in other words, the result of Tutorial D MINUS could omit a
triple that is not mentioned in a WHERE clause. Unless some adjustment
is made, I think this would cause a naive implementation to violate the
Assignment Principle. I believe the adjustment Tutorial D makes is to
forbid such a case in the language implementation, ie., in the dbms
implementation. However, I think such a dbms cannot support relational
closure. If what I've written so far is coherent, then I think
something has to give. Rather than adjust these two principles, I want
to see if I can adjust the MINUS definition. I'll leave that to Part
Three but I want to take my time just in case somebody can point out a
big error in the steps I've taken so far. |