数据库课程设计任务指导书.doc

数据库课程设计（CS372）设计指导书上海交通大学计算机科学与工程系2009年4月1 引言大型课程设计是我系多年来一直坚持的特色课程，其目的是培养我系学生在大型软件和系统软件设计开发方面的能力。数据库课程设计是大型课程设计之一。数据库技术具有广泛的应用，有关数据库技术的课程是计算机学科的主干课程之一。数据库管理系统（DBMS）是支持数据库应用的重要的系统软件。数据库课程设计的课程目标是让学生自己设计并实现一个小型的关系数据库管理系统。设立数据库课程设计的指导思想是：使学生加深对数据库原理课程中学到的基本概念、基本原理和基本技术的理解；提供一个让学生综合应用所学程序设计、操作系统、编译原理和软件工程等方面知识的机会；培养学生独立自主学习、分析和解决问题的能力；增强学生进行大型程序设计的实践能力。由于课程设置、课时安排等原因，为了完成这个课程设计，需要学生自学很多有关内容，而且系统涉及较多底层技术，所以总得来说，这是非常具有挑战性的课程设计任务。 文献【1】是本课程设计的主要的参考文献。2 系统分析数据库管理系统（DBMS）是建立在操作系统基础之上、用于管理数据库的系统软件。商用DBMS通常是功能全面而复杂的，但作为课程设计，我们要求学生设计实现的DBMS只需要具备一些基本功能组件，而且每个功能组件只需要完成简单而基本的功能。系统应该包括的基本功能组件及其相应功能描述如下：（1）存储管理器：在磁盘上按关系数据模型存储数据，并支持高效的访问（如索引和Hash）；（2）缓冲管理器：管理内存中的缓冲区，专用于与磁盘之间的数据I/O；（3）查询处理器：编译SQL语句，生成查询计划，优化查询计划；（4）执行引擎：执行查询计划；（5）用户界面：接受用户的SQL语句，显示返回结果；可以是图形用户界面，也可以是命令行界面。以上各个组件相互之间的关系如图1所示。DBMS还有很多其他组件或更全面的功能，如事务管理、并发控制和恢复机制等。由于复杂性和时间的关系，本课程设计不做要求。学有余力的同学可以考虑实现之。本课程设计只要求同学们定义一个SQL的较简单的子集。无论是支持的语句数量，还是每条语句的语法复杂度，相对于SQL标准都需要进行简化。3 系统设计要求按照软件工程规范进行DBMS的设计和实现。下面具体给出对DBMS各功能组件的设计要求和指导。查询处理器执行引擎缓冲管理器SQL语句查询计划存储管理器数据请求I/O请求缓冲区元数据数据/元数据/索引 图1：数据库管理系统组件构成3.1 存储管理器存储管理器实现对磁盘数据库的读写操作。DBMS当然可以自己管理磁盘，但更简单的实现方法是借助于操作系统的文件系统来管理磁盘数据。具体方法有两种：（1）一个表就是一个文件，文件具有自定义的格式，能够高效地读写文件记录。例如从dBase一直发展到FoxPro的.dbf文件格式（参见【2】），以及Access的.mdb文件（参见【3】）。这种方法比较适合个人桌面数据库系统。（2）一个数据库是一个文件，该数据库中的所有表都在这个文件上存储。可以把这个文件视为“逻辑磁盘”，它同样是划分为页（块）分配空间。例如SQL Server的.mdf主数据文件（参见【4】）。商用DBMS的数据文件格式非常复杂，同学们在设计自己的数据文件格式时应该做适当的简化。对数据文件的操作包括：记录存取（find，get，insert，delete，first，last等）；索引的建立与维护；数据文件的排序（归并排序）；数据字典的维护等。为了高效地访问文件记录，需要利用索引技术。数据库系统常用的索引是B树或B树，任何标准的数据结构或数据库系统教材都有这方面的内容。3.2 缓冲管理器数据库的数据存储于磁盘之上，但为了对数据进行操作，需要先把数据输入到内存中。缓冲管理器负责在系统分配的内存中维护缓冲区，用于缓冲来自磁盘的数据。缓冲区也是按页进行划分的。DBMS中所有需要从磁盘获取信息的部件都必须直接或间接地与缓冲区及缓冲管理器打交道。这些信息包括数据库的数据、元数据、索引等等。由于缓冲区的大小有限，缓冲管理器必须实现一个替换策略，即用新读进的磁盘块替换原来在缓冲区中的某个页。常见的替换策略包括LRU、FIFO等。3.3 查询处理器 查询处理器是本课程设计的最重要的部件。3.3.1 数据库语言SQL首先，需要定义一个简化的SQL语言。SQL语言包括数据定义语言（DDL）和数据操纵语言（DML）。本课程设计要求至少实现下面的语句。当然，每条语句都可以是高度简化的，即同学们可以自行给出其语法（SQL语法可参考【5】）。（1）数据定义语言DDL用来定义关系模式、视图等。主要语句包括：CREATE TABLEDROP TABLECREATE VIEWDROP VIEW在定义关系模式时，支持一些常用完整性约束的定义。如：PRIMARY KEYFOREIGN KEY REFERENCES CHECK（2）数据操纵语言用来对数据库中的数据进行查询和更新。主要语句包括：SELECTINSERTDELETEUPDATE3.3.2 数据字典数据字典也称为系统目录，其中存储元数据，即“关于数据的数据”。例如：数据库中有哪些表，每个表有哪些列，每个列的名称、类型、长度等。在编译有关DDL语句时，将用户提供的信息记录在数据字典中。将来进行查询处理时，数据字典是要频繁使用的系统数据。关系DBMS的数据字典本身一般也是用表来存储的。所以需要定义自己的数据字典的关系模式。例如，可以考虑的数据字典设计：systables(tablename,creator,)syscolumns(tableID,colname,type,length,key,default,index,)sysviews(viewname,definition)如果数据库有安全性子系统，则不同用户对不同的数据对象拥有不同的权限。为此，可以增加下列系统数据：user(uid,name,password)accesscontrol(uid,tablename,colname,priviledge)3.3.3 查询处理流程从用户输入SQL语句，到该语句被执行返回结果，其流程大体如图2所示。下面通过一个例子来详细说明这些步骤。数据库例： Student(sno, name, age) Course(cno, title) SC(sno, cno, grade) 查询例：SELECT cno FROM SC WHERE sno IN (SELECT sno FROM Student WHERE name LIKE wang%);（1）用户输入的查询语句字符串经词法分析器的分析，生成该查询的树表示；再经过语法语义检查器，根据数据字典中存储的数据库模式信息来检验分析树的有效性。例如：FROM中的表确实存在；语句中提及的所有列确实存在；表引用或未受限属性引用(在此时一般加上表名)都没有二义性；所有运算都是类型相容的；等等。上面的查询语句例子经过分析，可生成如图3所示的分析树。这里假设SQL语言的语法规则包括： := := SELECT FROM WHERE := := := IN （2）查询计划是表示查询计算的树，树的叶节点表示数据（表），内节点表示对数据的运算（操作）符。逻辑查询计划层次较高，是代数性的，其运算符对应于查询语言构造；而物理查询计划层次较低，是操作性的，其操作符对应实现的“存取方法”。 逻辑查询计划的运算符基于扩展关系代数。包括基本运算符（SELECT，PROJECT，CROSS-PRODUCT，UNION，DIFFERENCE）、非基本运算符（NATURAL-JOIN，THETA-JOIN，INTERSECT）和扩展运算符（RENAME，AGGREGATE/GROUP-BY，DISTINCT等）。从合法的分析树转换成逻辑查询计划只是直接了当的映射。例如从图3中的分析树可生成图4所示的逻辑查询计划。（3）利用关系代数的等价变换定律，可以将逻辑查询计划重写为更好的形式。重写逻辑查询计划可能产生更好的物理查询计划。重写是基于启发式规则的，例如最有效的一种启发式规则是“下推选择运算”。 对图4进行启发式优化，可以得到如图5所示的改进的逻辑查询计划。（4）对上面得到的更好的逻辑查询计划进行基于代价的优化，即可生成物理查询计划。物理查询计划的叶节点通常是表名，有时是索引或其他信息；内节点是操作符，即实现了的“存取方法”（算法）。例如单表的存取方法（TABLE SCAN，INDEX SCAN W/O CONDITION，CONDITION-BASED INDEX SCAN）、Join方法（NESTED-LOOP JOIN，SORT-MERGE JOIN，HASH JOIN）、SORT方法、GROUP/ AGGREGATE方法、UNION/ EXCEPT/ INTERSECT方法等等。另外，几个操作常常可以合并。对给定逻辑查询计划，可以有无数可能的物理查询计划。物理查询计划生成器尝试选出“最优的”计划。这是查询处理中内容最丰富最有效的部分! 从图5的逻辑查询计划可生成如图6所示的物理查询计划。至于对物理查询计划进行基于代价的优化，本课程设计不做要求。（5）最后是将物理查询计划树翻译成可执行代码，并交给执行引擎去执行。这一步非常依赖于系统。3.4 用户界面可以是命令行方式的用户界面，也可以是图形用户界面（GUI）。进入DBMS时应该有必要的登录过程，这是安全性的要求之一。系统管理员应该能定义数据库的合法用户及其相应权限。4 设计要求由两到三人组成开发小组共同完成一个DBMS项目。开发小组按照软件工程规范方法的要求进行开发。本指导书仅仅是一般的建议，各小组可以实施自己的设计方案。不得利用ODBC之类的API在现有的DBMS之上开发一个“DBMS”。必须开发一个以磁盘为主要存储介质的DBMS，不得以内存为主要介质。也就是说，如何在磁盘上组织数据库数据是课程设计的重要方面。对SQL语句的实现也必须通过编译技术，不能为实现而实现，通过各种取巧的手段来完成语句功能。考核时由学生在机器上操作演示，老师观察提问。最终提交光盘一份，内含所开发的DBMS系统和项目开发文档。各小组独立完成自己的系统开发，严禁抄袭、拷贝他人系统。一旦发现违反本条纪律，抄袭者与提供抄袭者都以零分论处。小组成员必须有明确的分工，开发文档必须各自分别撰写再汇总。严禁出现挂名现象。考核检查时将对此进行验证。一旦发现违反本条纪律，挂名者以零分论处，同组其他人成绩降等。5 参考资料【1】H. Garcia-Molina, J. D. Ullman, J. Widom. 数据库系统实现.【2】http:/www.moon-sof