系统设计

实验在IO方面主要调用的是提供好的BufPageManager和FileManager, 并对其进行了一系列的封装操作. 其中, BufPageManager中的文件即项目中所提的表, 项目中数据库的实现即所有表存放的一个文件夹. 由于BufPageManager每次读写一页大小为8kb, 因此将8kb作为一个页的大小.

每创建一个表时, 系统将初始化32个页作为该表的初始容量. 每个表的第零页存储该表共有的页数n（4B）, 以及大小为n的bitmap存储相应的页是否有空槽. 每个页大小为8KB. 由于每个表在创建的时候, 每条项目的最大长度是固定的, 所以以该最大长度作为每一个项目的长度, 并根据该长度确定每一页中最多存入多少条. 这里需要说明每一页存储的格式. 在每一页的尾端系统会维护一个长度为最多存入条数的bitmap, 用来记录每个槽位是否有条目占用. 同时, 在每个存入的条目末尾, 项目会维护一个长度为每个条目中属性个数的bitmap, 用来记录该条目对应的属性是否为NULL. 具体的页结构见如下示意图：
1

系统功能

支持MySQL的一些系列基本操作：Create语句（创建数据库DATABASE, 创建表TABLE）, Drop语句, Select语句, Delete语句, Insert语句, Update语句, DESC语句. 同时能够支持其他功能有：多表连接, 聚集查询, 聚集查询, 分组聚集查询, 模糊匹配, 外键约束, 运算符和运算表达式等.

主要模块设计原理

1. 记录管理模块

该模块主要负责底层有关table的相关操作, 实现一些类和方法对存储记录的文件进行管理. 实现这个模块的主要内容在系统所定义的Table类中, 这个类中一些需要维护的属性如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Table {
public:
    int _fileID;
    int length;     // length of item / byte
    int slotNum;    // number of data slot
    int bitSize;    // number of bitmap bits in the end of page
    int typeNum;
    uint pageNum;   // first 4 bytes of first page of the file
    int nullPos;     // offset of null bitmap in each item
    int freeNumPos;  // freeMapPos - 4
    int freeMapPos;  // offset of free bitmap in each page

	string tbName;
    string path;    // path/tbName.txt
    string priKey;

    map<string, int> offset;
    vector<string> sequence;
    map<string, vector<string> > check;
    Attr example;
}

说明：length表示每个条目的最大长度, slotNum表示每个页可供使用的槽的数目, bitSize指的是每页最后的Bitmap大小, typeNum指的是每个条目中的属性的数量, pageNum指的是一个Table中所拥有的页数, nullPos指的是每个条目最后bitmap相对于该条目起始位置的偏移量, offset保存了每个条目中的每个属性相对于该条目起始位置的偏移量, sequence保存了各个属性的名称, check保存了响应属性名称的域完整性约束, example是一个样例条目：保存了每个条目的最大长度, 条目中每个属性的类型以及长度

在每个表中系统还维护了一个hashMap, 用来保存主键的取值, 如果待插入条目中的主键值已经存在于hashMap中, 则报错.
- 插入操作：
主要的实现的功能为维护域完整性, 主键重复报错, 以及插入条目中存在null时的判断. 在插入一个新条目之前, 程序先查看每个表的第零页, 找到存在空槽的页, 然后查看该页尾端的bitmap, 确定一个空槽的位置, 也就是插入的位置. 然后进行check以及主键的检查工作. 接着程序会根据example对每个条目的描述来确定插入的信息, 并根据offset中记录的每个属性的偏移量来进行插入操作.
- 删除操作：
当一个条目待删除时, 系统不会将存储有该条目内容的槽位清空, 而是会把对应页尾端bitmap的值置为“空闲”, 这样在查询和插入操作进行的时候, 访问页尾端的bitmap即可知道哪些条目存在, 哪些是空槽, 就不必每条都进行访问, 从而提高了效率.
- 更新操作：
当更新一个条目的时候, 系统首先会调用一个名为conform的函数来对更新的条件与每个条目进行匹配, 如果一个条目符合条件, 则在相对位置上重写条目即可. 由于example样例条目的存在, 系统会根据条目中属性的类型以及长度先提取出待更新的条目, 然后对需要更新的属性进行更新, 在重新写入相应的槽位即可.
- 查询操作
与更新操作类似, 系统会调用conform函数来匹配条件与每个条目, 并输出相应查找的属性.

