Re: The IDS, the EDS and the DBMS

From: Jan Hidders <jan.hidders_at_REMOVETHIS.pandora.be>
Date: Tue, 14 Sep 2004 21:07:20 GMT
Message-Id: <pan.2004.09.14.21.10.13.654821@REMOVETHIS.pandora.be>

On Tue, 14 Sep 2004 13:29:11 -0700, Mikito Harakiri wrote:

> "Paul" <paul_at_test.com> wrote in message
> news:414745d8$0$13400$ed2e19e4_at_ptn-nntp-reader04.plus.net...

>> Mikito Harakiri wrote:
>> >>But irrationals, or even the subset of them that is the nth roots of
>> >>integers, don't have such a canonical form - for example consider
>> >>sqrt(2) + sqrt(3). So after a few simple addition or multiplication
>> >>operations the representation will rapidly get very unwieldy.
>> >
>> > When adding integers the representation grows as well, so there is
>> > really no difference.
>>
>> Well if I add two integers the result is usually not much bigger in
>> terms of space e.g.
>> 28594564654655 + 56467986465464
>>
>> but if I add two "surds" I get an expression that takes up at least
>> twice as much space e.g. sqrt(2) + sqrt(3). Also there could be
>> complicated ways to simplify the expressions which would be
>> computationally expensive compared to integers.
>
> The complexity of finite object can't be specified in absolute terms.

Indeed, but you could reformulate the problem a bit such that there is an input with a certain size. For example for the addition x + y over integers you know that the size of the result can be represented in O(max(|x|,|y|)). But for the multiplication x * y this is O(|x|+|y|). Quite interestingly if you consider the operations over unnormalized formulas (so no normalization at all and x + y is straightforwardly represented as "(" x "+" y ")") then for both operations you also have an upperbound of O(|x|+|y|). So in terms of space the addition becomes just as unwieldy as the multiplication already was. :-)

The question about the complexity of normalization is also interesting. From Tarksi we know that the reals are axiomatisable and you can represent these numbers by sets of simple equations. That's probably already been researched by somebody in the context of constraint databases and/or spatial databases.

• Jan Hidders

Received on Tue Sep 14 2004 - 16:07:20 CDT