ABSTRACT
Many mathematical objects can be represented as functors from finitely-presented categories $\textsf{C}$ to $\textsf{Set}$. For instance, graphs are functors to $\textsf{Set}$ from the category with two parallel arrows. Such functors are known informally as $\textsf{C}$-sets. In this paper, we describe and implement an extension of $\textsf{C}$-sets having data attributes with fixed types, such as graphs with labeled vertices or real-valued edge weights. We call such structures acsets, short for attributed $\textsf{C}$-sets. Derived from previous work on algebraic databases, acsets are a joint generalization of graphs and data frames. They also encompass more elaborate graph-like objects such as wiring diagrams and Petri nets with rate constants. We develop the mathematical theory of acsets and then describe a generic implementation in the Julia programming language, which uses advanced language features to achieve performance comparable with specialized data structures.
► BibTeX data
► References
[1] Awodey ``Category Theory'' Oxford University Press (2010).
[2] Baezand Courser ``Structured cospans'' Theory and Applications of Categories 35, 1771-1822 (2020).
arXiv:1911.04630
[3] Borceux ``Handbook of categorical algebra 1: Basic category theory'' Cambridge University Press (1994).
https://doi.org/10.1017/CBO9780511525858
[4] Bromberger, Fairbanks, and contributors, ``JuliaGraphs'' (2017).
https://doi.org/10.5281/zenodo.889971
[5] Bush, Leeming, and Walters, ``Computing left Kan extensions'' Journal of Symbolic Computation 35, 107-126 (2003).
https://doi.org/10.1016/S0747-7171(02)00102-5
[6] Cartmell ``Generalised algebraic theories and contextual categories'' Annals of Pure and Applied Logic 32, 209-243 (1986).
https://doi.org/10.1016/0168-0072(86)90053-9
[7] Cheng, Ding, Wang, Lu, and Du, ``Which category is better: Benchmarking relational and graph database management systems'' Data Science and Engineering 4, 309-322 (2019).
https://doi.org/10.1007/s41019-019-00110-3
[8] Codd ``A Relational Model of Data for Large Shared Data Banks'' Communications of the ACM 13, 377-387 (1970).
https://doi.org/10.1145/362384.362685
[9] Fong ``Decorated Cospans'' Theory and Applications of Categories 30, 1096-1120 (2015).
arXiv:1502.00872
[10] Hamanaand Fiore ``A foundation for GADTs and inductive families: dependent polynomial functor approach'' Proceedings of the seventh ACM 59-70 (2011).
https://doi.org/10.1145/2036918.2036927
[11] Hoyerand Hamman ``xarray: N-D labeled arrays and datasets in Python'' Journal of Open Research Software 5 (2017) Publisher: Ubiquity Pre.
https://doi.org/10.5334/jors.148
[12] Johnson, Rosebrugh, and Wood, ``Entity-relationship-attribute designs and sketches'' Theory and Applications of Categories 10, 94-112 (2002).
[13] Kock ``Elements of Petri nets and processes'' arXiv preprint (2020).
arXiv:2005.05108
[14] Lin ``Benchmark of popular graph/network packages v2'' (2020).
https://www.timlrx.com/blog/benchmark-of-popular-graph-network-packages-v2
[15] Mac Laneand Moerdijk ``Sheaves in Geometry and Logic'' Springer (1994).
https://doi.org/10.1007/978-1-4612-0927-0
[16] McKinney ``Data Structures for Statistical Computing in Python'' 56-61 (2010).
https://doi.org/10.25080/Majora-92bf1922-00a
[17] McLarty ``Elementary categories, elementary toposes'' Oxford University Press (1992).
[18] Müllerand Wickham ``tibble: Simple Data Frames'' (2018).
https://CRAN.R-project.org/package=tibble
[19] Patterson, Halter, Lynch, James, Baas, Brown, slibkind, C. Graaf, cbw124, Cremer, Monticone, Alessandro, Rackauckas, TagBot, Kilpatrick, and Protter, ``AlgebraicJulia/Catlab.jl: A framework for applied category theory'' (2021).
https://doi.org/10.5281/zenodo.5771194
[20] R Core Team ``R: A Language and Environment for Statistical Computing'' (2020).
https://www.R-project.org/
[21] Reyes, Reyes, and Zolfaghari, ``Generic figures and their glueings: A constructive approach to functor categories'' Polimetrica (2004).
[22] Riehl ``Category Theory in Context'' Dover Publications (2016).
[23] Rupeland Spivak ``The operad of temporal wiring diagrams: formalizing a graphical language for discrete-time processes'' arXiv preprint (2013).
arXiv:1307.6894
[24] Rydeheardand Burstall ``Computational category theory'' Prentice Hall (1988).
[25] Schultz, Spivak, Vasilakopoulou, and Wisnesky, ``Algebraic Databases'' Theory and Applications of Categories 32, 547-619 (2016).
arXiv:1602.03501
[26] Shipman ``The functional data model and the data languages DAPLEX'' ACM Transactions on Database Systems 6, 140-173 (1981).
https://doi.org/10.1145/319540.319561
[27] Spivak ``Functorial Data Migration'' Information and Computation 217, 31-51 (2012).
https://doi.org/10.1016/j.ic.2012.05.001
arXiv:1009.1166
[28] Spivakand Wisnesky ``Relational foundations for functorial data migration'' Proceedings of the 15th Symposium on Database Programming Languages 21-28 (2015) Extended version on arXiv.
https://doi.org/10.1145/2815072.2815075
arXiv:1212.5303
[29] Wyler ``Lecture notes on topoi and quasitopoi'' World Scientific (1991).
https://doi.org/10.1142/1047
Cited by
[1] John Baez, Xiaoyan Li, Sophie Libkind, Nathaniel D. Osgood, and Evan Patterson, "Compositional Modeling with Stock and Flow Diagrams", Electronic Proceedings in Theoretical Computer Science 380, 77 (2023).
[2] Kristopher Brown, Evan Patterson, Tyler Hanks, and James Fairbanks, Lecture Notes in Computer Science 13349, 155 (2022) ISBN:978-3-031-09842-0.
[3] Joachim Kock, "Whole-grain Petri Nets and Processes", Journal of the ACM 70 1, 1 (2023).
[4] John C. Baez, Xiaoyan Li, Sophie Libkind, Nathaniel D. Osgood, and Eric Redekopp, Fields Institute Communications 88, 175 (2023) ISBN:978-3-031-40804-5.
[5] Baike She, Tyler Hanks, James Fairbanks, and Matthew Hale, 2023 62nd IEEE Conference on Decision and Control (CDC) 1680 (2023) ISBN:979-8-3503-0124-3.
[6] Markus Lohmayer and Sigrid Leyendecker, "EPHS: A Port-Hamiltonian Modelling Language", IFAC-PapersOnLine 55 30, 347 (2022).
The above citations are from Crossref's cited-by service (last updated successfully 2024-04-27 23:35:47). The list may be incomplete as not all publishers provide suitable and complete citation data.
On SAO/NASA ADS no data on citing works was found (last attempt 2024-04-27 23:35:47).
This Paper is published in Compositionality under the Creative Commons Attribution 4.0 International (CC BY 4.0) license. Copyright remains with the original copyright holders such as the authors or their institutions.