{'fraction_non_alphanumeric': 0.0453679404680591, 'fraction_numerical': 0.010497177984685625, 'mean_word_length': 4.1870221890732795, 'pattern_counts': {'":': 0, '<': 0, '<?xml version=': 0, '>': 1, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 12, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Single Pushout Rewriting in Comprehensive Systems

The elegance of the single-pushout (SPO) approach to graph transformations arises from substituting total morphisms by partial ones in the underlying category. Thus, SPO’s applicability depends on the durability of pushouts after this transition. There is a wide range of work on the question when pushouts exist in categories with partial morphisms starting with the pioneering work of Löwe and Kennaway and ending with an essential characterisation in terms of an exactness property (for the interplay between pullbacks and pushouts) and an adjointness condition (w.r.t. inverse image functions) by Hayman and Heindel. Triple graphs and graph diagrams are frameworks to synchronize two or more updatable data sources by means of internal mappings, which identify common sub-structures. Comprehensive systems generalise these frameworks, treating the network of data sources and their structural inter-relations as a homogeneous comprehensive artifact, in which partial maps identify commonalities. Although this inherent partiality produces amplified complexity, Heindel’s characterisation still yields cocompleteness of the category of comprehensive systems equipped with closed partial morphisms and thus enables computing by SPO graph transformation.


Introduction and Motivation
We want to dedicate this paper to Michael Löwe, the founder of the singlepushout approach [12] and simultaneously a pioneer in the investigation of categories of partial algebras with partial morphisms between them [13].
In this paper, we want to combine these two theories. We introduce the category of comprehensive systems, formally a category in which the inner structure of the objects can be described with partial maps, and will show that SPO rewriting is applicable in this category. (1) (2) (3)

Fig. 1. Comprehensive system
Comprehensive Systems have been introduced in [21] (see also [22]) as a means for global consistency management, representing a collection of inter-related systems. To provide an intuition of a comprehensive system (Definition 3 in Sect. 3), take a look at Fig. 1. There are three conceptual models A 1 , A 2 , A 3 , which depict persons ( ) with certain features: In A 1 a phone number ( ) is assigned to the person, in A 2 and A 3 the person possesses a home address ( ) , and in A 3 persons additionally may have a business address ( ) . You may think of A 1/2/3 representing (excerpts of) the contents of three databases possibly in three distributed IT-systems, the first stores records of persons and phone numbers while the second and third store records of persons and addresses.
In many cases it is necessary to maintain global consistency of the databases' contents, especially in the presence of inter-model constraints [20]. Let us assume the following constraint: IMC Every person with a business address must either provide a phone number or a home address or both.
Violations of this constraint can only be discovered, if common elements in the models are identified. Thus one has to specify that a recorded person in A 1 is actually the same as some person record in A 2 and/or A 3 . Such commonality specifications extend the modelling language and are commonly used in practice, e.g. [5]. In Fig. 1 we employ grey-coloured "tentacles" to visualise three commonalities: (1) The three person records, (2) the two home addresses, and also (3) the two assignments of the home address to the person. Note that A 1/2/3 formally represent directed graphs. But the junctions of each commonality (•) -called commonality representatives -form another graph A 0 in Fig. 1. Elements of A 0 witness common elements among A 1/2/3 and these commonalities must obviously respect node-edge-incidences (see the person to home address assignment), such that their respective outgoing grey lines are in fact graph morphisms a i : For |I| = 2 the underlying star-shape of comprehensive systems (finite collections of arrows (a i ) i∈{1,...,n} with common source) reduces to the span shape • ← • → •, which is the underlying setting for triple graphs [18], the common source in the middle specifying the commonality graph. An extension of triple graphs are graph diagrams [23], a framework for multi-ary model synchronisation. Since multi-ary commonality relations such as the ternary tentacles of identical person records in Fig. 1 can not be encoded with several binary relations [19], one must distinguish relations of different arity in the underlying shape for graph diagrams: E.g. in Fig. 1, a shape with two nodes is required: One node specifies the existence of a graph containing binary home address commonalities and one node is used for ternary commonalities of person records. In larger system landscapes (n > 3), there may be many more commonality relations of arbitrary arity k ≤ n, which would cause a considerable amount of heterogeneity of commonality nodes in the underlying shape for graph diagrams. Moreover, this schema and hence the basic setting for implementations must be altered, whenever new commonality relations are added.
We showed in [21,22] that comprehensive systems are a homogeneous generalisation of graph diagrams. They are homogeneous, because we need only one node to cope with commonality relations of arbitrary arity (the center of the starshape specifying commonality graph A 0 ) and must not alter the base setting, if new relations are added. It is a generalisation, because we can implement each graph diagram as a comprehensive system, i.e. we can jointly collect different commonalities into one graph A 0 .
An important distinction, however, is that graph morphisms a i : A 0 → A i in comprehensive systems are allowed to be partial. E.g. a 1 : Fig. 1 is undefined on (2) and (3) in A 0 . Nevertheless can we show that comprehensive systems form a category CS, in which graph rewriting, especially SPO rewriting, is possible. For this, we will also consider the category Par(CS), i.e. CS equipped with partial morphisms, cf. Sect. 2. Although this requires handling both intrinsic and extrinsic partiality, we can prove existence of all pushouts in this category (Theorem 1 in Sect. 4) and hence demonstrate applicability of SPO rewriting. We expect the reader to have basic knowledge in category theory. For categorical artefacts, we employ the following notations: Categories like C will be denoted in a double-struck font. When distinguishing between members of C, we write |C| (or just C) for its objects and Arr(C) for its morphisms. Moreover, there are identities id A : A → A and composition, e.g. g • f , for f : A → B and g : B → C. SET is the category of sets and total mappings and we will use the letter G for categories that are based on a signature with unary operation symbols only, see Sect. 3 for more details. Monomorphisms ( ), epimorphisms ( ) and -if applicable -inclusions ( →) have special notations. We furthermore expect the reader to be familiar with basic universal constructions like pullbacks, coproducts, and pushouts. When describing a pullback as in Fig. 2, we either say that the span (g , f ) is the pullback of co-span (f, g) or we call g the pullback of g along f . Moreover, the pullback object D in this construction is highlighted with a small adjacent right angle.

Graph-Like Structures
A category G is called based on a signature with unary operation symbols only, if it is isomorphic to a category of total algebras w.r.t. a signature, which only contains sorts and unary operation symbols. The simplest example in our context -and the rationale behind using letter G -are directed graphs, which are based on a signature with sorts E and V and two unary operation symbols s, t : E → V . We do not endorse directed graphs in particular and could likewise choose G to be given by E-Graphs [4] or bipartite artefacts like condition-event-nets. It is well-known that all these categories are topoi and thus possess all limits (e.g. pullbacks) and colimits (coproducts, pushouts) [6].
Objects of such categories G are sometimes called "graph-like structures", as e.g. in [14], and thus we will simply call G-objects and morphisms "graphs" and "graph morphisms" bearing in mind the above mentioned more general setting.
Remark: G will serve as the base category (or base structure) for assembling comprehensive systems, cf. Fig. 1. Actually, we could have traded G for more general (weak) adhesive (HLR) categories w.r.t. an admissible subclass M of all monomorphisms. 1 Adhesive HLR categories have mainly been introduced to model attributes, which poses some challenges regarding adhesiveness, in turn requiring to work with special subclasses of morphisms, which are isomorphic on the "data part". However, we restrict ourselves to graph-like structures because we are not focusing on attributes here and we want to stay in the tradition of Michael Löwe, who originally investigated graph-like structures only. Since graph-like structures are sufficiently concrete, we can actually refer to an element x ∈ A for some A ∈ G, i.e. an element of some carrier set of graph A. Likewise, "∀x ∈ A" means "for all x of any sort s in the carrier set of A".

Partial Map Categories
Consider an arbitrary category C with pullbacks. Michael had the courage to leave the comfortable world of total C-morphisms and utilised partial morphisms [17] for the SPO approach. While other researchers adhered to total morphisms, he forcefully followed through with partiality and proved that it is worthwhile [12]. He used the following definitions: the pair (m, f ) is a representative of its equivalence class. m, f is called total, if m is an isomorphism, and we use the usual arrow tip in this case: It is then easy to see that the objects of C together with partial morphisms constitute a new category Par(C): An identity is the equivalence class of the identity span and composition of m 1 , f 1 : G 1 G 2 and m 2 , f 2 : G 2 G 3 is given by constructing the pullback span (m 2 , f 1 ) of co-span (f 1 , m 2 ) yielding the composed partial morphism m 1 • m 2 , f 2 • f 1 . This is in fact independent of the choice of pullbacks and independent of the choice of representatives.
Furthermore we obtain an identity-on-objects functor called the graphing functor [8], i.e. a canonical embedding of totality into partiality.

Definition 1 (Hereditary Pushout). [8] Any pushout in
. If all pushouts exist in C and they are all hereditary, we say that C is a hereditary pushout category.
The following result can be found in [10]: If the Γ -image of a C-span has a pushout in Par(C), then this cocone consists of two total morphisms, which are the Γ -image of the pushout of this span in C.
For C := G, we can refer to elements inside objects of G, such that we will work with representatives G − → H of a partial morphism, in which the left leg m is chosen as the effective inclusion of dom(f ), the domain of definition of the partial morphism, into G. Since the name m is of minor importance, we may as well write f : G H. In this setting, we will call f "total", if the inclusion m is the identity. For the remainder of this paper we will use G-inclusions when there is a choice for monomorphisms (replacing with →). The following result was stated in [7] but fully worked out already in [12]: Proposition 2. G is a hereditary pushout category. Finally, hereditariness can equivalently be characterised as follows: Fig. 3 is hereditary, if and only if in any commutative cube as in Fig. 3 Fig. 3) Fig. 3) is a monomorphism.

