Mikito Harakiri wrote:
> 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":-)
I was headed in the direction of a having clause and took a right turn
at Albuquerque.
Received on Fri Apr 21 2006 - 21:30:03 CDT
