Re: 'infinity' in GiST index

From: "Dave Held" <dave(dot)held(at)arraysg(dot)com>
To: "Pgsql Hackers" <pgsql-hackers(at)postgresql(dot)org>
Subject: Re: 'infinity' in GiST index
Date: 2005-05-05 14:59:07
Message-ID: 49E94D0CFCD4DB43AFBA928DDD20C8F9026184FF@asg002.asg.local
Views: Raw Message | Whole Thread | Download mbox | Resend email
Thread:
Lists: pgsql-hackers

> -----Original Message-----
> From: Tom Lane [mailto:tgl(at)sss(dot)pgh(dot)pa(dot)us]
> Sent: Wednesday, May 04, 2005 11:17 PM
> To: Oleg Bartunov
> Cc: Pgsql Hackers
> Subject: Re: [HACKERS] 'infinity' in GiST index
>
> [...]
> Seems like it's not really GiST's fault but a definitional problem
> for the timestamp datatype. Specifically, what does it mean to
> subtract two infinite timestamps? I find it hard to assign a
> value to any of these combinations:
> +infinity minus +infinity
> -infinity minus -infinity
> +infinity minus -infinity
> -infinity minus +infinity

That's because you're talking about transfinite arithmetic, and
subtraction is not defined therein. AKA "the arithmetic of
infinite cardinals". I've actually seen a few different
formulations, some of which say that adding a finite number to
an infinity results in a different number than the infinity, and
some that say it is the original infinity. However, it seems
that the most common formulation is the latter:

w + 1 = w

Where w is lower-case omega, or aleph_0. If we allowed subtraction,
then we could subtract w from both sides and end up with 1 = 0,
which would be an inconsistency. Also, -w makes sense when talking
about the reals, but not when talking about transfinite arithmetic.
There are no additive inverses, because that is the same as allowing
subtraction, with the same result. Note that within real arithemtic,
you can't do any math with infinity anyway.

> The first two can't really be identified with zero, and the
> last two are surely not representable are they?

Not unless you change to another math system, which, of course,
wouldn't be appropriate for this application.

> What's worse, a subtraction involving one infinite and one finite
> timestamp *is* well defined from a mathematical point of view, eg
> +infinity minus 'yesterday' = +infinity

Actually not. When doing transfinite arithmetic, you can only
add naturals to infinities. Otherwise, you're getting a form of
subtraction, which will eventually lead to inconsistency.

> but I doubt GiST will be happy if we make the datatype behave
> that way...

I guess it depends on why you want to take the difference. If
you want to take some measure of distance, it might be useful
to say that all infinite values of the same sign are at 0 distance
from each other, in which case you would say that +w - +w = 0.
Probably infinities of opposite signs should just be w apart
(which is also mathematically consistent).

__
David B. Held
Software Engineer/Array Services Group
200 14th Ave. East, Sartell, MN 56377
320.534.3637 320.253.7800 800.752.8129

Responses

Browse pgsql-hackers by date

  From Date Subject
Next Message Marc G. Fournier 2005-05-05 15:05:48 Re: [pgsql-advocacy] Increased company involvement
Previous Message Robert Treat 2005-05-05 14:28:50 Re: [GENERAL] Interesting article on transactional algorithms includes