范畴图数据库统一实现

Categorical Data Structures for Technical Computing

技术计算中的范畴数据结构

https://arxiv.org/abs/2106.04703

许多数学对象可表示为从有限呈现范畴 C 到集合范畴 S e t
的函子。例如，图（graphs）即为从具有两条平行箭头的范畴到 S e t
的函子。这类函子非正式地被称为 C -集（ C -sets）。本文提出并实现了一种对 C -集的扩展：允许数据带有固定类型属性，如顶点带标签的图或边带实值权重的图。我们将此类结构称为 acsets（attributed C -sets 的缩写，即“带属性的 C -集”）。该结构源自代数数据库领域的前期工作，是对图与数据框（data frames）的统一推广，并可涵盖更复杂的类图对象，例如带速率常数的接线图（wiring diagrams）与Petri网。本文首先发展了acsets的数学理论，继而描述了其在Julia编程语言中的通用实现；该实现借助语言的高级特性，在性能上可媲美专用数据结构。

1 引言

从事实践的数据科学家常常表示，他们至少将一半的时间用于数据清洗和数据管道管理，而非模型拟合。数据准备本身固有的困难，又因数据存储方式的多样性而进一步加剧：数据可能存在于 SQL 数据库、数据框（data frames）、图结构中，抑或散见于整个数据科学生态系统中的各类更专门的数据结构中。尽管每种数据结构可能各有优势，但它们均附带一套需重新学习的编程接口；此类结构的泛滥割裂了整个生态系统，并给互操作性带来了挑战。

针对这一问题的一种解决方案是围绕单一数据结构进行集中化：即数据框（data frame）。数据框是一种面向列的数据表；与矩阵不同，其各列可具有不同数据类型。Python 生态系统中广受欢迎的 pandas 包[16]即属此类；R 语言内置了 data.frame 类型[20]及其变体 tibble[18]；在 Julia 中，许多不同包实现了 Tables.jl 的通用接口，这在一定程度上改善了互操作性。

然而，所有这些包背后所依赖的，是同一种抽象数据模型，以及该模型固有的局限性。尤为关键的是，数据框模型无法有效表达实体之间的关系——这一概念在 SQL 中体现为外键（FOREIGN KEY）。当然，人们可以按某种临时约定维护一组相互引用的数据框，但此类关系并未被形式化，因而难以通过高层抽象进行便捷、鲁棒的操作。一个典型例子是：数据框无法恰当地刻画图的结构，后者需两个相互关联的数据表——一个用于顶点，一个用于边。

一种广为人知、可同时涵盖数据框与图的抽象是关系型数据库。关系型数据库具有模式（schema），用于描述一组关系及其之间的外键关联。然而，关系型数据库往往作为庞杂的单体系统存在，难以与通用编程语言集成。SQL 等关系查询语言，以及 Prolog、Datalog 等逻辑编程语言，均受制于所有独立领域专用语言（DSL）共有的“阿喀琉斯之踵”：一旦超出该 DSL 能力范围，便只能彻底脱离整个系统。而实践中，跳出 DSL 往往是必要的，因为即便表达能力最强的查询语言亦有其局限。因此，“多少逻辑应放在查询中、多少应放在数据库外的后处理中”便成为一个长期悬而未决的问题——即数据处理领域的“两种语言问题”（two-language problem）。此外，数据库通常被设计为全局可变状态，使其难以作为局部上下文中的一次性对象自然使用。例如，图虽可建模为数据库，但若某程序在某一时刻需同时维护成千上万乃至百万个处于不同作用域的图实例，则显然不希望为此启动百万个 SQL 数据库实例。

