Chapter 5 Relational Algebra Operators Expression Trees Constraints on Relations

What is an “Algebra” Mathematical system consisting of: Operands --- variables or values from which new values can be constructed. Operators --- symbols denoting procedures that construct new values from given values.

What is Relational Algebra? An algebra whose operands are relations or variables that represent relations. Operators are designed to do the most common things that we need to do with relations in a database. The result is an algebra that can be used as a query language for relations.

What we will learn… Core (or traditionally) relational algebra

Core Relational Algebra Union, intersection, and difference. Usual set operations, but require both operands have the same relation schema. Selection: picking certain rows. Projection: picking certain columns. Products and joins: compositions of relations.

Operators Operators Meanings meanings Set Union Difference Intersection Product Compare > >= < <= = Great Than Great Equal Less Than Less Equal Equal Not Equal Relation Selection Projection Join Divide Logical Not And Or

Set Operators R U S: union, the set of elements that are in R or S or both. R S: intersection, the set of elements that are in both R and S. R - S: difference, the set of elements that are in R but no in S. Required R and S must have schema with identical set of attributes, and Before calculation, the columns of R and S must be ordered.

RS A B C a1 b1 c1 a1 b2 c2 a2 b2 c1 RS a1 b3 c2 A B C a1 b2 c2 Ａ　　　Ｂ　　　Ｃ a1 b1 c1 a1 b2 c2 a2 b2 c1 R Ａ　　　Ｂ　　Ｃ a1 b2 c2 a1 b3 c2 a2 b2 c1 S RS A B C a1 b1 c1 a1 b2 c2 a2 b2 c1 a1 b3 c2 RS A B C a1 b2 c2 a2 b2 c1 R-S A B C a1 b1 c1

Projection L (R) Example title, year, length (Movie) L is a list of attributes from the schema of R. The result is a new relation that has only some of R’s columns. Eliminate duplicate tuples, if any. Example title, year, length (Movie) π

Selection C (R) Example C is a condition (as in “if” statements) that refers to attributes of R. The result is a new relation with a subset of R’s tuples that satisfy C. Example σ lentgh>=100 AND studioName = ‘Fox’ (Movie)

Cartesian Product or just product R  S Pair each tuple t1 of R with each tuple t2 of S. Result: a new relation with new tuples, each of them concatenation a pair of t1t2, the attributes of R and S are in ordered. But beware attribute A of the same name in R and S: use R.A and S.A.

RS A B C A B C S R Ａ Ｂ Ｃ a1 b1 c1 a1 b2 c2 a1 b2 c2 a1 b3 c2 a2 b2 c1 Ａ　　　Ｂ　　　Ｃ a1 b1 c1 a1 b2 c2 a2 b2 c1 R Ａ　　　Ｂ　　Ｃ a1 b2 c2 a1 b3 c2 a2 b2 c1 S RS A B C A B C a1 b1 c1 a1 b2 c2 a1 b1 c1 a1 b3 c2 a1 b1 c1 a2 b2 c1 a1 b2 c2 a1 b2 c2 a1 b2 c2 a1 b3 c2 a1 b2 c2 a2 b2 c1 a2 b2 c1 a1 b2 c2 a2 b2 c1 a1 b3 c2 a2 b2 c1 a2 b2 c1

Natural Join A frequent type of join connects two relations by: Equating attributes of the same name, and Projecting out one copy of each pair of equated attributes. Called natural join. Denoted: R1 R2

Theta-Join R C S C can be any boolean-valued condition. Take the product R x S. Then apply C to the result. C can be any boolean-valued condition. Historic versions of this operator allowed only A theta B, where theta was =, <, etc.

AθB R S

R R.B=S.B S R C<E S R S 等值连接 R S A B C a1 b1 5 a1 b2 6 a2 b3 8 B E b1 3 b2 7 b3 10 b3 2 b5 2 A R.B C S.B E a1 b1 5 b2 7 a1 b1 5 b3 10 a1 b2 6 b2 7 a1 b2 6 b3 10 a2 b3 8 b3 10 A R.B C S.B E a1 b1 5 b1 3 a1 b2 6 b2 7 a2 b3 8 b3 10 a2 b3 8 b3 2 Ａ　 Ｂ　　 Ｃ　　Ｅ a1 b1 5 3 a1 b2 6 7 a2 b3 8 10 a2 b3 8 2 自然连接 R S

Outerjoin Suppose we join R C S. A tuple of R that has no tuple of S with which it joins is said to be dangling. Similarly for a tuple of S. Outerjoin preserves dangling tuples by padding them with a special NULL symbol in the result.

Example: Outerjoin R = A B S = B C 1 2 2 3 4 5 6 7 1 2 2 3 4 5 6 7 (1,2) joins with (2,3), but the other two tuples are dangling. R OUTERJOIN S = A B C 1 2 3 4 5 NULL NULL 6 7

Dependent and Independent Operations R C S = C (R x S) R S = L ( C (R x S)) R S = R – (R – S)

