Relational Algebra

Engineering

transformation and optimization of relational algebra expressions

algebra
relational calculus (tuple-oriented and domain-oriented)
Query language is a language that

allows to extract data from database.

Formal languages are basis for creation of DB query languages (Alpha, QUEL, QBE, SQL)

(of the defined type) + operations. Algebra is closured if result

of any operation are the same type as a data in argument. Closure property allows to embed operations in each other.
Relational algebra = relations + operations.
Relational algebra closured.

Property of binary relations:
Operation ϕ is commutative if А ϕ В = B ϕ A
Operation ϕ is associative if (А ϕ В) ϕ С = А ϕ (В ϕ С)
Operation ϕ is distributive with respect with other operation θ, if А ϕ (В θ С ) = (А ϕ В) θ (А ϕ С)

projection
outer join
…

and S have the same arity/ that is they have

the same number of attributes.
Domains of corresponding attributes are compatible (the 1-st attribute of R is defined on the same domain as the 1-st attribute of S and so on) .

Set-theoretic operations require compatibility of their operands

with schemas R(A) and S(A), where A is a set

of attributes, is the relation T with schema T(A) that contains tuples of both relations, but without duplicates.

The operation commutative, associative and distributive with respect to the intersection .

Example:

with schemas R(A) and S(A), where A is a set

of attributes, is the relation T with schema (A) that contains only those tuples of the relation R, which are not present in the relation S.

The operation not commutative and associative and distributive.

Т(А) = R(А) ⎯ S(А) = {t | t ∈ R & t ∉ S}

Example:

Note: Relational algebra do not use set-theoretic complement operation!!!

schemas R(A) and S(A), where A is a set of

attributes, is the relation T with schema T(A) that contains tuples which simultaneously present in both relations.

The operation commutative, associative and distributive with respect to union.

Т(А) = R(А) ∩ S(А) = {t | t ∈ R & t ∈ S}

Example:

Intersection is expressed via difference: R ∩ S = R – (R – S)

A is a set of attributes, with respect to the

set of attributes В, where В ⊂ А, is a such relation S with the schema S(B) that contains tuples of the relation R by deleting from them values that belong attributes A - B.

S(B) = R[B] = {t[B] ⏐ t ∈ R}

Projection is denoted as: R[B] или πВ(R)

Example:

Note: Duplicate tuples are deleted

following comparison operators : =, ≠, < ≤, >, ≥.

The attributes A and B the same or different relations are θ-comparable, if for any values a ∈ A and b ∈ B expression а θ b is defined.

Set of attributes М = (A1,…, Ak) and N = (B1,…,Bn) are θ-comparable, if k = n and (Ai, Bi) are θ‑comparable. In this case expression M θ N means the following:
M θ N = (A1 θ B1) & … & (Ak θ Вk)

If t is a relation tuple, that contains sets of θ‑comparable attributes M and N, then the notation t[M] θ t[N] means the following: (t[A1] θ t[B1]) & … & (t[Ak] θ t[Вk]).

attributes of the relation R with schema R(A). Then selection

(restriction) of the relation R on condition М θ N, denoted as R [М θ N], is such relation T with schema T(A), which tuples satisfy the condition t[М] θ t[N].

Т(А) = R[M θ N] = {t | t ∈ R & t[M] θ t[N]}

Example:

The operation also has the following notation: σM θ N(R)

One of the attributes set M or N may be constant.

schemas R(А) and S(B) (A and B are sets of

attributes), denoted as R(A)×S(B), is a relation T of degree n+m with schema T(А, B) that contains all possible concatenations of tuples of relations R and S:

The operation is commutative and associative and distributive with respect of union and intersection.

Т(А,В) = R(А) x S(B) = {(t1,t2) | t1 ∈ R & t2 ∈ S}

Example:

θ-comparable attributes. Join of the relations R and S with

schemas R(A,M) and S(N,B) on a condition М θ N, denoted as R[М θ N]S, is a relation T with a schema T(A,M,N,B) which tuples are concatenation only those tuples of R and S, for which sets of attributes N and M satisfy condition М θ N.

T = R[М θ N]S = {(t1, t2) ⏐ t1 ∈ R ∧ t2 ∈ S ∧ t1[М] θ t2[N]}

Example:

The operation commutative and associative

The operation is also denoted as: R M θ NS
Join is expressed via the product and the selection: R M θ NS = σM θ N(R x S)

is called as equi-join .

Natural join is a join

