edited by
8,704 views
5 votes
5 votes

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)
edited by

3 Answers

7 votes
7 votes

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$ 

1 votes
1 votes
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.
edited by
0 votes
0 votes
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$
 
     

Related questions

1 votes
1 votes
2 answers
1
aditi19 asked May 8, 2019
1,223 views
Suppliers(sid, sname, address)Parts(pid, pname, color)Catalog(sid, pid, cost)Find the pids of the most expensive parts supplied by suppliers named Yosemite Sham
0 votes
0 votes
1 answer
2
aditi19 asked May 7, 2019
913 views
Given relationcatalog(sid, pid, cost)Find pairs of sids such that the supplier with the first sid charges more for some part than the supplier with the second sidwhat is ...
0 votes
0 votes
0 answers
3
kumar.dilip asked Oct 27, 2018
530 views
Online Site For practicing Relational Algebrahttps://dbis-uibk.github.io/relax/calc.htm
2 votes
2 votes
1 answer
4
learner_geek asked Dec 3, 2017
1,645 views
Consider the relations r1(P, Q, R) and r2(R, S, T) with primary keys P and R respectively. The relation r1 contains 2000 tuples and r2 contains 2500 tuples. The maximum s...