2. 系统管理模块

首先介绍sql语句的解析过程, 如下图所示
main
其中

  • YACC是利用yacc工具进行的语法解析类；
  • DBManager类记录并管理所有的database, 利用单例模式构建；
  • DataBase类是一个database的实例, 记录有database的表单等信息；
  • Table类管理一个表单, 可以对一个table进行item的操作(添加/删除/更改等).

在数据库存储中, 每个database对应一个文件夹, 而每个table对应一个文本文件. 因此在系统管理模块需要对本地数据进行相应更改, 结合语句简要说明如下：

  • 创建数据库：DBManager类中的database队列增加相应记录, 并在本地创建文件夹；
  • 删除数据库：DBManager类中移除相应database, 并将本地文件夹移除；
  • 切换数据库：在DBManager中记录当前数据库, 更改该属性即可；
  • 创建表： 在相应DataBase类中增加相应table记录, 在该文件夹下增加相应文本文件；
  • 删除表： 在相应DataBase类中移除相应table记录, 在该文件夹下删除相应文本文件.

3. 查询解析模块

语句解析部分和系统管理模块部分相同.
在YACC解析到相应语句后, 会借助DBManager来调用相应database中的table类来进行相应操作.
以下部分以insert语句为例说明整个过程：
1. yacc语法解析

1
2
3
4
5
6
insertsql:
    INSERT INTO IDENTIFIER '(' tableitems ')' VALUES valuesql {
        $$.init($3, $5, $8);
        $$.display();
        $$.work();
    };

利用yacc解析出insertsql后直接调用相应类的work函数.
2. DBManager获取DataBase
work函数直接调用DBManager类的相应函数tbWork, 而在该函数中会先获取相应DataBase类, 然后调用该DataBase类的函数insertTB;
3. DataBase获取Table
在DataBase中会先获取对应table类, 然后调用table的函数select；
4. Table调用insert函数
相应table执行insert函数, 函数原理见 记录管理模块

4. 附加模块：

  • 域完整性约束, 建表时的check关键字
    由于系统在表中有关于域完整性约束的map, 所以在新加入一个条目的时候只需查找对应map条目中是否包含添加的项, 如果不包含则报错；

  • 外键约束
    外键约束由于系统对于每个表都维护了一个hashMap, 所以只需查找相应表中的hashMap即可判断是否违反外键约束；

  • 模糊匹配
    模糊匹配系统使用了c++11, 因为c++11中能够采用正则表达式, 系统对于每个输入的模糊匹配串都做了如下处理：将%替换为.*, 将_替换为., 这样就可以用待匹配串与每个条目相应属性的值做正则匹配.

  • 三个表以上的连接
    由于系统未能有效实现索引功能, 所以多表连接问题系统采用的是最原始的暴力搜索方法, 不过在搜索过程中系统还是做了一些优化, 使得每搜索一个正确条目所用的时间并不显得十分长（但是计算复杂度可知相应的时间消耗依旧是n^2级别的）

  • 聚集查询
    聚集查询系统默认待查询的属性的类型为int, 所以只需将表遍搜, 然后获取相应查询操作的结果即可.

  • 分组聚集查询
    分组聚集查询是在聚集查询的基础上用一个临时的map将不同类别的值分别存储, 从而达到分组的目的.

5. 数据库信息存储

