Categorical Data Structures for Technical Computing

技術(shù)計(jì)算中的范疇數(shù)據(jù)結(jié)構(gòu)

https://arxiv.org/abs/2106.04703

許多數(shù)學(xué)對(duì)象可表示為從有限呈現(xiàn)范疇 C 到集合范疇 S e t
的函子。例如，圖（graphs）即為從具有兩條平行箭頭的范疇到 S e t
的函子。這類(lèi)函子非正式地被稱(chēng)為 C -集（ C -sets）。本文提出并實(shí)現(xiàn)了一種對(duì) C -集的擴(kuò)展：允許數(shù)據(jù)帶有固定類(lèi)型屬性，如頂點(diǎn)帶標(biāo)簽的圖或邊帶實(shí)值權(quán)重的圖。我們將此類(lèi)結(jié)構(gòu)稱(chēng)為 acsets（attributed C -sets 的縮寫(xiě)，即“帶屬性的 C -集”）。該結(jié)構(gòu)源自代數(shù)數(shù)據(jù)庫(kù)領(lǐng)域的前期工作，是對(duì)圖與數(shù)據(jù)框（data frames）的統(tǒng)一推廣，并可涵蓋更復(fù)雜的類(lèi)圖對(duì)象，例如帶速率常數(shù)的接線(xiàn)圖（wiring diagrams）與Petri網(wǎng)。本文首先發(fā)展了acsets的數(shù)學(xué)理論，繼而描述了其在Julia編程語(yǔ)言中的通用實(shí)現(xiàn)；該實(shí)現(xiàn)借助語(yǔ)言的高級(jí)特性，在性能上可媲美專(zhuān)用數(shù)據(jù)結(jié)構(gòu)。

1 引言

從事實(shí)踐的數(shù)據(jù)科學(xué)家常常表示，他們至少將一半的時(shí)間用于數(shù)據(jù)清洗和數(shù)據(jù)管道管理，而非模型擬合。數(shù)據(jù)準(zhǔn)備本身固有的困難，又因數(shù)據(jù)存儲(chǔ)方式的多樣性而進(jìn)一步加�。簲�(shù)據(jù)可能存在于 SQL 數(shù)據(jù)庫(kù)、數(shù)據(jù)框（data frames）、圖結(jié)構(gòu)中，抑或散見(jiàn)于整個(gè)數(shù)據(jù)科學(xué)生態(tài)系統(tǒng)中的各類(lèi)更專(zhuān)門(mén)的數(shù)據(jù)結(jié)構(gòu)中。盡管每種數(shù)據(jù)結(jié)構(gòu)可能各有優(yōu)勢(shì)，但它們均附帶一套需重新學(xué)習(xí)的編程接口；此類(lèi)結(jié)構(gòu)的泛濫割裂了整個(gè)生態(tài)系統(tǒng)，并給互操作性帶來(lái)了挑戰(zhàn)。

針對(duì)這一問(wèn)題的一種解決方案是圍繞單一數(shù)據(jù)結(jié)構(gòu)進(jìn)行集中化：即數(shù)據(jù)框（data frame）。數(shù)據(jù)框是一種面向列的數(shù)據(jù)表；與矩陣不同，其各列可具有不同數(shù)據(jù)類(lèi)型。Python 生態(tài)系統(tǒng)中廣受歡迎的 pandas 包[16]即屬此類(lèi)；R 語(yǔ)言?xún)?nèi)置了 data.frame 類(lèi)型[20]及其變體 tibble[18]；在 Julia 中，許多不同包實(shí)現(xiàn)了 Tables.jl 的通用接口，這在一定程度上改善了互操作性。

然而，所有這些包背后所依賴(lài)的，是同一種抽象數(shù)據(jù)模型，以及該模型固有的局限性。尤為關(guān)鍵的是，數(shù)據(jù)框模型無(wú)法有效表達(dá)實(shí)體之間的關(guān)系——這一概念在 SQL 中體現(xiàn)為外鍵（FOREIGN KEY）。當(dāng)然，人們可以按某種臨時(shí)約定維護(hù)一組相互引用的數(shù)據(jù)框，但此類(lèi)關(guān)系并未被形式化，因而難以通過(guò)高層抽象進(jìn)行便捷、魯棒的操作。一個(gè)典型例子是：數(shù)據(jù)框無(wú)法恰當(dāng)?shù)乜坍?huà)圖的結(jié)構(gòu)，后者需兩個(gè)相互關(guān)聯(lián)的數(shù)據(jù)表——一個(gè)用于頂點(diǎn)，一個(gè)用于邊。

一種廣為人知、可同時(shí)涵蓋數(shù)據(jù)框與圖的抽象是關(guān)系型數(shù)據(jù)庫(kù)。關(guān)系型數(shù)據(jù)庫(kù)具有模式（schema），用于描述一組關(guān)系及其之間的外鍵關(guān)聯(lián)。然而，關(guān)系型數(shù)據(jù)庫(kù)往往作為龐雜的單體系統(tǒng)存在，難以與通用編程語(yǔ)言集成。SQL 等關(guān)系查詢(xún)語(yǔ)言，以及 Prolog、Datalog 等邏輯編程語(yǔ)言，均受制于所有獨(dú)立領(lǐng)域?qū)Ｓ谜Z(yǔ)言（DSL）共有的“阿喀琉斯之踵”：一旦超出該 DSL 能力范圍，便只能徹底脫離整個(gè)系統(tǒng)。而實(shí)踐中，跳出 DSL 往往是必要的，因?yàn)榧幢惚磉_(dá)能力最強(qiáng)的查詢(xún)語(yǔ)言亦有其局限。因此，“多少邏輯應(yīng)放在查詢(xún)中、多少應(yīng)放在數(shù)據(jù)庫(kù)外的后處理中”便成為一個(gè)長(zhǎng)期懸而未決的問(wèn)題——即數(shù)據(jù)處理領(lǐng)域的“兩種語(yǔ)言問(wèn)題”（two-language problem）。此外，數(shù)據(jù)庫(kù)通常被設(shè)計(jì)為全局可變狀態(tài)，使其難以作為局部上下文中的一次性對(duì)象自然使用。例如，圖雖可建模為數(shù)據(jù)庫(kù)，但若某程序在某一時(shí)刻需同時(shí)維護(hù)成千上萬(wàn)乃至百萬(wàn)個(gè)處于不同作用域的圖實(shí)例，則顯然不希望為此啟動(dòng)百萬(wàn)個(gè) SQL 數(shù)據(jù)庫(kù)實(shí)例。

