本文共 3103 字，大约阅读时间需要 10 分钟。

关系查询处理和查询优化

1. 关系R(A,B)和S(B,C,D)的存储情况

R表有20000个元组，每个元组占用1个磁盘块，存储在40个磁盘块中。

S表有1200个元组，每个元组占用1个磁盘块，存储在30个磁盘块中。

(1) R上没有索引，执行select * from R;

这是一个全表扫描操作。

要读取所有20000个元组，每个元组占用1个磁盘块。磁盘块读取次数 = 20000 / 40 = 500次。

(2) R中A为主码，A有3层B+树索引，执行select * from R where A=10;

由于A字段有3层B+树索引，查找过程如下：

根据A=10先从根节点开始查找，3层B+树每层的元素不到40个。

三次查找后找到目标记录。

最后一次查找后需要读取该元组的所有字段。

总共需要4次磁盘块读写。

(3) 嵌套循环连接R⋈Join S

嵌套循环连接需要估算以下代价：

cost = Br + BrBs / (K - 1) + (Frs * Nr * Ns) / Mrs其中：

• Br是R表占用的内存块数
• BrBs是R和S联合占用的内存块数
• K是内存缓冲区块数
• Frs是连接选择率
• Nr是R表的元组数
• Ns是S表的元组数
• Mrs是存放连接结果的块因子

由于内存缓冲区块数K和存放连接结果的块因子Mrs未知，无法计算具体代价。

(4) 排序合并连接R⋈Join S

排序合并连接时，需要考虑R和S在B属性上的排序情况：

• 有序的情况：

  cost = Br + Bs + (Frs * Nr * Ns) / Mrs
  其中：
  • Br是R表占用的内存块数
  • Bs是S表占用的内存块数

• 无序的情况：

  需要在连接前对R和S的B字段进行排序。排序代价为：
  (2 * Br + 2 * Br * log2(Br)) + (2 * Bs + 2 * Bs * log2(Bs))
  其中：log2表示以2为底的对数。

  分别代入R有500块（每块存储500个元组），S有40块（每块存储30个元组），排序代价约为：

  R排序代价：500 * 11000次 ≈ 550000次
  S排序代价：40 * 480次 ≈ 19200次
  总排序代价约为114800次。

---

2. 学生-课程数据库查询优化

查询语句：

SELECT Cname FROM Student, Course, SC WHERE Student.Sno = SC.Sno AND SC.Cno = Course.Cno AND Student.Sdept = 'IS';

1. 原始语法树：

T1├── JOIN (Student, SC)│  └── JOIN (Course, SC)│      └── SELECT Cname└── WHERE Student.Sdept = 'IS'

2. 优化后的语法树：

T1├── JOIN (Student, SC) [条件：Sno]│  └── JOIN (Course, SC) [条件：Cno]│      └── SELECT Cname└── WHERE Student.Sdept = 'IS'

优化步骤：

先通过Sno筛选出与SC表匹配的学生记录。

再通过Cno筛选出与Course表匹配的课程记录。

最后返回Cname字段。

---

3. Teacher、Department、Work数据库模式

数据库模式：

• Teacher(Tno, Tname, Tage, Tsex)
• Department(Dno, Dname, Tno)
• Work(Tno, Dno, Year, Salary)

其中Tno、Dno、Year字段有B+树索引。

查询语句：

SELECT * FROM Work WHERE Year > 2000 AND Salary < 5000;

优化方法：

• 利用Year的B+树索引，快速定位Year > 2000的记录。
• 对于满足条件的记录，需检查Salary字段是否小于5000。
• 如果Salary字段没有索引，需全表扫描目标记录。

---

4. Teacher、Department、Work数据库模式复杂查询优化

查询语句：

SELECT Tname FROM Teacher, Department, Work WHERE Teacher.Tno = Work.Tno AND Department.Dno = Work.Dno AND Department.Dname = '计算机系' AND Salary > 5000;

1. 原始语法树：

T2├── JOIN (Teacher, Work) [条件：Tno]│  └── JOIN (Department, Work) [条件：Dno]│      └── WHERE Department.Dname = '计算机系'├── WHERE Salary > 5000└── SELECT Tname

2. 优化后的语法树：

T2├── JOIN (Teacher, Work) [条件：Tno]│  └── JOIN (Department, Work) [条件：Dno]│      └── WHERE Department.Dname = '计算机系'├── WHERE Salary > 5000└── SELECT Tname

优化步骤：

先通过Tno和Dno连接Teacher、Work和Department表。

在连接过程中筛选Dname = '计算机系'的部门记录。

最后筛选Salary > 5000的工作记录。

返回Teacher的Tname字段。

---

5. 日志记录分析

日志内容示例：

T1: T1 beginT2: T1 readT3: T4 readT4: T4 beginT4: T4 readT4: T4 writeT4: T4 commitT5: T4 readT5: T5 beginT5: T5 readT5: T5 writeT5: T5 commitT6: T5 readT6: T6 beginT6: T6 readT6: T6 writeT6: T6 commitT7: T6 read

(1) 系统故障发生在操作14之后：

• 需要重做的事务：T1和T3
• 需要回滚的事务：T4

(2) 系统故障发生在操作10之后：

• 需要重做的事务：T1
• 需要回滚的事务：T3

(3) 系统故障发生在操作9之后：

• 需要重做的事务：T1
• 需要回滚的事务：T2和T3

(4) 系统故障发生在操作7之后：

• 需要重做的事务：T1
• 需要回滚的事务：T2

---

6. 数据库日志示例分析

日志记录：

T1: T1 beginT2: T1 readT3: T2 readT4: T2 writeT5: T2 commitT6: T3 beginT6: T3 readT6: T3 writeT6: T3 commitT7: T3 read

(1) 系统故障发生在操作14之后：

• 系统回复后，A=8, B=7, C=11

(2) 系统故障发生在操作12之后：

• 系统回复后，A=10, B=0, C=11

(3) 系统故障发生在操作10之后：

• 系统回复后，A=10, B=0, C=11

(4) 系统故障发生在操作9之后：

• 系统回复后，A=10, B=0, C=11

(5) 系统故障发生在操作7之后：

• 系统回复后，A=10, B=0, C=11

(6) 系统故障发生在操作5之后：

• 系统回复后，A=0, B=0, C=0

转载地址：http://wkfz.baihongyu.com/