The Forum for Discussion about The Third Manifesto and Related Matters

You need to log in to create posts and topics.

Defining a function relation by means of a heading

12

A function relation is a relation that can appear in a relational expression as an argument to a relational operator. The declaration of an FR requires only a heading. The definition is supplied by an implementation written in some other language.

The simplest example is the select FR.

  • It will appear as one argument of the semijoin (MATCHES) operator.
  • It must declare a heading that is a subset of the other argument (which guarantees join compatibility).
  • It must implement a function that takes the values for those attributes as arguments and returns a boolean value.
  • The semijoin operator will interpret the return value to indicate whether the matching tuple exists or not.

And that's all there is. A similar strategy deals with the creation of new values (EXTEND) and with aggregation. The type system that deals with attribute types is confined to the implementing function, in whatever language is convenient.

Andl - A New Database Language - andl.org

Logically speaking there is nothing wrong with this. Practically speaking it is contrary to the undefined logical model assumed by tutorial D and appendix A as espoused by this group.

Regarding "definition ... implemention ... in some other language", the equivalences in the logically valid formula:

∃a∃b∃c(((Pa∧Qb∧Rc)↔(¬(Pa∧Qb)↔(Pa∧Qb∧¬Rc))))

must be denied by that mysterious model.

Instead, a number of valid but non-equivalent logical implications are assumed, typified by:

∃a∃b((Pb∧Qb)→(¬(Pa∧Qb)↔(¬Pa∨¬Qb)))

which ignores the situation where Rc represents a common projection of Codd's natural join expressed by (Pa∧Qb∧Rc) on the unproven basis that such a situation is "nonsense" according to at least one author, "gibberish" according to one TTM promoter and requires "runtime exceptions" according to another acolyte. Unlike the first formula this formula has only one equivalence, not two.

While a logically valid implication, this second formula with (Pb∧Qb) introduced as a substitute internal representation for (Pa∧Qb∧Rc) creates what Codd would have called a point of ambiguity because there is not necessarily a possible internal representation for each of the sub-formulas implied by the logical formula.

For example,

∃a∃b((Pb∧Qb)→(¬(Pa∧Qb)→(¬Pa∨Qb)))

is just one of the valid implications that make some conclusions ambiguous. This is a consequence of dbms designers assuming that an end-user's table determines dbms internal representation even though logic dictates otherwise.

Codd's application of his specialized logic required that a practical relation value be represented as a finite subset of a cartesion product of domains. That requirement makes the relation expressed as the sub-formula (¬Pa∨Qb) with its a and b terms represented in a single tuple impossible.

The logical mistake can be characterized as premature evaluation of De Morgan's laws. Thanks to CJ Date the pathology of the mistake is voluminous, including the logically fuzzy notion of external predicates compared to internal predicates when what should be compared are what Codd called internal representations. The very first sentence in the 1970 paper required that users must be protected from internal representations.

There is much more to that pathology including the ernest coder's curse of assuming theory from implementation or prescribed implementation but leaving that aside, it should be obvious that internal representations based on TTM's types, such as the type of its <dyadic join> are not logical representations when an implementation permits the substition of (Pa∧Qb) for (Pa∧Qb∧Rc).

That substitution permits the further mistake of inferring predicates from types and thinking values don't matter even though it is only extensions and logical formulas that can make a predicate true and express a formal model.

Codd understood the formal difference between the above formulas and so did Ian Heath in 1971. It seems likely that 20 years earlier so did Claude Shannon, Louise Chin and Alfred Tarski, probably George Boole and Augie D Morgan a hundred years earlier would have too if they had used different notation.

TTM and appendix A are not all mistakes. The first formula can be re-written in logically valid form as:

∃a∃b∃c((Pa∧Qb∧Rc)↔(¬(Pa∧Qb)↔((Pa∧¬(Pa∧Rc))∧(Qb∧¬(Qb∧Rc)))))

which preserves the two equivalences and introduces the practcal need for relative complement, an operation defined on connectives which tutorial D calls <minus>.

Codd also recognized that

∃a∃b∃c((Pa∧Qb∧Rc)→((Pa∨Qb)↔(¬Pa∨Qb∨¬Rc)))

is valid. Likewise any two of Pa Qb Rc negated in the formula (Pa∨Qb∨Rc) so some implications of a union are ambiguous. Again there is only one equivalence.

