数据库系统原理课程设计总结报告

1、精选优质文档-倾情为你奉上黑龙江大学“数据库系统原理课程设计”总结报告学院软件学院年级2011级专业软件工程学号姓名杜常数报告日期2013/12/21成绩黑龙江大学计算机科学技术学院黑龙江大学软件学院专心-专注-专业1、 开发环境硬件环境：Windows XP/Win7操作系统软件环境：Microsoft Visual Studio 20052、 DBMS系统架构如图2-1所示，通过该类图可以大致看到所有的类的属性、行为以及各个类相互之间的关系。图2-1 DBMS静态类图在运行本系统时，会先通过Ganalysis的构造方法对系统进行初始化，包括载入文法和文法的分析表。载入成功后用户输入SQL语

2、句时main函数会调用int Ganalysis:analysis_sql(char sql)对输入的 语句进行处理，如果文法分析不通过时返回一个正数（错误出现的位置），main函数则会调用void Ganalysis:showError();来显示语法错误。如果语法分析成功，analysis返回OK(-2)， Ganalysis会调用相应的模块来具体执行SQL语句。此时不管具体执行结果如何，都会返回OK，在主函数中再调用void Ganalysis:showExecuteResult ();来显示执行的结果。如下图2-2为该系统语法分析失败时的序列图，图2-3为系统语法分析成功时的序列图：图

3、2-2语法分析失败序列图图2-3 语法分析成功时的系统序列图3、DBMS主要功能模块本DBMS主要包含6个模块，分别是SQL语言的词法和语法分析功能模块、创建数据库及数据操作功能模块、索引的创建及删除模块、查询功能模块、查询优化模块、数据库保护功能模块。在以下的各小节中将会详细介绍。3.1 SQL语言的词法和语法分析（1）功能介绍该部分利用已有的编译知识，完成SQL语句的词法和语法分析工作，对用户输入的SQL语句进行检验是否正确。如果输入正确则进一步做处理，否则指出错误的位置。进一步了解DBMS中数据字典的作用，并为后续的查询处理和优化实验打好基础。主要包括的词法语法分析语句包括：（1）cre

4、ate table（8）create index（2）drop table（9）drop index（3）alter table（10）create view（4）insert（11）drop view（5）delete（12）create user（6）update（13）grant（7）select（14）revoke（2）相关理论首先使用词法分析将语句中各个单词分离出来，包括关键字、标识符、整数、运算符、界符等；第二步使用语法分析器判别语句中的语法错误，即不同中来的单词搭配错误；第三步使用语义分析，校对语义错误。SLR语法分析器由输入、输出、栈、驱动程序及包含动作（action）和转移（

5、goto）两部分的语法分析表构成的。驱动程序对所有的SLR语法分析器都是一样的，不同的语法分析器只是语法分析表有所不同。分析程序每次从输入缓冲区读入一个符号，并使用栈来存储形如s0X1s1X2s2Xmsm的串。其中sm在栈顶，Xi是文法符号，Si是称为状态的符号，每个状态符号概括了栈中位于它的下面的信息。栈顶的状态符号和当前的输入符号用来检索语法分析表，以决定移动规约分析的动作。在实际实现中，文法符号不必出现在栈里。SLR1语法分析的模型如图3.1-1所示：图3.1-1（3）算法描述首先需要对输入的字符串进行词法分析，先通过函数void strChange(string str,vector&

6、lt;string> &vecStr); 函数对字符串进行分割，将str中的单词、操作符等分成一个一个的string类型的字符串，并保持在vecStr中。具体的实现算法如下所示：void strChange(string str,vector<string> &vecStr)for (i=0;i<str.length();i+)if(stri=' '|stri='t')i+;continue;if(stri是运算符)/if(temp非空)将temp中保存的字符串保存到vecStr中temp=stri+;if(第i+1个也是

7、字符操作符？)如果stri与stri+1能构成"!="，">="，"<="则将temp+=stri+;vecStr.push_back(temp);temp清空else temp+=stri+;如果第i+1个字符串是分割符或操作符，则将temp保存到vecStr中。/forif(temp非空)向vecStr中保存temp对字符串进行分割后就可以进行文法分析了。利用函数int analysis:analysis_str(char sql,string &error)对SQL语句进行文法分析。其中函数bool anal

