0

Quoting the general expression of Tuple Relational Calculus (Fundamentals of Database Systems - Elmasri, Navathe; 6th edition)

A general expression of the tuple relational calculus is of the form

{t1.Aj, t2.Ak, ..., tn.Am | COND(t1, t2, ..., tn, tn+1, tn+2, ..., tn+m)}

where t1, t2, ..., tn, tn+1, ..., tn+m are tuple variables, each Ai is an attribute of the relation on which ti ranges, and COND is a condition or formula of the tuple relational calculus. A formula is made up of predicate calculus atoms, which can be one of the following:

1. An atom of the form R(ti), where R is a relation name and ti is a tuple variable. This atom identifies the range of the tuple variable ti as the relation whose name is R. It evaluates to TRUE if ti is a tuple in the relation R, and evaluates to FALSE otherwise.

2. An atom of the form ti.A op tj.B, where op is one of the comparison operators in the set {=, <, ≤, >, ≥, ≠}, ti and tj are tuple variables, A is an attribute of the relation on which ti ranges, and B is an attribute of the relation on which t ranges. An atom of the form ti.A op c or c op tj.B, where op is one of the comparison operators in the set {=, <, ≤, >, ≥, ≠}, ti and tj are tuple variables, A is an attribute of the relation on which ti ranges, B is an attribute of the relation on which tj ranges, and c is a constant value.

*Edit(Thanks to philipxy): The meaning of a query in TRC with respect to the above general expression would be,

For {t|p}--"The result of such a query is the set of all tuples t that evaluate COND(t) to TRUE". For {t.a1,t.a2,...|p}--"we first specify the requested attributes […] for each selected tuple t. Then we specify the condition for selecting a tuple following the bar".

There is also a mention of,

The only free tuple variables in a tuple relational calculus expression should be those that appear to the left of the bar (|).

Consider for example, a relation Students(id, grade) and we would like to find the "id's of all students who have secured the highest grade". The query specified in Tuple Relational Calculus could be

Q1 = {s1. id | students(s1) ^ ¬(∃ s2, students(s2) ^ ( s2. grade > s1.grade) )}

Here, s1 is the free variable.

Q1 can be interpreted as all id values of tuple variable s1, where s1 ranges within the relation student (i.e. s1 belongs to student) AND there does not exist a variable s2 such that s2 belongs to student and s2.grade > s1.grade.

Consider the queries,

Q2 = {s1. id | ∃ s1, students(s1) ^ ¬(∃ s2, students(s2) ^ ( s2. grade > s1.grade) )}

and

Q3 = {s1. id | ∀ s1, students(s1) ^ ¬(∃ s2, students(s2) ^ ( s2. grade > s1.grade) )}

As we can see, s1 (variable on the left of the bar) in Q2 and Q3 is also bounded by ∃ and ∀ respectively.

How is the interpretation of Q2 and Q3 different from Q1 assuming Q2 and Q3 are even possible ?

Note:

  • Queries Q2 and Q3 were made up from Q1 with the purpose of trying to understand what the queries would mean if the variables on the left side of '|' were bound by existential or universal quantifiers.
  • (Edit, after thinking a bit more) My interpretation of Q2 and Q3 is that the result of Q2 and Q1 will be the same will not be the same as Q2 will produce all id values of s1 if there exists atleast one s1 that belongs to student and for which there does not exist s2 such that s2 belongs to student and s2.grade > s1.grade (meaning, the result of Q2 is the "set of all student id if there exists atleast one student who got the highest grade"). Q3 will produce all id values of s1 if for every s1 that belongs to student and for which there does not exist s2 such that s2 belongs to student and s2.grade > s1.grade (meaning, the result of Q3 is the "set of all student id if every student got the highest grade"). But, I'm not sure if the queries Q2 and Q3 are even possible or even if such a scenario where the variables on the left of the bar are also bounded by quantifiers could occur in general.
