Quote from Dave Voorhis on August 25, 2019, 8:23 am

Quote from dandl on August 25, 2019, 7:10 am

The RA described by Codd in 1972 was founded on first order predicate logic. Call that FORA. With additions by HHT and TTM it has the following familiar features.

1. Relations, normalised, sets of tuples
2. Domains (roughly scalar types)
3. Selectors/attribute names (per HHT)
4. Literals of various types (corresponding to domains)
5. Operations on relations that yield other relations
6. Transitive closure (TCLOSE in TTM)
7. Closed functions of various types (domains).

I include closed functions here because they can always be rewritten as literals before applying any operations of the RA.

The second order RA (SORA) then includes the following.

1. Open functions of various types (domains)
2. Aggregating functions, including summarize, group and ungroup, wrap and unwrap, image relations
3. Fixed point recursion (while from Alice, GTC in DBE, CTE RECURSIVE in SQL)

Note that apart from while, the only thing needed to transform the FORA into SORA is the ability to replace a literal in some domain by a function.  All functions are assumed pure and provably safe (guaranteed to terminate). The result is a query language of immense power, which nevertheless expresses only safe queries.

The Turing Complete RA (TCRA) then includes the following.

1. GP language features such as recursive functions, loops, storage, assignment, etc.

This is actually a bit simplistic. Alice has a lengthy discussion on the subject, which I shall not attempt to paraphrase.

The stated intent of TTM and the syntactical form adopted by Tutorial D conceal the simplicity of the underlying algebra. It's just the FORA plus functions on domains, that's all.

The functions required by SORA must be implemented in one or more domain-specific languages, and in TD we have a host language, an RA language and a domain-specific function language all mixed up together. SQL is a mediocre implementation of the SORA, with a number of defects and a predefined set of domain functions. Aldat referred to the function-implementing language as a domain algebra, separate from the RA. Andl can be used as pure SORA, but strays elsewhere.

In summary: FORA is Codd, slightly extended, not very useful. SORA is what we use when we write queries in SQL, and what we should aspire to. IMO.

What we should aspire to for what?

I don't see any mention of the intended goal here. A better database language to replace SQL? A better programming language? Academic exploration of language design? A D per TTM? Something else?

Without a clear goal, this all seems to be much academic waffle -- which is reasonable for its own sake, but is that the goal here? (Perhaps the fact that this is in the "Database Theory" subforum answers that question.)

Quote from dandl on August 25, 2019, 1:47 pm

Sorry if that wasn't clear: my aim was always to arrive at a definition for "the usual operators of the RA" as per RM Pre 18.

TTM did us all a big disservice by failing to clarify what was intended here. One might assume it means the RA from Codd, but that would be the FORA and clearly that falls well short. No matter what you say about there not being "the RA", the FORA is self evidently not capable of satisfying the goal for TTM as a whole. So if not that, then what? I don't think D&D kept it a secret, I rather suspect they just didn't know what to say.

The key insight I think is the open function, one that can be substituted for a literal value in an operation of the RA, will be invoked multiple times in producing a result, and thereby makes this no longer first order logic. The only D&D reference I can find is to an "open expression" in the context of Tutorial D, but I think it is a far more fundamental concept. Every implementor of TTM D has read this para and implemented some kind of RA with embedded functions: a SORA and never a FORA. But they had to work this out for themselves, with only SQL and Tutorial D to guide them., nothing in TTM.

If the goal was to include a powerful query sub-language in some GP host language, then the SORA is what you need (not TTM D). LINQ probably already does that.

Quote from johnwcowan on August 25, 2019, 5:31 pm

Quote from dandl on August 25, 2019, 1:47 pm

The key insight I think is the open function, one that can [sic; ? cannot] be substituted for a literal value in an operation of the RA, will be invoked multiple times in producing a result, and thereby makes this no longer first order logic.

It sounds like you are talking about functions whose values depend on something other than their arguments, but you may also mean functions with side effects; the term pure function, which I take to be a synonym for your use of closed function, is unfortunately ambiguous between these concepts, being sometimes those functions which violate the second only and sometimes those that violate either.

I accept that the presence of open functions makes the underlying logic not first-order, but I am not yet convinced that it is even second-order.  Can you provide a proof sketch?

The only D&D reference I can find is to an "open expression" in the context of Tutorial D, but I think it is a far more fundamental concept.

Agreed.  The term open expression shows a failure to recognize that such things are representable as closures.  Well, none of us can know everything.

Quote from Dave Voorhis on August 25, 2019, 5:38 pm

Quote from dandl on August 25, 2019, 1:47 pm

Sorry if that wasn't clear: my aim was always to arrive at a definition for "the usual operators of the RA" as per RM Pre 18.

TTM did us all a big disservice by failing to clarify what was intended here. One might assume it means the RA from Codd, but that would be the FORA and clearly that falls well short. No matter what you say about there not being "the RA", the FORA is self evidently not capable of satisfying the goal for TTM as a whole. So if not that, then what? I don't think D&D kept it a secret, I rather suspect they just didn't know what to say.

The key insight I think is the open function, one that can be substituted for a literal value in an operation of the RA, will be invoked multiple times in producing a result, and thereby makes this no longer first order logic. The only D&D reference I can find is to an "open expression" in the context of Tutorial D, but I think it is a far more fundamental concept. Every implementor of TTM D has read this para and implemented some kind of RA with embedded functions: a SORA and never a FORA. But they had to work this out for themselves, with only SQL and Tutorial D to guide them., nothing in TTM.

If the goal was to include a powerful query sub-language in some GP host language, then the SORA is what you need (not TTM D). LINQ probably already does that.

Sorry, what are SORA and FORA again?

I read your post where you introduced them, but my understanding of it doesn't help me make sense of the parts of your post that make reference to SORA/FORA. Is there perhaps a way to rephrase them using familiar terms?

By "open function" do you mean a lambda expression?

At the time TTM was written (and, arguably, perhaps still true today), wouldn't "open functions" have been considered an internal implementation detail and not something to be exposed by a surface language intended to replace SQL, and/or orthogonal to TTM?

Aren't "the usual operators of the RA" made theoretically clear by (at least) Appendix A, and illustrated -- if not stated explicitly -- by Tutorial D?