8、ysis:action_at(int row, std:string vtch, int &num);将第row行符号为vtch的值保存到引用参数num中，如果action表对应的位置数据无效时将返回false. 函数bool analysis:goto_at(int row,char vnch,int &num)与action函数实现的功能类似。语法分析时首先把初始状态S0放在语法分析器的栈顶，把#压入符号栈中。然后执行如下部分的算法：for(i=0;i<str.size();)if(!action_at(status.top(),stri,num)分析出错，返回错误位

9、置为第i个单词;if(num>0)/移进状态栈中入栈num；符号栈中入栈stri+；else if(num<0)/规约按照第num个产生式进行规约，如果规约过程中出现栈空无法继续进行则返回错误位置为i-1if(!goto_at(status.top(),p->left,num)返回错误位置为i-1个单词将num压入状态栈，将第num个产生式的左部压入符号栈。else if(num=0)分析成功，返回OKif(i=str.size()返回出错位置为i-1个单词（4）程序流程图对字符串分割的函数流程图如下图3.1-2所示：开始i=0;i<str.length()?stri=

10、' '|stri='t'?i+YvecStr中保存tempstri是运算符？Ntemp非空？NYstri与stri+1构成>=,!=,<=,？temp+=stri+YvecStr中保存tempNtemp+=stri+如果第i+1个字符串是分割符或操作符，则将temp保存到vecStr中。结束NY对输入的SQL语句进行文法分析的函数int analysis:analysis_str(char sql,string &error)流程图如下所示：YYYYNY开始S0放在语法分析器的栈顶，把#压入符号栈中!action_at(status.top(

11、),stri,num)？i=0i<str.size()?分析出错，返回错误位置为第i个单词;num<0?状态栈中入栈num；符号栈中入栈stri+；stri+；Nnum>0?状态栈中入栈num；符号栈中入栈stri+；stri+；num=0?分析成功，返回OK 结束N （5）测试用例与实验结果 测试用例:3.1-1：create table stu(id int,name char(20),score int);测试用例3.1-2：select name,age,address from user;测试用例3.1-3：alerttt table stu add id int;

12、测试用例3.1-4：update stu set a='abcd' where a;3.2创建数据库及数据操作功能（1）功能介绍1、实现建立数据库表结构的功能。该部分还包括以下几个功能：（1）支持整型int、字符型char、变长字符型varchar数据。（2）以文件形式保存基本表。（3）具有相应的数据字典存储表名、表的结构等相关信息。2、实现输入数据库记录的功能，可以通过SQL insert语句向已有的表中插入数据库记录。当表不存在时会提示输入错误。3、实现删除数据库记录的功能，通过delete语句删除某一条或者符合某一条件的记录。同时会显示删除的记录个数。4、实现修改数据库记

13、录的功能，该部分通过update语句可以修改符合某一条件的记录。同时会显示所修改的记录个数。5、实现显示数据库结构和内容的功能。6、实现在已有的关系中添加属性的功能，利用alert命令可以添加一个表的属性。表不存在时会有错误提示。7、实现从已有的关系中删除属性的功能利用alert命令可以添加一个表的属性。表不存在时会有错误提示，当表只剩余一列时不允许再删除该属性可以通过drop语句删除表。8、实现删除表的功能，使用drop命令删除表，当表不存在时会提示表不存在的错误信息。（2）相关理论1、文件和文件记录数据通常都是以记录的形式存储在磁盘上。记录由一组相关的数据值或数据项排列而成。每个数据项对应

14、于记录的一个域，由一个或几个字节组成。记录的每个域具有一个名字和一个数据类型，如整数、字符串等。一组域名字及其对应的数据类型构成了记录型或记录格式。文件是一个记录序列。一个文件的所有记录都具有相同的记录型。如果一个文件的所有记录都具有相同的长度，这个文件被称为定长记录文件。如果一个文件中的不同记录可能具有不同的长度，则称这个文件为变长记录文件。以下是磁盘上存储文件的方法和特点。连续存储方法：按照文件中文件块的顺序把文件存储到连续磁盘块上。存取整个文件的效率高。文件扩充困难。链接存储方法：在每个文件块中增加一个指向下一个文件块所在的磁盘块的地址指针。便于文件扩充。读整个文件的速度很慢。索引存储方

