Codd's Information Principle
paul c
Principle but here's a version of a quote by Date: "The entire
information content of a relational database is represented in one and
only one way: namely, as attribute values within tuples within relations."
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?
Mr. Scott
"paul c" <toledob...@oohay.ac> wrote in message
news:2h1Gm.50615$PH1.9648@edtnps82...
Where is the "information" to the effect that 2 + 2 = 4 recorded? Certainly
not as attribute values within tuples within relations.
paul c
The values to satisfy that equation might well be recorded in relational
form but I presume you are not referring to that, rather to the general
truth of the equation as far as conventional arithmetic interpretation
is concerned.
I usually try to stay out of the discussions here about truth because a
database mechanism is not capable of appreciating that concept the way
humans can, just as a database doesn't record persons, only the symbols
we use for their names. No offense intended, but I think the question
borders on mysticism, imputing human concepts to a db, what Bob B uses
the anthrop-word to describe. We are all susceptible to those two
attitudes but I think we should make an effort to fall prey to them.
paul c
> ... We are all susceptible to those two
Oops, meant to say "make an effort to not fall prey to them".
Mr. Scott
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.
paul c
...
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.)
paul c
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?
Cimode
> 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?
Can you ellaborate on what you mean by *assignment*. If we are to
consider assignment in the sense of value assignment to a variable
then assignement is a simply component of mathematical logic.
Therefore, I do not see to define one according to the other through
precedence but rather through inclusion.
IMHO...
paul c
Yes, I mean assignment to a (programming) variable. I don't know of any
logical operator called 'assignment'.
Cimode
tends to restrict the possible meaning of assignment to a logical
assignment only to logical constructs such as relation variables.
Coming back to your question, though I could have hard time
understanding how pure logic could be applied to a programming
assignment, (which on an elementary sense is nothing but the semantic
representation of a physical memory bit manipulation) whithout a
relevant storage mechanism computing model defined first, I could
imagine it as being a possible assumption of his for the future
development of RM. My guess is he had enough to deal with on the
logical side of things.
On the other hand, I strongly doubt you first other assumption. But I
may just be wrong about that.
com...@hotmail.com
> 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
paul c
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.
paul c
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.)
Bob Badour
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.
Marshall
>
> 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
com...@hotmail.com
> 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.
> "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 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...@noone.com> wrote:
> 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.
>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
com...@hotmail.com
>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.
> 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.
> 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
paul c
>> "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.
Mr. Scott
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.
Bob Badour
Even if the user asked? Is it like taboo or something?
Mr. Scott
<com...@hotmail.com> wrote in message
news:1389f8a5-21c7-4b9d...@b2g2000yqi.googlegroups.com...
> On Oct 29, 7:40 pm, "Mr. Scott" <do_not_re...@noone.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
> 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?
>
> > 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.
> 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."
> 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.
> 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.
paul c
> paul c wrote:
...
>> 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?
Heh, not taboo in a fatal sense, just pointless and possibly a wasteful
distraction.
Distinguishing between everyday 'and' and logical 'AND' in user
relations, eg., saying part 'P1' is available in London from supplier
'S1' versus saying supplier 'S1' is in London AND supplier 'S1' supplies
part 'P1' is probably harmless. But I would not know how to answer the
user who then asked "where is the 'AND' in the relation's value?",
except to ask them back "well, what is the difference?".
If a join was involved to produce such a relation, a designer might find
one statement a more helpful reminder of his own actions than the other
but the extension's value is what matters to users (not to mention
references to the value by other operations). The answer 'fifteen
dollars owed' doesn't reflect whether it is a sum or a difference or
some other calculation. A user who wants to know which customers have
credits doesn't expect the receivables balance to answer the question.
Personally I would give users the simpler predicate, just as I would not
feel obliged to tell them that the answer to '6 + 9' involved a carry
operation.
vldm10
> "paul c" <toledobythe...@oohay.ac> wrote in message
>
> - 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
com...@hotmail.com
> com...@hotmail.com wrote:
> > On Oct 28, 12:51 pm, paul c <toledobythe...@oohay.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
paul c
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.)
Bob Badour
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.
paul c
...
> 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.
Bob Badour
I don't follow that at all.
paul c
> paul c wrote:
...
>> 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.
Bob Badour
I cannot make sense of what you wrote.
com...@hotmail.com
> A sentence is a well-formed formula with no free variables.
Yes, I was wrong.
> 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
paul c
Best I can do at the moment without a clue or two. If Bob B doesn't get
any part of it either there is little point embellishing or possibly I
have lapsed into mysticism, will reserve judgment for now. Oh well,
that's life.
Bob Badour
I suspect you simply do not include enough context to decipher what you
are saying. If I have a relation variable, R, at any given time, its
extension is simply its value. Is it not? Since R can have different
values at different times, it can have more than one extension; albeit,
only one at a time.
paul c
...
> I suspect you simply do not include enough context to decipher what you
> are saying. If I have a relation variable, R, at any given time, its
> extension is simply its value. Is it not? Since R can have different
> values at different times, it can have more than one extension; albeit,
> only one at a time.
Thanks, I'll ponder that. The only comments I want to make right now
are i) that I prefer to avoid talking about relvars until some choice of
language is made, which choice seems premature, eg., I can imagine an
environment where the programmer's context doesn't include assignment,
and ii) I think expressions have a value and extensions have a value
(maybe you are more pertinent saying that they are values, not sure) and
those two values are equivalent in Codd's RM context - my attitude about
equality as far as machines are concerned is that it should be
determined only by typical machine-level comparison instructions which I
hope keeps various language notions of equality out of the picture as
far as interpreting values is concerned. This is perhaps narrower or
stricter than most people want, maybe it's an unnecessary distinction
too but I'd rather be careful about it.
Bob Badour
In logic, a relation is the extension of a predicate, and a predicate is
the characteristic function of a relation. When talking about relational
databases, sometimes one has to be clear about the internal predicate
and the external predicate. At any given time, one will generally find
fewer tuples in any relation variable than the internal predicate would
allow because some parts of the predicate are not amenable to
calculating or to expressing algebraically.
If one has a relational expression, one may derive or calculate a
predicate for that expression, but it will always be the internal
predicate ignoring the external predicate. The dbms has no data about
the external predicate other than the actual tuples in relations. As far
as the dbms is concerned, the value of the relation itself is the
extension of the external predicate.
When you write about extensions of expressions, the phrase is
meaningless. Expressions do not have extensions--predicates do. If you
mean the extension of an expression's predicate, do you mean the
internal predicate? The external predicate? If you mean something else,
please define your terms.
paul c
...
> In logic, a relation is the extension of a predicate, and a predicate is
> the characteristic function of a relation. When talking about relational
> databases, sometimes one has to be clear about the internal predicate
> and the external predicate. At any given time, one will generally find
> fewer tuples in any relation variable than the internal predicate would
> allow because some parts of the predicate are not amenable to
> calculating or to expressing algebraically.
Do you mean certain negations and disjunctions aren't amenable, such as
the predicate "it is not the case that the temperature T in city C is T
degrees"?
(Thanks for the precision, still pondering the rest.)
Bob Badour
No. First, you have T representing 2 different measures so I cannot
understand your example.
I mean the predicate for "Employee, EmpID, manages department, DeptNo"
is too complex to calculate or to represent algebraically. It has all
sorts of complex factors that generally never get recorded anywhere such
as someone had to apply for a job with the company and that person had
to perform well enough to get promoted to management (not necessarily at
this company) etc.
What one can calculate or represent algebraically is much simpler:
DeptNo refers to some Department in the database. EmpID refers to some
Employee in the database. The referenced Employee--as described in the
database--has to meet certain criteria like having a base salary and
exempt status. If the data does not meet those criteria, the dbms will
reject it.
In general, the database describes part of the predicate, called the
internal predicate. The actual predicate (external predicate) has
additional factors not described in the database except for the
extension of the predicate itself: the relation.
In other words, the database does not describe the full predicate from
which one could calculate a relation. How one goes from predicate to
extension is not fully recorded. What is recorded is the extension of
the predicate, as far as the dbms is concerned, and those parts of the
predicate amenable to calculation or to algebraic representation.
The extension is a relation. The internal predicate is the set of
constraints including data types, names, candidate keys, foreign keys
etc. The full predicate is the conjunction of the internal predicate and
some unknown or unrepresented factors.
When you derive a relation via some relational expression, the derived
relation is the extension of some predicate. If the dbms represented
entire predicates, it could calculate that predicate, but the dbms does
not represent entire predicates. The dbms represents internal
predicates, and it can derive an internal predicate for the expression.
The expression is an expression. The calculated value of the expression
is an extension of some predicate. The predicate or characteristic
function of that extension is partially unknown.
paul c
> paul c wrote:
>> Do you mean certain negations and disjunctions aren't amenable, such
>> as the predicate "it is not the case that the temperature T in city C
>> is T degrees"?
>>
>> (Thanks for the precision, still pondering the rest.)
>
> No. First, you have T representing 2 different measures so I cannot
> understand your example.
>
> I mean the predicate for "Employee, EmpID, manages department, DeptNo"
> is too complex to calculate or to represent algebraically. It has all
> sorts of complex factors that generally never get recorded anywhere such
> as someone had to apply for a job with the company and that person had
> to perform well enough to get promoted to management (not necessarily at
> this company) etc.
And thank goodness for that!
Sampo Syreeni
> In general, the database describes part of the predicate, called the
> internal predicate. The actual predicate (external predicate) has
> additional factors not described in the database except for the
> extension of the predicate itself: the relation.
Personally I wouldn't talk about internal and external predicates. I'd
instead go with finite model theory terminology. There we have
theories, encoded in the RM as a finite set of explicit propositions
(the extension of the database) plus a bunch of first order predicate
logic which links together, constrains, and takes precedence to the
propositional extension (the so called intension of the database) in
case inconsistency in the encoded theory was about to arise somehow.
And second, we have real life models those theories try to capture.
In that framework it's easy to see that just about any realistic
database could have multiple real life models. And that including more
identifying features, being stricter with the semantic interpretation
of the theory wrt its models, and modelling constraints which are
actually valid because of physical, societal, etc. reasons within the
theory cause the theory to pick out fewer and fewer real life models.
Ideally, we'd like to make the theory strict enough to necessarily
pick out just one plausible model; that can actually happen when e.g.
every entity we handle has a natural key, and our constraints formally
encode that fact within our theory. This is essentially the reason why
natural keys hold such a prominent place in the theory of consistency
and normalization: they are perhaps the most important mechanism which
translates real world semantics into symbolically manipulable
constraints within our logical model, and so helps guarantee as close
to 1-1 correspondence between encoded propositions and real world
entities as possible.
At the same time, we can independently analyse the theory encapsulated
within the database as an entity separate from the real world models
it might have. This is then where normalization and like concepts come
in. They rely on the semantic correspondence encoded by e.g. natural
keys and the live facts which give rise to cardinality constraints,
inclusion dependencies, and whatnot. But once that source data is
formalized, the logical mechanism from there on in independent. That
then is mostly what we think about when we mention the Relational
Model.
--
Sampo
Cimode
I would be glad to hear how we establish a valid quantifier in
relational algebra using only internal predicates. The lack of
clarification of the external predicate, while being symptomatic
limitation of traditional RM relational theorists gladly recognize,
does not bother them much when it comes to operate relations
algebrically using only the internal predicate. That's where domain
analysis becomes handy...
Regards...
paul c
> ...
> I would be glad to hear how we establish a valid quantifier in
I thought projection is relational algebra's quantifier, are you talking
about something else?
Bob Badour
Projection is one quantifier. Equality (or containment) comparison is
the other.
Cimode
The concept that a relational *operation* (projection) involving a
relation R1 would also serve as a quantifier for the same relation is
a concept I am having difficulties with.
I'd rather have quantifiers defined according to a domain subtyping
(knowing that each un-ary relation attribute is nothing else a domain
subtype associated with both a header and additional relation level
constraints). I found that such approach is more practical to
establish quantifiers through the use of domain intervals in
relationship to cardinality through combinatory analysis.
com...@hotmail.com
> I would be glad to hear how we establish a valid quantifier in
> relational algebra using only internal predicates. The lack of
> clarification of the external predicate, while being symptomatic
> limitation of traditional RM relational theorists gladly recognize,
> does not bother them much when it comes to operate relations
> algebrically using only the internal predicate.
Please read Bob's recent postings and especially my posting of Oct 28
http://groups.google.ca/group/comp.databases.theory/browse_thread/thread/ebd880c6b29cddbd/1cc4b80087f296a2?hl=en#1cc4b80087f296a2
A query evaluates the extension of (ie tuples that satisfy)
a predicate expression (the one corresponding to the query
relation expression) built from external (ie base relation variable)
predicates.
An internal predicate is just a necessary but not necessarily
sufficient constraint on the tuples that can appear in a variable
(evaluated to avoid (some) erroneous inputs).
It has nothing to do with querying.
(I don't even find the notion of internal predicates helpful.
It's the overall database constraint that's important.)
On Nov 5, 3:08 pm, Cimode <cim...@hotmail.com> wrote:
> The concept that a relational *operation* (projection) involving a
> relation R1 would also serve as a quantifier for the same relation is
> a concept I am having difficulties with.
Use of a relation operation in a relation expression corresponds
to use of a connective or quantifier in the corresponding predicate
expression.
Read my referenced message.
Try an example.
It's all so straightforward.
philip
Cimode
I thank you for your response and the effort you have put into
detailing what is an internal predicate or what is an external
predicate is to the the relational model but I believe you are
entirely missing the point I have raised to paul c. See my comments
below
> > I would be glad to hear how we establish a valid quantifier in
> > relational algebra using only internal predicates. The lack of
> > clarification of the external predicate, while being symptomatic
> > limitation of traditional RM relational theorists gladly recognize,
> > does not bother them much when it comes to operate relations
> > algebrically using only the internal predicate.
>
> Please read Bob's recent postings and especially my posting of Oct 28http://groups.google.ca/group/comp.databases.theory/browse_thread/thr...
Will do. I don't spend as much time in cdt as I used to.
> A query evaluates the extension of (ie tuples that satisfy)
> a predicate expression (the one corresponding to the query
> relation expression) built from external (ie base relation variable)
> predicates.
> An internal predicate is just a necessary but not necessarily
> sufficient constraint on the tuples that can appear in a variable
> (evaluated to avoid (some) erroneous inputs).
Yes.
> It has nothing to do with querying.
Who mentionned querying?
> (I don't even find the notion of internal predicates helpful.
> It's the overall database constraint that's important.)
That's because domain constraint analysis has been left out of
relational algebric definition since it was prior to relational model
definition.
> > The concept that a relational *operation* (projection) involving a
> > relation R1 would also serve as a quantifier for the same relation is
> > a concept I am having difficulties with.
>
> Use of a relation operation in a relation expression corresponds
> to use of a connective or quantifier in the corresponding predicate
> expression.
That is precisely the concept I feel unconfortable with. In
traditional algebra, valid quantifiers are values not operations. I
do not see why ra should have the privilege to define its own rules on
that perspective.
> Read my referenced message.
> Try an example.
> It's all so straightforward.
Only if you accept as a premice that an operation can also serve as a
valid quantifier. There are other functions or intervals quantifiers
that can increase the expressive power of algebra but they do require
digging into domain analysis and combinatory analysis.
I do not see for instance how can such premice allow to develop a
computing model for effectively representing data independence in the
context of relation manipulation and operation.
I tend to think from current and past research that such premice leads
to confusion and limits the expressive ability and opportunity to
logically represent relational operations as a part of a turing
complete machine.
But of course that is just my opinion.
> philip
Regards...
Tegiri Nenashi
> ... In traditional algebra, valid quantifiers are values not operations. ...
I don't think there is universally agreed concept of quantifier for
algebra. Carrying over quantifiers from logic, one may suggest that
summation (http://en.wikipedia.org/wiki/Summation), product, infimum,
and supremum are quantifiers (they are essentially generalizations of
binary operations: addition, multiplication, meet, and join,
correspondingly). It is common in algebra to represent qunatified
operation in terms of binary ones; example:
1 + 2 + 3 + 4 + ... + n = n/(1-n)
Likewise, relational calculus quantified expression
exists y : R(x,y)
is essentially a disjunction
R(x,1) <OR> R(x,2) <OR> R(x,3) <OR> ...
(assuming positive integers domain {1,2,3,...} for y). This repeated
application of binary operation evaluates to binary operation: set
intersection join:
D(y) set_intersect R(x,y)
where D(y) is domain of y (which we assumed earlier to be
{1,2,3,...}). The last expression evaluates to projection which is
well known fact, but misses the big idea that universal and
existential quantifiers are dual quantifiers. Logical quantifiers in
algebraic form are set joins (which in some cases evaluate to
projection and relational division).
Cimode
> > ... In traditional algebra, valid quantifiers are values not operations. ...
>
> I don't think there is universally agreed concept of quantifier for
> algebra.
> Carrying over quantifiers from logic, one may suggest that
> summation (http://en.wikipedia.org/wiki/Summation), product, infimum,
> and supremum are quantifiers (they are essentially generalizations of
> binary operations: addition, multiplication, meet, and join,
> correspondingly). It is common in algebra to represent qunatified
> operation in terms of binary ones; example:
>
> 1 + 2 + 3 + 4 + ... + n = n/(1-n)
*function* instead of values. But there is a *significant* difference
between functions and operations since the first can be used as a
variable while the other not: an operation is an operation and a
variable is a variable. I do not see the clarity is an algebra that
uses a similar tool both for operating and quantifying variables.
And that applies to Summation as well. If we'd view Summation as an
algebric expression it is easy to dispute the fact that the variable
sigma is *not* the operation.
> Likewise, relational calculus quantified expression
>
> exists y : R(x,y)
I do not recall talking about calculus. Was exclusively refering to
algebra.
> is essentially a disjunction
>
> R(x,1) <OR> R(x,2) <OR> R(x,3) <OR> ...
>
> (assuming positive integers domain {1,2,3,...} for y). This repeated
> application of binary operation evaluates to binary operation: set
> intersection join:
>
> D(y) set_intersect R(x,y)
>
> where D(y) is domain of y (which we assumed earlier to be
> {1,2,3,...}). The last expression evaluates to projection which is
> well known fact, but misses the big idea that universal and
> existential quantifiers are dual quantifiers. Logical quantifiers in
> algebraic form are set joins (which in some cases evaluate to
> projection and relational division).
Yes. But that does not take away the possibility of having more
effective quantifiers than set joins (while keeping set joins as
operations).
Since combinatory analysis allows to establish that it is impossible
to build a Turing complete machine using such toolset, I particularily
doubt the soundness of goiing such path in the current state of
relational theory need for clarification. These are the kind of
conclusions one reaches when trying to build a computing model for RM.
Regards...
Cimode
uses a similar tool both for operating and quantifying variables. >>
paul c
...
> Likewise, relational calculus quantified expression
>
> exists y : R(x,y)
>
> is essentially a disjunction
>
> R(x,1) <OR> R(x,2) <OR> R(x,3) <OR> ...
In the spirit of the recent precision, it doesn't look to me like
'R(x,1)' et cetera are sets of tuples, which I believe '<OR>' requires.
Shouldn't that '<OR>' be logical 'OR'? Also the result doesn't look
'truth-valued', shouldn't it?
com...@hotmail.com
I'm not sure if I can help you if my last post didn't.
> I thank you for your response and the effort you have put into
Appreciate that.
> > > The concept that a relational *operation* (projection) involving a
> > > relation R1 would also serve as a quantifier for the same relation is
> > > a concept I am having difficulties with.
I don't understand this sentence.
There aren't any quantifiers in the relational algebra.
The quantifiers are in the corresponding predicate expression.
(If you use relational domain or tuple calculus then the calculus
expression looks just like the predicate expression.)
That's why I wrote the quote that follows.
> > Use of a relation operation in a relation expression corresponds
> > to use of a connective or quantifier in the corresponding predicate
> > expression.
>
> That is precisely the concept I feel unconfortable with.
Well I'm sorry, but that's the whole point of the relational algebra.
Following my referenced message, an example.
relation R{X} with predicate PR "blah blah...X..."
relation S{X, Y} iwth predicate PS "foo bah..X...Y..."
Consider relation query expression
RE=((R JOIN S) PROJECT X) UNION RELATION{Y 5}.
As a query this has associated predicate expression
PE=(EXISTS X (PR AND PS)) OR Y=5
Evaluation of RE gives the set of tuples that make PE true,
ie relation RE has predicate PE.
As a constraint you can think of PE as a statement
that must be equivalent to TRUE given the world as
described by the user's new variable values.
So if the corresponding relation result is not
RELATION{}{TUPLE{}}
(corresponding to predicate expression TRUE)
then PE is not equivalent to TRUE and the update is rejected.
(This characterization of constraints involves external predicates,
pace my last post.)
> > > I would be glad to hear how we establish a valid quantifier in
> > > relational algebra using only internal predicates.
I don't understand this.
Maybe you mean quantifier in the sense of
SUM(relation, expression) or or COUNT(relation)
(or that matter (relation WHERE expression)).
These actually involve relational calculus
(pace Date and Darwen).
(But special case EXISTS(relation, attribute) corresponds
to PROJECT OUT in the relational algebra.)
As explained in Tegiri's reply to your post this requires
some extension to the predicate
(and hence domain and tuple) calculus.
To use this notation we don't need to extend the
relational algebra because you can define the meaning
of such quantifier expressions in terms of iterated standard
expressions.
No one is saying the relational algebra can handle this.
But no one is saying you
have to limit yourself to the relational algebra, either.
It's just some math that can do some stuff.
Like predicate calculus or series notations.
> Only if you accept as a premice that an operation can also serve as a
> valid quantifier. There are other functions or intervals quantifiers
> that can increase the expressive power of algebra but they do require
> digging into domain analysis and combinatory analysis.
I don't understand this.
Maybe you mean generic quantifiers as addressed above.
> In
> traditional algebra, valid quantifiers are values not operations I
> do not see why ra should have the privilege to define its own rules on
> that perspective.
I don't understand.
We can define an algebra, ie a collection of values and
operators on them, to act any way we want.
Anyway, the quantifiers are not in the relational algebra,
they are in the corresponding predicate expression.
> > > The lack of
> > > clarification of the external predicate, while being symptomatic
> > > limitation of traditional RM relational theorists gladly recognize,
> > > does not bother them much when it comes to operate relations
> > > algebrically using only the internal predicate.
I don't understand this.
> domain constraint analysis has been left out of
> relational algebric definition since it was prior to relational model
> definition.
I don't know what domain constraint analysis is,
please give a reference.
I suppose you mean domain in the sense of problem domain,
ie the world modelled by the database.
The relational model has nothing to say
about how you establish your predicates.
It's just a way to automatically with a certain complexity
calculate the tuples satisfying a predicate expression
given the tuples satisfying some given predicates.
No one's saying that's all the functionality we'd ever want.
> I do not see for instance how can such premice allow to develop a
> computing model for effectively representing data independence in the
> context of relation manipulation and operation.
I don't understand this.
Having data independence means that changing
the structure but not meaning of data should be easy.
If you express yourself structurally relationally
then new (relational) structure can be described
simply by relational expressions.
> I tend to think from current and past research that such premice leads
> to confusion and limits the expressive ability and opportunity to
> logically represent relational operations as a part of a turing
> complete machine.
The relational algebra was specifically designed so that
1. you could use predicate calculus as a
(non-imperative) programming language and
2. it has a certain reasonable evaluation complexity.
Ie it was designed to have limited expressive ability.
(That's why there are no exact equivalents to NOT and OR
in a relational dbms.)
No one is saying it should do any more.
(To use relational algebra as a non-evaluated notation,
or if your system checks that your queries are "safe",
you can introduce those equivalents.)
If you allow recursion then you leave this complexity.
But people seem to be happy to still consider the dbms relational.
If you allow a certain higher evaluation complexity (resolution)
and a certain restricted notation (Horn clauses)
you get logic programming.
For higher complexity yet you get constraint programming.
Nevertheless relational algebra is still useful for giving
non-imperative semantics for these other systems.
So I guess a lot of your intuitions are right,
but I'd say you don't understand the basic
properties and limitations of the relational model.
(Also, I don't understand most of your post in detail.)
philip
Tegiri Nenashi
'R(x,1)' is a result of substituting y=1 into R(x,y). This is
literally the same trick as substituting n=1 in the term x^(-n) which
is a part of summation
sigma( n={1...inf} , x^(-n) )
We simply substituted sigma with "exists", bind variable n with y, and
left x as free variable in both cases. Moreover, many math books use
the big disjunction symbol "\/" for "exists" in order to emphasize the
idea that existential quantification is merely repeated application of
binary disjunction.
Tegiri Nenashi
> Anyway, the quantifiers are not in the relational algebra,
> they are in the corresponding predicate expression.
The main objective of Algebraic Logic is eliminating the concept of
quantifier. The two success stories are Boolean Algebra (aka
Propositional Calculus in algebraic form) and (Binary) Relation
Algebra (corresponding to some fragment of Predicate Calculus?)
Arguably, there is no ubiquitous algebraic system for Predicate
Calculus despite Tarski, Halmos, and many others exerted quite an
effort. (There is an inspirational essay by Halmos that I posted link
on sci.logic a while ago -- cant find the reference!) Codd's
relational algebra can be considered the first genuine algebraization
of predicate calculus...
Tegiri Nenashi
> ...There is an inspirational essay by Halmos that I posted link
> on sci.logic a while ago...
Here we go:
http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.24.4578&rep=rep1&type=pdf
One especially striking quote:
"I was looking for a dictionary, I believed that one must exist, a
dictionary that would translate the vague words that logicians used to
the precise language of mathematics."
paul c
To say that '<OR>' operates with free variables looks like a flight of
fancy to me. You'll have to substitute out the 'x' too if you want to
use '<OR>' or come up with a new definition for it, otherwise you're
just usurping it to apply to something other than tuples. Why don't you
just use tuple literals for your development? In any event, I don't see
how you can avoid a projection operator which I don't believe can be
defined in terms of the other D&D ops.
Tegiri Nenashi
OK, I shouldn't have written <OR> (to avoid any confusion caused by
reference to D&D "A"lgebra). It was meant to be iterative disjunction
of unary predicates
R(x,1) v R(x,2) v R(x,3) v ...
each obtained from binary predicate R(x,y) by formal substitution of
free variable y with constant. (From RA perspective this substitution
is projection indeed, but this idea is unnecessary -- everything was
meant to be explained in predicate calculus terms).
Tegiri Nenashi
> ...It was meant to be iterative disjunction
> of unary predicates
>
> R(x,1) v R(x,2) v R(x,3) v ...
>
> each obtained from binary predicate R(x,y) by formal substitution of
> free variable y with constant. (From RA perspective this substitution
Oops: it's restriction (join with "y=1") followed by projection to x,
or, more laconic set intersection join:
R(x,1) = R(x,y) <set intersection> "y=1"
Cimode
> On Nov 6, 10:54 am, Cimode <cim...@hotmail.com> wrote:
>
> I'm not sure if I can help you if my last post didn't.
>
> > I thank you for your response and the effort you have put into
>
> Appreciate that.
>
> > > > The concept that a relational *operation* (projection) involving a
> > > > relation R1 would also serve as a quantifier for the same relation is
> > > > a concept I am having difficulties with.
>
> I don't understand this sentence.
> There aren't any quantifiers in the relational algebra.
valid quantifiers that are not solely based on the internal-based
predicates since internal based predicates only partially represent
the relation.
> The quantifiers are in the corresponding predicate expression.
> (If you use relational domain or tuple calculus then the calculus
> expression looks just like the predicate expression.)
Thank you for this explanation.
> That's why I wrote the quote that follows.
>
> > > Use of a relation operation in a relation expression corresponds
> > > to use of a connective or quantifier in the corresponding predicate
> > > expression.
>
> > That is precisely the concept I feel unconfortable with.
>
> Well I'm sorry, but that's the whole point of the relational algebra.
I believe that we just do not have the same premice on what is
sufficient to allow relational algebra to build Turing complete
machine.
Please allow me to rephrase your last sentence to clarify my position:
"that's the whole point of *a* relational algebra which premice that
quantifying an internal predicate is a *sufficient* condition to
algebrically operate relations. I believe that premice is wrong.
I tend to think that relational algebra needs quantifiers based on
some more effective representation of the external predicate. But
that is just my opinion and based on a few years research.
No I mean valid quantifiers for relations.
> As explained in Tegiri's reply to your post this requires
> some extension to the predicate
> (and hence domain and tuple) calculus.
Calculus is a too naive way to provide sufficient expressive power for
building a logical relation representation. Which why I believe that
other mathematical tools are need for such task.(Combinatory Analysis
being one)
> To use this notation we don't need to extend the
> relational algebra because you can define the meaning
> of such quantifier expressions in terms of iterated standard
> expressions.
I do not perceive the work on clarifying relation level quantifiers as
an extension of relational algebra but rather as a part of its
definition.
> No one is saying the relational algebra can handle this.
I claim that it should. I am simply pointing some reasons on why it
can't.
> But no one is saying you
> have to limit yourself to the relational algebra, either.
> It's just some math that can do some stuff.
> Like predicate calculus or series notations.
Well, I believe that we should have the same rigor onto recognizing
the current limitations of relational algebra. I believe that
relational algebra is still on its infancy and needs reclarification.
> > Only if you accept as a premice that an operation can also serve as a
> > valid quantifier. There are other functions or intervals quantifiers
> > that can increase the expressive power of algebra but they do require
> > digging into domain analysis and combinatory analysis.
>
> I don't understand this.
> Maybe you mean generic quantifiers as addressed above.
Perhaps the above explanations have clarified my position.
> > In
> > traditional algebra, valid quantifiers are values not operations I
> > do not see why ra should have the privilege to define its own rules on
> > that perspective.
>
> I don't understand.
See above.
> We can define an algebra, ie a collection of values and
> operators on them, to act any way we want.
> Anyway, the quantifiers are not in the relational algebra,
> they are in the corresponding predicate expression.
>
> > > > The lack of
> > > > clarification of the external predicate, while being symptomatic
> > > > limitation of traditional RM relational theorists gladly recognize,
> > > > does not bother them much when it comes to operate relations
> > > > algebrically using only the internal predicate.
>
> I don't understand this.
See above.
> > domain constraint analysis has been left out of
> > relational algebric definition since it was prior to relational model
> > definition.
>
> I don't know what domain constraint analysis is,
> please give a reference.
Domain analysis is an extension of set theory that are referenced
primarily in Codd's pre-RM work. Domains were the fundation on which
RM was formulated before it became a world of its own .
> I suppose you mean domain in the sense of problem domain,
> ie the world modelled by the database.
> The relational model has nothing to say
> about how you establish your predicates.
> It's just a way to automatically with a certain complexity
> calculate the tuples satisfying a predicate expression
> given the tuples satisfying some given predicates.
That is an IS bias on what relational model and relational algebra
should be. I have a mathematical bias.
> > I do not see for instance how can such premice allow to develop a
> > computing model for effectively representing data independence in the
> > context of relation manipulation and operation.
>
> I don't understand this.
> Having data independence means that changing
> the structure but not meaning of data should be easy.
That is a consequence of data independence and not a cause.
> If you express yourself structurally relationally
> then new (relational) structure can be described
> simply by relational expressions.
Data independence also means that the internal logical representation
of relational operations is Turing Complete to allow a total
dissociation between the layer of operation and the structure of
relations. And I do not see how can that be done without quantifiers
in ra.
> > I tend to think from current and past research that such premice leads
> > to confusion and limits the expressive ability and opportunity to
> > logically represent relational operations as a part of a turing
> > complete machine.
>
> The relational algebra was specifically designed so that
> 1. you could use predicate calculus as a
> (non-imperative) programming language and
Yes.
> 2. it has a certain reasonable evaluation complexity.
> Ie it was designed to have limited expressive ability.
> (That's why there are no exact equivalents to NOT and OR
> in a relational dbms.)
> No one is saying it should do any more.
> (To use relational algebra as a non-evaluated notation,
> or if your system checks that your queries are "safe",
> you can introduce those equivalents.)
>
> If you allow recursion then you leave this complexity.
> But people seem to be happy to still consider the dbms relational.
> If you allow a certain higher evaluation complexity (resolution)
> and a certain restricted notation (Horn clauses)
> you get logic programming.
> For higher complexity yet you get constraint programming.
> Nevertheless relational algebra is still useful for giving
> non-imperative semantics for these other systems.
Nobody disputed the usefulness or soundness of ra. It is because one
believes it is a sound fundation that one spends more time studying it
and eventually pointing out what may be an incoherence in it.
> So I guess a lot of your intuitions are right,
> but I'd say you don't understand the basic
> properties and limitations of the relational model.
Right intuitions come from right assumptions.
> (Also, I don't understand most of your post in detail.)
I apologize for not being able to clarify my thought more clearly.
Some of my posts conclusions here are the conclusions of more than a
decade research effort defining a computing model for RM and attempt
to implement as a Turing Complete Machine. A lot of this work is
orthogonal to ra but reveals a need for further clarification on RM.
And it is difficult to synthetize all the research process in an
online thread.
Regards...
Cimode
> On Nov 6, 5:19 pm, com...@hotmail.com wrote:
>
> > Anyway, the quantifiers are not in the relational algebra,
> > they are in the corresponding predicate expression.
>
> The main objective of Algebraic Logic is eliminating the concept of
> quantifier.
> The two success stories are Boolean Algebra (aka
> Propositional Calculus in algebraic form) and (Binary) Relation
> Algebra (corresponding to some fragment of Predicate Calculus?)
>
> Arguably, there is no ubiquitous algebraic system for Predicate
> Calculus despite Tarski, Halmos, and many others exerted quite an
> effort. (There is an inspirational essay by Halmos that I posted link
> on sci.logic a while ago -- cant find the reference!)
I would be glad to put my hands on it.
> Codd's
> relational algebra can be considered the first genuine algebraization
> of predicate calculus...
I agree. But my belief is Codd's refining process (using domains)
that led to RM final formulation is even more significant because it
allows to add combinatory analysis and probabilism in RM toolset (as
OO crowd would say *by inheritance*) .
Regards.
Cimode
> On Nov 6, 7:11 pm, Tegiri Nenashi <tegirinena...@gmail.com> wrote:
>
> > ...There is an inspirational essay by Halmos that I posted link
> > on sci.logic a while ago...
>
>
> One especially striking quote:
> "I was looking for a dictionary, I believed that one must exist, a
> dictionary that would translate the vague words that logicians used to
> the precise language of mathematics."
The math language is in my research book. I do not have any
experience with publishing.