Codd's Information Principle

#11

On Oct 30, 11:41 am, paul c <toledobythe... (AT) oohay (DOT) ac> wrote:

Quote:

Yes, I mean assignment to a (programming) variable. I don't know of any
logical operator called 'assignment'.

You don't seem understand assignment.

Assignment has nothing to do with the relationship between relations
and logic or the relational model per se. The semantics of assignment
in a dbms language is exactly the same as it is in every programming
language.

You evaluate expressions using the current values of variables. You
can assign the value of an expression to a variable. This gives a new
overall state. The relationship between the values of one or more
variables in the post-(multiple-)assignment state and the expressions
that were used to express those values in the pre-assignment state
is simply (and tautologically) that the values of the assigned
expressions evaluated using the pre-assignment variable values are
the same as the values of the expressions consisting of just the
variable names evaluated using the post-assignment variable values
(ie the post-assignment values of the variables).

It doesn't matter what the types of variables are.

If a language allows assignment to an expression then the language
designer has to say what that means. Presumably the
post-assignment values of the variables in the assigned-to expressions
must be such that when they are evaluated in the post-assignment
state then their values are the same as the values of the assigned-
from
expressions evaluated in the pre-assignment state. If the language
processor cannot determine a single choice for the post-assignment
values of variables then the language designer has to give some sort
of
policy. But again, the particular assigned-from expressions have no
other relationship with the new state than that when evaluated in the
old state they give the values of the variables in the new state. The
particular assigned-from expressions don't matter, just their values.

philip

#12

compdb (AT) hotmail (DOT) com wrote:

Quote:

On Oct 30, 11:41 am, paul c <toledobythe... (AT) oohay (DOT) ac> wrote:
Yes, I mean assignment to a (programming) variable. I don't know of any
logical operator called 'assignment'.

You don't seem understand assignment.

Assignment has nothing to do with the relationship between relations
and logic or the relational model per se. The semantics of assignment
in a dbms language is exactly the same as it is in every programming
language.

You evaluate expressions using the current values of variables. You
can assign the value of an expression to a variable. This gives a new
overall state. The relationship between the values of one or more
variables in the post-(multiple-)assignment state and the expressions
that were used to express those values in the pre-assignment state
is simply (and tautologically) that the values of the assigned
expressions evaluated using the pre-assignment variable values are
the same as the values of the expressions consisting of just the
variable names evaluated using the post-assignment variable values
(ie the post-assignment values of the variables).

It doesn't matter what the types of variables are.

If a language allows assignment to an expression then the language
designer has to say what that means. Presumably the
post-assignment values of the variables in the assigned-to expressions
must be such that when they are evaluated in the post-assignment
state then their values are the same as the values of the assigned-
from
expressions evaluated in the pre-assignment state. If the language
processor cannot determine a single choice for the post-assignment
values of variables then the language designer has to give some sort
of
policy. But again, the particular assigned-from expressions have no
other relationship with the new state than that when evaluated in the
old state they give the values of the variables in the new state. The
particular assigned-from expressions don't matter, just their values.

philip

That's adding more notions, such as 'state' and 'before' and 'after',
'assignment to an expression' et al, all artifacts of certain physical
programming attitudes if you ask me. I'm more interested in subtracting
notions as far as possible.

#13

paul c wrote:

Quote:

compdb (AT) hotmail (DOT) com wrote:
On Oct 30, 11:41 am, paul c <toledobythe... (AT) oohay (DOT) ac> wrote:
Yes, I mean assignment to a (programming) variable. I don't know of any
logical operator called 'assignment'.

You don't seem understand assignment.

Assignment has nothing to do with the relationship between relations
and logic or the relational model per se. The semantics of assignment
in a dbms language is exactly the same as it is in every programming
language.

You evaluate expressions using the current values of variables. You
can assign the value of an expression to a variable. This gives a new
overall state. The relationship between the values of one or more
variables in the post-(multiple-)assignment state and the expressions
that were used to express those values in the pre-assignment state
is simply (and tautologically) that the values of the assigned
expressions evaluated using the pre-assignment variable values are
the same as the values of the expressions consisting of just the
variable names evaluated using the post-assignment variable values
(ie the post-assignment values of the variables).

It doesn't matter what the types of variables are.

If a language allows assignment to an expression then the language
designer has to say what that means. Presumably the
post-assignment values of the variables in the assigned-to expressions
must be such that when they are evaluated in the post-assignment
state then their values are the same as the values of the assigned-
from
expressions evaluated in the pre-assignment state. If the language
processor cannot determine a single choice for the post-assignment
values of variables then the language designer has to give some sort
of
policy. But again, the particular assigned-from expressions have no
other relationship with the new state than that when evaluated in the
old state they give the values of the variables in the new state. The
particular assigned-from expressions don't matter, just their values.