然而，从本质上讲，“由模式关联的一组表及其索引”这一构想，并无理由一定要求单体系统、持久化存储或全局作用域。关系数据库最早的文献已具备一套独立于具体实现惯例的数学模型，其基础是关系代数与一阶逻辑[8]。不久之后，又提出了函数式数据模型（functional data model），其基本构造单元为实体与函数；在该模型中，函数居于核心地位，而关系则被函数构成的“跨度”（spans of functions）——即所谓“制表跨度”（tabulating spans）——所替代。Johnson 等人曾以范畴论语言，借助“概形”（sketches）对该数据模型进行了形式化表述[12]。更近一步，Spivak 意识到，函数式数据模型可优雅地重构为：从一个有限呈现范畴到集合与函数范畴的一个函子[27]。随后，针对该函子模型如何容纳数据属性的扩展工作相继展开[28, 25]。

本文提出了一种高效的内存驻留式（in-memory）范畴数据库实现。根据所采用的模式，所得数据结构可表现为数据框、图，或大量此前因过于小众而缺乏专用实现的其他结构。借助 Julia 编程语言的高级特性，我们的实现性能可与前沿图库相媲美——尽管我们的“图库”实为一个更通用系统的轻量封装。

我们将此类数据结构称为 acsets（“attributed C-sets”的缩写，即“带属性的 C-集”）。我们以直接、实用的方式定义 acsets，并表明其可被重新表述为范畴代数中已被深入研究的对象；基于此数学图像，我们推导出了用于组合多个 acsets、查询 acsets 以及在不同模式的 acsets 间转换的高层操作。例如，我们可通用地计算固定模式下 acsets 的有限极限与余极限。但需强调的是，就大多数使用目的而言，使用者并不需要具备范畴论知识。

我们开发 acsets 的动因最初来自 Catlab 及 AlgebraicJulia 生态系统[19]中其他软件包的需求。在实现应用范畴论的各类构件过程中，我们意识到，所需诸多数据结构（至少在部分程度上）均可被 C-集（即余预层，copresheaves）所涵盖，并可通用地实现；但该抽象并不完全令人满意，因其未能涵盖“属性”（attributes）——即具有固定外部意义的数据（如实数、文本字符串等）。这最终引导我们走向 acsets 的形式体系，并促成了更系统化的软件实现。

贡献本文主要贡献在于：在通用编程语言中，以高效、灵活的方式实现了内存驻留的范畴数据库数据结构，支持应用范畴论中的关键构造，包括带装饰或带结构的余跨度（decorated/structured cospans）。我们的实现充分利用了 Julia 语言的元编程（metaprogramming）特性，在性能上可媲美高度专业化的前沿图库，同时具备远为广泛的通用性。据我们所知，这种在范畴数据结构中同时实现高性能与高通用性的组合尚属首次。

在更偏理论的层面，我们进一步探索了范畴数据库的设计空间，提出了一种 Spivak 等人函子数据模型的变体，其复杂度介于文献[28]与[25]之间，并推导了其基本数学性质。

结构安排本文第 2 节首先对 acsets 给出非形式化的概述，面向计算机科学家与软件工程师等普通读者；第 3 节回顾 C-集的数学理论（acsets 为其扩展），熟悉相关数学的读者可跳过该节；第 4 节发展带属性 C-集的理论，证明 acsets 是 C-集范畴中的切片对象（slice objects），并由此导出若干推论；最后，第 5 节讨论 acsets 的具体实现，并将其与 Julia 中前沿图库 LightGraphs.jl[4]进行基准测试，为“acsets 可同时实现通用性与高性能”这一主张提供实证支持。

2 带属性 C-集（Attributed C-sets）的使用
本节旨在直观传达对 acsets 的理解。我们首先说明两种常见数据结构——数据框与图——如何作为 acsets 的特例；为展示该形式体系的广泛适用性，我们还将简要介绍若干虽较罕见却颇具实用价值的 acsets 实例。

2.1 数据框与图
如引言所述，数据框是对“我们应如何存储数据”这一问题的流行解答。表 1 展示了一个仅含两列（a 与 b）的微型数据框。

