Formal definitions for Relation Constant, Transitive Closure, Extended Transitive Closure
The definition for ETCLOSE could have a constraint along the lines of:
and not exists w such that <A,B,w> is a member of Bs
This prohibits duplicate paths. Then we could have an ETCLOSE2 with all the <A,B,W> replaced by <A,B,C,W> to allow duplicate paths with different weights.
But this doesn't solve the problem posed by D&D, to compute a GTC with no extra key attribute. Which now looks rather harder. Ideas?
Side note: Union is not needed. The final result is always just the last term of the series.
Quote from dandl on February 24, 2021, 5:53 amThe definition for ETCLOSE could have a constraint along the lines of:
and not exists w such that <A,B,w> is a member of Bs
This prohibits duplicate paths. Then we could have an ETCLOSE2 with all the <A,B,W> replaced by <A,B,C,W> to allow duplicate paths with different weights.
But this doesn't solve the problem posed by D&D, to compute a GTC with no extra key attribute. Which now looks rather harder. Ideas?
Side note: Union is not needed. The final result is always just the last term of the series.
I suppose the difference might be if there is to be an aggregation afterwards or not?
So if each derived tuple is "a part of the final aggregation", it must be identified uniquely and we can later project the identifier away in the aggregation.
Otherwise, if no aggregation, then each derived tuple is just a fact and gets deduplicated.
Would there be cases where we want to keep track of the entire path, but not do an aggregation? Perhaps the org-chart "manager-report" where we collect up the "chain-of-command" as we go along?
EDIT: I am starting to think that maybe the function combining the C values should really be creating something new, a D value.
So you start with the relation S with attributes A,B of the same type and C to be collected.
Create S0 with attributes A,B and D, where D is a start value for the collecting variable, derived from the C.
Then S0 join S gives S1 and the function is now a function of a D and a C to yield a new D. S1 join S gives S2 and so on.
Now it's up to the user to do the sane thing with the D-creation, which could even be a tuple itself.
We should allow for the absence of C's as well to cover the chain-of-command case.
This could then even cover the ordinary TCLOSE by setting D to be a constant and is projected away at the end.
After giving this some thought I've come to the conclusion that there is no single GTC. The D&D description is misleading. As they say, it's all in the predicate.
The predicate for <A,B> is: A and B are nodes in a graph, and there is a direct path from A to B. For the TC it's: A and B are nodes in a graph, and there is a path from A that eventually reaches B. The CWA applies.
The predicate for <A,B,W> is not so easy. It could be:
- A is the parent of B, and the GTC is a genetic family tree
- A a container of B and the GTC is a parts explosion showing total parts usage
- A is a route to B and the GTC is a route map showing the shortest path
- and there are others.
D&D only addresses the second, but I don't think it's reasonable to pick just this one. In any case, I don't see there could be a single GTC addressing all these situations in one step.
So I think GTC has to resemble my ETC, but the result is <A,B,W,X> where X is a unique identifier of the path. Then an aggregation will pick out the answer we want, according to the chosen predicate.
Further thoughts: I cannot see any way to define a GTC similar to D&D down this path. The ETCLOSE I defined works fine for a tree, but not for a DAG or other kind of graph. I don't see any way to enumerate paths through the graph using FPL. Everything I've tried finishes up looking like while.
So my hypothesis is that while (as defined in Alice) is the least powerful construct able to compute a GTC. It's easy to implement, and could be added to TD/Rel is a matter of hours. It is familiar to those who know SQL CTE RECURSIVE, being almost identical in operation. It handles GTC with ease.
However: while is safe, but if combined with new value the result can be of infinite size. in effect, it enables counting. Since GTC requires new value, the question arises whether there is any construct that is sufficient for GTC but is also safe.
Quote from dandl on March 1, 2021, 5:10 amFurther thoughts: I cannot see any way to define a GTC similar to D&D down this path. The ETCLOSE I defined works fine for a tree, but not for a DAG or other kind of graph. I don't see any way to enumerate paths through the graph using FPL. Everything I've tried finishes up looking like while.
So my hypothesis is that while (as defined in Alice) is the least powerful construct able to compute a GTC. It's easy to implement, and could be added to TD/Rel is a matter of hours.
I think we've discussed this before, and my impression -- correct me if I'm wrong -- is that Tutorial D effectively generalises the functionality of while by allowing recursive user-defined operators/functions. Thus, a distinct WHILE operator is not necessary.
Quote from Dave Voorhis on March 1, 2021, 10:25 amQuote from dandl on March 1, 2021, 5:10 amFurther thoughts: I cannot see any way to define a GTC similar to D&D down this path. The ETCLOSE I defined works fine for a tree, but not for a DAG or other kind of graph. I don't see any way to enumerate paths through the graph using FPL. Everything I've tried finishes up looking like while.
So my hypothesis is that while (as defined in Alice) is the least powerful construct able to compute a GTC. It's easy to implement, and could be added to TD/Rel is a matter of hours.
I think we've discussed this before, and my impression -- correct me if I'm wrong -- is that Tutorial D effectively generalises the functionality of while by allowing recursive user-defined operators/functions. Thus, a distinct WHILE operator is not necessary.
Not really. At the time of writing TTM D&D had a clear concept of the Codd RA/TM (in Alice terms SPJRUN) and as reflected formally in App-A. They knew they needed the 3 RA extensions (new value, aggregation and TC), but not how to define them formally in App-A. They did not have a good understanding of generalised aggregation or GTC and it seems they had never heard of while.
The focus of their work is adding a type system for attributes, and a GP TC language as a viable replacement for SQL, and TTM reflects that. The formal underpinnings for the 3 extensions are missing. They just didn't know how. TTM now lists those as OO Pre 6 and RM VSS 5, but they're still not fully defined or in the language.
But as we all know, a GP TC language can compute anything: it's the ultimate fallback if you can't find anything better. I think SQL CTE RECURSIVE is better than hand-coded SQL, and I think while is better than hand-coded TD. YMMV.
Quote from dandl on March 4, 2021, 4:41 amQuote from Dave Voorhis on March 1, 2021, 10:25 amQuote from dandl on March 1, 2021, 5:10 amFurther thoughts: I cannot see any way to define a GTC similar to D&D down this path. The ETCLOSE I defined works fine for a tree, but not for a DAG or other kind of graph. I don't see any way to enumerate paths through the graph using FPL. Everything I've tried finishes up looking like while.
So my hypothesis is that while (as defined in Alice) is the least powerful construct able to compute a GTC. It's easy to implement, and could be added to TD/Rel is a matter of hours.
I think we've discussed this before, and my impression -- correct me if I'm wrong -- is that Tutorial D effectively generalises the functionality of while by allowing recursive user-defined operators/functions. Thus, a distinct WHILE operator is not necessary.
Not really. At the time of writing TTM D&D had a clear concept of the Codd RA/TM (in Alice terms SPJRUN) and as reflected formally in App-A. They knew they needed the 3 RA extensions (new value, aggregation and TC), but not how to define them formally in App-A. They did not have a good understanding of generalised aggregation or GTC and it seems they had never heard of while.
The focus of their work is adding a type system for attributes, and a GP TC language as a viable replacement for SQL, and TTM reflects that. The formal underpinnings for the 3 extensions are missing. They just didn't know how. TTM now lists those as OO Pre 6 and RM VSS 5, but they're still not fully defined or in the language.
But as we all know, a GP TC language can compute anything: it's the ultimate fallback if you can't find anything better. I think SQL CTE RECURSIVE is better than hand-coded SQL, and I think while is better than hand-coded TD. YMMV.
SQL CTE seems a kludgy way to incorporate something akin to general programming capabilities into the SQL evaluation model. Non-recursive SQL CTE has an equivalent in Tutorial D's WITH; recursive CTE is handled with a Tutorial D recursive operator.
WHILE is a loop or recursion over UNION.
I'm all for adding these if Hugh & Chris see fit to update Tutorial D to include while, but I'm not yet convinced there's a compelling reason to add it otherwise.
Quote from Dave Voorhis on March 4, 2021, 9:38 amQuote from dandl on March 4, 2021, 4:41 amQuote from Dave Voorhis on March 1, 2021, 10:25 amQuote from dandl on March 1, 2021, 5:10 amFurther thoughts: I cannot see any way to define a GTC similar to D&D down this path. The ETCLOSE I defined works fine for a tree, but not for a DAG or other kind of graph. I don't see any way to enumerate paths through the graph using FPL. Everything I've tried finishes up looking like while.
So my hypothesis is that while (as defined in Alice) is the least powerful construct able to compute a GTC. It's easy to implement, and could be added to TD/Rel is a matter of hours.
I think we've discussed this before, and my impression -- correct me if I'm wrong -- is that Tutorial D effectively generalises the functionality of while by allowing recursive user-defined operators/functions. Thus, a distinct WHILE operator is not necessary.
Not really. At the time of writing TTM D&D had a clear concept of the Codd RA/TM (in Alice terms SPJRUN) and as reflected formally in App-A. They knew they needed the 3 RA extensions (new value, aggregation and TC), but not how to define them formally in App-A. They did not have a good understanding of generalised aggregation or GTC and it seems they had never heard of while.
The focus of their work is adding a type system for attributes, and a GP TC language as a viable replacement for SQL, and TTM reflects that. The formal underpinnings for the 3 extensions are missing. They just didn't know how. TTM now lists those as OO Pre 6 and RM VSS 5, but they're still not fully defined or in the language.
But as we all know, a GP TC language can compute anything: it's the ultimate fallback if you can't find anything better. I think SQL CTE RECURSIVE is better than hand-coded SQL, and I think while is better than hand-coded TD. YMMV.
SQL CTE seems a kludgy way to incorporate something akin to general programming capabilities into the SQL evaluation model. Non-recursive SQL CTE has an equivalent in Tutorial D's WITH; recursive CTE is handled with a Tutorial D recursive operator.
Not at all. CTE makes big SQL queries easier to manage, exactly like WITH. RECURSIVE (and windowing) add major functionality without the need to write and debug a separate stored procedure.
WHILE is a loop or recursion over UNION.
That's misleading. In very loose terms:
- project and new value are about removing and adding attributes
- join, union and not are about slicing and dicing
- select (where) and while are about removing and adding tuples.
Using while and new value in concert a query can construct a relation of any dimensions partly or entirely of computed content. It fills what is otherwise a gap in the RA.
I'm all for adding these if Hugh & Chris see fit to update Tutorial D to include while, but I'm not yet convinced there's a compelling reason to add it otherwise.
As I said, I don't think they were ever able to formally define the entire extended RA, and their treatment of relcons, aggregation and GTC are all incomplete. I think it's too late to fix that now, but at least adding while would satisfy the VSS for GTC. They do acknowledge that SQL has the edge there.
Quote from dandl on March 4, 2021, 1:31 pmQuote from Dave Voorhis on March 4, 2021, 9:38 amQuote from dandl on March 4, 2021, 4:41 amQuote from Dave Voorhis on March 1, 2021, 10:25 amQuote from dandl on March 1, 2021, 5:10 amFurther thoughts: I cannot see any way to define a GTC similar to D&D down this path. The ETCLOSE I defined works fine for a tree, but not for a DAG or other kind of graph. I don't see any way to enumerate paths through the graph using FPL. Everything I've tried finishes up looking like while.
So my hypothesis is that while (as defined in Alice) is the least powerful construct able to compute a GTC. It's easy to implement, and could be added to TD/Rel is a matter of hours.
I think we've discussed this before, and my impression -- correct me if I'm wrong -- is that Tutorial D effectively generalises the functionality of while by allowing recursive user-defined operators/functions. Thus, a distinct WHILE operator is not necessary.
Not really. At the time of writing TTM D&D had a clear concept of the Codd RA/TM (in Alice terms SPJRUN) and as reflected formally in App-A. They knew they needed the 3 RA extensions (new value, aggregation and TC), but not how to define them formally in App-A. They did not have a good understanding of generalised aggregation or GTC and it seems they had never heard of while.
The focus of their work is adding a type system for attributes, and a GP TC language as a viable replacement for SQL, and TTM reflects that. The formal underpinnings for the 3 extensions are missing. They just didn't know how. TTM now lists those as OO Pre 6 and RM VSS 5, but they're still not fully defined or in the language.
But as we all know, a GP TC language can compute anything: it's the ultimate fallback if you can't find anything better. I think SQL CTE RECURSIVE is better than hand-coded SQL, and I think while is better than hand-coded TD. YMMV.
SQL CTE seems a kludgy way to incorporate something akin to general programming capabilities into the SQL evaluation model. Non-recursive SQL CTE has an equivalent in Tutorial D's WITH; recursive CTE is handled with a Tutorial D recursive operator.
Not at all. CTE makes big SQL queries easier to manage, exactly like WITH. RECURSIVE (and windowing) add major functionality without the need to write and debug a separate stored procedure.
It only makes big SQL queries somewhat easier to manage, with an abominable syntax that's apparently the only way to fit the requisite syntax into SQL's single-expression model.
It's a workaround, not a benefit.
WHILE is a loop or recursion over UNION.
That's misleading. In very loose terms:
- project and new value are about removing and adding attributes
- join, union and not are about slicing and dicing
- select (where) and while are about removing and adding tuples.
Using while and new value in concert a query can construct a relation of any dimensions partly or entirely of computed content. It fills what is otherwise a gap in the RA.
It's not misleading, and it's not a gap in "the" (?) RA.
I'm all for adding these if Hugh & Chris see fit to update Tutorial D to include while, but I'm not yet convinced there's a compelling reason to add it otherwise.
As I said, I don't think they were ever able to formally define the entire extended RA, and their treatment of relcons, aggregation and GTC are all incomplete. I think it's too late to fix that now, but at least adding while would satisfy the VSS for GTC. They do acknowledge that SQL has the edge there.
Not sure what "the entire extended RA" means and whilst the formal definitions may be incomplete, Tutorial D is complete for its purposes.
Again, if D&D see fit to add WHILE or other mechanisms to Tutorial D, then I'm happy to add them to Rel.
Otherwise, I add extensions to suit my own purposes and meet user requests, and so far I haven't seen a compelling need for WHILE and I haven't had a user request it. Note that Rel is open source and on GitHub, so anyone can send me merge requests. I'll approve them if the code is good, and in return I will add the contributor(s) to my distributed AUTHORS.txt file.
WHILE is a loop or recursion over UNION.
That's misleading. In very loose terms:
- project and new value are about removing and adding attributes
- join, union and not are about slicing and dicing
- select (where) and while are about removing and adding tuples.
Using while and new value in concert a query can construct a relation of any dimensions partly or entirely of computed content. It fills what is otherwise a gap in the RA.
It's not misleading, and it's not a gap in "the" (?) RA.
I'm all for adding these if Hugh & Chris see fit to update Tutorial D to include while, but I'm not yet convinced there's a compelling reason to add it otherwise.
As I said, I don't think they were ever able to formally define the entire extended RA, and their treatment of relcons, aggregation and GTC are all incomplete. I think it's too late to fix that now, but at least adding while would satisfy the VSS for GTC. They do acknowledge that SQL has the edge there.
Not sure what "the entire extended RA" means and whilst the formal definitions may be incomplete, Tutorial D is complete for its purposes.
This is the nub of the problem: you don't know and D&D don't know and you really should.We all should.
- Codd defined the RA at the level of Alice's SPJRUN, in algebraic form, with no type system and with all values created as literals.Very precisely, formally.
- TTM requires the 'usual operators of the relational algebra' without ever defining precisely what those are.
- DTATRM has a lengthy section on the subject, but mostly it is a definition of TD, not the RA. And it is incomplete (OO Pre 6 and RM VSS 5).
My definition of the ERA is roughly:
- Codd's RA extended to the point where queries are at least as powerful as SQL. That turns out to be new value, aggregation and while/recursion (SPJRUN+VAW).
- Not bound to any particular type system. That excludes GROUP and UNGROUP, which rely on RVA/TVA in the type system.
- In algebraic form and not bound to any particular language syntax. That precludes using TD to define the ERA; TD should be defined by reference to the ERA.
TD is incomplete because of its many omissions, as you are aware. Rel is complete, because it is its own definition, but as a query language it is less powerful than SQL.
Again, if D&D see fit to add WHILE or other mechanisms to Tutorial D, then I'm happy to add them to Rel.
Otherwise, I add extensions to suit my own purposes and meet user requests, and so far I haven't seen a compelling need for WHILE and I haven't had a user request it. Note that Rel is open source and on GitHub, so anyone can send me merge requests. I'll approve them if the code is good, and in return I will add the contributor(s) to my distributed AUTHORS.txt file.
That sounds like the railway company who wouldn't build a station in the town because there weren't any people getting on or off trains who might need one. Build one and they might come.