关系代数——扩展运算笔记

文章目录一、概述基本运算与扩展运算的关系二、交运算Intersection ∩定义前提条件用基本运算表达示例对应 SQL三、连接运算Join ⋈3.1 θ-连接Theta Join3.2 等值连接Equi-Join3.3 自然连接Natural Join对应 SQL四、除运算Division ÷定义用基本运算表达示例五、广义投影Generalized Projection定义示例对应 SQL六、外连接Outer Join6.1 左外连接Left Outer Join ⟕6.2 右外连接Right Outer Join ⟖6.3 全外连接Full Outer Join ⟗对应 SQL七、总结对比一、概述基本运算与扩展运算的关系关系代数共有五种基本运算其余所有运算均可由它们推导而来基本运算符号说明选择σ按条件筛选行投影π选取指定列并∪合并两个关系的元组差−取属于 R 但不属于 S 的元组笛卡尔积×两个关系的所有组合扩展运算包括交、连接、除、广义投影、外连接它们在实际查询中极为常用且都有对应的 SQL 实现。二、交运算Intersection ∩定义取两个关系中同时存在的元组。前提条件R 和 S 必须并相容属性数量相同对应属性的域相同用基本运算表达R ∩ S R − ( R − S ) R \cap S R - (R - S)R∩SR−(R−S)推导思路先从 R 中去掉 S 中没有的再从 R 中减去这部分剩下的就是两者共有的。示例R { (1, Alice), (2, Bob), (3, Carol) } S { (2, Bob), (3, Carol), (4, Dave) } R ∩ S { (2, Bob), (3, Carol) }对应 SQLSELECT*FROMRINTERSECTSELECT*FROMS;三、连接运算Join ⋈连接是最常用的扩展运算本质是从笛卡尔积中按条件筛选元组。3.1 θ-连接Theta JoinR ⋈ θ S σ θ ( R × S ) R \bowtie_\theta S \sigma_\theta(R \times S)R⋈θ​Sσθ​(R×S)θ 可以是任意比较条件、、、≤、≥、≠。3.2 等值连接Equi-Joinθ 条件为等号的特殊情况R ⋈ A B S σ A B ( R × S ) R \bowtie_{AB} S \sigma_{AB}(R \times S)R⋈AB​SσAB​(R×S)注意等值连接的结果中连接属性 A 和 B都会保留可能出现冗余。3.3 自然连接Natural JoinR ⋈ S R \bowtie SR⋈S自动在两个关系的同名属性上做等值连接并去除重复属性。示例Student(sid, name, dept_id) Department(dept_id, dept_name) Student ⋈ Department → 结果: (sid, name, dept_id, dept_name) 自动按 dept_id 匹配且只保留一份 dept_id对应 SQL-- θ-连接SELECT*FROMR,SWHERER.ageS.age;-- 等值连接SELECT*FROMRJOINSONR.dept_idS.id;-- 自然连接SELECT*FROMRNATURALJOINS;四、除运算Division ÷定义用于表达对于所有这类查询语义。R ÷ S { t ∣ t ∈ π R − S ( R ) ∧ ∀ s ∈ S , ( t , s ) ∈ R } R ÷ S \{ t \mid t \in \pi_{R-S}(R) \land \forall s \in S, (t, s) \in R \}R÷S{t∣t∈πR−S​(R)∧∀s∈S,(t,s)∈R}直观理解R ÷ S 的结果是 R 中那些与 S 中每一个元组都能配对的属性组合。用基本运算表达R ÷ S π R − S ( R ) − π R − S ( ( π R − S ( R ) × S ) − R ) R ÷ S \pi_{R-S}(R) - \pi_{R-S}\big((\pi_{R-S}(R) \times S) - R\big)R÷SπR−S​(R)−πR−S​((πR−S​(R)×S)−R)推导思路先找出 R 中所有可能的左半部分π_{R-S}®再找出那些与 S 中某些元组无法配对的左半部分两者相减剩下的就是与 S 中所有元组都能配对的示例Enroll(student_id, student_name, course_id, course_name, semester) Required(course_id, course_name) Enroll ÷ Required → 结果: 选修了所有必修课的 (student_id, student_name, semester)具体数据Enroll: | student_id | student_name | course_id | course_name | semester | |------------|--------------|-----------|-------------|----------| | 1 | 张三 | 101 | 数学 | 2026春 | | 1 | 张三 | 102 | 英语 | 2026春 | | 1 | 张三 | 103 | 语文 | 2026春 | | 2 | 李四 | 101 | 数学 | 2026春 | | 2 | 李四 | 102 | 英语 | 2026春 | | 3 | 王五 | 101 | 数学 | 2026春 | | 3 | 王五 | 102 | 英语 | 2026春 | | 3 | 王五 | 103 | 语文 | 2026春 | | 3 | 王五 | 104 | 物理 | 2026春 | Required: | course_id | course_name | |-----------|-------------| | 101 | 数学 | | 102 | 英语 | | 103 | 语文 | Enroll ÷ Required | student_id | student_name | semester | |------------|--------------|----------| | 1 | 张三 | 2026春 | | 3 | 王五 | 2026春 | 结果含义是找出那些把 Required 中所有必修课都选过的学生返回他们的 student_id, student_name, semester。五、广义投影Generalized Projection定义普通投影只能选取已有属性列广义投影允许在投影中使用算术表达式或函数来构造新属性。π A 1 , A 2 , . . . , f i ( A ) ( R ) \pi_{A_1, A_2, ..., f_i(A)}(R)πA1​,A2​,...,fi​(A)​(R)示例Employee(name, salary, bonus) 广义投影π_{name, total_pay}(Employee) 其中 total_pay salary bonus → 结果: name | total_pay --------|---------- Alice | 15000 Bob | 12000对应 SQLSELECTname,salarybonusAStotal_payFROMEmployee;六、外连接Outer Join普通连接内连接会丢弃不满足连接条件的元组外连接则保留这些悬空元组用NULL填充缺失部分。6.1 左外连接Left Outer Join ⟕保留左关系 R 中所有元组右关系 S 中无匹配时填 NULLR ⟕ S R ⟕ SR⟕SStudent(sid, name) Enrollment(sid, cid) (1, Alice) (1, 101) (2, Bob) (2, 101) (3, Carol) Student ⟕ Enrollment → (1, Alice, 101) (2, Bob, 101) (3, Carol, NULL) ← Carol 没有选课记录但被保留6.2 右外连接Right Outer Join ⟖保留右关系 S 中所有元组左关系 R 中无匹配时填 NULLR ⟖ S R ⟖ SR⟖S6.3 全外连接Full Outer Join ⟗左右两个关系的悬空元组都保留R ⟗ S R ⟗ SR⟗S对应 SQL-- 左外连接SELECT*FROMStudentLEFTOUTERJOINEnrollmentONStudent.sidEnrollment.sid;-- 右外连接SELECT*FROMStudentRIGHTOUTERJOINEnrollmentONStudent.sidEnrollment.sid;-- 全外连接SELECT*FROMStudentFULLOUTERJOINEnrollmentONStudent.sidEnrollment.sid;七、总结对比运算符号核心作用对应 SQL交∩取两个关系的公共元组INTERSECT连接⋈按条件合并两个关系JOIN ... ON除÷表达对所有语义无直接对应需用子查询广义投影π 带表达式投影时计算新属性SELECT expr AS alias外连接⟕ ⟖ ⟗保留不匹配的悬空元组LEFT/RIGHT/FULL OUTER JOIN核心要点这五种扩展运算虽然都可以由五种基本运算推导出来但在 SQL 和实际数据库查询优化中它们各自有对应的直接实现理解其语义对编写高效查询至关重要。