Re: Objects and Relations

On Jan 31, 4:10 pm, "Marshall" <marshall.spi..._at_gmail.com> wrote:
> On Jan 30, 6:32 am, "David BL" <davi..._at_iinet.net.au> wrote:
> > On Jan 30, 6:33 pm, "Marshall" <marshall.spi..._at_gmail.com> wrote:
>
>
> > I found your post very informative and interesting and shows me that
> > RA is more powerful than I imagined - when combined with aggregation.
> > I was expecting that substring testing would require transitive
> > closure.
>
> 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 thought RA was a strict subset of FOL - ie Horn clauses without recursion and negation.

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

> However
> if we imagine a general purpose programming language that was
> nonetheless relational through and through, we would of course be
> discussing a Turing complete language and it would be able
> to express TC.

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?

> I note that recursive functions are Turing complete, and that
> functions
> are a kind of relation, and we can use join on any kind of relation,
> therefore we can employ join with functions. Being able to do
> so expands the computational power of join to the "goes to 11"
> of Turing, at the cost of the loss of the strong normalization
> property
> that basic RA has, which as a very smart guy once said to me
> "is overrated anyway."

> > I admit the RM approach is a little foreign to me.
> > However, I have a remaining objection, and perhaps this could be
> > overthrown as well.
>
> > 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?

> The thing that I used to think was harder was figuring out
> early termination of aggregates. That is, if you are aggregating
> multiplication across a set of integers, you can stop doing any
> actual multiplication if you hit a zero. I found the key to this
> in some recently published Fortress documents; you can
> stop any time you hit a fixed point of the folded function.
> (So the system has to know fixed points.)
>
> Actually the Fortress documents are quite interesting in
> how they handle both catamorphisms and how they handle
> implicit parallelization. I note these are two things that
> are *quite* difficult to optimize in C++ because of its
> Mr. Pouty Pants memory model, where you pretty
> much have to assume everything is aliased to everything
> else unless you have an affidavit from the Postmaster General.
> I also note that these kinds of optimizations are a cakewalk
> for a relational language, and that the relative importance
> of implicit parallelization vs. standard C-style optimizations
> is strongly increasing over time with multiple CPU cores.
> Finally, I note that I am really starting to overuse the
> phrase "I note."

My guess is that FP is the best general strategy to achieve concurrency. In any case FP and RA are related.

> Upon rereading the last paragraph it appears my coherence
> level is dropping faster than a frat boy's pants at Mardi Gras,
> so I'd better sign off now. Sorry for any incoherence.
Received on Wed Jan 31 2007 - 15:18:06 CET