# Federated Learning With Highly Imbalanced Audio Data

Marc C. Green and Mark D. Plumbley
Centre for Vision, Speech and Signal Processing, University of Surrey
<EMAIL_ADDRESS>
<EMAIL_ADDRESS>
## I. Introduction

Since the establishment of the Detection and Classification of Acoustic Scenes
and Events (DCASE) challenge series in 2013 [19], machine learning for
environmental audio has become a thriving area of research. Broadly split into
the dual tasks of acoustic scene classification (ASC) and sound event
detection (SED), with various specialist subtasks, there are applications in
audio surveillance [4], smart home systems [12], and urban acoustic
environment monitoring [2, 3].

Until recently, there has been little consideration by the community of the
privacy implications of these applications of the technology. Deploying sound
sensor networks in public or private spaces using standard centralised machine
learning creates a scenario where a great deal of identifiable and potentially
sensitive personal audio information is relayed to a central server, and could
become accessible to unauthorised parties.

Federated Learning (FL) [16] is one method that has been proposed to address
these concerns. Using FL, the raw data is never transmitted from the local
client devices to the server. Instead, local data is used to train local
models, with only the trained parameters from these models transmitted to the
central server. The server aggregates the parameters from all the client
devices into a global model, which is then redistributed to the client
devices, where another round of local training takes place. This exchange
continues until the model is trained. Thus, client devices can benefit from
other clients’ data, without that local data ever leaving each device.

One of the key challenges of this approach is that there may be significant
variation in the environmental circumstances of different client devices, such
that the data may be unbalanced and not independent and identially distributed
(IID) across devices. That is, the distribution of data at each local device
may not be representative of the global distribution, in particular some
devices may have much more data than others, representing different subsets of
the classes of interest. This means that gradients estimated in client models
may be very biased and not representative of the gradient over the full
dataset [13]. Despite these problems, FL has been deployed as part of
commercial predictive text models [7].

Recently, Johnson _et al._ [9] presented a study into FL for sound event
detection using synthesised soundscape data. In their study, data was
artificially split across 100 clients to simulate both IID and non-IID
distributions, with the amount of training data evenly split across clients
(300 ten-second clips per client), using a total of 25 event classes. That
study found that, for IID data, FL was able to produce models performing
almost as well as centralised training, but using non-IID data greatly reduced
performance [9].

In this paper, we present a study using the FSD50K dataset [5], a large
collection of weakly-labelled real audio data, sourced from freesound.org [1],
featuring 200 classes, and with metadata including the usernames of the
uploaders of each sound clip. We investigate the effectiveness of FL in a
challenging audio scenario where, unlike in [9], the data has not been curated
especially for an FL investigation. Instead, by utlising the uploader
metadata, we simulate clients based on ‘real’ users, with the highly
imbalanced distributions one might expect from real-world users kept intact.
We believe this may serve to highlight the challenges inherent in this
approach and indicate potential paths for future work.

This paper is organised as follows: Section II establishes the key background
to this work, including details on the Federated Averaging (FedAvg) algorithm
(Section i) and FSD50K dataset (Section ii). Section iii outlines the
experimental setup used, with Section III presenting results from these
trials. Section IV discusses these results, and concluding thoughts and ideas
for future work are presented in Section V.

## II. Background

### i. Federated Learning

As covered in Section I, FL requires global model held on a central server
device, which is distributed to several client devices. These local model
copies are trained on the clients using the data available locally. There are
periodic rounds of communication between clients and server, where clients
transmit the locally-calculated model parameters back to the server. The key
component of FL is the incorporation by the server of these parameters from
the client models back into the global model. Several approaches have been
proposed to do this, including Federated Stochastic Variance Reduced Gradient
(FSRVG) [11], and CO-OP [21], but the most common is the FedAvg algorithm
[16], shown to have better performance than the others [17].

The FedAvg algorithm has three key parameters [16, 17]:

  * •

$C$ \- the fraction of clients selected for local training for each round of
communication between central server and clients.

  * •

$E$ \- the number of local epochs.

  * •

$B$ \- the local mini-batch size.

To start, a global model $w_{t}$ is initialised with random parameters. A
subset of clients $S_{t}$ is randomly selected according to $C$. At each time
step $t$, the local models $w^{k}_{t}$ for client $k$ in this subset are
updated to the global model, i.e. $w^{k}_{t}\leftarrow w_{t}$. Each client
computes $E$ epochs of training over a mini-batch of size $B$ per
communication round to yield new local models $w^{k}_{t+1}$. These local
models are transmitted to the server, which aggregates them into a new global
model according to [17, 11]:

$w_{t+1}=\sum_{k\in S_{t}}\frac{n_{k}}{\mu_{t}}w^{k}_{t+1}$ (1)

where $\mu_{t}$ is the total number of data points on all clients selected in
this round and $n_{k}$ is the number of data points on client $k$. In effect,
the new global model parameters are a weighted mean of local parameters from
each client.

### ii. Dataset

The dataset used in this study is the FSD50K dataset of human-labelled sound
events [5]. FSD50K features 51,197 audio clips of varying length drawn from
freesound.org [1], labelled with 200 classes drawn from the AudioSet ontology
[6]. The representation of classes in the dataset is very imbalanced, with
many more examples of some classes than others. There are, for instance, over
14,000 clips with a ‘music’ label, over 5,000 labelled ‘human voice’, but only
163 labelled ‘printer’. The FSD50K metadata includes the username of the
freesound.org user that uploaded each sound clip, denoted ‘uploaders’. There
are 3,647 unique uploaders in the training set, and the amount of data is
highly imbalanced between these, with only a very few contributing large
amounts of audio. The vast majority of uploaders contribute a small amount of
audio, with 3,080 contributing 10 clips or less, 1,635 of these contributing
only one clip. We have used this uploader information to divide the data into
clients, retaining systematic biases including use of different recording
equipment and the different classes contributed by each uploader. To keep the
number of clients manageable for this initial study, we used a reduced version
of the dataset limited to uploaders that contributed 100 or more clips,
resulting in 57 ‘high-volume’ clients. These 57 clients contain in total 35%
of the data included in the FSD50K training set.

### iii. Method

Audio from the FSD50K dataset is processed the same way as in the paper that
introduced the dataset [5]. The audio is downsampled to 22.5 kHz and
transformed to a 96-band mel-spectrogram. Clips are segmented into one-second
patches with 50% overlap, and these patches are processed using 30ms frames
with 10ms overlap, resulting in input arrays of shape $t\times f=101\times
96$. As in [5], these patches inherit clip-level labels. Class scores for each
patch are therefore averaged to generate clip-level predictions. These clip-
level predictions are used to calculate performance metrics.

We use the VGG-like architecture that was the best-performing model tested in
[5]. This consists of three convolutional layers of 32 filters, two of 64
filters and one of 128 filters, each layer followed by batch normalisation and
ReLU activation. Groups of layers with the same number of filters are followed
by $2\times 2$ max-pooling. All convolution kernels are $3\times 3$. The
output of these convolutional layers is summarised by both global max pooling
and global average pooling, concatenated to form input to two fully-connected
layers, the first of 256 units and the second of 200, matching the size of the
class vocabulary.

To generate baseline results, this model was trained in the conventional non-
FL centralised manner using the Adam optimiser [10] with a learning rate of
$5\text{\times}{10}^{-4}$. Two versions were trained, the first using the
complete FSD50K dataset, and the second using the reduced version with only
the high-volume client data. Following this, a series of models were trained
using FL and the high-volume client data. Local models were trained using
Adam, with a local learning rate of $5\text{\times}{10}^{-4}$. A grid search
combinining $C$ and $E$ values was performed as follows:

  * •

$C=\\{0.1,0.3,0.5,0.7\\}$

  * •

$E=\\{1,3,5\\}$

with batch size $B$ held constant at 64. These values represent proportions
from 10% to 70% of the clients selected in each communications round, with
either 1, 3, or 5 epochs of local training. Each test was run for 50
communication rounds, with area under the precision-recall curve (PR-AUC)
scores [18] recorded for the validation data after each round. Following this,
one final model was trained using FL and the complete FSD50K dataset (using
$C=0.5$ and $E=3$).

## III. Results

Figure 1: PR-AUC score for each epoch in the centrally-trained models.

Figure 1 shows the PR-AUC values for each epoch of training in the standard
centralised models trained using both the complete dataset and the high-volume
client data. Note that early stopping ended the high-volume model training
after 13 epochs. It can be seen that both these models show steady improvement
over the first four epochs of training before plateauing at around 0.53 and
0.23, respectively. The highest PR-AUC for the complete data is 0.55, which is
similar to the benchmark centralised model results reported in [5]. For the
high-volume model, the highest PR-AUC is 0.24, which is still fairly high
given that 65% of the training data is not used in this case. These provide
good baseline scores with which to compare the FL-trained models.

Figure 2: Global PR-AUC scores for models trained using FL across all 50
communication rounds between high-volume clients and central model.

Figure 2 shows the validation PR-AUC scores achieved using FL for each central
model after every round of communication with the high-volume clients. It can
be seen that, though generally the PR-AUC values are much noisier than for
centralised training, for all values of $C$, there are training rounds
yielding PR-AUC values greater than 0.25. The very best PR-AUC score achieved
in FL training is 0.284, for $C=0.3$ and $E=3$, though given the noisiness of
the results this cannot be taken as evidence that these represent good values
for those parameters. Results are less noisy when a larger fraction of clients
$C$ are selected each round. For $C=0.7$ a linear improvement in performance
for the first ten communication rounds can be seen, followed by a plataeu
where PR-AUC scores vary between around 0.2 and 0.25. This pattern is also
somewhat evident for $C=0.5$, though variations in performance from round-to-
round are more pronounced. Results for $C=0.3$ and $C=0.1$ vary very
erratically, though there is still an upward trend discernible for $C=0.3$.
This increased noisiness with decreasing $C$ could be due to the fact that for
low values of $C$, very different subsets of data are available for training
during each round of communication, thus potentially pushing the global model
too far towards one subset or another in each round. When more of the data is
available in each round, the bias is therefore less extreme, so the results
are not as noisy. This is the main visible effect of varying $C$, and is
consistent with observations in [17], where FL models were trained using MNIST
image files [14].

