How to decide whether this query in domain relational calculus is domain-independent?

Question

I am trying to understand whether the following query is domain-independent:

{t : ∀x ∀y ( (x≠y ∧ R(t,x) ∧ T(t,y)) → S(x,y) )

I think that this query is domain-independent because the left side of → forces it to be in every domain. Is that so?

Answer 1

I guess → is intended as material implication.

Then we can convert the predicate in the given query, using Boolean algebra equivalences:

• p → q == ¬p ∨ q -- so need to negate the LHS of implication
• ¬(p1 ∧ p2) == ¬p1 ∨ ¬p2 -- note the LHS of the given implication is a conjunction
• ¬(x ≠ y) == x = y

Then (omitting superfluous parens):

( (x≠y ∧ R(t,x) ∧ T(t,y)) → S(x,y) )
==
( x=y ∨ ¬R(t,x) ∨ ¬T(t,y) ∨ S(x,y) )

Observations:

• The disjunct x=y is Domain Dependent: x, y are universally quantified, the equality test doesn't require them to be drawn from any relation.
• The disjuncts ¬R(t,x) and ¬T(t,y) are negations of relation membership, so are Domain Dependent.
• S(x,y) is a relation membership, so is Domain Independent -- but since it's only one of the disjuncts, it doesn't rescue the overall query.
• Conclusion: the query overall is Domain Dependent.

(I can't tell what "forces it [what?] to be in every domain" is trying to say.)

At that link to Boolean Algebra, note what it says about Material Implication aka Material Conditional (I've changed the variable names to reflect the workings here.):

But if p is false, then the value of q can be ignored;

In other words, if the LHS expression is false, membership in S(x,y) can be ignored, so S(x,y) fails to constrain x,y. Then that t appears only in R(t,x) and T(t,y) is no help in constraining t: both those appearances are on LHS of the implication.

Edit: 'fails to constrain' here means fails to limit x,y or t to range over values appearing in tuples in ground relations.