The Gateway to Computer Science Excellence
+1 vote
336 views

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)
in Databases by Active (5.2k points)
edited by | 336 views
0
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)
0

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.$

0

@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

0

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.

3 Answers

+1 vote
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.
by Active (1.4k points)
edited by
+1
So "/" operator always return empty set?
+2
Sir it depends on the scenario.

Here, R2 has more number of tuples than R1. That is why R1/R2 has number of tuples as 0. On the other hand, If R1 has more number of tuples than R2 then R1/R2 may or may not be non-empty.

Explanation: 

For R1/R2 to be non-empty, there are three conditions: 
1. the set of attributes in R2 must be a proper subset of R1 i.e., R1 should have atleast one attribute more than R2. 

2. If point 1 is satisfied then R2 must not have more tuples than R1.

3. Let R1 has attributes a,b and R2 has attribute b. Then for R1/R2 to be non empty, there must exist atleast one value of attribute a in R1 such that R1 has tuples having that value of a and all values of attribute b from R2.

Then the relation R1/R2 will have those extra attributes from R1 which are not in R2. Let us consider an example,

let R1 have attributes {a,b} and R2 have attribute {b}. Then R1/R2 will contain attribute {a} i.e. 

number of attributes in R1/R2= (number of attributes in R1)- (number of attributes in R2)

Then R1/R2 will contain tuples, having attribute {a} ,from R1 which have tuples in R1 corresponding to all values of attribute b in R2.

All the cases are shown in the picture below.

0
For R1×R2, min = 0 ??? How?
+1
Sorry, i made a mistake. It is mentioned that N2>N1>0 (i didn't looked at). Minimum number of tuples in R1 x R2 will not be 0. I changed it. Thanks.

On the other hand if it was mentioned N2>N1>=0, then minimum should be 0.

If either R1 or R2 is empty i.e. number of tuples N1 or N2 is 0,

then R1 x R2 will be empty and number of tuples is 0 , which is minimum

Here both N1 and N2 can't be 0 as it is mentioned N2>N1. But if both N1 and N2 be 0 then also R1 × R2 will be empty and number of tuples will be 0

And maximum will be product of the number of tuples in both relations i.e. N1*N2.
0
for division operator why both min and max are 0?
0

Because R2 contains more number of tuples than R1.

@aditi19 i have commented on it previously. Plz see it . If u have any doubt in it then plz ask. I have mentioned all the cases in it.

0

@SuvasishDutta

I understood the minimum part. no tuples of R1 are linked to all tuples of R2. But how max can be 0? what if all the tuples of R1 are linked to all the tuples of R2? how does N1<N2 matters here?

+1

Plz see this picture below why number of tuples is 0 always for this question

0
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.
0
got it now👍
very nice and detailed explaination
0

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

+1 vote

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$ 

by Boss (27.5k points)
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$
 
     
by Veteran (119k points)

Related questions

Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
50,737 questions
57,314 answers
198,358 comments
105,081 users