on equality condition by attributes with the same names with deleting in the result relation one of the compared set of attributes.

Natural join is denoted by the symbol * (for example R*S).

Example:

R S R[B,C=B,C]S R*S

resulting relation attributes of one of the joined relations.
Semijoin

is denoted as: R[M θ N)S

R[М θ N)S = {(t1) ⏐ t1 ∈ R ∧ t2 ∈ S ∧ t1[М] θ t2[N]}

Example:

R S R[B,C=B,C)S

R[М θ N)S = (R[М θ N]S)[A] – where А is a set of attributes of the relation R

Semijoin is expressed via the join and projection in such a way:

the tuple t1 ∈ R[M], that is denoted as It1(R),

is the set of such tuples t2 ∈ R[N], that concatenation of tuples (t1,t2) belongs to the relation R.

It1 ∈ R[M](R) = {(t2) ⏐ t2 ∈ R[N] ∧ (t1,t2) ∈ R}

Examples:

R Ia1∈ R[A](R) Ia2∈ R[A](R) I(a1,b1)∈ R[A,B](R) Ic2∈ R[C](R)

respect of set of compatible attributes N and M, denoted

as R [N ÷ K] S, is a relation T(M) with such tuples t ∈ R[M] whose images It(R) contain all tuples of the projection S[K].

T(M) = R[N÷K]S = {t ⏐t ∈ R[M] & It(R) ⊇ S[K]}

The operation allows to formulate queries like this: - Output teachers that teach lectures of ALL types.

S

S[C] R[C÷C]S

Division operation is expressed by other operations of RA:
R[N÷K]S = R[M] – ((R(M) x S[K]) – R)[M]
Division operation is not commutative and associative

Bld, Fund)
TCH (TNo, DNo, Name, Post, Tel, Salary, Comm)
GRP (GNo,

DNo, Course, Num, Quantity, CurNo)
SBJ (SNo, Name)
ROM (RNo, Num, Building, Seats) LEC (TNo, GNo, SNo, RNo, Type, Day, Week)

Example of DB for RA queries

names and posts:
TCH[Name, Post] πName,Post(TCH)
Selection: Output information about CSF faculty:
FAC[Name =

‘CSF’] σName=‘CSF’(FAC)
Join: Output information about faculries and their departments:

FAC[FNo = FNo]DEP FAC FNo=FNoDEP

projection
1) Outputs names of faculties and their departments
(FAC[FNo = FNo]DEP)

[FAC.Name, DEP.Name] πFAC.Name, DEP.Name(FAC FNo=FNoDEP)
2) Outputs names of faculties with fund > 1000 and their departments :
((FAC[Fund > 1000])[FNo = FNo]DEP) [FAC.Name, DEP.Name] πFAC.Name, DEP.Name((σFund >1000(FAC)) FNo=FNoDEP)

condition
Query calculation path
Post =‘prof’ – selection condition Name - output
Name -

output

Outputs names of professors from CSF faculty and subjects that they teach.

((((((FAC[FNo=Fno]DEP) [DNo=DNo]TCH) [TNo=TNo]LEC) [SNo=SNo]SBJ) [FAC.Name=‘CSF’]) [Post=‘prof’]) [TCH.Name, SBJ.Name]

groups:
((LEC[TNo,GNo])[GNo÷GNo]GRP)[TNo]
2) Output teacher numbers that teach in ALL groups of

the first course:
((LEC[TNo,GNo])[GNo÷GNo](GRP[Course=1]))[TNo]
3) Output teacher names that teach in ALL groups of the first course:
(((LEC[TNo,GNo])[GNo÷GNo](GRP[Course=1])) [TNo=TNo]TCH)[TCH.Name]

LEC(GNo,TNo,...)

GRP(GNo, Course...)

TCH(TNo, Name...)

express complex queries, write query as a sequential program consisting

of a series of assignments by using intermediate temporal relations followed by an expression whose value is displayed as a result of the query.

Пример: Output teacher names that teach in ALL groups of the first course:
(((LEC[TNo,GNo])[GNo÷GNo](GRP[Course=1])) [TNo=TNo]TCH)[TCH.Name]
Temp1 ← LEC[TNo,GNo]
Temp2 ← GRP[Course=1]
Temp3 ← Temp1[GNo÷GNo]Temp2
Temp4 ← Temp3[TNo=TNo]TCH
Temp4[TCH.Name]

to refer to, the results of relational-algebra expressions.
It has the

