数据库系统实现 选择、投影、连接(spj)实验报告

《数据库系统实现 选择、投影、连接(spj)实验报告》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、实验四　SPJ算法一、实验内容：1.选择操作算法（TableScan;IndexScan）；2.投影操作算法；3.连接操作算法（嵌套循环连接；基于排序的等值连接；基于散列的等值连接；基于索引的连接）；二、实验要求：1.选择操作：i.无条件选择；ii.等值条件；iii.非等值条件；iv.范围条件；2.连接操作：i.卡氏积(排序连接和散列连接例外)；ii.等值条件；iii.非等值条件(排序连接和散列连接例外)；三、实验步骤：本实验代码实现使用的是C语言。1.iterator迭代器的设计：我们对一个表不管是进

2、行选择还是投影还是连接操作，都需要得到这个表的一条一条的元组，为此我们需要设计一个迭代器来方便的取出表中的元组。下面是我们对迭代器的设计，在文件scantable.h中：structiterator{intextent;/*currentwhichextent*/intblk;/*inwhichblockofthecurextent*/charb[PAGE_SIZE];/*curpagecontentpoint*/intt;/*?thtupofthecurpage*/intlen;/*tuplen*/}

3、;structiteratoropen_iter(constchar*tbname);intgetnext_iter(structiterator*iter,char*rec);/*fetchnexttuple,storeinrec*/intclose_iter(structiterator*iter);由于我们对记录的存储是聚簇的，所以我们的迭代器是一次取出一个块，然后一条一条的抛出记录，这个块中的记录用完之后再读下一个块，直到读出了这个表中的所有的块，得到了表中的所有记录。在iterator结构中，

4、extent,blk,t分别表示当前的区间，块，记录位置；b[PAGE_SIZE]存储了当前取出的块，len是记录的长度。open_iter()是打开一个迭代器，并进行初使化；close_iter()是关闭这个迭代器；getnext_iter()是得到下一条元组。具体的实现在scantable.c里面。1.SPJ结果的输出：在进行完选择和连接操作之后，得到的结果我们想返回给用户。我们实现了Oracle里里面SQL*plus界面里的返回结果的样式，即把结果表用字符界面显示出来。也在头文件scantable

5、.h里面，如下所示：intprint_tuple(char*rec,structtable_def*td);intprint_tbhdr(structtable_def*td);print_tbhdr()是显示结果表的表头，print_tuple()是显示结果表里的所有记录。在实现上，因为我们的每一条记录都是以char[]存储在数据文件里面，所以这个函数就是从记录头里面得到记录的模式信息，然后按记录模式逐个解析这条元组，然后按一定的形式显示。2.内存查找结构的实现：由于在下面的实验（基于块的嵌套循环连接

6、以及一些其它的一元操作）中要用到内存的查找结构：能在接近常量的时间内增加一个新元组，查找一个元组是否存在。所以我们需要实现一个这样的数据结构。这样的结构很多，像hash和平衡搜索树等等。我们选择了使用AVL树，也即平衡搜索树。因为我们觉得虽然时间性能上面AVL不如hash，但是在这个结构的管理上面，AVL还是有优势的。具体实现的接口如下(头文件avl.h中)：structBNode//definetypeofthenode{intnum;//numberofnodesintbf;//balance-fa

7、ctor(1,0,-1:thetreeisbalance)KeyTypekey;//keywordInfoTypedata;//storedatastructnode*lchild,*rchild;//leftchild,rightchildstructnode*same;//具有相同的key，但是其他信息不同};/*若平衡二叉树b中不存在与e相同的节点，则插入，并返回1；否则返回0**@b：在b指向的平衡二叉树中插入数据**@e：待插入的关键字**@taller：表示这颗树是否增高*/structBN

8、ode*InsertBT(structBNode*b,structRecorde,int*taller);/*@b：平衡二叉树据**@k：待查找的关键字找到节点后返回该节点*/structResult*SearchBT(structBNode*b,KeyTypek);/*回收二叉树的内存空间*/voidClearBT(structBNode*b);BNode是AVL树的结点的定义，每个结点里面保存了相应的key值和相应的元组数据和其它的一些