然而，從本質(zhì)上講，“由模式關(guān)聯(lián)的一組表及其索引”這一構(gòu)想，并無(wú)理由一定要求單體系統(tǒng)、持久化存儲(chǔ)或全局作用域。關(guān)系數(shù)據(jù)庫(kù)最早的文獻(xiàn)已具備一套獨(dú)立于具體實(shí)現(xiàn)慣例的數(shù)學(xué)模型，其基礎(chǔ)是關(guān)系代數(shù)與一階邏輯[8]。不久之后，又提出了函數(shù)式數(shù)據(jù)模型（functional data model），其基本構(gòu)造單元為實(shí)體與函數(shù)；在該模型中，函數(shù)居于核心地位，而關(guān)系則被函數(shù)構(gòu)成的“跨度”（spans of functions）——即所謂“制表跨度”（tabulating spans）——所替代。Johnson 等人曾以范疇論語(yǔ)言，借助“概形”（sketches）對(duì)該數(shù)據(jù)模型進(jìn)行了形式化表述[12]。更近一步，Spivak 意識(shí)到，函數(shù)式數(shù)據(jù)模型可優(yōu)雅地重構(gòu)為：從一個(gè)有限呈現(xiàn)范疇到集合與函數(shù)范疇的一個(gè)函子[27]。隨后，針對(duì)該函子模型如何容納數(shù)據(jù)屬性的擴(kuò)展工作相繼展開(kāi)[28, 25]。

本文提出了一種高效的內(nèi)存駐留式（in-memory）范疇數(shù)據(jù)庫(kù)實(shí)現(xiàn)。根據(jù)所采用的模式，所得數(shù)據(jù)結(jié)構(gòu)可表現(xiàn)為數(shù)據(jù)框、圖，或大量此前因過(guò)于小眾而缺乏專(zhuān)用實(shí)現(xiàn)的其他結(jié)構(gòu)。借助 Julia 編程語(yǔ)言的高級(jí)特性，我們的實(shí)現(xiàn)性能可與前沿圖庫(kù)相媲美——盡管我們的“圖庫(kù)”實(shí)為一個(gè)更通用系統(tǒng)的輕量封裝。

我們將此類(lèi)數(shù)據(jù)結(jié)構(gòu)稱(chēng)為 acsets（“attributed C-sets”的縮寫(xiě)，即“帶屬性的 C-集”）。我們以直接、實(shí)用的方式定義 acsets，并表明其可被重新表述為范疇代數(shù)中已被深入研究的對(duì)象；基于此數(shù)學(xué)圖像，我們推導(dǎo)出了用于組合多個(gè) acsets、查詢(xún) acsets 以及在不同模式的 acsets 間轉(zhuǎn)換的高層操作。例如，我們可通用地計(jì)算固定模式下 acsets 的有限極限與余極限。但需強(qiáng)調(diào)的是，就大多數(shù)使用目的而言，使用者并不需要具備范疇論知識(shí)。

我們開(kāi)發(fā) acsets 的動(dòng)因最初來(lái)自 Catlab 及 AlgebraicJulia 生態(tài)系統(tǒng)[19]中其他軟件包的需求。在實(shí)現(xiàn)應(yīng)用范疇論的各類(lèi)構(gòu)件過(guò)程中，我們意識(shí)到，所需諸多數(shù)據(jù)結(jié)構(gòu)（至少在部分程度上）均可被 C-集（即余預(yù)層，copresheaves）所涵蓋，并可通用地實(shí)現(xiàn)；但該抽象并不完全令人滿(mǎn)意，因其未能涵蓋“屬性”（attributes）——即具有固定外部意義的數(shù)據(jù)（如實(shí)數(shù)、文本字符串等）。這最終引導(dǎo)我們走向 acsets 的形式體系，并促成了更系統(tǒng)化的軟件實(shí)現(xiàn)。

貢獻(xiàn)本文主要貢獻(xiàn)在于：在通用編程語(yǔ)言中，以高效、靈活的方式實(shí)現(xiàn)了內(nèi)存駐留的范疇數(shù)據(jù)庫(kù)數(shù)據(jù)結(jié)構(gòu)，支持應(yīng)用范疇論中的關(guān)鍵構(gòu)造，包括帶裝飾或帶結(jié)構(gòu)的余跨度（decorated/structured cospans）。我們的實(shí)現(xiàn)充分利用了 Julia 語(yǔ)言的元編程（metaprogramming）特性，在性能上可媲美高度專(zhuān)業(yè)化的前沿圖庫(kù)，同時(shí)具備遠(yuǎn)為廣泛的通用性。據(jù)我們所知，這種在范疇數(shù)據(jù)結(jié)構(gòu)中同時(shí)實(shí)現(xiàn)高性能與高通用性的組合尚屬首次。

在更偏理論的層面，我們進(jìn)一步探索了范疇數(shù)據(jù)庫(kù)的設(shè)計(jì)空間，提出了一種 Spivak 等人函子數(shù)據(jù)模型的變體，其復(fù)雜度介于文獻(xiàn)[28]與[25]之間，并推導(dǎo)了其基本數(shù)學(xué)性質(zhì)。