Rewriting Rule and Derivation
While the double-pushout approach (DPO) [4] requires the construction of a pushout complement and another pushout in the underlying category C, the introduction of partial morphisms enables graph transformations to be expressed by a single pushout in Par(C). This elegant alternative to DPO was initiated by Raoult [16] and then fully worked out in Michael's PhD Thesis [12]. Computing by SPO graph transformation requires the existence of pushouts in Par(C) and it requires conflict freeness of matches, cf. Definition 2, if one wants to avoid partial matches. We can prove existence of pushouts for Par(CS) in Sect. 4, butin contrast to a simple criterion for conflict freeness in terms of injectivity of μ on delete-preserve pairs [12] -we have to leave the question of a criterion for conflict freeness in Par(CS) for future research.

Comprehensive Systems
For now and the rest of the paper, we fix a sufficiently large number n ∈ N. 2

Definitions and Background
i.e. of an n-tuple of partial graph morphisms (a j ) 1≤j≤n , which we call projections 3 .
In order to make reading easier, we always use letter i, if indexing comprises graphs A 0 , A 1 , . . . , A n and we use letter j, if indexing is only over the components A 1 , . . . , A n . Moreover, we denote comprehensive systems with bold face letters.
Comprehensive systems admit an all-embracing view on a system of possibly heterogeneously typed components, in which all necessary informational overlaps are coded, cf. Fig. 1. They have been treated on the level of graphs in [20] andon a more abstract level -in [3].

