A conjunctive query over schema $C$.

When this query is used as part of a call to migrate, the diagram will be composed with an acset and its limit will then be computed in $Set$.

See also: GlueQuery, GlucQuery


A contravariant data migration whose underlying functor $F$ may not be fully defined.

Instead, the migration F⋅X for an acset X can only be constructed once we have access to X's attributes and homs. The dictionary of parameters contains anonymous functions acting on $X$'s attributes using Julia functions defined on these attribute types.


"Gluc query" (gluing of conjunctive queries) over schema $C$.

The diagram of diagrams comprising the query specifies a finite colimit of finite limits. In the important special case that the outer diagram has discrete shape, it specifies a finite coproduct of finite limits and the query is called a "duc query" (disjoint union of conjunctive queries).

See also: GlueQuery, GlucQuery


Gluing or agglomerative query over schema $C$.

The diagram comprising the query specifies a finite colimit. In the important special case that the diagram has discrete shape, it specifies a finite coproduct and the query is called "linear" or "disjunctive".

See also: ConjQuery, GlucQuery


A diagram representing a (conjunctive, duc, gluing, or gluc) query.

Besides the diagram functor itself, a QueryDiagram contains a dictionary params of query parameters. The keys of params are the hom_generators of the target schema C on which the diagram is not fully defined until a migration is executed. The values are either Functions or constants. If Functions, then these values will have one argument for each hom_generator of the target schema D and return a further function of one argument.

When an ACSet $X$ is migrated via a QueryDiagram, the Functions in params are evaluated on the FinDomFunctions in $X$'s range, and the resulting one-variable functions are either pasted directly into the migrated ACSet $Y$, or else composed with intermediate FinDomFunctions defined by migrating $X$ using only the inner diagram. If the keys of params are constants then $Y$ will receive constant attributes at the corresponding values.


Construct a QueryDiagram based on the Functor F and with parameter dictionary params.

The type parameter T may be id, op, or possibly co or Any, though not all functionality is defined for co and not all functionality is definable for Any. Other type parameters are inferred from the type of F. The type C of the codomain F will in practice be a subtype of FinCat or of Diagram{T}.


A DiagramHom that may be partially-defined, to be evaluated later using the dictionary params of parameters.

As with QueryDiagrams, params will be a dictionary of Functions or perhaps constants. A QueryDiagramHom is expected to live inside a DataMigration M and to be fully evaluated whenever migrate is called on M and some ACSet X.