結(jié)構(gòu)安排本文第 2 節(jié)首先對(duì) acsets 給出非形式化的概述，面向計(jì)算機(jī)科學(xué)家與軟件工程師等普通讀者；第 3 節(jié)回顧 C-集的數(shù)學(xué)理論（acsets 為其擴(kuò)展），熟悉相關(guān)數(shù)學(xué)的讀者可跳過(guò)該節(jié)；第 4 節(jié)發(fā)展帶屬性 C-集的理論，證明 acsets 是 C-集范疇中的切片對(duì)象（slice objects），并由此導(dǎo)出若干推論；最后，第 5 節(jié)討論 acsets 的具體實(shí)現(xiàn)，并將其與 Julia 中前沿圖庫(kù) LightGraphs.jl[4]進(jìn)行基準(zhǔn)測(cè)試，為“acsets 可同時(shí)實(shí)現(xiàn)通用性與高性能”這一主張?zhí)峁⿲?shí)證支持。

2 帶屬性 C-集（Attributed C-sets）的使用
本節(jié)旨在直觀傳達(dá)對(duì) acsets 的理解。我們首先說(shuō)明兩種常見(jiàn)數(shù)據(jù)結(jié)構(gòu)——數(shù)據(jù)框與圖——如何作為 acsets 的特例；為展示該形式體系的廣泛適用性，我們還將簡(jiǎn)要介紹若干雖較罕見(jiàn)卻頗具實(shí)用價(jià)值的 acsets 實(shí)例。

2.1 數(shù)據(jù)框與圖
如引言所述，數(shù)據(jù)框是對(duì)“我們應(yīng)如何存儲(chǔ)數(shù)據(jù)”這一問(wèn)題的流行解答。表 1 展示了一個(gè)僅含兩列（a 與 b）的微型數(shù)據(jù)框。

在本文中，我們將數(shù)據(jù)框視為一組一維數(shù)組（稱(chēng)為“列”），所有列具有相同長(zhǎng)度。數(shù)據(jù)框中的一行，即為所有列在某一整數(shù)索引處的取值組合。用戶(hù)可通過(guò)列名訪(fǎng)問(wèn)單個(gè)列，也可通過(guò)索引訪(fǎng)問(wèn)單個(gè)行。為支持高效的數(shù)據(jù)訪(fǎng)問(wèn)與迭代，數(shù)據(jù)框通常以列優(yōu)先方式存儲(chǔ)（即作為列的列表），而非行優(yōu)先方式（即作為行的列表）。

我們將 acsets 構(gòu)建為數(shù)據(jù)框的擴(kuò)展，因此默認(rèn) Julia 中已有數(shù)據(jù)框的實(shí)現(xiàn)可用。在這一假想的實(shí)現(xiàn)中，

正如引言中所述，我們最終希望將圖視為兩個(gè)相互關(guān)聯(lián)的數(shù)據(jù)框。然而，在轉(zhuǎn)向這一策略之前，我們先考察圖的典型實(shí)現(xiàn)方式。在 Julia 中實(shí)現(xiàn)圖的最簡(jiǎn)單方法之一，或許是采用邊列表（edge list）數(shù)據(jù)結(jié)構(gòu)：

邊列表的一種常見(jiàn)變體是鄰接表（adjacency list）。它存儲(chǔ)源映射與目標(biāo)映射的原像集——借用數(shù)據(jù)庫(kù)的術(shù)語(yǔ)來(lái)說(shuō)，即為每個(gè)頂點(diǎn)建立索引，分別指向以其為起點(diǎn)（出邊）或終點(diǎn)（入邊）的邊。

2.2 邁向帶屬性的 C-集（Attributed C-sets）

圖與數(shù)據(jù)框之間存在一個(gè)本質(zhì)區(qū)別：我們可以對(duì)圖的頂點(diǎn)進(jìn)行置換（重標(biāo)號(hào)），只要相應(yīng)地更新源映射（source）與目標(biāo)映射（target），圖本身所表達(dá)的結(jié)構(gòu)含義便保持不變；然而，對(duì)于數(shù)據(jù)框，若將其中所有數(shù)值 6.0 替換為 2.0，則數(shù)據(jù)的含義將發(fā)生根本性改變。

這一區(qū)別對(duì)理解 acsets 至關(guān)重要，因此有必要引入一些非正式術(shù)語(yǔ)加以闡明：我們將圖中所存儲(chǔ)的連接性信息稱(chēng)為組合數(shù)據(jù)（combinatorial data），而將數(shù)據(jù)框中存儲(chǔ)的信息稱(chēng)為屬性數(shù)據(jù)（attribute data）。此類(lèi)區(qū)分在數(shù)據(jù)庫(kù)理論中是標(biāo)準(zhǔn)做法。例如，Johnson 等人的 EA 概念（EA sketches）明確區(qū)分了實(shí)體（entities）與屬性（attributes）[12]，其中“實(shí)體”即我們所稱(chēng)的組合數(shù)據(jù)。

在數(shù)據(jù)科學(xué)與科學(xué)計(jì)算中，我們經(jīng)常遇到同時(shí)包含組合數(shù)據(jù)與屬性數(shù)據(jù)的數(shù)據(jù)集。例如，假設(shè)需表示一個(gè)道路網(wǎng)絡(luò)：我們可以使用一個(gè)圖結(jié)構(gòu)，其中每個(gè)頂點(diǎn)（道路交叉口）關(guān)聯(lián)一對(duì)坐標(biāo) ( x , y )
，每條邊（道路）則附帶一個(gè)長(zhǎng)度屬性——該長(zhǎng)度可能因其彎曲或坡度而不同于端點(diǎn)間的歐氏距離。對(duì)此類(lèi)數(shù)據(jù)結(jié)構(gòu)的一種直接實(shí)現(xiàn)方式可能是：