以上所描述各用于维持数据库的类在程序结束时会依次写入本地文件中, 在下次程序运行时会先读入该部分数据, 完成各类的恢复工作.

运行方式

  • 主程序及makefile文件均在在/yacc/目录下, 利用该makefile即可进行编译, 生成主程序main；
  • 需要预先安装库：flex、bison、g++；
  • 主程序运行方式：直接运行主程序, 之后需要输入一个参数(0或1)：
    • 1表示不读入本地文件, 重新构建一个数据库
    • 0表示读入本地文件, 即恢复到上次程序结束时的状态
    • 在首次运行时需要输入1, 之后使用0参数即可

实验结果

实验结果表明, 此数据库文件系统可以很好地完成系统管理模块以及查询解析模块的相应工作, 并且能够很好地执行附加模块中域完整性约束、模糊匹配、聚集查询、分组聚集查询, 由于系统没有实现索引模块, 所以在外键约束和三个表以上的连接的功能上实现的效率不是很高, 因为采用的是暴力搜索的方法.

运行结果

1. 系统管理模块

1
2
3
4
5
6
7
8
9
10
11
12
CREATE DATABASE tempDB;
USE tempDB;
CREATE TABLE publisher(
id int(10) NOT NULL,
name varchar(25) NOT NULL,
state varchar(25) NOT NULL,
PRIMARY KEY(id)
);
SHOW TABLES;
DESC publisher;
DROP TABLE publisher;
DROP DATABASE tempDB;

结果

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
SQL: show table
+--------------------+
tables in tempDB
+--------------------+
publisher
+--------------------+

SQL:  desc table publisher
+-------------+-------------+------+-----+
| Field       | Type        | Null | Key |
+-------------+-------------+------+-----+
| id | INT(10) | NO  | PRI |
| name | VARCHAR(25) | NO  |     |
| state | VARCHAR(25) | NO  |     |
+-------------+-------------+------+-----+

2. 查询解析模块

SQL

1
2
INSERT INTO publisher VALUES (105001, 'American Technical Publisher', 'GA');
SELECT * FROM publisher WHERE id = 105001;

结果

1
2
3
id: 105001
name: American Technical Publisher
state: GA

SQL

1
INSERT INTO customer VALUES (300002, 'CHAD CABELLO', 'F');

结果

1
Primary Key Conflict!

SQL

1
INSERT INTO orders VALUES (304403, 200001, 'eight');

结果

1
INPUT ERROR

SQL

1
2
DELETE FROM orders WHERE quantity < 2;
SELECT * FROM orders WHERE quantity < 2;

结果

1
为空

SQL

1
2
UPDATE book SET title='Nine Times Nine' WHERE authors='David Ray';
SELECT title FROM book WHERE authors='David Ray';

结果

1
title: Nine Times Nine

SQL

1
UPDATE book SET copies='eight' WHERE title='A Walk Through the Fire';

结果

1
Update Input Error

SQL

1
SELECT * FROM publisher WHERE state='CA';

结果(选取部分)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
id: 104992
name: China Books &amp; Periodicals
state: CA
-------------------------
id: 104993
name: Dow Jones &amp; Company, Inc.
state: CA
-------------------------
id: 104994
name: Fox Chapel Publishing Company
state: CA
-------------------------
id: 104996
name: W.h. Smith And Son Publishers
state: CA
-------------------------
id: 104997
name: Transworld Publishers Limited
state: CA

SQL

1
SELECT title FROM book WHERE authors is null;

结果

1
title: Anyone Can Have a Happy

SQL

1
SELECT book.title, publisher.name, publisher.state FROM book, publisher WHERE book.publisher_id=publisher.id AND publisher.state='CA';

