{'fraction_non_alphanumeric': 0.030468359780228226, 'fraction_numerical': 0.00753064125715603, 'mean_word_length': 4.577030212127705, 'pattern_counts': {'":': 0, '<': 0, '<?xml version=': 0, '>': 0, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 7, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
A Formal Category Theoretical Framework for Multi-model Data Transformations

Data integration and migration processes in polystores and multi-model database management systems highly benefit from data and schema transformations. Rigorous modeling of transformations is a complex problem. The data and schema transformation field is scattered with multiple different transformation frameworks, tools, and mappings. These are usually domain-specific and lack solid theoretical foundations. Our first goal is to define category theoretical foundations for relational, graph, and hierarchical data models and instances. Each data instance is represented as a category theoretical mapping called a functor. We formalize data and schema transformations as Kan lifts utilizing the functorial representation for the instances. A Kan lift is a category theoretical construction consisting of two mappings satisfying a certain universal property. In this work, the two mappings correspond to schema transformation and data transformation.


Introduction
The biggest success stories in database theory are the relational model and relational algebra. Codd's theory [3] on relational databases has had an incomprehensible huge impact on database theory and applications. More formal and theoretical treatment of polystores and multi-model databases would make it possible us to repeat this success story in polystores and multi-model databases. A solid mathematical foundation would highly benefit their research and industry. Besides, to standardize the existing techniques and systems, a rigorous formulation is crucial.
Polystores and multi-model databases are a solution to the problem of handling a variety of data [12,14,20]. Native graph, document, key-value, and column databases have reached the point where they are competitive alternatives for relational databases especially in the cases when we perform a lot of read-and write-operations and heavy data analysis tasks. Since ML and AI are relying on massive amounts of data, NoSQL databases have gained attention.
Undoubtedly, polystores and multi-model databases are more complicated systems than ordinary relational databases since they subsume relational databases. arXiv:2201.04905v1 [cs.DB] 13 Jan 2022 The theory and language describing the systems have to evolve along with the systems which are gradually becoming more complex. But this should not mean that the theory and languages become more complex for end-users or even for database administrators and architects. Different databases have their own theoretical foundations and query languages that are not automatically compatible at a practical or theoretical level. This creates a huge challenge that we are tackling from the theoretical perspective.
Data and schema transformations form a significant part of the data integration and migration problems [10]. For example, the transformations might be needed at any point during the development of ML and AI solutions where databases are a part of the process. Initially, importing data requires transformations. Data integration between the databases can require multiple transformationbased views between the participating databases. Sometimes the most efficient solution is to materialize the transformed data. When the amount of data grows, the transformation systems need to be able to adapt for the growth. Thus monotonicity and temporality aspects of transformations are important to take into account. Eventually, the data require transformations before it can fit ML and AI models. For example, ML and AI models can use a knowledge graph approach but the data is stored in a relational database. The same transformation problems are also apparent for polystores and multi-model databases.
Often these transformations lack formal treatment. Daimler et al. [7] argue that informal data transformations are harmful. This is one of the challenges we are addressing in this work. The language, which is proved to be capable of capturing highly complex structures with a compact notation, is category theory. Liu et al. [19] visioned that the foundations of multi-model databases could be built on category theory because relational algebra's expressiveness is not powerful enough. We argue that the same applies to polystores. Our contributions include continuing previous research connecting category theory and database theory, formalizing graph and hierarchical models and instances in terms of category theory, and formalizing data transformations in polystores and multi-model databases as a solution to a category theoretical lifting problem.
Informally category can be thought of as a graph or a network with a certain additional structure. The additional structure is usually easy to find from computer science and database applications. If our goal is to express database theory precisely, it does not make sense to use only graphs because we can do modeling much better with categories.
In this work, we are often mentioning "schema". By schema, we do not only mean the conventional relational schema but a larger piece of information that contains any constraint related to a model. Also, the information about the model is part of the schema. Although modern NoSQL data is often referred to as schemaless, the data always have some constraints which we include in a schema in this context.

Related work
There are influential transformation frameworks but only a few of them are developed formally. SQLGraph [27] is a system, which translates graph databases to relational databases. It utilizes hashing and the fact that the modern relational databases natively support JSON. A framework of converting relational databases to graph databases by Virgilio et al. [9] utilizes schema paths. Das et al. [8] have developed a framework that creates RDF-view for property graph data in Oracle databases. All of these transformations are considered from a domain-specific and practical perspective although we identify that they have characteristical features which could be theoretically modeled and unified.
Jananthan et al. [15] propose associative algebra as a mathematical foundation for polystores. Leclercq et al. [18] built foundations of polystores on the tensor-based data model. Liu et al. [19] visioned that the foundations of multimodel databases could be built on category theory and we continue this work for polystores and multi-model databases.
There has been relatively much research on applying category theory to database theory. Our approach is highly influenced by David Spivak [25,26]. As he points out in [25], the category theoretical database research can be divided into two schools: category-based [24] and sketch-based [16]. A sketch [28] is a category with certain limit objects. Our position is category-based.
Besides work on database theory, category theory has been applied widely in computer science. Some of the most interesting and recent applications are programming languages (foundations of many functional programming languages), machine learning [6,11], automata learning [13], natural language processing (DisCoCat [5]), and quantum computing and mechanics [1,4]. Applied category theory has its annually organized conference called ACT (Applied Category Theory).

Categories
Category theory is a relatively new field of mathematics. Saunders MacLane and Samuel Eilenberg introduced categories, functors, and natural transformations in the mid-1940s as a "meta-mathematical" tool to study algebraic topology. MacLane [17] is the standard introduction to the topic. Other good introduction from mathematical perspective is [22] and from computer science perspective [26,28].
Definition 1 (Category). A category C consists of a collection of objects denoted by Obj(C) and a collection of morphisms denoted by Hom(C). For each morphism f ∈ Hom(C) there exists an object A ∈ Obj(C) that is a domain of f and an object B ∈ Obj(C) that is a target of f . In this case we denote f : A → B. We require that all the defined compositions of morphisms are included in C: if f : A → B ∈ Hom(C) and g : B → C ∈ Hom(C) are morphisms, then the composition g • f ∈ Hom(C) is defined and g • f : A → C is a morphism. Also, we assume that the composition operation is associative and that for every object A ∈ Obj(C) there exists an identity morphism id A : A → A so that f • id A = f and id A • f = f whenever the composition is defined.
See Figure 1 as a simple example of a category. In this work sans serif font always indicates a category. We follow the standard notation of category theory literature that is used, for example, in [22]. One of the most important categories is the category Set whose objects are sets and morphisms are functions between the sets. The composition operation of the morphisms is the composition of functions.

Functors
In science and mathematics, we often have functions or mappings which respect the underlying structures. Next, we define a structure-preserving mapping for categories. The mapping is called a functor.
Definition 2 (Functor). Assume C, D are categories. A functor F : C → D is defined so that for every object c in the category C, F (c) is an object in the category D and for every morphism f : Besides, we assume that following axioms hold: - . If every morphism in the category D has a preimage in the category C, we call the functor F full.
See Figure 2 (a) as an example of functor between two simple categories. The fact that a functor preserves the structure of a category is apparent in the example.

Natural transformations
The idea behind structure-preserving mappings is so fundamental that we can study what it means to preserve a structure of structure-preserving mappings.
The category theoretical notion for this is called a natural transformation. We follow a convention from category theory and denote a natural transformation by "⇒"-arrow.
Definition 3 (Natural transformation). Assume F, G : C ⇒ D are functors. A natural transformation α : F ⇒ G contains the following information: For each c ∈ C is associated a component of the natural transformation α c : F (c) → G(c). This component is a morphism in D so that the following diagram commutes for any morphism f : In equational format commuting means that See Figure 2 (b) as an example of a natural transformation.

Kan lifts
We discuss Kan lifts [21] shortly. Kan lift is a pair consisting of a functor and a natural transformation. The problem can be expressed as a diagram where all the arrows represent functors and a natural transformation ε : G • L ⇒ F . The category theoretical problem is to find a suitable functor L : A → B and a natural transformation ε : G • L ⇒ F which make the construction universal i.e. the natural transformation ε is universal among all the suitable natural transformations which satisfy the diagram. The problem is called a lifting problem.
Definition 4 (Kan lift). Let F : A → C and G : B → C be functors. A right Kan lift of F through G consists of a functor Rift G F : A → B and a natural transformation ε : G • Rift G F ⇒ F so that they satisfy the following universal property: given any other pair of a functor and a natural transformation The problem of finding the pair Rift G F : A → B and ε : G • Rift G F ⇒ F is called a lifting problem. The intuition behind Kan lifts is that we find a functor Rift G F that is the best approximation which makes the triangle "commute". The notion of Kan lift grabs a larger collection of data transformations since we do not require that the triangle necessarily commutes in strict sense. Although the definition is abstract, we believe that is suitably flexible to describe transformations conceptually.

Graphs
Graphs have a three-folded role in this work. The first role of graphs is that every category is naturally a graph where objects are the vertices and morphisms are the edges. On the other hand, a graph is an abstract data model which we are formalizing in terms of category theory. Some concrete models following the graph model are property graphs and RDF graphs. The third role of graphs is that they serve as the most standard tool to model relationships in a database, for example, ER diagrams and various relational schemas are graphs. We want to emphasize that these graphs should not be confused.

Definition 5 (Graph).
A graph G is a quad G = (V, E, src, tgt) where V is a set of vertices, E is the set of edges, src : E → V is the source function and tgt : E → V is the target function. If e ∈ E is an edge then its source vertex is src(e) = v and its target vertex is tgt(e) = w.
When we have graphs, it is natural to talk about paths. The following notation for paths is used in [24].

Functorial representation of relational data
We can draw a correspondence that we use categories to encode database constraints and functors to create instances. Because database instances have to follow the constraints, the structure-preserving (and thus constraint-preserving) mapping, a functor, is a natural choice to model instances and transfer constraints to them.
David Spivak [24] represented a simple database definition language using categories and functors. Now we shortly recall this construction. Following his ideas, we extend relational construction to graph and hierarchical data models. When data models have their functorial representations, we can define data transformations as a solution to the lifting problem (Definition 4).
Definition 7 (Categorical path equivalence relation [24]). Let G = (V, E, src, tgt) be a graph. A categorical path equivalence relation, denoted by ∼ =, is an equivalence relation on the set Path G of all the paths of G and it has the properties listed in Definition 3.2.4 in [24].
We omit the full list of properties since the list is relatively long and for this work, the most important is to know that the relation ∼ = is an equivalence relation on the set Path G .

Definition 8 (Categorical schema). A categorical schema is
where G is a graph and ∼ = is a categorical path equivalence relation on Path G . Definition 9 (Schema category). Let C = (G, ∼ =) be a categorical schema. The schema category C is the category whose objects are the vertices of the graph G and the morphisms are the equivalence classes of the paths of G defined by ∼ =.
The composition is defined as path composition with respect to the equivalence relation.
The schema category consists of objects which are table descriptions, for example, similar to that we have in the ER diagram. The morphisms are induced by the foreign key constraints between the tables. Intuitively, a schema category is the category induced by the corresponding ER diagram.
Definition 10 (Instance functor). Let C = (G, ∼ =) be a schema category. An instance functor I : C → Set maps the schema category to the category of sets and it satisfies the property that if p ∼ = q, then I(p) = I(q).
See Figure 3 (a) as an example of a relational instance functor. In Figure 3 (a) arrows are based on the constraints between the attributes. Since functional dependencies can be composed, the compositions of the dependencies are defined. A set of attributes trivially depends on itself which creates identity arrows.
For instance, we can ask a question related to Figure 3 (a): What is the channel that the moderator with ModName alicee owns? The answer can be found when we compose the arrow Moderator.FollowerID → Follower.ID with the arrow Follower.OwnChannel → Channel.ID. This gives us an arrow Moderator.FollowerID → Channel.ID. The answer is the channel with id C4 which can be read in Figure 3 (a).
The intuition behind a relational instance functor is that it sends each object c ∈ C (corresponding table description or a column in the schema) to a set I(c) ∈ Set. The set I(c) is the concrete instance of a table or a column. For example in Figure 3

Functorial representation of the graph and hierarchical data
Bumby et al. [2] gives a category theoretical formulation for graphs. Recall that we previously defined a graph G to be a quad (V, E, src, tgt). Property graphs have been studied from an algebraic and category theoretical perspective already in [23]. We do not assume that the graph would have a schema. In this sense, the construction differs from the one that we gave to the relational data. In practice, we might have a graph schema available, for example, in the cases when we are transforming relational data into graph data.
When a graph schema is available, we can encode it in the category theoretical definition. If we have a strict schema for the graph, we can generalize Spivak's approach for the relational data and assign the schema information to the objects 0 and 1 in Definition 11.
The classical graph example is a social network. Let us take a property graph -oriented approach and set that the object 1 is associated with a graph schema (person : {key, name, age}). The label person is the label of the node and key, name and age are keys for the properties stored in nodes. For edges we can define similar structure by setting 0 = [knows : {key, since}]. See Figure 3 (b)   The graph instance functor consists of the functor from the category that is a categorical representation for the graph schema to the category set. The graph is represented using the set notation and the conventional property graph notation.
As far as we know, hierarchical data, such as XML and JSON, do not have a category theoretical description that would have been studied previously. We use terms hierarchical data and tree data interchangeable. For any tree, we identify the characteristical feature that each node in the tree has exactly one parent node except the root. We can conceptually expand the tree construction so that the root is the unique node that has itself as a parent.
Definition 12 (Tree as functor). Let T be the one element category whose object is 0 and the only non-trivial morphism is p : 0 → 0. Diagrammatically the category is simply Now a tree is a functor T : T → Set which sends the single element 0 to the set of nodes of the tree. The single non-trivial morphism p : 0 → 0 is sent to the function that gives the parent node for each node in T (0). If the node is the root r, then we define T (p)(r) = r.

Intuition behind transformations represented in terms of category theory
Before formally discussing the transformations, we show a motivating example of how the theory in the previous sections manages to unify a big part of the transformation theory. This example is continuation to Figure 3 (b) where we had the classical social network data stored in a relational database. In our opinion, the most obvious way to store a social network is to use simple vertex-and edge-tables. The relationships are defined by foreign key constraints. The knows table, which serves as the edge-table, has at least two foreign keys, k.personID1 and k.personID2. These are connected to the person-table's primary key p.personID. Diagrammatically this can be expressed as We note that this schema already defines a schema category (Definition 9).
Recall the category theoretical representation for the graph in Definition 11. We can transform the relational instance into a graph in multiple ways. The first way to map the relational schema category to the graph schema category is on objects The objects 0 and 1 and morphisms s and t refer to the same objects and morphisms as in Definition 11. The second transformation is that we swap how the morphisms are mapped i.e. swap the roles of s and t. Compared to the first transformation this inverses the direction of the edges in the resulting graph. Besides these two mappings, we can find two more. The third possible functor collapses the relational schema i.e. it maps everything to the object 0 and its identity morphism: The fourth possible functor is similar to the previous functor but maps everything to the object 1. The benefit of the category theoretical formulation for transformations is that we can mathematically characterize, that the transformation which sends the knows-table to vertices and person-table to edges, is not valid because such transformation is not a functor. The transformations 3. and 4. have problems although they are well-defined functors. Thus functoriality is not a sufficient condition to characterize meaningful transformations. It does not make sense to map everything to edges (the result of the transformation 3.) because a valid edge needs to have a source and a target vertex. Also, a graph that contains only vertices without edges (the result of the transformation 4.) is not meaningful because edges are necessary for the most important graph operations. Thus we require that the functor should be full (Definition 2) to be relevant in practice. As we see, the transformations 3. and 4. as functors are not full but transformations 1. and 2. are.

Data transformation as lifting problem
Data and schema transformations are usually modeled as mappings from a source database to a target database. We base our data and schema transformation on Kan lifts [21]. Lifting problems have been considered in database theory also previously in [25]. As Definition 4 shows, the lift consists of two components: a functor and a natural transformation. Informally, the functor part is a schema mapping which describes a set of rules which define how the data items are mapped at a schema level. The functor is required to be full (Definition 2) because functors which are not full are not practically meaningful as the discussion in the previous section shows. Along the functor, we have a natural transformation which is data mapping. The pair satisfies the universal property which creates certain classification for transformations. The nature of this classification is still an open question.
The category theoretical approach to data and schema transformations reveals a crucial problem in transformation research. The problem is the separation of data and schema. In a world where relational databases are still the dominant databases, the division of data and schema is obvious. But the problem is apparent with the schemaless or schema-free models such as graphs and documents. If graph and document data transformations are approached from the relational perspective, we are likely to face problems. With category theory, we can model as much structure as the data has. Modeling transformations as pairs of mappings describes transformations more rigorously than a single total function between data sets.
Let I 1 : C 1 → Set and I 2 : C 2 → Set be two data instances as functors where the functors can represent either relational, graph or hierarchical instance functors as described in Definitions 10, 11, and 12. The question is how do we generally find a transformation between the data instances I 1 and I 2 . The problem can be expressed as a diagram where the functor F : C 1 → C 2 is the schema transformation mapping between the categorical representations of the schema categories C 1 and C 2 . The second part of the transformation consists of a natural transformation ε : I 2 • F ⇒ I 1 which obeys certain laws. If we assume that we have the two diagrams where the second diagram has a functor H : C 1 → C 2 and η : I 2 • H ⇒ I 1 a natural transformation. We then require that there exists a unique natural transformation γ : H ⇒ F such that η = ε • (I 2 • γ).
Definition 13 (Data and schema transformation). Let I 1 : C 1 → Set and I 2 : C 2 → Set be two data instances. A transformation from I 1 to I 2 is a Kan lift (Rift I2 I 1 : C 1 → C 2 , ε : I 2 • Rift I2 I 1 ⇒ I 1 ) so that the functor Rift I2 I 1 is a full functor.
We recall our example relational database instance in Figure 3 (a). In order to transform the relational instance to a property graph we need to construct a functor from the relational schema category to the graph schema category and define the natural transformation. Figure 4 describes the full transformation and the coloring codes the corresponding elements in each category. Informally, the natural transformation in the example could be understood so that for each object in the relational schema category, we have a mapping that tells how the corresponding relational data object in the category Set is mapped to the graph data object in the category Set.

Conclusions and future work
When the variety and amount of data grows, the need for polystores and multimodel databases is urgent. The efficient utilization of the systems requires a precise theory of how the systems operate and how they are modeled. So far, there has been extensive research on practical and implementational aspects. Without a proper theoretical framework, the field is left scattered. We are answering this challenge by formalizing the three most common data models and the data and schema transformations between them. We continued previous research and contributed by formalizing graph and hierarchical models functorially. We then focused on data and schema transformations between the functorial instances. Kan lifts require more studying as a basis for transformations but it seems a promising direction.
Query transformations form another half of the transformation systems. A query can be transformed correctly if the data is transformed correctly. This ties both transformations together which makes the modeling challenge still harder. Future work would include formalizing and unifying query transformations. In the case of SQL, the topic has already been studied in [25].
We identify that there is a need to model temporal data better. The problem of temporality is rarely addressed in polystore, multi-model database, and transformation research. Usually, the implicit assumption, especially in transformation frameworks, is that the systems are dealing with static data. Of course, that is hardly ever true and data changes and expands constantly. We believe that with category theory we can naturally include a time component to data.