Relational Algebra

and optimization of relational algebra expressions

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)

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 А ϕ (В θ С ) = (А ϕ В) θ (А ϕ С)

join
…

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

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:

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!!!

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)

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

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]).

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.

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:

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)

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

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:

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)

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.

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

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

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

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)

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]

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

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]

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]

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]

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.

[Fno=Fno] DEP
FAC DEP

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

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

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

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)

× × ×

σ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)))

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