Re: By The Dawn's Normal Light

Laconic2 wrote:

>> The motivating factor behind the development of relational database
>>  theory was first order predicate logic. It just so happened that 
>> the mathematical relation is a useful structure to model 
>> predicates.

OK, I mean it at a slightly lower level than that. Once you've established that you need to manage data, you could either jump straight in to sticking it into some kind of tabular structure, or you could take a step back and first of all represent it as logical propositions. These propositions can be grouped together into sets that follow the same predicate "pattern". Only once you've got past that stage so you think about representing them as mathematical relations.

>> The difference is down to first/second order logic I think. The 
>> fact that DBMS relations see their values as atomic is because: a) 
>> the relations specifically represent logical predicates, and b) the
>>  system is constrained to first-order logic only.

I don't think so. I'm not that up on this though so maybe someone can correct me if I'm wrong. Possibly some of their stuff on tuple and relation types does blur the boundary slightly between the relational engine and the type engine. But I think basically their relational model is very similar to Codd's original one.

>> In maths, the relation is more abstract. It doesn't represent 
>> anything, it just *is*. So looking "inside" a value doesn't matter 
>> because we're no longer talking about first-order logical 
>> predicates.

Yes, I guess that's my point - for databases we're applying relations to the specific practical problem of storing logical propositions. Which give them some added properties to pure abstract relations.

>> So it's not the fact that database tables are mathematical 
>> relations that forces the values in the tuples to be atomic, it's 
>> the fact that those tuples represent first-order logical predicates

Note that I'm not an expert so bear with me!

This is the definition from Wikipedia:
http://en.wikipedia.org/wiki/Second_order_logic

"In mathematical logic, second-order logic differs from first-order logic in that it allows quantification over subsets of a domain, or functions from the domain into itself, rather than only over individual members of the domain."

So suppose you have a set R:

By "quantification over x" (where x is a variable representing members of the set R) it means something like saying "for all members x of R, such-and-such is true". This is fine in first-order logic.

But if you want to say something like: "For all subsets of R, such-and-such is true", you can't unless you go to second-order logic.

Here's a definition from a more philosophical,rather than mathematical, point of view:
http://www.earlham.edu/~peters/courses/log/terms3.htm

'When the subject of the sentence is an individual object (like Socrates in "Socrates is mortal"), then we are using first order logic. When the subject is another predicate (like being mortal in "Being mortal is tragic"), then we are using second order logic or higher order logic.'

How this relates to relational databases?

Well I think that the set R above must be infinite for the above to make sense, and databases are finite, which is where I'm a bit unsure. But database relations are unbounded, so I think that's where it's relevant.

For example, consider the standard employee hierarchy example using the adjacency list method (i.e. X is the immediate boss of Y). The only way you can tell if someone is the (maybe not immediate) boss of someone else is to join the relation to itself an unbounded number of times. Which is kind of equivalent to quantifying over all subsets of the relation.

Please jump in if someone else has a clearer definition or a better concrete database example of the relevancy.

Paul. Received on Fri Oct 29 2004 - 15:40:13 CEST