Oracle FAQ Your Portal to the Oracle Knowledge Grid
 HOME | ASK QUESTION | ADD INFO | SEARCH | E-MAIL US

Home -> Community -> Usenet -> comp.databases.theory -> Re: Canonical DB

# Re: Canonical DB

From: Dmitry A. Kazakov <mailbox_at_dmitry-kazakov.de>
Date: Sat, 24 Jun 2006 10:59:44 +0200
Message-ID: <1xfv2bo493b8d.1e6zcglw36ulm.dlg@40tude.net>

On Sat, 24 Jun 2006 00:18:31 +0200, mAsterdam wrote:

> Dmitry A. Kazakov wrote:

```>> mAsterdam wrote:
>>
>> Imagine that the tuple is (X,Y) where X are streets and Y are avenues. Your
>> problem space has Manhattan distance. Linear sorting this table
>> fundamentally cannot help you to get out of O(n) pitfall, because whatever
>> order on the tuples you define it will not be a distance in 2D. The fact
>> that (X,Y) are indeed facts (no pun), does not help us here.
```

>
> Checking if I am understanding you:
>
> We have two tuples,
> T1(X1, Y1) and T2(X2, Y2), and
> md(T1, T2) defined as |X1 - X2| + |Y1 - Y2|
> Sorting will not help reducing the
> complexity of the md computation.

Complexity of operations defined in terms of md() [spatial operations]. The most obvious is the nearest neighbour search: for a given tuple T find a tuple T* for which md(T,T*) reaches the minimum on the table. (If T is unknown in advance, no linear sort of tuples can help). A more nasty thing is: find all tuples {Ti} for which md(T,Ti) < D.

```>> To express the meta-ideas behind relational and what
>>  some RM guys call "ad-hoc b**t."

>
>                               it-bucke ?   Nah. No clue :-)
(:-))

>>>ISTM local vs. global is within the navigational realm, so
>>>inappropriate for comparisons of computations with navigational
>>>vs. relational structures.
>>
>> I didn't meant scopes of variables. Though they are a case. I meant global
>> in a more general context: scope, effect, visibility.
```

>
> Ah, I see.
```--