Apparently he didn't point out that this particular union ambiguity has a practcal advantage when used to deny a step in the "backchain" he described later which an implementation can use to prove an inverse function when the backchain has equivalences as opposed to implications.

Inverse functions are needed if the day ever comes when the usefulness of automating the comparison of different data designs is realised, whether that be for applying equivalent optimizations or proving the correctness of a flight simulator, let alone recognizing that various base relvar operations are logically ambiguous and therefore incomplete.

Quote from dandl on May 23, 2020, 9:38 am

A function relation is a relation that can appear in a relational expression as an argument to a relational operator. The declaration of an FR requires only a heading. The definition is supplied by an implementation written in some other language.

Can you give some example code for this proposal?

Quote from Darren Duncan on May 25, 2020, 6:23 am
Quote from dandl on May 23, 2020, 9:38 am

A function relation is a relation that can appear in a relational expression as an argument to a relational operator. The declaration of an FR requires only a heading. The definition is supplied by an implementation written in some other language.

Can you give some example code for this proposal?

I'm still working on it, but something like this at present:

var si = RelationNode.Import(SourceKind.Csv, ".", "S", "SNo:text,SName:text,Status:integer,City:text");
var ss = si.Select("City", new TupSelect(t => (string)t[0] == "Paris"));

The key point is that a function relation defines a heading and a conforming function. From the implementation language point of view any object implementing the required interface will do. The function code can be inline, user-defined or system, of arbitrary complexity, and is the only part that has access to the scalar type system.

Andl - A New Database Language - andl.org
Quote from dandl on May 23, 2020, 9:38 am

A function relation is a relation that can appear in a relational expression as an argument to a relational operator.

A relvar or a relcon or a relational expression made up from those "can appear ... as an argument to a relational operator". I presume you're trying to define something else. What?

The declaration of an FR requires only a heading.

The declaration of a relvar requires only a heading. (Arguably TTM requires a key; possibly that key can default to whole heading without being explicitly declared.) I strongly expect that if something's going to act as a function within a relational expression, it too would need a key (possibly being the whole heading).

The definition is supplied by an implementation written in some other language.

The simplest example is the select FR.

  • It will appear as one argument of the semijoin (MATCHES) operator.
  • It must declare a heading that is a subset of the other argument (which guarantees join compatibility).
  • It must implement a function that takes the values for those attributes as arguments and returns a boolean value.
  • The semijoin operator will interpret the return value to indicate whether the matching tuple exists or not.

What you appear to be describing is usually called 'restrict'; because 'select' has become skunked by association with SQL.

From HHT 1975:

we have [algorithmic] relations which are pure predicates, ie. we can only recognise if a given tuple is in the relation or not.

Appendix A's PLUS can be used either within a semijoin -- which Tutorial D calls MATCHING, not MATCHES: R MATCHING PLUSor to achieve EXTEND R : {Z := X + Y}R JOIN PLUS. That usage for restrict is no different to S WHERE CITY = 'LEEDS'S MATCHING REL{TUP{CITY 'LEEDS'}}

Then "heading that is a subset of the other argument [of MATCHING]" is a characteristic of the usage/expression; not of the algorithmic relation -- as HHT 1975 have already specified.

Pleeease why can't you just re-use the thinking and terminology in HHT 1975? Or if you don't mean that, please say so and explain/motivate the differences.

And that's all there is.

HHT 1975 is admirably brief. But not four bullet points and a load of hand-waving brief.

A similar strategy deals with the creation of new values (EXTEND) and with aggregation.

Possibly you're talking about HHT 1975's 'effectiveness'. There's some quite complicated rules. Driven by what is in effect the declared key(s) of algorithmic relations. You've kinda re-invented the wheel. Only your wheel appears to be square.

The type system that deals with attribute types is confined to the implementing function, in whatever language is convenient.

 

Quote from dandl on May 25, 2020, 6:37 am
Quote from Darren Duncan on May 25, 2020, 6:23 am
Quote from dandl on May 23, 2020, 9:38 am

A function relation is a relation that can appear in a relational expression as an argument to a relational operator. The declaration of an FR requires only a heading. The definition is supplied by an implementation written in some other language.

Can you give some example code for this proposal?

I'm still working on it, but something like this at present:

