Re: Canonical DB

From: Dmitry A. Kazakov <>
Date: Sat, 24 Jun 2006 10:59:44 +0200
Message-ID: <>

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.
> How about general/specialized?

Well, yes, but it is different. General rather refers to a class of problems, handled in some general way. Global does to uniformity of the given problem. Though it is based on some generalization made before: "all data are tuples" or "Foo is defined on all instances of the class."

Dmitry A. Kazakov
Received on Sat Jun 24 2006 - 10:59:44 CEST

Original text of this message