关系代数 (Relational Algebra)

关系代数是一种用于关系数据库的过程化查询语言。它定义了一组运算，这些运算以一个或多个关系（表）作为输入，并生成一个新的关系作为输出。

1. 基本运算 (Fundamental Operations)

1.1 选择 (\(\sigma\))

作用：从关系 \(r\) 中选取满足给定谓词（条件） \(P\) 的元组（行）。

符号：\(\sigma_P(r)\)

示例：找出 instructor 关系中 Comp. Sci. 系且工资大于 80000 的讲师。

代数： \(\sigma_{\text{dept_name} = \text{'Comp. Sci.'} \land \text{salary} > 80000}(\text{instructor})\)

SQL 等价：

SELECT *
FROM instructor
WHERE dept_name = 'Comp. Sci.' AND salary > 80000;

1.2 投影 (\(\pi\))

作用：从关系 \(r\) 中选取指定的属性（列），并自动去除重复行。

符号：\(\pi_{A_1, A_2, ..., A_n}(r)\)

示例：找出 instructor 关系中所有讲师的姓名（name）和系名（dept_name）。

代数： \(\pi_{\text{name, dept_name}}(\text{instructor})\)

SQL 等价：

SELECT DISTINCT name, dept_name
FROM instructor;

1.3 并 (\(\cup\))

作用：返回两个关系中出现过的所有元组，并自动去除重复。要求两个关系 \(r\) 和 \(s\) 并相容（属性数量相同，且对应属性的域/类型相同）。

符号：\(r \cup s\)

示例：找出 2009 年秋季或 2010 年春季开设的所有课程。

代数： \(\pi_{\text{course_id}}(\sigma_{\text{semester} = \text{'Fall'} \land \text{year} = 2009}(\text{section}))\) \(\cup\) \(\pi_{\text{course_id}}(\sigma_{\text{semester} = \text{'Spring'} \land \text{year} = 2010}(\text{section}))\)

SQL 等价：

(SELECT course_id FROM section WHERE semester = 'Fall' AND year = 2009)
UNION
(SELECT course_id FROM section WHERE semester = 'Spring' AND year = 2010);

1.4 差 (\(-\))

作用：返回在关系 \(r\) 中出现，但在关系 \(s\) 中未出现的所有元组。要求 \(r\) 和 \(s\) 并相容。

符号：\(r - s\)

示例：找出 2009 年秋季开设，但 2010 年春季未开设的课程。

代数： \(\pi_{\text{course_id}}(\sigma_{\text{semester} = \text{'Fall'} \land \text{year} = 2009}(\text{section}))\) \(-\) \(\pi_{\text{course_id}}(\sigma_{\text{semester} = \text{'Spring'} \land \text{year} = 2010}(\text{section}))\)

SQL 等价：

(SELECT course_id FROM section WHERE semester = 'Fall' AND year = 2009)
EXCEPT
(SELECT course_id FROM section WHERE semester = 'Spring' AND year = 2010);

1.5 笛卡尔积 (\(\times\))

作用：将关系 \(r\) 的每个元组与关系 \(s\) 的每个元组进行组合，形成一个新的关系。如果 \(r\) 有 \(n\) 个元组 \(m\) 个属性， \(s\) 有 \(k\) 个元组 \(p\) 个属性，结果将有 \(n \times k\) 个元组和 \(m + p\) 个属性。

符号：\(r \times s\)

注意：笛卡尔积本身很少单独使用，它通常与 \(\sigma\) (选择) 结合使用，以形成连接（Join）。

示例：组合 student 和 takes 的所有元组，并筛选出 ID 相同的元组。

代数： \(\sigma_{\text{student.ID} = \text{takes.ID}}(\text{student} \times \text{takes})\)

SQL 等价：

SELECT *
FROM student, takes
WHERE student.ID = takes.ID;

1.6 重命名 (\(\rho\))

作用：改变关系或其属性的名称。当需要对一个关系自身进行比较（例如，通过笛卡尔积）时，这个运算至关重要。

符号：\(\rho_{S(B_1, ..., B_n)}(r)\) (将关系 \(r\) 重命名为 \(S\)，并将其属性重命名为 \(B_1\) 至 \(B_n\))

示例：找出所有工资大于 Comp. Sci. 系某个讲师工资的讲师。

代数： \(\pi_{T.\text{name}}(\rho_T(\text{instructor}) \bowtie_{T.\text{salary} > S.\text{salary}} \rho_S(\sigma_{\text{dept_name} = \text{'Comp. Sci.'}}(\text{instructor})))\)

SQL 等价：

SELECT DISTINCT T.name
FROM instructor AS T, instructor AS S
WHERE T.salary > S.salary AND S.dept_name = 'Comp. Sci.';

2. 派生运算 (Derived Operations)

2.1 交 (\(\cap\))

作用：返回同时出现在关系 \(r\) 和 \(s\) 中的元组。要求 \(r\) 和 \(s\) 并相容。

符号：\(r \cap s\)

说明：可由差运算推导：\(r \cap s = r - (r - s)\)

示例：找出 2009 年秋季且 2010 年春季开设的课程。

代数： \(\pi_{\text{course_id}}(\sigma_{\text{semester} = \text{'Fall'} \land \text{year} = 2009}(\text{section}))\) \(\cap\) \(\pi_{\text{course_id}}(\sigma_{\text{semester} = \text{'Spring'} \land \text{year} = 2010}(\text{section}))\)

SQL 等价：

(SELECT course_id FROM section WHERE semester = 'Fall' AND year = 2009)
INTERSECT
(SELECT course_id FROM section WHERE semester = 'Spring' AND year = 2010);

2.2 \(\theta\)-连接 (\(\bowtie_P\))

作用：按给定谓词（条件） \(P\) 连接两个关系 \(r\) 和 \(s\)。

符号：\(r \bowtie_P s\)

说明：这是笛卡尔积和选择的组合，等价于 \(\sigma_P(r \times s)\)。

示例：找出 instructor 和 student 中所有 dept_name 相同的元组。

代数： \(\text{instructor} \bowtie_{\text{instructor.dept_name} = \text{student.dept_name}} \text{student}\)

SQL 等价：

SELECT *
FROM instructor, student
WHERE instructor.dept_name = student.dept_name;

2.3 自然连接 (\(\bowtie\))

作用：在两个关系 \(r\) 和 \(s\) 的所有同名属性上进行等值连接，并自动去除重复的公共属性列。

符号：\(r \bowtie s\)

示例：连接 student 和 takes（它们有公共属性 ID）。

代数： \(\text{student} \bowtie \text{takes}\)

SQL 等价：

SELECT *
FROM student NATURAL JOIN takes;