在本文中，我们将数据框视为一组一维数组（称为“列”），所有列具有相同长度。数据框中的一行，即为所有列在某一整数索引处的取值组合。用户可通过列名访问单个列，也可通过索引访问单个行。为支持高效的数据访问与迭代，数据框通常以列优先方式存储（即作为列的列表），而非行优先方式（即作为行的列表）。

我们将 acsets 构建为数据框的扩展，因此默认 Julia 中已有数据框的实现可用。在这一假想的实现中，

正如引言中所述，我们最终希望将图视为两个相互关联的数据框。然而，在转向这一策略之前，我们先考察图的典型实现方式。在 Julia 中实现图的最简单方法之一，或许是采用边列表（edge list）数据结构：

边列表的一种常见变体是邻接表（adjacency list）。它存储源映射与目标映射的原像集——借用数据库的术语来说，即为每个顶点建立索引，分别指向以其为起点（出边）或终点（入边）的边。

2.2 迈向带属性的 C-集（Attributed C-sets）

图与数据框之间存在一个本质区别：我们可以对图的顶点进行置换（重标号），只要相应地更新源映射（source）与目标映射（target），图本身所表达的结构含义便保持不变；然而，对于数据框，若将其中所有数值 6.0 替换为 2.0，则数据的含义将发生根本性改变。

这一区别对理解 acsets 至关重要，因此有必要引入一些非正式术语加以阐明：我们将图中所存储的连接性信息称为组合数据（combinatorial data），而将数据框中存储的信息称为属性数据（attribute data）。此类区分在数据库理论中是标准做法。例如，Johnson 等人的 EA 概念（EA sketches）明确区分了实体（entities）与属性（attributes）[12]，其中“实体”即我们所称的组合数据。

在数据科学与科学计算中，我们经常遇到同时包含组合数据与属性数据的数据集。例如，假设需表示一个道路网络：我们可以使用一个图结构，其中每个顶点（道路交叉口）关联一对坐标 ( x , y )
，每条边（道路）则附带一个长度属性——该长度可能因其弯曲或坡度而不同于端点间的欧氏距离。对此类数据结构的一种直接实现方式可能是：

条目 1 和 2 构成了道路地图的组合数据，而条目 3 和 4 则构成了其属性数据。
在我们的实现中，组合数据始终以整数表示；而属性数据则通过类型参数表达，可由任意 Julia 类型填充。

需注意，最后一条（条目 5，即索引）与其他条目性质不同：索引是为了提升效率而引入的，即使省略它们，数据结构在逻辑上依然包含相同的信息。正因如此，当我们形式化地描述签名（schema）时，将省略索引信息；相反，索引可在编译时根据预期的工作负载动态选定——仅对那些频繁查询的键才应建立索引。

在 Catlab 的实现中，我们通过撰写模式（schema）的形式化规范，并将其传入一个函数，由该函数程序化地生成对应 acset 的数据结构，从而自动生成类似于 OrganizedRoadMap 的数据类型：

尽管 acsets 也提供了高层操作函数，但底层的访问器（accessors）与修改器（mutators）始终可用；并且如第 5 节的基准测试所示，它们运行迅速，因此用户不会受限于高层接口所暴露的功能。结合 Julia 语言能够使手写循环达到与“向量化”代码同等效率的能力，用户可轻松编写高性能算法——即便这些算法超出了核心库的预设范围。

2.3 超越图：接线图及其他类图结构
在计算机科学中，常出现与图类似、但具备额外或不同结构的对象。若为每种图的变体都手工定制数据结构，将导致软件复杂性呈爆炸式增长；然而，若缺乏定制数据结构，又无法高效利用其额外的数学结构。本节将表明，众多类图结构均可统一于 acset 这一概念之下，因而可通过统一、通用的软件接口进行操作。

以下三个示例均配有插图；因图幅较大，不便嵌入正文。建议读者先翻阅后续几页展开的图示，再返回正文阅读具体说明。

