CS352 Lecture - Relational Calculus; QBELast revised 9/26/08Objectives:1. To briefly introduce the tuple and domain relational calculi2. To briefly introduce QBE.Materials1. Jason Rozen QBE demo Senior ProjectI. The Relational Calculus A. The relational calculus is an alternative to the relational algebra as a basis for query languages. It is derived from predicate calculus. 1. A predicate is an assertion that we require to be true. When we formulate a query in the relational calculus, we specify a predicate that the object(s) we are looking for must satisfy.2. Unlike relational algebra - which is procedural - relational calculus is non-procedural - i.e. we specify what requirements the result must satisfy, not how to compute it.B. Just as the relational algebra serves as the mathematical foundation for the commercial query language SQL, the relational calculus serves as the mathematical foundation for various commercial visual query languages.C. There are two variants of the relational calculus: the tuple relational calculus and the domain relational calculus.1. In the tuple relational calculus, variables represent tuples, and predicates are formulated in terms of attributes of a tuple variable.Ex: Find book tuples for which author = dog:{ t | t ε book ^ t[author] = dog }2. In the domain relational calculus, variables represent individual attributes, and complete tuples are represented as lists of attributes.Ex: The above query:{ <call_number, title, author> | <call_number, title, author> ε book ^ author = dog }3. In either case, we represent a query by a predicate which we want the result to satisfy.1D. It is important to see that there are definite analogues between operations in relational algebra and predicates in relational calculus. 1. In fact, it can be shown that the systems are of equivalent power, in the sense that any query that can be formulated in the relational algebra (without the extensions we have discussed) can be formulated in either of the relational calculi, and any safe formula (we define this later) in either of the relational calculi is equivalent to some query in the relational algebra.2. Thus, it is possible for one system to support query languages of both types by internally translating from a query of one type into the language used internally (most often a variant of relational algebra, since this is procedural in nature.) E. We will now consider examples of relational calculus equivalents to each basic relational algebra operation.1. Relational algebra SELECTION: σ book author = dogSee the two examples above2. Relational algebra PROJECTION:π borrower last_name first_namea) tuple r.c.:{ t | ∃ s (s ε borrower ^ t[last_name]=s[last_name] ^ t[first_name]=s[first_name]) }where t is on the new scheme (last_name, first_name)b) domain r.c.:{ <last_name, first_name> | ∃ borrower_id (< borrower_id, last_name, first_name> ε borrower) }23. Relational algebra NATURAL JOIN: checked_out |X| borrowera) i. tuple r.c.:{ t | ∃ u, v (u ε checked_out ^ v ε borrower ^u[borrower_id] = v[borrower_id] ^t[borrower_id] = u[borrower_id] ^t[call_number] = u[call_number] ^t[date_due] = u[date_due] ^t[last_name] = v[last_name] ^t[first_name] = v[first_name]) }where t is on the new scheme(borrower_id, call_number, date_due, last_name, first_name)b) domain r.c.:{ <borrower_id, call_number, date_due, last_name, first_name> |<borrower_id, call_number, date_due> ε checked_out ^<borrower_id, last_name, first_name> ε borrower }4. Relational algebra UNION: Suppose we have two tables that have the same scheme - say student_borrower and fac_staff_borrower - and want a table including all persons in either group:a) tuple r.c.:{ t | (t ε student_borrower) v (t ε fac_staff_borrower) }b) domain r.c.:{ <borrower_id, last_name, first_name> |(<borrower_id, last_name, first_name> ε student_borrower) v(<borrower_id, last_name, first_name> ε fac_staff_borrower)}5. Relational algebra DIFFERENCE: Suppose, instead, we have a general borrower table - which contains information on all borrowers - plus a student_borrower table, which contains only student borrowers, and we want to list borrowers who are not students. In relational algebra, this would be borrower - student_borrowera) tuple r.c.:{ t | (t ε borrower) ^ ¬ (t ε student_borrower) }3b) domain r.c.:{ <borrower_id, last_name, first_name> |(<borrower_id, last_name, first_name> ε borrower) ^¬ (<borrower_id, last_name, first_name> ε student_borrower)}6. A more complete example: Find the last name of all borrowers who have an overdue bookπ σ checked_out |X| borrowerlast_name date_due < -- whatever today is --Ask class to do in each relational calculus:tuple:{ t | ∃ u,v ( u ε checked_out ^ v ε borrower ^ t[last_name] = v[last_name] ^ u[borrower_id] = v[borrower_id] ^u[date_due] < "September 18, 2002") }domain: { <last_name> | ∃ borrower_id, call_number, date_due, first_name ( <borrower_id, call_number, date_due> ε checked_out ^ <borrower_id, last_name, first_name> ε borrower ^ date_due < "September 18, 2002") }F. One important property of relational calculus formulas is SAFETY. A relational calculus formula is said to be safe iff it does not require us to inspect infinitely many objects.1. Example: the query { t | ¬ (t ε R) } is not safe. For any relation R, there are infinitely many tuples that are not members of that relation!2. Unsafe formulas are most often the result of improper use of not. In general, the set of all values NOT satisfying some predicate is infinite; so when not is used it must be coupled with an additional condition that narrows the scope of consideration - e.g. if P(x) and Q(x) are safe formulas then ¬ Q(x)is unsafe, butP(x) ^ ¬ Q(x)is safe.43. The most common way to ensure that a formula is safe is to include a formula that restricts consideration to tuples from a particular relation - i.e. a formula of the form t ε R or <a,b,c> ε R.4. Notice that the issue of safety is unique to the relational calculus. One cannot formulate an unsafe query in the relational algebra - hence only safe relational calculus formulas have relational algebra equivalents.II. Another Commercial Query Language: QBEA. As we noted earlier, there have been many different commercial relational query languages. One other we will look at briefly is QBE - Query by Example.1. Like SQL, QBE was developed by IBM. Today, it is supported for accessing databases from personal desktop