var si = RelationNode.Import(SourceKind.Csv, ".", "S", "SNo:text,SName:text,Status:integer,City:text");
var ss = si.Select("City", new TupSelect(t => (string)t[0] == "Paris"));
var si = RelationNode.Import(SourceKind.Csv, ".", "S", "SNo:text,SName:text,Status:integer,City:text"); var ss = si.Select("City", new TupSelect(t => (string)t[0] == "Paris"));
var si = RelationNode.Import(SourceKind.Csv, ".", "S", "SNo:text,SName:text,Status:integer,City:text");
var ss = si.Select("City", new TupSelect(t => (string)t[0] == "Paris"));

The key point is that a function relation defines a heading and a conforming function. From the implementation language point of view any object implementing the required interface will do. The function code can be inline, user-defined or system, of arbitrary complexity, and is the only part that has access to the scalar type system.

How does your "function relation" differ from a (read-only?) relvar?

Rel reads (and in some cases, writes) CSV files, Excel spreadsheets, MS Access databases, and tables in SQL DBMSs. From the Tutorial D point of view, they're all relvars; their physical implementation is irrelevant and (largely -- it's specified in the relvar declaration) external to Tutorial D.

In short, I'm not clear what a "function relation" adds to the canon.

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 AntC on May 25, 2020, 9:55 am
Quote from dandl on May 23, 2020, 9:38 am

A function relation is a relation that can appear in a relational expression as an argument to a relational operator.

A relvar or a relcon or a relational expression made up from those "can appear ... as an argument to a relational operator". I presume you're trying to define something else. What?

The declaration of an FR requires only a heading.

The declaration of a relvar requires only a heading. (Arguably TTM requires a key; possibly that key can default to whole heading without being explicitly declared.) I strongly expect that if something's going to act as a function within a relational expression, it too would need a key (possibly being the whole heading).

No argument. App-A defines its 5 operators in terms of a heading and body semantics, in set-builder notation. They have not demonstrated to my satisfaction coverage over all of the RA features of TD, but the approach is a good one.

I'm building up a reference of more than 20 RA operators using the same basic concept, and implementing them as a library. They show a very consistent set of features:

  • Some need only the operation name, and the heading is inferred (eg union, antijoin)
  • Some need a heading (eg project, rename, group)
  • A few need a heading and a function relation (eg extend, aggregate)
  • One needs a relation expression as an argument (while).

But within those limits it's highly regular and very straightforward to implement.

The definition is supplied by an implementation written in some other language.

The simplest example is the select FR.

  • It will appear as one argument of the semijoin (MATCHES) operator.
  • It must declare a heading that is a subset of the other argument (which guarantees join compatibility).
  • It must implement a function that takes the values for those attributes as arguments and returns a boolean value.
  • The semijoin operator will interpret the return value to indicate whether the matching tuple exists or not.

What you appear to be describing is usually called 'restrict'; because 'select' has become skunked by association with SQL.

Most references I found to the RA as well as Alice use select, and the matching symbol Greek sigma. I can't find anyone using restrict and I refuse to use where. I could care less, whatever is understood is fine with me.

From HHT 1975:

we have [algorithmic] relations which are pure predicates, ie. we can only recognise if a given tuple is in the relation or not.

Appendix A's PLUS can be used either within a semijoin -- which Tutorial D calls MATCHING, not MATCHES: R MATCHING PLUSor to achieve EXTEND R : {Z := X + Y}R JOIN PLUS. That usage for restrict is no different to S WHERE CITY = 'LEEDS'S MATCHING REL{TUP{CITY 'LEEDS'}}

Then "heading that is a subset of the other argument [of MATCHING]" is a characteristic of the usage/expression; not of the algorithmic relation -- as HHT 1975 have already specified.

Pleeease why can't you just re-use the thinking and terminology in HHT 1975? Or if you don't mean that, please say so and explain/motivate the differences.

[In DTATRM, TD calls it SEMIJOIN -- I have no idea why they changed it or when.] But yes, there is really no reason why the same library PLUS function cannot be used with both semijoin and select/restrict. They only difference is the interface. In App-A the only interface is a bunch of clunky RENAMES; I use headings to make things connect up nicely.

HHT has too little detail to be usable; as soon as you push on it, it falls apart. It's not widely known, so I wouldn't expect 'algorithmic relation' to be understood. They care about generation and 'effectiveness', I don't. I want stuff that works and I can use. They don't provide that.