mahesh Rao
  • 375
  • 1
  • 4
  • 16
  • What is your 1 specific question? PS There are many variants of tuple relational calculus, also of domain relational calculus & relational algebra--even differing in what a relation is--so you need to tell us your textbook name & edition. But since a question should be self-contained you should quote in text in your post the part of the grammar that would deal with your question. But that is also how you should approach your being stuck anyway. Otherwise we have to rewrite your textbook & also give a precis on general math notation around this sort of notation--"set comprehension". – philipxy Nov 06 '19 at 20:55
  • You ask about multiple things. If you don't know what they are, why are you asking for the difference between them?--Find out what each is. If you think you know what they are, why don't you know "the difference"--and what does that even mean?--Give *definitions* & you tell us what the similarities & differences are & ask whether that's reasonable. Either way ask a question specifically about how you are stuck on a specific point. – philipxy Nov 06 '19 at 21:00
  • {x|p} is the set of values for variable x that make p true. This is "set comprehension" with "(characteristic) predicate" p. So proposition s={x|p} re set s means forall x [x in s iff p]. Shorthand {...x...|p} means {y|exists x [y=(...x...) & p]}. TRCs define shorthands like {x.a,...|p} for {|p} ie {y|exists x [y= & p]}. Find the definitions of your TRC shorthands. RHS quantifications of x introduce a different nested variable. For x not free in p, p true gives all possible values for x & p false gives none. But a TRC won't allow that per "safety". – philipxy Nov 07 '19 at 00:03
  • @philipxy I'm not sure if I understood what you're saying. "You neither mention (compare to my 3rd comment) nor apply (per my 2nd comment) the definition of what a query expression means", but isn't that what is explained in the first quote and the second point under note ? (apologies if I'm mistaken). Also you said that Q2 and Q3 violate the last quote, which would mean that the queries aren't possible according to the author, right ? And the ultimate question of how those queries (Q2 and Q3) could be interpreted first depends on whether they are possible, which is why the title is different – mahesh Rao Nov 07 '19 at 14:27
  • Again: You quote syntax/grammar for an expression. But not the semantics/meaning of that expresssion. (In particular how the LHS plus the RHS gives a relation.) *Your question is, what do queries mean, so find where your textbook tells you & apply it & describe applying & describe getting stuck.* I can't say yes/no to "right?" yet since I suspect the 2nd quote is unclear; but having the definition of query meanings will help. Re "ultitimate question": Again: Just ask 1 question--1. Don't present that via asking other questions because then we don't know what your 1 clear precise question is. – philipxy Nov 07 '19 at 22:27
  • I looked at your textbook & it is poorly written. However they do (poorly) give, in about a sentence each, the meaning of queries of 2 forms: For {t|p}--"The result of such a query is the set of all tuples t that evaluate COND(t) to TRUE". For {t.a1,t.a2,...|p}--"we first specify the requested attributes […] for each selected tuple t. Then we specify the condition for selecting a tuple following the bar". (Plus see my comment about such notation.) So apply the latter to your queries. I'll answer when I can. – philipxy Nov 08 '19 at 06:41
  • "all id values of s1" is unclear. Correct: a row for each value of the type of column id in EMPLOYEE. (Not just for each id value in EMPLOYEE.) Also the rest of the 2nd bullet is not clear. (But we know you're trying to just restate the formulas.) Use enough words, sentences & references to things to be clear. For 2 "all id values of s1" are returned if the RHS is true. But what if the RHS is false? And for 3? PS In 2 & 3 LHS s1 & RHS s1 have different scopes--you could change either or both & the new query would mean the same thing. 2 & 3 are "unsafe" queries--see that later textbook section. – philipxy Nov 08 '19 at 13:01
  • @philipxy For Q2, if some tuple (say t) had an attribute 'id' and 'grade', if t satisfied RHS of Q2, then the result would be a set of all x.id where x is a tuple variable that represents all tuples with an attribute 'id'. This would therefore make Q2 an unsafe query. If NO tuple existed that satisfied the RHS, the result of the query would be an empty set. And for Q3, if ALL the tuples in the relation student satisfied the RHS of Q3, then it would produce the same "unsafe" result as in Q2, but if atleast one tuple didn't satisfy the RHS of Q3, the result is an empty set. Is this correct ? – mahesh Rao Nov 09 '19 at 12:54
  • I meant but didn't explicitly say that the idea was that you would edit your post to include such a description of the output for all circumstances, not just some. (Hopefully also edit to be clear.) (More later.) – philipxy Nov 10 '19 at 00:23

0 Answers0