Codd's Information Principle

#21

<compdb (AT) hotmail (DOT) com> wrote

Quote:

On Oct 29, 7:40 pm, "Mr. Scott" <do_not_re... (AT) noone (DOT) com> wrote:
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.)

Not so much, but this is an understandable misconception. The information
content in the database is the logical sum (disjunction) of the propositions
represented by each row in the database. Under both the closed and open
world interpretations, only those propositions that are judged to be true
are represented by rows in the database. The truth value of the sum of just
those propositions that are judged to be true is the same as the truth value
of the sum of all consistent propositions. That cannot be said if the
logical connector is AND instead of OR.

closed world:
true \/ false = true.
true /\ false = false.

open world:
true \/ unknown = true
true /\ unknown = unknown

Quote:

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.

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.

Are you saying that there is no point in defining constraints?

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)

Again, not so much. Pxy and Qxz have x in common; consequently, in order to
satisfy Pxy -> Qxz, there cannot be an instance of Pxy that is true without
an instance of Qxz that is true and has a corresponding value for x, but
there can be an instance of Qxz without a corresponding instance of Pxy.
Similarly, in order to satisfy Pxy iff Qxz, there cannot be an instance of
Pxy without a corresponding instance of Qxz and there cannot be an instance
of Qxz without a corresponding instance of Pxy. But for Pxy \/ Qxz, there
can be an instance of Pxy without a corresponding instance of Qxz and there
can be an instance of Qxz without a corresponding instance of Pxy.

Quote:

but that's not equivalent to what you wrote.

I don't know what you mean by "embodies". Implies? Is thus
constrained?

"Embodies" is easier to write than "is an arbitrary member of the set of all
models of."

Quote:

Also "sentence" means "proposition" but I don't know what you mean by
it.

A sentence is a well-formed formula with no free variables.

Quote:

And you seem to sometime use "database" when you mean "query result".

Not "query result" but rather "what can be queried." I thought the context
of my use of the term "database" was sufficient to disambiguate between the
different senses of the word. I guess I was wrong. Sorry.

Quote:

I can't make much sense of your database comments.
Your comments about the predicate for JOIN make sense.

philip

#22

On Oct 31, 6:00*am, "Mr. Scott" <do_not_re... (AT) noone (DOT) com> wrote:

Quote:

"paul c" <toledobythe... (AT) oohay (DOT) ac> wrote in message

news:urFGm.49866$Db2.28279 (AT) edtnps83 (DOT) ..

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 pointhas
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 itis
better to subtract notions than add them, ie., better to not introducea
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 canbe
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.- Hide quoted text -

- Show quoted text -

I appreciate this text.
However I would like to add some thoughts. Loosely speaking a database
is a model for a schema. Not necessary a relational schema. Sometimes
we also need all databases which were a model for the schema.
Sometimes we must keep wrong (false) data in our database because
there are procedures based on these false data (for example a
procedure at a court). More important, there are big DB fields of
general character where we maintain all data - good, wrong and false.

Vladimir Odrljin

#23

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

Quote:

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

Yes, I know, that's why I left in your double quotes.

Quote:

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.

The user *doesn't* have any choice.

Assume variables (base relations) v with attributes ai and predicate
(statement about the world) P and w with attributes bi and predicate
Q.
P and Q are chosen by the designer.
The user set the value of v and w having observed the world.

