# A different definition of MINUS, Part 2

From: paul c <toledobythesea_at_oohay.ac>
Date: Tue, 16 Dec 2008 09:51:56 -0800

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. Received on Tue Dec 16 2008 - 18:51:56 CET

Original text of this message