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

黑龙江大学

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

黑龙江大学软件学院

1、开发环境

硬件环境：Windows XP/Win7操作系统

软件环境：Microsoft Visual Studio 2005

2、DBMS系统架构

如图2-1所示，通过该类图可以大致看到所有的类的属性、行为以及各个类相互之间的关系。

图2-1 DBMS静态类图

在运行本系统时，会先通过Ganalysis的构造方法对系统进行初始化，包括载入文法和文法的分析表。载入成功后用户输入SQL语句时main函数会调用int Ganalysis::analysis_sql(char sql[])对输入的 语句进行处理，如果文法分析不通过时返回一个正数（错误出现的位置），main函数则会调用void Ganalysis::showError();来显示语法错误。如果语法分析成功，analysis返回OK(-2)， Ganalysis会调用相应的模块来具体执行SQL语句。此时不管具体执行结果如何，都会返回OK，在主函数中再调用void Ganalysis::showExecuteResult ();来显示执行的结果。

如下图2-2为该系统语法分析失败时的序列图，图2-3为系统语法分析成功时的序列图：

图2-2语法分析失败序列图

图2-3 语法分析成功时的系统序列图

3、DBMS主要功能模块

本DBMS主要包含6个模块，分别是SQL语言的词法和语法分析功能模块、创建数据库及数据操作功能模块、索引的创建及删除模块、查询功能模块、查询优化模块、数据库保护功能模块。在以下的各小节中将会详细介绍。

3.1 SQL语言的词法和语法分析

（1）功能介绍

该部分利用已有的编译知识，完成SQL语句的词法和语法分析工作，对用户输入的SQL语句进行检验是否正确。如果输入正确则进一步做处理，否则指出错误的位置。进一步了解DBMS中数据字典的作用，并为后续的查询处理和优化实验打好基础。

主要包括的词法语法分析语句包括：

（1）create 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）和转移（goto）两部分的语法分析表构成的。驱动程序对所有的SLR语法分析器都是一样的，不同的语法分析器只是语法分析表有所不同。分析程序每次从输入缓冲区读入一个符号，并使用栈来存储形如s0X1s1X2s2…Xmsm的串。其中sm在栈顶，Xi是文法符号，Si是称为状态的符号，每个状态符号概括了栈中位于它的下面的信息。栈顶的状态符号和当前的输入符号用来检索语法分析表，以决定移动规约分析的动作。在实际实现中，文法符号不必出现在栈里。SLR1语法分析的模型如图3.1-1所示：

图3.1-1

（3）算法描述

首先需要对输入的字符串进行词法分析，先通过函数void strChange(string str,vector &vecStr); 函数对字符串进行分割，将str中的单词、操作符等分成一个一个的string类型的字符串，并保持在vecStr中。具体的实现算法如下所示：

void strChange(string str,vector &vecStr){

    for (i=0;i        if(str[i]==' '||str[i]=='\'){

            i++;

            continue;

        }

        if(str[i]是运算符){//

            if(temp非空){

                将temp中保存的字符串保存到vecStr中

            }

            temp=str[i++];

            if(第i+1个也是字符操作符？){

如果str[i]与str[i+1]能构成"!="，">="，"<="则将temp+=str[i++];

}

            vecStr.push_back(temp);

            temp清空

        }

        else {

            temp+=str[i++];

            如果第i+1个字符串是分割符或操作符，则将temp保存到vecStr中。

        }

    }//for

    if(temp非空){

        向vecStr中保存temp

    }

}

对字符串进行分割后就可以进行文法分析了。利用函数int analysis::analysis_str(char sql[],string &error)对SQL语句进行文法分析。其中函数bool analysis::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        if(!action_at(status.top(),str[i],num)){

            分析出错，返回错误位置为第i个单词;

        }

        if(num>0){//移进

            状态栈中入栈num；

            符号栈中入栈str[i++]；

        }

        else if(num<0){//规约

            按照第num个产生式α→β进行规约，如果规约过程中出现栈空无法继续进行则返回错误位置为i-1

        }

            if(!goto_at(status.top(),p->left,num)){

                返回错误位置为i-1个单词

            }

            将num压入状态栈，将第num个产生式α→β的左部α压入符号栈。

        }

        else if(num==0){

            分析成功，返回OK

        }

    }

if(i==str.size())

        返回出错位置为i-1个单词

（4）程序流程图

对字符串分割的函数流程图如下图3.1-2所示：

