# Type checking/inference, practical application?

Quote from AntC on July 6, 2021, 6:05 amQuote from dandl on July 6, 2021, 1:45 amQuote from AntC on July 5, 2021, 9:54 pmQuote from Dave Voorhis on July 5, 2021, 3:06 pmQuote from dandl on July 5, 2021, 5:31 am

- The basic (Codd) Relational Algebra defines 6 operators:
select, project, join, rename, union, not.- The Extended RA adds 3:
extend, aggregate, while.Of course, that's

arelational algebra. There is nothing so definitive as to be consideredtheRelational Algebra.

`while`

is specific to the Alice book. I don't think I've seen any other algebra alleged to be relational that includes`while`

. Most use some sort of grouping operator -- such as`G`

in wikipedia -- with transitive closure.What I have provided is complete: a superset of every RA operation in TD, SQL and any similar query language using the named perspective. Feel free to provide your own version in some other form, but if complete they will be equivalent and there will be a trivial transformation between them.

Good grief you can be obtuse; and disagreeable! I didn't say anything about (not) complete or equivalent. I (and Dave) were objecting to your use of "

thebasic (Codd) Relational Algebra" and "theExtended RA". [my emphasis on "the".] Codd did not includerename; you're just plain wrong. There is no such things astheExtended RA. There's a wild variety of extensions over the generally-agreed basic operators.Since @mamcx seems to be relatively new to Relationland, I'm objecting to you making misleading/untrue claims in your

ex cathedratone of voice.CTE RECURSIVE in SQL is not spelled

while; its semantics are not given in terms ofwhile;whileappears only in the Alice book AFAICT.whileis not necessarily a part of any extension to the usual RA operators.When I said "G in wikipedia", I would have thought the link is pretty darn obvious. I am not claiming G is necessarily part of any extension to the usual RA operators. Because I am not claiming there is any commonly-accepted 'Extended RA'. I would strongly resist the idea that because some capability is in SQL, there must some equivalent in an algebra.

The

whileoperator is represented by CTE RECURSIVE in SQL, and is a superset of transitive closure. Givenwhile,TC is a trivial shorthand.Grouping is

aggregation,notwhile.I don't know G -- please provide a link.

Quote from dandl on July 6, 2021, 1:45 amQuote from AntC on July 5, 2021, 9:54 pmQuote from Dave Voorhis on July 5, 2021, 3:06 pmQuote from dandl on July 5, 2021, 5:31 am

- The basic (Codd) Relational Algebra defines 6 operators:
select, project, join, rename, union, not.- The Extended RA adds 3:
extend, aggregate, while.Of course, that's

arelational algebra. There is nothing so definitive as to be consideredtheRelational Algebra.

`while`

is specific to the Alice book. I don't think I've seen any other algebra alleged to be relational that includes`while`

. Most use some sort of grouping operator -- such as`G`

in wikipedia -- with transitive closure.What I have provided is complete: a superset of every RA operation in TD, SQL and any similar query language using the named perspective. Feel free to provide your own version in some other form, but if complete they will be equivalent and there will be a trivial transformation between them.

Good grief you can be obtuse; and disagreeable! I didn't say anything about (not) complete or equivalent. I (and Dave) were objecting to your use of "*the* basic (Codd) Relational Algebra" and "*the* Extended RA". [my emphasis on "*the*".] Codd did not include *rename*; you're just plain wrong. There is no such things as *the* Extended RA. There's a wild variety of extensions over the generally-agreed basic operators.

Since @mamcx seems to be relatively new to Relationland, I'm objecting to you making misleading/untrue claims in your *ex cathedra* tone of voice.

CTE RECURSIVE in SQL is not spelled *while*; its semantics are not given in terms of *while*; *while* appears only in the Alice book AFAICT. *while* is not necessarily a part of any extension to the usual RA operators.

When I said "G in wikipedia", I would have thought the link is pretty darn obvious. I am not claiming G is necessarily part of any extension to the usual RA operators. Because I am not claiming there is any commonly-accepted 'Extended RA'. I would strongly resist the idea that because some capability is in SQL, there must some equivalent in an algebra.

The

whileoperator is represented by CTE RECURSIVE in SQL, and is a superset of transitive closure. Givenwhile,TC is a trivial shorthand.Grouping is

aggregation,notwhile.I don't know G -- please provide a link.

Quote from dandl on July 7, 2021, 1:56 amQuote from Darren Duncan on July 6, 2021, 3:11 amQuote from dandl on July 6, 2021, 1:27 amQuote from Darren Duncan on July 5, 2021, 7:05 amAnd so at least some type checks can only be done at runtime or else the system is not computationally complete and hence is much less interesting and useful.

This is patently untrue. Happy to demolish any proposed examples on request.

I think this just comes down to definitions of what "compile time" and "runtime" actually mean, the assumption there is exactly on instance of the first which precedes all of the second.

Not really. Type safety is a property of the language spec, not of any particular implementation. If the spec is for a language that is statically type safe the program can be checked for safety, whether or not it is ever compiled (into executable code) or executed.

If we consider the restricted traditional scenario for language L that person P1 is writing an application in L, and then compiling that program to a machine binary and giving just that binary to person P2 to run their business on, then the entirety of "compile time" is when the program was in the hands of P1 and the entirety of the time the machine binary is being used in the hands of P2 is "runtime".

In this scenario, the only time "compile time type checks" could be done is by P1.

Now if the program has features to allow P2 to express arbitrary queries or business logic, arbitrary as in P2 has a computationally complete environment to work with, then P2 would in the general case be defining their own types and routines and executing them. But all of these type checks would be "at runtime" from the perspective of the program because P2 only has the machine binary which is "already compiled", and it isn't being recompiled to include whatever P2 defined.

So it is impossible for the types defined by P2 to have been checked at compile time of the main program because the compilation was finished before P2 had the program.

In contrast, if we define "compile time" as something that can be caused by a runtime, and there can be more than one, then my comment about impossibility doesn't apply.

In the latter case, the compile/runtime distinction is a lot more arbitrary as they tend to blur together into one undifferentiated stage which in effect is just runtime.

I don't see any blur. If languages L1 and L2 can be checked for static type safety then who does it or when or how is an implementation decision.

The point is that a program written in a safe language L1 which allows end-user programing in a safe language L2 can guarantee end-to-end type safety.

The current state of play is that Java/C# offer some degree of type safety, depending on how they are used. End-user programmability is usually limited and type safe.

Quote from Darren Duncan on July 6, 2021, 3:11 amQuote from dandl on July 6, 2021, 1:27 amQuote from Darren Duncan on July 5, 2021, 7:05 amAnd so at least some type checks can only be done at runtime or else the system is not computationally complete and hence is much less interesting and useful.

This is patently untrue. Happy to demolish any proposed examples on request.