條目 1 和 2 構(gòu)成了道路地圖的組合數(shù)據(jù)，而條目 3 和 4 則構(gòu)成了其屬性數(shù)據(jù)。
在我們的實(shí)現(xiàn)中，組合數(shù)據(jù)始終以整數(shù)表示；而屬性數(shù)據(jù)則通過(guò)類(lèi)型參數(shù)表達(dá)，可由任意 Julia 類(lèi)型填充。

需注意，最后一條（條目 5，即索引）與其他條目性質(zhì)不同：索引是為了提升效率而引入的，即使省略它們，數(shù)據(jù)結(jié)構(gòu)在邏輯上依然包含相同的信息。正因如此，當(dāng)我們形式化地描述簽名（schema）時(shí)，將省略索引信息；相反，索引可在編譯時(shí)根據(jù)預(yù)期的工作負(fù)載動(dòng)態(tài)選定——僅對(duì)那些頻繁查詢(xún)的鍵才應(yīng)建立索引。

在 Catlab 的實(shí)現(xiàn)中，我們通過(guò)撰寫(xiě)模式（schema）的形式化規(guī)范，并將其傳入一個(gè)函數(shù)，由該函數(shù)程序化地生成對(duì)應(yīng) acset 的數(shù)據(jù)結(jié)構(gòu)，從而自動(dòng)生成類(lèi)似于 OrganizedRoadMap 的數(shù)據(jù)類(lèi)型：

盡管 acsets 也提供了高層操作函數(shù)，但底層的訪(fǎng)問(wèn)器（accessors）與修改器（mutators）始終可用；并且如第 5 節(jié)的基準(zhǔn)測(cè)試所示，它們運(yùn)行迅速，因此用戶(hù)不會(huì)受限于高層接口所暴露的功能。結(jié)合 Julia 語(yǔ)言能夠使手寫(xiě)循環(huán)達(dá)到與“向量化”代碼同等效率的能力，用戶(hù)可輕松編寫(xiě)高性能算法——即便這些算法超出了核心庫(kù)的預(yù)設(shè)范圍。

2.3 超越圖：接線(xiàn)圖及其他類(lèi)圖結(jié)構(gòu)
在計(jì)算機(jī)科學(xué)中，常出現(xiàn)與圖類(lèi)似、但具備額外或不同結(jié)構(gòu)的對(duì)象。若為每種圖的變體都手工定制數(shù)據(jù)結(jié)構(gòu)，將導(dǎo)致軟件復(fù)雜性呈爆炸式增長(zhǎng)；然而，若缺乏定制數(shù)據(jù)結(jié)構(gòu)，又無(wú)法高效利用其額外的數(shù)學(xué)結(jié)構(gòu)。本節(jié)將表明，眾多類(lèi)圖結(jié)構(gòu)均可統(tǒng)一于 acset 這一概念之下，因而可通過(guò)統(tǒng)一、通用的軟件接口進(jìn)行操作。

以下三個(gè)示例均配有插圖；因圖幅較大，不便嵌入正文。建議讀者先翻閱后續(xù)幾頁(yè)展開(kāi)的圖示，再返回正文閱讀具體說(shuō)明。

示例 1：圖 1 展示了四種不同類(lèi)型的帶端口圖（port graphs），以及它們模式（schemas）的生成元。這些端口圖在兩個(gè)維度上有所不同：無(wú)類(lèi)型與有類(lèi)型，以及圓形（無(wú)向）與有向。在有類(lèi)型端口圖中，相連端口與連線(xiàn)的類(lèi)型必須一致。這一要求由以下等式表達(dá)：

對(duì)于圓形端口圖：

這兩個(gè)等式表明圖 1b 和 1d 中的某些三角形可交換。無(wú)類(lèi)型端口圖則無(wú)此限制。在圓形端口圖中，方框僅具有單一類(lèi)型的端口 Port，但連線(xiàn)是有方向的。而在有向端口圖中，端口被劃分為輸入端口（InPort）和輸出端口（OutPort），且連線(xiàn)必須從輸入端口指向輸出端口。按照慣例，輸入端口畫(huà)在左側(cè)，輸出端口畫(huà)在右側(cè)，從而可根據(jù)相鄰端口推斷連線(xiàn)的方向。

示例 2：一個(gè)細(xì)粒度 Petri 網(wǎng)由物種（species）、變遷（transitions）、到變遷的輸入（inputs to transitions）以及從變遷的輸出（outputs from transitions）組成 [13]。我們?cè)趫D 2 中可視化 Petri 網(wǎng)，按照傳統(tǒng)，物種用圓圈表示，變遷用方塊表示。Petri 網(wǎng)常通過(guò)增加一組“標(biāo)記”（tokens）來(lái)擴(kuò)展，每個(gè)物種對(duì)應(yīng)一組標(biāo)記。這可通過(guò)在模式中添加一個(gè)新對(duì)象 Tok 并引入從標(biāo)記到物種的映射來(lái)實(shí)現(xiàn)——這種用映射表示多對(duì)一關(guān)系的技巧，在使用關(guān)系代數(shù)建模數(shù)據(jù)時(shí)十分常見(jiàn)。請(qǐng)注意，細(xì)粒度 Petri 網(wǎng)的模式與有向二分圖（directed bipartite graph）的模式是同構(gòu)的，我們將在示例 6 中再次討論這一點(diǎn)。

示例 3：圖 3 繪制了有類(lèi)型與無(wú)類(lèi)型的無(wú)向接線(xiàn)圖（undirected wiring diagrams）的模式。粗略地說(shuō)，無(wú)向接線(xiàn)圖代表具有外邊界的系統(tǒng)的組合模式。想象將一個(gè)完整的接線(xiàn)圖放置于其中一個(gè)內(nèi)圓內(nèi)部，然后擦除該內(nèi)圓以獲得一個(gè)新的接線(xiàn)圖。這一操作使無(wú)向接線(xiàn)圖成為一個(gè)“操作元”（operad），該構(gòu)造在文獻(xiàn) [23] 中得到了精確化定義。