结果(选取部分)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
*** publisher ***
state: CA
*** publisher ***
name: Anglican Book Centre
*** book ***
title: Exortacao Aos Crocodilos
-------------------------
*** publisher ***
state: CA
*** publisher ***
name: Lyle Stuart Hardcover
*** book ***
title: The Rancher Takes a Wife
-------------------------
*** publisher ***
state: CA
*** publisher ***
name: Linstok Press, Incorporated
*** book ***
title: Flambards (Puffin Books)
-------------------------
*** publisher ***
state: CA
*** publisher ***
name: Bantam Doubleday Dell Pub
*** book ***
title: A Tall Man in a Low Land

3. 域完整性约束
SQL

1
2
INSERT INTO customer VALUES (307001, 'CHAD CABELLO', 'Male');
UPDATE publisher SET state='HI' WHERE name='New Video Group Inc';

结果

1
2
Check error
Check error

4. 外键约束
SQL

1
UPDATE book SET publisher_id='106001' WHERE title='A Voice Through a Cloud';

结果

1
Against publisher Key Restriction

5. 模糊匹配
SQL

1
SELECT name, gender FROM customer WHERE name = '_USTY%';

结果

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
*** customer ***
gender: F
*** customer ***
name: RUSTY PITTARD
-------------------------
*** customer ***
gender: F
*** customer ***
name: RUSTY FELT
-------------------------
*** customer ***
gender: M
*** customer ***
name: RUSTY SANNER
-------------------------
*** customer ***
gender: M
*** customer ***
name: DUSTY DEMELO
-------------------------
*** customer ***
gender: F
*** customer ***
name: RUSTY DACUS
-------------------------
*** customer ***
gender: F
*** customer ***
name: DUSTY LIRETTE
-------------------------
*** customer ***
gender: M
*** customer ***
name: DUSTY KUEHN

6. 三个表以上的连接
SQL

1
2
SELECT customer.name,book.title,orders.quantity FROM customer,book,orders
WHERE orders.customer_id=customer.id AND orders.book_id=book.id AND orders.quantity > 8;

因未加索引模块, 此部分运行时间过长, 不展示结果

7. 聚集查询

1
2
3
4
5
SELECT SUM(quantity) FROM orders WHERE customer_id=304403;
SELECT AVG(quantity) FROM orders WHERE customer_id=304403;
SELECT MAX(quantity) FROM orders WHERE customer_id=304403;
SELECT MIN(quantity) FROM orders WHERE customer_id=304403;
SELECT COUNT(*) FROM orders WHERE customer_id=304403;

结果

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
SQL:  select sum(quantity), from orders
+------------------------------+
SUM(quantity): 23
-------------------
SQL:  select avg(quantity), from orders
+------------------------------+
AVG(quantity): 4
-------------------
SQL:  select max(quantity), from orders
+------------------------------+
MAX(quantity): 9
-------------------
SQL:  select min(quantity), from orders
+------------------------------+
MIN(quantity): 2
-------------------
SQL:  select count(*), from orders
+------------------------------+
COUNT(*): 5

8. 分组聚焦查询

1
SELECT SUM(quantity) FROM orders GROUP BY customer_id;

结果(展示部分)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
306981: SUM(quantity): 11
306982: SUM(quantity): 7
306983: SUM(quantity): 15
306984: SUM(quantity): 17
306985: SUM(quantity): 27
306986: SUM(quantity): 31
306987: SUM(quantity): 3
306988: SUM(quantity): 20
306989: SUM(quantity): 30
306990: SUM(quantity): 17
306991: SUM(quantity): 39
306992: SUM(quantity): 24
306993: SUM(quantity): 8
306994: SUM(quantity): 39
306995: SUM(quantity): 6
306996: SUM(quantity): 32
306997: SUM(quantity): 13
306998: SUM(quantity): 28
306999: SUM(quantity): 11
307000: SUM(quantity): 39

参考文献

[1]. 数据库系统设计与原理 第二版 冯建华 周立柱 郝晓龙 编著

[2]. 数据库系统概念 Silberschatz Korth Sudarshan 著 杨冬青等 译

项目github链接：

dbclass project