TrivialDB - 一个简单的SQL引擎

TrivialDB是一个简单的数据库管理系统,我们实现了大部分常见的SQL语句和类型。同时支持多表连接、复杂表达式运算、多主键约束、外键约束、CHECK约束、UNIQUE和DEFAULT约束、聚集查询、利用B+树索引的查询优化,同时,我们支持任意长度的VARCHAR类型。

项目地址是 https://github.com/miskcoo/TrivialDB,这是这学期一门课程的大作业。

编译及运行

你需要有支持C++11特性的编译器,以及Bison和Flex两个库。本项目通过CMake来构建,在根目录运行

进行编译选项的设置,之后运行

进行项目的编译,编译后的可执行程序在build/trivial_db目录下。

编译后可以选择在testcase目录下运行python3 run_test.py运行测试程序。

系统功能

数据类型

数据库支持的基本类型有:

  • 整型(INT)
  • 浮点型(FLOAT)
  • 字符串型(VARCHAR)
  • 日期型(DATE),日期格式YYYY-MM-dd

日期类型的字面值和字符串相同,在实现中如果必要可以转换为字符串。

SQL语句

我们支持的SQL语句一共有如下几种

  • 插入语句:INSERT INTO ... VALUES ...
  • 删除语句:DELETE FROM ... WHERE ...
  • 查询语句:SELECT ... FROM ... WHERE ...
  • 更新语句:UPDATE ... SET ... WHERE ...
  • 创建数据库:CREATE DATABASE ...
  • 删除数据库:DROP DATABASE ...
  • 切换数据库:USE ...
  • 显示数据库信息:SHOW DATABASE ...
  • 创建表:CREATE TABLE ...
  • 删除表:DROP TABLE ...
  • 显示表信息:SHOW TABLE ...
  • 创建索引:CREATE INDEX ...
  • 删除索引:DROP INDEX ...

复杂表达式处理

表达式大致可以分为两种:算术表达式和条件表达式。由于采用Bison进行解析,可以支持任意深度嵌套的复杂表达式。我们所支持的基本运算主要如下

  • 四则运算,针对整数和浮点数进行。
  • 比较运算符,即<=, <, =, >, >=, <>。
  • 模糊匹配运算符,即LIKE,其实现采用C++11的正则表达式库。
  • 范围匹配运算符,即IN,可以在表的CHECK约束中以及WHERE子句中使用。
  • 空值判定运算符,即IS NULL和IS NOT NULL两种。
  • 逻辑运算,包含NOT、AND和OR三种。

以下是一些复杂表达式运算的例子

聚集查询

我们实现了五种聚集查询函数COUNT、SUM、AVG、MIN和MAX。其中COUNT不支持DISTINCT关键字。例如

属性完整性约束

我们支持多种属性完整性约束,分别是

  • 主键约束。一个表可以有多个列联合起来作为主键,只有在所有主键都相同时才认为两条记录有冲突,即这种情况下主键是一个元组。
  • 外键约束,每个域都可以有外键约束,引用另外一个表的主键。
  • UNIQUE约束,该约束限制某一列的值不能重复。
  • NOT NULL约束,该约束限制某一列不能有空值。
  • DEFAULT约束,该约束可以在INSERT语句不指定值是给某列赋予一个默认值。
  • CHECK约束,该约束可以对表中元素的值添加条件表达式的检查。

下面是一个简单的例子,注意如果在多个列都指定了PRIMARY KEY,那么就认为主键是一个元组,而不是有多个主键。例如Infos表的主键为(PersonID, InfoID)。

多表连接查询

在SELECT语句中,我们支持任意多表的连接操作,例如

并且,对于多个表的连接中形如A.Col1 = B.Col2的条件,那么如果这两个列的某一个拥有索引,会利用索引进行查询优化。例如如下查询就可以优化

具体的优化方法以及何种查询可以优化见文档中"查询优化"部分。

表别名

我们在多表连接查询时支持通过别名(alias)的方式对一个表进行连接,例如

Read More

[c++11]Sequenced before 规则和求值顺序

任何 C++ 操作符的求值顺序都是 unspecified(后面提到的除外),unspecified 也就是标准没有指定,可以由编译器决定,这包括在函数调用表达式中函数参数的求值顺序以及任何表达式的子表达式的求值顺序。编译器可以按照任意顺序将它们求值,对于相同的表达式,编译器也可以选择不同的顺序将它们求值。

在 C++ 中,没有什么从左到右或者从右到左的求值顺序,只有操作符从左到右和从右到左的结合性。就比如说表达式f1() + f2() + f3() 会通过加法操作符从左到右的结合性被解析为 (f1() + f2()) + f3(),但是对 f3 的调用可能会最先执行,然后是 f1,最后是 f2,因为它们的求值顺序是 unspecified。

C++ 是一个注重效率的语言,标准不指定一些表达式的求值顺序就是为了让编译器能做尽可能多的优化,即便要牺牲掉例如 i=i++ 这样表达式的正确性(据说在 Java 中就没这些问题,这个表达式的结果是确定的)。

(more…)

Read More

[c++11]Lambda 表达式

在 C++11 中新增了一个特性 —— Lambda 表达式,它提供了一个简便的方法来创建一个函数对象。

至于函数对象,它的用途通常是在调用标准库算法的时候作为核心部分传入的,比如说 std::sort 默认是从小到大排序,然而如果我们要从大到小排序在 C++ 98/03 中有三种方法

第一种是给 std::sort 一个函数,第二种是给一个函数对象,第三种是用标准库 functional 里面已经定义好了的函数对象

你可能会说,第三种多快多方便,但是,如果比较算法一变得复杂起来,如果标准库没有提供这样的函数对象,那你就不得不选择前两种方法了,肯定,很多人会选择第一种。

但是…… 如果你的比较函数要依赖于一个外部的,比较函数调用之时才确定的,那么第一种就无能为力了,考虑下面这个例子

这种写法无疑会消耗很多时间,增加很多代码量,于是 Lambda 表达式便在 C++11 标准中诞生了。

Lambda 的语法是这样的,首先以 [] 打头,之后是和普通函数一样的参数列表,然后是函数体,如果有返回值(假定为 T),那么在参数列表后加上 -> T,它语法大概就写成这样,最简单的 lambda 表达式就是 []{} 它什么都不做

[ capture ] ( argument-list ) -> return-type { statement }

  • [ capture ]:捕获列表。它总是出现在 lambda 函数开头,并且不能省略,事实上,它是 lambda 函数的引出符。捕获列表可以捕捉上下文中的变量以供 lambda 函数内部使用,具体用法请看下文。
  • ( argument-list ):参数列表。和普通函数参数列表一样,如果没够参数可以连同括号一起省略。
  • mutable:默认情况下 lambda 函数总是 const 函数,也就是说捕获的变量不可修改。mutable 可以取消其常量性,若有这个修饰符,参数列表不可省略。
  • return-type:函数返回类型。详见下文
  • { statement }:函数体。

(more…)

Read More

[c++11]编译期间判断两个类型的实例是否可以应用等于运算符

标题十分地长的样子、还是把以前写在其它地方的东西都搬到这个地方来了

我主要是想有两个类型分别是 A 和 B 的变量 a、b,能否在在编译期间获得一个 bool 常量,表示是否拥有 a == b 这样的运算

然后我们来看看测试的结果

(more…)

Read More