0
$\begingroup$

There's a parlour game of inventing exotic operators for Relational Algebra, and thereby reducing the number of operators needed to be 'Relationally Complete'. A popular operator for this is 'Inner Union' aka SQL's UNION CORRESPONDING.

I've just bumped into a single-operator basis for FOL, due to Schönfinkel. It's a combo of Sheffer stroke (written infix |) and existential quant (with the bound var superscripted).

P(x) |x Q(x) ≡ ¬∃x.(P(x)∧Q(x))

Q 1. Could there be a Relational Operator corresponding to that?

Q 2. If so, does that mean there could be a version of Relational Algebra with only one operator?

Q 3. If not, in what sense is Codd's 1972 set "complete"?

My thoughts so far:

Q 1. No. The FOL corresponds OK to RA (Natural Join). The corresponds OK to 'Remove' aka project-away, sometimes written π-hat. But RA can only express correspondence to negation when ¬ is nested inside . I.e. FOL P(x) ∧ ¬Q(x) corresponds to RA P MINUS Q. Whereas this single FOL operator has ¬ at outer level (i.e. absolute complement, not relative).

The reason Codd doesn't allow absolute complement is it makes queries 'unsafe', that is domain-dependent.

Q 2. Then no. Supplementary q: it's well known Codd omitted RENAME/ρ from his original set. Rename is needed to translate a FOL expression using = between variables:

∃x. P(x) ∧ (x = y)       -- corresponds to

ρ{y := x }(P)            -- relation P with attrib x

Presumably Schönfinkel's operator doesn't avoid the need for =(?).

Q 3. Then how does Codd's original RA express an equivalent to a FOL expression with outermost ¬? Or outermost , which is the same thing:

∀y.Q(y)≡¬∃y.¬Q(y)
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.