示例 1：图 1 展示了四种不同类型的带端口图（port graphs），以及它们模式（schemas）的生成元。这些端口图在两个维度上有所不同：无类型与有类型，以及圆形（无向）与有向。在有类型端口图中，相连端口与连线的类型必须一致。这一要求由以下等式表达：

对于圆形端口图：

这两个等式表明图 1b 和 1d 中的某些三角形可交换。无类型端口图则无此限制。在圆形端口图中，方框仅具有单一类型的端口 Port，但连线是有方向的。而在有向端口图中，端口被划分为输入端口（InPort）和输出端口（OutPort），且连线必须从输入端口指向输出端口。按照惯例，输入端口画在左侧，输出端口画在右侧，从而可根据相邻端口推断连线的方向。

示例 2：一个细粒度 Petri 网由物种（species）、变迁（transitions）、到变迁的输入（inputs to transitions）以及从变迁的输出（outputs from transitions）组成 [13]。我们在图 2 中可视化 Petri 网，按照传统，物种用圆圈表示，变迁用方块表示。Petri 网常通过增加一组“标记”（tokens）来扩展，每个物种对应一组标记。这可通过在模式中添加一个新对象 Tok 并引入从标记到物种的映射来实现——这种用映射表示多对一关系的技巧，在使用关系代数建模数据时十分常见。请注意，细粒度 Petri 网的模式与有向二分图（directed bipartite graph）的模式是同构的，我们将在示例 6 中再次讨论这一点。

示例 3：图 3 绘制了有类型与无类型的无向接线图（undirected wiring diagrams）的模式。粗略地说，无向接线图代表具有外边界的系统的组合模式。想象将一个完整的接线图放置于其中一个内圆内部，然后擦除该内圆以获得一个新的接线图。这一操作使无向接线图成为一个“操作元”（operad），该构造在文献 [23] 中得到了精确化定义。

我们希望上述示例已足以让读者信服：将类图数据结构表达为 acsets，既自然又具普适性。本文余下部分将主要聚焦于 acsets 的数学理论与具体实现；因此，若读者主要关注该技术的实际应用，可直接前往 Catlab 中的相关软件实现。

3 C-集回顾
在转向带属性 C-集（attributed C-sets）的理论之前，我们先回顾 C-集的概念——亦称范畴 C C 上的余预层（copresheaf）。在本节及下一节中，我们假定读者已熟悉范畴论的基本概念，即范畴（categories）、函子（functors）与自然变换（natural transformations）。

3.1 定义与示例

我们关注极限（limits）与余极限（colimits），是因为 C-集的应用通常涉及可通过极限或余极限表达的操作；我们将在后文看到，能够计算推出（pushouts）对于组合带结构的余跨度（structured cospans）至关重要。上述逐点公式（pointwise formula）导出了一种通用于函子范畴中计算极限与余极限的通用算法，我们已将其应用于有限 C-集的实现中。

3.3 查询与数据迁移

4 带属性 C-集的理论

在第 2 节中，我们对比了数据集中可包含的两类信息。第一类是组合数据（combinatorial data），它能被 C-集很好地建模。然而，第二类——属性数据（attribute data）——却不能被恰当地建模，因为 C-集的同构类会抽象掉集合中元素的实际内容，仅保留元素之间的关系。

我们对 acset 的定义与文献中其他带属性的范畴数据库定义密切相关［28, 25］。定义 7 是 Schultz 等人所提出的“代数数据库”［25］的一种更简洁但表达能力稍弱的变体：它用指向离散范畴的拟函子，替换了原定义中指向多类代数理论（multisorted algebraic theories）且保持积结构的代数拟函子（algebraic profunctors）。这意味着我们的数据模型不包含对属性数据的操作（例如数值加法、字符串拼接等内置代数运算）；当然，这类操作仍可在普通的 Julia 代码中实现。

