The Forum for Discussion about The Third Manifesto and Related Matters

You need to log in to create posts and topics.

Relational Completeness: not just about choice of operators

I continue to mull whether Codd's 1972 definition of 'Relational Completeness' is complete enough to define any operation over relations.

In particular, how to define a test for equality between relations?

Contrast that TTM (RM Pre 8) prescribes "D shall support the equality comparison operator “=” for every type T." That is, whether or not equality is included in "the usual operators of the relational algebra (or some logical equivalent thereof)." (RM Pre 18)

 

There's an immediate problem: RM Pre 8's operator returns a boolean, and type boolean is required to be included in a D, per RM Pre 1. Codd's algebra included only relations, not any scalar types specifically. That's not too bad; we could adopt some convention that (say) DEE represents True/relations are equal, DUM represents False.

And since I'm talking about a "logical equivalent" to an operator, I don't need to include testing equality between relations as a primitive. I could define it in terms of subset tests between relations (with other operators); or in terms of IS_EMPTY( ) with other operators. But try as I might, I couldn't define those in terms of Codd's primitives. The best I could do was: give me two relation values (extra to the ones I'm comparing), I'll return the first if the comparison is True, the second otherwise.

Codd's primitives don't give any way to express a relation literal. I can define DEE providing I know the name of a relation in the database that is guaranteed to be non-empty. I can define DUM providing I know the name of any relation at all in the database. But that seems terribly ad-hoc: the algebra should be complete even if the database is completely empty.

Then I've just come across 1 a discussion of 'functional completeness' of a logic, specifically the implicational fragment of the Propositional Calculus.

[Material] Implication alone is not functionally complete as a logical operator because one cannot form all other two-valued truth functions from it. However, if one has a propositional formula which is known to be false and uses that as if it were a nullary connective for falsity, then one can define all other truth functions. So implication is virtually complete as an operator. If P,Q, and F are propositions and F is known to be false, ...

Ok. Then I think it's legitimate to add DEE as a primitive, even though it's not an operator. Of course DUM =df DEE MINUS DEE. Now I can define an equality test to return DEE or DUM and I'm in business.

 

1 - https://en.wikipedia.org/wiki/Implicational_propositional_calculus#Virtual_completeness_as_an_operator

 

Quote from AntC on March 30, 2019, 9:49 am

I continue to mull whether Codd's 1972 definition of 'Relational Completeness' is complete enough to define any operation over relations.

...

Codd's primitives don't give any way to express a relation literal.

I think you answered the part of your own question dealing with booleans. It seems reasonable to assume some mechanism for creating the relational values on which the RA operates (and which are presented in his papers), and that given any plausible mechanism it could be used to create DEE and DUM if they didn't already exist. Problem solved.

But there are many other operations that the RA cannot perform. The first that come to mind are:

  • Anything to do with RVAs and TVAs (NEST, UNNEST, etc)
  • Anything that depends on computation or counting, since the RA is only first order (COUNT, ISEVEN, FOLD/SUM, WHILE, etc).

You don't need a type system, but you do need something more than the RA.

Andl - A New Database Language - andl.org