Re: Is a function a relation?

From: David BL <>
Date: Mon, 29 Jun 2009 07:39:12 -0700 (PDT)
Message-ID: <>

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!

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. 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.

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.

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?

> >> > 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.

> > 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 Mon Jun 29 2009 - 16:39:12 CEST

Original text of this message