Re: Box query

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! Received on Sat Apr 22 2006 - 03:58:51 CEST