SG-Database

SG-Database一种轻量、易扩展的关系式数据库系统。

其主要优势是，可以简单方便的向其中添加新的数据类型及对应索引。比如当我们想要在数据库中存储一些地图上的点，为了对其进行高效索引，需要建立类似KD-Tree等的索引结构，为了在传统的SQL数据库中实现这种索引，需要对数据库系统进行performance tuning，编程负担较重。而我们的数据库系统提供了更加方便易用的扩展结构，用户可以直接继承数据类型基类Basic实现自己的数据类型，并添加对应索引。添加的组件可以无开销地直接对接数据库，简单方便的实现对数据库系统功能的拓展。

在此基础上，我们实现了传统关系式数据库物理层面大部分功能和优化，如变更日志、IO优化、热区缓存、视图和表抽取、元组批操作等。在高层，我们放弃使用SQL语言，而是采用javascript语言和逻辑规则引擎联合进行对数据操作进行描述。使用javascript可以完成许多SQL语言很难编写或完成不了的数据操作，而且更符合大部分程序员的直觉。规则引擎用于描述WHERE条件，直接与索引模块对接，使得用户编写的索引结构可以直接接入查询功能当中。

由于只用了四天事件，还有一些功能我们没有完成。如数据操作语言(javascript)与数据库的对接、触发器（因为这与数据库查询语言相关）、与连接操作/多表查询有关的一些支持，以及并发控制（这十分重要，我们要多花一些时间进行研究设计）。

动态类型模块

需求

数据库需要存储不同类型的数据。因此数据库系统需要对数据类型提供支持。并要允许用户简单方便的定义自己的新数据类型，无开销地与数据库其它模块实现自动对接。

分析

不同数据类型具有不同数据成员，所以必须使用不同的类来存储。但列与表的对象都需要同存同取，不能对每个类型都建立一个对应的列/表类。因此需要引入动态类型特性。

设计

我们选择使用继承多态实现动态类型。首先定义数据类型基类（Basic类），其它类型均继承数据类型基类实现。在列类（col类）中，存储数据的对象为基类容器（vector<Basic*>），即将所有数据对象都向上转型为基类指针统一存储。

基类中定义虚函数getType，这个函数返回这个动态类型对象的类型。因此每个子类都需要对该虚函数进行实现。这样在向上转型之后依然可以获取数据的实际类型，以便在使用时进行逆变。

在col对象构造时，需要指定类型（因为关系式数据库中同一列存储的数据类型一定是相同的），当取用其中的数据时，按构造时指定的列类型进行转换。添加元素时也会进行类型检查，如添加的数据类型与列类型不符，将会抛出异常。

为了方便实现动态类型的配套操作，实现typeHelper静态空间，提供关于数据对象拷贝、判等、反序列化等功能。这样，需要使用这些功能时直接用基类指针作为参数调用函数即可，不需要手动转换再根据不同类型分别处理。相应地，在用户添加新数据类型时，也要在这些函数中添加新类型的处理case。

作为例子，我们实现了整型、浮点、字符串、布尔四种实值类型。

文档

Basic类

动态类型基类，直接创建该类型对象视为null数据

公有成员

virtual TYPE getType()

获取数据对象实际类型

virtual string toStr()

序列化这个数据对象，转换为字符串

日志模块

需求

记录对用户数据库进行的修改（增删改）操作。基于这些记录，可以在合适的时候将这些修改统一写入硬盘（修改先立刻在内存中实现，再在合适的时候统一在硬盘上的文件实现），降低IO代价。

分析

为了降低IO代价，必然要进行定点增量式写入。因此需要将每一次对表的修改（增删改）作为一条日志记录，

设计

首先定义日志记录类（record类），其需要记录三种对表的修改模式：插入、删除和修改（元组）。

三种修改所需的信息不同：插入仅需要记录插入的元组，不关心位置（元组是无序的）；删除只需要记录删除的元组（相对当前表的）位置（下标）；修改需要记录需修改元组的位置（下标）和修改内容（使用vector<Basic*>记录，长度为元组长度，不修改的条目可以使用占位符占位）。因此，三种不同的修改可以使用三种不同的构造函数，在构造函数中记录修改类型（增/删/改），便于在实现修改时，通过修改类型进入不同的分支。

将这些修改写入硬盘时，按日志队列顺序从头到尾实现修改即可。所有修改都已实现到硬盘后，日志队列将被清空。

文档

record类

日志记录类

私有成员

void setAddTarget(vector<Basic*> addTarget)