I think this just comes down to definitions of what "compile time" and "runtime" actually mean, the assumption there is exactly on instance of the first which precedes all of the second.

Not really. Type safety is a property of the language spec, not of any particular implementation. If the spec is for a language that is statically type safe the program can be checked for safety, whether or not it is ever compiled (into executable code) or executed.

If we consider the restricted traditional scenario for language L that person P1 is writing an application in L, and then compiling that program to a machine binary and giving just that binary to person P2 to run their business on, then the entirety of "compile time" is when the program was in the hands of P1 and the entirety of the time the machine binary is being used in the hands of P2 is "runtime".

In this scenario, the only time "compile time type checks" could be done is by P1.

Now if the program has features to allow P2 to express arbitrary queries or business logic, arbitrary as in P2 has a computationally complete environment to work with, then P2 would in the general case be defining their own types and routines and executing them. But all of these type checks would be "at runtime" from the perspective of the program because P2 only has the machine binary which is "already compiled", and it isn't being recompiled to include whatever P2 defined.

So it is impossible for the types defined by P2 to have been checked at compile time of the main program because the compilation was finished before P2 had the program.

In contrast, if we define "compile time" as something that can be caused by a runtime, and there can be more than one, then my comment about impossibility doesn't apply.

In the latter case, the compile/runtime distinction is a lot more arbitrary as they tend to blur together into one undifferentiated stage which in effect is just runtime.

I don't see any blur. If languages L1 and L2 can be checked for static type safety then who does it or when or how is an implementation decision.

The point is that a program written in a safe language L1 which allows end-user programing in a safe language L2 can guarantee end-to-end type safety.

The current state of play is that Java/C# offer some degree of type safety, depending on how they are used. End-user programmability is usually limited and type safe.

Quote from dandl on July 7, 2021, 3:09 amQuote from AntC on July 6, 2021, 6:05 amQuote from dandl on July 6, 2021, 1:45 amQuote from AntC on July 5, 2021, 9:54 pmQuote from Dave Voorhis on July 5, 2021, 3:06 pmQuote from dandl on July 5, 2021, 5:31 am

- The basic (Codd) Relational Algebra defines 6 operators:
select, project, join, rename, union, not.- The Extended RA adds 3:
extend, aggregate, while.Of course, that's

arelational algebra. There is nothing so definitive as to be consideredtheRelational Algebra.

`while`

is specific to the Alice book. I don't think I've seen any other algebra alleged to be relational that includes`while`

. Most use some sort of grouping operator -- such as`G`

in wikipedia -- with transitive closure.What I have provided is complete: a superset of every RA operation in TD, SQL and any similar query language using the named perspective. Feel free to provide your own version in some other form, but if complete they will be equivalent and there will be a trivial transformation between them.

Good grief you can be obtuse; and disagreeable! I didn't say anything about (not) complete or equivalent. I (and Dave) were objecting to your use of "

thebasic (Codd) Relational Algebra" and "theExtended RA". [my emphasis on "the".] Codd did not includerename; you're just plain wrong. There is no such things astheExtended RA. There's a wild variety of extensions over the generally-agreed basic operators.Ad hominem remarks noted and ignored.

Sorry you didn't understand: I was being too succinct. Call it Codd+ if you like: the 5 operators from his early work plus

renamefor the named perspective (optional). The Wikipedia article and I agree on that, sorry if you don't.Since @mamcx seems to be relatively new to Relationland, I'm objecting to you making misleading/untrue claims in your

ex cathedratone of voice.CTE RECURSIVE in SQL is not spelled

while; its semantics are not given in terms ofwhile;whileappears only in the Alice book AFAICT.whileis not necessarily a part of any extension to the usual RA operators.When I said "G in wikipedia", I would have thought the link is pretty darn obvious. I am not claiming G is necessarily part of any extension to the usual RA operators. Because I am not claiming there is any commonly-accepted 'Extended RA'. I would strongly resist the idea that because some capability is in SQL, there must some equivalent in an algebra.

Wikipedia lists the same same 3 extensions as mine:

- extended projection ==
extend/new value- aggregation (G) ==
aggregate- transitive closure, fix point queries, SQL ==
while[The treatment is incomplete, and they do not mention generalised TC.]The other proposed extensions are shorthands. While there are differences in presentation and syntax the algebra is the same: 6 basic plus 3 extensions. No more, no less.

To reiterate: I have built on the earlier work of D&D to provide:

- formal definitions of the basic 6 operators (similar to D&D)
- formal definitions of the 3 extended operators (not attempted by D&D)
- a formal treatment of
relconsas functions (discussed but not formalised by D&D)- a solution for Generalised TC based on
while(presented by D&D with no solution)If you can do better, the floor is all yours.

Quote from AntC on July 6, 2021, 6:05 amQuote from dandl on July 6, 2021, 1:45 amQuote from AntC on July 5, 2021, 9:54 pmQuote from Dave Voorhis on July 5, 2021, 3:06 pmQuote from dandl on July 5, 2021, 5:31 am

- The basic (Codd) Relational Algebra defines 6 operators:
select, project, join, rename, union, not.- The Extended RA adds 3:
extend, aggregate, while.arelational algebra. There is nothing so definitive as to be consideredtheRelational Algebra.

`while`

is specific to the Alice book. I don't think I've seen any other algebra alleged to be relational that includes`while`

. Most use some sort of grouping operator -- such as`G`

in wikipedia -- with transitive closure.thebasic (Codd) Relational Algebra" and "theExtended RA". [my emphasis on "the".] Codd did not includerename; you're just plain wrong. There is no such things astheExtended RA. There's a wild variety of extensions over the generally-agreed basic operators.

Ad hominem remarks noted and ignored.

Sorry you didn't understand: I was being too succinct. Call it Codd+ if you like: the 5 operators from his early work plus *rename* for the named perspective (optional). The Wikipedia article and I agree on that, sorry if you don't.

ex cathedratone of voice.while; its semantics are not given in terms ofwhile;whileappears only in the Alice book AFAICT.whileis not necessarily a part of any extension to the usual RA operators.

Wikipedia lists the same same 3 extensions as mine:

- extended projection ==
*extend/new value* - aggregation (G) ==
*aggregate* - transitive closure, fix point queries, SQL ==
*while*[The treatment is incomplete, and they do not mention generalised TC.]

The other proposed extensions are shorthands. While there are differences in presentation and syntax the algebra is the same: 6 basic plus 3 extensions. No more, no less.

To reiterate: I have built on the earlier work of D&D to provide:

- formal definitions of the basic 6 operators (similar to D&D)
- formal definitions of the 3 extended operators (not attempted by D&D)
- a formal treatment of
*relcons*as functions (discussed but not formalised by D&D) - a solution for Generalised TC based on
*while*(presented by D&D with no solution)