And that's all there is.

HHT 1975 is admirably brief. But not four bullet points and a load of hand-waving brief.

A similar strategy deals with the creation of new values (EXTEND) and with aggregation.

Possibly you're talking about HHT 1975's 'effectiveness'. There's some quite complicated rules. Driven by what is in effect the declared key(s) of algorithmic relations. You've kinda re-invented the wheel. Only your wheel appears to be square.

The type system that deals with attribute types is confined to the implementing function, in whatever language is convenient.

 

HHT succeeds by write a paper and getting it published. I succeed by writing working code and getting that published. Rather different goals.

Andl - A New Database Language - andl.org
Quote from Dave Voorhis on May 25, 2020, 10:25 am
Quote from dandl on May 25, 2020, 6:37 am
Quote from Darren Duncan on May 25, 2020, 6:23 am
Quote from dandl on May 23, 2020, 9:38 am

A function relation is a relation that can appear in a relational expression as an argument to a relational operator. The declaration of an FR requires only a heading. The definition is supplied by an implementation written in some other language.

Can you give some example code for this proposal?

I'm still working on it, but something like this at present:

var si = RelationNode.Import(SourceKind.Csv, ".", "S", "SNo:text,SName:text,Status:integer,City:text");
var ss = si.Select("City", new TupSelect(t => (string)t[0] == "Paris"));
var si = RelationNode.Import(SourceKind.Csv, ".", "S", "SNo:text,SName:text,Status:integer,City:text"); var ss = si.Select("City", new TupSelect(t => (string)t[0] == "Paris"));
var si = RelationNode.Import(SourceKind.Csv, ".", "S", "SNo:text,SName:text,Status:integer,City:text");
var ss = si.Select("City", new TupSelect(t => (string)t[0] == "Paris"));

The key point is that a function relation defines a heading and a conforming function. From the implementation language point of view any object implementing the required interface will do. The function code can be inline, user-defined or system, of arbitrary complexity, and is the only part that has access to the scalar type system.

How does your "function relation" differ from a (read-only?) relvar?

It's never a relvar. It does look like a relation value when used as an argument to a suitable function, but there are restrictions -- it doesn't work backwards.

Rel reads (and in some cases, writes) CSV files, Excel spreadsheets, MS Access databases, and tables in SQL DBMSs. From the Tutorial D point of view, they're all relvars; their physical implementation is irrelevant and (largely -- it's specified in the relvar declaration) external to Tutorial D.

In short, I'm not clear what a "function relation" adds to the canon.

Those should certainly look like relation constants. I have those too. But you cannot use PLUS that way. You have to join in such a way as to provide the arguments from a which a result can be calculated. It's a mapping from arguments to return value. It's a function, not a constant. [algorithmic if it makes you happier, but not a constant.]

Andl - A New Database Language - andl.org
Quote from dandl on May 25, 2020, 3:06 pm
Quote from Dave Voorhis on May 25, 2020, 10:25 am
Quote from dandl on May 25, 2020, 6:37 am
Quote from Darren Duncan on May 25, 2020, 6:23 am
Quote from dandl on May 23, 2020, 9:38 am

A function relation is a relation that can appear in a relational expression as an argument to a relational operator. The declaration of an FR requires only a heading. The definition is supplied by an implementation written in some other language.

Can you give some example code for this proposal?

I'm still working on it, but something like this at present:

var si = RelationNode.Import(SourceKind.Csv, ".", "S", "SNo:text,SName:text,Status:integer,City:text");
var ss = si.Select("City", new TupSelect(t => (string)t[0] == "Paris"));
var si = RelationNode.Import(SourceKind.Csv, ".", "S", "SNo:text,SName:text,Status:integer,City:text"); var ss = si.Select("City", new TupSelect(t => (string)t[0] == "Paris"));
var si = RelationNode.Import(SourceKind.Csv, ".", "S", "SNo:text,SName:text,Status:integer,City:text");
var ss = si.Select("City", new TupSelect(t => (string)t[0] == "Paris"));

The key point is that a function relation defines a heading and a conforming function. From the implementation language point of view any object implementing the required interface will do. The function code can be inline, user-defined or system, of arbitrary complexity, and is the only part that has access to the scalar type system.