设置修改的目标元组。

由于日志记录是在调用table修改（增删改）方法时进行同步创建，因此vector<Basic*>中的Basic对象来源于col，col持有所有权，有可能在之后被释放。如果被释放后再用这个记录对硬盘进行操作将造成文件错误。因此需要将vector<Basic*>中每个元素依次复制，复制后的对象由本类持有所有权。

公有成员

int opSub=-1

操作元组的下标（相对于创建该记录时刻表的下标）

recType type

操作类型，分为增（add）删（del）改（mod）

vector<Basic*> targetTuple

增加与修改的目标元组（要插入什么/要改成什么，修改可使用占位符）

record(vector<Basic*> addTarget)

“增”类型日志记录的构造函数

record(int opSub)

“删”类型日志记录的构造函数

record(int opSub, vector<Basic*> modTarget)

“改”类型日志记录的构造函数

record(const record &r)

拷贝构造函数

~record()

析构函数，释放持有所有权的targetTuple成员中Basic对象

具体说明

• 当record.type=ADD的时候，record.targetTuple里面所存储的是新添加的元组，targetTuple[0]就是这个元素第一列的值，targetTuple[1]就是第二个，以此类推。
• 当record.type=MOD的时候，record.opSub存储的是要修改目标行的元组（一行对应一个元组）。record.targetTuple里面存储的是这个元组该进行怎样的修改，注意如果里面元素getType结果是Placeholder代表这一列不进行修改（例如targetTuple[1].getType=="Placeholder"，这就表示第二列不变），当getType结果为其他的值时才代替表进行更改（里面存的就是改完的实际值）。
• 当record.type=DEL的时候，opSub中所存储的就是要删除元素的所在行（下标）。

table类中的日志成员

list<record> allRecord

存储上次硬盘写入后所有修改的日志记录。调用table的增删改方法时进行同步追加；调用table的硬盘文件更新方法，实现其中所有修改后对其进行清空。

视图与表抽取模块

需求

快速的使用一个表中的部分元组构造视图或复制一张新表。

视图是从一个基本表中导出的虚拟的表。在系统的数据字典中仅存放了视图的定义，不存放视图对应的数据。这些表的数据存放在数据库中。那些用于产生视图的表叫做该视图的基表。

视图看上去非常像数据库的物理表，对它的操作同任何其它的表一样。当通过视图修改数据时，实际上是在改变基表中的数据；相反地，基表数据的改变也会自动反映在由基表产生的视图中。

分析

这是传统数据库的常规功能。表抽取直接创建新的表和列对象，将选择的元素复制进去即可。视图需要建立一个对基本表的映射，这样才能使得对视图的修改通过映射作用到基本表上，使二者同步。

设计

视图并不是一个很好的设计，因为保持数据绑定在很多情况下并不容易做到。但我们仍在不损害运行效率和软件架构的情况下对其的基本功能进行实现。

我们所支持的是单表视图，因为多表视图需要连接条件才能保持，而在对视图进行修改时，动态正/反向解析连接条件以找到所修改元组在基本表中的位置，是非常低效的。在正常的数据库使用中也应该尽量减少这种操作。因此多表视图在本数据库中不做支持。

首先定义视图类（view类），其需要存储其所映射到的基本表，和视图中每个元组在基本表中对应的位置（下标）。

这种存储方式意味着基本表出现任何改变数据下标的修改时，视图都可能不再可用（访问不到正确的元素）。如果对基本表和视图进行双向绑定可以解决这种问题，但这会连带降低基本表的操作效率，并破坏软件上下层结构。

可以采取的方法是事件路由，即在一个上层模块中记录所有的“视图-表”绑定，所有的增删改操作都必须经过这个模块实际实施，当对一个基本表进行删除操作时，在删除完成后，这个操作会被发送到这个基本表所派生的所有视图中，如果这个操作对视图中元素有影响，那么基本表会进行对应修正。具体来说，如果一个视图中的元组在基本表中被删除，那么视图也会删除该元素，并将其之后元素的映射值全部减1. 如果一个在基本表中被删除的元素下标落在某个视图映射到的区间内，那么对于视图的映射表，从它右侧距离最近的的元素开始，其后所有元素的映射值全部减1.

文档

视图

view类

视图类

私有成员

table *t

这个视图所映射到的基本表

vector<int> allSub

视图中的元组依次对应的基本表中元组下标

void delElm(int opSub)

给定一个视图中元组下标，将其在allSub中删除，其后的元素映射值全部-1（这个视图所对应元组在基本表中被删除后使用）