我們希望上述示例已足以讓讀者信服：將類(lèi)圖數(shù)據(jù)結(jié)構(gòu)表達(dá)為 acsets，既自然又具普適性。本文余下部分將主要聚焦于 acsets 的數(shù)學(xué)理論與具體實(shí)現(xiàn)；因此，若讀者主要關(guān)注該技術(shù)的實(shí)際應(yīng)用，可直接前往 Catlab 中的相關(guān)軟件實(shí)現(xiàn)。

3 C-集回顧
在轉(zhuǎn)向帶屬性 C-集（attributed C-sets）的理論之前，我們先回顧 C-集的概念——亦稱(chēng)范疇 C C 上的余預(yù)層（copresheaf）。在本節(jié)及下一節(jié)中，我們假定讀者已熟悉范疇論的基本概念，即范疇（categories）、函子（functors）與自然變換（natural transformations）。

3.1 定義與示例

我們關(guān)注極限（limits）與余極限（colimits），是因?yàn)?C-集的應(yīng)用通常涉及可通過(guò)極限或余極限表達(dá)的操作；我們將在后文看到，能夠計(jì)算推出（pushouts）對(duì)于組合帶結(jié)構(gòu)的余跨度（structured cospans）至關(guān)重要。上述逐點(diǎn)公式（pointwise formula）導(dǎo)出了一種通用于函子范疇中計(jì)算極限與余極限的通用算法，我們已將其應(yīng)用于有限 C-集的實(shí)現(xiàn)中。

3.3 查詢(xún)與數(shù)據(jù)遷移

4 帶屬性 C-集的理論

在第 2 節(jié)中，我們對(duì)比了數(shù)據(jù)集中可包含的兩類(lèi)信息。第一類(lèi)是組合數(shù)據(jù)（combinatorial data），它能被 C-集很好地建模。然而，第二類(lèi)——屬性數(shù)據(jù)（attribute data）——卻不能被恰當(dāng)?shù)亟�，因�(yàn)?C-集的同構(gòu)類(lèi)會(huì)抽象掉集合中元素的實(shí)際內(nèi)容，僅保留元素之間的關(guān)系。

我們對(duì) acset 的定義與文獻(xiàn)中其他帶屬性的范疇數(shù)據(jù)庫(kù)定義密切相關(guān)［28, 25］。定義 7 是 Schultz 等人所提出的“代數(shù)數(shù)據(jù)庫(kù)”［25］的一種更簡(jiǎn)潔但表達(dá)能力稍弱的變體：它用指向離散范疇的擬函子，替換了原定義中指向多類(lèi)代數(shù)理論（multisorted algebraic theories）且保持積結(jié)構(gòu)的代數(shù)擬函子（algebraic profunctors）。這意味著我們的數(shù)據(jù)模型不包含對(duì)屬性數(shù)據(jù)的操作（例如數(shù)值加法、字符串拼接等內(nèi)置代數(shù)運(yùn)算）；當(dāng)然，這類(lèi)操作仍可在普通的 Julia 代碼中實(shí)現(xiàn)。

另一方面，我們的定義比 Spivak 與 Wisnesky 的定義［28］略為豐富：我們引入了屬性類(lèi)型（attribute type）的概念，而非將每個(gè)屬性視為擁有各自獨(dú)立的數(shù)據(jù)類(lèi)型。這一補(bǔ)充在我們的實(shí)現(xiàn)中十分便利——屬性類(lèi)型直接對(duì)應(yīng)生成的 Julia 數(shù)據(jù)類(lèi)型中的類(lèi)型參數(shù)（參見(jiàn)第 5 節(jié)）。

綜上所述，我們所提出的 acset 概念在復(fù)雜度上介于文獻(xiàn)［28］與［25］之間。

Spivak 與 Wisnesky 在文獻(xiàn)［28, Proposition 9.1.2］中也陳述了類(lèi)似的結(jié)果，盡管由于形式化方式的差異，其證明更為直接。

事實(shí)上，了解“acset 的范疇是預(yù)層范疇的一個(gè)切片范疇”這一點(diǎn)很有用，因?yàn)檫@類(lèi)范疇具有許多理想的性質(zhì)。由于預(yù)層范疇是初等拓?fù)渌梗╡lementary toposes），而拓?fù)渌沟那衅懂犎允峭負(fù)渌梗ā巴負(fù)渌够径ɡ怼保?7, Theorem 17.4］），因此 acset 的范疇本身也是一個(gè)拓?fù)渌埂Ｌ貏e地，所有有限極限與余極限均存在，并可通過(guò)已知公式計(jì)算。此外，在 上的 acset 范疇之間還存在一個(gè)幾何態(tài)射（geometric morphism）。因此，從抽象意義上講，acset 范疇的重要性質(zhì)由上述構(gòu)造決定并已被充分認(rèn)知；主要?jiǎng)?chuàng)新在于實(shí)現(xiàn)這些性質(zhì)所帶來(lái)的諸多實(shí)用應(yīng)用。第 5 節(jié)的大部分內(nèi)容將致力于展示預(yù)層范疇切片范疇的性質(zhì)如何轉(zhuǎn)化為設(shè)計(jì)與實(shí)現(xiàn)軟件的實(shí)際能力。

4.2 帶屬性 C-集構(gòu)造的函子性

此外，如下圖所示，“帶權(quán)集合”（weighted sets）的模式到“帶權(quán)圖”（weighted graphs）模式的包含關(guān)系，誘導(dǎo)出一個(gè)從帶權(quán)圖到帶權(quán)集合的態(tài)射，該態(tài)射將一個(gè)帶權(quán)圖映射為其帶權(quán)邊集合（weighted set of edges）。

