范疇圖數據庫統一實現

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