Varying the number of local training epochs $E$ seems to have only subtle
effects on performance. For $C=0.7$, the model improves more quickly in the
earlier rounds for higher values of $E$, but after round 10 there is little
observable effect. For $C=0.5$, there is some indication of improved
performance for $E=3$ compared to $E=1$ in earlier rounds, but results are too
noisy to draw any conclusions. For $C=0.1$, the maximum PR-AUC using $E=1$ is
0.21, whereas for $E=3$ and $E=5$, this increases to 0.25 and 0.26,
respectively. Likewise, for $C=0.3$, maximum PR-AUC for $E=1$ is 0.26, whereas
for $E=3$ PR-AUC is 0.27, and for $E=5$ it is 0.28. Similar patterns can be
observed when considering mean PR-AUC values. This might indicate that
increasing the number of local training epochs can somewhat compensate for the
smaller amounts of data used in each round for low values of $C$. For $C\geq
0.5$, however, there is no such pattern of improvement of either maximum or
mean scores.

Figure 3: PR-AUC score for each communication round for a model trained using
FL ($C=0.5$, $E=3$) and the whole FSD50K dataset.

Figure 3 shows the PR-AUC scores after each communication round for the FL
model using clients comprising the entirety of the FSD50K dataset. As
previously noted, this includes 1,635 clients with only a single point of
training data each, and many more with less than 100 points of data each. PR-
AUC values follow a broadly similar pattern to the high-volume $C=0.7$
results, with a gradual improvement over early rounds, followed by a plateau
where values stay around 0.2. There is, however, a small but noticeable
increase at round 36 where PR-AUC scores increase from peak values of around
0.22 to 0.24.

It is very interesting that these results for an FL model trained using the
whole of FSD50K are similar to the FL performance using the large uploader
data only, and much lower than those achieved using all this data in a
centralised manner (see Figure 1), despite nominal access to a lot more data.
Given that, upon incorporation into the global model, parameters from client
models are weighted based on the amount of data in the local model (see
Equation 1) it is possible that contributions from low-volume local models are
too small to have an impact on global parameters when presented alongside
parameters from high-volume clients.

Alternatively, since just under half of clients contribute only a single clip,
and 84% of clients contribute less than 10 clips, since clients are selected
uniformly, regardless of the amount of data they contribute, it is likely that
there will be considerably _less_ data contributing to training the global
model in any given round. In fact, since the high-volume clients represent
only 1.6% of all clients, the chances of any client from this group being
selected for local training over 50 communication rounds is only 40%. It is
conjectured that the small increase in PR-AUC at round 36 may have been due to
one of the high-volume clients being selected in that round.

## IV. Discussion

Taken together, the results for the high-volume client data and the whole
dataset suggest that when there are very considerable imbalances in the amount
of data contributed by each client, it may take many more rounds of
communication to approach the performance of a centrally-trained model than
when all clients contribute substantial amounts of data, as simulated in the
high-volume client models. For instance, although noisy, especially for lower
values of $C$, within around 10 rounds of communication, models trained using
FL and the high-volume client data are able to match the performance of the
model trained centrally using this data. By contrast, the FL model trained
using the complete dataset has reached only about half of the performance of
the centralised model after 50 rounds of communication. It is possible that,
given many more communication rounds, the performance of this model might
approach that of the centralised model, but given in most practical FL
scenarios, communication represents the largest cost and potential bottleneck
[15], this scenario is not ideal.

One way to improve performance in this case might be to implement a means by
which some high-volume clients could be guaranteed to be selected in each
training round, making sure a majority of the available data could be seen in
a smaller number of communication rounds. Such a system, may, however, reduce
the privacy of clients contributing a lot of data, as some form of additional
record would be needed regarding which clients these were.

The noisiness of the results from round to round, especially for low values of
$C$ in the high-volume client models, incidicate that for stable performance
it might be advisable to keep the proportion of clients participating in each
round high, if possible. If speed of model training is not a priority, a
system could perhaps be configured to wait until a majority of clients have an
update ready before performing global averaging. Unlike $C$, $E$ can be
increased without increasing communication costs. The results presented here
show that for lower values of $C$, increasing $E$ can result in slightly
higher maximum scores achieved, whilst for higher values of $C$ this results
in faster improvements in early communications rounds. In neither case does
altering $E$ seem to have any effect on the noisiness of the results.

One way to reduce the varibility in results from round to round with a low $C$
might be to introduce some form of smoothing at the global level by reducing
the impact of the client parameters in any particular communication round. In
[17], an approach is tested whereby the central server retains copies of the
most recent parameters from all clients, not just those participating in the
current round. The global model is updated based on all of these parameters.
This approach is shown to produce less noisy results between rounds, but also
takes longer to converge than the updates described in Equation 1. There is
also the potential of reduced privacy, in that parameters related to
particular clients are retained on the server, rather than being removed
immediately following calculation of the new global model, which could
conceivably allow, for instance, inference attacks [8].

Another approach that could be tested would be the selection of clients in
proportion to the amount of data they contribute, rather than uniformly at
random. In the case of this dataset, however, this could result in the many
small-volume clients hardly ever being selected, which would result in
essentially replicating training using high-volume clients only. Some form of
hybrid selection process might be required to balance these factors.

## V. Conclusions and Future Work

In this paper, we have presented a study in federated learning with highly
imbalanced audio data derived from the FSD50K dataset. The dataset was split
into clients based on upload contributors. Our results show that when all
client devices contain substantial amounts of data, training using federated
learning can yield global models with performance comparable to centrally-
trained models, without the global model requiring access to any local data.
On the other hand, when a majority of clients contribute very small amounts of
data, training using federated learning can result in a performance reduction
relative to a centrally-trained model, at least using the number of
communications rounds tested here. It is shown that the performance of a
global FL model tends to be more variable between rounds of training than
would typically be expected from a centrally-trained model. This is especially
true when training using small proportions of clients per round.

A possible next step would be to focus on a close investigation of the causes
of the reduced performance when using the complete FSD50K development set to
train a global model using federated learning, relative to training centrally.
If performance can indeed be improved by making sure some high-volume clients
are included in each round, the privacy implications of this should be
explored in depth.

It might also be interesting to investigate the benefits of FL at the client
level, rather than assessing performance using a global validation set. As
mentioned in [20], a local model too dependent on local data can degrade
performance by overfitting. Personalisation of the global model to local
circumstances is an approach that might maximise performance for individual
users. To investigate this using the full FSD50K data would necessitate
amalgamation of some of the small-volume uploaders into larger clients as it
is not possible to meaningfully assess performance on a single data point.

## VI. Acknowledgements

The authors would like to thank Andres Fernandez for his techincal assistance.
This work was supported by grant EP/T019751/1 from the Engineering and
Physical Sciences Research Council (EPSRC).

## VII. Supplementary Materials

The full Python code used to generate these results can be found at:
https://github.com/marc1701/fsd_fed.

## References

  * [1] https://freesound.org/.  Accessed: August 24, 2020.
  * [2] J. P. Bello, C. Silva, O. Nov, R. L. DuBois, A. Arora, J. Salamon, C. Mydlarz, and H. Doraiswamy, SONYC: A system for the monitoring, analysis and mitigation of urban noise pollution, Communications of the ACM, (2018), pp. 68–77.
  * [3] O. Bunting, J. Stammers, D. Chesmore, O. Bouzid, G. Y. Tian, C. Karatsovis, and S. Dyne, Instrument for soundscape recognition, identification and evaluation (ISRIE): Technology and practical uses, in Euronoise 2009, October 2009.
  * [4] M. Crocco, M. Cristani, A. Trucco, and V. Murino, Audio surveillance: A systematic review, ACM Computing Surveys, 48 (2016).
  * [5] E. Fonesca, X. Favory, J. Pons, F. Font, and X. Serra, FSD50K: an open dataset of human-labeled sound events.  arXiv, Oct 2020.
  * [6] J. F. Gemmecke, D. P. W. Ellis, D. Freedman, A. Jansen, W. Lawrence, R. C. Moore, M. Plakal, and M. Ritter, Audio Set: An ontology and human-labeled dataset for audio events, in Proc. IEEE ICASSP 2017, 2017, pp. 776–780.
  * [7] A. Hard, K. Rao, R. Mathews, F. Beaufays, S. Augenstein, H. Eichner, C. Kiddon, and D. Ramage, Federated learning for mobile keyboard prediction.  arXiv, 2018.
  * [8] J. Jia and N. Z. Gong, Defending against machine learning based inference attacks via adversarial examples: Opportunities and challenges, in Adaptive Autonomous Secure Cyber Systems, S. Jajodia, G. Cybenko, V. Subrahmanian, V. Swarup, C. Wang, and M. Wellman, eds., Springer International Publishing, Cham, 2020, pp. 23–40.
  * [9] D. S. Johnson, W. Lorenz, M. Taenzer, S. Mimilakis, S. Grollmisch, J. Abeßer, and H. Lukashevich, DESED-FL and URBAN-FL: Federated learning datasets for sound event detection.  arXiv, 2021.
  * [10] D. P. Kingma and J. Ba, Adam: A method for stochastic optimization.  arXiv, 2017.
  * [11] J. Konecný, H. B. McMahan, F. X. Yu, P. Richtárik, A. T. Suresh, and D. Bacon, Federated learning: Strategies for improving communication efficiency, in NIPS Workshop on Private Multi-Party Machine Learning, 2016.
  * [12] S. Krstulović, Audio event recognition in the smart home, in Computational Analysis of Sound Scenes and Events, T. Virtanen, M. D. Plumbley, and D. Ellis, eds., Springer International Publishing, Cham, 2018, pp. 335–371.
  * [13] K. Ksieh, A. Phanishayee, O. Mutlu, and P. B. Gibbons, The non-iid data quagmire of decentralized machine learning, in 37th International Conference on Machine Learning, 2020.
  * [14] Y. LeCun, C. Cortes, and C. J. C. Burges, The MNIST database of handwritten digits., 1998.
  * [15] T. Li, A. K. Sahu, A. Talwalkar, and V. Smith, Federated learning: Challenges, methods, and future directions, IEEE Signal Processing Magazine, 37 (2020), pp. 50–60.
  * [16] H. B. McMahan, E. Moore, D. Ramage, S. Hampson, and B. A. y Arcas, Communication-efficient learning of deep networks from decentralized data, in 20th International Conference on Artificial Intelligence and Statistics, 2017\.
  * [17] A. Nilsson and S. Smith, Evaluating the performance of federated learning, Master’s thesis, University of Gothenburg, 2018.
  * [18] scikit-learn developers, Metrics and scoring: quantifying the quality of predictions.  https://scikitlearn.org/stable/modules/model_evaluation.html.  Accessed: August 24, 2020.
  * [19] D. Stowell, D. Giannoulis, E. Benetos, M. Lagrange, and M. D. Plumbley, Detection and classification of acoustic scenes and events, IEEE Transactions on Multimedia, 17 (2015), pp. 1733–1746.
  * [20] K. Wang, R. Mathews, C. Kiddon, H. Eichner, F. Beaufays, and D. Ramage, Federated evaluation of on-device personalization.  arXiv, 2019.
  * [21] Y. Wang, CO-OP: Cooperative machine learning from mobile devices, Master’s thesis, University of Alberta, 2017.


