Re: Objects and Relations

On Jan 31, 6:18 am, "David BL" <davi..._at_iinet.net.au> wrote:
> On Jan 31, 4:10 pm, "Marshall" <marshall.spi..._at_gmail.com> wrote:
>
> > As an aside, please note that TC is not a showstopper for a relational
> > language. If we are speaking of a language that is equivalent in
> > computational power to first order logic, (such as basic SQL) then
> > we are speaking of a language that is not Turing complete.
>
> Does it make sense for a language to be equivalent in computational
> power to FOL when FOL is so rich as to be undecideable?

I don't quite follow this question. As someone who is used to general purpose programming languages, FOL occasionally feels weak to me.

> I thought RA was a strict subset of FOL - ie Horn clauses without
> recursion and negation.

I am unclear; however I was under the impression that Codd had shown that RA and FOL were of equivalent computational power.

> BTW is support for aggregation technically a part of RA or not?

Mumble. I have no idea what the conventional view is, however we lately have heard from Vadim a demonstration that aggregation is the inverse operation of join, so these days I'd have to say yes.

> Agreed.
>
> I've been trying to understand what things aren't possible with the
> basic RA (given that it's not Turing complete). Can you suggest a
> suitable reference?

Transitive closure is the canonical answer.

> > > The objection is this: I find it difficult to imagine a system being
> > > able to turn those select statements into fast efficient
> > > implementations on strings represented as arrays of characters.
> > > Presumably there is an integrity constraint that shows that a string
> > > has characters at all index positions from the start to the end of the
> > > string. Somehow the system sees this integrity constraint, realises
> > > that strings can be implemented as arrays and then is able to
> > > translate RA expressions into efficient algorithms. This all seems
> > > rather speculative to me.
>
> > > Can you answer this question for me? In the following
>
> > > select min(index) from S where c = ch and index >= fromIndex
>
> > > How does the system realise that it can avoid finding all characters
> > > satisfying the where clause, and then finding the minimum index? ie
> > > instead it should merely scan the array for the left most character
> > > matching ch starting at fromIndex.
>
> > Well, I can't put the pieces together in a nice package but I can
> > enumerate them. In short, the system has to understand order
> > theory.
>
> > I don't think it is the integrity constraint that matters so much as
> > that there is a total order on int, the type of index. Furthermore
> > the system understands the relationship between the comparators
> > (<, >=, etc.) and this order, and it understands the relationship
> > between < and min(). Knowing this it can know that it doesn't
> > have to examine any values for index that are <= fromIndex,
> > and it knows once it has found a single matching value, it doesn't
> > need to examine any values larger than that. Couple this with
> > the fact that if the system is using a naive array implementation
> > of the string, it will also know that the index values are laid
> > out *in order* in memory. (The fact that these values aren't
> > reified is irrelevant; they are still ordered. We can consider
> > the (index, char) tuple as being sequential, with the index
> > taking up 0 bytes and the char sizeof(char) bytes.) Oh, and
> > that the optimizer will know how to take advantage of joining
> > on an attribute that is in order in memory. IIUC these are all
> > things that optimizers are capable of doing in today's products.
>
> When we build all sorts of crazy, complicated RA expressions to
> perform string processing, can we really expect an optimizer to
> generate decent code? Are you saying all the theory currently exists?

Again I have to specifically disclaim any significant knowledge of query optimizers; it is just not my field. However as I understand it (which is weakly) yes, the theory does currently exist, for a lot of it anyway.

In general, though, someone who knows exactly what they are doing, and who is building a special-purpose engine, given a tool such as C++, will be able to build something that is better *for that special purpose* than a general-purpose solution will likely be. That difference may only be O(c) though.

> My guess is that FP is the best general strategy to achieve
> concurrency.

I favor the Erlang approach: no shared state, communication via message passing. It is a *very* good fit for a relational approach, although no one has ever put the pieces together as far as I know.

While I have great respect for FP, I happen to believe that *not* insisting on purity (in the FP sense of the word) is the right approach.
Constrained mutation > monads. Note the great success of impure functional approaches such as Lisp and SML. (I am not speaking of *commercial* success here.)

> In any case FP and RA are related.

Yes. And in fact I believe that relationship is deeper than is commonly recognized. In particular I believe that the two can be unified such that there are no visible seams between them.

Marshall Received on Thu Feb 01 2007 - 08:16:01 CET