4.3 帶屬性 C-集的結(jié)構(gòu)化余跨度

acset 常與結(jié)構(gòu)化余跨度（structured cospans）結(jié)合使用，后者是由 Baez 與 Courser ［2］提出的一種用于開(kāi)放系統(tǒng)的形式化方法，建立在 Fong 的裝飾余跨度（decorated cospans）［9］基礎(chǔ)之上。結(jié)構(gòu)化余跨度的范疇是對(duì)余跨度范疇的推廣，下面我們回顧其定義。

4.4 極限與余極限

5 帶屬性 C-集的實(shí)現(xiàn)

本節(jié)概述帶屬性 C-集實(shí)現(xiàn)中更值得關(guān)注的若干方面，尤其是那些充分利用了 Julia 或 Catlab 獨(dú)特特性的部分。

5.1 AttributedCSet 數(shù)據(jù)結(jié)構(gòu)

5.2 代碼生成

若每次對(duì) acset 執(zhí)行底層操作時(shí)，都需在運(yùn)行時(shí)解析其模式的類(lèi)型級(jí)描述，則由此產(chǎn)生的開(kāi)銷(xiāo)將使 acset 無(wú)法與手工編寫(xiě)的專(zhuān)用數(shù)據(jù)結(jié)構(gòu)在性能上競(jìng)爭(zhēng)。幸運(yùn)的是，Julia 語(yǔ)言支持一種名為生成函數(shù)（generated functions）的有用元編程機(jī)制，可避免此類(lèi)運(yùn)行時(shí)懲罰。

與宏（macro）類(lèi)似，生成函數(shù)可執(zhí)行任意 Julia 代碼以生成一段 Julia 表達(dá)式，隨后對(duì)該表達(dá)式求值；不同之處在于，宏作用于其參數(shù)的語(yǔ)法結(jié)構(gòu)，而生成函數(shù)則作用于其參數(shù)的類(lèi)型，并返回一個(gè)針對(duì)這些特定類(lèi)型定制的函數(shù)體表達(dá)式。由于 acset 的類(lèi)型已完整刻畫(huà)了其結(jié)構(gòu)，該類(lèi)型便足以生成針對(duì)每一操作的、高度特化且高效的代碼。首次調(diào)用后，這些特化代碼會(huì)被緩存，后續(xù)調(diào)用時(shí)無(wú)需重復(fù)生成。

在諸如 StaticArrays.jl 等對(duì)靜態(tài)尺寸向量的完整實(shí)現(xiàn)中，性能提升的很大一部分源于靜態(tài)向量被分配在棧上而非堆上；而循環(huán)展開(kāi)則使得通用地支持任意尺寸的靜態(tài)向量也能在性能上媲美那些為特定尺寸（如 2D 或 3D）硬編碼優(yōu)化的代碼。例如，歐幾里得幾何相關(guān)軟件包從此無(wú)需再為性能考慮而對(duì)二維、三維等情形單獨(dú)特化處理。

類(lèi)似地，如下基準(zhǔn)測(cè)試所示，生成函數(shù)使得 acset 的通用實(shí)現(xiàn)足以與針對(duì)特定 acset 手工特化的實(shí)現(xiàn)相競(jìng)爭(zhēng)。這不僅消除了大量領(lǐng)域?qū)Ｓ脦?kù)的必要性，更打開(kāi)了通向此前因開(kāi)發(fā)成本過(guò)高而被放棄的專(zhuān)用數(shù)據(jù)結(jié)構(gòu)的大門(mén)。特別是，它擺脫了諸如 MetaGraphs.jl 等包為支持任意用戶(hù)自定義數(shù)據(jù)屬性而被迫依賴(lài)字典（dictionaries）的困境；取而代之，用戶(hù)可直接創(chuàng)建一個(gè)恰好包含當(dāng)前應(yīng)用所需字段的、全新的專(zhuān)用數(shù)據(jù)結(jié)構(gòu)。

幾乎所有對(duì) acset 的基本操作均以生成函數(shù)實(shí)現(xiàn)。得益于對(duì)索引的支持（即同時(shí)存儲(chǔ)正向與逆像映射以實(shí)現(xiàn)快速查找），這種實(shí)現(xiàn)方式所節(jié)省的程序員工作量遠(yuǎn)超表面所見(jiàn)。諸如添加/刪除元素、修改態(tài)射取值等操作與索引的交互十分微妙；而通過(guò)用生成函數(shù)編寫(xiě)訪(fǎng)問(wèn)器與修改器，這些簿記工作得以一次性徹底解決。

5.3 底層操作

下面我們展示如何利用 acset 的底層接口編寫(xiě)高性能算法。作為示例，我們實(shí)現(xiàn)圖上的深度優(yōu)先搜索（DFS）。以下代碼以頂點(diǎn) s 為起點(diǎn)，對(duì)圖 g 進(jìn)行深度優(yōu)先遍歷，并返回一個(gè)父頂點(diǎn)數(shù)組（parent），其索引為頂點(diǎn)編號(hào)。

在上述代碼中，對(duì) incident 的調(diào)用返回從給定頂點(diǎn) v 出發(fā)的所有出邊列表——該操作利用了 acset 為態(tài)射 src 所維護(hù)的索引；隨后對(duì) subpart 的調(diào)用則給出所有由 v 指向的鄰接頂點(diǎn)列表。這種數(shù)據(jù)訪(fǎng)問(wèn)模式在循環(huán)中被反復(fù)使用。相比之下，僅提供高層、基于查詢(xún)?cè)L問(wèn)接口的關(guān)系型數(shù)據(jù)庫(kù)，在處理圖算法（包括諸多高度迭代或遞歸的搜索算法）時(shí)往往表現(xiàn)不佳［7］。