If variable v={t | P(a1 t.a1, ...)} and variable w={t | Q(b1
t.b1, ...)}
(using named operands) then it is unavoidably true that
(v JOIN w) = {t | P(a1 t.a1, ...)} AND Q(b1 t.b1, ...)}.
Suppose v={<joe, 10>, <mary, 20>} with P "a1 is a2 years old" and
w={<joe>, <sue>, <john>} with Q "a1 has a cat".
(ie joe is 10 and marry is 20 and no one else is any age).
Then (v JOIN w)={t| a1 is a2 years old and has a cat"} ie {<joe, 10>}
(ie the names and ages of those people who have cats.
So "joe is 10 and has a cat" is true and "mary is 20 and has a cat" is
false
and every other statement of the form "a1 is a2 has a cat" is false
too.
(This is just an example following my original message.)

This is why the operators of the relational algebra manipulate tuples
as they do.
The algebra plus this fact is essentially the relational model:
that the dbms calculates the tuples satisfying a transformation of
predicates
(in the users head) by evaluating the corresponding relation operator
on the
corresponding relations (in the database).

philip

#24

compdb (AT) hotmail (DOT) com wrote:

Quote:

On Oct 30, 9:41 pm, paul c <toledobythe... (AT) oohay (DOT) ac> wrote:
com... (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.

Yes, I know, that's why I left in your double quotes.

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.

The user *doesn't* have any choice.

Assume variables (base relations) v with attributes ai and predicate
(statement about the world) P and w with attributes bi and predicate
Q.
P and Q are chosen by the designer.
The user set the value of v and w having observed the world.

If variable v={t | P(a1 t.a1, ...)} and variable w={t | Q(b1
t.b1, ...)}
(using named operands) then it is unavoidably true that
(v JOIN w) = {t | P(a1 t.a1, ...)} AND Q(b1 t.b1, ...)}.
Suppose v={<joe, 10>, <mary, 20>} with P "a1 is a2 years old" and
w={<joe>, <sue>, <john>} with Q "a1 has a cat".
(ie joe is 10 and marry is 20 and no one else is any age).
Then (v JOIN w)={t| a1 is a2 years old and has a cat"} ie {<joe, 10>}
(ie the names and ages of those people who have cats.
So "joe is 10 and has a cat" is true and "mary is 20 and has a cat" is
false
and every other statement of the form "a1 is a2 has a cat" is false
too.
(This is just an example following my original message.)

This is why the operators of the relational algebra manipulate tuples
as they do.
The algebra plus this fact is essentially the relational model:
that the dbms calculates the tuples satisfying a transformation of
predicates
(in the users head) by evaluating the corresponding relation operator
on the
corresponding relations (in the database).

philip

I don't think I have much argument with most people here about
relational operators as far as how they can manipulate relational
representations of useful facts/assertions or make inferences from
minimalized/normalized relations are concerned.

However, I think many people are making correct arguments which are not
apt because they are not necessary.

Perhaps my attitude can be summarized by saying that I see no need to
preserve any interpretation of a relation's extension that involves
compound propositions (I don't mean by this that a view expression can't
be preserved in the form of a mechanical constraint). I think arguments
against this would be put best if they showed what problems result from
such an interpretation.

For want of a better name, I think of these as 'regular' relations,
maybe because at one time I preached 'regular' sentences to people who
were designing tables.

(A few asides: I don't want to quibble with some of the lingo because I
think it's somewhat beside my point, eg., I'm not making any comment at
all about the myriad interpretations of truth that abound here and I
don't object to alternative algebras on principle, eg., relational
lattice, assuming they have practical advantages, I just happen to find
the D&D definitions concise and tidy. I also lean to the view that
procedural/imperative languages create big problems for most people when
it comes to understanding RT.)

#25

paul c wrote:

Quote:

compdb (AT) hotmail (DOT) com wrote:

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

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

Yes, I know, that's why I left in your double quotes.

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.

The user *doesn't* have any choice.

Assume variables (base relations) v with attributes ai and predicate
(statement about the world) P and w with attributes bi and predicate
Q.
P and Q are chosen by the designer.
The user set the value of v and w having observed the world.

If variable v={t | P(a1 t.a1, ...)} and variable w={t | Q(b1
t.b1, ...)}
(using named operands) then it is unavoidably true that
(v JOIN w) = {t | P(a1 t.a1, ...)} AND Q(b1 t.b1, ...)}.
Suppose v={<joe, 10>, <mary, 20>} with P "a1 is a2 years old" and
w={<joe>, <sue>, <john>} with Q "a1 has a cat".
(ie joe is 10 and marry is 20 and no one else is any age).
Then (v JOIN w)={t| a1 is a2 years old and has a cat"} ie {<joe, 10>}
(ie the names and ages of those people who have cats.
So "joe is 10 and has a cat" is true and "mary is 20 and has a cat" is
false
and every other statement of the form "a1 is a2 has a cat" is false
too.
(This is just an example following my original message.)

This is why the operators of the relational algebra manipulate tuples
as they do.
The algebra plus this fact is essentially the relational model:
that the dbms calculates the tuples satisfying a transformation of
predicates
(in the users head) by evaluating the corresponding relation operator
on the
corresponding relations (in the database).

philip

I don't think I have much argument with most people here about
relational operators as far as how they can manipulate relational
representations of useful facts/assertions or make inferences from
minimalized/normalized relations are concerned.

However, I think many people are making correct arguments which are not
apt because they are not necessary.

Perhaps my attitude can be summarized by saying that I see no need to
preserve any interpretation of a relation's extension that involves
compound propositions (I don't mean by this that a view expression can't
be preserved in the form of a mechanical constraint). I think arguments
against this would be put best if they showed what problems result from
such an interpretation.

For want of a better name, I think of these as 'regular' relations,
maybe because at one time I preached 'regular' sentences to people who
were designing tables.

(A few asides: I don't want to quibble with some of the lingo because I
think it's somewhat beside my point, eg., I'm not making any comment at
all about the myriad interpretations of truth that abound here and I
don't object to alternative algebras on principle, eg., relational
lattice, assuming they have practical advantages, I just happen to find
the D&D definitions concise and tidy. I also lean to the view that
procedural/imperative languages create big problems for most people when
it comes to understanding RT.)

I would leave off the "assuming they have practical advantages". At
worst, exploring a primrose path reduces by one the number of paths to
explore. Provided, one doesn't insist on exploring the same primrose
path to the exclusion of all others, that is.

#26

Bob Badour wrote:
....

Quote:

I would leave off the "assuming they have practical advantages". At
worst, exploring a primrose path reduces by one the number of paths to
explore. Provided, one doesn't insist on exploring the same primrose
path to the exclusion of all others, that is.

Didn't mean to suggest otherwise. Sometimes the immediate expert
objection to the 'primrose path' turns out to be an advantage if the
idea is allowed to breath.

But one point seems very immediate to me - for any given relational
expression, there is only one equivalent extension.

#27

paul c wrote:

Quote:

Bob Badour wrote:
...

I would leave off the "assuming they have practical advantages". At
worst, exploring a primrose path reduces by one the number of paths to
explore. Provided, one doesn't insist on exploring the same primrose
path to the exclusion of all others, that is.

Didn't mean to suggest otherwise. Sometimes the immediate expert
objection to the 'primrose path' turns out to be an advantage if the
idea is allowed to breath.

But one point seems very immediate to me - for any given relational
expression, there is only one equivalent extension.

I don't follow that at all.

#28

Bob Badour wrote:

Quote:

paul c wrote:
....
Didn't mean to suggest otherwise. Sometimes the immediate expert
objection to the 'primrose path' turns out to be an advantage if the
idea is allowed to breath.

But one point seems very immediate to me - for any given relational
expression, there is only one equivalent extension.

I don't follow that at all.

If you mean the last sentence, I could expand it by saying that for any
given purpose, in other words any given application, I think that single
extension must have one interpretation. Since the expression might not
involve any algebraic operations, I think it is best to discard those in
the interpretation, no matter how the extension was formed. I say
'best' because that seems sufficient to me and I don't see how including
those ops is necessary. I would like to know what problems this causes,
eg., I don't see that inconsistences/contradictions or loss of utility
or inability to optimize result from it.

#29

paul c wrote:

Quote:

Bob Badour wrote:

paul c wrote:

...

Didn't mean to suggest otherwise. Sometimes the immediate expert
objection to the 'primrose path' turns out to be an advantage if the
idea is allowed to breath.

But one point seems very immediate to me - for any given relational
expression, there is only one equivalent extension.

I don't follow that at all.

If you mean the last sentence, I could expand it by saying that for any
given purpose, in other words any given application, I think that single
extension must have one interpretation. Since the expression might not
involve any algebraic operations, I think it is best to discard those in
the interpretation, no matter how the extension was formed. I say
'best' because that seems sufficient to me and I don't see how including
those ops is necessary. I would like to know what problems this causes,
eg., I don't see that inconsistences/contradictions or loss of utility
or inability to optimize result from it.

I cannot make sense of what you wrote.

#30

On Oct 31, 9:03 am, "Mr. Scott" <do_not_re... (AT) noone (DOT) com> wrote:

Quote:

A sentence is a well-formed formula with no free variables.
Yes, I was wrong.

Quote:

Are you saying that there is no point in defining constraints?
No, you can use them for all the things they are useful for.

(Support the user's understanding of the predicates,
help the designer improve the design,
help the dbms to prevent invalid states from user input errors,
help the dbms to optimize execution, etc.)
But they're not necessary for understanding, updating
or querying the database. The user just needs the predicates.

We'll just have to disagree about the rest.

philip