The Forum for Discussion about The Third Manifesto and Related Matters

Please or Register to create posts and topics.

Heading inference, not type inference

Quote from dandl on May 29, 2020, 2:30 am
Quote from AntC on May 28, 2020, 12:38 pm
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.

Corrections: The words you quoted are not mine.

Correction: clearly those words are quoted from Dave. Your name does not appear in my post -- except as a palimpsest from the "mostly pointless".

 

If I understand where this thread began, it's with the point that there are an infinite number of relation types, because each relation can have an arbitrary number of attributes and there are an arbitrary number of attribute types (including relation types).  Therefore, no nominal typing system like Java's or C#'s can capture them all, and a structural type system like Algol 68's is needed.  Fortunately, it doesn't have to be turtles all the way down, because there is no way to construct a recursive relation (one that contains itself as a value).

What is more, in TD when you declare a relational variable that lives in your program and not the database, you must either give a structural type using REL{} (possibly nested) or use SAME TYPE AS.  There is no way to name a specific relation type that I can find.


Algorithmic relations need not have a function underlying them: For example, a relation SQRT whose attributes are ROOT, SQUARE1, and SQUARE2 with the obvious semantics has three candidate keys, because if you know the value of one attribute, you know the value of the other two.

 

Quote from johnwcowan on September 21, 2020, 9:04 pm

If I understand where this thread began, it's with the point that there are an infinite number of relation types, because each relation can have an arbitrary number of attributes and there are an arbitrary number of attribute types (including relation types).  Therefore, no nominal typing system like Java's or C#'s can capture them all, and a structural type system like Algol 68's is needed.  Fortunately, it doesn't have to be turtles all the way down, because there is no way to construct a recursive relation (one that contains itself as a value).

Not so. My proposition is that there is exactly one relation type and exactly one tuple type, and that is easily captured by any programming language. Every relation or tuple value has an associated heading, which is a set of strings. Operators perform heading inference, not type inference. Structural types are an unnecessary complication.

What is more, in TD when you declare a relational variable that lives in your program and not the database, you must either give a structural type using REL{} (possibly nested) or use SAME TYPE AS.  There is no way to name a specific relation type that I can find.

Yes, you can only create values of a type, not the types themselves.


Algorithmic relations need not have a function underlying them: For example, a relation SQRT whose attributes are ROOT, SQUARE1, and SQUARE2 with the obvious semantics has three candidate keys, because if you know the value of one attribute, you know the value of the other two.

The only way I can see to formally define such a thing is by recourse to both the function and its inverse. So you need two functions, not zero.

 

 

Andl - A New Database Language - andl.org
Quote from dandl on September 22, 2020, 12:47 am

Not so. My proposition is that there is exactly one relation type and exactly one tuple type, and that is easily captured by any programming language.

The number of types that exist are a property of the programming language, not of the domain of discourse.  Some languages have only one numeric type, some have two, Common Lisp has eight.  But in TD relations are the same type iff they are unionable.

Every relation or tuple value has an associated heading, which is a set of strings.

A heading is a mapping from attribute names to attribute types.


Algorithmic relations need not have a function underlying them: For example, a relation SQRT whose attributes are ROOT, SQUARE1, and SQUARE2 with the obvious semantics has three candidate keys, because if you know the value of one attribute, you know the value of the other two.

That should have been SQUARE, ROOT1, and ROOT2, of course.

The only way I can see to formally define such a thing is by recourse to both the function and its inverse. So you need two functions, not zero.

Where's the problem?  If you know ROOT1, then ROOT2 is its negation and vice versa.  If you know SQUARE, then ROOT1 and ROOT2 are the non-negative square root and its negation respectively.  The only reason it's "not a function" is that functions are generally defined to return only one value, but that's not necessarily true.

Quote from johnwcowan on September 22, 2020, 1:56 am
Quote from dandl on September 22, 2020, 12:47 am

Not so. My proposition is that there is exactly one relation type and exactly one tuple type, and that is easily captured by any programming language.

The number of types that exist are a property of the programming language, not of the domain of discourse.  Some languages have only one numeric type, some have two, Common Lisp has eight.  But in TD relations are the same type iff they are unionable.