If you can do better, the floor is all yours.

Quote from Dave Voorhis on July 7, 2021, 8:18 amQuote from dandl on July 7, 2021, 3:09 amQuote from AntC on July 6, 2021, 6:05 amQuote from dandl on July 6, 2021, 1:45 amQuote from AntC on July 5, 2021, 9:54 pmQuote from Dave Voorhis on July 5, 2021, 3:06 pmQuote from dandl on July 5, 2021, 5:31 am

- The basic (Codd) Relational Algebra defines 6 operators:
select, project, join, rename, union, not.- The Extended RA adds 3:
extend, aggregate, while.arelational algebra. There is nothing so definitive as to be consideredtheRelational Algebra.

`while`

is specific to the Alice book. I don't think I've seen any other algebra alleged to be relational that includes`while`

. Most use some sort of grouping operator -- such as`G`

in wikipedia -- with transitive closure.thebasic (Codd) Relational Algebra" and "theExtended RA". [my emphasis on "the".] Codd did not includerename; you're just plain wrong. There is no such things astheExtended RA. There's a wild variety of extensions over the generally-agreed basic operators.Ad hominem remarks noted and ignored.

Sorry you didn't understand: I was being too succinct. Call it Codd+ if you like: the 5 operators from his early work plus

renamefor the named perspective (optional). The Wikipedia article and I agree on that, sorry if you don't.That would be best described as "Codd's 5-operator relational algebra, plus 'rename'" or similar.

What antc and I objected to is the notion that there is

therelational algebra. There is notherelational algebra. There are relational algebras.Or if there is

therelational algebra, it's "relations and some (unspecified) operators on relations."But really, there is no more

therelational algebra than there is, say, "the programming language standard library."There are, of course, things like "the C programming language standard library" or "the Java programming language standard library" (though these can and should be further qualified, at least to be specific enough for real work.) Likewise, there is "Codd's original relational algebra", or "Codd's 5-operator relational algebra, plus 'rename'", or "the TTM books' Appendix A", or "dandl's 10 operators", and so on.

Despite a certain lazy pedagogical tendency for university database courses to teach "the" relational algebra -- typically the operators and some expression syntax copied from the course textbook -- it properly should be understood as

somespecified set of operators on relations. What those operators might be is up to the implementer and the implementation, assuming it's implemented at all.Note that whilst a relational algebra

canbe implemented -- and some pedagogical tools do so -- it mainly provides some conceptual understanding and a descriptive framework to specify semantics for higher level languages, andmaybea practical basis for query optimisation. In terms of useful database language implementations, there is essentially no role. SQL implementations don't usually have an internal 'relational algebra' module.Reldoesn't implement Appendix A.

Quote from dandl on July 7, 2021, 3:09 amQuote from AntC on July 6, 2021, 6:05 amQuote from dandl on July 6, 2021, 1:45 amQuote from AntC on July 5, 2021, 9:54 pmQuote from Dave Voorhis on July 5, 2021, 3:06 pmQuote from dandl on July 5, 2021, 5:31 am

- The basic (Codd) Relational Algebra defines 6 operators:
select, project, join, rename, union, not.- The Extended RA adds 3:
extend, aggregate, while.arelational algebra. There is nothing so definitive as to be consideredtheRelational Algebra.

`while`

is specific to the Alice book. I don't think I've seen any other algebra alleged to be relational that includes`while`

. Most use some sort of grouping operator -- such as`G`

in wikipedia -- with transitive closure.thebasic (Codd) Relational Algebra" and "theExtended RA". [my emphasis on "the".] Codd did not includerename; you're just plain wrong. There is no such things astheExtended RA. There's a wild variety of extensions over the generally-agreed basic operators.Ad hominem remarks noted and ignored.

renamefor the named perspective (optional). The Wikipedia article and I agree on that, sorry if you don't.

That would be best described as "Codd's 5-operator relational algebra, plus 'rename'" or similar.

What antc and I objected to is the notion that there is *the *relational algebra. There is no *the* relational algebra. There are relational algebras.

Or if there is *the* relational algebra, it's "relations and some (unspecified) operators on relations."

But really, there is no more *the* relational algebra than there is, say, "the programming language standard library."

There are, of course, things like "the C programming language standard library" or "the Java programming language standard library" (though these can and should be further qualified, at least to be specific enough for real work.) Likewise, there is "Codd's original relational algebra", or "Codd's 5-operator relational algebra, plus 'rename'", or "the TTM books' Appendix A", or "dandl's 10 operators", and so on.

Despite a certain lazy pedagogical tendency for university database courses to teach "the" relational algebra -- typically the operators and some expression syntax copied from the course textbook -- it properly should be understood as *some* specified set of operators on relations. What those operators might be is up to the implementer and the implementation, assuming it's implemented at all.

Note that whilst a relational algebra *can* be implemented -- and some pedagogical tools do so -- it mainly provides some conceptual understanding and a descriptive framework to specify semantics for higher level languages, and *maybe* a practical basis for query optimisation. In terms of useful database language implementations, there is essentially no role. SQL implementations don't usually have an internal 'relational algebra' module. *Rel* doesn't implement Appendix A.

*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 dandl on July 8, 2021, 1:16 amA page of text to quibble over a word. Whatever.

But do you say that there are "a wild variety of extensions over the generally-agreed basic operators."? If so

- do you agree that there is
abasic RA (of 5 operators for the unnamed and 6 for the named perspectives)?- can you provide any example of extensions that are not subsets, trivial transformations or shorthands for the ones I gave?

A page of text to quibble over a word. Whatever.

But do you say that there are "a wild variety of extensions over the generally-agreed basic operators."? If so

- do you agree that there is
*a*basic RA (of 5 operators for the unnamed and 6 for the named perspectives)? - can you provide any example of extensions that are not subsets, trivial transformations or shorthands for the ones I gave?

Quote from AntC on July 8, 2021, 2:30 amQuote from dandl on July 8, 2021, 1:16 amA page of text to quibble over a word. Whatever.

But do you say that there are "a wild variety of extensions over the generally-agreed basic operators."? If so

- do you agree that there is
abasic RA (of 5 operators for the unnamed and 6 for the named perspectives)?Appendix A's operators have as much right to be called

abasic RA as any.

- "It should be obvious that A is relationally complete [22]. Previous algebras have needed six operators for this purpose (typically RENAME, restrict, project, TIMES, UNION, and MINUS); we have reduced that number to five." -- that is, five including RENAME.
- "... We do not actually need both <AND> and <OR> in order to achieve relational completeness, thanks to De Morgan's Laws."
- "In fact, we will show in the next section that we do not really need <RENAME> either; thus, we could in fact reduce our algebra still further to just the two operators <REMOVE> and either <NOR> or <NAND> (plus <TCLOSE>)."
- Now you might or might not agree that D&D manage to dispense with <RENAME>; but they certainly end up with fewer than 5 operators.
Under the Tropashko approach, which has as much right to be called