For any predicate signature $\predicateSig$ and $\operationSig$, there exists a category $\doGraphCat{\predicateSig}{\operationSig}$ whose objects are sketches in $\intervalskecat{\GG}{\predicateSig}{\operationSig}$ and arrows are DO-graphs.

Unitality and Associativity are immediately given because pushouts preserve identities and their application is associative.

The equivalence of DO-graphs and DO-workflows lifts to the categorical level:

$\doGraphCat{\predicateSig}{\operationSig} \equiv \doWFCat{\predicateSig}{\opsig}$corr:dogDowEquiv
The parsing-mapping from Theorem <ref> extends to an identity on objects functor which is an equivalence.

$\doGraphCat{\predicateSig}{\opsig}$ is a hypergraph categorytheo:hypergraphCat

Follows immediately from propositions <ref>, <ref> and <ref>.

This last theorems allows us to interpret diagrammatic queries in a SMC, which can be visualized as a String Diagram.

termalgTerm Algebra
Given a sketch $X$ of variables and an operation signature , we build...

Term Algebra Adjunctiontheo:adjunction
There is an adjunction $\mathsf{T} \dashv \mathsf{U}$ with $\mathsf{U}: \catOpsigAlg{\skecatgp}{\opsig} \to \skecatgp$ being the (forgetful) projection on the underlying carrier and $\mathsf{T}: \skecatgp \to \catOpsigAlg{\skecatgp}{\opsig}$ being the (free) term algebra functor over a sketch.

Was basically given in <cit.>.
We have to adapt it to the slightly changed situation, though.

Oops: at this point, we are very far from this result. We need first to define what is a term=complex query over a sketch $X$, and show that the set of all terms over $X$ is an -algebra $T_\opsig(X)$. Then we need to show that the mapping $X\mapsto T_\opsig(X)$ is functorial (and I expect it could be a hassle). Only after that we are ready to prove that there is an adjunction.

§ BITS-AND-PIECES AGAIN: STARTED ON MAY 19

§.§ Diagrammatic reasoning

So far, our setting comprises a sketch category $\SS=\skecatgp$ and an operation signature  given by its arity function	. Note that any operation symbol  in  can be seen as a predicate symbol $P_\opvar$ with the arity sketch $P_\opvar^\arfun=E_\opvar$ (we use the same symbol  for predicate arities too). Hence, we have a bigger predicate signature $\PP_\OO$ with $\carr{\PP_\OO}=\carr{\PP}\sqcup\carr{\OO}$.  Recall also that any sketch in a subsignature $\PP'\subset\PP_\OO$ is automatically a $\PP_\OO$ sketch, in which $\semm{P}=\varnothing$ for any $P\in\PP_\OO\setminus \PP'$. We thus have full embedding $\SS_{\PP'}\righthookarrow\SS_{\PP_\OO}$.

An equational axiom (condition) for signature  is given by

§.§ something below endinput after mQ merge

We begin with defining a unified predicate signature  encompassing all operation symbols considered as predicate symbols whose arities are scopes $E_{\_}$ of the operations.

The carrier $\carr{\PPOE}=\carr{\PP}\sqcup\carr{\OO}$ and the arity mapping is provided by the universal property of coproducts as shown by diagram in  below:

\[
\xymatrix{
\carr{\PP}\ar@{>->}[r]
\ar[d]_{\arfun_\PP}
\ar@{-->}[d]^{\arfun_{\PPOE}} %\boldsymbol{!}}
\carr{\OO} \ar@{>->}[l]
\ar[d]^{\arfun_\OO}
\\  % ROW 2
\Ob{\GG}\ar@{>->}[r]
& \Ob{\monicarrowCat{\skecatgp}}\ar@{>->}[l]_-{\cod}
\]

whose diagonal is defined to be the arity monic of the multiquery $Q+ Q'$. Note that pushout (a) and sketch $E_{+}$ are in category . However, we know that sketches $E_Q$ and $E_{Q'}$ are, in fact, projections of -sketches $Q(X)$ and $Q'(X)$, and we may take pushout in the sketch category  as shown in diagram (b).
It is easy to see that forgetting -diagrams in sketch $(Q+Q')(X)$ would convert it into sketch  $E_+$.

[If we partially order the class $QQ(X)$ by multiquery subsetting, then operation sum would make it into a join semi-lattice with bottom $0_X$.]
Diagram (b) presents the same diagram in the .oops: it is still to be introduced

Then any multiquery unit $\eta_Q$ in $\GG||\PP_Q$ can also be considered a monic in $\GG||\PPOO$; the context will point to the hosting category.

§.§ Equiv of complex queries wrt. relayering

For any $n\le N(Q)$ and $q\in\iQuery{Q^n}$, we define

$$\heifun(q)=\nfont{min}\compr{i\le n}{\funimg{b^q}\subseteq E_{Q^i} }.$$

We say the $Q$ is normalized (or in a normal form) if $\heifun(q)=n$ for any $q$.

Any complex query $Q=[Q_1,...,Q_N]$ can be uniquely normalized to  $Q^!=[Q^!_1,...,Q^!_{N!}]$ by moving any atomic query $q$ in $Q$ to a multiquery of the  height: if $q\in Q_n$ and $\heifun(q)=m<n$, then we move $q$ to $Q^!_m$.

We begin the downshifting procedure with $n=2$ and build

$$Q_1^{n=2}=Q_1\cup\compr{q\in Q_2}{\heifun(q)=1} \text{ and } Q_2^{n=2}=Q_2\setminus \compr{q\in Q_2}{\heifun(q)<2}.$$

Then we take $n=3$ and redefine the sets above

$$Q_1^{n=3}=Q_1^{n=2}\cup\compr{q\in Q_3}{\heifun(q)=1} \text{ and }
Q_2^{n=3}=Q_2^{n=2}\cup\compr{q\in Q_3}{\heifun(q)=2}
along with redefining

$$Q_3^{n=3}=Q_3\setminus \compr{q\in Q_2}{\heifun(q)<3}.$$

And so on for $n=4,...,N$, which will give us $Q^!$.

We call two complex queries  $Q$ and $Q'$ equivalent and write $Q\cong Q'$  if $Q^!=Q'^!$. It is easy to see that if $Q\cong Q'$ then  $IE_{Q}=IE_{Q'}$ and for nay -algebra $A$, $\semm{Q}^A=\semm{Q'}^A$.
Maybe we actually don't need it because equivalence classes of cospans are enough to prove associativity...yes, it was designed as a pre-caution measure

For any $n\le N(Q)$ and $q\in\iQuery{Q^n}$, we define

$$\heifun(q)=\nfont{min}\compr{i\le n}{\funimg{b^q}\subseteq E_{Q^i} }.$$

We say the $Q$ is normalized (or in a normal form) if $\heifun(q)=n$ for any $q$.

Any complex query $Q=[Q_1,...,Q_N]$ can be uniquely normalized to  $Q^!=[Q^!_1,...,Q^!_{N!}]$ by moving any atomic query $q$ in $Q$ to a multiquery of the  height: if $q\in Q_n$ and $\heifun(q)=m<n$, then we move $q$ to $Q^!_m$.

We begin the downshifting procedure with $n=2$ and build

$$Q_1^{n=2}=Q_1\cup\compr{q\in Q_2}{\heifun(q)=1} \text{ and } Q_2^{n=2}=Q_2\setminus \compr{q\in Q_2}{\heifun(q)<2}.$$

Then we take $n=3$ and redefine the sets above

$$Q_1^{n=3}=Q_1^{n=2}\cup\compr{q\in Q_3}{\heifun(q)=1} \text{ and }
Q_2^{n=3}=Q_2^{n=2}\cup\compr{q\in Q_3}{\heifun(q)=2}
along with redefining

$$Q_3^{n=3}=Q_3\setminus \compr{q\in Q_2}{\heifun(q)<3}.$$

And so on for $n=4,...,N$, which will give us $Q^!$.

We call two complex queries  $Q$ and $Q'$ equivalent and write $Q\cong Q'$  if $Q^!=Q'^!$. It is easy to see that if $Q\cong Q'$ then  $IE_{Q}=IE_{Q'}$ and for nay -algebra $A$, $\semm{Q}^A=\semm{Q'}^A$.
Maybe we actually don't need it because equivalence classes of cospans are enough to prove associativity...yes, it was designed as a pre-caution measure

Piece for maybe future use:
Moreover, substitution is compatible with merge:

\begin{equation}\label{eq:mq-subst-mergeCompatible}
(Q_1+_X Q_2)^f = Q_1^f +_{X'} Q_2^f
\end{equation}

[Composition of ]

H- can be composed sequentially and in parallel.
to be completed

[Finite graphs]

Empty ? the plan is to take a few facts from makkai

Hence, the following results proved by Makkai can be transferred to our f-signatures and f-sketches .

[Sketch categories $\skecatgp$ and $\skecatgpmono$]

a1) The class of all $\predicateSig$-sketches over $\cat{G}$ and sketch morphisms make a small category denoted by $\skecatgp$. Mono-sketches and their morphisms form its full subcategory  , and there is a forgetful functor as shown by the lower horizontal arrow in diagram (<ref>) (read the forgetful functor name as “minus indexing”). Moreover,  $(\forgetind)$ is left adjoint to $i$,
,  is a reflective subcategory of .

a2)  Two diagonal arrows in the commutative diagram (<ref>)(a) are split opfibrations.

d)  Two diagonal arrows in the commutative diagram (<ref>)(d) are split fibrations.

