Re: Range Types, discrete and/or continuous

From: David Fetter <david(at)fetter(dot)org>
To: Tom Lane <tgl(at)sss(dot)pgh(dot)pa(dot)us>
Cc: Jeff Davis <pgsql(at)j-davis(dot)com>, pgsql-hackers(at)postgresql(dot)org
Subject: Re: Range Types, discrete and/or continuous
Date: 2010-10-25 06:53:22
Message-ID: 20101025065322.GN1132@fetter.org
Views: Raw Message | Whole Thread | Download mbox | Resend email
Thread:
Lists: pgsql-hackers

On Sun, Oct 24, 2010 at 06:59:34PM -0400, Tom Lane wrote:
> Jeff Davis <pgsql(at)j-davis(dot)com> writes:
> > Last development cycle, one of the questions that was unresolved
> > was whether to handle ranges like a discrete set (that is, [1,5) =
> > [1,4] ) or continuous or both.
>
> Put me in the camp that says you need both. I really seriously
> dislike the idea of representing [1, 2) as [1, 2-epsilon], mainly
> because there is often no portable value for epsilon.
> Dump-and-restore would be quite hazardous.

It wouldn't be stored as (1, 2-epsilon). It would be stored more like
(1, 2, closed, open).

> > If we treat those as discrete, then R1 = R2, R1 contains R2, R2 contains
> > R1, and R2 - R1 = R1 - R2 = empty. However, if we treat those as
> > continuous, then we get a contradiction:
> > R2 contains R1
> > R1 does not contain R2
> > R2 - R1 = ( 2009-01-01 01:00:10, 2009-01-01 01:00:10.000001 ) = empty?
>
> This is a circular argument: your conclusion that there's a
> contradiction in the concept of continuous ranges depends on the
> assumption that the datatype is discrete; and with such an
> assumption *of course* you can get a contradiction.

There's a reason all the temporal database theory is done with
discrete time, even though physics, etc., have been known to model
time as continuous.

If you have a coherent, worked-out theory of continuous ranges, please
feel free to develop and publish it just as Snodgrass, et al., have
done with discrete ranges, but please *don't* feel free to assume that
you can just wave a magic wand and make continuous time ranges "just
work" because it pleases you aesthetically.

The burden of proof of that would be on you to show that the theory so
far developed extends into continuous ranges, then back into floating
point.

You would need to start with the first part. I don't think it's fair
to make the project however long it takes you to explore this,
especially if it turns out that continuous ranges *don't* work in some
way that's congruent with discrete ranges.

> But the real problem is that if the user wants to think in terms of
> continuous ranges, the only way that he can convert those to
> discrete ranges is to assume an epsilon for the datatype, and he
> shouldn't be forced to do that; not even if the datatype does have a
> well-defined epsilon at the implementation level, which several of
> ours don't.

They're all well defined, but not uniform. This is true even in the
case of integer timestamps. We don't actually have a real "real"
type, despite the fact that "real" is synonymous with some kind of
floating point thingy.

Let's start with discrete range types, and if it ever turns out that
we actually want some kind of model of continuous range types, we can
do the basic research that would involve, etc., later.

Cheers,
David.
--
David Fetter <david(at)fetter(dot)org> http://fetter.org/
Phone: +1 415 235 3778 AIM: dfetter666 Yahoo!: dfetter
Skype: davidfetter XMPP: david(dot)fetter(at)gmail(dot)com
iCal: webcal://www.tripit.com/feed/ical/people/david74/tripit.ics

Remember to vote!
Consider donating to Postgres: http://www.postgresql.org/about/donate

In response to

Responses

Browse pgsql-hackers by date

  From Date Subject
Next Message Gnanakumar 2010-10-25 07:36:30 pg_ctl: server does not shut down
Previous Message Robert Haas 2010-10-25 03:49:49 Re: knngist - 0.8