对输入的SQL语句进行文法分析的函数int analysis::analysis_str(char sql[],string &error)流程图如下所示：

（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;

测试用例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、实现修改数据库记录的功能，该部分通过update语句可以修改符合某一条件的记录。同时会显示所修改的记录个数。

5、实现显示数据库结构和内容的功能。

6、实现在已有的关系中添加属性的功能，利用alert命令可以添加一个表的属性。表不存在时会有错误提示。

7、实现从已有的关系中删除属性的功能利用alert命令可以添加一个表的属性。表不存在时会有错误提示，当表只剩余一列时不允许再删除该属性可以通过drop语句删除表。

8、实现删除表的功能，使用drop命令删除表，当表不存在时会提示表不存在的错误信息。

（2）相关理论

1、文件和文件记录

数据通常都是以记录的形式存储在磁盘上。记录由一组相关的数据值或数据项排列而成。每个数据项对应于记录的一个域，由一个或几个字节组成。记录的每个域具有一个名字和一个数据类型，如整数、字符串等。一组域名字及其对应的数据类型构成了记录型或记录格式。文件是一个记录序列。一个文件的所有记录都具有相同的记录型。如果一个文件的所有记录都具有相同的长度，这个文件被称为定长记录文件。如果一个文件中的不同记录可能具有不同的长度，则称这个文件为变长记录文件。以下是磁盘上存储文件的方法和特点。

连续存储方法：按照文件中文件块的顺序把文件存储到连续磁盘块上。存取整个文件的效率高。文件扩充困难。

链接存储方法：在每个文件块中增加一个指向下一个文件块所在的磁盘块的地址指针。便于文件扩充。读整个文件的速度很慢。

索引存储方法：在磁盘上存储一个或多个索引块。每个索引块包含指向文件块的指针。

每个数据库管理系统都包含一个称为数据字典的小型数据库。

2、数据字典

数据字典用来存储数据库中数据对象的描述信息和数据库管理系统需要的控制信息。数据对象的描述信息包括概念模式、内模式、外模式以及它们之间的映象的描述。数据库管理系统需要的控制信息包括查询优化、安全性检查、用户权限验证、事务处理、报告生成、约束验证、数据定义和操纵语言编译等系统程序模块所需要的信息。

3、堆文件的查找操作

查找一个满足给定条件的记录：必须从文件的第一个记录开始搜索，直到发现满足条件的记录为止。如果满足条件的记录不止一个，需要搜索整个文件。

4、堆文件的插入操作

堆文件的头存储它的最末一个磁盘块的地址。插入一个记录时，首先，读文件头，找到最末磁盘块地址，把最末磁盘块读入主存储器缓冲区；然后，在缓冲区内把新记录存储到最末磁盘块的末尾；最后，把缓冲区中修改过的最末磁盘块写回原文件。

5、堆文件的删除操作

第一种方法：首先找到被删除记录所在的磁盘块；然后读到主存缓冲区，在缓冲区中删除记录；最后把缓冲区内容写回磁盘文件。这种方法将使文件中出现空闲的存储空间，需要周期地整理存储空间，避免存储空间的浪费。

第二种方法：在每个记录的存储空间增加一个删除标志位。当删除一个记录时，把删除标志位置1。查找记录时跳过删除位置为1的记录。这种方法也需要周期地整理存储空间。

