Heading inference, not type inference
Quote from dandl on May 26, 2020, 2:07 pmQuote from Dave Voorhis on May 26, 2020, 9:10 amQuote from dandl on May 26, 2020, 6:00 amQuote from Dave Voorhis on May 25, 2020, 4:10 pmQuote from dandl on May 25, 2020, 2:20 pmQuote from AntC on May 25, 2020, 9:29 amQuote from dandl on May 25, 2020, 3:59 amQuote from Dave Voorhis on May 24, 2020, 9:22 amQuote from dandl on May 24, 2020, 2:13 amAs far as the point I am making in this thread, a grouped attribute value (such as
PQon p23 of DTATRM) is an argument to a selector operator and since both value and selector specify a heading, those headings must be checked (recursively in this case). But it is not necessary to generate a unique type in order to do that. I'm proposing to distinguish the concepts of (strict) type safety from (rule-based) heading compatibility.I'm continuing to not see what's at issue here. "Heading inference, not type inference". This seems like a distinction without a difference. If the compiler is inferring the Heading for all intermediate sub-terms within an expression; what is it not doing that means it's not inferring the type?
In a sense I agree. My proposal is to consider separately the conventional type checking used for the scalar types from the rather unconventional heading inference of the RA operators (which, BTW are never spelled out in TTM or DTATRM, except by reference to TD).
Heading transformations are spelled out in Appendix A of DTATRM, starting with "Now we can define the operators per se."
<NOT>, <REMOVE>, <RENAME>, <AND> and <OR> are formally defined, each explicitly specifying a heading transformation in the form
Hs= ...Then the Tutorial D relational operators are defined in terms of the Appendix A relational algebra, so the semantics of heading transformations are clear.
You're right of course. Obviously I was referring to the main text of DTATRM, but that omission is indeed addressed in App-A. I find it confusing that its main purpose is to define a 'new RA', but its greatest value is these careful definitions of familiar operators.
<OR>, <NOT> are very far from familiar operators, as at the time of writing DTATRM.
It's disappointing that the heading and body definitions are only provided for the 5 proposed new operators.
The operators are claimed to be (more than) relationally complete. The translation from Tutorial D to the core of operators is defined in Appendix A. I would have thought an easy exercise for the reader to give setbuilder specs for any derived operator.
These goals, while of some interest in their own right, are irrelevant to my current pursuit. And no, it's not trivial. You try and do that, particularly for SUMMARIZE and TCLOSE.
SUMMARIZE and TCLOSE are both "short hand" definitions, i.e., functions defined in terms of more primitive operators. There's no need to formally derive the type formula for SUMMARIZE or TCLOSE when a working compiler will do it for you.
TCLOSE is not a shorthand; alteratively, it is a shorthand for while. In either case it is a primitive operation. There is formal treatment of the other 5 operators, but not TCLOSE. I don't think it's at all easy to complete the set. This is an omission.
SUMMARIZE as a shorthand rests on an aggregation primitive that IMO cannot be reproduced by those 5 operators. To be compliant with TTM OO Pre 6 it would have to make use of an iterated aggregate operator; or it would be one of the operators in TD. No attempt has been made to derive either of these.
I have implemented both of these using function relations.
TCLOSE is defined in terms of more primitive operators in Chapter 6 of DTATRM, at the end of the RM Prescription 19 section.
No, that's wrong. The definition of TCLOSE in DTATRM p184 is written as a recursive operator in TD. Recursion is a primitive operation not available from any combination of relational operators. App-A does not acknowledge this. The heading and body in set-builder notation should have been included.
Appendix A treats TCLOSE as primitive from a theoretical point of view, but provides an example of a practical implementation in Tutorial D. That or an equivalent implementation in another language is sufficient to derive its type. It may not have the theoretical elegance you're perhaps looking for, but its certainly pragmatically workable. Indeed, it's how TCLOSE is implemented in Rel.
SUMMARIZE is defined in terms of more primitive operators in Appendix A of DTATRM, starting with the heading "Summarization."
The (type) signatures for aggregation operators like COUNT, SUM, AVG, etc. are not explicitly given but should be self-evident.
App-A proposes that all such operators be replaced by relcons. I can see how to construct the relcon PLUS (leaving aside the issue that it is self-evidently infinite), but I do not see how to construct relcons to fill the roles of COUNT or SUM. App-A does not address this. Perhaps you could show me.
COUNT is SUM of an attribute value 1, and SUM is repeated PLUS. But what is served by forcing some theoretical completeness on definitions that exist only for theoretical purposes?
For the purposes of creating a working language, determining the types of COUNT and SUM is trivial: COUNT is an integer and SUM is the same type as the expression it's summing.
TCLOSE is defined in terms of more primitive operators in Chapter 6 of DTATRM, at the end of the RM Prescription 19 section.
No, that's wrong. The definition of TCLOSE in DTATRM p184 is written as a recursive operator in TD. Recursion is a primitive operation not available from any combination of relational operators. App-A does not acknowledge this. The heading and body in set-builder notation should have been included.
Appendix A treats TCLOSE as primitive from a theoretical point of view, but provides an example of a practical implementation in Tutorial D. That or an equivalent implementation in another language is sufficient to derive its type. It may not have the theoretical elegance you're perhaps looking for, but its certainly pragmatically workable. Indeed, it's how TCLOSE is implemented in Rel.
That was not the question.
- You said TCLOSE is a shorthand. It's not (or not at least a shorthand for any other operators that are part of A).
- App-A gives formal definitions (in the Hs/Bs form) for 5 A operators: NOT, REMOVE, RENAME, AND and OR. It includes TCLOSE in the list but fails to provide a formal definition in that form. This is a serious omission, in my view.
- The informal description provided elsewhere rests on a recursive function, which is precisely the primitive omitted from App-A.
SUMMARIZE is defined in terms of more primitive operators in Appendix A of DTATRM, starting with the heading "Summarization."
The (type) signatures for aggregation operators like COUNT, SUM, AVG, etc. are not explicitly given but should be self-evident.
App-A proposes that all such operators be replaced by relcons. I can see how to construct the relcon PLUS (leaving aside the issue that it is self-evidently infinite), but I do not see how to construct relcons to fill the roles of COUNT or SUM. App-A does not address this. Perhaps you could show me.
COUNT is SUM of an attribute value 1, and SUM is repeated PLUS. But what is served by forcing some theoretical completeness on definitions that exist only for theoretical purposes?
For the purposes of creating a working language, determining the types of COUNT and SUM is trivial: COUNT is an integer and SUM is the same type as the expression it's summing.
Again, we're talking App-A and not implementation. I already know everything I need to about implementing a language (see Andl). [And implementing PLUS is already impossible.]
I say that the relcon approach used by PLUS cannot be used for aggregation. This requires an additional primitive operation not acknowledged by App-A.
Incidentally, WRAP/UNWRAP and GROUP/UNGROUP are also beyond App-A.
The limits of App-A as written are the first order RA, roughly akin to Codd or the SPRJUN in Alice. There are 3 higher order primitives required to replicate the RA as per TD (new value, recursion, aggregation), plus assignment. An acknowledgment of this in the light of writings by others is overdue.
Quote from dandl on May 27, 2020, 12:30 amTCLOSE is defined in terms of more primitive operators in Chapter 6 of DTATRM, at the end of the RM Prescription 19 section.
No, that's wrong. The definition of TCLOSE in DTATRM p184 is written as a recursive operator in TD. Recursion is a primitive operation not available from any combination of relational operators. App-A does not acknowledge this. The heading and body in set-builder notation should have been included.
Appendix A treats TCLOSE as primitive from a theoretical point of view, but provides an example of a practical implementation in Tutorial D. That or an equivalent implementation in another language is sufficient to derive its type. It may not have the theoretical elegance you're perhaps looking for, but its certainly pragmatically workable. Indeed, it's how TCLOSE is implemented in Rel.
That was not the question.
- You said TCLOSE is a shorthand. It's not (or not at least a shorthand for any other operators that are part of A).
- App-A gives formal definitions (in the Hs/Bs form) for 5 A operators: NOT, REMOVE, RENAME, AND and OR. It includes TCLOSE in the list but fails to provide a formal definition in that form. This is a serious omission, in my view.
- The informal description provided elsewhere rests on a recursive function, which is precisely the primitive omitted from App-A.
Yes, TCLOSE is specifically treated in TTM as being shorthand for something like the example given on DTATRM pg #184, but we can presume every relational algebra operator is notionally shorthand for some more primitive operations. I thought the goal was a practical one: to determine the type of various relational algebra operators. For <NOT>, <REMOVE> etc., it's given in the form of heading transformations. It is indeed omitted for TCLOSE, but you could either practically determine it via the example given on page #184, automatically determine it by implementing the example like that on page #184, or derive it simply.
Its omission is hardly a "serious omission", as such "omissions" are typical in textbooks like DTATRM; in some texts prefaced with encouragement like, "Determining the <something> is left as an exercise for the reader."
Remember that DTATRM, DBE, TTM, An Introduction to Database Systems, etc. are not specifications, they are scientific texts. Per the first sentence of the DTATRM preface, "This is a textbook on database management."
Per that same preface, "The ThirdManifesto — the Manifesto for short — is a proposal for a foundation for data and database management systems (DBMSs); it can be seen as an abstract blueprint for the design of a DBMS and the language interface to such a DBMS."
Creation of specifications -- and implementations; equivalent to the specifics that a blueprint (abstract or otherwise) normally omits -- is thus left as an exercise for the reader.
SUMMARIZE is defined in terms of more primitive operators in Appendix A of DTATRM, starting with the heading "Summarization."
The (type) signatures for aggregation operators like COUNT, SUM, AVG, etc. are not explicitly given but should be self-evident.
App-A proposes that all such operators be replaced by relcons. I can see how to construct the relcon PLUS (leaving aside the issue that it is self-evidently infinite), but I do not see how to construct relcons to fill the roles of COUNT or SUM. App-A does not address this. Perhaps you could show me.
COUNT is SUM of an attribute value 1, and SUM is repeated PLUS. But what is served by forcing some theoretical completeness on definitions that exist only for theoretical purposes?
For the purposes of creating a working language, determining the types of COUNT and SUM is trivial: COUNT is an integer and SUM is the same type as the expression it's summing.
Again, we're talking App-A and not implementation. I already know everything I need to about implementing a language (see Andl). [And implementing PLUS is already impossible.]
I say that the relcon approach used by PLUS cannot be used for aggregation. This requires an additional primitive operation not acknowledged by App-A.
Incidentally, WRAP/UNWRAP and GROUP/UNGROUP are also beyond App-A.
The limits of App-A as written are the first order RA, roughly akin to Codd or the SPRJUN in Alice. There are 3 higher order primitives required to replicate the RA as per TD (new value, recursion, aggregation), plus assignment. An acknowledgment of this in the light of writings by others is overdue.
WRAP/UNWRAP and GROUP/UNGROUP are indeed beyond Appendix A, but there's nothing that precludes providing useful features and facilities beyond the scope of Appendix A. The stated goal, as I recall, was to provide a firm foundation for data, not to formally derive a high-level language from one small set of primitive operators covered in an appendix.
Yes, TCLOSE is specifically treated in TTM as being shorthand for something like the example given on DTATRM pg #184, but we can presume every relational algebra operator is notionally shorthand for some more primitive operations. I thought the goal was a practical one: to determine the type of various relational algebra operators. For <NOT>, <REMOVE> etc., it's given in the form of heading transformations. It is indeed omitted for TCLOSE, but you could either practically determine it via the example given on page #184, automatically determine it by implementing the example like that on page #184, or derive it simply.
No, the point of this thread was that you directed me to App-A, specifically the formal specifications on page a.12, which I accept. I have now pointed out that formal specifications are missing for 3 other primitives, the ones underlying EXTEND (new value), TCLOSE (while) and SUMMARIZE (aggregation). There are informal treatments of them, but formal treatments are missing. Your explanations and excuses are pointless, they're just plain missing. That's all.
Incidentally, WRAP/UNWRAP and GROUP/UNGROUP are also beyond App-A.
The limits of App-A as written are the first order RA, roughly akin to Codd or the SPRJUN in Alice. There are 3 higher order primitives required to replicate the RA as per TD (new value, recursion, aggregation), plus assignment. An acknowledgment of this in the light of writings by others is overdue.
WRAP/UNWRAP and GROUP/UNGROUP are indeed beyond Appendix A, but there's nothing that precludes providing useful features and facilities beyond the scope of Appendix A. The stated goal, as I recall, was to provide a firm foundation for data, not to formally derive a high-level language from one small set of primitive operators covered in an appendix.
Stated goals of App-A are:
- to describe a 'new relational algebra'
- to act as an 'obvious precursor to D'
- 'all of the relational operators of Tutorial D to be mappable to expressions in A'.
It fails to fullfil this last goal unless there are formal treatments of those 3 additional primitives. With them, I think it's all covered.
Quote from dandl on May 28, 2020, 2:39 amYes, TCLOSE is specifically treated in TTM as being shorthand for something like the example given on DTATRM pg #184, but we can presume every relational algebra operator is notionally shorthand for some more primitive operations. I thought the goal was a practical one: to determine the type of various relational algebra operators. For <NOT>, <REMOVE> etc., it's given in the form of heading transformations. It is indeed omitted for TCLOSE, but you could either practically determine it via the example given on page #184, automatically determine it by implementing the example like that on page #184, or derive it simply.
No, the point of this thread was that you directed me to App-A, specifically the formal specifications on page a.12, which I accept. I have now pointed out that formal specifications are missing ...
What chiefly seems to be missing is David's imagination/understanding. Appendix A does most of the heavy lifting; more than enough for its expressed purpose; don't expect to be spoon-fed everything; it's reasonable to leave some of the dark corners as exercises for the reader.
for 3 other primitives, the ones underlying EXTEND (new value), ...
Disagree. You've been making this bogus claim about "new value" for years; and everybody (who could be bothered) has been disagreeing for years. All that's happened is you've exhausted everybody's patience. There's a section titled "Dispensing with restrict (WHERE), EXTEND, ...". You'd be on much firmer ground if you said that the method Appendix A uses to dispense with EXTEND relies on either RENAME or (what I've called) 'equi-relations' as a primitive; and that that is not fully worked out.
... TCLOSE (while) ...
I'll leave Dave to respond on that.
... and SUMMARIZE (aggregation).
Disagree. The EXTEND mechanism is fine; presuming a PLUS-alike over the RVAs produced from GROUP.
There are informal treatments of them, but formal treatments are missing. Your explanations and excuses are pointless, they're just plain missing. That's all.
Don't be so rude. Pull your head in.
Incidentally, WRAP/UNWRAP and GROUP/UNGROUP are also beyond App-A.
The limits of App-A as written are the first order RA, roughly akin to Codd or the SPRJUN in Alice. There are 3 higher order primitives required to replicate the RA as per TD (new value, recursion, aggregation), plus assignment. An acknowledgment of this in the light of writings by others is overdue.
WRAP/UNWRAP and GROUP/UNGROUP are indeed beyond Appendix A, but there's nothing that precludes providing useful features and facilities beyond the scope of Appendix A. The stated goal, as I recall, was to provide a firm foundation for data, not to formally derive a high-level language from one small set of primitive operators covered in an appendix.
Stated goals of App-A are:
- to describe a 'new relational algebra'
- to act as an 'obvious precursor to D'
- 'all of the relational operators of Tutorial D to be mappable to expressions in A'.
It fails to fullfil this last goal ...
Disagree. "mappable" is not a claim that you're going to get spoon-fed all the mappings right here in Appendix A. You might need to do some interpretation -- possibly even actually think for yourself.
... unless there are formal treatments of those 3 additional primitives. With them, I think it's all covered.
Quote from Dave Voorhis on May 27, 2020, 2:57 pm
WRAP/UNWRAP and GROUP/UNGROUP are indeed beyond Appendix A, but there's nothing that precludes providing useful features and facilities beyond the scope of Appendix A. The stated goal, as I recall, was to provide a firm foundation for data, not to formally derive a high-level language from one small set of primitive operators covered in an appendix.
To try to get something useful out of this so far mostly pointless thread ... What primitives might we need for A to cater for WRAP, GROUP? My starter for ten:
Considering DTATRM p46
SP3 WRAP ( { P#, QTY } AS PQ )translates to(SP3 EXTEND {PQ := TUP{P# P#, QTY QTY}}) {ALL BUT P#, QTY}
The TUP{ } constructor selector there is Tutorial D, but not a primitive in A. So we need to add it. This doesn't undermine the claim that A is relationally complete, because Codd 1972 (in defining 'relationally complete') also doesn't include any way to construct Tuple or Relation constants/literals. The EXTEND, per Appendix A, translates to a JOIN to a PLUS-alike relcon. The heading of the relcon is {P# P#, QTY QTY, PQ TUP{P# P#, QTY QTY}} -- heading obtained by mashing together SPT2, SPT3 on p46. The relcon contains every P#, QTY, PQ subject to the constraint P# == P# FROM PQ AND QTY == QTY FROM PQ.
Considering DTATRM p43
SP GROUP ( { P#, QTY } AS PQ )translates toSP{S#} EXTEND {PQ := ((SP JOIN REL{TUP{S# S#}}) {P#, QTY})}
The REL{TUP{ }} constructor selectors there are Tutorial D, but not primitives in A. So we need to add them. This doesn't undermine the claim that A is relationally complete, because Codd 1972 also doesn't include any way to construct Tuple or Relation constants/literals. In the REL{TUP{S# S#}}, the S# is free, so this is an 'open expression' binding to the S# from the outer SP. The EXTEND translates to something it's too late at night to get my head round ...
Quote from AntC on May 28, 2020, 11:01 amQuote from dandl on May 28, 2020, 2:39 amYes, TCLOSE is specifically treated in TTM as being shorthand for something like the example given on DTATRM pg #184, but we can presume every relational algebra operator is notionally shorthand for some more primitive operations. I thought the goal was a practical one: to determine the type of various relational algebra operators. For <NOT>, <REMOVE> etc., it's given in the form of heading transformations. It is indeed omitted for TCLOSE, but you could either practically determine it via the example given on page #184, automatically determine it by implementing the example like that on page #184, or derive it simply.
No, the point of this thread was that you directed me to App-A, specifically the formal specifications on page a.12, which I accept. I have now pointed out that formal specifications are missing ...
What chiefly seems to be missing is David's imagination/understanding. Appendix A does most of the heavy lifting; more than enough for its expressed purpose; don't expect to be spoon-fed everything; it's reasonable to leave some of the dark corners as exercises for the reader.
for 3 other primitives, the ones underlying EXTEND (new value), ...
Disagree. You've been making this bogus claim about "new value" for years; and everybody (who could be bothered) has been disagreeing for years. All that's happened is you've exhausted everybody's patience. There's a section titled "Dispensing with restrict (WHERE), EXTEND, ...". You'd be on much firmer ground if you said that the method Appendix A uses to dispense with
EXTENDrelies on eitherRENAMEor (what I've called) 'equi-relations' as a primitive; and that that is not fully worked out.... TCLOSE (while) ...
I'll leave Dave to respond on that.
Nah. My patience is exhausted.
for 3 other primitives, the ones underlying EXTEND (new value), ...
Disagree. You've been making this bogus claim about "new value" for years; and everybody (who could be bothered) has been disagreeing for years. All that's happened is you've exhausted everybody's patience. There's a section titled "Dispensing with restrict (WHERE), EXTEND, ...". You'd be on much firmer ground if you said that the method Appendix A uses to dispense with
EXTENDrelies on eitherRENAMEor (what I've called) 'equi-relations' as a primitive; and that that is not fully worked out.
No, it's not RENAME, that's adequately covered. The problem is relcons.
As far as I'm concerned the relcon section is a thought experiment, on how the rest of the RA might interface with something that generated new values. It falls short of formality, and it does not address the question of how the values populating a relcon come to be. Obviously they could never be written out as a literal, so they must be calculated. In that sense they correspond precisely with the 'algorithmic' relations of HHT, and they comply with the 'new value' description in Alice. A formal treatment would show that this is so.
I'm sorry if you don't see that, but I don't see what else I can say that would change your mind. A deep reading of Alice might help.
... TCLOSE (while) ...
I'll leave Dave to respond on that.
He won't. He thinks it's solved by dropping out of the RA and into a separate language that supports recursion. But that's precisely the point: the extra primitive required is recursion. See Alice.
... and SUMMARIZE (aggregation).
Disagree. The
EXTENDmechanism is fine; presuming aPLUS-alike over the RVAs produced fromGROUP.
That's circular. RVAs and GROUP rely on aggregation, aggregation relies on RVAs. Neither of them can be built out of the other primitives. But again, you don't see that. Alice s5.5 is brief, but helpful in understanding this.
Stated goals of App-A are:
- to describe a 'new relational algebra'
- to act as an 'obvious precursor to D'
- 'all of the relational operators of Tutorial D to be mappable to expressions in A'.
It fails to fullfil this last goal ...
Disagree. "mappable" is not a claim that you're going to get spoon-fed all the mappings right here in Appendix A. You might need to do some interpretation -- possibly even actually think for yourself.
The point, which I think you miss, is that a formal treatment would show that the claim is false. The RA of App-A with its 5 (or even 6) operators falls short.
Quote from AntC on May 28, 2020, 12:38 pmQuote from Dave Voorhis on May 27, 2020, 2:57 pm
WRAP/UNWRAP and GROUP/UNGROUP are indeed beyond Appendix A, but there's nothing that precludes providing useful features and facilities beyond the scope of Appendix A. The stated goal, as I recall, was to provide a firm foundation for data, not to formally derive a high-level language from one small set of primitive operators covered in an appendix.
To try to get something useful out of this so far mostly pointless thread ... What primitives might we need for A to cater for
WRAP, GROUP? My starter for ten:Considering DTATRM p46
SP3 WRAP ( { P#, QTY } AS PQ )translates to(SP3 EXTEND {PQ := TUP{P# P#, QTY QTY}}) {ALL BUT P#, QTY}The
TUP{ }constructorselector there is Tutorial D, but not a primitive in A. So we need to add it. This doesn't undermine the claim that A is relationally complete, because Codd 1972 (in defining 'relationally complete') also doesn't include any way to construct Tuple or Relation constants/literals. TheEXTEND, per Appendix A, translates to aJOINto aPLUS-alike relcon. The heading of the relcon is{P# P#, QTY QTY, PQ TUP{P# P#, QTY QTY}}-- heading obtained by mashing together SPT2, SPT3 on p46. The relcon contains everyP#, QTY, PQsubject to the constraintP# == P# FROM PQ AND QTY == QTY FROM PQ.
Corrections: The words you quoted are not mine. In the references I have, Codd does not acknowledge the independent existence of tuples in any sense, nor the existence of RVAs. He does construct literal relations, but nothing calculated (except perhaps the boolean values computed by restriction).
Yes, you can construct and deconstruct a TVA by joining with a suitably construct 'relcon'. So that just leaves the primitive required to populate the 'relcon' (which obviously cannot be a literal). The TUP{} expression here is a new value (did not already exist in the database), and requires a primitive to create.
Considering DTATRM p43
SP GROUP ( { P#, QTY } AS PQ )translates toSP{S#} EXTEND {PQ := ((SP JOIN REL{TUP{S# S#}}) {P#, QTY})}The
REL{TUP{ }}constructorselectors there are Tutorial D, but not primitives in A. So we need to add them. This doesn't undermine the claim that A is relationally complete, because Codd 1972 also doesn't include any way to construct Tuple or Relation constants/literals. In theREL{TUP{S# S#}}, theS#is free, so this is an 'open expression' binding to theS#from the outerSP. TheEXTENDtranslates to something it's too late at night to get my head round ...
Yes, App-A is 'relationally complete' as per Codd, but falls short of being 'TD-complete'. And yes, I can read the code, I know how it works, Andl already does this.
So the 'relcon' here would be one with an RVA. The regular new value primitive that supports App-A 'relcons' doesn't do this, you need an aggregation primitive. The mechanism here by which the outer S# binds to the REL{} function shown here is an aggregation function.
The reason (in general) that aggregation is different is that the argument to the aggregating function is a bag, not a set. Rather than introducing bags into the mix, you can either go with the iterated function as per OO Pre 6 or the 'aggregate function' method outlined in Alice.
Quote from dandl on May 29, 2020, 1:33 am
I'm sorry if you don't see that, but I don't see what else I can say that would change your mind. A deep reading of Alice might help.
Alice is a different text, taking a different approach. You've been reading too much Alice and expecting its approach to appear in just the same form in TTM/Appendix A. Stop reading Alice; try harder to read the TTM texts in their own terms.