5.4 范疇操作

acset 的一個(gè)用途是為第 4.3 節(jié)所述的結(jié)構(gòu)化余跨度（structured cospans）提供其中的“結(jié)構(gòu)”。為支持這一應(yīng)用，我們必須能夠計(jì)算推出（pushouts）。本節(jié)簡(jiǎn)要概述 acset 推出的計(jì)算方法，以余等化子（coequalizers）這一特例進(jìn)行說(shuō)明。

根據(jù)第 4.4 節(jié)，acset 的余極限是逐點(diǎn)（pointwise）計(jì)算的。因此，在討論如何在 acset 范疇中計(jì)算余等化子之前，我們首先回顧如何在有限集合范疇中計(jì)算余等化子（參見(jiàn)［24, §4.6］）。為便于討論，我們采用以下數(shù)據(jù)結(jié)構(gòu)來(lái)表示形如 { 1 , … , n }
的有限集及其間的函數(shù)——需注意，此處代碼遠(yuǎn)比 Catlab 中的實(shí)際實(shí)現(xiàn)更簡(jiǎn)單、泛化程度更低。

例如，圖的連通分量可以通過(guò)對(duì)源映射與目標(biāo)映射 V → E
的余等化子（coequalizer）提取得到。要計(jì)算 acset 態(tài)射的余等化子，首先需要一個(gè)用于表示 acset 態(tài)射的 Julia 數(shù)據(jù)結(jié)構(gòu)——即在 FinSet 中為模式中的每個(gè)對(duì)象配備一個(gè)命名元組（named tuple）。接著，給定一對(duì)平行的 acset 態(tài)射，我們對(duì)每個(gè)對(duì)象應(yīng)用上述余極限函數(shù)，并依據(jù)“余極限逐點(diǎn)計(jì)算”的證明來(lái)構(gòu)造最終的余極限 acset。需要注意的是，這還要求實(shí)現(xiàn)余極限的泛性質(zhì)（universal property）。詳細(xì)實(shí)現(xiàn)可參見(jiàn) Catlab 的源代碼。

5.5 基準(zhǔn)測(cè)試

在第 5.2 節(jié)中，我們聲稱(chēng)生成函數(shù)的使用使 acsets 在性能上能夠與手工編寫(xiě)的專(zhuān)用數(shù)據(jù)結(jié)構(gòu)相競(jìng)爭(zhēng)。本節(jié)通過(guò)與 LightGraphs.jl（一個(gè)前沿的 Julia 圖庫(kù)［4］）進(jìn)行基準(zhǔn)測(cè)試，提供支持該主張的實(shí)證證據(jù)。LightGraphs 的性能優(yōu)于用 C++ 編寫(xiě)的圖庫(kù)，并遠(yuǎn)勝于流行的 Python 圖庫(kù) NetworkX［14］。

基準(zhǔn)測(cè)試結(jié)果如圖 7 所示，其性能已按 Julia 當(dāng)前最優(yōu)水平（LightGraphs/MetaGraphs）的時(shí)間歸一化。用于生成這些基準(zhǔn)測(cè)試的代碼可在 GitHub 上獲取。其中，綠色標(biāo)記的測(cè)試結(jié)果優(yōu)于當(dāng)前最優(yōu)水平，紅色標(biāo)記的測(cè)試結(jié)果則比當(dāng)前最優(yōu)水平慢兩倍以上。在“Graph”和“SymmetricGraph”測(cè)試中，我們分別針對(duì)有向圖與無(wú)向圖，評(píng)測(cè)了判斷邊是否存在、遍歷所有邊、遍歷頂點(diǎn)鄰接點(diǎn)以及構(gòu)建路徑圖的操作。遺憾的是，我們的無(wú)向圖數(shù)據(jù)結(jié)構(gòu)本質(zhì)上劣于“無(wú)向圖”數(shù)據(jù)結(jié)構(gòu)，因此我們無(wú)法期望在無(wú)向圖基準(zhǔn)測(cè)試中達(dá)到同等速度。在“GraphConnComponents”和“SymmetricGraphConnComponents”測(cè)試中，我們計(jì)算了路徑圖、完全圖、星形圖及 Tutte 圖的連通分量。在“WeightedGraph”和“LabeledGraph”測(cè)試中，我們分別修改并遍歷帶權(quán)圖與帶標(biāo)簽圖的權(quán)重和標(biāo)簽。最后，在“RandomGraph”測(cè)試中，我們構(gòu)建具有不同分布的隨機(jī)圖；而在“Searching”測(cè)試中，我們遍歷此前生成的隨機(jī)圖。

基準(zhǔn)測(cè)試表明，無(wú)需大量?jī)?yōu)化努力，且 acset 核心不包含任何圖特定代碼的情況下，acset 的性能通�？膳c LightGraphs 相媲美，多數(shù)情況下差距在兩倍以?xún)?nèi)。然而，當(dāng)我們與 MetaGraphs.jl（一個(gè)常用于為 LightGraphs 圖附加數(shù)據(jù)屬性的包）相比時(shí)，發(fā)現(xiàn) acset 可帶來(lái)顯著的性能提升。這是因?yàn)�，正如我們所�?jiàn)，我們的 acset 實(shí)現(xiàn)能夠?yàn)槿我馓囟ǖ捻旤c(diǎn)與邊屬性模式生成專(zhuān)門(mén)化的圖數(shù)據(jù)結(jié)構(gòu)；而另一方面，MetaGraphs 通過(guò)為每個(gè)頂點(diǎn)和每條邊附加字典來(lái)統(tǒng)一處理所有情況，導(dǎo)致內(nèi)存布局效率低下。

