用于查询优化的关系代数

---

当发出查询时，首先对其进行扫描、解析和验证。然后创建查询的内部表示，例如查询树或查询图。然后设计替代执行策略来从数据库表中检索结果。为查询处理选择最合适的执行策略的过程称为查询优化。

DDBMS 中的查询优化问题

在DDBMS中，查询优化是一项至关重要的任务。由于以下因素，替代策略的数量可能呈指数级增加，因此复杂性很高 -

• 存在许多碎片。
• 片段或表在各个站点的分布。
• 通信链路的速度。
• 本地处理能力的差异。

因此，在分布式系统中，目标通常是找到一种良好的查询处理执行策略，而不是最佳策略。执行查询的时间是以下各项的总和 -

• 是时候将查询传递给数据库了。
• 执行本地查询片段的时间。
• 是时候收集来自不同站点的数据了。
• 是时候向应用程序显示结果了。

查询处理

查询处理是从查询放置到显示查询结果的所有活动的集合。步骤如下图所示 -

关系代数

关系代数定义了关系数据库模型的基本操作集。一系列关系代数运算形成关系代数表达式。该表达式的结果表示数据库查询的结果。

基本操作是 -

• 投影
• 选择
• 联盟
• 路口
• 减
• 加入

投影

投影操作显示表的字段的子集。这给出了表的垂直分区。

关系代数语法

$$\pi_{<{属性列表}>}{(<{表​​名称}>)}$$

例如，让我们考虑以下学生数据库 -

如果我们想显示所有学生的姓名和课程，我们将使用以下关系代数表达式 -

$$\pi_{姓名,课程}{(学生)}$$

选择

选择操作显示满足特定条件的表的元组子集。这给出了表的水平分区。

关系代数语法

$$\sigma_{<{条件}>}{(<{表​​名称}>)}$$

例如，在学生表中，如果我们想显示所有选择 MCA 课程的学生的详细信息，我们将使用以下关系代数表达式 -

$$\sigma_{课程} = {\small "BCA"}^{(学生)}$$

投影和选择操作的组合

对于大多数查询，我们需要投影和选择操作的组合。有两种方法可以编写这些表达式 -

• 使用投影和选择操作的顺序。
• 使用重命名操作来生成中间结果。

例如，显示 BCA 课程所有女学生的姓名 -

• 使用投影和选择操作序列的关系代数表达式

$$\pi_{姓名}(\sigma_{性别 = \small "女性" AND \: 课程 = \small "BCA"}{(学生)})$$

• 使用重命名操作生成中间结果的关系代数表达式

$$FemaleBCAStudent \leftarrow \sigma_{性别 = \small "Female" AND \: 课程 = \small "BCA"} {(STUDENT)}$$

$$结果 \leftarrow \pi_{姓名}{(女 BCAS 学生)}$$

联盟

如果 P 是一个操作的结果，而 Q 是另一个操作的结果，则 P 和 Q 的并集 ($p \cup Q$) 是 P 或 Q 或两者中没有重复项的所有元组的集合。

例如，显示所有第一学期或 BCA 课程的学生 -

$$Sem1学生 \leftarrow \sigma_{学期 = 1}{(学生)}$$

$$BCAStudent \leftarrow \sigma_{课程 = \small "BCA"}{(STUDENT)}$$

$$结果 \leftarrow Sem1Student \cup BCAStudent$$

路口

如果 P 是一个运算的结果，而 Q 是另一个运算的结果，则 P 和 Q 的交集 ( $p \cap Q$ ) 是 P 和 Q 中的所有元组的集合。

例如，给出以下两个模式 -

员工

项目

显示项目所在以及员工居住的所有城市的名称 -

$$CityEmp \leftarrow \pi_{城市}{(员工)}$$

$$CityProject \leftarrow \pi_{城市}{(项目)}$$

$$结果 \leftarrow CityEmp \cap CityProject$$

减

如果 P 是一个运算的结果，Q 是另一个运算的结果，则 P - Q 是 P 中且不在 Q 中的所有元组的集合。

例如，列出所有没有正在进行的项目的部门（状态=正在进行的项目） -

$$AllDept \leftarrow \pi_{部门}{(员工)}$$

$$ProjectDept \leftarrow \pi_{部门} (\sigma_{状态 = \small "ongoing"}{(PROJECT)})$$

$$结果 \leftarrow 所有部门 - 项目部门$$

加入

连接操作将两个不同表（查询结果）的相关元组组合成一个表。

例如，考虑银行数据库中的两个模式：客户和分行，如下所示 -

顾客

分支

列出员工详细信息以及分支机构详细信息 -

$$结果 \leftarrow 客户 \bowtie_{Customer.BranchID=Branch.BranchID}{BRANCH}$$

将 SQL 查询转换为关系代数

SQL 查询在优化之前被转换为等效的关系代数表达式。查询首先被分解为更小的查询块。这些块被转换为等效的关系代数表达式。优化包括对每个块的优化，然后对整个查询进行优化。

例子

让我们考虑以下模式 -

员工

项目

作品

实施例1

