打开关系数据库的黑匣子

关系数据库很棒。 它们不仅在存储数据方面非常有效，而且还具有优美的基础数学理论。 但是，尤其是当人们通过ORM使用数据库时，它看起来像一个黑匣子。 打开黑匣子是掌握主题的绝佳方法，因此，我决定深入研究并自己构建一个最小但功能齐全的关系数据库系统。 在这篇文章中，我将与您分享我的旅程。

我的目的不是展示SQL的幕后工作方式，而是展示关系数据库背后的基本原理。 即使希望更具体，也有几种SQL方言，例如PostgreSQL，MySQL等，它们之间可能会有很大的差异。

在深入研究实现之前，我们应该对基础数学对象有深入的了解。 那么，让我们谈谈真正的关系是什么！

（如果您希望以交互方式进行操作并使用代码，则可以在GitHub上的存储库中找到！）

关系

"数学家就像法国人：无论您对他们说什么，他们都会翻译成他们自己的语言，并且随之而来的是完全不同的东西。" —约翰·沃尔夫冈·冯·歌德

为了理解关系数据库，首先，我们将定义什么是关系。 从数学上讲，关系R超过集合

是其笛卡尔积的子集：

举个例子，<运算符是一个关系。 您可以将其视为所有自然数元组的集合，其中元组中的第一个元素小于第二个。 这实际上是在数学中定义<的方式。

一个更具体的示例将有助于掌握此抽象定义。 假设我们正在谈论公司中的员工。 每个员工都有一个唯一的ID，姓名，职位和薪水：

在此模型中，雇员是四个维度的向量：

员工关系就是其中的一组。 使用关系数据库术语，关系对应于一个表，并且关系的元素是该表中的记录。 在下文中，我将这些术语互换使用。

在Python中，我们将使用特殊字典和带有一组记录的表来对记录进行建模。 我们可以使用更复杂的东西（例如，熊猫数据框），但是这些将是完美的。 请注意，使用集时，不允许重复记录。

由于默认情况下字典是不可散列的，因此无法将它们插入集合中。 为了避免这种情况，我为Record类添加了一个哈希方法，该方法返回由dict获得的元组的哈希。

这样做很危险，因此我们应该小心。 因为字典是可变的，所以它们的"哈希"（如上所述）可以更改。 因此，如果将其放入集合中并更改其值之一，则哈希值将发生变化，并且由于Python中的集合在幕后使用哈希值，这可能会使事情变得混乱。 因此，为避免这种情况，我已通过覆盖__setitem__特殊方法来明确禁止修改记录。

为了处理更多数据，我们还将为任务表添加以下几列：id，employee_id，completed。 employee_id将描述ID为id的任务属于哪个员工，完成的只是一个布尔值，指示其状态。

我们的表将是记录集，我们现在手动创建它们。

既然我们已经奠定了适当的基础，是时候来看一下使关系数据库起作用的原因了：操作。

关系代数：关系运算

如果我们没有办法检索和构造数据库中的信息，那么关系数据库将几乎无用。 通过在关系上应用运算符可以实现此任务。 关系代数是这些运算定义的数学结构。 确切地说，关系代数的元素是函数，其输入和输出是关系。

如果这听起来对您来说太抽象了，我们来看一些具体的例子！

选择

选择运算是最基本的运算符之一，它根据某些条件过滤关系。 表示为

其中C表示条件。 在我们的示例数据库中，条件可以是"员工的薪水超过60000"。 可以将其视为一个获取记录并返回一个布尔值的函数，该布尔值指示是否已满足条件。

如果我们为雇员表应用条件"薪水大于60000"，这就是我们得到的。

投影

select运算符用于选择我们表中的记录。 但是，我们可能希望对列也应用过滤器，以删除不必要的信息。 这可以通过投影运算符完成。 用表示

其中S表示应保留的列列表。 这在我们的设置中也很容易实现。

当我们将employees表投影到id和name列时，就会发生这种情况。

改名

重命名列通常非常有用。 例如，我们两个表都有一个id列，这可能会引起一些歧义，因此需要重命名。

叉积

这是事情开始变得有趣的地方。 关系数据库的真正优势在于，您可以在多个表中组合信息，并可以通过查询这些组合表来回答复杂的问题。 最简单的方法是使用叉积，叉积以所有可能的方式将记录合并在一起。 我将在实现之前展示一个示例，以确保它清晰无误。

在这里，我们看到冲突的列名可能成为问题。 在取叉积之前，每个列的每个表都以表名作为前缀。

叉积运算符用表示

您可能已经观察到跨产品组合信息而不考虑逻辑一致性。 跨产品表中的某些记录显示了一个雇员和属于另一个雇员的任务。 我们将在稍后使用联接时解决此问题。

