Cryville 元数据库框架（第二版）

背景

现如今的主流数据库大多使用表格的结构储存数据。通常，这样的一个表格里，一列相当于应用层面下某个数据结构的一个字段定义，一行相当于一个实例，一个单元格相当于实例上某个字段的值。一个表格中，每一列表示的属性及其数据类型是由开发者预定义的。一般情况下，用户的操作只会影响表格中行（记录）的增删及行内某列数据的更新，而不会影响到列本身的定义。这种结构符合直觉，毕竟表格中每一列的定义需要与程序中的数据结构的每个字段相对应，而只有开发者能够定义这些数据结构。这样的结构也使数据库能够拥有较高的性能。

在本团队（Cryville）开发的另一个项目中，我们遇到了数据结构会频繁变化，有时甚至可以由用户的操作修改的情况，即用户的操作可以在数据结构中更新、插入或删除字段。在主流数据库中，这样的操作一般由开发者完成，并且有两种方式：第一种是更新原有的表，直接新建一列，这种方式开销非常大，且十分耗时；第二种是新建一个主键与原表相同的表，这种方式会使一个数据结构对应多个表，会降低数据库的可维护性。

基于以上的背景，我们决定探索一种新的更加灵活的数据库结构。

设计思路

为了让用户的操作能够修改数据结构，我们在数据库层面假定一个新的概念，将应用层面中数据结构的字段本身和字段的值统一到这个概念中。由于实例的增删也是依据用户的操作完成的，我们也将实例本身统一到这个概念中。现在，字段、实例和实例中字段的值三者在数据库层面中处于同一地位。我们把这个概念称为“元子”。

元子之间需要有一种表示其相互关系的方式。参考字段、实例和实例中字段的值这三者，我们用一个三元组表示一个形如“A 的 B 是 C”的关系。对于形如“A 是 B”这样看似由两个元子就能构成的关系，我们引入一个特殊的、语义为“存在”的元子，将这类型的关系表示为“A 的存在是 B”。

关于字段的数据类型，上层系统（即数据库实现或应用层系统）自行决定是否对数据进行类型处理。

正式定义

下文的“CMDF”指代本文档所描述的数据库框架。

术语

在本文档中，对于“必须”“不得”“应当”“不应”“可以”这些关键词，当且仅当以粗体出现时，需要按照 BCP 14 [RFC2119] [RFC8174] 中的描述解读。

数据结构

元子

元子（meton）是数据库中的一个抽象数据对象。

元子对和关系

三个元子 $A$、$B$ 和 $C$ 间可以组成一个称为正关系（forward relation）的三元组，记作 $\left(A,B,C\right)$，语义为“$A$ 的 $B$ 是 $C$”。此时元子 $B$ 和元子 $C$ 构成一个正元子对（forward meton pair），记作 $\langle B,C\rangle$。

元子对集

Student {
	
}

Name {
	
}
Student_Lime {
	Name: Name_Lime;
}
Name_Lime {
	~Name: Student_Lime;
}

系词元子

一个数据库中，必须存在且仅存在一个元子 $e$，使得正关系 $\left(e,e,e\right)$ 存在。称这个元子 $e$ 为系词元子（copula meton），其语义为“存在”。

_ {
	_: _;
	~_: _;
}

_ {
	_: _;
	~_: _;
	~_: Student;
	~_: Name;
}
Student {
	_: _;
	~_: Student_Lime;
}
Student_Lime {
	_: Student;
	Name: Name_Lime;
}
Name {
	_: _;
	~_: Name_Lime;
}
Name_Lime {
	_: Name;
	~Name: Student_Lime;
}

元子标识

每个元子有一个固定长度的元子标识（meton identifier），用于索引元子。

摘要

元子中可以容纳一段可变长度的、代表实际数据的二进制数据，称为摘要（summary）。

Name_Lime {
	"Lime";
	~Name: Student_Lime;
}

业务

一个 CMDF 实现必须支持读取数据库，但是可以选择是否支持写入数据库。对于这两种实现，本文档指定不同的业务需求。

数据库层

一个 CMDF 实现必须实现以下业务：

• [C.D.1] 以只读的模式连接到一个已有的数据库。
• [C.D.2] 关闭一个数据库连接。

一个支持写入的 CMDF 实现必须实现以下业务：

