Term
| (4.1) What is the input to a relational query? |
|
Definition
| The inputs and outputs of a query are relations. |
|
|
Term
| (4.1) What is the result of evaluating a query? |
|
Definition
| A query is evaluated using instances of each input relation and it produces an instance of the output relation. |
|
|
Term
| (4.2) Database systems use some variant of relational algebra to represent query evaluation plans. Explain why algebra is suitable for this purpose. |
|
Definition
| A fundamental property of algebra is that every operator accepts one or two relation instances as arguments and returns a relation instance as the result, since queries share this property it is easy to compose operators to form complex queries. |
|
|
Term
| (4.2.1) Describe the selection operator. (use "sigma" to name the selection operator symbol) |
|
Definition
| The selection operator specifies the tuples to retain through a selction condition. In general, the selection condition is a boolean combination of terms that uses a comparison operator and two expressions (one of these may be a constant or and attribute, the other must be an attribute). Example: sigma rating>8(S2) |
|
|
Term
| (4.2.1) What can you say about the cardinality of the input and output tables for the selection operator? (That is, if the input has k tuples, what can you say about the output?) |
|
Definition
| The cardinality of the output will be <= to the cardinality of the input. If the input has k tuples, the output will have k-x tuples where x can be 0,1,...,k. |
|
|
Term
| (4.2.1) Describe the projection operator. (use pi as the name to describe the projection) |
|
Definition
| The projection operator allows us to extract columns from a relation. The columns specified in the expression are the fields in the instance that are to be retained. Example: pi sname,rating(S2) |
|
|
Term
| (4.2.1) What can you say about the cardinality of the input and output for the projection operator? |
|
Definition
| The input and output will have the same cardinality. |
|
|
Term
(4.2.1) How would you go about evaluating this expression:
pi sname,rating(sigma rating>8(S2)) |
|
Definition
| As in algebra, you evaluate the inner expression first: sigma rating>8(S2). You then use the output of this expression (for clarity,called S3 since it is an instance itself) as the argument to the outer expression: pi sname,rating(S3) |
|
|
Term
| (4.2.2) Describe the relational algebra set operation called "union". |
|
Definition
| This operation returns an instance containing all tuples that occur in either argument relation. Both arguments must be union-compatible. |
|
|
Term
| (4.2.2) Describe the relational algebra set operation called "intersection". |
|
Definition
| This operation returns a relation instance containing all tuples that occur in both argument instances. Both arguments must be union-compatible. |
|
|
Term
| (4.2.2) What does it mean when both relation instances are union-compatible? |
|
Definition
| Both relation instances must be compatible with each other; they must have the same number of fields, and the corresponding fields taken in order from left to right must have the same domains. |
|
|
Term
| (4.2.2) Describe the relational algebra set operation called "set-difference". |
|
Definition
| This operation returns a relation instance containing all tuples that occur in the first argument relation but not in the second argument relation. |
|
|
Term
| (4.2.2) Describe the relational algebra set operation called "cross-product". |
|
Definition
| This operation returns a relation instance whose schema contains all the fields of the first argument relation (in order), followed by all the fields of the second argument relation (in order). The resulting relation contains one tuple for each possible combination of tuples. |
|
|
Term
| (4.2.2) What can you say about the cardinality of the input and output for the union operator? |
|
Definition
| The cardinality of the return relation is the sum of the cardinality of both argument relations minus the cardinality of the intersection of the two arguments. |
|
|
Term
| (4.2.2) What can you say about the cardinality of the input and output for the intersection operator? |
|
Definition
| The cardinality of the return relation is the sum of the cardinality of both argument relations minus the cardinality of the return relation of a union operation involving both argument relations. |
|
|
Term
| (4.2.2) What can you say about the cardinality of the input and output for the set-difference operator? |
|
Definition
| The cardinality of the return relation equals the cardinality of the first argument minus the cardinality of the return relation of an intersection operation between the two argument relations. |
|
|
Term
| (4.2.2) What can you say about the cardinality of the input and output for the cross-product operator? |
|
Definition
| The cardinality of the return relation equals the cardinality of the first argument relation times the cardinality of the second argument relation. (cardinality 3 relation x cardinality 2 relation = cardinality 6 relation) |
|
|
Term
| Explain how the renaming operator is used. Is it required? (Use rho as name for renaming operator.) |
|
Definition
| It is not required, but it is useful in providing clarity when field names are ambiguous, or when intermediate relation names are helpful. For instance if two relations in a cross product both have fields called "id", then you would want to rename the id fields like 1->sid1,5->sid2 (must use positional reference sinc both names are the same). Example: rho(C(1->sid1,5->sid2), S1 x R1) The result relation is named C with the 1st and and 5th columns named sid1 and sid2 respectively. |
|
|
Term
| (4.2.4) Why is the join operation given special attention? |
|
Definition
| Because the join operation is a very useful operation that occurs very frequently. This operation is more efficient than the cross-product, because it combines the cross-product, selection and projection operations. |
|
|
Term
| (4.2.4) Define the Condition Join operation. |
|
Definition
| It is the cross-product of two relations followed by a selection operation. The condition of the selection often refers to attributes of both argument relations. The notation is the first argument name followed by the join symbol with the conditions listed as subscripts, followed by the second argument. |
|
|
Term
| (4.2.4) Define the Equijoin operation. |
|
Definition
| This is a special kind of condition join where the condition consists solely of equalities. The result relation actually has an additional projection performed on it that drops the second column for each each equality expression. This refinement makes it preferable to the condition join. The notation is the first argument name followed by the join symbol with the equalities listed as subscripts, followed by the second argument. |
|
|
Term
| (4.2.4) Define the Natural Join operation. |
|
Definition
| This is a special kind of equijoin in which equalities are specified on all fields having the same name. The notation uses only the join symbol, without a condition statement subscript. |
|
|
Term
| (4.2.5) Why is the division operator not given special treatment in database systems like the join is? |
|
Definition
| Since it is not needed as often, database languages have not implemented division as a distinct operator. |
|
|
Term
| (4.2.5) If given a relation A with attributes x, y and relation B with attribute y. Describe the division operation A/B. |
|
Definition
| The basic idea is to compute all x values in a that are not disqualified. An x value is disqualified if by attaching a y value from B, we obtain a tuple (x,y) that is not in A. |
|
|
Term
| (4.2.5) Define the division operation in terms of the basic relational algebra operations. |
|
Definition
| pi subx(A) - pi subx((pi subx(A) X B) - A) |
|
|
