Quote from dandl on July 7, 2021, 1:56 am

Quote from Darren Duncan on July 6, 2021, 3:11 am

Quote from dandl on July 6, 2021, 1:27 am

Quote from Darren Duncan on July 5, 2021, 7:05 am

And 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 am

Quote from AntC on July 6, 2021, 6:05 am

Quote from dandl on July 6, 2021, 1:45 am

Quote from AntC on July 5, 2021, 9:54 pm

Quote from Dave Voorhis on July 5, 2021, 3:06 pm

Quote 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 a relational algebra. There is nothing so definitive as to be considered the Relational 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.

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.

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.

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 am

Quote from dandl on July 7, 2021, 3:09 am

Quote from AntC on July 6, 2021, 6:05 am

Quote from dandl on July 6, 2021, 1:45 am

Quote from AntC on July 5, 2021, 9:54 pm

Quote from Dave Voorhis on July 5, 2021, 3:06 pm

Quote 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 a relational algebra. There is nothing so definitive as to be considered the Relational 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.

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.

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.

Quote from dandl on July 8, 2021, 1:16 am

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 am

Quote from dandl on July 8, 2021, 1:16 am

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)?

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.

 

• 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, 8:51 am

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 am

Quote from dandl on July 8, 2021, 1:16 am

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

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)?

No, because there isn't.

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

See AntC's answer.

Quote from AntC on July 8, 2021, 12:37 pm

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.

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 am

Quote from AntC on July 8, 2021, 12:37 pm

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?

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

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?