Categorical Calculus and Algebra for Multi-Model Data

Jiaheng Lu · 2026

Read Categorical Calculus and Algebra for Multi-Model Data by Jiaheng Lu (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2603-10081.txt.

Introduction

Lu lays a firm base for querying databases that hold several data types at once. Multi model bases store table, tree and graph data side by side, yet query theory lags behind. Lu proposes categorical calculus and categorical algebra, extending the table based forms of each. He proves the two have equal power. He also gives change rules to speed queries up. Then he weighs what they can say and what they cost to run, giving designers a clear map.

Catalog record

CREATORJiaheng Lu
YEAR2026
COLLECTIONPAPERS
FORMATTXT
FILE SIZE42841
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2603.10081

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Categorical Calculus and Algebra for Multi-Model Data Jiaheng Lu Abstract Multi-model databases are designed to store, manage, and query data in various models, such as relational, hierarchical, and graph data, simultaneously. In this paper, we provide a theoretical basis for querying multi-model databases within the categorical paradigm. We propose two formal query languages: categorical calculus and categorical algebra, by extending relational calculus and relational algebra respectively for multi-model databases. We demonstrate the equivalence between these two languages of queries. We propose a series of transformation rules of categorical algebra to facilitate query optimization. Finally, we analyze the expressive power and computation complexity for the proposed query languages. 1 Introduction The “Variety” of data is one of the most important issues in modern data management systems [ 18 , 12 ] . Across various applications, data sources inherently exhibit diverse organizational structures and formats, e.g. relation, graph, XML, JSON, etc. In order to provide a unified view and query interface, a categorical model (e.g. [ 3 , 16 , 29 ] ) has been proposed to define a formal, unified data model capable of effectively accommodating this diverse array of data models. This paper proposes a comprehensive query framework within the categorical paradigm. We establish a theoretical groundwork for a multi-model query language through the introduction of categorical algebra and categorical calculus. Recall that relational calculus and relational algebra are two theoretical languages used for expressing queries on relational databases. They provide a way to formulate queries that can retrieve and manipulate data stored in relational database systems. Analogously, this paper develops categorical calculus and algebra for categorical databases. While categorical calculus is a declarative language that describes the properties of desired objects and morphisms in categories, categorical algebra is a procedural language that provides operations to manipulate categories and retrieve specific objects and morphisms from them. The contributions and organization of the paper are as follows: (i) We introduce categorical calculus for formulating queries on categorical databases. This calculus extends the relational domain calculus by incorporating multi-model predicates. These predicates enable the formulation of queries such as reachability queries in graph data, and twig pattern matching for parent-child and ancestor-descendant relationships in XML data (Section 3 ). (ii) We propose categorical algebra that includes both set operations and category operations. Set operations involve manipulating individual or multiple sets, while category operations enable the conversion between sets, functions and categories. Categorical algebra can address a wide range of queries, including relational queries, XML twig pattern matching, graph pattern matching, and reachability queries on graphs. We establish a theorem demonstrating the equivalence between categorical calculus and categorical algebra. Specifically, each categorical calculus can be expressed using a set of operators of categorical algebra, and vice versa (Section 4 ). (iii) We define a series of transformation rules of algebra expressions, which rewrite categorical algebraic expressions into more efficient forms for query optimization. We analyze the expressive power and computation complexity for the proposed query languages (Section 5 ). Related work. This work is related to two categories of previous research: (1) applied category theory for query languages in databases, and (2) query calculus and algebra for various types of data. Although category theory was initially developed as an abstract mathematical language to unify algebra and topology, researchers have explored its applications in various fields, including database query languages. Tannen (1994) [ 27 ] highlights that concepts from category theory can lead to a series of useful languages for collection types such as sets, bags, lists, complex objects, nested relations, arrays, and certain kinds of trees. Libkin (1995) [ 14 ] uses universality properties to study the syntax of query languages with approximations. Libkin and Wong (1997) [ 15 ] showcase the connection between database operations on collections and the categorical notion of a monad. More recently, Schultz and Spivak (2016) [ 25 ] introduce a categorical query language that serves as a data integration scripting language. Gibbons et al. (2018) [ 7 ] present an elegant mathematical foundation for database query language design using category theory concepts such as monads and adjunctions. These works demonstrate the intriguing connections between category theory and database query languages, revealing how category theory can inform and enhance database query language design. Since Codd (1972) [ 4 ] demonstrated that the same class of database queries can be expressed by relational algebra and the safe formulas of relational calculus, query algebra and calculus have become central topics in database research. A plethora of related works exist on query algebra and calculus across various types of data, including relational data [ 4 , 30 , 20 , 21 ] , nested relational data [ 22 , 9 ] , graph data [ 6 , 10 ] , object-oriented data [ 13 ] , incomplete and probabilistic data [ 26 , 8 ] , etc. These previous papers lay the foundation for database systems to process various types of data. Our paper pushes the frontier forward by proposing query calculus and algebra for categorical data with the application on multi-model databases. 2 Preliminaries Figure 1: This toy example shows three types of data including relation, XML and graph. They have a unified categorical representation. A database can be viewed as a category, specifically a set category. In this context, each object in the category represents a set, while each morphism corresponds to a function between two sets. The composition of morphisms aligns with the composition of functions. In the rest of this paper, we will use the terms “ set ” and “ object ” interchangeably, as well as “ function ” and “ morphism ” interchangeably. There are three fundamental types of objects within this category: entity objects , attribute objects , and relationship objects . For example, Figure 1 illustrates a unified category representation of three types of data (relation, XML, and graph) from E-commerce, which contains customers, social network, and order information with three distinct data models. Customer information is stored in a relational table—their IDs, names, and credit limits. Graph data bear information about mutual relationships between the customers, i.e., who knows whom. In XML documents, each order has an ID and a sequence of ordered items, each of which includes product name. Those three types of data can be integrated in one unified category schema in Figure 1 (d), where “ Knows ” is a relationship object, “ Customer ”, “ Order ”, and “ Product ” are entity objects and “ ID ”, “ CName ”, “ PName ” are attribute objects. Furthermore, the category under discussion is not just any set category, but rather a thin category, defined as follows: Definition 1 . ( Thin Category or Posetal Category ) [ 23 ] Given a pair of objects X and Y in a category \mathcal{C} , and any two morphisms f , g : X\to Y , we say that \mathcal{C} is a thin category (or posetal category) if and only if the morphisms f and g are equal. In category theory, a commutative diagram is a graphical representation that depicts the relationships between objects and morphisms. A diagram is commutative meaning that different paths through the diagram yield the same result.

Read the complete text