Re: Newbie question about db normalization theory: redundant keys OK?

"David Portas" <REMOVE_BEFORE_REPLYING_dportas_at_acm.org> wrote in message news:Vo-dnU2P5eRW3vXanZ2dnUVZ8tChnZ2d_at_giganews.com...
> "Brian Selzer" <brian_at_selzer-software.com> wrote in message
> news:0rm9j.24872$4V6.3317_at_newssvr14.news.prodigy.net...
>>
>>
>> Isn't it true that with FOL, there must be separate interpretations for
>> tuple A and tuple B, since they belong to different database values,
>> whereas with modal or temporal logic, the same interpretation can apply
>> to both?
>
> I don't know enough about modal logic to comment on that part. I don't see
> how you conclude that for FOL there MUST be separate interpretations just
> because the values have different valid times. It seems like there are
> temporal database models and even logic programming that don't require
> anything like modal logic to produce useful results.
>

I believe one of the logicians out there can answer better than I, but the way I understand it, an interpretation is an assignment. For modal logic, an interpretation assigns meaning to every symbol that appears in any possible world, and then one of those possible worlds is determined to be the actual world. As a consequence, no matter how often a symbol appears in however many possible worlds, the interpretation involves a single assignment. First order logic doesn't deal with possibility and necessity, so as far as I know, the possible worlds interpretation doesn't apply. That's why you need separate FOL interpretations for database values that occur at different times: each distinct database value necessarily involves a separate assignment. How, for example, can you assign meaning for something that doesn't exist? If Baby Mike will be born on Halloween, 2008, then how can you use the same interpretation for a database today as a database on Christmas, 2008? With modal logic, the possibility that Baby Mike will be born can be represented, and therefore meaning can be assigned to the symbol for Baby Mike.

>>
>> That assumes that relational assignment is primitive. I would argue that
>> insert, update and delete are the primitive operations, and that
>> assignment is a shorthand for a combination of the primitives delete and
>> insert. Information is lost when an update is translated into an
>> assignment, but not so the reverse: an assignment can always be
>> translated into a delete and an insert.
>>
>
> I think it is self-evident that assignment can preserve exactly as much
> information as the user requires it to. If the information in question can
> be represented as values within relations then, ipso facto, a relational
> assignment is sufficient. Any form of DELETE or INSERT operator therefore
> doesn't add any expressive power. At best it would be a syntax shortcut of
> some kind.
>

You're right about DELETE and INSERT, but not about UPDATE. If you look at UPDATE in TTM (pps. 112-113), you can see what happens:

UPDATE r ( Ai := X, Aj := Y)

where i <> j is supposedly equivalent to

( ( EXTEND r ADD ( X AS Bi, Y AS Bj ) ) { ALL BUT Ai, Aj } )

    RENAME ( Bi AS Bk, Bj AS Aj, Bk AS Ai )

where Bi, Bj, and Bk are arbitrary distinct attribute names that do not appear in r.

Now if you look at the result of

EXTEND r ADD ( X AS Bi, Y AS Bj ),

you'll notice that each tuple has both the old values and the new values for each affected attribute. Clearly if Ai or Aj is prime, then that information that ties each tuple in the result to its corresponding tuple in r is projected away by "{ ALL BUT Ai, Aj }". Information is lost. The result may be the same, but how that result was arrived at is lost in translation, and therefore cannot be verified.

> --
> David Portas
>
>
Received on Wed Dec 19 2007 - 06:34:57 CET