Combining Operations to Form Query Algebras allow us to express sequences of operations in a natural way. Example: in arithmetic --- (x + 4)*(y - 3). Relational algebra allows the same. For example  title, year( lentgh>=100 (Movie) studioName = ‘Fox’ (Movie))

Expressions Precedence of relational operators: Unary operators --- select, project--- have highest precedence, bind first. Then come products and joins. Then intersection. Finally, union and set difference bind last. But you can always insert parentheses to force the order you desire.

Expression Trees Leaves are operands --- either variables standing for relations or particular, constant relations. Interior nodes are operators, applied to their child or children.

For example: lentgh >= 100 Movie studioName = ‘Fox’  title, year

例：学生—课程数据库，包括Student，Course，SC三个关系 Sno Sname Ssex Sage Sdept 95001 李勇　　　　 男　　 　　20　　　　 CS　　　 95002 刘晨　　　　 女 19 IS 95003　　 王敏　　　 　女 18 MA 95004　 张立　　　　 男 19 IS Course SC Cno Cname Cpqo Ccredit 1 数据库 5 4 2　　　　数学 2 　　信息系统　　　 1 4 4　　　 操作系统 6 3 5　　　 数据结构 7 4 6　　　 数据处理 2 7　　 　Pascal语言　　 6 4 Sno Cno Grade 95001 1 92 95001 2 85 95001 3 88 95002 2 90 95002 3 80

Sno( Cno = ‘1’ or Cno=‘3’ (SC)) Sname,Sdept(Student)  Sdept = ‘IS’(Student) Sno( Cno = ‘1’ (SC)) Sno( Cno = ‘1’ or Cno=‘3’ (SC)) Sname（  Cpno = ‘5’ (Course) SC Sno,Sname(Student) ）

Integrity Constrain of Relations Entity Constrain The attributes belong to key can not be set as NULL. Reference Constrain Foreign Key: an non-key attribute A in R is a key in S, then the A is called a foreign key of R. The value of foreign key can only be NULL or same as what is in S. User-define Constrain Users define the constrains themselves.

关系的完整性 实体完整性 参照完整性 用户定义完整性 ★ 实体完整性和参照完整性是关系模型必须满足的，被称作关系的不变性，由关系数据库系统自动支持 ★

实体完整性 规则：若属性A是基本关系R的主属性，则属性A不能取空值 说明：基本关系的主码中的任何属性都不能取空值，而不仅是主码整体不能取空值 依据：现实世界的实体是唯一可分的 例：学生（学号，姓名，性别，专业号，年龄） 　　课程（课程号，课程名，学分） 　　选修（学号，课程号，成绩）

参照完整性 例１：学生实体与专业实体间的关系： 学生（学号，姓名，性别，专业号，年龄） 专业（专业号，专业名） 　　学生（学号，姓名，性别，专业号，年龄） 　　专业（专业号，专业名） 关系参照图 外码 参照关系 被参照关系 专业号 学生关系　　　　　　专业关系 例２：学生，课程，学生与课程之间的多对多联系： 　　学生（学号，姓名，性别，专业号，年龄） 　　课程（课程号，课程名，学分） 　　选修（学号，课程号，成绩） 关系参照图　　 被参照关系 对于参照完整性的解释： 　　例１：学生关系中每个元组的“专业号”属性只能取： 　　　　　（１）空值 　　　　　（２）非空值 　　例２：“学号”及“课程号”能取两类值，但按实体完整性规则，它们作为选修关系的主属性只能取非空值，故二者只能取非空值． 参照关系 主码？外码？ 学号 课程号 学生关系　　　　 选修关系　　　　　课程关系

参照完整性 规则：参照关系R中每个元组在外码F上的值必须为： 例３：学生（学号，姓名，性别，专业号，年龄，班长） 定义：外码 被参照关系 参照关系 例３：学生（学号，姓名，性别，专业号，年龄，班长） 定义：外码 设F是参照关系R的一个或一组属性，但不是R的码，若F与被参照关系S的主码相对应，则称F是R的外码（详细定义见教材P54） 规则：参照关系R中每个元组在外码F上的值必须为： 或者取空值（F的每个属性值均为空值） 或者等于S中某个元组的主码值 外码

用户定义完整性 用户定义的、具体应用中的数据必须满足的约束条件 成绩：0－100之间 身份证、身份证和生日对应关系

Reading Guide Required: 5.2 Recommended: 《数据库系统概论》第二章中的关系代数

练习 图书馆管理数据库 用关系代数描述以下查询要求 读者(读者编号, 姓名, 单位) 图书(书号, 书名, 作者, 出版社, 单价, 类型) 借阅记录(读者编号, 书号, 借阅日期, 应还日期) 还书记录(读者编号, 书号, 归还日期) 用关系代数描述以下查询要求 查询“人民邮电出版社”出版的所有图书的相关信息 查询单价在15元以上的书名和作者 查询8号读者2003年3月10日所借图书的相关信息 查询超期归还图书的读者姓名和单位 查询借阅过《天龙八部》的读者的信息 查询借阅过“金庸”所有著作的读者的姓名 查询没有借阅过任何图书的读者的姓名