philip

That's adding more notions, such as 'state' and 'before' and 'after',
'assignment to an expression' et al, all artifacts of certain physical
programming attitudes if you ask me. I'm more interested in subtracting
notions as far as possible.

Another example is assigning to a variable twice. Various complications
go away if a variable can be assigned to only once. (Is there a name
for such a variable? In the old days it might have been called a macro.)

#14

paul c wrote:

Quote:

compdb (AT) hotmail (DOT) com wrote:

On Oct 30, 11:41 am, paul c <toledobythe... (AT) oohay (DOT) ac> wrote:

Yes, I mean assignment to a (programming) variable. I don't know of any
logical operator called 'assignment'.

You don't seem understand assignment.

Assignment has nothing to do with the relationship between relations
and logic or the relational model per se. The semantics of assignment
in a dbms language is exactly the same as it is in every programming
language.

You evaluate expressions using the current values of variables. You
can assign the value of an expression to a variable. This gives a new
overall state. The relationship between the values of one or more
variables in the post-(multiple-)assignment state and the expressions
that were used to express those values in the pre-assignment state
is simply (and tautologically) that the values of the assigned
expressions evaluated using the pre-assignment variable values are
the same as the values of the expressions consisting of just the
variable names evaluated using the post-assignment variable values
(ie the post-assignment values of the variables).

It doesn't matter what the types of variables are.

If a language allows assignment to an expression then the language
designer has to say what that means. Presumably the
post-assignment values of the variables in the assigned-to expressions
must be such that when they are evaluated in the post-assignment
state then their values are the same as the values of the assigned-
from
expressions evaluated in the pre-assignment state. If the language
processor cannot determine a single choice for the post-assignment
values of variables then the language designer has to give some sort
of
policy. But again, the particular assigned-from expressions have no
other relationship with the new state than that when evaluated in the
old state they give the values of the variables in the new state. The
particular assigned-from expressions don't matter, just their values.

philip

That's adding more notions, such as 'state' and 'before' and 'after',
'assignment to an expression' et al, all artifacts of certain physical
programming attitudes if you ask me. I'm more interested in subtracting
notions as far as possible.

To be fair to philip, those are exactly the notions involved with
imperative programming languages. No need to invent anything else to
describe them. View updates are assignments to expressions.

#15

On Oct 30, 1:28*pm, paul c <toledobythe... (AT) oohay (DOT) ac> wrote:

Quote:

Another example is assigning to a variable twice. *Various complications
go away if a variable can be assigned to only once. *(Is there a name
for such a variable? In the old days it might have been called a macro.)

"Single-assignment variable." The style of programming is called
"Static single assignment."

Marshall

#16

On Oct 28, 12:51*pm, paul c <toledobythe... (AT) oohay (DOT) ac> wrote:

Quote:

Recently there has been mention of logical connectors being implicit in
tuples, eg. Mr. Scott wrote: "Each row of the join represents a
conjunction of propositions, one for each operand", ie., what I think is
called a compound proposition. I sometimes write similar, as well
regarding disjunctions. *But usually my purpose is simply to understand
the algebra.

I would like to ask where is the "information" to the effect that
certain rows represent compound propositions recorded?