\begin{equation}\label{eq:skeFibr}
\begin{array}{cc}
\begin{diagram}[small]
\skecatgpmono&&
\pile{\rInto^i \\ \lTo_{{-}\mathrm{indexing}} }
&& \skecatgp
\\
\\
\end{diagram}
& \quad % diag on the right
\begin{diagram}[small]
\monicsubcatbr{\skecatgpmono}%_{\mathrm{monic}}
\pile{\rInto^i \\ \lTo_{{-}\mathrm{indexing}} }
&& \monicsubcatbr{\skecatgp}%_{\mathrm{monic}}
\\
\\
&&\monicsubcat{\GG} %_{\mathrm{monic}}
\end{diagram}
\\ [25pt]
\text{a) opfibrations} & \text{d) fibrations}
\end{array}
\end{equation}

To be completed

§.§ Graphs
the fancy graph story should go here!!!
We fix a category  with pullbacks,  whose objects will be called graphs. To guide intuition, the reader may think of -objects as (co)presheaves, , functors $\II\rightarrow\setcat$, where  a suitable small category (as a rule, finite) defining our `graphs', and -s are s. For example, ordinary graphs are defined by category $\II_\graphind$ freely generated by the following four-element graph:

\begin{equation}\label{eqdiag:schema4graphs}
\begin{tikzcd}[row sep = 3em, column sep = 3em]
\Node & \Arrow \ar[l,"\ta", shift left=0.5ex] \ar[l,"\so" ', shift right=0.5ex]
\end{tikzcd}
\end{equation}

Category $\II_\Graph$ differs from graph <ref> by two identity loops added to nodes, and equations $\id_\Arrow\comp\so=\so$ etc forcing it to be a category. Examples and discussion of other schemas  useful for applications can be found in <cit.>. Below we will introduce several notions defined over , whose names include adjective diagrammatic referring to this graphical intuition, and the entire  will be referred to as . Category  will be called the base category for all constructs defined below.

Stuff here is for references only in case it'll be needed in the main sections

§ BITS AND PIECES

§.§ For the intro-on MMt from SLE paper

Model driven software engineering (MDE) puts models at the heart of software development, and makes it heavily dependent on the provision of intelligent model management (MMt) frameworks and tools. A common approach to implementing MMt tasks is to present models as collections of objects, and to program model operations in terms of operations applied to these objects; we can call this object-at-a-time programming (ObjATP).
Since models may contain thousands of interrelated objects, ObjATP can be  laborious and error-prone. In a sense, it is similar to the infamous record-at-a-time programming (RecATP) in data processing, and has similar problems of “micro-management".

Replacing RecATP by relation-ATP (“macro-management") has raised data processing technology to a qualitatively new level in semantic transparency and programmer productivity.  Similarly, one can expect that model-ATP, in which an engineer can think of MMt routines in terms of operations over models as integral entities, could significantly facilitate development of MMt applications. Lately, this program has been pursued by the database community  <cit.>, and is being gradually developed by the MDE community under the umbrella of megamodeling <cit.>.

§.§ For the intro-Makkai about Ehresmann

Quote from Makkai <cit.>

According to Ehresmann, a sketch is a graph with certain cones and cocones distinguished in it. A simple-minded generalization is to allow arbitrary types of distinguished diagrams in place of cones and cocones. The intention is, as with Ehresmann, to associate certain definite qualities with the distinguished diagrams; in Ehresmann’s case these are “limit cone” and “colimit cocone”. In the case of Ehresmann’s sketches, this intention is realized by the fixing of the intended semantics, which stipulates that a model of a sketch, a graph map from the underlying category of the sketch into a category, should turn the distinguished cones and cocones into limit cones and colimit cocones, respectively.

The Ehresmannian semantics has an obvious and potentially vast extension to the generalized sketches, by associating essentially arbitrary qualities of diagrams in categories with the distinguished diagrams, the only restriction being that the quality associated with a diagram has to match the shape of the diagram. For example, in Cartesian closed categories, the operation of exponentiation involves a kind of diagram that contains all the data for any particular exponential, in much the same way as a limit cone contains the necessary data for a particular instance of limit; since a product is involved in the exponential, the data for that product are part of the diagram. Thus, we have a corresponding kind of (generalized) sketch for Cartesian closed categories. In this kind of semantic determination, it is not necessary to limit ourselves to qualities given by universal properties; the target categories may need to have additional structure to support the semantics. This paper adopts the above-described simple-minded extension of the notion of sketch. However, it restricts the possible semantics to a certain “internal” form, in contrast to the “purely external”, and in principle arbitrary, determination in Ehresmann’s style of the qualities talked about above.

As our discussion in Sect.2 and Example in Appendix suggest, we need a very general notion of graphs as presheaves  G for a suitable schema category $\HH$. In all our applications, graphs have  structure that allows their traversal from the top elements to the bottom.

For example, ordinary directed multigraphs are given by schema $\HH=\Graph$ with $\Ob{\Graph}=\{\nfont{Node},\nfont{Arrow}\}$ and two non-identity arrows ,ArrowNode so that object Arrow is above Node. Other examples can be found in the TR. Hence, we require category  to be  in the folloiwng sense.

a huge old bits-and-pieces stuff

§.§ From

We begin with an obvious observations about forgetful functors in the diagram below:

\rTo^{\carr{.}}
\\
\rTo_{\carr{.}_0}
\gracat

where the leftmost one forgets composition, the upper right makes special loops ordinary loops (forgets the label) while the lower right deletes special loops at all. then it's not forgetful? We will denote the two compositions by . and $\carrcarr{.}_0$.

§.§.§ Diagrammatic Query Languages

There are two sources of motivation for this section: a) MDE and database applications in which the notion of query is omnipresent, and b) pure mathematics: what is the counterpart of sketches (as diagram theories over predicate signatures) for diagram operations, and how far could we develop a universal diagram algebra.

It tuns out that both motivational lines lead to the same construct, which we will call either query or DO-graph to recall the first or, resp. the second, motivational line. In the universal algebra view, queries are nothing but diagrammatic terms.

We will begin with an example showing what a query is and how queries are often encoded (queryexample). Then we will formalize queries as graphs with diagram operations (DO-graphs in short).  We will first consider atomic (or elementary) queries and then proceed to complex queries/DO-graphs. For the latter, we will give two formalizations: the first is data-centric, in which complex queries are encoded as sketches (similarly to encoding equational theories and algebras by Horn predicate logic ), and the second is workflow-centric, in which a complex query is seen as a workflow (similarly to seeing terms as abstract syntax trees)

§ DERIVED OPERATIONS (COMPLEX QUERIES) AS WORKFLOWS

below commented is the section {sections/atom-query} which is currently the same as {sections/atom-query-discrete}

Our next goal is to specify how atomic queries can be composed into complex queries.

Sketch Representation of Fig. <ref>

[Example <ref>  continued]

An example of a sketch is depicted in Fig. <ref>. In the linear notation, we can treat it as a conjunctive formula

$$\monicpred(f)\wedge\monicpred(f')\wedge\pbpred(m, l, m', l') \wedge .....$$
to be completed after names of arrows are fixed: $l,f$ are to be, say, $m1,m2$...

[Graphs as sketches]

A rather trivial example of a sketch is to consider any graph $G \in \cat{G}$ as a sketch $\discrete{G}$ with $\constr{\discrete{G}} = \emptyset$ (denoting the empty set).

It is easy to see that for any graph $X$, mapping _X/X is a fibration. Hence,

§.§ Makkai

§.§ ?

Arity of operation  hm, it'd be nice to show arrows 01, 32 as monics and place  symbol in $E$

[Diagram Algebra]

Let $\operationSig$ be an operation signature over predicate signature .
An $\operationSig$-algebra is a pair $A = (\carr{A}, {\semm{\_}}^A)$ that comprises a carrier sketch $\carr{A} \in \SS\eqdef \skecatgp$ and for each operation symbol $\opvar$, its  interpretation $\semm{\opvar}^{A}$ as a diagrammatic operation over $A$, , a mapping

\frar{\opInterpret{\opvar}{A}}{\SS(I_\opvar,\carr{A})}{\SS(E_\opvar,\carr{A})}

such that the following diagram commutes for any binding bI_A

\begin{equation}\label{eq:algviaE2}
\xymatrix{
I_\opvar \ar@{>->}[rr]^{IE_\opvar} \ar[dr]_b & & E_\opvar \ar[dl]^{\opInterpret{\opVar}{A}(b)} \\
& \carrier{A}
\end{equation}

§.§ makkai constr

The category $\iistarp$ is define as follows:

* Every object and morphism of $\II$ is also a member $\iistarp$, i.e. $\II \subseteq \iistarp$.

* Every object and morphism of $\predicateSig$ is also a member of $\iistarp$, i.e. $\predicateSig \subseteq \iistarp$.

*  Additionally, the class of morphism $\catArrows{\iistarp}$ in $\iistarp$ is extended with all triples $(P,a,H)$, in which
$P \in \catObj{\predicateSig}$,  $H \in \catObj{\II}$ and $a \in P^\arfun(H)$, and consider such triples as arrows aPH called mediating arrows.

Composition of arrows $\compose{f}{g}$ with both $f,g \in \catArrows{\II}$ or $\catArrows{\predicateSig}$ is retained by composition in  and $\predicateSig$ respectively.
Thus, it remains to define composition of “new” mediating arrows
with“old” arrows in  and .
There are two cases:

a) If $f$ is a new mediating arrow aPH and $\frar{g}{H}{H'} \in \catArrows{\II}$ is old, we define fg = P^(g)(a)PH' (, in Fig.(4), $\ovr{10}\comp\so=\ovr{1}$ ).

b) When $f$ is an old arrow $\frar{f}{P}{P'}\in\predsig$ and $g$ is a new arrow $\frar{\ovr{a}}{P'}{H}$ , we define
fg = f^(a)PH,[Recall that $\arfun$ is a contravariant functor],  (, in Fig.(4), $pre\comp\ovr{01} =\ovr{10}$).

It is easy to verify that  is again an :
For an object $H \in \II$ we assign the height $\depfun_\iistarp(H) = \depfun_\II(H)$, and for every $P \in \predicateSig$ we assign $\depfun_\iistarp(P) = N(\II) + \depfun_\predicateSig(P)$.
The construction is well defined since $\II$ and $\predicateSig$ are both h-categories and the only “new” elements in the construction above are mediating arrows from objects in $\predicateSig$ into objects in $\II$ such that acyclicity is preserved. Thus, we have a cospan of  inclusions:

\begin{equation}\label{eq:hcatcospan}
\II\rInto\iistarp\lInto\predsig
\end{equation}

§.§ Hierarchical things

[Acyclic and hierarchical categories]

a) 	A (small) category  is called acyclic if its carrier graphs $\carrcarr{\CC}_0$ is acyclic (such graphs are often called dags).
[Lawvere called a   one-way if all its endomorphisms are identities, , all $hom(X,X)$ are singletons. However, a one-way  still allows cycles consisting of isomorphic objects. Hence, a  is acyclic iff it is one-way and skeletal.
A (small) category  is called hierarchical (we also say  is an h-) if its set of objects is partitioned into a countable number of disjoint layers $\Ob{\CC}=\bigcup_{0\le n<\omega}C_n$ such that if $C_n=\varnothing$ for some $n$, then $C_{n'}=\varnothing$ for all $n'>n$. This defined a function ω, and we call the ordinal number $N=max\compr{\heifun(x)}{x\in\Ob{\CC}}$ the height of  and write $N=\heifun(\CC)$. Note that $\heifun(\CC)=\omega$ iff there are no empty layers.

Moreover, the following conditions hold for any two objects $x,y$ in : if $\CC(x,y)\noteq\varnothing$, then either $\heifun(x) <\heifun(y)$ or $x=y$, but in the latter case we require $\CC(x,x)=\{\id_x \}$. In addition, for any $n$ with $C_n\noteq\varnothing$ and any $x\in C_n$ there is at least one $x'\in C_{n-1}$ (called a (direct) parent of $x$) with $\CC(x,x')\noteq \varnothing$. Thus, all -arrows go down from higher to lower layers, the only arrows within a layer are identities, and each object with non-zero height has at least one direct parent. Note that we do not exclude the possibility of direct grand-parents, , arrow spanning layers.

An h-  is called horizontally finite (h-finite) if all layers are finite and for any pair $0\le m<n<\omega$, the set $\CC(m,n)=\bigcup_{x\in C_m, y\in C_n}\CC(y,x)$ is finite.  is vertically finite (v-finite) if it has a finite height.
Note that neither h- nor v-finiteness alone implies finiteness of the entire category, but together they do make an h- finite.

We will consider a finite dag as a layered set of vertexes $V=\bigcup_{n\inn\{0,1,...,N\}} V_i$ with arrows going down from a higher layer $V_n$ to a lower layer $V_m$, $m<n$.  We call elements of layer $V_n$ n-vertexes (cf. $n$-cells). We will also call 0-vertexes nodes and $(n>0)$-vertexes (hyper)edges or arcs.

[Sketch notation]
Sketches $S \in \skecatgp$ differ from graphs $G \in \GG$ in the sense that they additionally contain a set of diagrams, thus we will also refer to them as DP-graphs (with DP referring to Diagram Predicates). Diagrams a.k.a. constraints are visualized as annotations, i.e. a label showing the constraint name together with a set of edges (called tentacles) connecting the label with graph elements denoting the scope of the constraint, i.e. arity binding.
The figure below shows an example of a DP-graph containing two nodes $A$ and $B$, and two edges $f$ and $g$, together with a constraint named $1$ annotated with the predicate $[=]$ (whose arity is a pair of parallel arrows) and whose binding scope comprises the whole graph.
[If an arrow occurs in the scope of a constraint, its source and target nodes occur as well and the corresponding tentacles can be omitted.so, lets remove lines A-=-B]
still it'd better to have the graph bigger than the scope, say, add to the graph an arrow hBC. Even better would be to have yet another declaration of =, say, for a pair of arrows
k,lCD to show the diff between a predicate and a constr declaration.

[Families]Should go to Notation section
Given a set $X$, a family of $X$'s elements is a function

ffX whose domain is called the indexing set.

[Arrows in $\predsig$]
Readers, which familiar with the original formulation of predicate signatures by Makkai, may wonder why $\predicateSig$ is category rather than a set.
Thus, we want to elaborate on the meaning of the arrows in $\predicateSig$
Explain arrows in $\predicateSig$..

[Semantics for signatures]
A model for a signature  is a pair $A=( \carrier{A},\interpret{\_}{A})$ of a 'graph' $A \in \cat{G}$ and a family of 'valid tuples' p^Ap^A(p^, A)

for each $p\in\predsig$, obeying for each arrows $\arrow{p}{e}{p'} \in \predsig$

\[
%\dom(\interpret{p'}{A}) \subseteq \dom(\interpret{P}{A})
\carr{\interpret{p'}{A}} \subseteq \carr{\interpret{p}{A}}
\]

and for all $d \in \carr{\interpret{p'}{A}}$ the following diagram commutes:

\[
\xymatrix{
\arfun(p) \ar[rr]^{\arfun(e)} \ar[dr]_{\interpret{p}{A}(d)} & & \arfun(p') \ar[dl]^{\interpret{p'}{A}(d)} \\
& A &
\]

We can see a model as a collection of tables — one table per predicate symbol, whose column names (attributes) are elements of $p^\arfun$ and rows are elements of $\GG(p^\arfun, A)$, bindings of elements in the arity graph $\arityOf{p}$ with elements of $A$. Note that by defining $\interpret{p}{A}$ to be a family (multiset) rather than a set, we allow having multiple rows with the same values—this is usual practice of database systems.

§.§ for intro

There are two sources of motivation for this section: a) MDE and database applications in which the notion of query is omnipresent, and b) pure mathematics: what is the counterpart of sketches (as diagram theories over predicate signatures) for diagram operations, and how far could we develop a universal diagram algebra.

It tuns out that both motivational lines lead to the same construct, which we will call either query or DO-graph to recall the first or, resp. the second, motivational line. In the universal algebra view, queries are nothing but diagrammatic terms.

§.§ About Bindings Square Fibrations

Proof. i) Functor IE is a fibration. Given are a binding diagram  (whose projection on  is $IE^\dvar$) and a sq-arrow ^2IE^'IE^ (see the black part of the left diagram in bSqFacts). We need to build a binding diagram $\dvar'$ and a prism  ^4' such that its upper face is $\dmorvar^2$ — this is done with the blue-colour workflow in the left diagram in bSqFacts. Finally, we need to show that this blue thing is maximal amongst similar $\Rrightarrow$ – see the red workflow.

The right diagram in  bSqFacts shows a special case where $\dmorvar^2$ is diagonal – we will need it later for considering queries.

ii) Discrete fibration – see the green workflow.

iii) Fibr. . Pushout 3D-pasting lemma should work??

For the proof of lemma <ref>: lifting workflow

§.§ Transformations?

Diagrammatic Operationex:diagOp
Consider $\cat{G}$ to be the category of directed multigraphs and let $\boldsymbol{\Pi}$ a graph signature that contains a predicate [comp] whose arity graph is a triangle with the intended semantics that the third edge represents the composition of the other two edges.
The respective diagrammatic operation is given by the following sketch-inclusion:

\[
\resizebox{\linewidth}{!}{
\def\g#1{\save [].[rr]!C="g#1"*+<0.5em,4em>[F-:<3pt>]\frm{}\restore}%
\xymatrix{
& I & & &   & O \ar@{}[d]|(0.8){[comp]} & \\
\g1iv_1 \ar[r]_{ie_1} & iv_2 \ar[r]_{ie_2} & iv_3 \ar@{}[rr]^(.25){}="a"^(.75){}="b" \ar@{^{(}->} "a";"b" & & \g2iv_1 \ar[r]_{ie_1}<EMAIL_ADDRESS>& iv_2 \ar[r]_{ie_1} & iv_3
\]

Multiple diagrammatic graph operations can be organized into a signature $\Sigma$.
Now, given an object $G \in \cat{G}$, we may consider all possible executions of diagram operations on the carrier $G$.
We call this structure a (model) transformation language over $G$.
This terminology stems from the MBSE vernacular and we will soon understand its adequacy.
Transformation Languagedef:tl
Given a predicate signature $\boldsymbol{\Pi}$, diagrammatic operation signature $\Sigma$ and an object $G \in \catObj{\cat{G}}$, called carrier.
The $\Sigma$-transformation language $TL_\Sigma(G)$ over $G$ is given by:

models $\catObj{TL_\Sigma(G)} := \{m \mid m \in \catObj{G/\cat{G}}\}$, i.e. objects taken from the coslice category $G/\cat{G}$.

transformations $\catArrows{TL_\Sigma(G)} := (TL_\Sigma(G)(m_1,m_2))_{m_1,m_2 \in \absolute{TL_\Sigma(G)}}$, where a single class is defined by $TL_\Sigma(G)(m_1,m_2) := \{ \langle b,o \rangle \mid \exists o \in \Sigma : b \in m_1^{I_o} \wedge \mbox{the colimit apex of } m_1 \xleftarrow{b}  \inlineinclusionarrow{I_o}{}{O_o} \mbox{ is isomorphic to } m_2  \}$.

$TL_\Sigma(G)$ is categoryprop:tlCat

$TL_\Sigma(G)$ is a free objectprop:tlFree

$TL_\Sigma(G)$ has symmetric monoidal structureprop:tlSMC
$I = 1$, the terminal object in $\cat{G}$ and $\otimes = \times$ the cartesian product in $\cat{G}$ provides a symmetric monoidal structure on $TL_\Sigma(G)$

$TL_\Sigma(G)$ has initial and terminal objectslem:tlInitTerm
The initial object in $TL_\Sigma(G)$ is $G$ and the terminal object is $1$.

Follows trivially from Definition <ref> and the fact that $1$ is the terminal object in $\cat{G}$.

To be practically useful, we actually need some more or less technical operations:
unit, copy, counit and merge.
The unit provides a fresh carrier $G$, copy produces two copies of the input and is given by the diagonal $\Delta : G \mapsto (G,G)$.
The counit discards the input (by mapping to the terminal object) and merge fuses the results of two operations together (by taking the pushout).
These additional morphism do not violate the above theorems and we call the resulting augmentation $TL_\Sigma^+(G)$.
It follows that is posses some additional useful properties.

$TL_\Sigma^+(G)$ is cocompleteprop:tlPCoComplete

$TL_\Sigma^+(G)$ is compact closedprop:tlPCoComplete

Thus, the arrows $TL_\Sigma^+(G)$ represent all possible terms that we can built from the given operations in a signature $\Sigma$.
Every term can be represented as a string diagram.
We give a concrete example by formalizing an exogenous model transformation:

Model Transformationex:mt
Consider again the sketch presented in Example <ref>, which may serve as a metamodel for object-oriented class diagrams.
We now show how the canonical model transformation example: translating OO diagrams into relational database schemas is implemented in our framework.
For this we assume the existence of the following diagrammatic operations in addition to the already introduced composition in Example <ref>

\[
\def\h#1{\save [].[r]!C="g#1"*+<0.5em,1em>[F-:<3pt>]\frm{}\restore}%
\xymatrix @R=1em {
I_{proxy} & & O_{proxy} & \\
*+<1em,1em>[F-:<3pt>]{iv_1} \ar@{}[rr]^(.25){}="a"^(.75){}="b" \ar@{^{(}->} "a";"b" &  & \h1iv_1 \ar[r]_{oe_1}^{[proxy]} & ov_1
\]

\[
\def\h#1{\save [].[r]!C="g#1"*+<0.5em,1em>[F-:<3pt>]\frm{}\restore}%
\xymatrix  {
I_{connect} & &  & O_{connect} & \\
\h1iv_1 & iv_2 \ar@{}[rr]^(.25){}="a"^(.75){}="b" \ar@{^{(}->} "a";"b" &  & \h2iv_1 \ar[r]_{oe_1}^{[connect]} & iv_2
\]

\[
\def\k#1{\save [].[dr]!C="g#1"*+<1em,1em>[F-:<3pt>]\frm{}\restore}%
\xymatrix {
I_{close} &  &  & O_{close} & \\
\k1iv_1 \ar[r]^{ie_1} & iv_2  \ar@{}[dr]^(.5){}="a"  &  & \k2iv_1 \ar@{}[dl]^(.5){}="b" \ar@{^{(}->} "a";"b" \ar@{}[dr]|{[comm]} \ar[r]^{ie_2} & iv_2 \\
iv_3 \ar[r]_{ie_3} \ar[u]^{ie_2} & iv_4 & & iv_3  \ar[r]_{ie_3} \ar[u]^{ie_2} & iv_4 \ar[u]_{oe_1}
\]

with the intended semantics that proxy freely creates a new proxy object for every given input object together with the respective mapping,
connect acts similar with the difference that the target type already exists and close adds the missing mapping such that the resulting square becomes commutative.
We argue that these four operations suffice to perform the object to relational transformation.
TODO Here we need basically a good visualization and naming convention to make it understandable. The process is rather clear: First Proxy is applied to UserType, Attribute and Association to create Tables, Columns, and ForeignKeys resp. Connect is used to create the primary key column connection and close is used to establish consistency of column membership in the correct table etc.

Note, that diagrammatic operation create diagrams when they are applied.
Thus, we can on the fly verify that whether the model transformation is correct.

The following is already covered in the introduction.

We begin with an informal discussion. The arity of a diagrammatic operation   is given by an inclusion of graphs ^I_E_ whose domain is called the Input and the codomain is the scopE of the operation. For example, if  is arrow composition, $\opvar=\comppred$, then the  input graph is some fixed pair of consecutive (composable) arrows and the scope graph is the  triangle. If  is pullback, $\opvar=\pbpred$, then the  input graph is some fixed arrow opspan and the scope is the  square, in fact, the square plus its diagonal, , a cone.  If we want to consider pullbacks only defined for cospans whose first leg is monic (and the respective leg of the resulting span is also monic), $\opvar=\pbmpred$, then we need to require the input and scope of  to be sketches (in the signature $\predsig=\{\monicpred \}$) rather than graphs, and the arity inclusion $\pbmpred^\arfun$ is a -sketch , , a sketch inclusion. We may also want to consider the universal property of pullbacks as an operation, whose input encompasses two squares over the same opspan, one is declared to be a pullback and the other is declared commutative, and thus the input is a sketch in the signature $\predsig=\{ \nfont{pb,=_{squ} }\}$. The scope consists of those two squares plus a unique mediating arrow between their  vertexes, and two commutativity declarations for the corresponding triangles, and thus the scope is a sketch in the signature $\predsig'= \{ \nfont{pb,=_{squ},=_{tri}}\}$. The arity of this operation is a $\predsig'$-sketch inclusion.

For several definitions below, we fix a () category  as the schema for 'graphs',
$\GG=\setcat^\II$  is the corresponding presheaf topos,  a predicate signature over , and $\SS=\skecatgp$ is the  presheaf topos of sketches.

\begin{equation}\label{eq:alg-disc-fibr}
\begin{array}{c} %@{\qquad}c}
%	& % 2nd diag
\xymatrix{
% row 1
\LDiagr{B}
\ar@[blue]@/_5pc/@{-->}[dddd]_{\labell_B}
\ar@{-->}[rrr]^{\bind_B}%{\arfun'_B}
\ar[dr]^{\semm{}_B}
%\ar@{-->}[dd]_{(\proj{IE})'} %{\olabel}
& \msquareXCat{\carr{B}}{\SS}
\ar@/^5pc/@{->}[dddd]^{\proj{IE}}
\ar@{->}[dl]^{\proj{E}} %{\olabel}
\\  %row 2
& %\pointedDownarrowCat{\carr{B}}{\SS}
\mtriangleXCat{\carr{B}}{\SS}
\ar[r]^(0.6){\proj{II}}
&	\pointedDownarrowCat{\carr{B}}{\SS}
\\ % row 3
\LDiagr{A}
\ar@[red]@{->}[uu]^-{\textcolor{red}{h!}}
%\ar@{->}[uu]_{!} %{\olabel}
\ar@{-->}[rrr]^{\bind_A} %{\arfun'_A} %{\bind\quad}
\ar[dr]^{\semm{}_A}
\ar@{-->}[dd]|{\labell_A} %{\olabel}
& \msquareXCat{\carr{A}}{\SS}
\ar@[red]@{->}[uu]^-{\textcolor{red}{h^\square}}
\ar[dd]^{\proj{IE}}
\ar@{->}[dl]_{\proj{II}}
\\  %row 4
& %\pointedDownarrowCat{\carr{A}}{\SS}
\mtriangleXCat{\carr{A}}{\SS}
\ar[drr]_{\proj{IE}}
\ar[r]^(0.6){\proj{II}}
\ar@[red]@{->}[uu]^-{\textcolor{red}{h^\triangle}}
\ar@[red]@{->}[uu]^-{\textcolor{red}{\_\comp h}}
\\   % row 5
\opsig \ar[rrr]^\arfun
\monicarrowCat{\SS} %\ar[ul]^\cod
\\
%	\text{a) Semantic definition (presheaf style)}
%	&
\text{Algebra moprhism --ver.1}
%	\\
%	&\text{\zd{\parbox{5cm}{it should be like \eqref{skedef}
%				to expalin the diff between all facts and true facts}}
\end{array}
\end{equation}

\begin{equation}\label{eq:alg-disc-fibr-2}
\begin{array}{c} %@{\qquad}c}
%	& % 2nd diag
\xymatrix{
% row 1
\LDiagr{B}
\ar@[blue]@/_5pc/@{-->}[dddd]_{\labell_B}
\ar@{-->}[rrr]^{\arfun'_B}
\ar[dr]^{\semm{}_B}
%\ar@{-->}[dd]_{(\proj{IE})'} %{\olabel}
& \msquareXCat{\carr{B}}{\SS}
\ar@/^5pc/@{->}[dddd]^{\proj{IE}}
\ar@{->}[dl]^{\proj{E}} %{\olabel}
\\  %row 2
& \pointedDownarrowCat{\carr{B}}{\SS}
\ar[r]^(0.7){\dom_{\carr{B}}}
\\ % row 3
\LDiagr{A}
\ar@{->}[uu]_{!} %{\olabel}
\ar@{-->}[rrr]^{\arfun'_A} %{\bind\quad}
\ar[dr]^{\semm{}_A}
\ar@{-->}[dd]|{\labell_A} %{\olabel}
& \msquareXCat{\carr{A}}{\SS}
\ar[uu]_{h^\square}
\ar[dd]^{\proj{IE}}
\ar@{->}[dl]^{\proj{E}} %{\olabel}
\\  %row 4
& \pointedDownarrowCat{\carr{A}}{\SS}
\ar@{->}[uu]^-{\_\comp h}
%\ar[uu]^(0.5){\_\comp h}
\ar[r]^(0.7){\dom_{\carr{A}}}
\\   % row 5
\opsig \ar[rrr]^\arfun
\monicarrowCat{\SS} \ar[ul]^\cod
\\
%	\text{a) Semantic definition (presheaf style)}
%	&
\text{Algebra \mor\- ver.2 (equiv.)}
%	\\
%	&\text{\zd{\parbox{5cm}{it should be like \eqref{skedef}
%				to expalin the diff between all facts and true facts}}
\end{array}
\end{equation}

The above is a presheaf-style definition. Its fibrational counterpart is the following definition. An algebra $A$ is given by

a) its carrier sketch  $\carr{A}\in \SS$, which gives rise to a pullback square shown in the left part of alg-discb. Its apex is the set of all correctly labelled binding diagrams over A.

b) a mapping $\semm{}_A$ as shown by the curved arrow such that the outer rectangle commutes.

It is easy to see that the diagram alg-discb is just a rephrasing of alg-disca in the monadic-style manner with $LDiagr(A)$ playing the role of a monad.

If  is a signature with pre- but without post-condition dependencies (, category $\opsigEE$ is derived from $\opsigIE$ and thus not needed in the definition), then by considering diagram alg-discb in  rather than   we obtain diagrammatic algebras for signatures with only pre-dependencies.

§.§ ===========

§.§ Example of a query

Consider again the example depicted in Figure <ref> and this time especially at sub figure <ref>.
It makes the application of the three pullback operations (shown as chevrons) including their in- and output (shown as arrows) explicit.
Furthermore, we visually distinguish elements that are given (colored black) and those computed by operations (colored blue).
A straightforward way of formalizing this concept is by utilizing existing sketch machinery.

§.§ intro piece for complex q

We will begin with an example showing what a query is and how queries are often encoded (queryexample). Then we will formalize queries as graphs with diagram operations (DO-graphs in short).  We will first consider atomic (or elementary) queries and then proceed to complex queries/DO-graphs. For the latter, we will give two formalizations: the first is data-centric, in which queries are encoded as sketches (similarly to encoding equational theories and algebras by Horn predicate logic ), and the second is workflow-centric, in which a query is seen as a workflow (similarly to seeing terms as abstract syntax trees)

§.§.§ Playing with signatures as fibrations

see text below the endinput

(A) Long ago I played with some abstract spec of sketches but now I know cat patterns better, and found interesting things.

Def. A morphism (map) of predicate signatures is a functor commuting with arities. In other words, the category of pred signatures  is the slice category $\catCat/\GG$.

Now we redefine a sketch map as a triple f=(f,f,f)SS' where $\abs{f}$ as above, f' a signature map, and f is as above but now we require  $\compose{\constrfun{f}}{\labell'}=\compose{\labell}{\psigfun{f}}$ (, the square rather than the triangle commutes).  This gives us a   equipped with two functors, , a span in :

\begin{equation}\label{eq:fibspan}
\psigcat\lTo^{sig} \skecat\rTo^{\abs{\_}}\GG
\end{equation}

The left leg is a (split) fibration, whose lifts are vertical wrt. the second functor (, are carrier identities). Dually, the right functor is a (split) opfibration, whose lifts are vertical wrt. $\abs{\_}$ (signature identities). (This nice correspondence could be called orthogonality. Moreover, most probably, the span should satisfy one more condition (a version of Beck-Chevalley):

for any sketch  $S\in\abs{\skecat}$  with signature $\predsig=sig.S$ and carrier $G=\abs{S}$,  and arrows u∙, vG∙,
there is a unique isomorphism

\begin{equation}\label{eq:BC}
S.u^*.v_* \cong S.v_*.u^*
\end{equation}

Then it will be a gadget called Street fibration. This gadget under the name fibred span is defined by Jacobs in his book (Def. 9.1.5 on p.514) but his condition (b) seems to be not the same as the Beck-Chevalley above; and Jacob's formulation is awkward, so, let's use (<ref>).

The span representation (<ref>) is a sort of a proper general view of logical theories: each of them (a sketch) must have a) a signature and b) a carrier object (of variables) providing connectivity, which play dual roles (fibration and opfibration) for theory maps – I think that this general philosophy should be more or less explicit in Jacobs book. Jacobs also shows a version of Grothendieck: any fibred span is equivalent to a functor

\begin{equation}\label{eq:fibgroth}
\frar{\skefun}{\psigcat^{op}\times\GG}{\catCat}
\end{equation}

so that  in (<ref>) is $\int \skefun$. We should have a similar fibred span description of diagram algebra, but for algebra it should be something richer.

(B) Another useful description of sketches is this. Any sketch $S$ can be see as a predicate symbol with arity $\abs{S}$.
Then the category $\skecat(\predsig)$ can be seen as a big signature whose arrows are sketch morphisms. We thus have a functor . I proved (long ago) that this functor is a monad over .

View composition 1

[View composition]
Views can be associatively composed and make a category

the proof should go along the lines of kleislicat-2.

View composition 2

§.§ ===========

[Diagram Algebra Morphism]
Given two multialgebras $A, A'$, their   fAA' is a pair of mappings fAA' and f_AA' such that
to be completed to subsume the def below

Let $\operationSig$ be a operation signature and $A$ and $B$ be two $\opsig$-algebras.
An algebra morphism $\arrow{A}{f}{B}$ is given by a sketch morphism $\arrow{\carrier{A}}{\carrier{f}}{\carrier{B}}$ obeying

\begin{equation}
\label{eq:diagAlgebraMoprhism}
\opInterpret{\opVar}{B}_{IE}(\compose{b}{\carrier{f}}) = \compose{\opInterpret{\opVar}{A}_E(b)}{\carrier{f}}
\end{equation}

for all $b : \inputArity{\opVar} \to \carrier{A}$. Diagrammatically:

\[
\xymatrix{
I_\opvar \ar@{>->}[rr]^{IE_\opvar} \ar[dr]_b \ar@/_/[ddr]_{\compose{b}{\carrier{f}}} & & E_\opvar \ar[dl]^{\opInterpret{\opVar}{A}_{IE}(b)} \ar@/^/[ddl]^{\opInterpret{\opVar}{B}_{IE}(\compose{b}{\carrier{f}})} \\
& \carrier{A}  \ar[d]^{\carrier{f}} & \\
& \carrier{B} &
\]

[Algebra category]
All $\opsig$-algebras and their morphisms form a category $\GG||\predsig||\opsig$ supplied with a forgetful functor alg2ske||||.

to be revised
Follows immediately from the fact that $\skecatgp$ is a category and the identity in Eq. <ref> is transitive.

[Universal algebra cont'd]
Hence, categories ... and  ..... are isomorphic. Thus, diagram algebra subsumes universal algebra.

§ NOTATION AND TERMINOLOGY

§ PROOFS

§.§ Hypercat structure?

Our next goal is to build an sm-category from DOI-sketches.
To do this we employ the idea of decorated cospans <cit.> since DOI-sketches (Def. <ref>) already provide us with a cospan and recite the central notion below:

From now on, we assume that our signatures of operation symbols are finite. (Or another finiteness condition is to be assumed to avoid size problems below.)
decoratedCospanDecorated Cospans
Let $\cat{C}$ be a category with finite colimits, and $(\decfun, \dectra) : (\cat{C}, +) \to (\catSet, \times)$
be a LAX symmetric monoidal functor (see smfunctor in Appendix <ref>) called the decoration functor.
An ($\decfun$-)decorated cospan is a pair consisting of a cospan $A \xrightarrow{i} N \xleftarrow{o} B$ in $\cat{C}$ together with an element $s \in \decfun(N)$ called the decoration.

Consider forgetful functor
that strips an operational sketch over $(\opsig,\predsig)$ of its -diagrams (see (<ref>) on p.eq:forgetfultriangle  above). It gives rise to an inverse  mapping

that assigns to any predicate -sketch $S$, the SET of all possible operational sketches over it:

\decfun_\opsig(S) =\comprcolon{\opske\in\Ob{\opskecatgpo}}{F_\opsig(\opske)=S}

It is easy to see that an DOI-sketch in the signature  (over ) is nothing but a $\decfun_\opsig$-decorated cospan. Hence, to make the decorated cospan  applicable, we need to find the comparison  $\delta_\opsig$ and prove that

\frar{(\decfun_\opsig, \delta_\opsig)}{(\skecatgp,+)}{(\catSet,\times)}

is a lax sm-functor.

We provide the presentation how DOI graphs fit into the decorated cospan framework in two steps.
First, we will define a suitable decoration functor and afterwards reformulated the definition of DOI-sketches in terms of Def. <ref>.
This requires a few technical definitions

specialOSketchPropsOperational sketch properties
Let $\opsig$ be an operation signature over $\predsig$ and $S \in \skecatgpo $ a sketch w.r.t $\oppredsig$.
We define two functions

\begin{eqnarray}
ins : \begin{cases}
\catObj{\constr{S}} \to \powerset{\carrier{S}} \\
c \mapsto \{ x \in \carrier{S} \mid x \in \image{\compose{IE_{\labell(c)}}{\bind}} \}
\end{cases} \\
outs : \begin{cases}
\catObj{\constr{S}} \to \powerset{\carrier{S}}  \\
c \mapsto \{ x \in \carrier{S} \mid x \in \image{\compose{OE_\labell(c)}{\bind}} \}
\end{cases}
\end{eqnarray}

which, given a diagram $c \in \constr{S}$ with $\labell(c) \in \opsig$, returns a set of all carrier elements in the input and output scope respectively (for a diagram $c'$ with $\labell(c) \in \predsig$ it will just return the empty set).
Furthermore, we define a relation $\prec \subseteq \catObj{\constr{S}} \times \catObj{\constr{S}}$ that is defined on a pair $(c, c')$ iff. there exists an element $x \in outs(c) \cap ins(c)$. The transitive and reflexive close is denoted $\preceq$.

The sketch $S$ is said

* to have no confusion w.r.t. produced elements when every element is in the output scope of at most one operation diagram, i.e. for each $c, c' \in \constr{S}$ and any element $x \in outs(c) \cap outs(c')$ if follows that $c = c'$.

* to have no junk w.r.t. a subgraph $G \subseteq \carrier{S}$ when for every additional element there exist an operation producing it, i.e. for each  $x \in \carrier{S} \setminus G$ there exists a diagram $c \in \constr{S}$ such that $x \in outs(c)$.

* to have no cycles w.r.t. operation applications when every operation diagram does not depend on elements transitively produces by itself, i.e. $\preceq \subseteq \catObj{\constr{S}} \times \catObj{\constr{S}}$ is a partial order.

The def. above seems conceptually wrong: the three conditions look like as a reformulation of the notion of a DO-sketch defined above, that is, this def. should be a theorem that any DO-sketch also has properties above. Also, why you work with objects only? It's easy to see that for any $c\in Constr(S)$ such that $pred(c)\in\opsig$ we have the entire square diagram $\Square\rightarrow\skecatgp$ as explained in Lemma <ref>.  It all was written, or am I missing the point?

opDecoratorOperation Decoration
Let $\opsig$ be an operationg signature.
We define a sm-functor $(\decorator, \phi) : (\skecatgp,+) \to (\catSet, \times)$ as follows:Object mapping: Let $S \in \skecatgp$ be a sketch, $\decorator$ assigns to $S$ a set $\{ S' \mid S' \in \skecat{\GG}{\oppredsig} \}$ for which

* The carrier of each $S' \in \decorator(S)$ is equal to $S$, i.e. $\carrier{S} = \carrier{S'}$

* For each $S' \in \decorator(S)$, the diagrams of $S$ is a subobject of the diagrams in $S'$ added diagrams are mapped to operation symbols, i.e. $\constr{S} \subseteq \constr{S'}$ and for all $c \in \constr{S'} \setminus \constr{S}$ it holds $\labell(c) \in \opsig$.

*  Every $S' \in \decorator(S)$ has no confusion.

*  Every $S' \in \decorator(S)$ has no cycles.

Arrow mapping: Let $S = (\carrier{S}, \constr{S})$ and $T = (\carrier{T}, \constr{T})$ be two sketches in $\skecatgp$ and $\arrow{S}{f}{T}$ be a sketchmorphism.

\begin{equation}
\decorator(f) : \begin{cases}
\decorator(S) \to \decorator(T) \in \catArrows{\catSet} \\
(\carrier{S'}, \constr{S'}) \mapsto (\carrier{f}(\carrier{S'}), \constr{T'})
\end{cases}
\end{equation}

where $\constr{T'}$ is given by the pushout object in the following diagram:

\begin{equation}
\xymatrix{
\constr{S} \ar[d]_{\constr{f}} \ar@{^{(}->}[r] & \constr{S'} \ar[d]^{\constr{f}^*} \\
\constr{T} \ar@{^{(}->}[r] & \constr{T'}
\end{equation}

To verify that this mapping is well-defined note that $\constr{T'}$ is a pushout object, thus every diagram $c$ in $\constr{T'}$ either stem from $\constr{T}$ or $\constr{S'}$ (or both). If it stems from $\constr{T}$ is must be necessarily mapped to a predicate, i.e. $\labell(c) \in \predsig$, and thus unaffected by <ref> and <ref>. If it stems from $\constr{S'}$ note that $S$ has to already fulfill  <ref> and <ref> by the definition of $\decorator$ on object. Coherence Maps:
The value of $\phi_{\boldsymbol{I}}$ is the empty sketch $(\emptyset, \emptyset)$ since there are elements that operation diagrams can be bound to.
We may need the requirement that the scope of an operation must not be empty.
The definition of the coherence maps w.r.t. monoidal product is straighforward and it is easy to see that it is both well-defined and compatible with associators, unitors, and symmetries.

\begin{equation}
\phi_{S,T} = \begin{cases}
\decorator(S) \times \decorator(T) \to \decorator(S + T) \\
( (\carrier{S}, \constr{S}), (\carrier{T},\constr{T} ) \mapsto ( \carrier{S} + \carrier{T}, \constr{S} + \constr{T} )
\end{cases}
\end{equation}

This functor is indeed a decoration in a sense that it takes a sketch $S$ over $\predsig$ as input and produces the set of all sketches over $\oppredsig$ that can be produced by adding arbitrary operation diagrams to $S$ obeying the no-confusion and no-cycle properties.

doiDecoratedDOI-graphs as Decorated Cospan (Reformulated)
A DOI graph is given by a cospan $I \overset{i}{\hookrightarrow} K \overset{o}{\hookleftarrow} O$ of monomorphism in $\skecatgp$ and a sketch $S \in \decorator(K)$ (the decoration) obeying

*  $S$ has no-junk w.r.t. $I \subseteq K$.

Not that the no-junk condition in Def. <ref> and the no-confusion condition imposed by $\decorator$ ensure conditions a) and b) in Def.<ref> to hold.
And the no-cycle condition imposed through $\decorator$ directly implies c) in Def.<ref>.
Thus, Definitions <ref> and <ref> are equivalent.

Composition of DOI-graphs (Definition <ref>) theo:wellDefined
DOI graphs can be composed via pushouts.

Let $(I_l \overset{i_l}{\hookrightarrow} K_l \overset{o_l}{\hookleftarrow} O_l, S_l \in \decorator(K_l))$ and $(I_r \overset{i_r}{\hookrightarrow} K_r \overset{o_r}{\hookleftarrow} O_r, S_r \in \decorator(K_r))$ be two DOI-graphs.

\begin{equation}
\xymatrix{
& & K \ar@{}[dd]|{(1)} & & \\
& K_l \ar[ur]^{u} & & K_r \ar[ul]_v & \\
I_l \ar@{^{(}->}[ur]^{i_l} &  & O_l = I_r \ar@{_{(}->}[ul]_{o_l} \ar@{^{(}->}[ur]^{i_r} & & O_r \ar@{_{(}->}[ul]_{o_r}
\end{equation}

Consider the diagram above where (1) is given by pushout.
Since $\skecatgp$ is a topos and thus adhesive and pushouts therefore preserve monomorphisms $u$ and $v$ are both mono and can be chosen as inclusions.
Therefore, we get a composite $I_l \overset{\compose{i_l}{u}}{\hookrightarrow} K \overset{\compose{o_r}{v}}{\hookleftarrow} O_r$.
The decoration object $S \in \decorator(K)$ for thus cospan is produced by $S = \decorator([u,v])(\phi_{K_l,K_r}(S_l,S_r))$.
It remains to show that is satisfies <ref>.
We will proof this by contradiction and assume there is an element $x \in \carrier{K} \setminus I$ such that there is no $c \in \constr{S}$ with $c \in outs(c)$.
Because $K$ is a pushout object and the hypothesis it most hold that $x \in \carrier{K_r}$ and further $x \in \carrier{I_r}$ because of the no-junk property of the right DOI-graphs co-span.
The element must have an image under $\carrier{o_l}$ denoted $x'$ and because of the no-junk property of the left DOI co-span there most be some diagram $c' \in \constr{S_l}$ such $x' \in outs(c')$.
The sketch morphism $\arrow{S_l}{\decorator(u)}{S}$ must preserve the definedness of this diagram which however contradicts the hypothesis.

Finally, we want to return to a more abstract level and put our work in context with other recent trends in Applied Category Theory, namely SMCs and String Diagrams, cf. Appendix <ref>.
We mentioned earlier that diagrammatic queries, i.e. DO-graphs or equivalently DO-workflows, are the diagrammatic equivalent of a term.
Thus, they could be represented as a category.
intervalSketchesPredicate Interval Sketches
Let $\predicateSig$ and $\mathcal{Q}$ be two predicate signatures and let $\predicateSig$ be a subcategory of $\mathcal{Q}$.
We define a category $\intervalskecat{\GG}{\predicateSig}{\mathcal{Q}}$:
Its objects being all sketches $S \in \skecat{\GG}{\predicateSig'}$ for any predicate signature $\predicateSig'$ such that  $\predicateSig \subseteq \predicateSig' \subseteq \mathcal{Q}$.
A hom-set $\homset{\intervalskecat{\GG}{\predicateSig}{\mathcal{Q}}}{S}{S'}$ for objects $S \in \skecat{\GG}{\predicateSig'}$ and $S' \in \skecat{\GG}{\predicateSig''}$ contains all $\skecat{\GG}{\predicateSig'}$ between $S$ ans $S'$.

Initial objects in $\intervalskecat{\GG}{\predicateSig}{\mathcal{Q}}$prop:initialObjectsIntervalSkeCat
$\intervalskecat{\GG}{\predicateSig}{\mathcal{Q}}$ has an initial object $\boldsymbol{0}$.
Its carrier $\carrier{\boldsymbol{0}}$ is the initial object $\emptyset$ in $\GG$ and its diagrams $\constr{\boldsymbol{0}}$ is the empty category.

Obviously there is a unique morphism into every object of $\intervalskecat{\GG}{\predicateSig}{\mathcal{Q}}$, which immediately arises from the initial object properties of carrier and constraints in $\GG$ and $\catCat$.

Pushouts in $\intervalskecat{\GG}{\predicateSig}{\mathcal{Q}}$prop:pushoutIntervalSkeCat
$\intervalskecat{\GG}{\predicateSig}{\mathcal{Q}}$ has pushouts for every span of $\intervalskecat{\GG}{\predicateSig}{\mathcal{Q}}$ -morphisms.

$\intervalskecat{\GG}{\predicateSig}{\mathcal{Q}}$ is adhesiveprop:intervalSkeCatAdhesive
See Appendix <ref>.

TODO: Show existence of pullbacks along monos and Van-Kampen property

doGraphCoSpanDO-graph Co-Span representation
Every DO-graph $D$ according to Def.<ref> is actually a co-span of inclusion morphisms in $\intervalskecat{\GG}{\predicateSig}{\oppredsig}$ where the apex is subject to the additional conditions <ref> and <ref> in Def.<ref>.

DO-graph compositionprop:doGraphComp
Let $D$ and $E$ be two DO-graphs represented as co-spans, cf. Def.<ref> where $\doGraphOutput{D} = \doGraphInput{E}$.
We can define their composite $\compose{D}{E}$ with co-span composition by pushouts and the result is a DO-graph:

Due to proposition <ref> the square (1) exists, yielding $u$ and $v$.
Due to proposition <ref>, the pushout (1) preserves monomorphisms such that $u$ and $v$ are monic and since pushouts are determined up to isomorphism, we can chose $u$ and $v$ as inclusions.
It remains to show that the conditions  <ref> and <ref> from Def.<ref> are fulfilled.
The latter is a TODO

DO-graph categoryprop:doGraphCat
For any predicate signature $\predicateSig$ and $\operationSig$, there exists a category $\doGraphCat{\predicateSig}{\operationSig}$ whose objects are sketches in $\intervalskecat{\GG}{\predicateSig}{\operationSig}$ and arrows are DO-graphs.

Unitality and Associativity are immediately given because pushouts preserve identities and their application is associative.

The equivalence of DO-graphs and DO-workflows lifts to the categorical level:

$\doGraphCat{\predicateSig}{\operationSig} \equiv \doWFCat{\predicateSig}{\opsig}$corr:dogDowEquiv
The parsing-mapping from Theorem <ref> extends to an identity on objects functor which is an equivalence.

$\doGraphCat{\predicateSig}{\opsig}$ is a hypergraph categorytheo:hypergraphCat

Follows immediately from propositions <ref>, <ref> and <ref>.

This last theorems allows us to interpret diagrammatic queries in a SMC, which can be visualized as a String Diagram.

termalgTerm Algebra
Given a sketch $X$ of variables and an operation signature , we build...

Term Algebra Adjunctiontheo:adjunction
There is an adjunction $\mathsf{T} \dashv \mathsf{U}$ with $\mathsf{U}: \catOpsigAlg{\skecatgp}{\opsig} \to \skecatgp$ being the (forgetful) projection on the underlying carrier and $\mathsf{T}: \skecatgp \to \catOpsigAlg{\skecatgp}{\opsig}$ being the (free) term algebra functor over a sketch.

Was basically given in <cit.>.
We have to adapt it to the slightly changed situation, though.

Oops: at this point, we are very far from this result. We need first to define what is a term=complex query over a sketch $X$, and show that the set of all terms over $X$ is an -algebra $T_\opsig(X)$. Then we need to show that the mapping $X\mapsto T_\opsig(X)$ is functorial (and I expect it could be a hassle). Only after that we are ready to prove that there is an adjunction.