另一方面，我们的定义比 Spivak 与 Wisnesky 的定义［28］略为丰富：我们引入了属性类型（attribute type）的概念，而非将每个属性视为拥有各自独立的数据类型。这一补充在我们的实现中十分便利——属性类型直接对应生成的 Julia 数据类型中的类型参数（参见第 5 节）。

综上所述，我们所提出的 acset 概念在复杂度上介于文献［28］与［25］之间。

Spivak 与 Wisnesky 在文献［28, Proposition 9.1.2］中也陈述了类似的结果，尽管由于形式化方式的差异，其证明更为直接。

事实上，了解“acset 的范畴是预层范畴的一个切片范畴”这一点很有用，因为这类范畴具有许多理想的性质。由于预层范畴是初等拓扑斯（elementary toposes），而拓扑斯的切片范畴仍是拓扑斯（“拓扑斯基本定理”［17, Theorem 17.4］），因此 acset 的范畴本身也是一个拓扑斯。特别地，所有有限极限与余极限均存在，并可通过已知公式计算。此外，在 上的 acset 范畴之间还存在一个几何态射（geometric morphism）。因此，从抽象意义上讲，acset 范畴的重要性质由上述构造决定并已被充分认知；主要创新在于实现这些性质所带来的诸多实用应用。第 5 节的大部分内容将致力于展示预层范畴切片范畴的性质如何转化为设计与实现软件的实际能力。

4.2 带属性 C-集构造的函子性

此外，如下图所示，“带权集合”（weighted sets）的模式到“带权图”（weighted graphs）模式的包含关系，诱导出一个从带权图到带权集合的态射，该态射将一个带权图映射为其带权边集合（weighted set of edges）。

4.3 带属性 C-集的结构化余跨度

acset 常与结构化余跨度（structured cospans）结合使用，后者是由 Baez 与 Courser ［2］提出的一种用于开放系统的形式化方法，建立在 Fong 的装饰余跨度（decorated cospans）［9］基础之上。结构化余跨度的范畴是对余跨度范畴的推广，下面我们回顾其定义。

4.4 极限与余极限

5 带属性 C-集的实现

本节概述带属性 C-集实现中更值得关注的若干方面，尤其是那些充分利用了 Julia 或 Catlab 独特特性的部分。

5.1 AttributedCSet 数据结构

5.2 代码生成

若每次对 acset 执行底层操作时，都需在运行时解析其模式的类型级描述，则由此产生的开销将使 acset 无法与手工编写的专用数据结构在性能上竞争。幸运的是，Julia 语言支持一种名为生成函数（generated functions）的有用元编程机制，可避免此类运行时惩罚。

与宏（macro）类似，生成函数可执行任意 Julia 代码以生成一段 Julia 表达式，随后对该表达式求值；不同之处在于，宏作用于其参数的语法结构，而生成函数则作用于其参数的类型，并返回一个针对这些特定类型定制的函数体表达式。由于 acset 的类型已完整刻画了其结构，该类型便足以生成针对每一操作的、高度特化且高效的代码。首次调用后，这些特化代码会被缓存，后续调用时无需重复生成。

在诸如 StaticArrays.jl 等对静态尺寸向量的完整实现中，性能提升的很大一部分源于静态向量被分配在栈上而非堆上；而循环展开则使得通用地支持任意尺寸的静态向量也能在性能上媲美那些为特定尺寸（如 2D 或 3D）硬编码优化的代码。例如，欧几里得几何相关软件包从此无需再为性能考虑而对二维、三维等情形单独特化处理。

类似地，如下基准测试所示，生成函数使得 acset 的通用实现足以与针对特定 acset 手工特化的实现相竞争。这不仅消除了大量领域专用库的必要性，更打开了通向此前因开发成本过高而被放弃的专用数据结构的大门。特别是，它摆脱了诸如 MetaGraphs.jl 等包为支持任意用户自定义数据属性而被迫依赖字典（dictionaries）的困境；取而代之，用户可直接创建一个恰好包含当前应用所需字段的、全新的专用数据结构。

