The Tuple Relational Calculus

By -

The Tuple Relational Calculus

When we write a relational-algebra expression, we provide a sequence of procedures that generates the answer to our query. The tuple relational calculus, by contrast, is a nonprocedural query language. It describes the desired information without giving a specific procedure for obtaining that information.

A query in the tuple relational calculus is expressed as

{t | P (t)}

that is, it is the set of all tuples t such that predicate P is true for t. Following our earlier notation, we use t[A] to denote the value of tuple t on attribute A, and we use t ∈ r to denote that tuple t is in relation r.

Before we give a formal definition of the tuple relational calculus, we return to some of the queries for which we wrote relational-algebra expressions in Section 3.2.

Example Queries

Say that we want to find the branch-name, loan-number, and amount for loans of over $1200:

{t | t ∈ loan ∧ t[amount ] > 1200}

Suppose that we want only the loan-number attribute, rather than all attributes of the loan relation. To write this query in the tuple relational calculus, we need to write an expression for a relation on the schema (loan-number). We need those tuples on (loan-number) such that there is a tuple in loan with the amount attribute > 1200. To express this request, we need the construct “there exists” from mathematical logic. The notation

∃ t ∈ r (Q(t))

means “there exists a tuple t in relation r such that predicate Q(t) is true.”

Using this notation, we can write the query “Find the loan number for each loan of an amount greater than $1200” as

{t |∃ s ∈ loan (t[loan-number ] = s[loan-number ]

∧ s[amount ] > 1200)}

In English, we read the preceding expression as “The set of all tuples t such that there exists a tuple s in relation loan for which the values of t and s for the loan-number attribute are equal, and the value of s for the amount attribute is greater than $1200.” Tuple variable t is defined on only the loan-number attribute, since that is the only attribute having a condition specified for t. Thus, the result is a relation on (loan-number).

Consider the query “Find the names of all customers who have a loan from the Perryridge branch.” This query is slightly more complex than the previous queries, since it involves two relations: borrower and loan. As we shall see, however, all it requires is that we have two “there exists” clauses in our tuple-relational-calculus expression, connected by and (∧). We write the query as follows:

image

In English, this expression is “The set of all (customer-name) tuples for which the customer has a loan that is at the Perryridge branch.” Tuple variable u ensures that the customer is a borrower at the Perryridge branch. Tuple variable s is restricted to pertain to the same loan number as s. Figure 3.37 shows the result of this query.

To find all customers who have a loan, an account, or both at the bank, we used the union operation in the relational algebra. In the tuple relational calculus, we shall need two “there exists” clauses, connected by or (∨):

image

This expression gives us the set of all customer-name tuples for which at least one of the following holds:

• The customer-name appears in some tuple of the borrower relation as a borrower from the bank.

• The customer-name appears in some tuple of the depositor relation as a depositor of the bank.

If some customer has both a loan and an account at the bank, that customer appears only once in the result, because the mathematical definition of a set does not allow duplicate members. The result of this query appeared earlier in Figure 3.12.

If we now want only those customers who have both an account and a loan at the bank, all we need to do is to change the or (∨) to and (∧) in the preceding expression.

image

The result of this query appeared in Figure 3.20.

Now consider the query “Find all customers who have an account at the bank but do not have a loan from the bank.” The tuple-relational-calculus expression for this query is similar to the expressions that we have just seen, except for the use of the not (¬) symbol:

image

This tuple-relational-calculus expression uses the ∃ u ∈ depositor (.. .) clause to require that the customer have an account at the bank, and it uses the ¬ ∃ s ∈ borrower (.. .) clause to eliminate those customers who appear in some tuple of the borrower relation as having a loan from the bank. The result of this query appeared in Figure 3.13.

The query that we shall consider next uses implication, denoted by ⇒. The formula P ⇒ Q means “P implies Q”; that is, “if P is true, then Q must be true.” Note that P ⇒ Q is logically equivalent to ¬P ∨ Q. The use of implication rather than not and or often suggests a more intuitive interpretation of a query in English.

Consider the query that we used in Section 3.2.3 to illustrate the division operation: “Find all customers who have an account at all branches located in Brooklyn.” To write this query in the tuple relational calculus, we introduce the “for all” construct, denoted by ∀. The notation

image

In English, we interpret this expression as “The set of all customers (that is, (customer- name) tuples t) such that, for all tuples u in the branch relation, if the value of u on at- tribute branch-city is Brooklyn, then the customer has an account at the branch whose name appears in the branch-name attribute of u.”

Note that there is a subtlety in the above query: If there is no branch in Brooklyn, all customer names satisfy the condition. The first line of the query expression is critical in this case — without the condition

∃ r ∈ customer (r[customer -name]= t[customer -name])

if there is no branch in Brooklyn, any value of t (including values that are not customer names in the depositor relation) would qualify.

Formal Definition

We are now ready for a formal definition. A tuple-relational-calculus expression is of the form

{t | P(t)}

where P is a formula. Several tuple variables may appear in a formula. A tuple variable is said to be a free variable unless it is quantified by a ∃ or ∀. Thus, in t ∈ loan ∧ ∃ s ∈ customer (t[branch-name] = s[branch-name])

