 | |
#51
 
| |||
| |||
|
Re: Codd's Information Principle -
11-06-2009
, 10:11 PM
|
Anyway, the quantifiers are not in the relational algebra, they are in the corresponding predicate expression. |
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...
#52
| |||
| |||
|
|
...There is an inspirational essay by Halmos that I posted link on sci.logic a while ago... |
http://citeseerx.ist.psu.edu/viewdoc...=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."
#53
| |||
| |||
|
|
On Nov 6, 5:08 pm, paul c <toledobythe... (AT) oohay (DOT) ac> wrote: Tegiri Nenashi wrote: ... 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? '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. |
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.
#54
| |||
| |||
|
|
Tegiri Nenashi wrote: On Nov 6, 5:08 pm, paul c <toledobythe... (AT) oohay (DOT) ac> wrote: Tegiri Nenashi wrote: ... 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? *'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. 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. * |
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).
#55
| |||
| |||
|
|
...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... |
or, more laconic set intersection join:
R(x,1) = R(x,y) <set intersection> "y=1"
#56
| |||||||||||||||||||
| |||||||||||||||||||
|
|
On Nov 6, 10:54 am, Cimode <cim... (AT) hotmail (DOT) 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. Precisely. I am just claiming that relational algebra should have |
predicates since internal based predicates only partially represent
the relation.
Quote:
|
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. |
Quote:
|
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 |
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.
Quote:
|
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.) No I mean valid quantifiers for relations. |
Quote:
|
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 |
other mathematical tools are need for such task.(Combinatory Analysis
being one)
Quote:
|
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 |
definition.
Quote:
|
No one is saying the relational algebra can handle this. I claim that it should. I am simply pointing some reasons on why it |
Quote:
|
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 |
relational algebra is still on its infancy and needs reclarification.
Quote:
|
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. |
Quote:
|
*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. |
Quote:
|
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. |
Quote:
|
*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 |
RM was formulated before it became a world of its own .
Quote:
|
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 |
Quote:
|
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. |
Quote:
|
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 |
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.
Quote:
|
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. |
Quote:
|
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 |
and eventually pointing out what may be an incoherence in it.
Quote:
|
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. |
Quote:
|
(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...
#57
| |||
| |||
|
|
On Nov 6, 5:19*pm, com... (AT) hotmail (DOT) 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. True but in the context of RM, algebra is a tool not an end motive. |
Quote:
|
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. |
Quote:
|
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) |
allows to add combinatory analysis and probabilism in RM toolset (as
OO crowd would say *by inheritance*) .
Regards.
#58
| |||
| |||
|
|
On Nov 6, 7:11*pm, Tegiri Nenashi <tegirinena... (AT) gmail (DOT) com> wrote: ...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...1.24.4578&rep=... 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." Hi hi hi... |
The math language is in my research book. I do not have any
experience with publishing.
 |
« Previous Thread
|
Next Thread »
| Thread Tools | |
| Display Modes | |
Linear Mode
| |
Powered by vBulletin Version 3.5.3
Copyright ©2000 - 2012, Jelsoft Enterprises Ltd.
Copyright ©2000 - 2012, Jelsoft Enterprises Ltd.