Re: Box query

From: Bob Badour <bbadour_at_pei.sympatico.ca>
Date: Sat, 22 Apr 2006 00:57:45 GMT
Message-ID: <dcf2g.63962$VV4.1197081@ursa-nb00s0.nbnet.nb.ca>

Mikito Harakiri wrote:

> Mikito Harakiri wrote:
>

>>Given a set of n-dimensional boxes
>>
>>table boxes (
>>    dimension# integer,
>>    low   integer,
>>    high  integer
>>)
>>
>>find all the pairs that intersect...

>
>
> And those pairs supposed to be what? Right, box ids:
>
> 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
;

Yes, there is something special about this query. Assume some queries are not special. We can then divide all queries into two sets: special queries and nonspecial queries. Membership in the latter set would be a special property of those queries leading to a contradiction. Therefore, all queries are special.

Other reasons are: it depends heavily on inequality, negation and the existential quantifier. Received on Fri Apr 21 2006 - 19:57:45 CDT