Relation algebra is not relational algebra

关系代数（Relation algebra）不是关系代数（Relational algebra）

Relation algebra ≠ relational algebra Lots of people confuse relation algebra with relational algebra, including Wikipedia (until today) and one of my favorite database influencers, Jamie Brandon. I don’t blame them, because the names only differ by 2 letters, and I believe not even Ted Codd knew about relation algebra; otherwise I doubt he would have named his thing “relational algebra”. 关系代数（Relation algebra）≠ 关系代数（Relational algebra）。许多人会将两者混淆，包括维基百科（直到今天为止）以及我最喜欢的数据库领域意见领袖之一 Jamie Brandon。我并不怪他们，因为这两个名称仅有两个字母之差。我相信即便是 Ted Codd 本人可能都不知道“关系代数（Relation algebra）”的存在；否则，我很怀疑他是否还会将自己的理论命名为“关系代数（Relational algebra）”。

If you use a database, you’ve probably heard of the relational algebra, which is the foundation for, well, relational databases. Codd introduced the algebra in his 1970 paper A relational model of data for large shared data banks and gave it the name “relational algebra” 2 years later. For theory fans, his seminal result (now known as Codd’s theorem) says that relational algebra is equivalent to the so-called domain independent relational calculus, which is essentially a well-behaved fragment of first-order logic queries. 如果你使用数据库，你可能听说过“关系代数（Relational algebra）”，它是关系数据库的基础。Codd 在他 1970 年的论文《大型共享数据库的关系模型》中引入了这种代数，并在两年后将其命名为“关系代数（Relational algebra）”。对于理论爱好者来说，他那项开创性的成果（现称为 Codd 定理）指出，关系代数等价于所谓的“域无关关系演算（domain independent relational calculus）”，这本质上是一阶逻辑查询中表现良好的一部分。

Far fewer people know about relation algebra outside of logic and pure math. There, it is defined as an algebraic structure abstractly by a set of axioms, and the name comes from how a concrete algebra over binary relations can be conveniently modeled by it. An interesting counterpart to Codd’s theorem is that relation algebra is equivalent to $\text{FOL}^3$, which restricts first-order logic to use at most 3 different variables (but quantifiers can be nested arbitrarily deep). However, it can be extended to match the expressive power of FOL with a fork operator. 在逻辑学和纯数学领域之外，很少有人了解“关系代数（Relation algebra）”。在那里，它被定义为一组公理下的抽象代数结构，其名称源于它如何方便地对二元关系上的具体代数进行建模。与 Codd 定理有趣对应的是，关系代数等价于 $\text{FOL}^3$，即将一阶逻辑限制为最多使用 3 个不同变量（但量词可以任意深度嵌套）。不过，通过引入分叉算子（fork operator），它可以被扩展以匹配一阶逻辑（FOL）的表达能力。

OK, so relational algebra is a CS thing, and relation algebra is a math thing? Not so fast! It turns out relation algebra has been quietly finding applications in computer science as well. One major piece of software built on it is the Alloy analyzer which calls it “relational logic” (which was incorrectly redirected to the page for relational algebra until I fixed it just now…). Alloy is a descendant of the Z notation by the late and great Jean-Raymond Abrial. 好吧，所以“关系代数（Relational algebra）”是计算机科学的东西，而“关系代数（Relation algebra）”是数学的东西？别急！事实证明，关系代数（Relation algebra）也一直在计算机科学中悄悄地寻找应用场景。基于它构建的一个重要软件是 Alloy 分析器，它将其称为“关系逻辑（relational logic）”（直到我刚才修复之前，它被错误地重定向到了关系代数（Relational algebra）的页面……）。Alloy 是已故伟大的 Jean-Raymond Abrial 所创 Z 符号语言的后继者。

Let’s try it again: so relational algebra is a DB thing, and relation algebra is for math and formal methods? Still not. Over the decades, there has been a small but dedicated group of people led by Dirk Van Gucht applying the ideas of relation algebra to database theory and systems. We provide some pointers to the literature in our recent paper on the Prela query language - which brings me to my final point: Prela appears to be the first query language since Van Gucht’s IUGQL that is based on relation algebra. 再试一次：所以“关系代数（Relational algebra）”是数据库的东西，而“关系代数（Relation algebra）”是用于数学和形式化方法的？依然不对。几十年来，以 Dirk Van Gucht 为首的一小群专注的研究者一直致力于将关系代数（Relation algebra）的思想应用于数据库理论和系统。我们在最近关于 Prela 查询语言的论文中提供了一些文献指引——这引出了我的最后一点：Prela 似乎是自 Van Gucht 的 IUGQL 以来，第一个基于关系代数（Relation algebra）的查询语言。

I believe relation algebra really deserves to be known by more people. Tarski said it best: “the calculus of relations has an intrinsic charm and beauty which makes it a source of intellectual delight to all who become acquainted with it”. Finally, I’ve started calling it “Tarski’s Algebra of Relations”, or TAR for short, in hope to avoid confusion in the future. That’s right, Tarski calls relation algebra by yet another name, “the calculus of relations”, and that is again not the same as the relational calculus in database theory… 我相信关系代数（Relation algebra）确实值得被更多人了解。Tarski 说得最好：“关系演算具有一种内在的魅力和美感，使它成为所有接触过它的人的智力愉悦之源”。最后，我开始称其为“Tarski 关系代数（Tarski’s Algebra of Relations）”，简称 TAR，希望能避免未来的混淆。没错，Tarski 用了另一个名字来称呼关系代数，即“关系演算（the calculus of relations）”，而这又与数据库理论中的“关系演算（relational calculus）”不是同一个东西……