第三种方法：当删除一个记录时，把文件末尾记录移动到被删除记录的位置。避免了存储空间的整理。只适用于定长记录文件。

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[]){

    char tname[100];

    从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 (id1,id2 … idn) values('value1', 'value2'…'valuen');”或者形如“insert into table_name values('value1', 'value2'…'valuen');”具体的算法如下所描述：

int Insert::insertRecord(char sql[]){

    if(获取表结构失败)

        return ERROR;

    if(sql[3]!="("){//insert into table_name values(...);

        对表的结构做检验，如果插入结构不正确，则返回并提示结构不匹配。

        向表中追加一条记录。

    }

    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[]){

    从sql中提取表名table_name.

    if(获取表结构失败) //表不存在

        return ERROR;

    if(set语句中存在与数据字典不符的列名)

        return ERROR;

    if(where语句中存在与数据字典不符的列名)

        return ERROR;

    从文件"database"+table_name+".txt"中读取表内容table。

    for(int row=0;row        if(table[row]符合条件)

            对table[row]修改。

    }//for

table写回到文件"database"+table_name+".txt"中.

    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"中读取表内容table。

    for(int row=0;row        if(table[row]符合条件)

            删除table[row]。

    }//for

将table写回到文件"database"+table_name+".txt"中.

    return OK;

}

5、添加属性的功能

Alter类中的函数int Alter::addColumn(char sql[])负责实现添加属性的功能。除了需要对数据字典中表的结构进行修改外，还要对存储表的文件进行修改，使文件的表结构与数据字典里存储的结构一致。具体的实现算法如下所示:

int Alter::addColumn(char sql[]){

    从sql语句中提取表名table_name;

    if(从数据字典中获取table_name表结构失败) //该表不存在

        return ERROR;

if(要添加的列名中存在与表结构中一致的列名) //sql语句中存在错误

        return ERROR;

    修改数据字典中的表的结构。

    从文件"database"+table_name+".txt"中读取表的内容存储到table中。

    for(int i=0;i        向table[i]中添加相应的列，值为空。

    将table写回到文件"database"+table_name+".txt"中。

    return OK;

}

6、删除属性的功能

Alter类中的函数int Alter:: delColumn(char sql[])负责实现删除属性的功能。该函数的实现与添加属性中addColumn实现类似，除了有sql语句的校验还有对数据字典和存储文件的修改。具体的实现算法如下所示:

int Alter::delColumn(vector vstr){//alter table name drop id1,id2,id3...  

    从sql语句中提取表名table_name;

    if(从数据字典中获取table_name表结构失败) //该表不存在

        return ERROR;

if(要删除的列名中有未知的列名) //sql语句错误

        return ERROR;

    修改数据字典中的表的结构。

    从文件"database"+table_name+".txt"中读取表的内容存储到table中。

    for(int i=0;i        从table[i]中删除要删掉的列。

    将table写回到文件"database"+table_name+".txt"中。

    return OK;

}

7、删除表的功能

int Drop::dropTable(char sql[]){

    从sql中提取要删除的表table_name.

    if(数据字典中不存在表table_name的记录)

        return ERROR;

    删除数据字典中关于table_name的记录

    system("del database\\\\"+table_name+".txt");//调用DOS功能对记录文件的删除

    return OK;

}

（4）程序流程图

1、创建表的功能

如图3.2-1为创建表的流程图。即int Create::create_table(char sql[])函数的实现流程图。

图3.2-1

2、插入记录的功能

图3.2-2

3、修改数据库记录的功能 

图3.2-3

4、删除数据库记录的功能

图3.2-4

5、添加属性的功能

图3.2-5

6、删除属性的功能

图3.2-6

7、删除表的功能

图3.2-7

（5）测试用例与实验结果 

1、测试用例3.2-1：create table student (name char(8),psw char (8),xh int,sorce int );

执行结果如图所示：

数据字典中保存的信息如下所示：

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  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 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;

执行结果如下图所示：

查看数据字典中如下图所示：

通过select语句查看表的内容如下所示：

6、测试用例3.2-6

alter 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命令建立相应的索引文件，当使用select语句查询表时如果存在相应列的索引，则系统会自动提示使用的索引文件。同时用户还可以使用drop index命令来删除已有的索引文件。本系统中创建的是辅助索引。由于时间仓促，使用的索引是普通索引，即基于二分查找的方式来提高查找的效率。

（2）相关理论

1、索引文件

类似于科技图书中的名词术语索引。

当查找一个记录时，先查阅索引，找到记录在文件中的地址，然后从文件读出这个记录。 

一个文件的索引通常定义在该文件的一个或一组域上。这组域称为索引域。

索引也是一个文件，称为索引文件。被建立索引的文件称为数据文件。

索引文件的记录称为索引记录或索引项。

每个索引记录包括两个域

第一个域用来存储数据文件索引域的值K；

第二个域用来存储一个或一组指针，每个指针指向一个索引域值为K的记录所在磁盘块的地址。

索引文件通常都按照索引域值的大小排序，以提高存取效率。

索引文件一般都远小于数据文件。

2、索引的分类

按照索引文件的结构，索引可以分为两类。

第一类是稀疏索引:稀疏索引把所有的数据记录按关键字的值分成许多组，每组设立一个索引项。这种索引的索引项少，管理方便，但插入和删除的代价较高。

第二类索引是稠密索引:稠密索引为每个记录设立一个索引项。记录存放是任意的，但索引是有序的。这种索引的查找，更新都比较方便，但索引项多，空间复杂性大。  

按照索引域的特点，索引可以分为三类。

主索引：索引域是数据文件的键；数据文件已经按照键值大小排序；由于索引域是键，每个索引域值对应唯一一个记录，索引记录的第二个域只存储一个指针。

聚集索引:索引域不是键；数据文件已经按照索引域排序；一个索引域值可能对应于多个记录，索引记录的第二个域可能存储多个指针。

辅助索引:索引域是数据文件的任何非排序域；一个文件只能具有一个主索引，但是可以具有多个辅助索引。

（3）算法描述

1、创建索引

int Create::create_index(char sql[]){//create index index_name on table_name (col_name asc/desc )

    if(索引已经存在)

        return ERROR;

    if(获取表结构失败)

        return ERROR;

    if(要创建索引的列名不存在)

        return ERROR;

    对索引列排序存入文件；

    数据字典中追加索引文件信息。

    return OK;

}

2、索引的更新维护

int index_update_check(table, struct){

    for(i=0;i        if(getIndex (table.name,struct.colname)!= ERROR){

            重新生成该索引文件

        }

    }

    return OK;

}

（4）程序流程图

1、创建索引

2、索引的更新维护

（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 index iname;

drop index iscore;

再执行select * from stu where stu.name='xiaoli';系统没有关于使用索引的提示：

3.4查询功能

（1）功能介绍

在该部分功能中主要提供给用户查询的功能，包括单关系全投影、单关系选择投影、多关系全投影、多关系选择投影等。用户还可以使用相应的选择条件选择部分查询。在表的存储中使用了C++ STL里的vector，利用一位数组上对表操作，因此在进行笛卡尔积、链接等操作时可以有任意多个表。为了用户查看方便，不至于显示时对表的各列混淆，我在实际显示中对每一列列名的前面还加上了表名，这样会显的清晰明了。

（2）相关理论

1、查询定义：

由高级查询语言（如SQL）表示的对数据库的一个或一组操作。

2、查询处理的步骤：

(1)扫描和语法分析

(2)查询优化

(3)查询代码生成

(4)查询执行

如下图所示是查询处理流程图和各步骤所产生的结果

3、关系数据库系统的查询处理包括两个方面：

实现各种关系代数操作的算法

查询优化：产生具有较高效率的查询执行计划，不一定是最优的执行计划。查询优化并不是所有的数据库系统都能做到。

过程性语言：查询优化的工作由用户来做

说明性语言：系统来做

设每个关系存储在一个文件中，每个文件仅存储一个关系。

参数说明：

TR：关系Ｒ中的元组数。

BR：关系Ｒ的磁盘块数。

M：主存缓冲区的块数(每块的容量等于一个磁盘块的容量)。 

IR：关系Ｒ的每个元组的字节数。

ｂ：每个磁盘块的字节数。  

（3）算法描述

1、选择的实现算法：

void Select::oper_select(Stable table,vector condition,Stable &result){ 

    if(rownum==0)//空表

        return ;

    for(i=0;i        if(table[i]符合条件){ 

            result.add(table[i]);

        }

    }

}

2、笛卡尔积的实现算法：

void Select::oper_product(Stable table1,Stable table2,Stable &result){ 

    for(i=0;i        for(j=0;j            result.add(table1[i]+table2[j]);

        }

    }

}

3、投影的实现算法：

void Select::oper_projective(Stable table,vector projective,Stable &result){

    for(i=0;i<(int)projective.size();i++){ 

        for(j=0;j            if(projective[i]==table.col_name[j]){

                result.col_name.push_back(table.col_name[j]);

                result.col_type.push_back(table.col_type[j]);

                vorder.push_back(j);

                break;

            }

        }//for

    }

    for(i=0;i        for(j=0;j<(int)vorder.size();j++){

            result.value.push_back(table.value[i*tcolnum+vorder[j]]);

        }

    }

}

4、查询树的计算实现算法：

void Select::tree_cal(searchTree *&tree){

    searchTree *p=tree;

    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"){

        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、选择的实现算法流程图：

2、笛卡尔积的实现算法流程图：

3、投影的实现算法流程图：

（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、测试用例3.4-3：

select * from stu,course;

select stu.name,course.name from stu,course where stu.id=1;

4、测试用例3.4-4：

select stu.name,course.name,grade.score from stu,course,grade where stu.id=grade.sid and course.id=grade.cid;

3.5查询优化

（1）功能介绍

在数据库的查询过程中使用不同的策略处理一个查询会得到不同的时间开销。因此选择较优的查询处理策略，可以大大减少查询处理时间，提高系统的处理能力。

在前面3.4节查询功能的介绍中也曾经提到过，该DBMS在内存查询处理时使用的是vector存储表的内容，而实际的查询过程当中几个只有十几行的表做完笛卡尔积后vector的大小就达到了六千多，而真正做完选择和投影后大小也不过几百甚至几十甚至为空。这个事实不仅充分说明了查询优化的必要性，也给了我们一个查询优化的方法：当一个查询中具有选择和连接时，应当先执行选择后执行连接，尽量减少中间结果的大小，加快连接操作的处理。

在该部分的优化中关键的函数有两个，一个主要是对选择条件的优化，当没有选择条件时不会调用该函数；另一个是对投影的优化，当然，任何的选择语句都会有投影操作，因此这一部分是一定会被调用的。理论上来说应该把投影的操作下移，原先查询树顶部的结点也自然不复存在，但如果不保留原先查询树顶部的结点优化之后可能输出的结果与用户希望的输出顺序有差异。因此我实际对查询树投影下移做了相应的优化之后，最顶部投影结点并没有去掉，但这并不会妨碍查询的效率。

（2）相关理论

1、启发式查询优化

在很多数据库管理系统中，查询处理的第一步是把查询变换为与关系代数对应的内部表示，如查询树。一个查询可以变换为一个等价的关系代数表达式。在关系数据库管理系统中，关系代数表达式的优化是一个非常重要的问题。

2、关系代数等价变换规律 

设E1和E2是两个关系代数表达式。如果E1和E2表示相同的关系，则称E1和E2等价，记作E1≡E2。

3、关系代数等价变换规律 （12类）

3.1选择串接律c1  AND ... AND cn (E)≡c1 (c2 (...(cn (E))...) 

3.2选择交换律c1 (c2  (E) )≡c2(c1 (E) ) 

3.3投影串接律ΠL1(ΠL2(...(ΠLn(E))...))≡ΠL1 (E)，其中E是关系代数表达式，Li是投影属性集合，而且L1 L2 ... Ln。

3.4选择投影交换律 ΠL (C (E) )≡C (ΠL (E) )其中，E是关系代数表达式，L是投影属性集合，C是选择条件，C只涉及L中的属性。ΠL (C (E) )≡ΠL (C (ΠL, B1, ..., Bm (E) ))。C还涉及L以外的属性B1、...、Bm 

3.5连接和笛卡儿乘积的交换律E1×E2≡E2×E1，E1   CE2≡E2   CE1 其中，E1和E2是关系代数表达式，C是连接条件。

3.6集合操作的交换律E1∪E2≡E2∪E1，E1∩E2≡E2∩E1其中，E1和E2是关系代数表达式。

3.7连接、笛卡儿乘积和集合操作的结合律

(1)  (E1×E2)×E3≡E1×(E2×E3),

(2)  (E1     C1E2)     C2E3 ≡ E1     C1 (E2     C2 E3),

(3)  (E1∪E2)∪E3 ≡ E1∪(E2∪E3),

(4)  (E1∩E2)∩E3 ≡ E1∩(E2∩E3), 

3.8选择、连接和笛卡儿乘积的分配律

(1) C1 (E1   C2 E2)≡(C1 (E1))C2 E2 其中，C1是选择条件，C2是连接条件，E1和E2是关系代数表达式，C1仅涉及E1的属性。

(2) C1 (E1      C2 E2)≡(C11 (E1))     C2 (C12 (E2))其中，C1是选择条件，C2是连接条件，E1和E2是关系代数表达式，C1=C11∧C12，C11仅涉及E1的属性，C12仅涉及E2的属性。

(3) 用×代替上边两个等价式中的    C2，就可以得到选择与笛卡尔乘积的分配律。

3.9投影、连接和笛卡尔乘积的分配律

(1) ΠL (E1     C E2)≡(ΠL1 (E1))     C  (ΠL2 (E2))

其中，C是连接条件，E1和E2是关系代数表达式，L=L1∪L2是投影属性集合，L1仅涉及E1的属性，L2仅涉及E2的属性，C仅涉及L的属性。

(2) ΠL (E1     C  E2)≡ΠL ( (ΠL1E1)      C (ΠL2E2) )

其中，C是连接条件，E1和E2是关系代数表达式，C涉及E1的属性A1、...、Ai、...、Ak和E2的属性B1、...、Bj、...、Bp，L{Ai, ..., Ak, Bj, ..., Bp}，L1={A1，...，Ai，...，Ak}，L2={B1，..., Bj，...，Bp}。

(3) 用×代替上边两个等价式中的   C，就可以得到选择与笛卡尔乘积的分配律。

3.10 选择与集合操作的分配律

(1) C (E1∪E2)≡(C (E1))∪(C (E2))，

(2) C (E1∩E2)≡(C (E1))∩(C (E2)),

(3) C (E1－E2)≡(C (E1))－(C (E2)),

3.11 投影与集合操作的分配律

(1) ΠL (E1∪E2)≡(ΠL (E1))∪(ΠL (E2)),

(2) ΠL (E1∩E2)≡(ΠL (E1))∩(ΠL (E2)),

(3) ΠL (E1－E2)≡(ΠL (E1))－(ΠL (E2)),

3.12 其他等价变换律

除了上述规律以外，还有很多其他等价变换规律。例如，使用DeMorgan定律可以把选择或连接条件等价地转换为其他形式的条件。

4、从关系代数表达式到查询树的转换：

给定如下查询

SELECT  A  FROM  R1，R2，R3   WHERE  P=15 AND N=“User” 

使用上述方法可以得到关系代数表达式

ΠA ( P=15 AND N=“User” ((R1×R2)×R3))

对应的查询树如下所示:

5、启发式代数优化算法：

输入：关系代数表达式。

输出：计算输入关系代数表达式的程序。

方法：

(1) 使用规律1把每个选择操作 C1 AND ... AND Cn (E)变换为： C1 ( ... ( Cn (E)) ... )；

(2) 使用规律2,4,8和10，把查询树上的每个选择操作移到尽可能靠近叶结点；

(3) 使用规律3、4、9和11，把查询树上的每个投影操作移到尽可能靠近叶结点；

(4) 使用规律1、3和4把串接的多个选择或多个投影操作组合为单个的选择或投影操作；

(5) 使用规律7重新安排叶结点，使得具有最小选择操作的叶结点最先执行；

(6) 组合笛卡尔乘积和相继的选择操作形成连接操作；

(7) 把最后的查询树划分为多个子树，使得每个子树上的操作可以由单个存取程序一次完成。划分方法如下：

① 每个二目操作在且仅在一个子树中；

② 如果二目操作α在子树T中，而且从叶到根的方向的路径β→α是仅包含一目操作的最长路径，则β→α也包含在T中。

(8) 产生一个计算最后查询树的程序，每一步计算一个子树。

（3）算法描述

1、对查询树的优化

void treeOptimize(searchTree *&tree){

    p=tree;

    if(p==NULL||p->left==NULL)

        return ;

    if(tree->left->name=="select")

        selectOptimize(tree);

    //以下为投影的优化

    按表对投影分类生成链表头结点为head

    while(head!=NULL){

    p=head->left;

    head=head->next;

    将p结点尽量下移接近对应的表。

    }//while

}

2、选择条件的优化

void selectOptimize(searchTree *&tree){

    head=tree->left;

    selectSplit(head,head->left); //对选择条件拆分

    计算条件结点数selectNum

    for(j=0,head=tree;j        p=head->left;

        head=head->left;

        将p结点尽量移近叶结点。

    }//for

}

（4）程序流程图

1、对查询树的优化

2、选择条件的优化

3.6数据库保护功能

（1）功能介绍

数据库使用的用户可能不只一个，因此这就要求系统需要有能够添加用户的功能、授权使用的功能。在该DBMS中，system是相当于管理员的一个作用，可以创建用户，也可以像普通用户一样创建表和授权用户表的使用权限。其他用户则没有创建用户的功能。所有的用户包括system在内，对于表的权限都是谁创建谁拥有该表的权限，当然用户授权给其他用户操作权限的前提也是自己必须要有该操作权限，移除其他用户的权限时用户也应拥有该表的操作权限。

同时为了安全性需要，例如可能有用户不小心删除掉了某个比较中要的数据，甚至整个表都已经删除。此时可以使用该系统的数据库日志进行恢复。日志保存在“database/DD/log.txt”中。数据库中记录了日期、时间、用户名、所做的操作、和操作的结果，如果有错误，日志中还会相应的显示错误的原因。

（2）相关理论

1、数据库系统一般可以分为单用户和多用户系统两种。

在任何一个时刻只允许一个用户使用的数据库系统称为单用户数据库系统。

允许多个用户同时使用的数据库系统称为多用户数据库系统。

多数数据库系统都是多用户系统。

例如飞机订票数据库系统、银行数据库系统等

2、在一个多用户数据库系统中，数据库中存储的数据项是用户程序存取的基本信息资源。

一个存取或改变数据库内容的程序的运行称为一个数据库事务，简称事务。

多个事务可同时运行并同时要求存取或修改同一个数据库记录。如果不对并发运行的事务加以适当的控制，会引起很多问题。

（3）算法描述

1、用户授权算法实现：

int Grant_Revoke::execute_grant(char sql[]){

//sql：grant id1,id2,id3.... on table_name to user1,user2.....;

    对表名、权限、用户名正确性检查

    if(用户权限已经存在){

            return  ERROR;

    }

    for(i=0;i        修改数据字典中user[i]的权限.

    }

    return OK;

}

2、用户移除权限算法实现与用户授权的算法实现类似，一个是向数据字典相应的用户中添加权限，一个是从数据字典中移除用户的权限。因此这里不再赘述。

（4）程序流程图

1、用户授权算法实现：

（5）测试用例与实验结果 

1、测试用例3.6-1：

用户system登录：

2、测试用例3.6-2：

创建用户，create user test identified by system password '123456';

打开数据字典，可以看到已经多了一个关于test用户的记录

如下是使用test进行登录的测试：

3、测试用例3.6-3:

如下所示，当用户没有权限时，用户不能查询相应的表

select * from stu;

system给test授权之后，用户就可以对表stu进行相应的操作，如下所示：

grant select,delete,update on stu to test;

查看数据字典，可以看到test用户的权限中已经多了一条记录，如下所示：

4、测试用例3.6-4：

数据库日志“database/DD/log.txt”部分内容如下截图所示：

4、总结

    以前的各科不管是小实验，还是课程设计都没有像现在的数据库系统原理一样如此模块多、内容多。各个模块既相又互之间有着紧密的联系。面对着这样的一个难题，既有对上学期编译原理的懵懵懂懂，还有对这一学期的数据库的完全捉摸不透，开始真的就想退缩了，但是仍然心里不甘就这样失败。于是研究一段时间遇到不会的就搁下了，搁一段时间又重新拿起来。反反复复，最后终于可以长舒一口气，放下沉重的心情，数据库课程设计终于做完了。

    完成这一科的实验，我既积累了许多的经验，也发现了自己的许多问题。以前对于vector的使用多半只是局限于push_back()，重载运算符[]的使用。现在突然明白很多时候也会使用到insert，而且还可以插入多个。还有string类，以前总对于find，substr都闲麻烦不愿多研究，而这一次不得不使用了，经过几次的使用发现其实也挺容易的。还有更多的尤其是像数据库课程设计这样的比较大的前后相互关联比较紧密的程序，动手之前一定要做好充足的准备工作。正所谓“工欲善其事，必先利其器”，我就犯了这样的一个错误，先前框架准备工作没有做好，越到后期越发现问题的严重。首先是对于命名的不合理，Ganalysis类虽然包含对用户的SQL语句分析工作，但还有对执行的调用；其次各个模块例如Select类、Create类…这些类里有很多一致的函数，还有一些类都需要获取数据字典的内容，表的内容等等。这也就说明应该需要一个抽象类来做为他们的父类，而具有相同功能的函数放到父类中，而且，在调用、获取结果时会简单很多，层次也就更清晰了。

    这一次的实验结束了，但这才仅仅是个开始，后面还会有更多的挑战，我坚信：我会一直努力下去！

5、参考文献

《数据库系统概论》作者：萨师煊，王珊  出版社：高等教育出版社

《数据库系统设计与原理(第二版)》作者：R. Ramakrishnan,J.Gehrke 冯建华，周立柱，郝晓龙等译  出版社：清华大学出版社

《数据库系统概念》（Database System Concepts Third Edition）作者：Abraham Silberschatz 等，杨冬青等译  出版社：机械工业出版社

《数据库系统原理》作者：李建中，王珊  出版社：电子工业出版社

《数据库系统基础教程》作者：Jeffrey D.Ullman等，岳丽华等译