abasic RA as any:

- There's
`NatJoin, InnerUnion`

;- plus a distinguished element
`DUM`

aka`R00`

(not an operator);- plus some auxiliary operators that can be defined in terms of those:
`NOTMATCHING`

,`REMOVE`

(which D&D prefer overproject).So no I don't agree there is even

asingle "basic RA (of 5 operators ...)".The key concept here (per ref [22 -- i.e. Codd 1972] in the quote from Appendix A) is 'relationally complete'. Anything qualifies as

abasic RA providing it is at least relationally complete. That definition has nothing to do with counting operators.We might question whether Codd 1972's set of operators achieve his objective in that paper (indeed they don't, since he omitted the named perspective, despite it appearing clearly in his 1970 paper). And we might critique the 1972 paper as being confused/confusing in presenting the objective. But clearly the objective is about expressive ability, not counting operators.

- can you provide any example of extensions that are not subsets, trivial transformations or shorthands for the ones I gave?
See above.

Any strict subset of those 5/6 would not be expressively complete. Appendix A's <AND>, <OR> are generalisations of some of the operators in Codd 1972. Tropashko

`InnerUnion`

is also a combination/generalisation of Codd's`UNION`

,project.Whether a transformation is "trivial" or a "shorthand" seems to me a matter of opinion. Is the lambda calculus a "trivial transformation" or a "shorthand" for a Turing machine? Those two are expressively equivalent -- is the point. Turing 1937 proved the equivalence, by a transformation approach. There is nothing "trivial" in that paper.

You seem not to be 'getting it' that the criterion is expressive ability, not numbers of operators.

Quote from dandl on July 8, 2021, 1:16 amA page of text to quibble over a word. Whatever.

- do you agree that there is
abasic RA (of 5 operators for the unnamed and 6 for the named perspectives)?

Appendix A's operators have as much right to be called *a* basic RA as any.

- "It should be obvious that A is relationally complete [22]. Previous algebras have needed six operators for this purpose (typically RENAME, restrict, project, TIMES, UNION, and MINUS); we have reduced that number to five." -- that is, five including RENAME.
- "... We do not actually need both <AND> and <OR> in order to achieve relational completeness, thanks to De Morgan's Laws."
- "In fact, we will show in the next section that we do not really need <RENAME> either; thus, we could in fact reduce our algebra still further to just the two operators <REMOVE> and either <NOR> or <NAND> (plus <TCLOSE>)."
- Now you might or might not agree that D&D manage to dispense with <RENAME>; but they certainly end up with fewer than 5 operators.

Under the Tropashko approach, which has as much right to be called *a* basic RA as any:

- There's
`NatJoin, InnerUnion`

; - plus a distinguished element
`DUM`

aka`R00`

(not an operator); - plus some auxiliary operators that can be defined in terms of those:
`NOTMATCHING`

,`REMOVE`

(which D&D prefer over*project*).

So no I don't agree there is even *a* single "basic RA (of 5 operators ...)".

The key concept here (per ref [22 -- i.e. Codd 1972] in the quote from Appendix A) is 'relationally complete'. Anything qualifies as *a* basic RA providing it is at least relationally complete. That definition has nothing to do with counting operators.

We might question whether Codd 1972's set of operators achieve his objective in that paper (indeed they don't, since he omitted the named perspective, despite it appearing clearly in his 1970 paper). And we might critique the 1972 paper as being confused/confusing in presenting the objective. But clearly the objective is about expressive ability, not counting operators.

See above.

Any strict subset of those 5/6 would not be expressively complete. Appendix A's <AND>, <OR> are generalisations of some of the operators in Codd 1972. Tropashko `InnerUnion`

is also a combination/generalisation of Codd's `UNION`

, *project*.

Whether a transformation is "trivial" or a "shorthand" seems to me a matter of opinion. Is the lambda calculus a "trivial transformation" or a "shorthand" for a Turing machine? Those two are expressively equivalent -- is the point. Turing 1937 proved the equivalence, by a transformation approach. There is nothing "trivial" in that paper.

You seem not to be 'getting it' that the criterion is expressive ability, not numbers of operators.

Quote from dandl on July 8, 2021, 8:51 amThank you for drawing my attention (again) to Algebra A. At this point I retract what I said above, with apologies. I had done too much from memory.

As commonly accepted RA applies to the following:

- Original (Codd): "traditional set operations (Cartesian product, union, intersection, difference) and less traditional operations on relations (projection, join, division,

restriction)".- Basic Named: A set of 6 operators corresponding to SPJRUN in Alice. (there is also an unnamed perspective)
- Extended: may include new values, aggregation, transitive closure and fixed point recursion.
Less well known is the following.

- Algebra-A, comprising Not, Remove, Rename, And, Or, Transitive Closure and relational constants.
The first two of these are identical in expressive power. The extensions increase it considerably. AA and TD sit somewhere between. Note that although AA claims to reduce the count from 6 to 5, it depends on relcons to do so, and both this and the passing mention of aggregation fall well short of formal specification.

AA provides formal definitions of only 5 operators. I took AA as a starting point and have provided formal definitions for relcons, aggregation and Extended Transitive Closure. See: http://www.andl.org/2021/07/formal-definitions-for-an-extended-relational-algebra/.

My ERA is a superset of all the others, except fixed point recursion

(whilein Alice). It includes every operator in Original, Basic Names, Extended and Algebra-A, or provides them as a shorthand/macro. It does not include some SQL features including outer joins, fixed point and ordered queries, but otherwise it has an expressive power greater than any other RA I know of. [Datalog lives on another planet.]As well as the algebra I would include

`DUM`

and relational assignment in any language based on it.If Tropasko has a full set of definitions I would be interested to see them.

Thank you for drawing my attention (again) to Algebra A. At this point I retract what I said above, with apologies. I had done too much from memory.

As commonly accepted RA applies to the following:

- Original (Codd): "traditional set operations (Cartesian product, union, intersection, difference) and less traditional operations on relations (projection, join, division,

restriction)". - Basic Named: A set of 6 operators corresponding to SPJRUN in Alice. (there is also an unnamed perspective)
- Extended: may include new values, aggregation, transitive closure and fixed point recursion.

Less well known is the following.

- Algebra-A, comprising Not, Remove, Rename, And, Or, Transitive Closure and relational constants.

The first two of these are identical in expressive power. The extensions increase it considerably. AA and TD sit somewhere between. Note that although AA claims to reduce the count from 6 to 5, it depends on relcons to do so, and both this and the passing mention of aggregation fall well short of formal specification.

