Re: Codd's Information Principle

On 7 nov, 02:19, com..._at_hotmail.com wrote:
> On Nov 6, 10:54 am, Cimode <cim..._at_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.
Precisely. I am just claiming that relational algebra should have 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.

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

> 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... Received on Sat Nov 07 2009 - 14:18:01 CET