15、法：在磁盘上存储一个或多个索引块。每个索引块包含指向文件块的指针。每个数据库管理系统都包含一个称为数据字典的小型数据库。2、数据字典数据字典用来存储数据库中数据对象的描述信息和数据库管理系统需要的控制信息。数据对象的描述信息包括概念模式、内模式、外模式以及它们之间的映象的描述。数据库管理系统需要的控制信息包括查询优化、安全性检查、用户权限验证、事务处理、报告生成、约束验证、数据定义和操纵语言编译等系统程序模块所需要的信息。3、堆文件的查找操作查找一个满足给定条件的记录：必须从文件的第一个记录开始搜索，直到发现满足条件的记录为止。如果满足条件的记录不止一个，需要搜索整个文件。4、堆文件的插入操作

16、堆文件的头存储它的最末一个磁盘块的地址。插入一个记录时，首先，读文件头，找到最末磁盘块地址，把最末磁盘块读入主存储器缓冲区；然后，在缓冲区内把新记录存储到最末磁盘块的末尾；最后，把缓冲区中修改过的最末磁盘块写回原文件。5、堆文件的删除操作第一种方法：首先找到被删除记录所在的磁盘块；然后读到主存缓冲区，在缓冲区中删除记录；最后把缓冲区内容写回磁盘文件。这种方法将使文件中出现空闲的存储空间，需要周期地整理存储空间，避免存储空间的浪费。第二种方法：在每个记录的存储空间增加一个删除标志位。当删除一个记录时，把删除标志位置1。查找记录时跳过删除位置为1的记录。这种方法也需要周期地整理存储空间。第三种方法

17、：当删除一个记录时，把文件末尾记录移动到被删除记录的位置。避免了存储空间的整理。只适用于定长记录文件。6、堆文件的修改操作定长记录文件：找到记录所在磁盘块，读入主存缓冲区，在缓冲区中修改记录，并写回磁盘。变长记录文件：先删除后插入。（3）算法描述1、创建表的功能创建表的功能由Create类的函数int Create:create_table(char sql)；来实现。其中传入的参数sql为形如“create table table_name (id1 类型1，id2 类型2 idn 类型n)” 其具体的算法描述如下所示：int Create:create_table(char sql)cha

