# Relational Completeness: not just about choice of operators

Quote from AntC on March 30, 2019, 9:49 amI 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 "

Dshall support the equality comparison operator “=” for every typeT." That is, whether or not equality is included in "the usual operators of therelational 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)DEErepresents True/relations are equal,DUMrepresents 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

DEEproviding I know the name of a relation in the database that is guaranteed to be non-empty. I can defineDUMproviding 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, andFare propositions andFis known to be false, ...Ok. Then I think it's legitimate to add

DEEas a primitive, even though it's not an operator. Of courseDUM=_{df}DEEMINUSDEE. Now I can define an equality test to returnDEEorDUMand I'm in business.

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

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, andFare propositions andFis 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.

Quote from dandl on March 30, 2019, 12:35 pmQuote from AntC on March 30, 2019, 9:49 amI 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

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

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

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.