Re: Functions and Relations

From: NENASHI, Tegiri <tnmail42_at_gmail.com>
Date: Sun, 19 Nov 2006 00:54:52 +0100 (CET)
Message-ID: <Xns987FC0DECA827asdgba_at_194.177.96.26>


"Marshall" <marshall.spight_at_gmail.com> wrote in news:1163886665.418503.107140_at_h48g2000cwc.googlegroups.com:

> On Nov 17, 12:19 pm, "Aloha Kakuikanu" <aloha.kakuik..._at_yahoo.com>
> wrote:
>> > NENASHI, Tegiri wrote:
>> > How one presents 'sqrt' as a relation in the database ? Please
>> > show.
>> This looks like a good opportunity to post a reworked snippet from my
>> exchange with Marshall.
>>
>> Function u=f(x,y,z) in general is a predicate Pf(x,y,z,u) with some
>> additional constraint. Given that a predicate is often an infinite
>> relation we have obvious difficulty implementing it. Let's discuss
>> this later, but focus on the benefits of representing functions as
>> relations. We have
>>
>> 1. Function invocation is a join:
>>
>> f(x) /\ x=1
>
> (A small detail, but function invocation (I like to say "application")
> would
> more usually be defined as join followed by projection over the result
> attributes.)
>We can be more general, however, and define a form of
> application that also encompasses partial application. Thus,
> application
> is join followed by projection over the symmetric difference of the
> operand attributes. This lets us do things like
>
> predicate Power = {x, y, z | x ^ y = z}
>
> partial application:
>
> Square = Power /\ `y=2` \/ `x, z`
>
> (The join with the empty (x,z) relation is what differentiates
> plain join from application.)
>
> We are left with a function Square(x) = x^2
>
> Thus, partial application (defined only in terms of the relational
> lattice operations) can encompass what functional programming
> languages call Currying.

It is like currying yes and very interesting but please show a practical example with relations.

>
>
>> 2. Function composition is a join:
>>
>> g(f(x)) <==> g(z,y) /\ f(y,x)
>
> Also an exciting result.

But it must be g o f <==> project_zx(g /\ f) no ? Also the natural join commutes and the composition of functions is not commutative.

>
> There is a subtle concern here with variable capture aka
> alpha conversion. In other words, we can run into trouble
> when f and g have attributes with names in common that
> we didn't expect. We can get out of it via the usual way:
> renaming. I recall that the original Tropashko paper
> pointed out how renaming could also be defined only
> in relational lattice terms.
>
>
>> Suppose we have the relation R(x,y) where y=x^2. No function yet,
>> just a relation.
>>
>> As it has two columns the simplest joins we can think of are:
>>
>> R /\ `y=9`
>>
>> R /\ `x=3`
>>
>> where `y=9` and `x=3` are constant unary relations.
>>
>> In the first case, we probably want to project the resulting relation
>> to `x`
>>
>> (R /\ `y=9`) \/ 'x'
>>
>> in the second case to `y`
>>
>> (R /\ `x=3`) \/ 'y'
>>
>> Informally, in the first case we want to know the result of sqrt(9),
>> in the first case just 3^2
>>
>> How the join is evaluated in both cases? Well, let's go into the
>> second case, because it's easier. As one relation is infinite, the
>> only feasible join method is nested loops. Moreover, we have to
>> start from the relation which is finite, that is `x=3`. Now, there
>> are the two possibilities:
>> 1. Scan the whole R relation and find all the matching tuples. Not
>> feasible too!
>
> Indeed, the difference between the two kinds of relations seems to
> be exactly that: intensional relations are computation and extensional
> relations are the result of computation! Thus, we cannot scan the
> relation until/unless we have performed the computation.

You say that tuples have not values but formulas ? How you realize this interesting theory in the model ?

==
Tegi Received on Sun Nov 19 2006 - 00:54:52 CET

Original text of this message