t is a free variable. Tuple variable s is said to be a bound variable.

A tuple-relational-calculus formula is built up out of atoms. An atom has one of the following forms:

image

As we could for the relational algebra, we can write equivalent expressions that are not identical in appearance. In the tuple relational calculus, these equivalences include the following three rules:

image

Safety of Expressions

There is one final issue to be addressed. A tuple-relational-calculus expression may generate an infinite relation. Suppose that we write the expression

{t |¬ (t ∈ loan)}

There are infinitely many tuples that are not in loan. Most of these tuples contain values that do not even appear in the database! Clearly, we do not wish to allow such expressions.

To help us define a restriction of the tuple relational calculus, we introduce the concept of the domain of a tuple relational formula, P. Intuitively, the domain of P, denoted dom(P ), is the set of all values referenced by P. They include values mentioned in P itself, as well as values that appear in a tuple of a relation mentioned in P. Thus, the domain of P is the set of all values that appear explicitly in P or that appear in one or more relations whose names appear in P. For example, dom(t ∈ loan ∧ t[amount ] > 1200) is the set containing 1200 as well as the set of all values appearing in loan. Also, dom(¬ (t ∈ loan)) is the set of all values appearing in loan, since the relation loan is mentioned in the expression.

We say that an expression {t | P (t)} is safe if all values that appear in the result are values from dom(P ). The expression {t |¬ (t ∈ loan)} is not safe. Note that dom(¬ (t ∈ loan)) is the set of all values appearing in loan. However, it is possible to have a tuple t not in loan that contains values that do not appear in loan. The other  examples of tuple-relational-calculus expressions that we have written in this section are safe.

Expressive Power of Languages

The tuple relational calculus restricted to safe expressions is equivalent in expressive power to the basic relational algebra (with the operators ∪, −, ×, σ, and ρ, but without the extended relational operators such as generalized projection G and the outer-join

operations) Thus, for every relational-algebra expression using only the basic operations, there is an equivalent expression in the tuple relational calculus, and for every tuple-relational-calculus expression, there is an equivalent relational-algebra expression. We will not prove this assertion here; the bibliographic notes contain references to the proof. Some parts of the proof are included in the exercises. We note that the tuple relational calculus does not have any equivalent of the aggregate operation, but it can be extended to support aggregation. Extending the tuple relational calculus to handle arithmetic expressions is straightforward.

Comments

Post a Comment

Popular posts from this blog

Database System Architectures:Parallel Systems.

By -
Image
Parallel Systems Parallel systems improve processing and I/O speeds by using multiple CPUs and disks in parallel. Parallel machines are becoming increasingly common, making the study of parallel database systems correspondingly more important. The driving force behind parallel database systems is the demands of applications that have to query extremely large databases (of the order of terabytes — that is, 1012 bytes) or that have to process an extremely large number of transactions per second (of the or- der of thousands of transactions per second). Centralized and client – server database systems are not powerful enough to handle such applications. In parallel processing, many operations are performed simultaneously, as opposed to serial processing, in which the computational steps are performed sequentially. A coarse-grai n parallel machine consists of a small number of powerful processors; a massivel y parallel or fine-grai n parallel machine uses thousands of smaller processors....
Read more

DATABASE DESIGN -2 part2

By -
Image
Multi-valued Dependencies and Fourth Normal Form (a) The EMP relation with two MVDs: ENAME —>> PNAME and ENAME —>> DNAME. (b) Decomposing the EMP relation into two 4NF relations EMP_PROJECTS and EMP_DEPENDENTS. (c) The relation SUPPLY with no MVDs is in 4NF but not in 5NF if it has the JD(R1, R2, R3). (d) Decomposing the relation SUPPLY into the 5NF relations R1, R2, and R3.   Multi-valued Dependencies and Fourth Normal Form Definition: A multi-valued dependency (MVD) X —>> Y specified on relation schema R, where X and Y are both subsets of R, specifies the following constraint on any relation state r of R: If two tuples t1 and t2 exist in r such that t1[X] = t2[X], then two tuples t3 and t4 should also exist in r with the following properties, where we use Z to denote (R - (X υ Y)): t3[X] = t4[X] = t1[X] = t2[X]. t3[Y] = t1[Y] and t4[Y] = t2[Y]. t3[Z] = t2[Z] and t4[Z] = t1[Z]. An MVD X —>> Y in R is called a trivial MVD if (a) Y is a subset...
Read more

Database System Architectures:Network Types

By -
Image
Network Types Distributed databases and client – server systems are built around communication networks. There are basically two types of networks: local-are a networks and wide- are a networks . The main difference between the two is the way in which they are distributed geographically. In local-area networks, processors are distributed over small geographical areas, such as a single building or a number of adjacent buildings. In wide-area networks, on the other hand, a number of autonomous processors are distributed over a large geographical area (such as the United States or the en- tire world). These differences imply major variations in the speed and reliability of the communication network, and are reflected in the distributed operating-system design. Local-Area Networks Local-are a network s ( LAN s) (Figure 18.10) emerged in the early 1970s as a way for computers to communicate and to share data with one another. People recognized that, for many enterprises, numerous small...
Read more