Walter Mitty wrote:
....
In case you haven't seen it, here's a link to a widely-regarded, maybe even classic textbook:

http://mitpress.mit.edu/sicp/full-te...oc_%_sec_3.1.3

see "The Costs of Introducing Assignment". The authors distinguish 'substitution model' as being a property of functional languages. I think the A-algebra (algebras typically involve the substitution model, what many of us were taught in grade school, if I've got it right) and with an equality operator are among what they might call the functional languages. I'd also say most people start with a schema that constrains the possible assignment variables/pointers (eg., by declaring the allowable relvar or table names in advance) and never consider the algebraic implications. This puts the systems they make on logical quicksand. For example, there are two kinds of constraints for any relation, implicit and explicit. If the algebra or equivalent is ignored, certain implicit constraints are ignored too, such as the projection identities (eg., Heath) and heading constraints, in other words, logical independence. In most application languages, you can't map or interpret a sin
gle pointer to a set of algebraic symbols, but single algebraic expressions can be substituted for elements in the set of all possible language variables/pointers. I'd say when designing a schema it is logically safer to express the design constraints algebraically (with shorthands of course), then pick among the algebraic symbols that one prefers to interpret as variables/pointers. In a functional language, one needn't bother with this choice, that language will choose variables that satisfy the equations and we might not even need to know the definitions, eg., 'names', of all of them. In this sense, I'd say functional languages are at a 'higher-level' of abstraction and so too the A-algebra even though I'd guess many programmers would imagine it is somehow a 'lower-level' of detail.


Beyond predictability, an algebra or calculus starting point may not matter to the average developer but it is crucial in the design of a dbms imlementation which must nearly optimize for practical execution times, eg., deciding whether an index can check a key constraint. Without that starting point, one is only guessing whether optimizations are logically sound and consistent.

"paul c" <toledobythesea (AT) oohay (DOT) ac> wrote

Maybe you should re-read it. In Chapter 3 the substitution model is
abandoned in favor of the environment model for obvious reasons.

"Walter Mitty" <wamitty (AT) verizon (DOT) net> wrote


You're not quite misreading my comments, but that's not exactly how I would
say it. While it doesn't matter what combination of SQL imperatives were
performed or in what sequence, a database update isn't just the difference
between two states. Let me explain. This is not a simple explanation, and
I want to be thorough and absolutely clear so that there isn't any
confusion. In the following, a database is a value--a set of relations,
which are also values. To say 'database value' or 'relation value,'
therefore, is redundant. I've also shied away from words like 'state'
because they are loaded and draw heckles and derision from people who still
think the world is flat.

1. The set of all possible databases is determined by the database schema. A
possible database is simply one that conforms to the database schema.

2. Only one possible database can actually be the database at a time.

3. Each possible database corresponds to a distinct proposition where
a. each relation schema corresponds to a sentence (a closed first-order
formula), and for finite domains each relation schema extends into a set of
tuples, each of which corresponding to a positive atomic formula in the
first-order language of the proposition,
b. each database constraint corresponds to one or more sentences,
c. each element of each domain corresponds to a distinct constant, and
d. each key value in each tuple corresponds to either a constant or a
definite description, so that
e. the proposition is the logical conjunction of all of those formulae.

4. Due to the unique name, closed world and domain closure assumptions, only
one of the corresponding propositions can be assigned a positive truth value
at a time.

5. A database update essentially asserts that a different possible database
is now the database, but there is more to it than that.

6. A consequence of a database update is that a negative truth value is
assigned to the proposition that corresponds to the possible database that
has been the database the current database) and a positive truth value is
assigned to the proposition that corresponds to the possible database that
is becoming the database (the proposed database).

7. Due to 6, expressions in the algebra and the calculus can involve no more
than one database or possible database at a time.

Note that up to this point I have avoided references to individuals in the
universe of discourse, even though the assignment of positive and negative
truth values to propositions can only happen under an interpretation. Even
so, just as you cannot draw a sound conclusion from a proposition that has
been assigned a negative truth value and thus does not represent what is the
case--especially one that is the conjunction of many atomic formulae, the
result of any algebraic expression that involves more than one possible
database must therefore be considered suspect.

8. Since each tuple has a key value, under an interpretation each tuple maps
indirectly to an individual in the universe, but not necessarily to the same
individual all the time.

For example, suppose that there is one red hat, one blue hat, one green hat
and one orange hat, then the phrase 'the guy wearing the red hat' is
definite (hence the definite article), and in a room with up to four guys
wearing hats, 'the guy wearing the red hat' uniquely identifies a particular
guy.../at a time/. Now suppose you have two pictures of the room, and the
red hat appears in each picture. Is it valid to say that 'the guy wearing
the red hat' is the same guy in each picture? No, it isn't. The guy wearing
the red hat at the time that one of the pictures was taken could have
swapped hats with the guy that was wearing the blue hat, or could have
walked out of the room and handed the hat to someone that wasn't in the
picture. The point is that the key value 'red' may map to different
individuals at different times.

9. A database update consists of a set of primitive assertions that together
enumerate

a. all of the tuples in the current database that map to individuals
that no longer exist;
b. all of the tuples in the current database that map to individuals
that differ only in appearance (and how); and
c. all of the tuples in the proposed database that map to individuals
that came into being.

10. Assignment is not primitive: it is composed of combinations of 9a and 9c
and is semantically different from 9b. Consider the example in 8.
Assignment would corresponds the the scenario where the guy walked out of
the room--the guy wearing the red hat doesn't even appear in the other
picture. 9b would correspond to the scenario where the guys that were in
the room swapped hats--the guy wearing the red hat differs only in
appearance from one picture to the other.

11. There can be more than one set of primitive assertions that results in
the same proposed database value--in fact, there can be a large number of
them. This is why I hold that a database update isn't just the difference
between the proposed database and the current database.

12. A database update, therefore, specifies not just which possible
database is now the database, but exactly how the proposed database differs
from the current database.

A database is a set of named sets of sets of named values: it is not a set
of named sets of named sets of named values, though you can make it a set of
named sets of named sets of named values by introducing surrogates
(automatically generated identifiers), which act as rigid designators in the
first-order language of the propositions that correspond to possible
databases. With surrogates it is possible to determine exactly what is
different between one database and the next and by extension one picture of
the universe and the next because surrogates rigidly designate--that is,
permanently identify--individuals in the universe of discourse. Surrogates,
therefore, would make it possible to treat the operations insert, update and
delete as shortcuts for assignments. Without surrogates, on the other hand,
information is lost when those operations are translated into assignments:
in particular, exactly how one database differs from the next is lost,
making it extremely difficult if not impossible to define transition
constraints. (Try writing a set-based update trigger that acts as a
transition constraint on a table with a natural key. You'll find that you
can't determine with certainty whether or not a key update such as the hat
swapping example above occurred. And as a consequence, you can't just join
the old value to the new one to determine what happened.)

As far as whether or not assignment is imperative, the same thing that
limits expressions in the algebra and the calculus to a single database at a
time (see 6 above) prevents assignment from being defined using just the
algebra or the calculus. So if by declarative you mean "capable of being
defined just using the algebra," then assignment and all database updates in
general are definitely inherently imperative.

"paul c" <toledobythesea (AT) oohay (DOT) ac> wrote

Thanks for the link. A long time ago, I used to know Gerald Sussman.