RDBMS-Implementation

关系型数据库原型系统实现 SevenKiki

系统构建安装

在命令行按照以下步骤进行输入

cd /to/RDBMS/root_dir cd build cmake .. make -j sudo make install # 将rdbms_app安装到/usr/local/bin

系统设计方案

系统功能模块

本系统是一个简单的关系型数据库原型系统，采用 Visual Studio Code 2019作为开发平台，完成数据库管理系统的设计，实现了对模式、表格、数据库的常规管理及操作。 采用模块化的设计思想，大大提高了系统开发效率，并且最大限度减少错误。在对系统功能分析的基础上，应用模块化设计思路，得到下图所示的关系型数据库原型系统的功能模块图。

系统目录结构

关键技术与实现

算子实现

在本系统中实现了表上的6个算子 Union、Intersection、Difference、Projection、Selection、Natural Join。

主要文件： rdbms/operations/operation.hpp rdbms/operations/operation.cpp

1. runion<table R1, table R2>
   1. 功能：在两表上进行union操作
   2. 实现：将两个表的数据添加到一个新表

R1 U R2 = {(a1,...,an) | (a1,...,an) E R1 V (a1,..,an) E R1}

2. intersection<table R1, table R2>
   1. 功能：在两个表上进行intersection操作
   2. 实现：当表中元组在两个表中都存在，将元组插入到新表中

R1 n R2 = {(a1,...,an) | (a1,..,an) E R1 & (a1,..,an) E R2 }

3. difference<table R1, table R2>
   1. 功能：在两表上进行difference操作
   2. 实现：当表中元组只存在本表，而不存在另外一个表中时，将元组插入到新表中

R1 - R2 = {(a1,...,an) | (a1,..,an) E R1 & ~((a1,..,an) E R2)}

4. projection<table R1, string P>
   1. 功能：在表R1中映射P对应属性值
   2. 实现：当P匹配某一个属性名时，将该属性所有值插入到新表中

Pi(A1,A2,......,An) R1 = {(a1,.....,an)| (b1,....,bn) E R1 ^ (a1 = b1,....am = bm)}

5. selection<table R1, string A, string S>
   1. 功能：在表R1中筛选出属性A的值为S的元组
   2. 实现：当P匹配表中某一个属性名，且S匹配该属性中某一个值时，将该元组插入到新表中

Tproposition (R1) = {(a1,a2,......an)|(a1,a2,.....an) E R1 ^ (proposition)}

6. natural_join<table R1, table R2, string id1, string id2, string A1, string A2>
   1. 功能：连接两表
   2. 实现：如果关系R1与R2具有相同的属性组B，且该属性组的值相等时的连接，结果关系的属性集合为R1的属性并上R2减去属性B的属性集合

R1 |X| R2 = Pi(a1,a2,...an)|(a1,a2,.....an) E R1 ^ (a1,a2,.....an) E R2 ^ (T R1.A1 = R2.A2 = ...= Rn.An)

元组管理——tuple类

主要文件： rdbms/util/tuples.hpp rdbms/util/tuples.cpp

• 使用cell类存储元组中的每个属性值
• 使用STL set容器存储tuple的cells set<set<cell,cellComparator> > elements，优势为：set的底层实现是基于红黑树，加入set的所有元素会依据元素的键值自动被排序，加快查找速度，set不允许两个元素有相同的元素，这也符合表中不能有两个相同的元组这一原则

表管理——table 类

主要文件： rdbms/operations/table.hpp rdbms/operations/table.cpp

表类是一种使用n元关系存储数据的关系数据模型

R = {(a1,...,an) | a1 E A1 ,a2 E A2, ...,an E An}

其中

• 表是一个关系
• 每一行是一个n元组
• columns（属性）来自一个已定义的Domain，每个属性都有一个唯一的属性名

模式管理——rschema类

主要文件： rdbms/operations/rschema.hpp rdbms/operations/rschema.cpp

一个关系型模式包含表名和属性名，一个关系实例是一组用预定义模式创建的有限元组。示例如下，这是一个关系模式，其中表名是student, 属性有name、Age和Departmen。 基于该模式，可以创建一个名为student_info的表，如下图所示：

用户界面命令与测试截图

以下命令支持从RDBMS命令行使用，本节使用一个简单的学生系统作为测试示例,展示了输出截图。为了与平时实验衔接，在下一节还测试了个人通信薄用例

1. 给定模式名称、属性列表，新建一个关系型模式

create rschema

e.g: create rschema ID Name ID-num 其中 ID 是模式名，Name， ID-num是属性

其他例子：

create rschema Attendance ID-num Number-of-present create rschema Contact Name Email create rschema Grade ID-num Points

输出截图：

2. 给定表名、关系型模式，新建一个空表

create table

e.g:create table Student ID