几乎所有对 acset 的基本操作均以生成函数实现。得益于对索引的支持（即同时存储正向与逆像映射以实现快速查找），这种实现方式所节省的程序员工作量远超表面所见。诸如添加/删除元素、修改态射取值等操作与索引的交互十分微妙；而通过用生成函数编写访问器与修改器，这些簿记工作得以一次性彻底解决。

5.3 底层操作

下面我们展示如何利用 acset 的底层接口编写高性能算法。作为示例，我们实现图上的深度优先搜索（DFS）。以下代码以顶点 s 为起点，对图 g 进行深度优先遍历，并返回一个父顶点数组（parent），其索引为顶点编号。

在上述代码中，对 incident 的调用返回从给定顶点 v 出发的所有出边列表——该操作利用了 acset 为态射 src 所维护的索引；随后对 subpart 的调用则给出所有由 v 指向的邻接顶点列表。这种数据访问模式在循环中被反复使用。相比之下，仅提供高层、基于查询访问接口的关系型数据库，在处理图算法（包括诸多高度迭代或递归的搜索算法）时往往表现不佳［7］。

5.4 范畴操作

acset 的一个用途是为第 4.3 节所述的结构化余跨度（structured cospans）提供其中的“结构”。为支持这一应用，我们必须能够计算推出（pushouts）。本节简要概述 acset 推出的计算方法，以余等化子（coequalizers）这一特例进行说明。

根据第 4.4 节，acset 的余极限是逐点（pointwise）计算的。因此，在讨论如何在 acset 范畴中计算余等化子之前，我们首先回顾如何在有限集合范畴中计算余等化子（参见［24, §4.6］）。为便于讨论，我们采用以下数据结构来表示形如 { 1 , … , n }
的有限集及其间的函数——需注意，此处代码远比 Catlab 中的实际实现更简单、泛化程度更低。

例如，图的连通分量可以通过对源映射与目标映射 V → E
的余等化子（coequalizer）提取得到。要计算 acset 态射的余等化子，首先需要一个用于表示 acset 态射的 Julia 数据结构——即在 FinSet 中为模式中的每个对象配备一个命名元组（named tuple）。接着，给定一对平行的 acset 态射，我们对每个对象应用上述余极限函数，并依据“余极限逐点计算”的证明来构造最终的余极限 acset。需要注意的是，这还要求实现余极限的泛性质（universal property）。详细实现可参见 Catlab 的源代码。

5.5 基准测试

在第 5.2 节中，我们声称生成函数的使用使 acsets 在性能上能够与手工编写的专用数据结构相竞争。本节通过与 LightGraphs.jl（一个前沿的 Julia 图库［4］）进行基准测试，提供支持该主张的实证证据。LightGraphs 的性能优于用 C++ 编写的图库，并远胜于流行的 Python 图库 NetworkX［14］。

基准测试结果如图 7 所示，其性能已按 Julia 当前最优水平（LightGraphs/MetaGraphs）的时间归一化。用于生成这些基准测试的代码可在 GitHub 上获取。其中，绿色标记的测试结果优于当前最优水平，红色标记的测试结果则比当前最优水平慢两倍以上。在“Graph”和“SymmetricGraph”测试中，我们分别针对有向图与无向图，评测了判断边是否存在、遍历所有边、遍历顶点邻接点以及构建路径图的操作。遗憾的是，我们的无向图数据结构本质上劣于“无向图”数据结构，因此我们无法期望在无向图基准测试中达到同等速度。在“GraphConnComponents”和“SymmetricGraphConnComponents”测试中，我们计算了路径图、完全图、星形图及 Tutte 图的连通分量。在“WeightedGraph”和“LabeledGraph”测试中，我们分别修改并遍历带权图与带标签图的权重和标签。最后，在“RandomGraph”测试中，我们构建具有不同分布的随机图；而在“Searching”测试中，我们遍历此前生成的随机图。