Definition 4 (Morphism of Comprehensive Systems). Let
holds in Par(G), the category of graphs and partial morphisms.
Whenever we mention morphisms f : A → A between comprehensive systems, we implicitly assume the components of A and A be denoted as in Definition 3 and we assume the constituents of f be denoted as in Definition 4. There is the obvious identical morphism id A for each comprehensive system A and composition can be defined componentwise. Hence we obtain Proposition 4 (Category CS and Component Functors). Let G be a category as described above. It is important to note that we claim (1) to hold in Par(G) and not in G! Let's investigate the consequences: Recall that the definition of composition of partial morphisms involves pullbacks. In the situation in Fig. 5 this enforces that a pullback of ⊆ j along f 0 (to express the composition of ⊆ j , a j and id A0 , f 0 ) can be chosen to be equal to ⊆ j , the inclusion of the domain of definition of f j • a j into A 0 , see the upper square in Fig. 5, and it enforces that the lower square commutes. If x ∈ A 0 , this observation is equivalent to the statement x ∈ dom(a j ) ⇐⇒ f 0 (x) ∈ dom(a j ), because "⇒" corresponds to commutatitivity of the upper square and "⇐" corresponds to the pullback property (in SET and hence in G, in which pullbacks are constructed sortwise). This yields a more handy admissibility characterisation for CS-morphisms: and the lower square in Fig. 5 commutes. Usually a morphism between two partial algebras A and B requires only preservation of definedness, i.e. "⇒" in (2). In the next section, we justify why we additionally need reflection of definedness.