The designer associates with each (base relation) variable
and (the relation version of) each function a predicate
(an informal but precise statement about the world).
Eg for variable v: person number X has letter Y in their name.
Eg for function +(A, B) returning C (whose relation version
has attributes A, B and C where A+B=C and functional
dependency {A, B} -> C): A plus B equals C. (So
functions are just a way to use further base relations that
don't change.)

Every relation expression has an associated predicate.
One that is just a variable name is associated with that
variable's predicate. One that is just a function application
denotes the value of the function for values of the
given argument expressions. One that is a relation
literal is associated with the OR over tuples of the AND
over attributes of the EQUALS of the name and the value.
Eg if the literal is {X, Y}{<1, a>, <2,b>} then the
associated predicate is (X=1 AND Y=a) OR (X=2 and Y=b).
Every other relation expression is associated with the
predicate you get by transforming its operands
appropriately for the relation expression's operator.
Eg if the relation expression is r JOIN s then the
corresponding predicate is ((predicate associated with r)
AND (predicate associated with s)); for r PROJECT ALL BUT x
it's (EXISTS x (predicate associated with r)).
So every relation expression corresponds to a logic expression.
*So the relational model is just giving another notation for logic.*

Substituting a tuple typed by a relation into its associated
predicate gives a proposition. If the relation variables'
tuples are those that give true propositions from their
predicates then an expression's tuples are those that
give true propositions from its predicate. Ie if the
variables and functions reflect the world so does a query
result. So we observe the world, update the variables so
that they reflect the world, then query. Repeat.

To update a variable is to give it a value reflecting the
new way the world is. It doesn't matter what the predicate
was in the old state for the expression you used.
You are just specifying some new tuples.
It just might be convenient to specify them in terms
of the old state and/or other variables and/or literals.

Quote:

"Each row of the join represents a
conjunction of propositions, one for each operand"

This doesn't make sense. Perhaps "one from each operand"?
If so, yes. The predicate associated with r JOIN s is
(predicate associated with r) AND (predicate associated with s).
So each result tuple present makes this true and
each result tuple absent makes this false.

Quote:

I would like to ask where is the "information" to the effect that certain
rows represent compound propositions recorded?

The database designer gives the variable and function predicates.
Only if you know them could you possibly observe the world
and reflect it in the tuples that are and are not in the variables,
or compose a query or interpret its results.
Then each relation expression has a predicate based on the predicates
of
its operands and the transformation of its operators (as explained
above).
So the fact that JOIN result rows represent compound propositions is a
property of the relational model, like that relations have tuples and
attributes.

On Oct 29, 4:38 pm, "Mr. Scott" <do_not_re... (AT) noone (DOT) com> wrote:

Quote:

Where is the "information" to the effect that 2 + 2 = 4 recorded? Certainly
not as attribute values within tuples within relations.

The relation version of "+" has a tuple like <LEFT 2, RIGHT 2, SUM 4>;
if you call + with 2 and 2 you get result 4.
But the fact that "+" in a query denotes addition is in the heads of
the
database designer and users.

Quote:

a relation value that has been obtained by a language devices
such as insert or assignment where the definition is based on union.
The 'OR' disappears.

The assigned tuples made the source expression's
predicate true in the old state of the world and they make the
assigned
variable's predicate true in the new state of the world (that's why
you
assigned them). How you specified the tuples doesn't matter.

philip

#17

On Oct 29, 7:40*pm, "Mr. Scott" <do_not_re... (AT) noone (DOT) com> wrote:

Quote:

Suppose that a database embodies the
following sentence,
forall x forall y forall z Pxy \/ Qxz
The database has two tables, let's call them P and Q, with predicates Pxy
and Qxz respectively.

I don't understand what you are trying to say.
The variable predicates and values determine the database proposition.
If the predicates for variables P and Q are Pxy and Qxz
then by definition the database proposition is (ie the database states
that)
(AND [for <x, y> in P] Pxy) AND
(AND [for <x, y> typed by but not in P] ~Pxz) AND
(AND [for <x, z> in Q] Qxz) AND
(AND [for <x, z> typed by but not in Q] ~Qxz)
(The ANDs with fors mean standard math series notation.)
This is equivalent to
(forall <x, y> in P Pxy) AND
(forall <x, y> typed by but not in P ~Pxz) AND
(forall <x, z> in Q Qxy) AND
(forall <x, x> typed by but not in Q ~Qxz)
I can't make much sense of what you're writing, but it seems to
be inconsistent with this.

Quote:

The
dependencies defined on the database also have an impact.

The dependencies are simply things that are true of the values that
of P and Q will simultaneously hold. Their tuples are determined by
their predicates and the way the world is.
So there's no effect to adding them to the database proposition;
they're always true.

Quote:

inclusion dependency from P[x] to Q[x].
forall x forall y forall z Pxy iff Qxz

If P's xs must be in Q then
forall x forall y (Pxy -> exists z Qxz)
but that's not equivalent to what you wrote.

I don't know what you mean by "embodies". Implies? Is thus
constrained?
Also "sentence" means "proposition" but I don't know what you mean by
it.
And you seem to sometime use "database" when you mean "query result".
I can't make much sense of your database comments.
Your comments about the predicate for JOIN make sense.

philip

#18

compdb (AT) hotmail (DOT) com wrote:

Quote:

On Oct 28, 12:51 pm, paul c <toledobythe... (AT) oohay (DOT) ac> wrote:
....
"Each row of the join represents a
conjunction of propositions, one for each operand"

This doesn't make sense. Perhaps "one from each operand"?
If so, yes. The predicate associated with r JOIN s is
(predicate associated with r) AND (predicate associated with s).
So each result tuple present makes this true and
each result tuple absent makes this false.
...

I was quoting Mr. Scott. Regardless, I don't agree with either
interpretation. I realize that many, perhaps most, people who have been
trained in logic or read about it would place my attitude somewhere
between unfaithful and ignorant, but I would never try to tell a user
that some predicates are conjunctions and some aren't.

#19

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

Quote:

paul c wrote:
Mr. Scott wrote:
...
Let's explore a simple example. Suppose that a database embodies the
following sentence,