AA provides formal definitions of only 5 operators. I took AA as a starting point and have provided formal definitions for relcons, aggregation and Extended Transitive Closure. See: http://www.andl.org/2021/07/formal-definitions-for-an-extended-relational-algebra/.

My ERA is a superset of all the others, except fixed point recursion *(while* in Alice). It includes every operator in Original, Basic Names, Extended and Algebra-A, or provides them as a shorthand/macro. It does not include some SQL features including outer joins, fixed point and ordered queries, but otherwise it has an expressive power greater than any other RA I know of. [Datalog lives on another planet.]

As well as the algebra I would include `DUM`

and relational assignment in any language based on it.

If Tropasko has a full set of definitions I would be interested to see them.

Quote from Dave Voorhis on July 8, 2021, 9:10 amQuote from dandl on July 8, 2021, 1:16 amA page of text to quibble over a word. Whatever.

I draw your attention to the TTM epigraph:

All logical differences are big differences-- Ludwig Wittgenstein

The distinction between

therelational algebra andarelational algebra is important, because it's a frequent source of confusion and misunderstanding among beginners to the field. Indeed, it's often their first introduction to the fact that it's a fluid, active, and controversial field, and definitely not ossified like poor database pedagogy sometimes makes it appear.

abasic RA (of 5 operators for the unnamed and 6 for the named perspectives)?No, because there isn't.

See AntC's answer.

Quote from dandl on July 8, 2021, 1:16 amA page of text to quibble over a word. Whatever.

I draw your attention to the TTM epigraph:

All logical differences are big differences-- Ludwig Wittgenstein

The distinction between *the* relational algebra and *a* relational algebra is important, because it's a frequent source of confusion and misunderstanding among beginners to the field. Indeed, it's often their first introduction to the fact that it's a fluid, active, and controversial field, and definitely not ossified like poor database pedagogy sometimes makes it appear.

abasic RA (of 5 operators for the unnamed and 6 for the named perspectives)?

No, because there isn't.

See AntC's answer.

*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 July 8, 2021, 12:37 pmQuote from dandl on July 8, 2021, 8:51 am... Note that although AA claims to reduce the count from 6 to 5, it depends on relcons to do so, and both this and the passing mention of aggregation fall well short of formal specification.

Appendix A has a specification of

`SUMMARIZE`

and`GROUP`

in terms of the operators previously defined. What's not formal enough about it?As well as the algebra I would include

`DUM`

and relational assignment in any language based on it.If Tropas[h]ko has a full set of definitions I would be interested to see them.

- Tropashko
`^`

aka lattice meet aka`NatJoin`

specified as per Appendix A`<AND>`

.(So this caters for Codd's

`Intersection`

,`TIMES`

as special cases -- same approach as Appendix A.)

- Tropashko
`v`

aka lattice join aka`InnerUnion`

specified as follows (using the style of FORMAL DEFINITIONS in Appendix A):

- Let
`s`

be`r1 InnerUnion r2`

. It is required that if`<A, T1> ∈ Hr1`

and`<A, T2> ∈ Hr2`

, then`T1 = T2`

.Hs = Hr1 intersection Hr2

Bs = {ts : (exists tr1 and tr1 ∈ Br1 and ts ⊆ tr1) or (exists tr2 and tr2 ∈ Br2 and ts ⊆ tr2) }

The condition on headings

`Hr1, Hr2`

is the same as Appendix A's condition on headings for`<AND>, <OR>`

aka 'join-compatible'.

The`⊆`

condition on the tuples in the bodies is taking advantage of Appendix A/TTMdefining tuples as sets. This makes the definition domain-independent, like Codd's`UNION`

, unlike`<OR>`

.

Tutorial D's`UNION`

equivalent to Codd's`UNION`

is`InnerUnion`

specialized for operands of the same heading -- same as how Appendix A handles`UNION`

using`<OR>`

.

`InnerUnion`

is equivalent to SQL`UNION CORRESPONDING`

or ISBL`UNION`

.

`InnerUnion`

can be defined equationally in terms of`NatJoin`

, so is (arguably/controversially) not 'basic' but derived.

`DUM`

aka`R00`

is defined as per Appendix A/TTM: the relation with empty heading, empty body:`REL{} {}`

.- For projection, note that the Tropashko approach uses only relation values, there's no separate mathematical 'sort' of attribute names or attribute-comma-list. So

`r1 project r2 =df r1 InnerUnion (r2 NatJoin R00)`

-- so a derived operator.- Note that
`r2`

is unrestricted apart from needing to be join-compatible so might have attributes that don't appear in`r1`

-- or indeed its heading might be disjoint from`r1`

, in which case the`project`

=`r1 InnerUnion R00`

.- For semijoin

`r1 MATCHING r2 =df (r1 NatJoin r2) InnerUnion (r1 NatJoin R00)`

-- so a derived operator.- For anti(semi)join,
`NOTMATCHING`

behaves as per Appendix A. It is the solution to the simultaneous equations -- so a derived operator.

`(r1 NOTMATCHING r2) InnerUnion (r1 NatJoin r2) = r1`

`(r1 NOTMATCHING r2) NatJoin (r1 NatJoin r2) = r1 NatJoin r2 NatJoin R00`

- Also:
`r1 MATCHING r2 = r1 NOTMATCHING (r1 NOTMATCHING r2)`

-- generalised from McGoveran & Date 1994- For restriction/
`WHERE`

, use relcons with`NatJoin`

-- same approach as Appendix A.- For
`EXTEND`

, use relcons with`NatJoin`

-- same approach as Appendix A.- For
`RENAME`

, dispense with it using relcons with`COMPOSE`

-- same approach as Appendix A. And I am dubious about that approach; but it's no worse than Appendix A.`r1 COMPOSE r2 =df (r1 NatJoin r2) REMOVE (r1 InnerUnion r2)`

-- so a derived operator; not a "macro" operator -- whatever Appendix A's scare quotes are trying to convey.`r1 REMOVE r2`

is`r1`

projected on the attributes not in common with`r2`

. Note that`r2`

is unrestricted apart from needing to be join-compatible so might have attributes that don't appear in`r1`

-- or indeed its heading might be disjoint from`r1`

, in which case the`REMOVE`

is a no-op. Defined equationally, compare the definition for`NOTMATCHING`

-- so a derived operator:

`r1 NatJoin (r1 REMOVE r2) = r1`

`r1 InnerUnion (r1 REMOVE r2) = r1 REMOVE r2`

`(r1 REMOVE r2) InnerUnion r2 = r1 InnerUnion R00`

`r1 project r2 = r1 REMOVE (r1 REMOVE r2)`

- (We believe these equations sufficient to define
`REMOVE`

uniquely -- just as soon as we can equationally define`R00`

uniquely.)- Or if you've been following along the thread on complements and pseudocomplements,
`r1 REMOVE r2 = r1 InnerUnion hComp(r2)`