Why Must Definedness Be Reflected?
Since our goal is to show that SPO rewriting is applicable for comprehensive systems, we must show that Par(CS) possesses all pushouts. Assume we would not have claimed reflection of definedness for CS-morphisms, but only commutativity of the two squares in Fig. 5, which is equivalent to claiming the properties of Proposition 5 except for the implication direction "⇐" in (2). In this case let's consider for n = 1 two simple comprehensive systems. Let G = SET and A 0 = { * } and A 1 = {•} be two one-element sets and let A = (a 1 : A 0 A 1 ) with a 1 the totally undefined map depicted with ( * •) and A = (a 1 : A 0 → A 1 ) with a 1 the unique total map from A 0 to A 1 depicted ( * → •). If we only work with preservation of definedness, then morphism id A , f : A → A , in which f 0 maps * to * and f 1 maps • to •, is an admissible morphism. We claim that the span A If there would be a pushout of this span of two total morphisms in Par(CS), then, by Proposition 1, it must coincide with the pushout of them in CS. Since f is an epimorphism in CS (because all f j are epimorphims in G), the pushout in CS must have p 1 = p 2 = id A as cocone, see the left top square in Fig. 6. The two partial morphisms m, h and id A , id A let the outer rectangle of partial morphisms commute, i.e.

m, h • id
in Par(CS), because the pullback object of m and f equals the pullback object of id A and f in CS. If there would be a unique mediator u, see the dashed line in the diagram, we must have u = id A , id A , because the lower rhombus must be commutative. However, for this u the right rhombus fails to be commutative, This example shows that we cannot expect to have all pushouts in Par(CS), if we would not require reflection of definedness. And this is true, even if the two morphisms, for which the pushout shall be constructed, are total monomorphisms.

Important Properties
Let's now assume all CS-morphisms to reflect definedness.
In the sequel, we will use formulations like "a property is valid componentwise" in CS or some construction "is carried out componentwise". Since many of the following considerations are based on this methodology, we give a formalisation: "Pushout", "Pullback", "Monomorphism", "Commutativity" impose truth of a predicate (a certain property) on a diagram in a category C. For pushouts and pullbacks the underlying diagram is a square, for the predicate "Monomorphism" it is a single arrow, for "Commutativity" it is an appropriate triangle of arrows. E.g. CS-morphism f : A → B is a componentwise monomorphism means that each f i is a G-monomorphism. More precisely: Given a diagram D of any of the above mentioned shapes in CS, let D i := C i (D) with component functor C i from Proposition 4, then the predicate p is true componentwise if and only if it is true for D i in G for all i ∈ {0, . . . , n}.
Another formulation is "componentwise construction of predicate p", where p is based on a certain universal property. If e.g. p is the predicate for pushouts, consists of two steps: In a first step one constructs pushout cospans In a second step one tries to define the projections d j in D := (d j : D 0 D j ) 1≤j≤n , cf. Definition 3, with the help of the pushouts' unique mediators. The cospan morphisms f and g consist of the respective components (f i ) 0≤i≤n and (g i ) 0≤i≤n . The phrase "p can be constructed componentwise" then means that the newly constructed object D is an admissible object according to Definition 3, that the newly created morphisms f and g are admissible according to Definition 4, and that predicate p holds on the resulting diagram in CS, i.e. the square that arises from enhancing the above CS-span by the CS-cospan yields a pushout in CS. Of course, this procedure applies to other universal constructions in a similar way and after such a construction, we know that property p is valid componentwise.
"Commutatitivity" is valid componentwise by definition, but we also obtain. Proof. Componentwise validity of monomorphy and componentwise construction of pullbacks have been proved in [11] for so-called S-cartesian functor categories. We showed in [21] (see also [22]) that -for a certain schema category -this functor category is equivalent to CS.   Fig. 7 is a G-pushout and the two back faces are pullbacks (cf. Definition 4 and the definition of composition of partial arrows on page 4), the prerequisite of the equivalent characterization of hereditaryness in Proposition 3 are fulfilled. Hence the fact that the middle layer in Fig. 7 is also a pushout (by construction) implies that the two upper front faces become pullbacks and the vertical upward arrow d j in the front right can be chosen to be an inclusion arrow. This shows that the componentwise construction indeed yields an admissible comprehensive system

