Re: Box query

From: Isaac Blank <izblank_removethis__at_yahoo.com>
Date: Fri, 28 Apr 2006 19:17:41 GMT
Message-ID: <pTt4g.21584$tN3.462_at_newssvr27.news.prodigy.net>

"Mikito Harakiri" <mikharakiri_nospaum_at_yahoo.com> wrote in message news:1145671131.059290.281130_at_i40g2000cwc.googlegroups.com...

> 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!
>

Actualy, it is a version of the 2-level nesting subquery solution - only the innermost subquery is replaced with a check for non-overlap Received on Fri Apr 28 2006 - 21:17:41 CEST