Re: A good book

From: Bob Badour <bbadour_at_pei.sympatico.ca>
Date: Sat, 08 Jul 2006 02:29:01 GMT
Message-ID: <NLErg.7715$pu3.171840@ursa-nb00s0.nbnet.nb.ca>

Marshall wrote:

> Chris Smith wrote:
>

>>Bob Badour <bbadour_at_pei.sympatico.ca> wrote:
>>
>>>Chris Smith wrote:
>>>
>>>>I'm suggesting that you've yet to establish the connection between:
>>>>
>>>>(a) predicate calculus and elegant code
>>>>(b) databases and predicate calculus
>>>
>>>Relational calculus = 1st order predicate calculus
>>>
>>>Am I missing something?
>>
>>No, you're almost certainly not missing something.  Nevertheless, what
>>I'm asking for ought to be relatively simple, so I'll try to explain it
>>another way.
>>
>>As is pointed out here several times every five minutes (okay, not that
>>often...), database design and programming is rather frequently and
>>unfortnuately performed from very little theoretical basis at all.  At
>>the same time, it's frequently stated that relational databases operate
>>on a solid mathematical foundation.  That's a useful statement if and
>>only if that mathematical foundation provides tools that are useful in
>>practice for reasoning about behavior, transformations, correctness,
>>etc. of the code written in relational languages.  If this connection is
>>not made, then all this talk about predicate calculus is pointless.  I
>>am looking for the sources that explain how this connection is made.
>>Are there theorems of relational theory that suggest certain program
>>transformations, or certain criteria for correctness?

>
>
> Relational theory is mostly about data, at least historically. So
> I would change your question to being a question about theorems
> in relational theory about data transformations, rather than
> program transformations.

In fact, one could argue that there is no difference between the two. Using the relational calculus or the relational algebra to derive equivalent access paths for optimization does both.

> The obvious thing to me to mention is the normal forms.
>
> The normal forms describe precisely schema in which
> redundancy is present, and also show what anomalies
> can occur as a result. They also show how it is possible
> to perform a lossless decomposition such that some
> redundancy is removed, eliminating the possibility for
> the update anomalies associated with that particular
> normal form.
>
> In practice I have found that most of the problems
> with databases can be traced to failure to adhere to
> the normal forms.
>
> Without the formal foundation, in particular the theoretical
> understanding of keys, the normal forms would be impossible.
> (Instead we'd have design patterns. :-)

I agree. After Codd's 1970 paper, then comes his paper establishing the equivalence between the algebra and the calculus (and thereby the equivalence between set algebra and predicate calculus). I forget the year of that one. 1971? 1972? It was early 1970's in any case.

After that, Ron Fagin's work on normal forms was perhaps the most notable application of the theory. He used it to prove that fifth normal form was necessary and sufficient to avoid update anomalies using decomposition by project/join.

>>You made a
>>comment in another thread that suggested that features added to
>>relational databases can be traced back to the mathematical model;
>>where's a source that explains how?

>
> In brief:
>
> Every relation has an associated predicate.
> Every element of every table is a proposition.
> Every relational algebra expression is an expression of
> logical inference, deriving new propositions from existing
> ones.

If he is looking for a citable reference source, I would suggest the 1970 paper. Received on Fri Jul 07 2006 - 21:29:01 CDT