Proposition 6 (Componentwise Properties of CS
and a commutative square (f : A → B, g : B → D, g : A → C, f : C → D) in CS. It remains to show that it is also a pushout.
Let for this a CS-object Z := (Z 0 zj − Z j ) 1≤j≤n and two CS-morphisms h : B → Z and k : C → Z be given such that h • f = k • g. Then componentwise considerations easily yield unique u := (u i : D i → Z i ) 0≤i≤n factoring through the components of h and k, resp., see Fig. 8, which shows the situation involving h only. It is easy to see that universality of d j and d j yield commutativity of all squares in Fig. 8, such that it remains to show that u is a CS-morphism. For this we use the equivalent characterization in Proposition 5, in particular we have to show (2) for u. Let for this x ∈ D 0 be given. It is well known that pushouts in G yield jointly surjective cospans, i.e. x has a preimage y in C 0 or in B 0 , cf. again Fig. 7. Assume w.l.o.g. that there is y ∈ B 0 and g 0 (y) = x (the case, where there is a preimage in C 0 , is similar). Then again using Proposition 5 several times yields Fig. 8) ⇐⇒ z j (u 0 (x)) is defined (h 0 = u 0 • g 0 and x = g 0 (y)), which shows that u is a CS-morphism. 4

Fig. 8. Admissibility of u
The proof of the existence of coproducts is similar: k∈I be a family of comprehensive systems indexed over some (possibly infinite) index set I. It is then easy to see that is the coproduct of them, where k∈I A k i denotes G-coproducts (hence the CScoproduct is constructed componentwise). For each j the partial morphism k∈I a k j is defined to be equal to a r j on each A r 0 . The unique mediator for a family (f k : A k → B) can be shown to be a CSmorphism by similar arguments as above for u. It is well-known that all colimits can be constructed from binary pushouts and coproducts [1], hence CS is indeed cocomplete.
The equivalent characterization of hereditaryness in Proposition 3 uses the predicates pushout, pullback, monomorphism, and commutativity, of which we have shown that validity in CS is equivalent to componentwise validity. By jumping back and forth from a comprehensive system to its components, this yields

Corollary 1. CS is a hereditary pushout category.
Although it is not the focus of this paper, we mention another important consequence for the application of graph transformations in CS: Corollary 2. CS is a weak adhesive HLR category [4] w.r.t. the class of all monomorphisms.
Proof. Heindel proves in [8], Prop. 8.1 that this conclusion can be drawn from Corollary 1, if pushouts are always stable under pullbacks, i.e. the implication "top face pushout, all side faces pullbacks ⇒ bottom face pushout" holds for all choices of vertical morphisms in Fig. 3. But this implication is true in CS by Proposition 6 and because this holds in G [6].
This corollary guarantees validity of the classical theorems for DPO rewriting such as Local Church Rosser, Parallelism, or Local Confluence Theorem to hold in CS, as well. 5

The Partial Map Category of Comprehensive Systems Admits All Pushouts
The goal of this section is to prove that SPO rewriting is well possible for comprehensive systems CS by showing that the category Par(CS) possesses all pushouts. This will follow mainly from a result of Hayman and Heindel: Proposition 7 (Existence of Pushouts of Partial Maps, [7]). Let C be a category with pullbacks in which for each span C  (3)