How does your "function relation" differ from a (read-only?) relvar?

It's never a relvar. It does look like a relation value when used as an argument to a suitable function, but there are restrictions -- it doesn't work backwards.

Rel reads (and in some cases, writes) CSV files, Excel spreadsheets, MS Access databases, and tables in SQL DBMSs. From the Tutorial D point of view, they're all relvars; their physical implementation is irrelevant and (largely -- it's specified in the relvar declaration) external to Tutorial D.

In short, I'm not clear what a "function relation" adds to the canon.

Those should certainly look like relation constants. I have those too. But you cannot use PLUS that way. You have to join in such a way as to provide the arguments from a which a result can be calculated. It's a mapping from arguments to return value. It's a function, not a constant. [algorithmic if it makes you happier, but not a constant.]

I'm not sure what you mean by "it doesn't work backwards", but are you sure RelationNode.Import(...) is the example you meant to use?

Am I right that what you mean by a "function relation" is a function that returns a relation that is parametrised by subsequent terms in the expression?

For example, a RelationNode.Import with a SQL source might use Select to generate appropriate SQL for execution by an external DBMS, rather than restricting in-memory?

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 May 25, 2020, 3:39 pm
Quote from dandl on May 25, 2020, 3:06 pm
Quote from Dave Voorhis on May 25, 2020, 10:25 am
Quote from dandl on May 25, 2020, 6:37 am
Quote from Darren Duncan on May 25, 2020, 6:23 am
Quote from dandl on May 23, 2020, 9:38 am

A function relation is a relation that can appear in a relational expression as an argument to a relational operator. The declaration of an FR requires only a heading. The definition is supplied by an implementation written in some other language.

Can you give some example code for this proposal?

I'm still working on it, but something like this at present:

var si = RelationNode.Import(SourceKind.Csv, ".", "S", "SNo:text,SName:text,Status:integer,City:text");
var ss = si.Select("City", new TupSelect(t => (string)t[0] == "Paris"));
var si = RelationNode.Import(SourceKind.Csv, ".", "S", "SNo:text,SName:text,Status:integer,City:text"); var ss = si.Select("City", new TupSelect(t => (string)t[0] == "Paris"));
var si = RelationNode.Import(SourceKind.Csv, ".", "S", "SNo:text,SName:text,Status:integer,City:text");
var ss = si.Select("City", new TupSelect(t => (string)t[0] == "Paris"));

The key point is that a function relation defines a heading and a conforming function. From the implementation language point of view any object implementing the required interface will do. The function code can be inline, user-defined or system, of arbitrary complexity, and is the only part that has access to the scalar type system.

How does your "function relation" differ from a (read-only?) relvar?

It's never a relvar. It does look like a relation value when used as an argument to a suitable function, but there are restrictions -- it doesn't work backwards.

Rel reads (and in some cases, writes) CSV files, Excel spreadsheets, MS Access databases, and tables in SQL DBMSs. From the Tutorial D point of view, they're all relvars; their physical implementation is irrelevant and (largely -- it's specified in the relvar declaration) external to Tutorial D.

In short, I'm not clear what a "function relation" adds to the canon.

Those should certainly look like relation constants. I have those too. But you cannot use PLUS that way. You have to join in such a way as to provide the arguments from a which a result can be calculated. It's a mapping from arguments to return value. It's a function, not a constant. [algorithmic if it makes you happier, but not a constant.]

I'm not sure what you mean by "it doesn't work backwards", but are you sure RelationNode.Import(...) is the example you meant to use?

I'm surprised. These things look so obvious.

A function maps from one set to another, from arguments to return value. It doesn't work backwards, from return value to arguments. A constant works both ways: a SINE constant could be looked up on the return value to get the arcsine.

The Import() node was included so you could see where the data came from, including the heading. The next line select is the relation function.

Am I right that what you mean by a "function relation" is a function that returns a relation that is parametrised by subsequent terms in the expression?

For example, a RelationNode.Import with a SQL source might use Select to generate appropriate SQL for execution by an external DBMS, rather than restricting in-memory?

A relation function:

  • is invoked by name and heading
  • takes a relation as an argument, heading must conform
  • returns a relation, heading is inferred.

An import relation function might have a heading like "sql,rva" and would import one table as an RVA per tuple with attribute SQL in its argument.

Andl - A New Database Language - andl.org
12