其他例子：

create table Training-attendance Attendance create table Training-grade Grade
create table Students-contact Contact
create table Team-leader ID

输出截图：

3. 给定表名、csv文件路径，将文件导入到表中（追加模式）

copy <table name， string filepath>

e.g: copy student /Users/yuki/Desktop/student

4. 在现有表中插入一行数据

insert

e.g: insert Student Kirub G1T31

输出截图：

5. 在现有表中删除一行数据

remove row

remove row Student Kirub G1T31

输出截图：

6. 给定表名，显示表中所有数据

display

display Student

输出：

7. 删除现有表

remove table

remove table Student

输出：

8. 给定两个表名，进行intersect

intersect

intersect Student Team-leader

输出：

9. 给定两个表名，进行union

union

union Student Team-leader

输出：

10. 给定两个表名，进行difference

difference

difference Student Team-leader

输出：

11. 给定一个表名、需要映射的属性列表，进行Projection

project

project Students-contact Email

输出：

12. 给定一个表名、属性名、具体的值，进行select

select

select Training-grade ID-num G1T32

输出：

13. 给定两个表名，两个属性名，两个连接属性名，进行natural join

njoin <joining atribute from the 1st table>

Njoin Student Training-attendance ID-num ID-num Name Number-of-present

输出：

14. 查询数据库中的所有关系模式、表的元数据

database

输出：

15. 清屏

cls

16. 退出程序

exit

个人通信薄测试截图

1. 创建通信薄模式 addressbook

create rschema addressbook id name address email resume 测试截图：

2. 由通信薄模式创建表 ab

create table ab addressbook 测试截图：

3. 显示表ab

display ab 测试截图：

4. 从csv文件导入数据

copy ab /Users/yuki/Desktop/addressbook.csv 测试截图：

5. 插入新数据

insert ab 11 tom11 address11 email11 resume11111111111111 insert ab 12 tom12 address12 email12 resume11111111111111 测试截图：

6. 删除刚插入的一条数据

remove row ab 2 tom12 address12 email12 resume11111111111111 测试截图:

7. 显示database

database 测试截图：

8. select * from ab where ab.name = tom8

select ab name tom8 测试截图：

9. select * from ab where ab.email = email8

select ab email email8 测试截图：

未来工作与体会

体会

数据定义

在原型系统的设计阶段，我意识到之前三个实验都有一个明显缺陷——表的结构无法自定义，也就是说，表的属性个数、属性类型、属性名称在系统实现时就已经固定，比如在实验三中固定通信薄的结构如下， 这样的数据库系统只能运用用于个人通信薄，如何让数据库系统可以满足自定义的表结构？

struct addressbook{
    int ab_size;             //record size in bytes
    int ab_personkey;       //主键值
    char ab_phonenum;		//手机号
    char ab_name[25];       //人名
    char ab_address[50];    //地址
    char ab_email[25];      //邮箱
    int resume_len;        //变长个人简历
    char ab_resume[0];
};

对于这个问题，我在本原型系统解决方法是：

• 定义模式，在建表前先根据表的属性建立模式
• 指定模式，进行建表

查询解析

数据库查询语句复杂，如何进行查询语句解析？ 对于这个问题，我在本原型系统解决方法是：

• 简化查询语句，查询词之间用空格分割，便于解析，减少工作量
• 逐个实现数据库的六个算子（Union、Intersection、Difference、Projection、Selection、Natural Join），调用算子进行查询

加快查询速度

如何加快数据库查询速度？ 商业界和学术界通常使用索引来加快查询速度，考虑到索引工作量大、难实现，在本原型系统解决方法是：

• 将表中的所有元组存储在STL set容器中，set容器基于红黑树，能够快速查找元组
• 将元组中的属性值存储在STL set容器中，能够快速查找元组中的属性

用户界面

本原型系统的用户界面良好，主要体现在以下方面：

• 可以安装到系统，在命令行中可直接连接数据库
• 用户界面简洁，键入-help可以获取命令帮助
• 提供清幕指令
• 命令输入错误会有详细提示，以及相关指令帮助

未来工作

1. 数据权限管理：使用独立的用户权限表来设计表上的授权访问机制，包括：用户信息和权限的定义、授权和验证；
2. 事务回滚：对简单的事务性故障，能够支持对元组的删除撤销(UNDELETE)；
3. 表的属性个数限制：目前表属性的个数限制为10，未来将扩展表的属性个数；
4. 导入数据的文件格式限制：目前仅支持csv文件导入，未来将支持更多的文件类型；
5. 查询条件： 目前仅支持单表查询，系统中已经实现了连接算子，未来将基于连接算子实现多表查询；
6. 索引结构：目前属于哪个STL set容器加快查询速度，但是会增加空间大小，未来考虑设计索引类，加快查询速度。