following syntax:
ρR(A1,A2,...,An)(E)

Where: Е – relational algebra expression,
R(A1,A2,...,An) – name of the relation ant its attributes that is calculated by expression E.

Example: Output names of faculties and their departments. Rezulted relation should have name FAC_DEP with attributes FName и DName respectively:
ρFAC_DEP(FName,DName)(FAC[FNo=FNo]DEP)[FAC.Name,DEP.Name]

to be used in the projection list. R[F1, F2,...,Fn] πF1, F2,...,Fn(R)
Where: R –

relation or expression of relational algebra;
F1, F2,...,Fn – are arithmetic expressions involving constants and attributes in the schema of E.

Example: Output teacher names and their salary + commission

TCH[Name, Salary + Commission]

that avoids loss of information.

Computes the join and then adds

tuples form one relation that does not match tuples in the other relation to the result of the join.

(inner join)
FAC [Fno=Fno] DEP
FAC DEP

F-2 CTF Dick F-3 CEF Bob F-4 CYB John

DEP DNo Name Head FNo

D-1 SE Kate F-1 D-2 DBMS Lucy F-1 D-3 CAD Dave F-2 D-4 PL Stiv NULL D-5 CAM Sam NULL

2) Left outer join FAC 〈Fno=Fno] DEP
FAC DEP

FNo Name Dean DNo Name Head FNo

F-1 CSF Ann D-1 SE Kate F-1 F-1 CSF Ann D-2 DBMS Lucy F-1 F-2 CTF Dick D-3 CAD Dave F-2 F-3 CEF Bob null null null null F-4 CYB John null null null null

FAC

DEP

F-2 CTF Dick F-3 CEF Bob F-4 CYB John

DEP DNo Name Head FNo

D-1 SE Kate F-1 D-2 DBMS Lucy F-1 D-3 CAD Dave F-2 D-4 PL Stiv NULL D-5 CAM Sam NULL

3) Right outer join FAC [Fno=Fno〉 DEP
FAC DEP

FNo Name Dean DNo Name Head FNo

F-1 CSF Ann D-1 SE Kate F-1 F-1 CSF Ann D-2 DBMS Lucy F-1 F-2 CTF Dick D-3 CAD Dave F-2 null null null D-4 PL Stiv null null null null D-5 CAM Sam null

FAC

DEP

DEP




FNo Name Dean DNo Name

Head FNo

F-1 CSF Ann D-1 SE Kate F-1 F-1 CSF Ann D-2 DBMS Lucy F-1 F-2 CTF Dick D-3 CAD Dave F-2 F-3 CEF Bob null null null null F-4 CYB John null null null null null null null D-4 PL Stiv null null null null D-5 CAM Sam null

FAC

DEP

Inner join

Left outer join

Right outer join

Full outer join

of selection and projection:
πG(σF(R))=σF(πG(R))=σF&G(R), если G ⊇ F
3) Distributivity of

selection and product
σF(R х S) = σF(R) x σF(S)
4) Distributivity of selection and set-theoretic operations:
σF(R ∪ S)=σF(R) ∪ σF(S), σF(R ∩ S)=σF(R) ∩ σF(S)
5) Distributivity of selection and join:
σF(R S) = σF(R) S, если условие F относится к R
6) Distributivity of projection and set-theoretic operations :
πF(R ∪ S)=πF(R) ∪ πF(S), πF(R ∩ S)=πF(R) ∩ πF(S)

S(C,D) RA,B) S(C,D)

R(A,B) S(C,D)

× × ×

σD=9

σB=C & D=9 σB=C σB=C B=C

σD=9

πA

πA

πA

πA

πA(σB=C & D=9(R(A, B)x S(C,D)))

optimization:
Transform each selection σF1&...&Fn(E) to the sequence of selections σF1(...

σFn(E))
Move each selection downwards of the tree as far as it is possible (thus (vertical) size of the relation is reduced).
Adjacent selection and cartesian product are replaced by join.
Move each projection downwards of the tree as far as it is possible (thus (horizontal) size of the relation is reduced).
Transform each cascade of adjacent selections and projections into single projection or selection with subsequent projection

relational model
Procedural language, how to retrieve data
No practical

relevance for querying DB
Formal basis for query optimization
Important terms & concepts:
Union R ∪ S, difference R – S, intersection R ∩ S
Projection π(R)
Selection σ(R)
Cartesian product R x S
Joins R S
Difference