公有成员

string ID

视图名

view(string ID, table* t, vector<int> allSub)

构造函数

bool delElmDir(int opSub)

在删除了一个基本表元组后由事件路由调用，参数为所删除元组基本表中的下标。如果这个基本表元组在该视图中，那么视图也会删除该元素，并将其之后元素的映射值全部减1. 如果一个在基本表中被删除的元素下标落在某个视图映射到的区间内，那么对于视图的映射表，从它右侧距离最近的的元素开始，其后所有元素的映射值全部减1.

void mod(int opSub, vector<Basic*> tuple)

修改视图中的元素，并作用到基本表

void del(int opSub)

删除视图中的元素，并作用到基本表

void del(vector<int> allOpSub)

批量删除视图中的元素（会自动处理删除产生的下标偏移），并作用到基本表

表抽取

col类中的表抽取方法

col* genNewCol(vector<int> subList)

将this列中下标所指元组复制形成一个新列，并返回

col类中的表抽取方法

vector<int> findCol(vector<string> colID)

给定一些列名，查找对应列下标

table* genNewTable(vector<int> colSubList, vector<int> tupSubList)

给定一些列的下标和元组下标，将其复制形成一个新表，并返回

列/表模块

需求

设计数据结构存储数据库中的表

分析

关系式数据库表中的不同列具有不同的特性，如不同类型、不同约束、不同触发器等。因此需要用一个单独的结构来表示。这些结构的对象再堆叠起来，就形成了表。

设计

定义列类（col类），在构造函数中指定该类的数据类型和基本约束。并可以通过成员函数添加触发器和其它约束（因为目前数据查询语言尚未与数据库系统完成对接，触发器和约束暂时不被支持）。当向列中添加数据时，会自动检查添加的数据类型是否与列的数据类型相同，如果不同将抛出异常。

定义表类（table类），表类需对列、索引和日志均进行支持。表中的所有列在构造时作为构造函数参数传入，转移所有权到表对象，其后自动对所有列建立索引（默认为遍历索引，即遍历查询），用户可以自行对某一列构造其它索引，并通过替换索引的成员函数替换掉原先的索引。日志记录的功能挂载在表类的增/删/改方法中，当操作完成后，自动创建日志记录追加到日志中。具体参照“日志模块”章节。

对于增/删/改操作，从表的层次讲，其操作的单元是元组。在函数内部，会将这些对元组的操作转换为对对应列的操作，并调用列的增/删/改函数，进行实际实施。

另外，表类还需支持查询功能。这里的查询指的是根据条件对表中元素进行筛选，即“单表查询”。多表查询通过单表查询结果进行表提取，再进行多次查询即可完成，之后我们会对这一功能进行进一步封装。表示条件需要使用逻辑规则引擎中的规则表达式（ruleExp）对象，每个对象表达对一列数据的条件，查询过程需要传入对所有列的条件（无条件的列传nullptr），然后对每一列，依次用该列对应条件调用该列索引进行查询，将最后的结果取交集。

文档

col类

列类

私有成员

const TYPE type

列中数据的数据类型

vector<Basic*> allData

列中的数据

公有成员

string ID

列名

col(TYPE type,string ID)

构造函数

col(const col &c)

拷贝构造函数

const vector<Basic*>& getAllData()

获取数据容器引用（只读），使得用户可以自行浏览、提取数据

TYPE getType()

获取列中数据的数据类型

void pushData(Basic* v)

向列中添加数据，会自动进行类型检查

col* genNewCol(vector<int> subList)

选择列中的一些数据，创建一个新列（会拷贝数据）

bool mod(int opSub,Basic* v)

修改列中的某个元素。如果传入的v为占位符或与当前位置数据相同，那么不会进行修改返回false。否则返回true

void del(int opSub)

删除列中的某个元素

void del(vector<int> allOpSub)

批量删除列中的元素。内部会自动处理删除产生的下标偏移

~col()

析构函数，释放所有数据的空间

table类

表类

私有成员

vector<col*> allCol

表中的所有列

vector<index*> allIndex

每一列对应的索引

list<record> allRecord

从上次硬盘写入到目前的所有日志记录

公有成员

string ID

表名

table(string ID, vector<col*>allCol)

构造函数

table(const table& t)

拷贝构造函数（不会拷贝索引，还是会重新建立遍历索引）

void changeIndex(int sub, index* ind)

变更某一列的索引

const vector<col*>& getAllCol()