• [W.D.1] 建立一个新的数据库。
  • 必须同时向新建的数据库内添加系词元子^[W.M.1]。
• [W.D.2] 以读写的模式连接到一个已有的数据库。
  • 如果该数据库已有一个读写模式的数据库连接，则该业务必须失败。

一个 CMDF 实现可以实现以下业务：

• [C.D.O1] 删除一个已有的数据库。
  • 如果该数据库已有一个数据库连接，则该业务必须失败。

下文中所有对数据库的操作，都是通过数据库连接进行的。

元子层

令 $n$ 为当前数据库中元子的总数。

一个 CMDF 实现必须实现以下业务：

• [C.M.1] 在 $O\left(1\right)$ 的时间内获取数据库的系词元子。
• [C.M.2] 给定元子标识，在 $O\left(\log n\right)$ 的时间内在数据库中索引到对应的元子。
  • 若不存在符合条件的元子，则该业务必须失败或者返回索引尝试结束时最后访问的元子（如果有）。
• [C.M.3] 获取给定元子的元子标识。
• [C.M.4] 获取给定元子的摘要。

一个支持写入的 CMDF 实现必须实现以下业务：

• [W.M.1] 给定元子标识和摘要，在 $O\left(\log n\right)$ 的时间内向数据库中添加一个元子。
  • 应当同时往该元子的元子对集中添加至少一个键元为系词元子的正元子对^[W.S.1]。
  • 若已存在给定元子标识的元子，则该业务必须失败。
• [W.M.2] 给定元子标识，在 $O\left(\log n\right)$ 的时间内从数据库中移除对应的元子。
  • 必须同时移除该元子的元子对集上所有的元子对^[W.S.2]。
  • 若不存在给定元子标识的元子，则该业务必须失败。

一个 CMDF 实现应当实现以下业务：

• [C.M.R1] 在 $O\left(\log n\right)$ 的时间内获取数据库中元子的数量。

元子对集层

令 $n$ 为元子的元子对集中元子对的总数。

一个 CMDF 实现必须实现以下业务：

• [C.S.1] 枚举给定元子的元子对集中所有的元子对。
• [C.S.2] 给定元子和键元，在 $O\left(\log n\right)$ 的时间内获取一个从元子的元子对集中枚举所有给定键元的元子对的枚举器。
  • 该业务不得失败。若不存在符合条件的元子对，则该业务必须返回一个空的枚举器。
• [C.S.3] 给定元子和元子对，在 $O\left(\log n\right)$ 的时间内在元子的元子对集中索引到元子对。
  • 若不存在符合条件的元子对，则该业务必须失败或者返回索引尝试结束时最后访问的元子对（如果有）。

一个支持写入的 CMDF 实现必须实现以下业务：

• [W.S.1] 向一个元子的元子对集中，在 $O\left(\log n\right)$ 的时间内，添加给定正（逆）元子对。
  • 必须同时向该元子对值元的元子对集中，在 $O\left(\log n\right)$ 的时间内，添加对应的逆（正）元子对。
  • 若元子对集中已存在给定的正（逆）元子对，则该业务必须失败。
• [W.S.2] 从一个元子的元子对集中，在 $O\left(\log n\right)$ 的时间内，移除给定正（逆）元子对。
  • 必须同时从该元子对值元的元子对集中，在 $O\left(\log n\right)$ 的时间内，移除对应的逆（正）元子对。
  • 若元子对集中不存在给定的正（逆）元子对，则该业务必须失败。

一个 CMDF 实现应当实现以下业务：

• [C.S.R1] 在 $O\left(\log n\right)$ 的时间内获取给定元子的元子对集中元子对的数量。
• [C.S.R2] 给定元子和键元，在 $O\left(\log n\right)$ 的时间内获取元子的元子对集中给定键元的元子对的数量。

元子对层

一个 CMDF 实现必须实现以下业务：

• [C.P.1] 在 $O\left(1\right)$ 的时间内，获取给定元子对集的键元的元子标识。
• [C.P.2] 在 $O\left(1\right)$ 的时间内，获取给定元子对集的值元的元子标识。

一个 CMDF 实现应当实现以下业务：

• [C.P.R1] 在 $O\left(1\right)$ 的时间内，获取给定元子对集的键元。
• [C.P.R2] 在 $O\left(1\right)$ 的时间内，获取给定元子对集的值元。