綜上所述，這些基準(zhǔn)測(cè)試表明：在科學(xué)計(jì)算中，將 acset 用于對(duì)性能敏感的任務(wù)是合理的。盡管未來(lái)仍有可能進(jìn)一步提升性能，但當(dāng)前系統(tǒng)已足以勝任大多數(shù)內(nèi)存駐留工作負(fù)載。事實(shí)上，即使在存在可行替代方案（如 LightGraphs 或 DataFrames）的情形下，acset 已能實(shí)現(xiàn)相當(dāng)不錯(cuò)的性能；更關(guān)鍵的是，在許多根本沒(méi)有合理替代方案的情境中，acset 表現(xiàn)出的強(qiáng)大潛力為我們對(duì)這種范疇化數(shù)據(jù)結(jié)構(gòu)方法的未來(lái)發(fā)展帶來(lái)了高度期待。

6 總結(jié)與展望

本文中，我們?yōu)閷?acset 作為技術(shù)計(jì)算中的實(shí)用數(shù)據(jù)結(jié)構(gòu)奠定了理論與計(jì)算基礎(chǔ)。該方法的優(yōu)勢(shì)有三重：acset 為包括圖與數(shù)據(jù)框在內(nèi)的眾多現(xiàn)有數(shù)據(jù)結(jié)構(gòu)提供了統(tǒng)一的抽象；它支持關(guān)系型數(shù)據(jù)新數(shù)據(jù)結(jié)構(gòu)的快速開(kāi)發(fā)；且其底層范疇理論已被充分理解，從而便于實(shí)現(xiàn)諸如極限、余極限和函子式數(shù)據(jù)遷移等強(qiáng)大而通用的操作。

原則上，上述所有變體均可在 Julia 中采用與本文類(lèi)似的方法實(shí)現(xiàn)。然而，要理解 acset 所支持的諸多范疇構(gòu)造的含義，仍需更多理論研究。

另一項(xiàng)未來(lái)工作的方向是提升圍繞 acset 變異（mutation）的符號(hào)推理能力。已知 acset 模式中的關(guān)系可通過(guò)極限與余極限等范疇論構(gòu)造予以保持，但這些關(guān)系不會(huì)在用戶(hù)代碼中自動(dòng)驗(yàn)證。例如，在使用對(duì)稱(chēng)圖（示例 5）時(shí)，任何對(duì)稱(chēng)圖的極限或余極限都保證產(chǎn)生一個(gè)有效的對(duì)稱(chēng)圖，但確保對(duì) acset 數(shù)據(jù)結(jié)構(gòu)的任何直接變異都能維持邊對(duì)合關(guān)系（edge involution）的責(zé)任在于用戶(hù)。至少在某些特殊情況下，應(yīng)有可能靜態(tài)檢查某一特定的 acset 變異模式是否保持了關(guān)系所蘊(yùn)含的不變式。這可以在代碼生成階段完成，以避免運(yùn)行時(shí)開(kāi)銷(xiāo)。雖然對(duì)任意變異進(jìn)行驗(yàn)證不切實(shí)際，但對(duì)于某些基本變異是可以實(shí)現(xiàn)的。然后，只要高層代碼僅使用這些基本變異，相應(yīng)的不變式就能得到保障。例如，一個(gè)簡(jiǎn)單的函數(shù)若負(fù)責(zé)向?qū)ΨQ(chēng)圖添加一條邊及其逆邊，則該函數(shù)的正確性可被驗(yàn)證。只要高層代碼僅通過(guò)此函數(shù)添加邊，由此構(gòu)造出的所有對(duì)稱(chēng)圖的有效性便能得到保證。

總之，我們或許可以將 acset 的使用方式與另一類(lèi)極為流行的參數(shù)化數(shù)據(jù)類(lèi)型——代數(shù)數(shù)據(jù)類(lèi)型——相比較。代數(shù)數(shù)據(jù)類(lèi)型在數(shù)學(xué)上被形式化為多項(xiàng)式函子的初始代數(shù) [10]，其形態(tài)在 acset 數(shù)據(jù)模型中無(wú)處不在，卻極少作為內(nèi)存駐留數(shù)據(jù)結(jié)構(gòu)實(shí)現(xiàn)。另一方面，許多編程語(yǔ)言——尤其是函數(shù)式語(yǔ)言——支持某種形式的代數(shù)數(shù)據(jù)類(lèi)型，但代數(shù)數(shù)據(jù)類(lèi)型在數(shù)據(jù)庫(kù)系統(tǒng)中卻相當(dāng)罕見(jiàn)。鑒于兩種范式各自明確的優(yōu)勢(shì)，我們尚不清楚為何這種分離應(yīng)當(dāng)存在。我們?cè)?Julia 中對(duì) acset 的實(shí)現(xiàn)，雖高效且可用，但如果能成為內(nèi)置編程語(yǔ)言特性，其人機(jī)交互體驗(yàn)將更佳；同樣，代數(shù)數(shù)據(jù)類(lèi)型若能在數(shù)據(jù)庫(kù)中成為強(qiáng)大功能，也將大放異彩。兩類(lèi)數(shù)據(jù)結(jié)構(gòu)適用于不同場(chǎng)景：代數(shù)數(shù)據(jù)類(lèi)型擅長(zhǎng)表示語(yǔ)法樹(shù)及其他遞歸數(shù)據(jù)，而 acset 則有效表達(dá)圖狀結(jié)構(gòu)與表格數(shù)據(jù)。展望未來(lái)，我們期望看到 acset 在更多編程語(yǔ)言與庫(kù)中得以實(shí)現(xiàn)。我們希望 acset 最終能獲得與代數(shù)數(shù)據(jù)類(lèi)型同等的基礎(chǔ)地位，并與數(shù)據(jù)框和圖一起，成為數(shù)據(jù)科學(xué)與科學(xué)計(jì)算的標(biāo)準(zhǔn)抽象。

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