Re: Box query
From: Bob Badour <bbadour_at_pei.sympatico.ca>
Date: Sat, 22 Apr 2006 02:30:03 GMT
Message-ID: <Lyg2g.64016$VV4.1199224_at_ursa-nb00s0.nbnet.nb.ca>
>>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!
Date: Sat, 22 Apr 2006 02:30:03 GMT
Message-ID: <Lyg2g.64016$VV4.1199224_at_ursa-nb00s0.nbnet.nb.ca>
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 Sat Apr 22 2006 - 04:30:03 CEST