0

Why are quantifiers needed in Tuple Relational Calculus?
Lets say I have this statement:

{S.sname | S in Student and (exists G in Grade )(S.s# = G.s#)};

Why can't I just use this instead?

{S.sname | S in Student and G in Grade and S.s# = G.s#};

user1766555
  • 553

1 Answers1

1

When you write "$\{S: $ stuff about $S$ and $G\}$", what does $G$ mean? Think about it this way: if I say "The set of people who bought Sam a penguin," this describes a set - except you don't know who Sam is. Now, by contrast, "The set of people who bought someone a penguin" makes perfect sense. This latter sentence has the form "$\{S: \exists G($stuff$)\}$": it is $\{p$: there exists a person $q$ such that $p$ bought $q$ a penguin$\}$.

The point is that you need the "$\exists$" to make what you're writing fully meaningful: free variables - that is, variables not bound by a quantifier, or introduced via set-builder notation - are inherently ambiguous.

Noah Schweber
  • 245,398
  • What's the difference between free and bound variables? Is there a limit on free and bound variables, such as the amount you are allowed to have? – user1766555 Oct 23 '16 at 15:56
  • 1
    @user1766555 A free variable is, as I said, a variable not bound by a quantifier or introduced via some operation like set-builder notation (arguably "${x:$" is a kind of quantifier, although that's an odd view and beside the point). And no, there is no limit on the number you're allowed. See the wiki page for more details. – Noah Schweber Oct 23 '16 at 16:00
  • Could I have a valid example of where there's a query of 2 free variables and no bound variables? Where each variable is under a different column? – user1766555 Oct 23 '16 at 16:03
  • @user1766555 I'm not sure what you mean by "each variable is under a different column," but consider the formula "$x+y+z+w=4$". This is a perfectly well-formed formula (well, technically I should have thrown in parentheses but oh well), and has four free variables. It is not, however, a sentence - it does not make sense to say that it is true, or that it is false. Meanwhile, "$\forall x\forall y\forall z\forall w(x+y+z+2=4)$" is a perfectly legitimate (if false) sentence. We can also have multiple variables show up in set builder notation: e.g. "${x: {y: x+y$ is even$}$ is infinite$}$". – Noah Schweber Oct 23 '16 at 20:16