Re: Box query

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

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)

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 Sat Apr 22 2006 - 02:57:45 CEST