获取列容器引用（只读），使得用户可以自行浏览、提取数据

static table* loadFile(string path)

从文件中反序列化，加载一张表

void saveFile(string path)

将表序列化，保存到文件中

void updateFile(string path)

将目前日志中描述的变更实现到文件中

table* genNewTable(vector<int> subList)

选择表中的一些列，创建一个新列（会拷贝数据）

void add(vector<Basic*> tuple)

向表中添加一个元组

void mod(int opSub, vector<Basic*> tuple)

修改表中的某个元组（tuple代表修改后元组，可使用占位符）。修改调用列的mod方法实现，因此可以明确哪一列修改确实进行，哪个一列并不需要修改。这个结果作用于两种可选的日志策略：如开启logStrategy宏，那么修改日志中的vector<Basic*>对象仅记录实际进行修改的列元素，其它元素为占位符；如果不开启，那么修改日志中的vector<Basic*>对象记录修改后的元组。两种不同的日志策略需要两种不同的updateFile（硬盘文件增量修改）算法支持，目前我们的updateFile支持的是不开启logStrategy的策略

void del(int opSub)

删除表中的一个元组

void del(vector<int> allOpSub)

批量删除列中的元素。内部会自动处理删除产生的下标偏移

vector<int> find(vector<ruleExp> allExp)

筛选表中符合条件的元组，返回这些元组的下标。表示条件需要使用逻辑规则引擎中的规则表达式（ruleExp）对象，每个对象表达对一列数据的条件，查询过程需要传入对所有列的条件（无条件的列传nullptr），然后对每一列，依次用该列对应条件调用该列索引进行查询，将最后的结果取交集。

~table()

析构函数，释放所有列和索引的空间

索引模块

需求

根据不同数据类型、不同约束的类产生的不同特点。数据库需要各种不同的索引加速查询。因此数据库系统需要对索引提供支持。并要允许用户简单方便的定义自己的新索引结构，无开销地与数据库其它模块实现自动对接。

分析

不同索引有着不同的数据结构，如B树与二叉查找树一定是两个不同的类型存储。所以不同的索引也必须使用不同的类来存储（将索引使用的实际数据结构作为索引类的成员）。但列与表的对象都需要同存同取，不能对每个类型都建立一个对应的列/表类。因此仍需要使用继承多态。

设计

首先定义索引基类（index类），其它索引均继承基类实现。在表类（table类）中，存储索引的对象为基类容器（vector<index*>），即将所有索引对象都向上转型为基类指针统一存储。

在本数据库系统的设计中，所谓“索引”不一定要求有独立的查找数据结构（如B树等）。因为每一次查找均会调用索引对象进行，所以即使是顺序遍历查找，也是一种“索引”。但如果是具有独立查找数据结构的索引，当数据改变（进行增删改）时，其对应的数据结构需要更新，而像顺序查找这类“索引”，就不需要更新。因此有必要对二者进行区分。所以在基类中，设置了一个bool型flag，标记该索引类是否需要在每次进行增删改时同步对其进行更新。如果flag为true，则在表对象的增/删/改方法被调用时，也会自动调用索引的增/删/改虚函数，使得二者同步（因此这种情况下这三个虚函数必须有效实现）。而如果flag为false，索引类中的增/删/改虚函数就不会被调用，保持基类的“调用即抛出异常”实现即可。

用户可以继承索引基类创建自己的索引。如果用户的索引具有独立的查找数据结构，那么需要在构造函数中建立这个数据结构、置flag为true，并实现维护该结构的增/删/改虚函数。无论是否具有独立查找结构，必须实现查找虚函数，该函数传入一个条件（由规则表达式对象表示），返回查找结果。

对于传入的规则条件，查找函数可能有必要进行一些解释和转化，如NOT-GART（NOT为根节点，GART为其子节点）代表小于等于，AND-GART/EQU（AND的两个子节点为GART和EQU）代表大于等于等。有许多表达方式是等价的，如果一些逻辑条件对应着查找算法的某条分支，那么就有必要从传入的规则表达式中确定用户到底描述的是哪种条件——如果是单层的表达式，这很简单。但如果是上文所说的嵌套表达式，就相对困难（之后我们会对表达式化简提供一些封装）。如果对复杂的规则不想进行化简（要求用户必须传入简单的），或者这个索引根本不支持某种条件，那么可以在检测出这种情况时抛出“index does not support this exp”异常。如果查找算法不依赖规则进行路径选择，只需要代入数据判断真值，那么可以直接对规则对象调用eval函数，传入你要代入的数据即可。

