Re: Relational Model and Search Engines?

In message <dfKlc.39446$Y%6.5362560_at_wards.force9.net>, Paul <paul_at_test.com> writes
>Leandro Guimarães Faria Corsetti Dutra wrote:
>
>>>Do you think the relational model could efficiently be used as the basis
>>>of search engines such as google
>> Why not?
>> The relational model is purely logical. Physically the
>> implementor is free to use whatever tricks he may wish.
>
>I've seen this argument used a lot and it doesn't seem quite right.

Actually, it is right. And that is my beef with relational theory.

Relational Theory is based totally on set theory and logic. In other words, it's an exercise in pure maths.
>
>Suppose I have two logical models that do the same thing. For
>implementing them physically, the best possible algorithm for one might
>be O(n^2) but for the other it might be O(1).

Or it might be "knapsack complex" - so what. The only thing of interest to relational theory is "will it complete in finite time", or to rephrase that, "is it a solvable problem".
>
>I can't think of a reasonable example right now, but suppose I have a
>model that is identical to the relational model except it requires me
>to factorise a random 1000-digit number before each query (not for any
>reason, this is just a pathological example).

The fact that the solution might take longer to calculate than the age of the universe is irrelevant to relational theory. It's "a detail of the implementation".
>
>This is a logical model but clearly any implementation of it will be
>inferior to a similar implementation of the standard relational model.
>
>So what I'm saying is that a logical model is not totally independent
>of any physical implementation of it, there may be a upper bound on how
>efficient it can be.

Which is why MultiValue, Tree, and most other models that muddle up theory and implementation will kick the sh*te out of relational when you actually run them in the real world ...
>
>Paul.

Cheers,
Wol

-- 
Anthony W. Youngman - wol at thewolery dot demon dot co dot uk
HEX wondered how much he should tell the Wizards. He felt it would not be a
good idea to burden them with too much input. Hex always thought of his reports
as Lies-to-People.
The Science of Discworld : (c) Terry Pratchett 1999