毕业设计（论文）-小型数据库命令解析器、数据存储的设计与实现设计与实现.doc

小型数据库命令解析器、数据存储的设计与实现摘 要当今时代，“数据”已经成为一种资源。随着各种数据获取技术和数据库技术的迅速发展，人们积累的数据越来越多，如何更加合理的管理数据显得更加重要。小型数据库就是模拟目前比较流行的一些大型数据库，实现通过在命令行输入相应命令来对数据进行存储，管理和查询。该小型数据库MyDB包括两大模块：SQL命令解析器及数据存储模块。SQL命令解析器负责解析用户命令并完成用户对表的创建、删除、插入、更新等操作；数据存储模块的主要功能是保存和管理用户的数据。整个系统是用C语言、采用模块化的程序设计思想实现的。关键词：MyDB；命令解析；数据存储；C语言Minidatabase- Design and Implementation of Command Interpreter and Data StorageAbstractIn this information era, data has been a kind of resource. With the fast development of data getting technology and database technology, people accumulate more and more data. How to manage these data more rational become more and more important. Minidatabase is to simulate popular database at present and implement data storage, management and querying by inputting commands from command line. This Minidatabase MyDB includes two modules: SQL command parser and data storage. SQL command parser takes in change of parsing user commands and operating tables, such as creating a table, deleting a table, inserting elements into table and updating table. The primary function of data storage module is to save and manage user data. The whole system is designed with the idea of modularized programmer and developed with C program language.Key words: MyDB ; command parse ; data storage ; C program language目 录论文总页数：24页1引言11.1数据库课程教学的现状11.2研制DBMS的重要性11.3MyDB的设计目标22数据库理论22.1数据元素的表示22.1.1字段22.1.2记录32.1.3块32.2查询编译器33MyDB的实现53.1记录的定义53.2命令解析模块63.2.1 词法分析器73.2.2 语法分析器113.2.3 SQL语句的实现133.3基本表模块183.3.1数据组织183.3.2基本表的实现193.4数据存储模块20结 论21参考文献21致 谢23声 明241 引言1.1 数据库课程教学的现状现在数据库教学的不足突出地表现在以下几点：1普遍只强调理论，不重视实践，在学习过程中难以对概念深刻领悟，课程结束后就很快把其中许多内容给淡忘掉了。2现有对数据库的实践也是流于形式，内容肤浅与真实的数据库管理系统相去甚远。比如用SQL语言对数据库进行一定的创建查询操作。这些实践都不过是对数据库管理系统的使用，根本谈不上了解数据库本身的运行机理。而且这些实践都太过理想化，完全把底层原理透明化了，这些实践充其量只不过是对SQL语言熟悉而已。3用真实的数据库管理系统来实践显然要好得多。但现实中的数据库管理系统都太过庞大，比如开源的数据库管理系统MYSQL，仅源代码就达数十万行之多。专业人员阅读起来都不会很容易，更不要说刚读本科的学生对其进行修改了，所以收效甚微。以上三点明显地说明了：“实践”在数据库原理教学中的重要性。需要一个能够真正对数据库所学理论进行有效的实践的数据库管理系统。但缺少一个好的教学用数据库管理系统，现有的教学用数据库管理系统并不那么适合中国的实际情况。因此，无论是从应用的角度还是学习数据库的理论教学的角度来看，设计与实现一个小型的数据库管理系统都是很有必要的。1.2 研制DBMS的重要性数据库技术产生于1970年前后。它的出现使得计算机的应用进入了新的时期，社会的每个领域都与计算机发生了联系。数据库技术聚集了数据处理最精华的思想，是管理信息最先进的工具。信息社会的紧迫需求使数据库技术成为计算机园地中一支最有生命力的新秀。而与人工智能的结合又使它获得了新的血液。20世纪80年代中期数据库技术进入一个新的层次，智能数据库、演绎数据库、专家数据库、面向对象数据库、工程数据库、多介质数据库、并行数据库、实时数据库等就是当代数据库研究的前沿。数据库管理系统（DBMS）的研制是一件非常复杂的软件工程。它涉及的面非常广泛，需要软件、硬件及设备方面的知识；需要一定的物质条件；需要研制人员的丰富的编程经验和精深的软件技术；需要科学的管理方法和科学先进的测试技术。当然由于系统的功能和规模不一样，其复杂程度也相差很大。大一点的数据库如IMS花费几千人年，系统R的研制花费了120个专家人年以及几千程序员人年，SYSTEM2000花费400人年。数据库的设计与数据库的设计不同，前者属于系统软件设计，与机器世界比较接近，它的基础是OS；后者属于应用软件设计，与现实世界更为接近，它的基础是数据库。所以数据库是介于用户程序和OS之间的一个中间媒介，是使得物理数据库与用户程序相互独立的软件系统。研制数据库对于从事数据库开发的科研人员和教学人员是一件十分有价值的工作。通过参加研制数据库的工作，可以加深对数据库技术的理解，弄清其来龙去脉，提高技术水平，从而改进数据库教学质量。更重要的是满足社会需求。同时数据库的研制是一件很基础的工作，是研究面向对象数据库、分布式数据库、知识库以及智能数据库的基础。因此，数据库原理一般都作为计算机专业的基础课程学习。1.3 MyDB的设计目标先看看国际上有关数据库发展的情况。随着计算机广泛而深入地应用与社会各行各业，作为其中重要支柱的系统软件数据库变的越来越庞大，功能越来越强，而且这种发展势头丝毫不见有放慢的迹象。特别是随着网络通信技术的发展，现代主流的数据库厂商纷纷把网络特性集成系统之中，甚至还出现了专门应用于网络环境的分布式数据库管理系统。所有这些数据库的复杂性给数据库的设计带来很大的挑战。如果个人想设计并实现一个商用的数据库基本上是不可能的，复杂的技术细节会把数据库的最基本的理论完全掩盖。因此，学生很难通过商用的数据库学习数据库的原理。MyDB是一个面向教学用的DBMS，这是必须首先坚持的，同时亦对DBMS的存储管理、SQL语言感兴趣。总之，MyDB是一个基于关系代数的、用C实现的、面向教学的关系型数据库管理系统。2 数据库理论2.1 数据元素的表示首先，研究一下最基本的数据元素的表示，即关系数据库系统中的属性值的表示。这是用“字段”来表示的。然后，考察字段如何组装成存储系统中更大的元素：记录、块和文件2.1.1 字段属性需要用定长或变长的字节序列表示，称作“字段”；可以用下式所示的CREATE TABLE 语句在SQL系统中声明一个关系。数据库负责表示和存储由这个定义描述的关系。既然关系是元组的集合，元组与记录或“结构”（C或C+术语）相似，可以设想每一个元组在磁盘中作为一条记录来存储。记录会占据某个磁盘块（或一部分），在记录内部，对应于关系的每一个属性有一个字段。CREATE TABLE StudentInfor（number int ,name CHAR(6) ,age int ,address CHAR(20) ,）2.1.2 记录字段被组装成定长或变长的集合，成为“记录”；l 定长记录的构造元组由记录表示，而记录由上述所讨论的各种字段组成。最简单的情况是记录的所有字段均为定长，则可以将字段连接成记录。l 记录首部当设计记录的格式的时候，必然会引出另一个问题：通常在记录中需要保存一些信息，而这些信息不是任何字段的值。因此有必要在记录的首部添加相关信息，如：记录长度、字段数等。2.1.3 块构成一个关系或类的外延的记录集存储为块的集合，成为文件。2.2 查询编译器查询处理器需采取三个主要步骤：1）对使用诸如SQL的某种语言书写的查询进行语法分析，亦即将查询语句转换成按某种有用方式表示查询语句结构的语法树；2）把语法分析树转换成代数关系表达式树（或某种类似标记），称之为逻辑查询计划；3）逻辑查询计划需转换成物理查询计划，物理查询计划不仅指名了要执行的操作，而且也找出了这些操作执行的顺序、执行每步所用的算法、获得所存储数据的方式以及数据从一个操作传递给另一个操作的方式。查询编译的开始几个阶段如图所示：图1 查询编译的阶段图1. 语法分析与语法分析树语法分析器的工作是接收用类似SQL这样的语言编写的文本并将之转换成语法分析树，结点对应于以下两者之一：1）原子：它们是词法成分，如关键字（如SELECT等）、关系或属性的名字、常数、括号、操作符（如+等），以及其它成分；2）语法类：即在一个查询中起相似作用的查询子成分所形成族的名字。可以用尖括号将描述性的名称括起来表示语法类。例如，用于表示以常用的select-from-where形式的查询，而将用于表示属性条件的任何表达式，如跟在SQL语句where之后的表达式。如果结点是一个原子，则该结点没有子女。然而，若该结点是一个语法类，则其子女通过该语言的语法规则之一进行描述。1. SQL的一个简单子集的语法通过给出可用于SQL子集的语言的某些规则，我们借此说明语法分析树的过程。1）查询语法用于表示所有正则SQL查询语句。它的一些语法规则是： := := ():=符号表示“可以表述为”。2）Select列表 := , := 这两条规则说明一个选择列表可以为任何由逗号分隔的属性列表：要么是单个属性，要么是一个属性、一个逗号以及一个或多个属性的任意列表。3）From列表 := , := 这里的from列表可由任意用逗号分隔的关系列表组成。这里只列出了部分规则，其他的规则请参考其他的书籍。我们来看这样一个查询语句：SELECT title FROM StarsInWHERE starName IN(SELECT nameFROM MovieStarWHERE birthdate LIKE %1960);按照我们所描绘的语法，此查询语句的语法分析树如下所示图2 语法分析树根是语法类，任何一个查询语句的语法树都必然是这种情况。顺着数往下走，我们可知该查询语句是select-from-where的形式；选择列表仅由属性title构成，from列表只有一个关系StarsIn。3 MyDB的实现3.1 记录的定义在这里，段是解析用户命令的最小单位，若干段的集合就构成了一条记录。因此段和记录的定义是进行命令解析器及数据存储的基础。在MyDB中，段与记录的关系可表示如下：记录长度字段数字段名1字段名2字段名n文件指针字段类型字段类型字段类型字段长度字段长度字段长度图3 段与记录的关系段和记录的定义在hrecord.h中实现：1 段的定义：typedef struct FldInforStruct/* 字段名 */char fldname10 ;/* 字段类型 */char fldclass6 ;/* 字段长度 */int fldlen ;/* 小数长度 */int dicimllen ; FieldInfor_T ;2 记录的定义：typedef struct WorkAreaStruct /* 记录长度 */int reclen ;/* 字段数 */int fldnum ;/* 记录总数 */int rectotal ;/* 字段结构信息指针数组，0号单元未用 */FieldInfor_T fldinforptrMAX_FIELD_NUM + 1;/* 文件指针 */FILE *DBFile_ptr ; RecordWorkArea ;3.2 命令解析模块SQL语言是一种面向集合的结构化查询语言。用SQL语言编写的命令一般都是解释执行的。所谓解释执行，就是解释和执行同步，不是像编译那样先把程序全部扫描一遍翻译成机器指令再直接运行机器指令。一般SQL语言可以嵌套在C等其他的高级语言中。因此，现在的商业用数据库都有自己的一套编译器系统，实现SQL解释（或编译）和高级语言编译器的无缝集成。由于MyDB的各个模块接口是采用C语言函数调用，因此SQL语言也不可避免地要和底层模块的接口函数打交道。MyDB命令解析器具体的原理图如下：图4 命令解析器具体工作流程原理图3.2.1 词法分析器词法分析器将SQL源程序解释成一个个独立的记号，然后将记号的类型以及记号所对应的值返回给语法分析器。MyDB的词法分析过程如图所示：图5 词法分析1) 首先删除用户命令中的空格、制表符、逗号等，提取相关的字符，这个功能由函数CutBlankTab_Head_Tail完成；2) 然后扫描提取的字符串，分步将关键字提取出。第一步，连分隔符（如括号等）一起提取，这个由函数GetSubstr_Delimitor完成；第二步，提取分隔符内的字符串，这步由函数GetSubstr_BetweenDelim完成；第三步，提取合法字符集，这一步由函数GetSubstr_ValidChar完成；3) 将字段信息存入数组，包括所提取出的字段名，字段类型，字段长度等，这个主要由函数*Change完成；4) 将记录值存入结构中，将所提取出来的记录值插入相应的结构之中。实现各流程的函数会在下面分别叙述。1. MyDB的词法分析器的关键字表为：enum SysKeyWordSetCREATE,DROP,INSERT,DELETE,SELECT,UPDATE,EXIT,HELP ;由于MyDB只是一个面向教学的微型数据库，所以它所包含的关键字仅仅是标准SQL的一个很小的子集。2. 词法分析器的接口参数：用户给出的命令结构是SQL编译器进行词法分析的基础。词法分析的任务在于提取关键字、省略多余空格等等。所以用户命令结构信息的定义也是必要的。/* 用户命令结构信息 */typedef struct /* 命令内部代码，如INSERT , CREATE等 */SysKeyWord_Type Cmd ;/* 表名 */char userstr10 ;/* 字段信息指针 */FieldInfor_T *fld ;/* 记录值指针数组 */char *recvalptrMAX_FIELD_NUM + 1 ;/* 查找范围 */char range10 ;/* 介词 */char parse20 ;/* 表达式 */char expression30 ;char token100 ;int count ;CmdRec_Type ;此接口参数定义了用户命令的结构信息，以便后来词法分析中关键字及有效值的提取。3. 词法分析器的接口函数词法分析器的接口函数定义在头文件lexical_tool.h中。主要是与词法分析相关的函数体，包括：l void CutBlankTab_Head_Tail (char *S);此函数用于删除词头和词尾的空格以及控制符；l void CutComma (char *S) ;此函数用于删除词头逗号；l int CountSymbol (char *S , char c) ;此函数用于计算字符个数；l int GetSubstr_Delimitor (char *S , int *ScanPos , char * Delimitor , char *Substr) ;此函数根据分隔符集合Delimitor，在串S中扫描起点ScanPos，取出子串Substr，并且移动扫描起点到新的位置，用于词法分析。伪码如下：int GetSubstr_Delimitor(char *S , int *ScanPos , char * Delimitor , char *Substr)InStr = FALSE;/*跳过分隔符（双引号的分隔符除外）*/while(*ScanPos len) & (strchr(Delimitor , *(S + (*ScanPos) != NULL)if(*(S + (*ScanPos) = )InStr = !InStr ;(*ScanPos) + ;SubstrBegin = *ScanPos ;/*扫描子串，包括双引号内的分隔符*/while(*ScanPos = len) & (InStr | (strchr (Delimitor , *(S + *ScanPos) = NULL)if(*(S + (*ScanPos) = )InStr = !InStr ;(*ScanPos) + ;/*复制子串*/strncpy(Substr , S + SubstrBegin , *ScanPos - SubstrBegin) ;/*串尾加0*/(Substr + *ScanPos - SubstrBegin) = 0 ;ok = (strcmp(Substr , ) != 0) & (*ScanPos) = len) ;l int GetSubstr_BetweenDelim(char *S , int *ScanPos , char Delim1 , char Delim2 , char *Substr);此函数在串S中扫描起点，取出在分隔符Delim1和Delim2之间的子串Substr，并且移动扫描起点到新的位置，用于词法分析。伪码如下：int GetSubstr_BetweenDelim(char *S , int *ScanPos , char Delim1 , char Delim2 , char *Substr)left = *ScanPos ;len = strlen(S) ;if(len = 0)*Substr = 0 ;return (TURE) ;/*验明左边的分隔符*/while(left len) & (Delim1 != Sleft)+left ;if(Sleft != Delim1)return 0 ;right = left + 1 ;/*验明右边的分隔符*/while(right len) & Sright != Delim2)+right ;if(Sright != Delim2)return 0 ;/*复制子串*/strncpy(Sunstr , &Sleft + 1 , right - left + 1) ;Substrright - left + 1 = 0 ;/*移动扫描点*/*ScanPos = right + 1 ;l int GetSunstr_ValidChar(char *S , int *ScanPos , char *ValidCh , char *Substr);此函数在串S中扫描起点后，取出由合法字符集合ValidCh组成的子串Substr，并且移动扫描点到新的位置，用于词法分析。伪码如下：int GetSunstr_ValidChar(char *S , int *ScanPos , char *ValidCh , char *Substr)len = strlen(S) ;*Substr = 0 ;while(*ScanPos len) & (strchr(ValidCh , SScanPos) = NULL) + (*ScanPos) ;left = *ScanPos ;while(*ScanPos = 1)for(i = 0 ; i strlen(Cmdline) ; i +)if(判断是否为行为动词)/*存储此关键字*/CmdRec.Cmd = SysKeyWordArrayi.SysW_N ; else if(判断是否为介词)/*存储此介词*/strcpy(CmdRec.parse , Token) ; else if(判断是否为表达式)ptr = strchr(Token , =) ;if (ptr)strcpy(CmdRec.expression , Token) ;else/*判断是否为全部范围*/ptr = strchr(Token , *) ;if(ptr)strcpy(CmdRec.range , *) ;elseptr = strchr(Token , ,) ;if(ptr)strcpy(CmdRec.range , Token) ;elsestrcpy(CmdRec.userstr , Token) ;return ;对具体SQL语句的语法的判断在Mydb.c中进行处理。相应的伪码表示如下：int main(void)swich(CmdRec.Cmd)case CREATE:Do_Create(CmdRec) ;breakcase DROP:Do_Remove(CmdRec.userstr) ;break;case INSERT:Do_Insert(CmdRec) ;break;case SELECT:Do_Select(CmdRec,CmdRec.token) ;break;case UPDATE:Do_Update(CmdRec,CmdRec.token);break;case DELETE:Do_Delete(CmdRec,CmdRec.token);break;case EXIT:exit(0);break;case HELP:Do_Help;break;default:break;return 0;3.2.3 SQL语句的实现MyDB所支持的SQL语句大体遵从标准的SQL语句的规范。在其规范上有稍许变动。MyDB支持标准SQL语句的一个子集，具体所支持的SQL语句的行为动词是：create、select、drop、delete、update、insert等。SQL语句的接口函数均包含在mysql.h头文件中，在mysql.c中进行具体的实现。接口函数如下：l int Do_Remove(char *file) ;删除文件，相当于Drop语句；l void Do_Insert(CmdRec_Type CmdRec) ;插入语句，将要插入的值放入表内，插入语句的实现过程如下图：图7 Insert语句实现过程伪码实现如下：void Do_Insert(CmdRec_Type CmdRec)定位头文件;读取一级数据元;读取二级数据元，即各字段信息;for(i = 0 ; i 插入字段数 ; i +)/*根据不同情况将要出入的记录值写入文件;*/if(插入的属性值为float)将此float类型字段值插入表中;else if(插入的属性值为int)将此int类型字段值插入表中;else (插入的属性值为char)将此char类型字段值插入表中;每插入一条记录，记录总数加1; 关闭数据文件;l void Do_Select (CmdRec_Type CmdRec , char *Token);查询语句，根据不同的情况实现对数据的简单查询，SELECT函数的分析过程如下图：图8 Select语句实现过程伪码如下：void Do_Select(CmdRec_Type CmdRec , char *Token)取得运算符在查询条件数组中的位置;把数据文件一二级原数据载入工作区;取得查询条件中字段相对应的本记录首位置的长度以便定位;for(m = 0 ; m reordtotal ; m +)逐一从文件读取每一条记录;根据字段类型读取记录值;swich(ch)/*根据记录类型对取出的记录值进行处理即满足条件的记录输出到屏幕*/case 整形:该整型数据满足条件，定位文件至该记录头位置;逐一输出该记录字段值;break;case 浮点形:该浮点型数据满足条件，定位文件至该记录头位置;逐一输出该记录字段值;break;case 字符型:该字符型数据满足条件，定位文件至该记录头位置;逐一输出该记录字段值;break;default:break;关闭数据文件;l void Do_Delete(CmdRec_Type CmdRec , char *Token);对基本表的数据的删除。MyDB的删除函数的分析过程如下图：图9 Delete语句实现过程伪码如下：void Do_Delete(CmdRec_Type CmdRec , char *Token)打开数据文件;for(m = 0 ; m recordtotal ; m +)swich(ch)/*根据删除条件字段的类型的不同，分流处理*/case 整形:满足删除条件显示的屏幕;不满足删除条件的写入临时新文件;break;case 浮点形:满足删除条件显示的屏幕;不满足删除条件的写入临时新文件;break;case 字符型:满足删除条件显示的屏幕;不满足删除条件的写入临时新文件;break;default:break;关闭数据文件;l void Do_Update(CmdRec_Type CmdRec,char *Token);更新数据库中的数据。MyDB中的Update函数分析过程如下图：图10 Update语句实现过程伪码如下：void Do_Update(CmdRec_Type CmdRec , char *Token)打开数据文件 ;for(m = 0 ; m recordtotal ; m +)/*根据字段的不同进行分流处理*/swich(ch)case 整形:将满足更新条件的进行更新并现实在屏幕;不满足条件的写入临时文件;break;case 浮点形:将满足更新条件的进行更新并现实在屏幕;不满足条件的写入临时文件;break;case 字符型:将满足更新条件的进行更新并现实在屏幕;不满足条件的写入临时文件;break;de