dbTalk Databases Forums  

A different definition of MINUS, Part 2

comp.databases.theory comp.databases.theory


Discuss A different definition of MINUS, Part 2 in the comp.databases.theory forum.



Reply
 
Thread Tools Display Modes
  #1  
Old   
paul c
 
Posts: n/a

Default 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.


Reply With Quote
Reply




Thread Tools
Display Modes

Posting Rules
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts

vB code is On
Smilies are On
[IMG] code is On
HTML code is Off



Powered by vBulletin Version 3.5.3
Copyright ©2000 - 2013, Jelsoft Enterprises Ltd.