中国民航大学计算机科学与技术学院，天津

收稿日期：2020年10月6日；录用日期：2020年10月21日；发布日期：2020年10月28日

摘要

目前国内的计算机系统能力培养多以组成原理、操作系统和编译系统为主，鲜有数据库管理系统(DBMS)开发的相关介绍。作为系统软件的重要组成部分，本文设计了一个DBMS开发项目，以此培养学生的计算机系统能力。项目结合数据库原理与编译原理等计算机专业骨干课程，以DBMS原型设计开发为载体，综合锻炼学生的程序设计能力、算法与数据结构应用能力，数据库原理和编译原理技术的理解与实现能力，为培养具有扎实理论基础和极强实践能力的计算机专业本科生提供了一条有效途径。

关键词

编译原理，数据库，系统能力培养，DBMS

System Development Capability Training of Computer Science with Compiler Principles & Database

Zhiyuan Zhang

School of Computer Science & Technology, Civil Aviation University of China, Tianjin

Received: Oct. 6^th, 2020; accepted: Oct. 21^st, 2020; published: Oct. 28^th, 2020

ABSTRACT

Computer system ability training in China is mainly based on computer organization, operating system and compiling system, while little about the development of database management system (DBMS). As DBMS is an important issue of the system software, this paper designs a DBMS development project to cultivate students’ computer system ability. The project mainly combines the courses of database principle and compiler principle, takes DBMS prototype design and development as the carrier, comprehensively exercises the students’ programming ability, algorithm and data structure application ability, and the understanding and implementation ability of database principle and compiler principle technology, so as to provide an effective way for cultivating computer major undergraduates with solid theoretical foundation and strong practical ability.

Keywords:Compiler Principle, Database, System Capability Training, DBMS

Copyright © 2020 by author(s) and Hans Publishers Inc.

This work is licensed under the Creative Commons Attribution International License (CC BY 4.0).

http://creativecommons.org/licenses/by/4.0/

1. 引言

计算机系统能力培养近年来一直受到教育部计算机专业教指委和各大高校的重视。在硬件系统能力培养上，北京航空航天大学等高校以计算机组成原理课程为核心，以MIPS指令集为基础，通过让学生自主设计CPU，完成一台功能相对完整的计算机 [1] [2]。辅以裁剪操作系统内核和GCC编译器使该计算机可编译和执行简单的C语言程序，极大提高了学生的硬件系统设计能力。华中科技大学结合数字逻辑和计算机组成原理两门课程，从门电路开始在FPGA上设计CPU，其上配合接口、操作系统、编译器等相应课程的实验内容，有效解决课程实验目标离散、实验内容无序割裂不能融合构成完整计算机系统的问题 [3]。桂林电子科技大学在计算机专业系统能力培养方面构建了基础能力培养、专业能力培养和综合能力培养三个层次，硬件系列课程实践环节和软件系列课程实践环节的“三横两纵”体系 [4]，使学生初步具备计算机系统综合开发能力。

在软件系统能力培养上，中国科学技术大学 [5] 和同济大学 [6] 等高校以编译原理课程为核心，通过逐层深入的方式让学生开发一个Java语言子集或C语言子集的编译程序，使高级语言能够被正确地编译和执行，提高了学生的软件系统设计能力。苏州大学编译原理实验则注重正规式到NFA的自动转换等编译核心算法的实现，并将SQL解析和LaTex源文件解析加入语法分析实验中 [7]。中国矿业大学配合工程教育改革，以培养学生解决复杂工程问题能力为目标，基于开源的Clang + LLVM设计和组织编译原理课程教学 [8]。中国人民大学 [9] 等高校则以数据库原理课程为核心，开发了具有自主知识产权的数据库系统。斯坦福大学 [10] 在数据库方面开设了CS145、CS245、CS345、CS346、CS347等多门课程，其中CS145只介绍数据库系统的使用，CS345和CS347介绍数据库理论知识，CS245介绍数据库系统的实现，CS346是DBMS实现的实验课。目前国内数据库原理课程的实验教学主要还是以SQL语句、存储过程等如何使用某种数据库产品的使用为主 [11]，鲜有关于DBMS系统开发的实验教学。对于计算机科学与技术专业的学生来说，不应只局限于应用软件的开发，系统软件的设计和开发更能体现和提高计算机专业学生的软件开发能力。DBMS是一种常用的系统软件，而开发一个DBMS更是综合了程序设计、数据结构、操作系统、数据库原理、编译原理的众多知识点，能极大提高学生的系统软件设计和开发能力。本文尝试设计一个实践教学项目，要求实现一个简单的DBMS系统，包括数据库的创建和删除、表的创建和删除，以及记录的增删查改等功能，借此培养学生的计算机系统软件开发能力。

