关系代数 （Relational Algebra）与SQL查询语言类似，不过多用于理论，SQL查询语言用于现实的数据库查询。
Three types of operations/operators on relations：
fundamental operations：基本运算
additive operations：由基本运算组合而成的附加运算
Fundamental operations 部分
Select Operation
相当于SQL查询语言中的where
Select operation is defined as:
σ p ( r ) = { t ∣ t ∈ r ∧ p ( t ) } \Large \sigma_p(r)=\{t|t \in r \land p(t) \} σ p ( r ) = { t ∣ t ∈ r ∧ p ( t )} p p p ∧ \land ∧ ∨ \lor ∨ e g eg e g = = = e e e > > > < < < ≤ \le ≤ ≥ \ge ≥
Project Operation
相当于SQL查询语言中的select
Notation:
Π A 1 , A 2 , … , A k ( r ) \Large \Pi_{A_1,A_2,\dots,A_k}(r) Π A 1 , A 2 , … , A k ( r ) where A i A_i A i r r r
例子1：
Π I D , n a m e , s a l a r y ( i n s t r u c t o r ) \Large \Pi_{ID,name,salary}(instructor) Π I D , nam e , s a l a ry ( in s t r u c t or )
复制 SELECT distinct ID, name , salary
FROM instructor; 例子2：
Π n a m e ( σ d e p t _ n a m e = ′ P h y s i c s ′ ( i n s t r u c t o r ) ) \Large \Pi_{name}(\sigma_{dept\_name='Physics'}(instructor)) Π nam e ( σ d e pt _ nam e = ′ P h ys i c s ′ ( in s t r u c t or ))
复制 SELECT distinct name
FROM instructor
WHERE dept_name = 'Physics' ; Positional Notation（位置标记）
Use $1， $2, . . . refer to the first attribute, the second attribute, and so on.
例子：
如果表结构为instructor(ID, name, dept_name, salary)，那么：
Π $ 4 ( σ $ 4 < $ 8 ( i n s t r u c t o r × i n s t r u c t o r ) ) \Large \Pi_{\$4} (\sigma_{\$4 < \$8} (instructor \times instructor )) Π $4 ( σ $4 < $8 ( in s t r u c t or × in s t r u c t or ))
复制 SELECT distinct i1.salary
FROM instructor i1 JOIN instructor i2
WHERE i1.salary < i2.salary; 即选出所有不是最高工资的工资。
Union Operation
Union operation on relation r and s is defined as:
r ∪ s = { t ∣ t ∈ r ∨ t ∈ s } \Large r \cup s=\{t|t \in r \lor t \in s \} r ∪ s = { t ∣ t ∈ r ∨ t ∈ s }
r, s must have the same arity (same number of attributes)
The attribute domains must be compatible（兼容的）
例子：
Based on “emp-dept” schema, find all employees working as 'CLERK' or having salary higher than 2000, or fulfill both conditions.
Π n a m e ( σ j o b = ′ C L E R K ′ ( e m p ) ) ∪ Π n a m e ( σ s a l a r y > 2000 ( e m p ) ) \Large \Pi_{name}(\sigma_{job='CLERK'}(emp)) \cup \Pi_{name}(\sigma_{salary>2000}(emp)) Π nam e ( σ j o b = ′ C L ER K ′ ( e m p )) ∪ Π nam e ( σ s a l a ry > 2000 ( e m p )) Set-Difference Operation
Set difference operation on relation r and s is defined as:
r − s = { t ∣ t ∈ r ∧ t ∉ s } \Large r - s=\{t|t \in r \land t \notin s \} r − s = { t ∣ t ∈ r ∧ t ∈ / s }
r, s must have the same arity
The attribute domains must be compatible
例子：
Based on “emp-dept” schema, find all employees working as 'CLERK' ，but not having salary higher than 2000.
Π n a m e ( σ j o b = ′ C L E R K ′ ( e m p ) ) − Π n a m e ( σ s a l a r y > 2000 ( e m p ) ) \Large \Pi_{name}(\sigma_{job='CLERK'}(emp)) - \Pi_{name}(\sigma_{salary>2000}(emp)) Π nam e ( σ j o b = ′ C L ER K ′ ( e m p )) − Π nam e ( σ s a l a ry > 2000 ( e m p )) Cartesian-product operation
Cartesian-product operation on relation r and s is defined as:
r × s = { t ∣ t = t 1 t 2 ∧ t 1 ∈ r ∧ t 2 ∈ s } \Large r \times s=\{t|t=t_1t_2 \land t_1 \in r \land t_2 \in s \} r × s = { t ∣ t = t 1 t 2 ∧ t 1 ∈ r ∧ t 2 ∈ s } 例子1：
Give the relational algebra expression for the operations shown:
Π A , B , C , D , E ( σ A = C ( r × s ) ) \Large \Pi_{A,B,C,D,E}(\sigma_{A=C}(r \times s)) Π A , B , C , D , E ( σ A = C ( r × s )) 例子2:
Based on “emp-dept” schema， find all employees’ name and their departments' name .
Π e m p . n a m e , d e p t . n a m e ( σ e m p . d e p t n o = d e p t . d e p t n o ( e m p × d e p t ) ) \Large \Pi_{emp.name, dept.name}(\sigma_{emp.deptno=dept.deptno}(emp \times dept)) Π e m p . nam e , d e pt . nam e ( σ e m p . d e pt n o = d e pt . d e pt n o ( e m p × d e pt )) Rename Operation
returns the result of expression E under the name x:
ρ x ( E ) \Large \rho_{\text{x}}(E) ρ x ( E ) If a relational-algebra expression E has arity n then:
ρ x ( A 1 , A 2 , … , A n ) ( E ) \Large \rho_{\text{x}(A_1,A_2,\dots,A_n)}(E) ρ x ( A 1 , A 2 , … , A n ) ( E ) Additive operations 部分
We define additional operations that do not add any power to the relational algebra, but that simplify common queries. An additional operation can be replaced/re-represented by basic operations.
Set-Intersection Operation
For relation r and s, set-intersection operation on r and s is defined as:
r ∩ s = { t ∣ t ∈ r ∧ t ∈ s } = r − ( r − s ) \Large r \cap s=\{t|t \in r \land t \in s \}=r-(r-s) r ∩ s = { t ∣ t ∈ r ∧ t ∈ s } = r − ( r − s ) 例子：
Based on “emp-dept” schema, find all employees working as 'CLERK' and having salary higher than 2000.
Π n a m e ( σ j o b = ′ C L E R K ′ ( e m p ) ) ∩ Π n a m e ( σ s a l a r y > 2000 ( e m p ) ) \Large \Pi_{name}(\sigma_{job='CLERK'}(emp)) \cap \Pi_{name}(\sigma_{salary>2000}(emp)) Π nam e ( σ j o b = ′ C L ER K ′ ( e m p )) ∩ Π nam e ( σ s a l a ry > 2000 ( e m p )) Natural-Join Operation
Let r and s be relations on schemas R and S respectively, and assuming R ∩ S = A 1 ， A 2 ， … ， A n R\cap S = {A_1， A_2， \dots， A_n } R ∩ S = A 1 ， A 2 ， … ， A n
r ⋈ s = σ r . A 1 = s . A 1 ∧ ⋯ ∧ r . A n = s . A n ( r × s ) \Large r \bowtie s = \sigma_{r.A_1=s.A_1 \land \dots \land r.A_n=s.A_n}(r \times s) r ⋈ s = σ r . A 1 = s . A 1 ∧ ⋯ ∧ r . A n = s . A n ( r × s )
Natural join is associative(结合律)
( A ⋈ B ) ⋈ C = A ⋈ ( B ⋈ C ) \Large (A \bowtie B) \bowtie C = A \bowtie (B \bowtie C) ( A ⋈ B ) ⋈ C = A ⋈ ( B ⋈ C )
Natural join is commutative (交换律)
A ⋈ B = B ⋈ A \Large A \bowtie B = B \bowtie A A ⋈ B = B ⋈ A Theta Join
The theta join operation is defined as:
r ⋈ θ s = σ θ ( r × s ) \Large r \bowtie_\theta s = \sigma_\theta(r \times s) r ⋈ θ s = σ θ ( r × s ) where θ \theta θ R ∪ S R \cup S R ∪ S
Division
记不住公式没问题，看例子理解。
R ÷ S = Π R − S ( r ) − Π R − S ( ( Π R − S ( r ) × S ) − Π R − S , S ( r ) ) \Large R \div S = \Pi_{R-S}(r) - \Pi_{R-S}((\Pi_{R-S}(r) \times S) - \Pi_{R-S,S}(r)) R ÷ S = Π R − S ( r ) − Π R − S (( Π R − S ( r ) × S ) − Π R − S , S ( r )) 例子1：
Find all students who have taken all courses offered in the Biology department.
Π n a m e , c o u r s e _ i d ( ρ S ( s t u d e n t ) ⋈ S . I D = T . I D ρ T ( t a k e s ) ) ÷ Π c o u r s e _ i d ( σ d e p t _ n a m e = ′ B i o l o g y ′ ( c o u r s e ) ) \Large \begin{align} &\Pi_{name,course\_id}(\rho_{S}(student) \bowtie_{S.ID=T.ID} \rho_{T}(takes)) \\ \div &\Pi_{course\_id}(\sigma_{dept\_name = 'Biology'}(course)) \end{align} ÷ Π nam e , co u rse _ i d ( ρ S ( s t u d e n t ) ⋈ S . I D = T . I D ρ T ( t ak es )) Π co u rse _ i d ( σ d e pt _ nam e = ′ B i o l o g y ′ ( co u rse ))
复制 select distinct S.name
from student as S
where not exists (
(
select course_id
from course
where dept_name = 'Biology'
)
except
(
select T.course_id
from takes as T
where S.ID = T.ID
)
); 例子2：
Based on “emp-dept” schema, find the jobs provided by all the departments having employees.
首先，确定目标的是job，条件是deptno
Π j o b , d e p t n o ( e m p ) ÷ Π d e p t n o ( d e p t ) \Large \Pi_{job,deptno}(emp) \div \Pi_{deptno}(dept) Π j o b , d e pt n o ( e m p ) ÷ Π d e pt n o ( d e pt ) 例子3：
找到提供了工资在3000到4000之间所有职位的部门，给出部门名称。
首先确定目标是deptno，条件是job
Assignment Operation
The assignment operation (← \leftarrow ← with ... as...
Outer Join
Outer join is an extension of the join operation that avoids loss of information.
left outer join operation is defined as:
( r ⋈ s ) ∪ ( r − Π R ( r ⋈ s ) × { ( null , … , null ) } ) \Large (r \bowtie s) \cup (r- \Pi_R(r \bowtie s) \times \{ (\text{null},\dots, \text{null})\}) ( r ⋈ s ) ∪ ( r − Π R ( r ⋈ s ) × {( null , … , null )}) Extended operations部分
Generalized Projection
Generalized project（广义投影） extends the projection operation by allowing arithmetic functions to be used in the projection list.
Π F 1 , F 2 , … , F n ( E ) \Large \Pi_{F_1,F_2,\dots,F_n}(E) Π F 1 , F 2 , … , F n ( E ) each of F 1 , F 2 , … , F n F_1,F_2,\dots,F_n F 1 , F 2 , … , F n
Aggregation functions
Aggregate operation（聚集运算） in relational algebra is defined as:
G 1 , G 2 , … , G n G F 1 ( A 1 ) , F 2 ( A 2 ) , … , F n ( A n ) ( E ) \Large _{G_1,G_2,\dots,G_n} \mathcal{G}_{F_1(A_1),F_2(A_2),\dots,F_n(A_n)}(E) G 1 , G 2 , … , G n G F 1 ( A 1 ) , F 2 ( A 2 ) , … , F n ( A n ) ( E )
E E E
G 1 , G 2 , … , G n G_1,G_2,\dots,G_n G 1 , G 2 , … , G n
Each F i F_i F i
Each A i A_i A i
例子1：
Based on “emp-dept” schema,Find the average salary in each department
d e p t n o G a v g ( s a l ) ( e m p ) \Large _{deptno} \mathcal{G}_{avg(sal)}(emp) d e pt n o G a vg ( s a l ) ( e m p ) 例子2：
获得工资比所在部门平均工资高的员工姓名、工资以及所在部门的平均工资。
Π e n a m e , s a l , a v g s a l ( σ s a l > a v g s a l ( e m p ⋈ ( d e p t n o G a v g ( s a l ) a s a v g s a l ( e m p ) ) ) ) \Large \Pi_{ename,sal,avgsal}(\sigma_{sal>avgsal}(emp \bowtie(_{deptno} \mathcal{G}_{avg(sal) \, as\, avgsal}(emp)))) Π e nam e , s a l , a vg s a l ( σ s a l > a vg s a l ( e m p ⋈ ( d e pt n o G a vg ( s a l ) a s a vg s a l ( e m p )))) 
