Formula Sheets: Relational Algebra

 Page 1


Relational Algebra
Unary Op erations
Selection (s )
• Notation: s
condition
(R) .
• Desc ription: Selects tuples from relation R satisfying condition.
• Res ult: {t? R| condition(t) is true} .
Pro jec tion (p )
• Notation: p
A1,A2,...,An
(R) .
• Des cription: Selects sp ecified attributes A
1
,A
2
,...,A
n
from relation R , remo v es duplicates.
• Re sult: {t[A
1
,A
2
,...,A
n
]| t? R} .
Rename (? )
• Notation: ?
S
(R) or ?
S(A1,A2,...,An)
(R) .
• Des cription: Renames relation R to S or renames attributes.
Set T heory Op erations
Union (? )
• Notation: R?S .
• Des cription: T uples in R or S (or b oth), sc hemas m ust b e compatible.
• Re sult: {t| t? R or t? S} .
In tersection (n )
• Notation: RnS .
• Des cription: T uples common to R and S .
• R esult: {t| t? R and t? S} .
Difference ( - )
• Notation: R-S .
• Des cription: T uples in R but not in S .
• Re sult: {t| t? R and t / ? S} .
Binary Op erations
Cartesian Pro duct (× )
• Notation: R×S .
• Desc ription: Com bines all tuples of R with all tuples of S .
• Result: {(r,s)| r? R,s? S} .
• Sc hema: A ttributes of R union attributes of S .
Natural Joi n (?? )
• Notation: R ?? S .
• Description: Joins R and S on common attributes, remo v es duplicate attributes.
• Result: {t| t[A]? R,t[B]? S,t[AnB] = R[AnB] = S[AnB]} , where A,B are attributes of R,S .
Theta Join (??
?
)
1
Page 2


Relational Algebra
Unary Op erations
Selection (s )
• Notation: s
condition
(R) .
• Desc ription: Selects tuples from relation R satisfying condition.
• Res ult: {t? R| condition(t) is true} .
Pro jec tion (p )
• Notation: p
A1,A2,...,An
(R) .
• Des cription: Selects sp ecified attributes A
1
,A
2
,...,A
n
from relation R , remo v es duplicates.
• Re sult: {t[A
1
,A
2
,...,A
n
]| t? R} .
Rename (? )
• Notation: ?
S
(R) or ?
S(A1,A2,...,An)
(R) .
• Des cription: Renames relation R to S or renames attributes.
Set T heory Op erations
Union (? )
• Notation: R?S .
• Des cription: T uples in R or S (or b oth), sc hemas m ust b e compatible.
• Re sult: {t| t? R or t? S} .
In tersection (n )
• Notation: RnS .
• Des cription: T uples common to R and S .
• R esult: {t| t? R and t? S} .
Difference ( - )
• Notation: R-S .
• Des cription: T uples in R but not in S .
• Re sult: {t| t? R and t / ? S} .
Binary Op erations
Cartesian Pro duct (× )
• Notation: R×S .
• Desc ription: Com bines all tuples of R with all tuples of S .
• Result: {(r,s)| r? R,s? S} .
• Sc hema: A ttributes of R union attributes of S .
Natural Joi n (?? )
• Notation: R ?? S .
• Description: Joins R and S on common attributes, remo v es duplicate attributes.
• Result: {t| t[A]? R,t[B]? S,t[AnB] = R[AnB] = S[AnB]} , where A,B are attributes of R,S .
Theta Join (??
?
)
1
• Notation: R ??
?
S .
• De scription: Joins R and S based on condition ? .
• R esult: {t| t? (R×S),?(t) is true} .
Division (/ )
• Notation: R/S .
• Description: Find s v alues in R ’s attributes not in S that are asso ciated with all v alues in S .
• Result: {t[A-B]|?s? S,(t[A-B],s)? R} , where A is attributes of R , B is attributes of S .
A dditional Op erati ons
Aggregate F unctions
• Notation:
grouping attributes
G
aggregate function
(R) .
• Examples: COUNT , SUM, A V G, MAX, MIN.
• Description: Groups tuples b y sp ecified attributes, applies aggregate function.
Prop erties
Comm utativit y
• Union: R?S = S?R .
• In tersection: RnS = SnR .
• Natural Join: R ?? S = S ?? R .
Asso ciat ivit y
• Union: (R?S)?T = R? (S?T) .
• I n tersection: (RnS)nT = Rn (SnT) .
• Natural Join: (R ?? S) ?? T = R ?? (S ?? T) .
Equiv alences
• Selection: s
c1?c2
(R) = s
c1
(s
c2
(R)) .
• Pro j ection: p
A
(p
B
(R)) = p
A
(R) , if A? B .
• Join and Se lection: R ??
?
S = s
?
(R×S) .
• In tersection: RnS = R- (R-S) .
2