, in which`hComp( )`

is the (unique) relative complement of`r2 NatJoin R00`

within the convex sublattice bounded by the interval`[R10, R00]`

. (Where`R10`

is lattice bottom aka`Dumpty`

.)- For
`<NOT>`

, Clayden's Tropashko system does not include it -- preferring`NOTMATCHING`

instead. (Note that`NOTMATCHING`

is a generalisation of Codd 1972's`MINUS`

and Appendix A requires`<NOT>`

to appear only within a conjunction in the surface expression, which amounts to`NOTMATCHING`

.)If you've been following along the thread on complements and pseudocomplements,

`<NOT>`

is the (unique) relative complement within the convex sublattice bounded by the interval`[r1 NatJoin R00, r1 InnerUnion R11]`

. (Where`R11`

aka fullest-possible-relation is the (unique) absolute pseudocomplement of`R00`

.)So we've arrived at equivalent expressive power to the

Aalgebra (but with`InnerUnion`

instead of`<OR>`

). If I've left out any operators, they can be derived following Appendix A's equivalences.

Quote from dandl on July 8, 2021, 8:51 am... Note that although AA claims to reduce the count from 6 to 5, it depends on relcons to do so, and both this and the passing mention of aggregation fall well short of formal specification.

Appendix A has a specification of `SUMMARIZE`

and `GROUP`

in terms of the operators previously defined. What's not formal enough about it?

As well as the algebra I would include

`DUM`

and relational assignment in any language based on it.If Tropas[h]ko has a full set of definitions I would be interested to see them.

- Tropashko
`^`

aka lattice meet aka`NatJoin`

specified as per Appendix A`<AND>`

.

(So this caters for Codd's `Intersection`

, `TIMES`

as special cases -- same approach as Appendix A.)

- Tropashko
`v`

aka lattice join aka`InnerUnion`

specified as follows (using the style of FORMAL DEFINITIONS in Appendix A):- Let
`s`

be`r1 InnerUnion r2`

. It is required that if`<A, T1> ∈ Hr1`

and`<A, T2> ∈ Hr2`

, then`T1 = T2`

.

- Let

Hs = Hr1 intersection Hr2

Bs = {ts : (exists tr1 and tr1 ∈ Br1 and ts ⊆ tr1) or (exists tr2 and tr2 ∈ Br2 and ts ⊆ tr2) }

The condition on headings `Hr1, Hr2`

is the same as Appendix A's condition on headings for `<AND>, <OR>`

aka 'join-compatible'.

The `⊆`