How this works is that the partially-defined DiagramHom consisting of shape_map, diagram_map, and precomposed_diagram is whiskered with X (except where it's undefined), and then the functions in params are used to fill in the gaps.

See also QueryDiagram, param_compose

QueryDiagramHom{T}(shape_map, diagram_map, precomposed_diagram, params)

Construct a QueryDiagramHom of variance T and fields the given arguments, with further type parameters inferred.


Build a QueryDiagramHom with variance T by first building a DiagramHom using args..., then adding the params.

There are many methods of DiagramHom allowing various calling conventions, and this allows QueryDiagramHom to steal them all reasonably efficiently.


Whisker a partially-defined DiagramHom with a Functor, using the dictionary params to fill in any gaps.

While QueryDiagramHoms have internal params for a similar purpose, it is sometimes necessary to borrow params from a QueryDiagram or DataMigration containing f, which is the functionality enabled here.

See also: param_compose


Lazily compose a diagram with parameters (see QueryDiagram) with a Functor.

The result is not evaluated, so the returned QueryDiagram may remain partially defined with parameters still to be filled in.

See also: force, QueryDiagram


Force-evaluate a partially-defined FinDomFunctor by using Functions in params to fill in undefined entries of F's hom_map.

If Obtype and Homtype are specified, then the returned functor is guaranteed to have exactly those value types in its ob_map and hom_map.


Force-evaluate the d.diagram for a QueryDiagram d.

The result is a SimpleDiagram, and in particular the inner call to force attempts to use d.params to produce a fully-defined FinDomFunctor.


Interpret conjunctive data migration as a colimit of representables.

Given a conjunctive data migration (a functor J → Diag{op}(C)) and the Yoneda embedding for C (a functor op(C) → C-Set computed via yoneda), take colimits of representables to construct a op(J)-shaped diagram of C-sets.

Since every C-set is a colimit of representables, this is a generic way of constructing diagrams of C-sets.


Whisker a partially natural transformation α with a functor H, given any needed parameters params specifying the functions in H's codomain which the whiskered result should map to.

Currently assumes the result will be a totally defined transformation.


Counts anonymous objects and homs to allow them unique internal refs. Tracks names of objects to avoid multiple objects with the same name. Doesn't track names for homs since it doesn't matter for eg free diagrams; macros like fincat will handle hom uniqueness for themselves.

Note that ob_over[x] is the object of the base which x is over, perhaps confusingly.


Left-most argument plus remainder of left-associated binary operations. ops denotes the operations that won't need to be reversed for the desired parser output (AST.Apply or AST.Coapply).


If d,d' are singleton diagrams and f hasn't yet been specified, make a DiagramHom with the right domain, codomain, and shape_map but the natural transformation component left as GATExpr{:zeromap} for now. Otherwise just wrap f up as a DiagramHom between singletons.


Limit fragment: initial parsing for homs between conjunctive diagrams and/or single objects. The components of the output AST encode both the functor and natural transformations parts of a diagram morphism, so it's semantically non-obvious whether they should be ObExprs or HomExprs; we choose the former somewhat arbitrarily.


Parse a contravariant data migration from a Julia expression.

The process kicked off by this internal function is somewhat complicated due to the need to coerce queries and query morphisms to a common category. The high-level steps of this process are:

  1. Parse the queries and query morphisms into intermediate representations (DiagramData and DiagramHomData) whose final types are not yet determined.
  2. Promote the query types to the tightest type encompassing all queries, an approach reminiscent of Julia's own type promotion system.
  3. Convert all query and query morphisms to this common type, yielding Diagram and DiagramHom instances.

Present a diagram in a given category.

Recall that a diagram in a category $C$ is a functor $F: J → C$ from a small category $J$ into $C$. Given the category $C$, this macro presents a diagram in $C$, i.e., constructs a finitely presented indexing category $J$ together with a functor $F: J → C$. This method of simultaneous definition is often more convenient than defining $J$ and $F$ separately, as could be accomplished by calling @fincat and then @finfunctor.

As an example, the limit of the following diagram consists of the paths of length two in a graph:

@diagram SchGraph begin
  (e₁, e₂)::E
  (t: e₁ → v)::tgt
  (s: e₂ → v)::src

Morphisms in the indexing category can be left unnamed, which is convenient for defining free diagrams (see also @free_diagram). For example, the following diagram is isomorphic to the previous one:

@diagram SchGraph begin
  (e₁, e₂)::E
  (e₁ → v)::tgt
  (e₂ → v)::src

Of course, unnamed morphisms cannot be referenced by name within the @diagram call or in other settings, which can sometimes be problematic.


Present a category by generators and relations.

The result is a finitely presented category (FinCat) represented by a graph, possibly with path equations. For example, the simplex category truncated to one dimension is:

@fincat begin
  V, E
  (δ₀, δ₁): V → E
  σ₀: E → V

  σ₀ ∘ δ₀ == id(V)
  σ₀ ∘ δ₁ == id(V)

The objects and morphisms must be uniquely named.


Define a functor between two finitely presented categories.

Such a functor is defined by sending the object and morphism generators of the domain category to generic object and morphism expressions in the codomain category. For example, the following functor embeds the schema for graphs into the schema for circular port graphs by ignoring the ports:

@finfunctor SchGraph SchCPortGraph begin
  V => Box
  E => Wire
  src => src ⨟ box
  tgt => tgt ⨟ box

A constructor exists that purports to allow the user to check that a proposed functor satisfies relations in the domain, but this functionality doesn't yet exist (and the problem is undecidable in general.) Thus the only check is that the source and target of the image of an arrow are the image of its source and target.


Present a free diagram in a given category.

Recall that a free diagram in a category $C$ is a functor $F: J → C$ where $J$ is a free category on a graph, here assumed finite. This macro is functionally a special case of @diagram but changes the interpretation of equality expressions. Rather than interpreting them as equations between morphisms in $J$, equality expresions can be used to introduce anonymous morphisms in a "pointful" style. For example, the limit of the following diagram consists of the paths of length two in a graph:

@free_diagram SchGraph begin
  (e₁, e₂)::E
  tgt(e₁) == v
  src(e₂) == v

Anonymous objects can also be introduced. For example, the previous diagram is isomorphic to this one:

@free_diagram SchGraph begin
  (e₁, e₂)::E
  tgt(e₁) == src(e₂)

Some care must exercised when defining morphisms between diagrams with anonymous objects, since they cannot be referred to by name.


Construct a graph in a simple, declarative style.

The syntax is reminiscent of Graphviz. Each line a declares a vertex or set of vertices, or an edge. For example, the following defines a directed triangle:

@graph begin
  v0, v1, v2
  fst: v0 → v1
  snd: v1 → v2
  comp: v0 → v2

Vertices in the graph must be uniquely named, whereas edges names are optional.


Contravariantly migrate data from one acset to another.

This macro is shorthand for defining a data migration using the @migration macro and then calling the migrate function. If the migration will be used multiple times, it is more efficient to perform these steps separately, reusing the functor defined by @migration.

For more about the syntax and supported features, see @migration.


Define a contravariant data migration.

This macro provides a DSL to specify a contravariant data migration from $C$-sets to $D$-sets for given schemas $C$ and $D$. A data migration is defined by a functor from $D$ to a category of queries on $C$. Thus, every object of $D$ is assigned a query on $C$ and every morphism of $D$ is assigned a morphism of queries, in a compatible way. Example usages are in the unit tests. What follows is a technical reference.

Several categories of queries are supported by this macro:

  1. Trivial queries, specified by a single object of $C$. In this case, the macro simply defines a functor $D → C$ and is equivalent to @finfunctor or @diagram.
  2. Conjunctive queries, specified by a diagram in $C$ and evaluated as a finite limit.
  3. Gluing queries, specified by a diagram in $C$ and evaluated as a finite colimit. An important special case is linear queries, evaluated as a finite coproduct.
  4. Gluc queries (gluings of conjunctive queries), specified by a diagram of diagrams in $C$ and evaluated as a colimit of limits. An important special case is duc queries (disjoint unions of conjunctive queries), evaluated as a coproduct of limits.

The query category of the data migration is not specified explicitly but is inferred from the queries used in the macro call. Implicit conversion is performed: trivial queries can be coerced to conjunctive queries or gluing queries, and conjunctive queries and gluing queries can both be coerced to gluc queries. Due to the implicit conversion, the resulting functor out of $D$ has a single query type and thus a well-defined codomain.

Syntax for the right-hand sides of object assignments is:

  • a symbol, giving object of $C$ (query type: trivial)
  • @product ... (query type: conjunctive)
  • @unit (alias: @terminal, query type: conjunctive)
  • @join ... (alias: @limit, query type: conjunctive)
  • @cases ... (alias: @coproduct, query type: gluing)
  • @empty (alias: @initial, query type: gluing)
  • @glue ... (alias: @colimit, query type: gluing)

Thes query types supported by this macro generalize the kind of queries familiar from relational databases. Less familiar is the concept of a morphism between queries, derived from the concept of a morphism between diagrams in a category. A query morphism is given by a functor between the diagrams' indexing categories together with a natural transformation filling a triangle of the appropriate shape. From a practical standpoint, the most important thing to remember is that a morphism between conjunctive queries is contravariant with respect to the diagram shapes, whereas a morphism between gluing queries is covariant. TODO: Reference for more on this.



Extends Catlab.jl with facilities for migrating acsets (see Acsets.jl) to different schemas via conjunctive, duc, and gluing queries. Such queries are determined by a functor on the target schema valued in diagram categories of the target schema.