基准测试表明，无需大量优化努力，且 acset 核心不包含任何图特定代码的情况下，acset 的性能通常可与 LightGraphs 相媲美，多数情况下差距在两倍以内。然而，当我们与 MetaGraphs.jl（一个常用于为 LightGraphs 图附加数据属性的包）相比时，发现 acset 可带来显著的性能提升。这是因为，正如我们所见，我们的 acset 实现能够为任意特定的顶点与边属性模式生成专门化的图数据结构；而另一方面，MetaGraphs 通过为每个顶点和每条边附加字典来统一处理所有情况，导致内存布局效率低下。

综上所述，这些基准测试表明：在科学计算中，将 acset 用于对性能敏感的任务是合理的。尽管未来仍有可能进一步提升性能，但当前系统已足以胜任大多数内存驻留工作负载。事实上，即使在存在可行替代方案（如 LightGraphs 或 DataFrames）的情形下，acset 已能实现相当不错的性能；更关键的是，在许多根本没有合理替代方案的情境中，acset 表现出的强大潜力为我们对这种范畴化数据结构方法的未来发展带来了高度期待。

6 总结与展望

本文中，我们为将 acset 作为技术计算中的实用数据结构奠定了理论与计算基础。该方法的优势有三重：acset 为包括图与数据框在内的众多现有数据结构提供了统一的抽象；它支持关系型数据新数据结构的快速开发；且其底层范畴理论已被充分理解，从而便于实现诸如极限、余极限和函子式数据迁移等强大而通用的操作。

原则上，上述所有变体均可在 Julia 中采用与本文类似的方法实现。然而，要理解 acset 所支持的诸多范畴构造的含义，仍需更多理论研究。

另一项未来工作的方向是提升围绕 acset 变异（mutation）的符号推理能力。已知 acset 模式中的关系可通过极限与余极限等范畴论构造予以保持，但这些关系不会在用户代码中自动验证。例如，在使用对称图（示例 5）时，任何对称图的极限或余极限都保证产生一个有效的对称图，但确保对 acset 数据结构的任何直接变异都能维持边对合关系（edge involution）的责任在于用户。至少在某些特殊情况下，应有可能静态检查某一特定的 acset 变异模式是否保持了关系所蕴含的不变式。这可以在代码生成阶段完成，以避免运行时开销。虽然对任意变异进行验证不切实际，但对于某些基本变异是可以实现的。然后，只要高层代码仅使用这些基本变异，相应的不变式就能得到保障。例如，一个简单的函数若负责向对称图添加一条边及其逆边，则该函数的正确性可被验证。只要高层代码仅通过此函数添加边，由此构造出的所有对称图的有效性便能得到保证。

总之，我们或许可以将 acset 的使用方式与另一类极为流行的参数化数据类型——代数数据类型——相比较。代数数据类型在数学上被形式化为多项式函子的初始代数 [10]，其形态在 acset 数据模型中无处不在，却极少作为内存驻留数据结构实现。另一方面，许多编程语言——尤其是函数式语言——支持某种形式的代数数据类型，但代数数据类型在数据库系统中却相当罕见。鉴于两种范式各自明确的优势，我们尚不清楚为何这种分离应当存在。我们在 Julia 中对 acset 的实现，虽高效且可用，但如果能成为内置编程语言特性，其人机交互体验将更佳；同样，代数数据类型若能在数据库中成为强大功能，也将大放异彩。两类数据结构适用于不同场景：代数数据类型擅长表示语法树及其他递归数据，而 acset 则有效表达图状结构与表格数据。展望未来，我们期望看到 acset 在更多编程语言与库中得以实现。我们希望 acset 最终能获得与代数数据类型同等的基础地位，并与数据框和图一起，成为数据科学与科学计算的标准抽象。

原文链接：https://arxiv.org/pdf/2106.04703