condition on the tuples in the bodies is taking advantage of Appendix A/*TTM* defining tuples as sets. This makes the definition domain-independent, like Codd's `UNION`

, unlike `<OR>`

.

**Tutorial D**'s `UNION`

equivalent to Codd's `UNION`

is `InnerUnion`

specialized for operands of the same heading -- same as how Appendix A handles `UNION`

using `<OR>`

.

`InnerUnion`

is equivalent to SQL `UNION CORRESPONDING`

or ISBL `UNION`

.

`InnerUnion`

can be defined equationally in terms of `NatJoin`

, so is (arguably/controversially) not 'basic' but derived.

`DUM`

aka`R00`

is defined as per Appendix A/*TTM*: the relation with empty heading, empty body:`REL{} {}`

.- For projection, note that the Tropashko approach uses only relation values, there's no separate mathematical 'sort' of attribute names or attribute-comma-list. So
`r1 project r2 =df r1 InnerUnion (r2 NatJoin R00)`

-- so a derived operator.- Note that
`r2`

is unrestricted apart from needing to be join-compatible so might have attributes that don't appear in`r1`

-- or indeed its heading might be disjoint from`r1`

, in which case the`project`

=`r1 InnerUnion R00`

.

- For semijoin
`r1 MATCHING r2 =df (r1 NatJoin r2) InnerUnion (r1 NatJoin R00)`

-- so a derived operator.

- For anti(semi)join,
`NOTMATCHING`

behaves as per Appendix A. It is the solution to the simultaneous equations -- so a derived operator.`(r1 NOTMATCHING r2) InnerUnion (r1 NatJoin r2) = r1`

`(r1 NOTMATCHING r2) NatJoin (r1 NatJoin r2) = r1 NatJoin r2 NatJoin R00`

- Also:
`r1 MATCHING r2 = r1 NOTMATCHING (r1 NOTMATCHING r2)`

-- generalised from McGoveran & Date 1994

- For restriction/
`WHERE`

, use relcons with`NatJoin`

-- same approach as Appendix A. - For
`EXTEND`

, use relcons with`NatJoin`

-- same approach as Appendix A. - For
`RENAME`

, dispense with it using relcons with`COMPOSE`

-- same approach as Appendix A. And I am dubious about that approach; but it's no worse than Appendix A. `r1 COMPOSE r2 =df (r1 NatJoin r2) REMOVE (r1 InnerUnion r2)`

-- so a derived operator; not a "macro" operator -- whatever Appendix A's scare quotes are trying to convey.`r1 REMOVE r2`

is`r1`

projected on the attributes not in common with`r2`

. Note that`r2`

is unrestricted apart from needing to be join-compatible so might have attributes that don't appear in`r1`

-- or indeed its heading might be disjoint from`r1`

, in which case the`REMOVE`

is a no-op. Defined equationally, compare the definition for`NOTMATCHING`

-- so a derived operator:`r1 NatJoin (r1 REMOVE r2) = r1`

`r1 InnerUnion (r1 REMOVE r2) = r1 REMOVE r2`

`(r1 REMOVE r2) InnerUnion r2 = r1 InnerUnion R00`

`r1 project r2 = r1 REMOVE (r1 REMOVE r2)`

- (We believe these equations sufficient to define
`REMOVE`

uniquely -- just as soon as we can equationally define`R00`

uniquely.) - Or if you've been following along the thread on complements and pseudocomplements,
`r1 REMOVE r2 = r1 InnerUnion hComp(r2)`

, in which`hComp( )`

is the (unique) relative complement of`r2 NatJoin R00`

within the convex sublattice bounded by the interval`[R10, R00]`

. (Where`R10`

is lattice bottom aka`Dumpty`

.)

- For
`<NOT>`

, Clayden's Tropashko system does not include it -- preferring`NOTMATCHING`

instead. (Note that`NOTMATCHING`

is a generalisation of Codd 1972's`MINUS`

and Appendix A requires`<NOT>`

to appear only within a conjunction in the surface expression, which amounts to`NOTMATCHING`

.)

If you've been following along the thread on complements and pseudocomplements, `<NOT>`

is the (unique) relative complement within the convex sublattice bounded by the interval `[r1 NatJoin R00, r1 InnerUnion R11]`

. (Where `R11`

aka fullest-possible-relation is the (unique) absolute pseudocomplement of `R00`

.)

So we've arrived at equivalent expressive power to the **A** algebra (but with `InnerUnion`

instead of `<OR>`

). If I've left out any operators, they can be derived following Appendix A's equivalences.

Quote from dandl on July 9, 2021, 12:57 amQuote from AntC on July 8, 2021, 12:37 pmQuote from dandl on July 8, 2021, 8:51 am... Note that although AA claims to reduce the count from 6 to 5, it depends on relcons to do so, and both this and the passing mention of aggregation fall well short of formal specification.

Appendix A has a specification of

`SUMMARIZE`

and`GROUP`

in terms of the operators previously defined. What's not formal enough about it?The specification goes as far as <summary spec> on page a.18 but no further. Functions such as min/max/sum and generic aggregation as per TTM RM Pre 6 are not specified here, but they are in mine.

As well as the algebra I would include

`DUM`

and relational assignment in any language based on it.If Tropas[h]ko has a full set of definitions I would be interested to see them.

- Tropashko
`^`

aka lattice meet aka`NatJoin`

specified as per Appendix A`<AND>`

.(So this caters for Codd's

`Intersection`

,`TIMES`

as special cases -- same approach as Appendix A.)

- Tropashko
`v`

aka lattice join aka`InnerUnion`

specified as follows (using the style of FORMAL DEFINITIONS in Appendix A):

- Let
`s`

be`r1 InnerUnion r2`

. It is required that if`<A, T1> ∈ Hr1`

and`<A, T2> ∈ Hr2`

, then`T1 = T2`

.Hs = Hr1 intersection Hr2

Bs = {ts : (exists tr1 and tr1 ∈ Br1 and ts ⊆ tr1) or (exists tr2 and tr2 ∈ Br2 and ts ⊆ tr2) }

The condition on headings

`Hr1, Hr2`

is the same as Appendix A's condition on headings for`<AND>, <OR>`

aka 'join-compatible'.

The`⊆`

condition on the tuples in the bodies is taking advantage of Appendix A/TTMdefining tuples as sets. This makes the definition domain-independent, like Codd's`UNION`

, unlike`<OR>`

.

Tutorial D's`UNION`

equivalent to Codd's`UNION`

is`InnerUnion`

specialized for operands of the same heading -- same as how Appendix A handles`UNION`

using`<OR>`

.

`InnerUnion`

is equivalent to SQL`UNION CORRESPONDING`

or ISBL`UNION`

.

`InnerUnion`

can be defined equationally in terms of`NatJoin`

, so is (arguably/controversially) not 'basic' but derived.

`DUM`

aka`R00`

is defined as per Appendix A/TTM: the relation with empty heading, empty body:`REL{} {}`

.- For projection, note that the Tropashko approach uses only relation values, there's no separate mathematical 'sort' of attribute names or attribute-comma-list. So

`r1 project r2 =df r1 InnerUnion (r2 NatJoin R00)`

-- so a derived operator.- Note that
`r2`

is unrestricted apart from needing to be join-compatible so might have attributes that don't appear in`r1`

-- or indeed its heading might be disjoint from`r1`

, in which case the`project`

=`r1 InnerUnion R00`

.- For semijoin

`r1 MATCHING r2 =df (r1 NatJoin r2) InnerUnion (r1 NatJoin R00)`

-- so a derived operator.- For anti(semi)join,
`NOTMATCHING`

behaves as per Appendix A. It is the solution to the simultaneous equations -- so a derived operator.

`(r1 NOTMATCHING r2) InnerUnion (r1 NatJoin r2) = r1`

`(r1 NOTMATCHING r2) NatJoin (r1 NatJoin r2) = r1 NatJoin r2 NatJoin R00`

- Also:
`r1 MATCHING r2 = r1 NOTMATCHING (r1 NOTMATCHING r2)`

-- generalised from McGoveran & Date 1994- For restriction/
`WHERE`

, use relcons with`NatJoin`

-- same approach as Appendix A.- For
`EXTEND`

, use relcons with`NatJoin`

-- same approach as Appendix A.- For
`RENAME`

, dispense with it using relcons with`COMPOSE`

-- same approach as Appendix A. And I am dubious about that approach; but it's no worse than Appendix A.`r1 COMPOSE r2 =df (r1 NatJoin r2) REMOVE (r1 InnerUnion r2)`

-- so a derived operator; not a "macro" operator -- whatever Appendix A's scare quotes are trying to convey.`r1 REMOVE r2`

is`r1`

projected on the attributes not in common with`r2`

. Note that`r2`

is unrestricted apart from needing to be join-compatible so might have attributes that don't appear in`r1`

-- or indeed its heading might be disjoint from`r1`

, in which case the`REMOVE`

is a no-op. Defined equationally, compare the definition for`NOTMATCHING`

-- so a derived operator:

`r1 NatJoin (r1 REMOVE r2) = r1`

`r1 InnerUnion (r1 REMOVE r2) = r1 REMOVE r2`

`(r1 REMOVE r2) InnerUnion r2 = r1 InnerUnion R00`

`r1 project r2 = r1 REMOVE (r1 REMOVE r2)`

- (We believe these equations sufficient to define
`REMOVE`

uniquely -- just as soon as we can equationally define`R00`

uniquely.)- Or if you've been following along the thread on complements and pseudocomplements,
`r1 REMOVE r2 = r1 InnerUnion hComp(r2)`

, in which`hComp( )`

is the (unique) relative complement of`r2 NatJoin R00`

within the convex sublattice bounded by the interval`[R10, R00]`

. (Where`R10`

is lattice bottom aka`Dumpty`

.)- For
`<NOT>`

, Clayden's Tropashko system does not include it -- preferring`NOTMATCHING`

instead. (Note that`NOTMATCHING`

is a generalisation of Codd 1972's`MINUS`

and Appendix A requires`<NOT>`

to appear only within a conjunction in the surface expression, which amounts to`NOTMATCHING`

.)If you've been following along the thread on complements and pseudocomplements,

`<NOT>`

is the (unique) relative complement within the convex sublattice bounded by the interval`[r1 NatJoin R00, r1 InnerUnion R11]`

. (Where`R11`

aka fullest-possible-relation is the (unique) absolute pseudocomplement of`R00`

.)So we've arrived at equivalent expressive power to the

Aalgebra (but with`InnerUnion`

instead of`<OR>`

). If I've left out any operators, they can be derived following Appendix A's equivalences.I agree. That's taken quite a bit of effort: thank you.

- So the final body count is: NatJoin, InnerUnion, NOTMATCHING, relcons (plus TCLOSE)?
- DUM is a relcon, why define it separately?
- as far as I was aware, AA does not dispense with RENAME (see p a.7)
- AA does discuss further reductions (see pa.8) which would place in on much the same footing.
This seems to be on a par with AA but does not formally treat relcons, aggregation or transitive closure. So the expressive power is on a par with AA (except for TCLOSE), and lower than the ERA I have presented.

But overall the similarities are more striking than the differences. Are these different algebras, or just variations on a theme?

Quote from AntC on July 8, 2021, 12:37 pmQuote from dandl on July 8, 2021, 8:51 am`SUMMARIZE`

and`GROUP`

in terms of the operators previously defined. What's not formal enough about it?

The specification goes as far as <summary spec> on page a.18 but no further. Functions such as min/max/sum and generic aggregation as per TTM RM Pre 6 are not specified here, but they are in mine.

As well as the algebra I would include

`DUM`

and relational assignment in any language based on it.If Tropas[h]ko has a full set of definitions I would be interested to see them.

- Tropashko
`^`

aka lattice meet aka`NatJoin`

specified as per Appendix A`<AND>`

.(So this caters for Codd's

`Intersection`

,`TIMES`

as special cases -- same approach as Appendix A.)

- Tropashko
`v`

aka lattice join aka`InnerUnion`

specified as follows (using the style of FORMAL DEFINITIONS in Appendix A):

- Let
`s`

be`r1 InnerUnion r2`

. It is required that if`<A, T1> ∈ Hr1`

and`<A, T2> ∈ Hr2`

, then`T1 = T2`

.Hs = Hr1 intersection Hr2

Bs = {ts : (exists tr1 and tr1 ∈ Br1 and ts ⊆ tr1) or (exists tr2 and tr2 ∈ Br2 and ts ⊆ tr2) }

`Hr1, Hr2`

is the same as Appendix A's condition on headings for`<AND>, <OR>`

aka 'join-compatible'.

The`⊆`

condition on the tuples in the bodies is taking advantage of Appendix A/TTMdefining tuples as sets. This makes the definition domain-independent, like Codd's`UNION`

, unlike`<OR>`

.

Tutorial D's`UNION`

equivalent to Codd's`UNION`

is`InnerUnion`

specialized for operands of the same heading -- same as how Appendix A handles`UNION`

using`<OR>`

.

`InnerUnion`

is equivalent to SQL`UNION CORRESPONDING`

or ISBL`UNION`

.

`InnerUnion`

can be defined equationally in terms of`NatJoin`

, so is (arguably/controversially) not 'basic' but derived.

`DUM`

aka`R00`

is defined as per Appendix A/TTM: the relation with empty heading, empty body:`REL{} {}`

.- For projection, note that the Tropashko approach uses only relation values, there's no separate mathematical 'sort' of attribute names or attribute-comma-list. So

`r1 project r2 =df r1 InnerUnion (r2 NatJoin R00)`

-- so a derived operator.- Note that
`r2`

is unrestricted apart from needing to be join-compatible so might have attributes that don't appear in`r1`

-- or indeed its heading might be disjoint from`r1`

, in which case the`project`

=`r1 InnerUnion R00`

.- For semijoin

`r1 MATCHING r2 =df (r1 NatJoin r2) InnerUnion (r1 NatJoin R00)`

-- so a derived operator.- For anti(semi)join,
`NOTMATCHING`

behaves as per Appendix A. It is the solution to the simultaneous equations -- so a derived operator.

`(r1 NOTMATCHING r2) InnerUnion (r1 NatJoin r2) = r1`

`(r1 NOTMATCHING r2) NatJoin (r1 NatJoin r2) = r1 NatJoin r2 NatJoin R00`

- Also:
`r1 MATCHING r2 = r1 NOTMATCHING (r1 NOTMATCHING r2)`

-- generalised from McGoveran & Date 1994- For restriction/
`WHERE`

, use relcons with`NatJoin`

-- same approach as Appendix A.- For
`EXTEND`

, use relcons with`NatJoin`

-- same approach as Appendix A.- For
`RENAME`

, dispense with it using relcons with`COMPOSE`

-- same approach as Appendix A. And I am dubious about that approach; but it's no worse than Appendix A.`r1 COMPOSE r2 =df (r1 NatJoin r2) REMOVE (r1 InnerUnion r2)`

-- so a derived operator; not a "macro" operator -- whatever Appendix A's scare quotes are trying to convey.`r1 REMOVE r2`

is`r1`

projected on the attributes not in common with`r2`

. Note that`r2`

is unrestricted apart from needing to be join-compatible so might have attributes that don't appear in`r1`

-- or indeed its heading might be disjoint from`r1`

, in which case the`REMOVE`

is a no-op. Defined equationally, compare the definition for`NOTMATCHING`

-- so a derived operator:

`r1 NatJoin (r1 REMOVE r2) = r1`

`r1 InnerUnion (r1 REMOVE r2) = r1 REMOVE r2`

`(r1 REMOVE r2) InnerUnion r2 = r1 InnerUnion R00`

`r1 project r2 = r1 REMOVE (r1 REMOVE r2)`

- (We believe these equations sufficient to define
`REMOVE`

uniquely -- just as soon as we can equationally define`R00`

uniquely.)- Or if you've been following along the thread on complements and pseudocomplements,
`r1 REMOVE r2 = r1 InnerUnion hComp(r2)`

, in which`hComp( )`

is the (unique) relative complement of`r2 NatJoin R00`

within the convex sublattice bounded by the interval`[R10, R00]`

. (Where`R10`

is lattice bottom aka`Dumpty`

.)- For
`<NOT>`

, Clayden's Tropashko system does not include it -- preferring`NOTMATCHING`

instead. (Note that`NOTMATCHING`

is a generalisation of Codd 1972's`MINUS`

and Appendix A requires`<NOT>`

to appear only within a conjunction in the surface expression, which amounts to`NOTMATCHING`

.)`<NOT>`

is the (unique) relative complement within the convex sublattice bounded by the interval`[r1 NatJoin R00, r1 InnerUnion R11]`

. (Where`R11`

aka fullest-possible-relation is the (unique) absolute pseudocomplement of`R00`

.)Aalgebra (but with`InnerUnion`

instead of`<OR>`

). If I've left out any operators, they can be derived following Appendix A's equivalences.

I agree. That's taken quite a bit of effort: thank you.

- So the final body count is: NatJoin, InnerUnion, NOTMATCHING, relcons (plus TCLOSE)?
- DUM is a relcon, why define it separately?
- as far as I was aware, AA does not dispense with RENAME (see p a.7)
- AA does discuss further reductions (see pa.8) which would place in on much the same footing.

This seems to be on a par with AA but does not formally treat relcons, aggregation or transitive closure. So the expressive power is on a par with AA (except for TCLOSE), and lower than the ERA I have presented.

But overall the similarities are more striking than the differences. Are these different algebras, or just variations on a theme?