联合

因此，我们已经看到，使用叉积，我们可以"横向"组合表。 很自然地期望相同的"垂直"，就像过滤行（选择）和列（项目）的情况一样。 这可以用联合运算符完成。

严格来讲，当表具有不同的列时，此运算符实际上没有任何意义。 但是，有一个解决方案：可以用空值（例如None）填充缺少的列。

区别

我们的最后一个算子是差，它再次类似于集合理论的差。 它只是从另一个表中消除了一个表的行。

因为实现中的表是集合，所以我们可以简单地使用内置方法。

您可能会注意到交叉点被遗漏了。 这是因为交集可以用

要么

difference(left, difference(left, right))

在代码中。

相交运算符的情况不是唯一的。 实际上，所有相关运算符都可以作为前六个运算符的组合获得，我们将在后面看到。

关系代数方面的SQL查询

现在我们有了所有这些看似抽象的操作，我们可以开始了解SQL查询如何转换为关系代数。 假设我们要查询所有年薪超过60k USD的雇员的姓名。 在SQL中，这看起来像

SELECT name FROM employees WHERE salary > 60000

在我们的实现中，这等效于

temp_table = select(employees, [lambda x: x['salary'] > 60000])result = project(temp_table, ['name'])

因此，我们可以看到我们的工具功能强大，足以表达这些类型的查询。 但是，最整洁的事情仍然摆在我们面前。 为了能够回答有关我们数据的更复杂的问题（例如，那些没有完成任务的员工的平均工资是多少），我们需要能够智能地合并表格之间的信息。 这些都是通过联接完成的。

Join

在关系代数中有几种将表组合在一起的方法。 到目前为止，我们已经看到了一个：叉积，即使逻辑上不一致，也可以将所有记录组合在一起。 但是，可以将表进行水平组合，以使结果表包含有意义的信息。 同样，有几种方法可以做到这一点。 我们将从最基本的一个开始：theta join。

Theta加盟

Theta join运算符只是叉积和选择运算的组合。 用表示

其中θ表示选择的条件。 例如，在employee ['id']和task ['employee_id']匹配的条件下，雇员和任务的theta联接如下所示。

如您所见，这解决了跨产品问题，即给定记录中的任务不一定属于同一记录中的员工。

外连接

在某些情况下，即使在另一个表中没有逻辑上对应的元素，在连接过程中保留一些信息也是有用的。 这就是左/右/全外部联接运算符的作用。 我们将不做详细介绍，但是这些运算符会将theta联接中缺少的左/右/两个表中的行合并在一起。

查询是关系代数的元素

我们已经看到，大多数查询，甚至联接，都只能用六个运算符来表示：

· 选择

· 项目

· 改名

· 叉积

· 联盟

· 区别

要查看更复杂的查询，让我们介绍第三个表，其中包含Dunder Mifflin Scranton的客户。 每个客户都有一个ID，一个姓名和一个contact_id，即联系员工的ID。

现在考虑以下查询："其联系人至少具有一项未完成任务的客户的名字是什么？"

为了回答这个问题，我们必须合并来自所有三个表的信息。 思考我们需要采取的步骤是很有用的。 在这里，我们要

· 通过将employee和tasks表连接在一起，找到任务不完整的雇员，

· 将结果表连接到客户表以匹配客户名称以联系员工，

· 通过投影到"客户名称"列来选择客户名称。

在代码中，这类似于以下内容。

无论多么复杂，每个查询都可以表示为一个称为表达式树的图形。

> Expression tree for the query "what are the names of the clients whose contacts have at least one

实际上，这不是执行此查询的唯一可能方法，还有其他解决方案。 例如，我们可以立即为所有三个表创建叉积，并使用一次选择过滤掉所需的记录。 使用SQL时，引擎会通过估算给定执行计划的所需成本并选择最适合您的方案来尝试优化查询。

从关系代数到SQL

关系代数只是冰山一角。 它为我们提供了代表查询的构造块，但是，它没有为我们提供寻找如何最佳表示查询的工具。 在幕后，SQL实际上使用关系演算，它本质上是一种基于关系代数的声明性语言。 这意味着您仅描述所需的内容，而不是所需的内容。 后面的部分由发动机确定。

我们缺少诸如集合之类的核心SQL功能，即将关系映射到元素的函数（例如平均函数）。 因此，要建立一个功能齐全的关系数据库还有很长的路要走。 但是，已经奠定了基础，并明确了实现之路。

资源资源

在搜寻过程中，我有两个出色的资源可以帮助我建立关系数据库：

· 珍妮弗·维多姆（Jennifer Widom）的数据库MOOC

· 关系数据库理论David Maier

(本文翻译自Tivadar Danka的文章《How to Build a Relational Database From Scratch》，参考：)