Definition 5 (Inverse Images and Upper Adjoints
Note that U is unique, if it exists [7], and that f −1 is monotone, since pulling back (between comma categories) is functorial and preserves monomorphisms.

. . . and in CS
Proposition 8. CS has images and the pullback functors preserve them.
Proof. Let f : We use G's epimono-factorizations [6] to decompose f 0 and (f j ) 1≤j≤n in Fig. 5 accordingly. In particular f 0 =: m 0 •e 0 . Then the pullback of m 0 and ⊆ j and its unique mediator u w.r.t. df and e 0 • ⊆ j yields the situation in Fig. 9a, where the left upper square is a pullback by the pullback decomposition lemma. In G pullbacks preserve epimorphisms, i.e. u is an epimorphism and the square in Fig. 9b has a unique diagonal [6]â j : I → Im(f j ), such that everything commutes. Adding this diagonal in Fig. 9a yields Im(f ) := (Im(f 0 )â j − Im(f j )) 1≤j≤n and the inclusion Im(f ) − → A . Moreover, Im(f ) can be shown to 6 Since we are working with equivalence classes, is easy to see that f −1 is independent of the choice of representative of m and independent of the choice of pullback. 7 A function U : (X, ≤X ) → (Y, ≤Y ) between two partially ordered sets is called monotone, if it preserves the order, i.e. ∀x, x ∈ X : be the image of f : A → A in CS, because it was set up by componentwise epimono-factorization (in G), in which the mono-part is componentwise the least subobject of the respective codomains of f 0 and f j . Pullback functors preserve images in CS because of the essential uniqueness of epi-mono-factorisations, of preservation of monomorphisms and epimorphisms [6] under pullbacks in G, and componentwise pullback construction (cf. Proposition 6).
By Proposition 8, the latter term in this equation is the image factorisation of n • v and hence f −1 (U(n)) = f −1 ( k∈I m k ) n, the former being the least, the latter being some subobject of A factoring through n • v.

The Main Theorem
Theorem 1. Par(CS) has all pushouts.
Proof. Because CS has all pushouts by Proposition 6 and thus span-completions, this follows from Proposition 7, Corollary 1 and Proposition 9.
Due to space limitations we can not provide an example in which the full power of SPO rewriting compared to the DPO approach can be demonstrated. Instead we provide a simple example, which reveals one additional helpful aspect of our definition of CS-morphisms. The proper construction of arbitrary pushouts in Par(CS) (with non-injective rules and/or partial matches) is elaborated in [7].
Assume that a comprehensive system is in state G (the bottom left system in Fig. 10) which is apparently inconsistent w.r.t IMC in Sect. 1, because the person in G 2/3 possesses no phone. If it turns out that this person is the same as the one in G 1 , we can restore global consistency by applying rule ρ : L R ∈ Arr(Par(CS)), which deletes a binary commonality (dashed) among two person records and adds a new ternary commonality which comprises these two records. The application of the rule yields a comprehensive system H (bottom right), which satisfies IMC. Despite being relatively simple, this example demonstrates an advantage of our approach: We do not need Negative Application Conditions to prevent repeated application of the rule, because there is no longer a corresponding match of L into H. This is the case, because l 1 Fig. 10. SPO rule application (the projection of L 0 into L 1 , cf. Definition 3) is undefined on the only element in L 0 , but the respective projection h 1 in H is defined on the hypothetically matched element (in H 0 ), i.e. the required reflection of definedness is violated, cf. Definition 4.

Related and Future Work
The best reference for Single Pushout Rewriting is [12], see also [2]. Comprehensive systems are basically a functor category invented in [20] and generalized in [11], its basic ideas originating from the theory of triple graphs [18]. Pushouts in partial map categories and especially hereditariness of colimits have been thoroughly investigated in [7,8].
Our approach still lacks the proof that it is practically applicable, but we hope that SPO rules can serve as a basis for repair rules [15] in order to maintain consistency of informationally overlapping multimodels. We must also find an appropriate way of SPO rule typing, which can not rely on pure slice categories, because a typing morphism should not be forced to reflect definedness. And there should be a thorough characterisation of conflict-freeness in CS, which is difficult, because upper adjoints in CS are not constructed componentwise. The situation is as in the following quotation: "The contents of this [paper] should rather be considered a starting point . . . than the final document of this research issue" 8 .