2. 教学目的

本项目通过设计和开发一个功能相对完整的数据库管理系统(DBMS)，融会贯通程序设计、算法与数据结构、编译原理、数据库原理等多门课程内容，专业理论素养和实践能力相结合，综合培养学生的系统软件开发能力。实现的DBMS系统主要具备以下功能：数据库定义语言(DDL)和数据库操纵语言(DML)的编译以及查询计划的生成；实现创建数据库和数据表、实现单表增删查改功能；实现创建索引(聚集索引和非聚集索引)，实现多表连接查询功能。

3. 教学要求

3.1. 编译器设计

编译器实现将SQL语言解释翻译成相应的语义动作或查询计划，其依据为所支持的标准SQL语法。首先定义SQL语言的上下文无关文法，保证其符合自上而下或自下而上语法分析的要求；然后定义其语法制导翻译规则，保证SQL语言的语义能够得到正确的解释和执行。整个翻译过程分为词法分析、语法分析、语义分析和中间代码生成等环节。其中词法分析将SQL语句分解为独立的词法单位记号，如保留字，标识符，运算符及分界符等；语法分析检查SQL语句是否符合相应的语法规范，即是否能从上下文无关文法正确推导出SQL语句或者SQL语句是否可以正确归约到文法的开始符号；语义分析在语法分析的基础上检查SQL语句是否合理，如表名或字段名是否存在，运算符和字段类型是否匹配等；中间代码生成根据语法制导翻译规则生成相应的语义动作或生成查询计划，然后遍历查询计划并执行相应代码返回检索数据。

3.2. 数据库设计

数据库中需存储元数据信息和用户数据信息，为简单起见，不考虑存储日志数据。元数据是指数据库、表及索引等的定义，包括字段名称、类型、大小以及约束条件等。元数据在SQL语句翻译中起到类似于编译编程序符号表的作用，用于进行语义检查及数据存储空间的分配。由于要经常检索元数据，要求其查询速度要快，可考虑以适当的形式常驻内存，其持久化也要考虑日后读取的方便快捷性。

用户数据是指表中实际存储的数据。最简单的方式是为每一张表建立单独的存储文件，文件名即为表的名称。也可通过在元数据中设置表的存储位置偏移量的方法将所有数据存储在一个大的数据文件中。表中数据通常都是有结构的，每条记录的长度一般都相同，可根据记录长度实现随机访问。若记录长度不同，可考虑增加索引列表记录每条记录的起始位置和长度信息。由于索引列表中每条记录的长度是相同的，因此也可通过变址方式实现记录的随机访问。

若查询列无索引条目，则需进行全表扫描，因此在常用查询列上建立索引可加快查询速度。索引分为聚簇索引和非聚簇索引，每张表上只能建立一个聚簇索引，表中记录按照聚簇索引物理排列记录顺序。聚簇索引对范围查询非常有效，此时只需找出初始记录和终止记录的位置，返回两者之间的所有记录即可。可建立多个非聚簇索引，为优化查询性能，一般采用B + 树，其实现需要较好地掌握算法和数据结构中的相关内容，是项目实现的难点。当以表的索引列为查询条件时，SQL编译器应能生成带有索引的查询计划，而不是采用全表扫描的方式。多表连接查询时，也是先从索引开始，将相关记录读入内存后再按照规则进行连接。若不能全部读入内存，可采用存储为临时文件的方式。

3.3. 人机交互接口

DBMS提供人机交互接口连接用户和数据库。接受用户输入的SQL语句，利用编译器对SQL语句进行翻译，对SQL语句中的错误给出正确提示，生成并执行查询计划，最后返回查询结果。

4. 教学过程设计

4.1. 框架设计

图1. DBMS系统框架结构图

DBMS框架结构如图1所示。实线是控制流和数据流，虚线仅表示数据流。DDL编译器负责数据库创建、删除，模式的创建、删除及修改，索引维护等数据定义语言的编译工作。查询编译器负责数据增删查改等DML语言的编译工作，根据缓冲区中的元数据信息进行语义分析，生成查询计划。同时根据缓冲区的数据统计信息选择一个较优的查询计划并提交给执行引擎。执行引擎向资源管理器发出一系列小数据单元的请求(如记录)，资源管理器负责控制数据文件、数据格式以及索引文件。查询数据的请求传递给缓冲区管理器，缓冲区管理器的任务是从持久化的辅存中将一部分数据以页的形式存取到主存中，以加快查询速度。