TTM is a proposal for a type system, around which a programming language is to be built. In my proposal, the RA is supported by a single relation type and a single tuple type. There are no limits on what other types the language might support, or for what purpose.

Every relation or tuple value has an associated heading, which is a set of strings.

A heading is a mapping from attribute names to attribute types.

You're mistaken. I know what my proposal says, and it says set of strings.


Algorithmic relations need not have a function underlying them: For example, a relation SQRT whose attributes are ROOT, SQUARE1, and SQUARE2 with the obvious semantics has three candidate keys, because if you know the value of one attribute, you know the value of the other two.

That should have been SQUARE, ROOT1, and ROOT2, of course.

The only way I can see to formally define such a thing is by recourse to both the function and its inverse. So you need two functions, not zero.

Where's the problem?  If you know ROOT1, then ROOT2 is its negation and vice versa.  If you know SQUARE, then ROOT1 and ROOT2 are the non-negative square root and its negation respectively.  The only reason it's "not a function" is that functions are generally defined to return only one value, but that's not necessarily true.

Where's the solution? Computer software doesn't 'know' anything. Either you show working software, from which a design and set of formal principles can be deduced, or you show the formal basis on which a design and implementation can be based. I can do that for functions, but not for stuff you just 'know'. I can do that for your SQUARE based on two functions, and in general for all such cases where a function has an inverse.

A function returning two values is not a problem, but how would you deal with trig functions such as SIN()?

 

Andl - A New Database Language - andl.org
Quote from dandl on September 22, 2020, 3:48 am

TTM is a proposal for a type system, around which a programming language is to be built. In my proposal, the RA is supported by a single relation type and a single tuple type.