要显示工资低于平均工资的所有员工的详细信息，我们编写 SQL 查询 -

SELECT * FROM EMPLOYEE 
WHERE SALARY < ( SELECT AVERAGE(SALARY) FROM EMPLOYEE ) ;

该查询包含一个嵌套子查询。因此，这可以分为两个块。

内部块是 -

SELECT AVERAGE(SALARY)FROM EMPLOYEE ;

如果此查询的结果是 AvgSal，则外部块是 -

SELECT * FROM EMPLOYEE WHERE SALARY < AvgSal;

内部块的关系代数表达式 -

$$AvgSal \leftarrow \Im_{平均（薪水）}{员工}$$

外部块的关系代数表达式 -

$$\sigma_{工资 <{AvgSal}>}{员工}$$

实施例2

要显示员工“Arun Kumar”的所有项目的项目 ID 和状态，我们编写 SQL 查询 -

SELECT PID, STATUS FROM PROJECT 
WHERE PID = ( SELECT FROM WORKS  WHERE EMPID = ( SELECT EMPID FROM EMPLOYEE 
            WHERE NAME = 'ARUN KUMAR'));

该查询包含两个嵌套子查询。因此，可以分为三个块，如下 -

SELECT EMPID FROM EMPLOYEE WHERE NAME = 'ARUN KUMAR'; 
SELECT PID FROM WORKS WHERE EMPID = ArunEmpID; 
SELECT PID, STATUS FROM PROJECT WHERE PID = ArunPID;

（这里ArunEmpID和ArunPID是内部查询的结果）

这三个块的关系代数表达式是 -

$$ArunEmpID \leftarrow \pi_{EmpID}(\sigma_{Name = \small "Arun Kumar"} {(EMPLOYEE)})$$

$$ArunPID \leftarrow \pi_{PID}(\sigma_{EmpID = \small "ArunEmpID"} {(WORKS)})$$

$$结果 \leftarrow \pi_{PID, Status}(\sigma_{PID = \small "ArunPID"} {(PROJECT)})$$

关系代数算子的计算

关系代数运算符的计算可以通过多种不同的方式完成，每种替代方式称为访问路径。

计算替代方案取决于三个主要因素 -

• 操作员类型
• 有效内存
• 磁盘结构

执行关系代数运算的时间是以下总和 -

• 是时候处理元组了。
• 是时候将表的元组从磁盘获取到内存了。

由于处理元组的时间比从存储中获取元组的时间小得多，特别是在分布式系统中，因此磁盘访问通常被视为计算关系表达式成本的指标。

选择的计算

选择操作的计算取决于选择条件的复杂性和表属性上索引的可用性。

以下是根据索引的计算替代方案 -

• 无索引- 如果表未排序且没有索引，则选择过程涉及扫描表的所有磁盘块。每个块都被放入内存中，并且检查块中的每个元组是否满足选择条件。如果满足条件，则显示为输出。这是成本最高的方法，因为每个元组都被带入内存并且每个元组都被处理。

• B+ 树索引- 大多数数据库系统都是基于 B+ 树索引构建的。如果选择条件基于字段（该字段是此 B+ Tree 索引的键），则使用此索引来检索结果。然而，处理具有复杂条件的选择语句可能涉及大量的磁盘块访问，并且在某些情况下需要对表进行完整扫描。

• 哈希索引- 如果使用哈希索引并且在选择条件中使用其关键字段，则使用哈希索引检索元组将变得一个简单的过程。哈希索引使用哈希函数来查找存储该哈希值对应的键值的桶的地址。为了找到索引中的键值，执行哈希函数并找到桶地址。搜索桶中的键值。如果找到匹配，则将实际元组从磁盘块提取到内存中。

连接计算

当我们想要连接两个表（例如 P 和 Q）时，必须将 P 中的每个元组与 Q 中的每个元组进行比较，以测试是否满足连接条件。如果满足条件，则连接相应的元组，消除重复字段并附加到结果关系中。因此，这是最昂贵的操作。

计算连接的常见方法是 -

嵌套循环方法

这是传统的连接方法。可以通过以下伪代码来说明（表 P 和 Q，带有元组 tuple_p 和 tuple_q 以及连接属性 a） -

For each tuple_p in P 
For each tuple_q in Q
If tuple_p.a = tuple_q.a Then 
   Concatenate tuple_p and tuple_q and append to Result 
End If 
Next tuple_q 
Next tuple-p 

排序合并方法

在这种方法中，两个表根据连接属性单独排序，然后合并排序后的表。由于记录数量非常多，内存无法容纳，因此采用外部排序技术。一旦各个表被排序，每个排序的表一页被带到内存中，根据连接属性进行合并，并且连接的元组被写出。

散列连接方法

该方法包括两个阶段：分区阶段和探测阶段。在分区阶段，表 P 和 Q 被分成两组不相交的分区。确定一个公共的哈希函数。该哈希函数用于将元组分配给分区。在探测阶段，将 P 的某个分区中的元组与 Q 的相应分区中的元组进行比较。如果匹配，则将它们写出。