用于查询优化的关系代数

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

DDBMS 中的查询优化问题

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

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

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

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

查询处理

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

关系代数

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

基本操作是 −

• Projection
• Selection
• Union
• Intersection
• Minus
• Join

Projection

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

关系代数语法

$$\pi_{<{AttributeList}>}{(<{Table Name}>)}$$

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

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

$$\pi_{Name,Course}{(STUDENT)}$$

Selection

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

关系代数语法

$$\sigma_{<{Conditions}>}{(<{Table Name}>)}$$

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

$$\sigma_{Course} = {\small "BCA"}^{(STUDENT)}$$

投影和选择操作的结合

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

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

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

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

$$\pi_{Name}(\sigma_{Gender = \small "Female" AND \: Course = \small "BCA"}{(STUDENT)})$$

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

$$FemaleBCAStudent \leftarrow \sigma_{Gender = \small "Female" AND \: Course = \small "BCA"} {(STUDENT)}$$

$$Result \leftarrow \pi_{Name}{(FemaleBCAStudent)}$$

Union

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

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

$$Sem1Student \leftarrow \sigma_{Semester = 1}{(STUDENT)}$$

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

$$Result \leftarrow Sem1Student \cup BCAStudent$$

Intersection

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

例如，给定以下两个模式 −

EMPLOYEE

PROJECT

显示项目所在且员工所在的所有城市名称 −

$$CityEmp \leftarrow \pi_{City}{(EMPLOYEE)}$$

$$CityProject \leftarrow \pi_{City}{(PROJECT)}$$

$$Result \leftarrow CityEmp \cap CityProject$$

Minus

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

例如，列出所有没有正在进行的项目的部门(状态=正在进行的项目) −

$$AllDept \leftarrow \pi_{Department}{(EMPLOYEE)}$$

$$ProjectDept \leftarrow \pi_{Department} (\sigma_{Status = \small "ongoing"}{(PROJECT)})$$

$$Result \leftarrow AllDept - ProjectDept$$

Join

Join(连接)操作将两个不同表(查询结果)的相关元组合并到一个表中。

例如，考虑银行数据库中的两个架构:客户和分行，如下所示 −

CUSTOMER

BRANCH

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

$$Result \leftarrow CUSTOMER \bowtie_{Customer.BranchID=Branch.BranchID}{BRANCH}$$

将 SQL 查询转换为关系代数

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

示例

让我们考虑以下模式 −

EMPLOYEE

PROJECT

WORKS

示例 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_{AVERAGE(Salary)}{EMPLOYEE}$$

Relational algebra expression for outer block −

$$\sigma_{Salary <{AvgSal}>}{EMPLOYEE}$$

示例 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)})$$

$$Result \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 的相应分区中的元组进行比较。如果匹配，则将它们写出。