Okay, so your proposal is a different type system from TTM: by all means.  (In which case, why are we discussing it here?  But no matter, I'm not a stickler for on-topic.)

You're mistaken. I know what my proposal says, and it says set of strings.

Which means the attribute values in the tuples are of any type?

 

Where's the solution? Computer software doesn't 'know' anything.

By "know", I mean of course that given one of the three attributes, the values of the other two can be determined.

A function returning two values is not a problem, but how would you deal with trig functions such as SIN()?

Again, I see no difficulty.  There will be one tuple for each sine-arcsine pair.

Something I meant to mention earlier is that algorithmic relations like this aren't infinite in TTM, beecause every TTM scalar type is specifically restricted to be finite.  The second paragraph of DTATRM chapter 3 says: "So what is a type? Essentially, it is a named, finite set of values."  What the story is in your non-TTM type system, I don't know.

Quote from johnwcowan on September 22, 2020, 4:09 am
Quote from dandl on September 22, 2020, 3:48 am

TTM is a proposal for a type system, around which a programming language is to be built. In my proposal, the RA is supported by a single relation type and a single tuple type.

Okay, so your proposal is a different type system from TTM: by all means.  (In which case, why are we discussing it here?  But no matter, I'm not a stickler for on-topic.)

My proposal is for a modest change to TTM, to achieve exactly the same end goals but with a type system that is more compatible with existing languages.

You're mistaken. I know what my proposal says, and it says set of strings.

Which means the attribute values in the tuples are of any type?

Absolutely not. Values have types, headings do not. A relation of POINT{int X,int Y} has a heading of {X,Y} and a type of relation. When a relation value is created the mapping of heading to attribute types is fixed for that value, but not before. Operators do heading inference and type checking, but not type inference. Life is simpler.

Where's the solution? Computer software doesn't 'know' anything.

By "know", I mean of course that given one of the three attributes, the values of the other two can be determined.

By an algorithm, I presume, but one that is not a function. Then what is it?

A function returning two values is not a problem, but how would you deal with trig functions such as SIN()?

Again, I see no difficulty.  There will be one tuple for each sine-arcsine pair.

Sorry, I really don't understand what you're proposing. The domain of SIN() is infinite -- you can't prefill a table. The range of ARCSINE() is limited -- it will never return all the values that are input to SIN(). One way or another you finish up having to treat these as two separate functions, regardless of how you go about it.

Something I meant to mention earlier is that algorithmic relations like this aren't infinite in TTM, beecause every TTM scalar type is specifically restricted to be finite.  The second paragraph of DTATRM chapter 3 says: "So what is a type? Essentially, it is a named, finite set of values."  What the story is in your non-TTM type system, I don't know.

Best to check the latest version -- they changed that. TTM now says:

RM Prescription 1 was further revised in February, 2013. Previously, the first sentence of this Prescription
had been “A scalar data type (scalar type for short) is a named, finite set of scalar values (scalars for
short).” We have removed the word “finite” because it proved to be controversial. We included that word
originally because in practice the set of values that can be supported is constrained by the available
memory space, which is finite.

 

 

Andl - A New Database Language - andl.org
Quote from dandl on September 22, 2020, 5:52 am
Quote from johnwcowan on September 22, 2020, 4:09 am
Quote from dandl on September 22, 2020, 3:48 am

TTM is a proposal for a type system, around which a programming language is to be built. In my proposal, the RA is supported by a single relation type and a single tuple type.

Okay, so your proposal is a different type system from TTM: by all means.  (In which case, why are we discussing it here?  But no matter, I'm not a stickler for on-topic.)

My proposal is for a modest change to TTM, to achieve exactly the same end goals but with a type system that is more compatible with existing languages.

At, if I recall correctly, the expense of weakening type-safety.

Also, defining a heading as a set of strings, etc., is a particular implementation idea only appropriate to certain (rather limited) implementation target languages.

It shouldn't be a change to the model, which is sound.

I'm the forum administrator and lead developer of Rel. Email me at dave@armchair.mb.ca with the Subject 'TTM Forum'. Download Rel from https://reldb.org
Quote from Dave Voorhis on September 22, 2020, 8:53 am
Quote from dandl on September 22, 2020, 5:52 am
Quote from johnwcowan on September 22, 2020, 4:09 am
Quote from dandl on September 22, 2020, 3:48 am

TTM is a proposal for a type system, around which a programming language is to be built. In my proposal, the RA is supported by a single relation type and a single tuple type.

Okay, so your proposal is a different type system from TTM: by all means.  (In which case, why are we discussing it here?  But no matter, I'm not a stickler for on-topic.)

My proposal is for a modest change to TTM, to achieve exactly the same end goals but with a type system that is more compatible with existing languages.

At, if I recall correctly, the expense of weakening type-safety.

Also, defining a heading as a set of strings, etc., is a particular implementation idea only appropriate to certain (rather limited) implementation target languages.

It shouldn't be a change to the model, which is sound.

As far as I can see, the weaknesses you have in mind are in the implementation based on common existing languages, not in the model. And yes, it would be better to refer to the heading as a 'set of attribute names' as per TTM, rather than specifically a set of strings. The proposed model is sound.

Andl - A New Database Language - andl.org
Quote from dandl on September 22, 2020, 1:20 pm
Quote from Dave Voorhis on September 22, 2020, 8:53 am
Quote from dandl on September 22, 2020, 5:52 am
Quote from johnwcowan on September 22, 2020, 4:09 am
Quote from dandl on September 22, 2020, 3:48 am

TTM is a proposal for a type system, around which a programming language is to be built. In my proposal, the RA is supported by a single relation type and a single tuple type.

Okay, so your proposal is a different type system from TTM: by all means.  (In which case, why are we discussing it here?  But no matter, I'm not a stickler for on-topic.)

My proposal is for a modest change to TTM, to achieve exactly the same end goals but with a type system that is more compatible with existing languages.

At, if I recall correctly, the expense of weakening type-safety.

Also, defining a heading as a set of strings, etc., is a particular implementation idea only appropriate to certain (rather limited) implementation target languages.

It shouldn't be a change to the model, which is sound.

As far as I can see, the weaknesses you have in mind are in the implementation based on common existing languages, not in the model. And yes, it would be better to refer to the heading as a 'set of attribute names' as per TTM, rather than specifically a set of strings. The proposed model is sound.

I mean the TTM model's heading is sound. It needs no changes.

I'm the forum administrator and lead developer of Rel. Email me at dave@armchair.mb.ca with the Subject 'TTM Forum'. Download Rel from https://reldb.org