Thread: left and overleft/notright revisited: why !>> and !<< might be poor names

Just thought of this, in reference to earlier discussion about replacing
&< and &> with !<< and !>> to correct the problem w/ rtree search
strategy "replacement" at the node level.

It's possibly nit-picking but I'm that way.

Again, using 1D definitions here.

S << T can be (and I would expect, usually is) defined as "for all x in
S and y in T, x < y" or the equivalent thereof (not exist x in s, y in T
s.t. x>=y, etc).

S !>> T could be defined in at least two ways:

As logical union of << and && cases: S !>> T iff S << T or S && T
As negation of >>: S !>> T iff not (S >> T)

which looked fine, until today when I thought of this.

Consider the empty interval (n,n) (any empty interval will do, they're
all the same empty set), and any nonempty interval (and thus set) S.
For convenience I'll refer to (n,n) in its set form, {}.

Perhaps not so obviously, any of the following are true for all such S:
{} << S, S << {}, {} << {}, and conversely for >>.  This holds true for
all positional "less than" and "greater than" operations I've ever seen
defined over sets (of "ordinary numbers" if you'll pardon that).

Now, if "!>>" (the replacement for overleft) is defined in the first
way, union of << and &&, then {} !>> S is true.  On the other hand, if
"!>>" is defined in the second way, {} !>> S is false.  Hmmm.

Observations:

1. This may be irrelevant.  I don't know what the impact of attempting
to index an empty open interval (or for that matter a singleton closed
interval) in an r-tree would be, but I imagine there might be problems
finding any such interval using any of the strategy operators (except
maybe ~=).  (I'd also imagine whatever type was using the rtree would
need to pick "an" empty interval to represent all of them, but that's
another can of worms).  Whether immediately relevant or not, I feel the
usual definition for the operator should be clear, at least in comments.

2. The whole point of the operator replacement at the node level, you're
testing a box which contains some target T, rather than (in this case)
lying to the left of T.  Thus, the "left or overlap" definition for !>>
seems appropriate, which would mean that !>> really isn't the negation
of >>.

Proposal:

any of:

1. Keep !>> and !<< as "good enough", document (somewhere) that they are
properly defined as "<< or &&" and ">> or &&" respectively, and thus
aren't equivalent to !S>>T and !S<<T resp. where empty open intervals
are concerned;

2. Change the operator names to be more consistent with the definition;

3. Change the definition to !S>>T and !S<<T resp. and comment that empty
open intervals are non-indexable,

or

4. Do nothing, and assume anyone creating a data type that supports open
intervals, and then inserting an empty open interval into an r-tree
index, deserves whatever they get. :)


Thoughts?

-- Bill

Tom Lane wrote:
> William White <bwhite@frognet.net> writes:
>
>>Consider the empty interval (n,n) (any empty interval will do, they're
>>all the same empty set),
>
>
> I don't think that's the case.  [0,0) and [1,1) are certainly
> distinguishable given the normal machine representation of intervals.

Every definition of an interval I've seen defines it in terms of a set.

For example, the interval (a,b) in R is the set {x : x > a and x < b}.
Thus, the empty set does not have a unique representation as an interval
in R, just as the nondirected line segments ((0,0),(1,1)) and
((1,1),(0,0)) are identical regardless of the fact that the
representations are not.

Incidentally, my attempts to construct valid operators which *do* treat
various open empty intervals as distinct led to some rather peculiar
(usually inconsistent) results, especially when operating upon empty
open intervals whose endpoints were identical (e.g., (a,a] and (a,a]).

> If you use a mathematical model that says they're not distinguishable,
> that says to me that you chose the wrong model --- especially when the
> model leads you into logical difficulties that need not (and do not)
> exist in the actual implementation.

Do you have an alternative to suggest, given the requirements that the
operators return the expected results on nonempty intervals, and the
usual logic applies (e.g., S @ T and S ~ T ==> S ~= T)


Thanks,

-- Bill

William White <bwhite@frognet.net> writes:
> Consider the empty interval (n,n) (any empty interval will do, they're
> all the same empty set),

I don't think that's the case.  [0,0) and [1,1) are certainly
distinguishable given the normal machine representation of intervals.
If you use a mathematical model that says they're not distinguishable,
that says to me that you chose the wrong model --- especially when the
model leads you into logical difficulties that need not (and do not)
exist in the actual implementation.

My feeling about it is [0,0) << [1,1) but not vice versa.

            regards, tom lane