Raghuramkrishnan Exercise 4.1 Relational Algebra

Question

Given two relations R1 and R2, where R1 contains N1 tuples, R2 contains N2 tuples, and N2>N1> 0, give the minimum and maximum possible sizes (in tuples) for the result relation produced by each of the following relational algebra expressions. In each case, state any assumptions about the schemas for R1 and R2 that are needed to make the expression meaningful:

1. $R1 \cup R2$ (union)
2. $R1 \cap R2$ (intersection)
3. $R1-R2$ (set difference)
4. $R1 X R2$ (cartesian product)
5. $σa=5(R1)$ (selection)
6. $\pi a(R1)$ (projection)
7. $R1/R2$ (division)

Comments

pls check whether my solution is correct or not

1. max=m+n, min=m+n

2. max=N1, min=0(no common tuples in R1 and R2)

3. max=N1(R1 and R2 are disjoint sets), min=0(all tuples of R1 are present in R2)

4. max=N1*N2, min=N1*N2

5. max=N1, min=0

6. I'm little confused here

7. Max=N1(all tuples of R1 are associated to all tuples of R2), min=0(no tuple of R1 is associated to all the tuples of R2)

---

pls check whether my solution is correct or not

1. Max is correct But min will be max(N1,N2) i.e. N2.

6. Max = N1 (If All the values of attribute $a$ are distinct), Min = 1 (If all the values of attribute $a$ are same.)

7. Max,Min will be Zero because $N_1 < N_2.$

---

@Deepakk Poonia (Dee)

In first, R1 union R2, there is no need of max(N1, N2) becuz already we know this N2>N1>0(given)

so the answer is 1.min = N2 and max=N1+N2

---

guys i treated this question in terms of discrete mathematics concept later i found it is the question of database(by seeing tag)

Is this okay? to think like that because all of the answer I did right except selection and projection.

@Arjun is this right approach? becuz i treated tuples in relation as 2-tuple(for simplicity) and then solve it.

for eg. 1.R1 union R2

for min -:

R1={(2,3)}

R2={(2,3),(1,3),(4,5)}

min tuples =N2 ie 3

for Max

R1={(1,3)}

R2={(2,3),(4,5)}

max tuples  =  N1+N2 ie.3

this merely take seconds to think in mind.

Answer 1

For typing convenience, I'll use $R,S$ for $R_1,R_2$ respectively. Similarly, $m,n$ instead of $N_1,N_2$

Given $n > m>0.$

Schema assumption for expressions $R \cup S, R \cap S, R -S :$ They must be Union Compatible i.e. For these Set Operations to be valid, we require that two conditions hold:

1. The relations $R$ and $S$ must be of the same arity. That is, they must have the same number of attributes.

2. The domains of the $i-th$ attribute of $R$ and the $i-th$ attribute of $S$ must be the same, for all $i.$

Note that $R$ and $S$ can be either database relations or temporary relations that are the result of relational-algebra expressions.

1. $R \cup S :$ Max = $m+n $ (When R,S are disjoint sets) ; Min = $max(m,n) $ which is $n$ here (Min when one relation is subset of other )

2. $R \cap S :$ Max = $min(m,n) = m $ (when one relation is subset of other) ; Min = $0 $ (When R,S are Disjoint sets )

3. $R -S : $ Max = $m $ (When R,S are disjoint sets) ; Min = $0 $ (When R is subset of S )

---

4. $R \times S :$ No schema assumptions required.

Max, Min = $m.n$

---

5. $\sigma_{a =5}R :$

Schema Assumption : In the schema of $R,$ there should be an attribute by the name $'a'.$ Moreover, the domain of this attribute $'a'$ must contain $5.$

Max = $m$ (When all the tuples of $R$ have value of attribute $a$ as 5.)

Min = 0 (When None of the tuples of $R$ have value of attribute $a$ as 5.)

---

6. $\prod_aR : $

Schema Assumption : In the schema of $R,$ there should be an attribute by the name $'a'. 

Max = $m$ (When None of the two tuples of $R$ have same value of attribute $a.$) 

Min = 1 (When all the tuples have same value for attribute $a.$)

7. $R/S :$ 

Schema Assumption : Let relation R,S have X,Y set of attributes respectively. Then $R/S$ to be valid, We have $X \supset Y.$ (Y must be proper subset of X.)

For the given Question :

Max, Min = 0 (Because $n > m$)

---

In General, For $R/S :$

If $m \geq n, $ and $n \neq 0,$ then Max = Floor$(m/n),$ Min = 0

If $n = 0$ then Max = $m$ (When $X-Y$ have distinct values in all tuples), Min = 1 if $m \neq 0$ and All the tuples have same value for $X-Y$, Or Min  = 0 if $m=0$ 

Answer 2

1. For R1 U R2, min number of tuples= N2 if R1 is proper subset of R2.
Max number of tuples= N1 + N2.

2. For intersection, min = 0 , and maximum number of tuples = N1

3. For R1-R2, min no of tuples= 0 , and max number of tuples = N1.

4. For R1×R2, both min and max= N1×N2

5. For selection, min = 0 and maximum number of tuples= N1

6. For projection, min number of tuples = 0 if all the entries in attribute a are NULL , and maximum number of tuples = N1 if all the entries are distinct.

7. For R1/R2, both minimum and maximum no of tuples is 0.

Comments

That is R1 must have atleast N2 tuples containing all the N2 values of attribute Y in R2.
If R1 has no of tuples less than N2 then some values of Y from R2 is missing in R1. Therefore R1/R2 will not contain any tuple.

---

got it now👍
very nice and detailed explaination

---

In Relational Algebra, For duplicate elimination, null is treated like any other value, and two nulls are assumed to be the same. PROJECTION operation handles NULL values just like any other value while eliminating duplicates. Thus , if two tuples in the projection result are exactly same and both have NULL values in the same fields, then they are treated as duplicates.

So, In $6,$ Min = 1.

https://practice.geeksforgeeks.org/problems/explain-how-relational-algebra-operations-deal-with-null-values

http://www.cbcb.umd.edu/confcour/Spring2014/CMSC424/Relational_algebra.pdf

Moreover, Null values are usually excluded in the definition of relational algebra, except when operations like outer join are defined. So, while solving such questions, I guess, you can ignore the consideration of Null values. In Relational algebra, unless explicitly mentioned, Null values are not considered. 

http://db.inf.uni-tuebingen.de/staticfiles/teaching/ss09/db1/db1-03.pdf

Answer 3

Operation	Number of tuple extracted	In words
$R_{1}\cup R_{2}$	$max=m+n$ $min=m+n$   [Number of elements in $m$ rows first copied to resultant table then $n$ rows are concatenated]	duplicate tuple eliminated
$R_{1}\cap R_{2}$	$max=m \cap n$ $min=m \cap n$ Common rows among both tables are extracted	duplicate rows eliminated
$R_{1}- R_{2}$	Same as. $R_{1}\cap \left ( R_{2} \right )'$ $max=N_{1}$ $min=0$
$R_{1}\times R_{2}$	$max=m\times n$
$\sigma _{a=5}\left ( R_{1} \right )$	Tuple a on those rows where it's value is 5 will return
$\pi _{a}\left ( R_{1} \right )$	Print those values where $a$ exists
$R_{1}\div R_{2}$	All element of $R_{2}$ must be satisfied in $R_{1}$
$R_{1}\bowtie R_{2}$	$max=m\times n$ $min=0$