Show HN: Prela – Purely Algebraic Relation Combinators 深度解读

背景

关系演算（Calculus of Relations）因其内在的魅力与美感，被阿尔弗雷德·塔斯基（Alfred Tarski）誉为“所有熟悉它的人都能从中获得智力愉悦”的源泉。基于这一理论基石，Prela 应运而生。

Prela 是一个基于塔斯基关系代数（Tarski's Algebra of Relations）的嵌入式查询语言。其设计目标是让查询语句更加简洁、清晰且高效。在实现层面，Prela 采用浅层嵌入（shallow embedding）的方式集成到宿主编程语言中，其操作符即为宿主语言中的普通函数。底层实现遵循延续传递风格（Continuation-Passing Style, CPS），从而能够编译为高效的列式执行计划。

需要注意的是，Prela 目前仍处于早期开发阶段的研究原型状态。语言设计和实现都在经历频繁且大幅度的变更。作者目前正专注于完善 Julia 语言的实现版本，同时在其他分支上也有实验性的 Rust 和 Zig 移植版本。

核心内容

Prela 的核心在于其独特的数据模型和查询表达方式，它通过“关系组合子”（Relation Combinators）来构建查询。

数据模型：一切皆为二元关系

要理解 Prela 的底层逻辑，必须首先明确其数据模型。在 Prela 中，所有数据都被视为二元关系（Binary Relation）。查询由一系列接受二元关系并产生二元关系的操作符组成。

我们可以将这种模型理解为一种极端的规范化形式：任何拥有 $k$ 列的表，都被“拆解”（shredded）为 $k$ 个二元表，每个表对应一列。

以简化查询 movie : (production_year > 2008) → title 为例：

• 在原始模式中，title 和 production_year 是同一张表的属性。
• 在 Prela 中，它们各自成为独立的二元关系，分别将电影 ID 映射到标题和生产年份。
• movie 本身也是一个特殊的二元关系，它对应于原始表的主键 ID 列，是一个关于 ID 的恒等关系（Identity Relation），即包含所有 (i, i) 对。
• 因此，每个“列表”可以被视为从主键到对应值的映射。

操作符与组合子

Prela 的操作符（如 >、in 等）在宿主语言（如 Julia）中是常规函数，但针对关系进行了重载。

1. 谓词过滤：

   • 例如 production_year > 2008 返回一个二元关系，它是 production_year 关系的子集，仅保留第二列（值列）大于 2008 的元组。
   • 其他谓词如 Info.type == "countries" 同理。

2. 限制组合子 (:)：

   • 符号 : 表示限制（Restriction），它接受两个关系，并将左操作数（LHS）的最后一列与右操作数（RHS）的第一列进行限制。
   • 本质上，这等同于左半连接（Left-Semi Join）。
   • 在示例 movie : (production_year > 2008) 中，movie 与过滤后的 production_year 进行半连接。由于 movie 是恒等关系，最终结果保留了生产年份大于 2008 的电影 ID。

3. 关系组合子 (→)：

   • 符号 → 表示关系组合（Relational Composition），是 Prela 和塔斯基关系代数的核心。
   • 可以将二元关系视为函数的泛化：类型 (X, Y) 的二元关系允许每个输入 X 对应多个输出 Y。
   • 组合操作 R → S 的逻辑是：首先对每个 x 应用 R 得到一系列 y，然后对每个 y 应用 S 得到一系列 z。
   • 在上述示例中，(movie : (production_year > 2008)) 的类型为 Movie -> Movie，title 的类型为 Movie -> String。它们的组合产生了 Movie -> String 类型的输出，即从符合条件的电影映射到其标题。
   • 直观理解：可以将电影视为一个 JSON 对象，→ 类似于字段访问，而 : 用于指定过滤器。

4. 连接与输出 (∧ 和 ×)：

   • ∧ 是 × 的别名，即乘积组合子（Product Combinator）。
   • 它接受类型为 X -> Y 和 X -> Z 的两个关系，并在 X 上进行连接，产生类型为 X -> (Y, Z) 的输出。
   • 作为连接（∧）：用于组合不同的谓词。例如 (production_year > 2008) ∧ (kind in ("movie", "episode")) 筛选出年份大于 2008 且类型为电影或剧集的记录。
   • 作为输出（×）：用于组合输出列。在完整示例中，title、data（评分）和 company（公司名称）通过 × 连接输出。
   • 注意：× 并不存在于原始的塔斯基代数中，因为它引入了元组（Tuples），打破了“一切皆二元”的原则。但在 Prela 中，元组被视为存储在列中的不透明值，所有操作符仍可正常处理包含元组的关系，这提供了极大的实用便利性。

查询示例解读

以 Join Order Benchmark 22a 为例，Prela 查询如下：

movie
: (info → (Info.type == "countries")
∧ (Info.info in ("Germany", "German", "USA", "American")))
∧ (keyword in ("murder", "murder-in-title", "blood", "violence"))
∧ (production_year > 2008)
∧ (kind in ("movie", "episode"))
→ title
× (data : (Data.data < "7.0") ∧ (Data.type == "rating") → Data.data)
× (company : (Company.note ≁ r"\(USA\)")
∧ (Company.note ~ r"\(200.*\)")
∧ (Company.country != "[us]")
∧ (Company.type == "production companies") → Company.name)

直观语义： 该查询寻找满足以下条件的电影：

• 产地为德国或美国；
• 包含谋杀、血腥、暴力等关键词（惊悚片）；
• 生产年份在 2008 年之后；
• 类型为电影或剧集。

对于每部符合条件的电影，输出：

• 标题；
• 评分（若低于 7.0）；
• 制作公司（若满足特定排除条件）。

与 SQL 的对比：

• 在 SQL 思维中，movie 位于 FROM 子句，: 和 → 之间的谓词位于 WHERE 子句，→ 之后的内容位于 SELECT 子句。
• Prela 的优势：不同于 SQL 将谓词和输出分离，Prela 允许自由交错谓词和输出，使查询结构更自然。
• 子查询处理：(data : ...) 和 (company : ...) 部分在 SQL 中需要特殊的子查询语法，而在 Prela 中只是普通的子表达式。
• 导航式连接：Prela 的连接通过查询结构以导航风格体现，而非显式的 JOIN 条件。

高级特性：宿主语言赋能

由于 Prela 直接嵌入宿主语言，它可以免费获得许多在其他查询语言中被视为高级特性的功能。以 TPCH q21