18、r tname100;从sql语句中提取表名table_name，存储在table_name中.if(isExistTable(table_name)提示表已经存在。return ERROR;向数据字典中追加table_name的表名table_name以及表的结构。创建文件"database/"+table_name+".txt".return OK;2、插入记录的功能插入记录的功能由Insert类里的int Insert:insertRecord(char sql)；函数来实现。传入的sql语句参数形如“insert into table_name

19、(id1,id2 idn) values('value1', 'value2''valuen');”或者形如“insert into table_name values('value1', 'value2''valuen');”具体的算法如下所描述：int Insert:insertRecord(char sql)if(获取表结构失败)return ERROR;if(sql3!="(")/insert into table_name values(.);对表的结构做检验，如果插入

20、结构不正确，则返回并提示结构不匹配。向表中追加一条记录。else/insert into table_name(id1.)values('value1'.);if(sql语句中插入位置与插入的值不匹配)return ERROR;if(插入位置中列名与数据字典信息不符)return ERROR;向表中追加一条记录。提示记录插入成功。return OK;3、修改数据库记录的功能修改数据库记录的函数实现由Update类中的int Update:updateRecord(char sql)函数来实现，具体算法如下所示:int Update:updateRecord(char sql)从

21、sql中提取表名table_name.if(获取表结构失败) /表不存在return ERROR;if(set语句中存在与数据字典不符的列名)return ERROR;if(where语句中存在与数据字典不符的列名)return ERROR;从文件"database"+table_name+".txt"中读取表内容table。for(int row=0;row<rowNum;row+)if(tablerow符合条件)对tablerow修改。/fortable写回到文件"database"+table_name+".tx

22、t"中.return OK;4、删除数据库记录的功能修改数据库记录的函数实现由Update类中的int Delete:deleteRecord(char sql);函数来实现，具体算法如下所示:int Delete:deleteRecord(char sql)从sql语句中提取表名table_name;if(从数据字典中获取table_name表结构失败) /该表不存在return ERROR;if(where语句中存在与数据字典不符的列名)return ERROR;从文件"database"+table_name+".txt"中读取表内容ta

23、ble。for(int row=0;row<rowNum;row+)if(tablerow符合条件)删除tablerow。/for将table写回到文件"database"+table_name+".txt"中.return OK;5、添加属性的功能Alter类中的函数int Alter:addColumn(char sql)负责实现添加属性的功能。除了需要对数据字典中表的结构进行修改外，还要对存储表的文件进行修改，使文件的表结构与数据字典里存储的结构一致。具体的实现算法如下所示:int Alter:addColumn(char sql)从sql语

24、句中提取表名table_name;if(从数据字典中获取table_name表结构失败) /该表不存在return ERROR;if(要添加的列名中存在与表结构中一致的列名) /sql语句中存在错误return ERROR;修改数据字典中的表的结构。从文件"database"+table_name+".txt"中读取表的内容存储到table中。for(int i=0;i<rowNum;i+)向tablei中添加相应的列，值为空。将table写回到文件"database"+table_name+".txt"中。

25、return OK;6、删除属性的功能Alter类中的函数int Alter: delColumn(char sql)负责实现删除属性的功能。该函数的实现与添加属性中addColumn实现类似，除了有sql语句的校验还有对数据字典和存储文件的修改。具体的实现算法如下所示:int Alter:delColumn(vector<string> vstr)/alter table name drop id1,id2,id3. 从sql语句中提取表名table_name;if(从数据字典中获取table_name表结构失败) /该表不存在return ERROR;if(要删除的列名中有未知

26、的列名) /sql语句错误return ERROR;修改数据字典中的表的结构。从文件"database"+table_name+".txt"中读取表的内容存储到table中。for(int i=0;i<rowNum;i+)从tablei中删除要删掉的列。将table写回到文件"database"+table_name+".txt"中。return OK;7、删除表的功能int Drop:dropTable(char sql)从sql中提取要删除的表table_name.if(数据字典中不存在表table_na

27、me的记录)return ERROR;删除数据字典中关于table_name的记录system("del database"+table_name+".txt");/调用DOS功能对记录文件的删除return OK;（4）程序流程图1、创建表的功能如图3.2-1为创建表的流程图。即int Create:create_table(char sql)函数的实现流程图。开始从sql语句中提取表名table_name，存储在tname中.存在表table_name?向数据字典中追加tname的表名tname以及表的结构。创建文件"database/&q

28、uot;+tname+".txt".结束出错处理YN图3.2-12、插入记录的功能N开始结束获取取表结构失败？str3!="("？对表的结构做检验，如果插入结构不正确，则返回并提示结构不匹配。向表中追加一条记录。向表中追加一条记录。NYsql语句中插入位置与插入的值不匹配？出错处理YNY图3.2-23、修改数据库记录的功能 N开始结束从sql中提取表名table_name.获取表结构失败？出错处理set语句中存在与数据字典不符的列名？where语句中存在与数据字典不符的列名？从文件"database"+table_name+"

29、;.txt"中读取表内容 row=0;row<rowNum？对tablerow修改。tablerow符合条件？将table写回到文件"database"+table_name+".txt"中.row+NYNYYNNYY图3.2-34、删除数据库记录的功能开始结束从sql语句中提取表名table_name;从数据字典中获取table_name表结构失败?where语句中存在与数据字典不符的列名？从文件"database"+table_name+".txt"中读取表内容table。in

30、t row=0row<rowNum？tablerow符合条件？删除tablerowrow+将table写回到文件"database"+table_name+".txt"中.出错处理YYYNNN图3.2-45、添加属性的功能YYNN开始结束从sql语句中提取表名table_name;从数据字典中获取table_name表结构失败?要添加的列名中存在与表结构中一致的列名？从文件"database"+table_name+".txt"中读取表内容 row=0row<rowNum？向table

31、i中添加相应的列，值为空row+将table写回到文件"database"+table_name+".txt"中.出错处理YN图3.2-56、删除属性的功能开始结束从sql语句中提取表名table_name;从数据字典中获取table_name表结构失败?要删除的列名中有未知的列名？从文件"database"+table_name+".txt"中读取表内容 row=0row<rowNum？从tablei中删除要删掉的列row+将table写回到文件"database"+t

32、able_name+".txt"中.出错处理YYYNNN修改数据字典中的表的结构 图3.2-67、删除表的功能开始结束从sql语句中提取表名table_name;数据字典中不存在表table_name的记录?删除数据字典中关于table_name的记录出错处理YNsystem("del database"+table_name+".txt"); 图3.2-7（5）测试用例与实验结果 1、测试用例3.2-1：create table student (name char(8),psw char (8),xh int,sorce int

33、);执行结果如图所示：数据字典中保存的信息如下所示：2、测试用例3.2-2：insert into student values('abc','abc','1','30');insert into student values('abc','abc','2','60');insert into student values('du','ccd','3','70');insert into student

34、values('li','ssc','4','90');insert into student values('chen','ccc','5','80');insert into student values('chen','ccc','5','a80');如下图所示为“database/student.txt”中的保存信息：3、测试用例3.2-3：update student set sorce =55

35、 where xh=5;update student set sorce1=10 where name='abc'执行结果如下图所示：通过select语句查看表内容如下所示：4、测试用例3.2-4：delete from student where name='abc'delete from student where sorce >=55;执行结果如下图所示：执行select * from student ;语句结果如下图所示：5、测试用例3.2-5：alter table student add sorce1 int;执行结果如下图所示：查看数据字典中

36、如下图所示：通过select语句查看表的内容如下所示：6、测试用例3.2-6alter table student drop (sorce1);alter table student drop (a);执行结果如下图所示：数据字典中对于student的表结构的存储如下图所示：通过select语句查看score1已经不存在了，表的内容如下截图所示：7、测试用例3.2-7：drop table student;如下为执行的结果，通过select查看表时发现系统提示表已经不存在：3.3索引的创建及删除（1）功能介绍此部分意在通过建立索引文件以提高查询的效率。通过create index命令建立相应的

37、索引文件，当使用select语句查询表时如果存在相应列的索引，则系统会自动提示使用的索引文件。同时用户还可以使用drop index命令来删除已有的索引文件。本系统中创建的是辅助索引。由于时间仓促，使用的索引是普通索引，即基于二分查找的方式来提高查找的效率。（2）相关理论1、索引文件类似于科技图书中的名词术语索引。当查找一个记录时，先查阅索引，找到记录在文件中的地址，然后从文件读出这个记录。 一个文件的索引通常定义在该文件的一个或一组域上。这组域称为索引域。索引也是一个文件，称为索引文件。被建立索引的文件称为数据文件。索引文件的记录称为索引记录或索引项。每个索引记录包括两个域第一个域用来存储数

38、据文件索引域的值K；第二个域用来存储一个或一组指针，每个指针指向一个索引域值为K的记录所在磁盘块的地址。索引文件通常都按照索引域值的大小排序，以提高存取效率。索引文件一般都远小于数据文件。2、索引的分类按照索引文件的结构，索引可以分为两类。第一类是稀疏索引:稀疏索引把所有的数据记录按关键字的值分成许多组，每组设立一个索引项。这种索引的索引项少，管理方便，但插入和删除的代价较高。第二类索引是稠密索引:稠密索引为每个记录设立一个索引项。记录存放是任意的，但索引是有序的。这种索引的查找，更新都比较方便，但索引项多，空间复杂性大。 按照索引域的特点，索引可以分为三类。主索引：索引域是数据文件的键；数据

39、文件已经按照键值大小排序；由于索引域是键，每个索引域值对应唯一一个记录，索引记录的第二个域只存储一个指针。聚集索引:索引域不是键；数据文件已经按照索引域排序；一个索引域值可能对应于多个记录，索引记录的第二个域可能存储多个指针。辅助索引:索引域是数据文件的任何非排序域；一个文件只能具有一个主索引，但是可以具有多个辅助索引。（3）算法描述1、创建索引int Create:create_index(char sql)/create index index_name on table_name (col_name asc/desc )if(索引已经存在)return ERROR;if(获取表结构失败)

40、return ERROR;if(要创建索引的列名不存在)return ERROR;对索引列排序存入文件；数据字典中追加索引文件信息。return OK;2、索引的更新维护int index_update_check(table, struct)for(i=0;i<table.rowNum();i+)if(getIndex (,struct.colname)!= ERROR)重新生成该索引文件return OK;（4）程序流程图1、创建索引开始结束索引已经存在？对索引列排序存入文件；获取表结构失败？要创建索引的列名不存在？出错处理数据字典中追加索引文件信息YNNNYY2

41、、索引的更新维护开始i=0重新生成该索引文件i<table.rowNum？getIndex(,struct.colname)!= ERRORi+开始YYNN（5）测试用例与实验结果 1、测试用例3.3-1:create index iname on stu (name asc);create index iscore on grade(score desc);执行结果如下图所示：查看数据字典中会有关于相关索引的记录如下图所示是对于“database/iname.index”的文件内容：如下图，当查询时使用了索引时会自动提示使用的索引文件2、测试用例3.3-2:drop

42、 index iname;drop index iscore;再执行select * from stu where ='xiaoli'系统没有关于使用索引的提示：3.4查询功能（1）功能介绍在该部分功能中主要提供给用户查询的功能，包括单关系全投影、单关系选择投影、多关系全投影、多关系选择投影等。用户还可以使用相应的选择条件选择部分查询。在表的存储中使用了C+ STL里的vector，利用一位数组上对表操作，因此在进行笛卡尔积、链接等操作时可以有任意多个表。为了用户查看方便，不至于显示时对表的各列混淆，我在实际显示中对每一列列名的前面还加上了表名，这样会显的清晰明

43、了。（2）相关理论1、查询定义：由高级查询语言（如SQL）表示的对数据库的一个或一组操作。2、查询处理的步骤：(1)扫描和语法分析(2)查询优化(3)查询代码生成(4)查询执行如下图所示是查询处理流程图和各步骤所产生的结果3、关系数据库系统的查询处理包括两个方面：实现各种关系代数操作的算法查询优化：产生具有较高效率的查询执行计划，不一定是最优的执行计划。查询优化并不是所有的数据库系统都能做到。过程性语言：查询优化的工作由用户来做说明性语言：系统来做设每个关系存储在一个文件中，每个文件仅存储一个关系。参数说明：TR：关系中的元组数。BR：关系的磁盘块数。M：主存缓冲区的块数(每块的容量等于一个磁

44、盘块的容量)。 IR：关系的每个元组的字节数。：每个磁盘块的字节数。 （3）算法描述1、选择的实现算法：void Select:oper_select(Stable table,vector<string> condition,Stable &result) if(rownum=0)/空表return ;for(i=0;i<rownum;i+)if(tablei符合条件) result.add(tablei);2、笛卡尔积的实现算法：void Select:oper_product(Stable table1,Stable table2,Stable &res

45、ult) for(i=0;i<table1.rowNum;i+)for(j=0;j<table2.rowNum;j+)result.add(table1i+table2j);3、投影的实现算法：void Select:oper_projective(Stable table,vector<string> projective,Stable &result)for(i=0;i<(int)projective.size();i+) for(j=0;j<projective.size();j+)if(projectivei=table.col_namej)

46、result.col_name.push_back(table.col_namej);result.col_type.push_back(table.col_typej);vorder.push_back(j);break;/forfor(i=0;i<trownum;i+)for(j=0;j<(int)vorder.size();j+)result.value.push_back(table.valuei*tcolnum+vorderj);4、查询树的计算实现算法：void Select:tree_cal(searchTree *&tree)searchTree *p=tr

47、ee;string temp;if(p->left=NULL&&p->right=NULL)/叶结点return ;if(p->left!=NULL)tree_cal(p->left);if(p->right!=NULL)tree_cal(p->right);if(p->name="projective")oper_projective(*(p->left->table),p->condition,*(p->table);else if(p->name="select"

48、;)oper_select(*(p->left->table),p->condition,*(p->table);else if(p->name="product")oper_product(*(p->left->table),*(p->right->table),*(p->table);（4）程序流程图1、选择的实现算法流程图：NNYY开始table.rownum=0i<rownum?tablei符合条件?result.add(tablei)i+结束YNi=02、笛卡尔积的实现算法流程图：NNYY开始int

49、 i=0, j=0;i<table1.rowNumj=0;j<table2.rowNum Numresult.add(table1i+table2j);j+i+开始3、投影的实现算法流程图：NYYNY开始NNYYint i=0, j=0;i<projective.sizej=0;j<projective.size Num Numresult.col_name.push_back(table.col_namej);j+i+结束result.col_type.push_back(table.col_typej);projectivei=table.col_namej Num

50、 Numvorder.push_back(j);i<table.rowNumi=0j=0;j<(int)vorder.size()result.value.push_back(table.valuei*tcolnum+vorderj);j+i+N（5）测试用例与实验结果 1、测试用例3.4-1：select * from stu;2、测试用例3.4-2：select * from grade where score>60;select * from grade where score>60 and cid=4 or sid=1 and score>=70;3、测试

51、用例3.4-3：select * from stu,course;select , from stu,course where stu.id=1;4、测试用例3.4-4：select ,,grade.score from stu,course,grade where stu.id=grade.sid and course.id=grade.cid;3.5查询优化（1）功能介绍在数据库的查询过程中使用不同的策略处理一个查询会得到不同的时间开销。因此选择较优的查询处理策略，可以大大减少查询处理时间，提高系统的处理能力。在前

52、面3.4节查询功能的介绍中也曾经提到过，该DBMS在内存查询处理时使用的是vector存储表的内容，而实际的查询过程当中几个只有十几行的表做完笛卡尔积后vector的大小就达到了六千多，而真正做完选择和投影后大小也不过几百甚至几十甚至为空。这个事实不仅充分说明了查询优化的必要性，也给了我们一个查询优化的方法：当一个查询中具有选择和连接时，应当先执行选择后执行连接，尽量减少中间结果的大小，加快连接操作的处理。在该部分的优化中关键的函数有两个，一个主要是对选择条件的优化，当没有选择条件时不会调用该函数；另一个是对投影的优化，当然，任何的选择语句都会有投影操作，因此这一部分是一定会被调用的。理论上来

53、说应该把投影的操作下移，原先查询树顶部的结点也自然不复存在，但如果不保留原先查询树顶部的结点优化之后可能输出的结果与用户希望的输出顺序有差异。因此我实际对查询树投影下移做了相应的优化之后，最顶部投影结点并没有去掉，但这并不会妨碍查询的效率。（2）相关理论1、启发式查询优化在很多数据库管理系统中，查询处理的第一步是把查询变换为与关系代数对应的内部表示，如查询树。一个查询可以变换为一个等价的关系代数表达式。在关系数据库管理系统中，关系代数表达式的优化是一个非常重要的问题。2、关系代数等价变换规律 设E1和E2是两个关系代数表达式。如果E1和E2表示相同的关系，则称E1和E2等价，记作E1

54、E2。3、关系代数等价变换规律 （12类）3.1选择串接律sc1 AND . AND cn (E)sc1 (sc2 (.(scn (E).) 3.2选择交换律sc1 (sc2 (E) )sc2(sc1 (E) ) 3.3投影串接律L1(L2(.(Ln(E).)L1 (E)，其中E是关系代数表达式，Li是投影属性集合，而且L1 ÍL2 Í. ÍLn。3.4选择投影交换律 L (sC (E) )sC (L (E) )其中，E是关系代数表达式，L是投影属性集合，C是选择条件，C只涉及L中的属性。L (sC (E) )L (sC (L, B1, ., Bm (E) )。C还涉及L以外的属性B1、.、Bm 3.5连接和笛卡儿乘积的交换律E1×E2E2×E1，E1 CE2E2 CE1 其中，E1和E2是关系代数表达式，C是连接条件。3.6集合操作的交换律E1E2E2E1，E1E2E2E1其中，E1和E2是关系代数表达式。3.7连接、笛卡儿乘积和集合操作的结合律(1) (E1×E2)×E3E1×(E2×E3),(2) (E1 C1E2) C2