Re: Box query
Date: 21 Apr 2006 19:04:26 -0700
Message-ID: <1145671466.386925.321640_at_j33g2000cwa.googlegroups.com>
Mikito Harakiri wrote:
> Bob Badour wrote:
> > Mikito Harakiri wrote:
> >
> > > Mikito Harakiri wrote:
> > >
> > >>Given a set of n-dimensional boxes
> > >>find all the pairs that intersect...
> > >
> > > table boxes (
> > > *id* integer,
> > > dimension# integer,
> > > low integer,
> > > high integer
> > > )
> > >
> >
> > select b1.id as box1, b2.id as box2
> > from boxes b1, boxes b2
> > where b1.id < b2.id
> > and not exists (
> > select 1 from boxes b3, boxes b4
> > where b3.id = b1.id
> > and b4.id = b2.id
> > and b4.dimension# = b3.dimension#
> > and (b4.high < b3.low or b4.low > b3.high)
> > )
> > group by 1, 2
> > ;
>
> This is quite surprising answer. I didn't believe it first, and tried
> to find counterexample without actually trying to figure out what your
> query is doing! The reason why it looks surprising is the following.
> The query is a set intersection join kind of query which is
> generalization of relational division. Now, relational division
> expressed in SQL is either query with 2 levels nesting subqueries, or 1
> level nested subqueries with minus operator, or the query with counting
> subquery in the having clause. Your query is neither of those!
To add more, there is a next question that I was going to ask: "find the intersection volume". And your query even have the correct "group by" clause in place. I'm really puzzled if you already knew the answer, or put "group by" incidentally instead of "distinct":-) Received on Sat Apr 22 2006 - 04:04:26 CEST