1.迭代器算法的提出
数据库的三大类操作
-
一次单一元组的一元操作
下面是选择和投影操作，使用迭代器算法优化
-
整个关系的一元操作
-
整个关系的二元操作
-
整个关系的一元操作和二元操作可以使用以下算法进行优化
2.查询实现的两种策略
-
物化计算策略
一个关系操作就会扫描一遍数据库，下面的方式会扫描三次
-
流水线计算策略
用一系列迭代器构建流水线算法，三个操作组合在一起才扫描一遍数据库
3.迭代器算法基础
迭代器： 迭代的读取一个集合中的每一个元素，而封装其读取细节
- 面向对象的构造–可学习《面向对象程序设计语言》如C++,Java
类 Class A { }
类的函数/方法 Class A { void f1(){ } }
类的继承 Class A : B
类的实例化–对象: 例如“ a = new A； ” 或者 “A a”;
有一个抽象类
class iterator {
void Open();
tuple GetNext();//tuple元组类型
void Close();
iterator &inputs[];
}
所有关系操作可继承此迭代器进行构造。
不同操作，可以构造不同的Open(),GetNext(), Close()函数
R.Open();//打开R的关系
t := R.GetNext();//R的下一条记录
R.Close();
迭代器的构造：表空间扫描法-读取关系
- 读取R中每一个元组的迭代器，R迭代器
Open() {
b := R的第一磁盘块；
t := b的第一个元组；
}
GetNext() {
IF ( t 已超过磁盘块b的最后一个元组 ）{
将b前进到下一块
IF (没有下一块)
RETURN NotFound;
ELSE /* b是一个新块 */
t := b的第一个元组；
}
oldt := t;
将t前进到b的下一元组；
RETURN oldt；
}
Close() {
}
迭代器的构造：R∪S的算法-构造并操作的迭代器
- Union(R,S)迭代器
Open() {
R.Open();//迭代器R初始化
CurRel := R;//当前关系为R
}
GetNext() {
IF ( CurRel == R ） {
t:= R.GetNext();//读取R的一个元组
IF (t<> NotFound)
RETURN t; /* 未处理完 ，找到了R∪S的一个元组*/
ELSE { /* 已处理完R */
S.Open();
CurRel := S;
}
}
RETURN S.GetNext();
/* S处理完返NotFound,其将NotFound再返回 */
}
Close() {
R.Close();
S.Close();
}
迭代器的构造：
- SELECTION(R)
一次一个元组的操作
最少只需一个内存Block的内存空
基于R迭代器构造一个选择运算的迭代器
Open() {
R.Open();
}
GetNext() {
Cont:
t:= R.GetNext();//读取R的一个元组
IF (t<> NotFound)
IF F(t) == TRUE
RETURN t;
ELSE GOTO Cont;
ELSE RETURN NotFound;
}
Close() {
R.Close();
}
迭代器构造：在选择迭代器的基础上构造投影迭代器
- PROJECTION(SELECTION(R))
Open() {
SELECTION.Open();
}
GetNext() {
t:= SELECTION.GetNext();
IF (t<> NotFound) {
p := PROJECTION(t, α)//元组t按照α投影出来
RETURN p;
}
ELSE RETURN NotFound;
}
Close() {
SELECTION.Close();
}
迭代器构造：
- R Join S
Open() {
R.Open(); S.Open();
r:= R.GetNext();//R的下一个元祖
}
读R的一个元祖，循环读S的一个元祖
GetNext() {
REPEAT
{
s:= S.GetNext();
IF ( s == NotFound ）
{
S读取空了，则读取R的下一个元祖，再去循环S去读
S.Close();
r: = R.GetNext();
IF (r == NotFound)
RETURN NotFound;
ELSE
{
S.Open();
s := S.GetNext();
}
}
}
UNTIL (r 与s能够连接);
RETURN r和s的连接；
}
Close() {
R.Close(); S.Close();
}
- 与连接操作的基本实现算法的思想是一致的