forall x forall y forall z Pxy \/ Qxz

The database has two tables, let's call them P and Q, with predicates
Pxy and Qxz respectively.

Now suppose that at a given moment,

P has rows {{x:a,y:b},{x:a,y:c},{x:b,y:c}}
Q has rows {{x:a,z:d},{x:c,z:d}}

then P JOIN Q would have rows {{x:a,y:b,z:d},{x:a,y:c,z:d}}

Now let's apply logic.

The ground formulas represented in P are Pab, Pac, Pbc.
The ground formulas represented in Q are Qad, Qcd.

What is represented in P JOIN Q? Pab /\ Qad, Pac /\ Qad.
That's because P JOIN Q has the complex predicate Pxy /\ Qxz..
x being free in both P and Q is important because only those ground
formulas in P and Q that have a common x value satisfy the predicate of
P JOIN Q.

It should be clear now that it is the nature of join that dictates that
certain rows represent compound propositions, but there is more. The
dependencies defined on the database also have an impact. There really
isn't space here to go into detail, but suppose that the database
embodies the sentence,

forall x forall y forall z Pxy -> Qxz

Now the database still consists not only of the same two tables, but
also an inclusion dependency from P[x] to Q[x].

forall x forall y forall z Pxy iff Qxz

Here the database would consist of just one table but each row would
represent a biconditional.

I have no argument about the application of logic. Perhaps my point has
more to do with the language devices, such as 'insert', that are
essentially an assignment. While they are defined in logical terms they
are outside logic in the sense that when they are applied, something
special happens, a 'die is cast', as it were.

(Once we enter the realm of assignment, talk of possible base and view
differences is inevitable. I don't think it's inapt to say that treating
views differently from base values amounts to saying that assignment is
polymorphic, ie., behaves differently depending. I don't see a necessary
reason for that. But when dealing with a value that is the result of
assignment, I think it remains clear that the view definition is
effectively no more than a constraint on the view's value, and not a
constrain on the base values in the expression of the view's definition.
This may seem fuzzy and mystical perhaps due to my language not being
really up to the task but if that can be forgiven, I would say that it is
better to subtract notions than add them, ie., better to not introduce a
difference.)

Maybe it's useful to ask this: Was Codd trying to introduce assignment to
logic, (eg. was he trying to augment predicate calculus) or was he trying
to apply logic to the assignment of recorded values?

Neither. Codd wasn't trying to introduce assignment to logic because
assignment is an integral aspect of logic. Under an interpretation, meaning
is assigned to the terms of the first-order language and truth values are
assigned to the formulas. The terms of the language include variables and
function applications. Elements of the domain are assigned to variables,
and function applications evaluate to elements of the domain (constant
symbols being nothing more than 0-ary functions). Formulas are then
assigned truth values in the following way: once each term has been mapped
to an element of the domain, each ground atom is analyzed to judge whether
or not it is true. For example, if c evaluates to a particular car and Px
is the predicate "<x> is red," then the ground atom Pc is assigned a
positive truth value if and only if the car that c evaluates to is in fact
red at the time of interpretation. The relational model provides a
framework for recording those judgements so that they can be used to answer
queries. Codd wasn't trying to apply logic to the assignment of recorded
values; instead, he provided a framework whereby conclusions can be drawn
from recorded judgements by applying logic. More importantly, since only
what has been judged to be true can appear in a database, conclusions can be
drawn from what is in the database independent of what the symbols recorded
actually mean. What you refer to as assignments, inserts, updates and
deletes, merely correct what is recorded to reflect the current
interpretation. The database before an update reflects a different
interpretation than the database afterward. For example, if the car
referenced in the ground atom Pc has been painted blue, then Pc should be
judged to be false, since that particular car is no longer red at the time
of interpretation; consequently, the row in the database that represents Pc
should be removed since only what is judged to be true should be represented
in the database.

#20

paul c wrote:

Quote:

compdb (AT) hotmail (DOT) com wrote:

On Oct 28, 12:51 pm, paul c <toledobythe... (AT) oohay (DOT) ac> wrote:

...

"Each row of the join represents a
conjunction of propositions, one for each operand"

This doesn't make sense. Perhaps "one from each operand"?
If so, yes. The predicate associated with r JOIN s is
(predicate associated with r) AND (predicate associated with s).
So each result tuple present makes this true and
each result tuple absent makes this false.
...

I was quoting Mr. Scott. Regardless, I don't agree with either
interpretation. I realize that many, perhaps most, people who have been
trained in logic or read about it would place my attitude somewhere
between unfaithful and ignorant, but I would never try to tell a user
that some predicates are conjunctions and some aren't.

Even if the user asked? Is it like taboo or something?