-2

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?

philipxy
  • 14,867
  • 6
  • 39
  • 83
JobProcessTask
  • 123
  • 6
  • Your phrases are not clear & your reasoning is not clear. What does "the left side of → forces" mean? "forces it" What is "it"? What is the reasoning that justifies "because"? Give small clear steps of reasoning that are eventually connected to definitions/theorems/algorithms that you quote. What is your textbook name & edition? Use enough words, sentences & references to parts of examples to clearly & fully say what you mean. Look at examples you have been given. What is your 1 exact question? Your title asks one & your post asks another. PS That is not tuple calculus, it is domain calculus. – philipxy Jul 19 '22 at 20:27
  • Please link to a reference for what notation you're using. It seems to be not this: https://en.wikipedia.org/wiki/Domain_relational_calculus; nor Codd's Tuple Relational Calculus https://en.wikipedia.org/wiki/Tuple_relational_calculus -- which is what he used to define Domain Independence. Your notation seems to borrow from both. Does `R(t,x)` etc mean a named relation? Then you are using positional notation, not attribute naming? – AntC Jul 20 '22 at 01:53

1 Answers1

0

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.

AntC
  • 2,623
  • 1
  • 13
  • 20
  • "Conclusion: the query overall is Domain Dependent" But the expression processed is not the "the given query"/"the overall query" either in the sense of the set comprehension or the RHS wff of it, it's nested within it, you don't justify how quantification affects it, so this doesn't determine whether the overall query is domain dependent. PS "constrain" is unexplained. – philipxy Jul 20 '22 at 06:39
  • Comprehension including in relational calculi is of the form `{ tuple | wff }` & an older math convention was to use `:` as an alternative to `|`. Since they say it's a calculus query, there should be a closing wff `}` & they are apparently asking for tuples with one column satisfying the wff, though it's not clear what the correct syntax would be or what their relations are exactly. – philipxy Jul 21 '22 at 01:44