作为例子，我们实现了遍历和B+树两种索引。前者针对任意列，后者只针对唯一性约束的数值（Int/Float）列。

文档

index类

索引基类

保护成员

bool supportMod=false

标记索引是否维护独立查找数据结构的flag

公有成员

virtual vector<int> find(ruleExp rule)=0

查找函数，参数为查找条件

col* c

本索引针对的列对象（不拷贝，与表同步变化）

index(col* c) : c(c)

构造函数

bool isSupportMod()

返回flag值

virtual void add(Basic* v)

添加一个数据（实现中应对查找数据结构做同步修改）

virtual void mod(int opSub, Basic* v)

修改一个数据（实现中应对查找数据结构做同步修改）

virtual void del(int opSub)

删除一个数据（实现中应对查找数据结构做同步修改）

virtual ~index()

析构函数，用于释放查找数据结构

逻辑规则引擎模块

需求

设计逻辑规则引擎用于描述数据查找（筛选）规则。

分析

本数据库系统不使用SQL作为查询语言，对数据的操作由javascript脚本结合操作库来完成。但对于数据的查找（筛选）规则，无法直接使用javascript程序描述。因为不同的条件可能对应不同查找算法（索引）中的不同执行路径，这个规则的表示起的是一个指示作用，表达“想要什么”而不是“要怎么做”（具体怎么做由查找算法实现）。所以必须使用一个可拆分、可组合的数据结构，用户可以对其进行组合，表达自己想要的查询；查找算法对其进行拆分，找到对应的算法执行路径。

设计

我们采用类似表达式树的结构。每个规则表达式对象有两个子节点。因为在单表查询中，条件都是诸如AGE>18之类，一侧是一个常量，另一侧用列中的数据替代。因此在构造表达式对象时，常量子节点需要被指定。常量子节点有两种类型可选，一是像上文所说为一个实际的数据对象，也可以依然为一个表达式对象，以实现表达式的嵌套。一些运算（如NOT）只需要一个操作数，就用常量子节点作为这个操作数。

在进行多表查询时，常量子节点需要依次被表2中的数据替代。所以我们提供了一个成员函数用于修改这个表达式对象的常量子节点。

一些时候，查找算法并不仅仅要知道表达式对象所要表达的条件，还需要将数据代入表达式进行实际求值。因此需要提供eval方法，eval传入一个数据作为变量子节点的取值（查询（筛选）问题中，所有子树变量子节点的取值都是相同的，如对AGE列的筛选条件AGE>18 AND AGE<60）。其实现就是递归求值。

只要运算的结果是逻辑值，就被称为逻辑操作。因此规则引擎支持的运算不应当仅限于AND、OR、NOT等，也应允许用户拓展。在我们的设计中，表达式基类不限定操作数的数据类型，所以仅支持EQU（判断相等）运算（因为这个运算也不要求操作数类型）。其它类型特化的运算都由子类进行实现（因此也要求eval为虚函数）。

我们注意到，手动构造表达式树结构比较繁琐。因此之后会实现javascript逻辑表达式（字符串）向表达式树的转换模块。

作为例子，我们实现了数值型的逻辑表达式类用于进行<、>运算；布尔型的逻辑表达式类用于进行AND、OR、NOT运算。

文档

ruleExp类

规则表达式基类

保护成员

ruleOp op

该表达式进行的运算

Basic* operand2B=nullptr

常量子节点（数据）

ruleExp* operand2E=nullptr

常量子节点（嵌套表达式）

int nestingLevel=0

嵌套层数

bool operandIsBasic()

设定的常量子节点是否为数据

公有成员

ruleExp(ruleOp op, Basic* operand)

构造函数。以数据作为常量子节点

ruleExp(ruleOp op, ruleExp* operand)

构造函数。以其它规则表达式作为常量子节点

void resetOperand(Basic* operand)

修改常量子节点（仅支持修改/修改为数据）

ruleOp getOp()

获取这个表达式执行的运算

int getNestingLevel()

获取嵌套层数

Basic* getOperand2B()

获取常量子节点（数据）

ruleExp* getOperand2E()

获取常量子节点（嵌套子树）

virtual bool eval(Basic* operand1B)

表达式求值。传入一个数据作为变量子节点的取值（查询（筛选）问题中，所有子树变量子节点的取值都是相同的，如对AGE列的筛选条件AGE>18 AND AGE<60）

virtual ~ruleExp()

析构函数，用于释放常量子节点（数据也持有所有权）