4.2. 编译器设计

4.2.1. 文法设计

采用自上而下的递归下降语法分析方法，因此将文法设计为LL(1)文法。实现了创建数据库(create table)，创建表(create table)，删除数据库(drop database)，删除表(drop table)，插入数据(insert into tablename)，删除数据(delete from tablename)，查询数据(select from tablename)功能。

4.2.2. 编译器类图设计

图2. 编译器主要类图设计

图2给出了编译器涉及到的主要类，其中每个类只标出了比较重要的一些成员变量和方法。Symbol类和Lexer类负责词法分析，其中Symbol类存放词法单位记号，如常量、变量、保留字、运算符等，Lexer类是词法分析的主类，负责识别单词符号，其中的nexttoken()方法返回语法分析所需的下一个词法记号。SQLAParser是一个抽象类，包括语法分析中涉及到的一些栈操作的定义，其中的token方法就从Lexer中读取下一个词法记号。SQLParser是SQLAParser类的扩展，接收用户输入的SQL语句并进行语法分析。

4.3. 数据存储组织

在底层，一个数据库对应一个后缀名为mdf的文件。数据按块组织，每个块的大小设置为4096个字节，即4 k大小。数据库初始大小为16 k个数据块，即64 M。当存储容量不够时，每次增加4 M，也就是1024个数据块。

4.3.1. 元数据组织

元数据占一个数据块。包含数据块的使用情况，有多少张表，每张表模式对应的数据块列表，如图3所示。简单起见，数据块连续分配，其使用情况包含两部分内容：已经使用的最大块号blockUsed、删除不用的块号列表removedBlockList。一个数据块被删除后，就将其加入removedBlockList列表，再次申请新块时，优先从其中选取。若没有，则新分配一个最大块号。

图3. 元数据块的组织

每个表模式占另外一个单独的块，包含第一个数据块的编号，模式名称以及多个属性字段信息，如图4所示。对于长度不定的字符串，例如模式名称schemaName，采用两部分存储：第一部分用4个字节存储字符串的长度信息，第二部分存储字符串本身的信息。由于java中存储一个字符需要2个字节，因此其占用的字节数为字符串本身长度的2倍。

图4. 模式块的组织

4.3.2. 数据存储组织

数据块的按照链接方式组织在一起，每一个数据块均在开始位置表明下一个数据块的编号，若为−1，则表示是最后一个数据块。每条记录按照模式指定的长度定长存储，如图5所示。插入记录时，根据recordNumber将指针移动到新纪录的位置，写入后将recordNumber加1。读取和修改时，只需将指针移动到相应的位量后，按照相应的数据类型进行读取和写入。为简单起见，删除某条记录时，后面的记录相应往前移动。

图5. 数据块的组织

4.3.3. 数据库类图设计

图6. 数据库组织管理主要类图设计

数据库类图设计如图6所示。Block类是所有数据块的父类，定义了基本的数据块操作，包括读写各种类型的数据。MetaBlock负责元数据块管理，SchemaBlock负责模式数据块管理，DataBlock负责存放实际数据的块的管理。Diskmanagement类负责和底层的数据文件打交道，程序运行过程中，数据块都先存放在BufferAccess中，在缓冲区内进行管理。RecordManagement类是编译器和数据处理的联系通道，编译器识别的各种命令如create table，insert table等都是直接调用该类相应的方法实现的。Table管理具体某张表，Attribute类存储该表中具体的某个属性列的定义，Tuple类则具体存储表中的某条记录。ExpressionIntepreter负责解释SQL语句中的表达式，并将其转换为实际的值。

5. 系统运行结果

源代码包含21个java源文件，代码量3845行，以下是系统的部分运行结果演示。

6. 结束语

“DBMS系统的设计和开发”项目综合运用了计算机科学与技术专业多门课程的知识，能将学生所学理论知识应用于实践，提高其系统软件开发能力。设计开发了其中的部分功能，通过实际运行验证了项目的可行性。一些高层次的内容如索引，多表连接查询以及查询优化等有待进一步实现。

基金项目

中国民航大学教育教学改革项目：CAUC-2017-B1-09。

文章引用

张志远. 结合编译原理与数据库的计算机系统能力培养
System Development Capability Training of Computer Science with Compiler Principles & Database[J]. 计算机科学与应用, 2020, 10(10): 1789-1797. https://doi.org/10.12677/CSA.2020.1010189

参考文献