Re: What is Aggregation? Re: grouping in tuple relational calculus

"Jan Hidders" <jan.hidders_at_REMOVETHIS.pandora.be> wrote in message news:n0OSd.18586$jx1.2312308_at_phobos.telenet-ops.be...
> Dawn M. Wolthuis wrote:
>>
>> I've just started to look into one of the other topics on my list --
>> I'd like to understand what the concern is about non-1NF structures
>> leading to 2nd order predicate logic for queries. I do understand that
>> if it did require such then we get into Godel's theorem territory. I
>> just don't know what exactly drives us there to know why folks bring that
>> up.
>
> Neither do I. In any practical query language you would never allow
> quantification over your whole infinite domain but only over finite
> subsets that are computed by a subquery. So you never can say things like
> "for all x it holds that Q(x)" but always "for all x in Q1 it holds that
> Q2(x)" where Q1 is a subquery. That guarantees that the result is
> computable. Compare this to how numbers are used in the flat relational
> model. Adding these unrestricted and with a little arithmetic to first
> order logic also would take us straight to Goedel territory, but with the
> same trick we are able to use them safely in SQL anyway.
>
>> I'm thinking I should read about monadic second order logic (which is
>> provable). Do you have any idea if monadic 2nd order logic is relevant
>> to the FDM, XML data model, PICK model, or other non-RDM data models?
>
> For FDM I'm not sure, but for the XML data model and pretty much any data
> model that is similar to ordered labeled trees (which, I suspect, includes
> the PICK data model) it's importance is comparable to that of FOL for the
> relational model. It's nearly impossible to find a database theory paper
> on ICDT or PODS that deals with such data models and does not mention MSO
> somewhere.

OK, I've got some acronyms to search for now ;-)

> To give a small example, it is well known that specialized DTDs (a clean
> formal version of XML Schema) are equivalent with MSO. This means that if
> you can describe in MSO what your documents look like, then there is a
> specialized DTD that exactly allows those documents, and vice versa.

Would you recommend use of .dtd instead of .xsd files for schema definition? It seems xml schema files have become the standard, haven't they. You indicate that you think dtds are cleaner -- in what way is that the case? I'm beginning to think that you know everything that I want to know on the subject of data models -- sorry for continuing the questions, but your answers are very helpful. cheers! --dawn

> -- Jan Hidders
Received on Wed Feb 23 2005 - 02:04:39 CET