Re: Canonical DB

From: Dmitry A. Kazakov <>
Date: Thu, 22 Jun 2006 11:20:29 +0200
Message-ID: <>

On Thu, 22 Jun 2006 01:47:03 +0200, mAsterdam wrote:

> Robert Martin wrote:

>> Things like tree searches, graph walks, etc.

> No, tree searches and graph walks are things
> you *need* to do (and specify) when all you have
> is navigational structures. They are part of their cost.
> Now where is the benefit - what are you computing:
> Which (or which types of) computations are easier
> with a navigational structure?

That's easy. The benefit is in reducing the cardinality of the problem space. Tree, graph and a table, too, can serve as sparse descriptions of some large problem space. Consider a route map. The original space is 3D continuum. You cannot handle it as-is in any finite system. A graph here is just a sparse description, of something, which otherwise might be impossible to compute.

Talking about cases where usage of the "original" relational structure is possible, but computationally inefficient, consider distance mappings. Technically each ordered structure induces some distance. For example, a table with ordered keys induces one between rows d(k1,k2)=k2-k1. A tree structure does it as well, it is so-called tree distance. This induced distance is obviously not the problem space distance. Which might have an immense computational impact. Example: kd-trees vs. relational tables. [Euclidean (any 3D) distance cannot be mapped to *any* linear order. It is a hard fact. So there is no key which could work. This was the thing which killed Prolog in machine learning (nobody would even try RA.)]

Another advantage of graphs and other "non-linear" structures, is that you might do things which would otherwise illegal. For example, self-referential structures. Self-containment is illegal, but a thing which behaves as if it contained itself is possible through indirection. There are many cases where you have to use such models, because other models would be complex/inadequate/illegal. If you want a generalized description, it is the problems where local descriptions are still "good-behaving", linear, but global ones are a nightmare. Graph is locally is almost as good as a table.

Dmitry A. Kazakov
Received on Thu Jun 22 2006 - 11:20:29 CEST

Original text of this message