Re: Is a function a relation?

From: Brian Selzer <>
Date: Mon, 29 Jun 2009 23:46:13 -0400
Message-ID: <dUf2m.1632$>

"David BL" <> wrote in message
> On Jun 29, 5:11 pm, "Brian Selzer" <> wrote:
>> "David BL" <> wrote in message
>> > The definition of 'variable' (relevant to this discussion) doesn't
>> > constrain physical implementation choices in any way. The sense in
>> > which a variable is deemed to hold a value can be arbitrarily
>> > indirect, and for example may involve physical storage of deltas.
>> The use of relvars does constrain physical implementation--at least
>> indirectly. The decision to use relvars relegates delete, insert, and
>> update to being shortcuts for assignment.
> I disagree. Variables can have many distinct ways of being
> reassigned. This can be modelled by representing changes to variables
> as values of various types!

Can you please elaborate?

> My area of research (Operational Transform) concerns the recording of
> locally generated deltas on a replicated, distributed database as
> values (called "operations") that can be propagated efficiently in
> order to achieve synchronisation without any need for distributed
> transactions.

It sounds like a very interesting area of research. I can only imagine what it entails.

> I certainly don't think of operations as just shortcuts
> for assignments. This is not just a physical distinction, it is a
> logical one. In fact a logical representation of an operation allows
> for the concept of intention preservation when operations are
> transformed against each other in such a way that they can be applied
> in different orders at different sites, yet still allow all sites in
> the distributed system to converge to the same final state.
> Let the execution of operation O on state S result in state S' denoted
> by S' = S+O. In the OT literature two concurrent operations O1,O2
> that are applied on the same initial state S are said to be equivalent
> if S+O1 = S+O2. This is not a sufficient condition for O1=O2.

I'm cringing a bit here. This reminds me of the problems associated with Sql Server replicating updates as delete/insert pairs.

> This formalises the sense in which it is possible to say that delete,
> insert and update can be equivalent to assignment, but not the same as
> assignment.

I'm cringing again, because this implies that descriptions must be rigid under the intended interpretation. I think that in order to be equivalent, the result has to be not just the same syntactically, but also semantically. When I issue an update, I am asserting that something appears different, but when I issue a delete and an insert, I am asserting that something ceased to exist while at the same time something else came into existence; therefore, even though the results of two operations may be identical syntactically, they are not necessarily semantically equivalent.

> This is regardless of whether one treats the database state as the
> abstract value of a database variable.
>> >> Abstract, well defined mathematical objects cannot change, so a
>> >> formalism
>> >> that admits only abstract, well defined mathematical objects cannot be
>> >> used
>> >> to model things that can change.
>> > I already pointed out the flaw in that statement. Physical database
>> > systems are variables not values.
>> I don't think it is flawed since those variables can only contain
>> abstract,
>> well defined mathematical objects that cannot change.
> I don't see what the problem is.
>> >> > When you say a value means different things at different times it
>> >> > seems like you're thinking a value is what C.Date calls an
>> >> > appearance
>> >> > of a value, which actually has more to do with a variable that
>> >> > exists
>> >> > in time and space.
>> >> Please don't misrepresent me: I didn't say that a value means
>> >> different
>> >> things at different times; I said that a term in a formal language can
>> >> mean
>> >> different things at different times.
>> >> Also, a variable is a container for a value. How can it exist in time
>> >> and
>> >> space?
>> > You're going to have to expand on that.
>> What do you want to know?
> When someone uses a debugger to view values of integer variables on
> the stack frame, are you saying they aren't variables, or that they
> don't exist in time and space?

Now you're talking about a physical manifestation of the abstract.

>> >> > I don't consider relation values to have names.
>> >> That doesn't surprise me. I suppose that you would attribute the same
>> >> meaning to a relation that is constructed by explicitly stating the
>> >> heading
>> >> and tuples, as a relation consisting of the exact same set of tuples
>> >> that
>> >> is
>> >> the result of a union of two relations in the database?
>> > Relation values aren't constructed (rather they are selected). You
>> > make it sound like they can suddenly spring into existence.
>> They can in D. See <relation selector inv> on page 110 of TTM 3rd
>> Edition.
> That is a *selection* of a relation value. It doesn't cause a
> relation value to come into existence. D&D are careful about this -
> that's why they use the term selection not construction.

I don't know about you, but the right hand side of the assignment,

PQ := RELATION { TUPLE { P# P#('P1'), QTY QTY( 600) } ,

                                 TUPLE { P# P#('P5'), QTY QTY( 500) } ,
                                 TUPLE { QTY QTY(1000), P# P#('P2') } ,
                                 TUPLE { P# P#('P4'), QTY QTY( 500) } ,
                                 TUPLE { QTY QTY(400), P# P#('P3') } ,
                                 TUPLE { P# P#('P6'), QTY QTY( 100) } } ;

From page 153, TTM 3rd Edition, looks to me like a relation that just sprang into existence!

>> > Since relation values don't exist in space or time it doesn't make
>> > sense to think that they in themselves record facts about the real
>> > world. They only do that when they appear as encoded values in a
>> > physical database (as the current value of a relation variable).
>> Not sure what you mean by this.
> Given a relation type (i.e. schema), there are a number (possibly
> infinite) of relation values that conform to that type. The type and
> the values of that type are all abstract and carry almost no
> information.
> Consider the analogy of a textual string. If you could look at a vast
> number of random strings, you might occasionally find some interesting
> ones like Shakespeare's Macbeth. Information comes from the
> *selection* of useful values from amongst the multitude. An analogy
> is how a sculptor uncovers a work of art in a block of stone even
> though it was there all along.
> The amount of information in a value can be quantified by the size of
> the smallest program that can generate that value. A program to
> generate the set of all strings is trivial (at least on an abstract
> machine that's equivalent to a Turing machine with its infinite
> tape!), whereas a program to output only one selected string is
> arbitrarily large.
Received on Tue Jun 30 2009 - 05:46:13 CEST

Original text of this message