C-sets for data analysis: relational data and conjunctive queries

Conjunctive queries on C-sets

The mutagenesis dataset, available through the Relational Dataset Repository, is a collection of molecular graphs from a study on the mutagenicity of certain chemical compounds. The dataset has a three-level relational structure: there is a set of molecules, each of which has a set of atoms, which may be connected pairwise by chemical bonds.

The complete schema includes data attributes for each of the three types.

@present SchMutagenesis(FreeSchema) begin
  (Indicator, Categorical, Name, Numerical)::AttrType
  
  Molecule::Ob
  molecule_id::Attr(Molecule, Name)
  (ind1, inda)::Attr(Molecule, Indicator)
  (logp, lumo)::Attr(Molecule, Numerical)
  mutagenic::Attr(Molecule, Indicator)
  
  Atom::Ob
  molecule::Hom(Atom, Molecule)
  atom_id::Attr(Atom, Name)
  atom_type::Attr(Atom, Categorical)
  element::Attr(Atom, Name)
  charge::Attr(Atom, Numerical)
  
  Bond::Ob
  (atom1, atom2)::Hom(Bond, Atom)
  bond_type::Attr(Bond, Categorical)
end

@acset_type MutagenesisData(SchMutagenesis,
  index=[:atom1, :atom2, :molecule],
  unique_index=[:atom_id, :molecule_id])

The attributes molecule_id and atom_id do not appear to be meaningful but are carried over from the primary keys in the original SQL database.

The data is loaded into Catlab by making three SELECT * from [table]; queries on the SQL database and mapping the primary keys to integer IDs. We omit this routine code, which should in any case be automated in the future. The result is an ACSet mutagenesis having the following dimensions.

map(Tables.rowcount, tables(mutagenesis))

(Molecule = 188, Atom = 4893, Bond = 5243)

Here are excerpts from each of the tables:

pretty_tables(mutagenesis, crop=:both, display_size=(15,80))

┌──────────┬─────────────┬───────┬───────┬──────┬────────┬───────────┐
│ Molecule │ molecule_id │  ind1 │  inda │ logp │   lumo │ mutagenic │
├──────────┼─────────────┼───────┼───────┼──────┼────────┼───────────┤
│        1 │          d1 │  true │ false │ 4.23 │ -1.246 │      true │
│        2 │         d10 │  true │ false │ 4.62 │ -1.387 │      true │
│        3 │        d100 │ false │ false │ 2.68 │ -1.034 │     false │
│        4 │        d101 │  true │ false │ 6.26 │ -1.598 │      true │
│        5 │        d102 │  true │ false │  2.4 │ -3.172 │      true │
│        6 │        d103 │  true │ false │ 4.69 │ -1.487 │      true │
│        7 │        d104 │  true │ false │ 6.26 │ -1.546 │      true │
│    ⋮     │      ⋮      │   ⋮   │   ⋮   │  ⋮   │   ⋮    │     ⋮     │
└──────────┴─────────────┴───────┴───────┴──────┴────────┴───────────┘
                                                      181 rows omitted
┌──────┬──────────┬─────────┬───────────┬─────────┬────────┐
│ Atom │ molecule │ atom_id │ atom_type │ element │ charge │
├──────┼──────────┼─────────┼───────────┼─────────┼────────┤
│    1 │        3 │  d100_1 │        22 │       c │ -0.128 │
│    2 │        3 │ d100_10 │         3 │       h │  0.132 │
│    3 │        3 │ d100_11 │        29 │       c │  0.002 │
│    4 │        3 │ d100_12 │        22 │       c │ -0.128 │
│    5 │        3 │ d100_13 │        22 │       c │ -0.128 │
│    6 │        3 │ d100_14 │        22 │       c │ -0.128 │
│    7 │        3 │ d100_15 │        22 │       c │  0.202 │
│  ⋮   │    ⋮     │    ⋮    │     ⋮     │    ⋮    │   ⋮    │
└──────┴──────────┴─────────┴───────────┴─────────┴────────┘
                                           4886 rows omitted

┌──────┬───────┬───────┬───────────┐
│ Bond │ atom1 │ atom2 │ bond_type │
├──────┼───────┼───────┼───────────┤
│    1 │     1 │    12 │         7 │
│    2 │     1 │    24 │         1 │
│    3 │     3 │     4 │         7 │
│    4 │     4 │     5 │         7 │
│    5 │     4 │     9 │         1 │
│    6 │     5 │     6 │         7 │
│    7 │     5 │    10 │         1 │
│  ⋮   │   ⋮   │   ⋮   │     ⋮     │
└──────┴───────┴───────┴───────────┘
                   5236 rows omitted

We are now going to make queries against the mutagenesis data. Generally speaking, Catlab supports evaluating conjunctive queries on attributed \mathsf{C}-sets. Although more restrictive than arbitrary SQL queries, conjunctive queries play in a central role in the theory and practice of relational databases. They are precisely the queries that can be expressed in regular logic, the subsystem of first-order logic with connectives \exists, \wedge, \top. Alternatively, as we will see later, they are the queries that can be computed as finite limits in \mathsf{Set}.

In Catlab, conjunctive queries are most easily specified using the @relation macro, which has the general form:

@relation (out1=var1, out2=var2, …) [where (x,y,z,…)] begin
  T₁(col1=var3, col2=var4, …)
  ⋮
  Tₙ(col1=var5, col2=var6, …)
end

Every relation statement in the macro body specifies a table T_i and a subset of its columns, with each column assigned to a variable. To evaluate the query, you take the cartesian product of the selected tables T_1, \dots, T_n, then filter the rows so that any two columns assigned to the same variable are equal. Finally, you return a table that exposes a subset of the variables, given by the output names in the first clause. The full set of variables is optionally stated in the where clause; if it is omitted, the set of variables is inferred.

Conjunctive queries are more intuitive than this description may make them appear. Returning to the mutagenesis data, we might assume that molecular graphs are undirected, so that for every for bond between atoms a_1 and a_2, there is also a bond between atoms a_2 and a_1. We can check this assumption using the following query.

symmetric_pairs = @relation (atom1=a1, atom2=a2) begin
  Bond(atom1=a1, atom2=a2)
  Bond(atom1=a2, atom2=a1)
end

nrow(query(mutagenesis, symmetric_pairs))

0

In fact, no bond in this dataset has a corresponding bond in the opposite direction. The creators of the data presumably left the oppositely oriented bonds implicit.

A more fundamental constraint is that any two bonded atoms must belong to the same molecule.

bond_within_molecule = @relation (Bond=b) begin
  Bond(_id=b, atom1=a1, atom2=a2)
  Atom(_id=a1, molecule=m)
  Atom(_id=a2, molecule=m)
end

result = query(mutagenesis, bond_within_molecule)
nrow(result) == nparts(mutagenesis, :Bond)

true

At least this assumption is satisfied by the data! The schema presented earlier has no equations, but we could have added an equation explitictly stating the assumption:

@present SchMutagenesis(FreeSchema) begin
  [...]
  
  compose(atom1, molecule) == compose(atom2, molecule)
end

By default, the variables in a query may take any values, but variables can be fixed to specific values using the optional third argument to query. For example, the following query returns all carbon atoms belonging to a mutagenic molecule, together with the charges of the atoms.

atoms_in_molecule = @relation (Atom=a, molecule=m, charge=charge) begin
  Atom(_id=a, element=element, charge=charge, molecule=m)
  Molecule(_id=m, mutagenic=mutagenic)
end

query(mutagenesis, atoms_in_molecule, (element="c", mutagenic=true))

The mutagenesis data is essentially a collection of graphs, one for each molecule, where the vertices are atoms and the edges are bonds. The conventional way to process such data would be to convert it into a graph, using a specialized data structure for directed graphs. In Catlab, this conversion is easily achieved by functorial data migration in its basic, contravariant form:

using Catlab.Graphs

g = Graph(mutagenesis, Dict(:V => :Atom, :E => :Bond),
                       Dict(:src => :atom1, :tgt => :atom2))
(V = nv(g), E = ne(g))

(V = 4893, E = 5243)

The graph’s connected components correspond to the molecules. An advantage of the graph representation is that you can directly apply any graph analytics procedure that expects a graph as input. However, in contrast to other systems, in Catlab there are no further advantages to performing this conversion. Traversing the derived graph will be no faster or slower than traversing the MutagenesisData object, because graphs in Catlab are \mathsf{C}-sets isomorphic to the atom-bond substructure of the mutagenesis structure. This what we meant at the outset when we said that attributed \mathsf{C}-sets are a joint generalization of graphs and data frames.

The unification of graphs with relational data cuts in both directions. On the one hand, since graphs in Catlab are \mathsf{C}-sets, we can efficiently evaluate conjunctive queries against them. As a simple example, here are all the directed paths of length two in the derived graph:

paths2 = @relation (vert1=v1, vert2=v2, vert3=v3) begin
  E(src=v1, tgt=v2)
  E(src=v2, tgt=v3)
end

query(g, paths2)

On the other hand, we can formulate richer queries against the mutagenesis data, where more data attributes are available. The following query refines the previous one to find all directed paths from a carbon atom to a nitrogen atom to another carbon atom. The resulting table is much smaller.

paths2 = @relation (atom1=a1, atom2=a2, atom3=a3) begin
  Bond(atom1=a1, atom2=a2)
  Bond(atom1=a2, atom2=a3)
  Atom(_id=a1, element=elem1)
  Atom(_id=a2, element=elem2)
  Atom(_id=a3, element=elem3)
end

query(mutagenesis, paths2, (elem1="c", elem2="n", elem3="c"))

Conjunctive queries as limits

The theory of relational databases is category theory. This statement is true in many ways and from many perspectives, but we will focus on just one: the equivalence between conjunctive queries on relational databases and finite limits in the category of sets. This equivalence is almost immediate if you are familiar with the relevant concepts; it is certainly not new (Kato 1983; Alagic and Alagic 1991). Nevertheless, it is a fruitful observation for both category theory and relational databases. In one direction, conjunctive queries inherit an intuitive diagrammatic syntax through the operad of undirected wiring diagrams. Conversely, any general-purpose package for computational category theory, which Catlab aims to be, ought to be able to efficiently compute finite limits of sets. Algorithms for doing so have been extensively developed by database theorists and engineers.

Here is a dictionary between conjunctive queries of different kinds and finite limits in \mathsf{Set} of different shapes.

• cross joins of tables X and Y are products

  

• joins² along attributes a_X: X \to A and a_Y: Y \to A are pullbacks

  

• multi-way joins along attributes a_i: X_i \to A, for i=1,\dots,n, are wide pullbacks

  

• general conjunctive queries are limits of finite bipartite diagrams

The last statement, about conjunctive queries and bipartite diagrams, requires elaboration. We will break it down into two steps. First, conjunctive queries can be represented by undirected wiring diagrams (UWDs); in Catlab, they actually are UWDs.³ Second, the UWD translates into a bipartite diagram, whose limit is the result of the query.

As an illustration, recall this conjunctive query on the mutagenesis data.

bond_within_molecule = @relation (Bond=b) begin
  Bond(_id=b, atom1=a1, atom2=a2)
  Atom(_id=a1, molecule=m)
  Atom(_id=a2, molecule=m)
end

bond_within_molecule isa UndirectedWiringDiagram

true

The tables in the query correspond to boxes (unfilled circles) in the UWD and the variables correspond to junctions (filled circles).

We won’t say much more about UWDs here. For additional examples of diagrammatic query syntax, see the related earlier post by Andrew Baas on UWDs and SQL queries.

In the second step, the UWD translates into a bipartite diagram in \mathsf{Set}, where the boxes of the UWD become vertices in the diagram’s top layer and the junctions become vertices in the bottom layer.

The result R of the conjunctive query is then the limit of this bipartite diagram, which can be thought of as a “generalized pullback.”

In technical terms, isomorphism classes of data frames (multispans) constitute an algebra of the operad of UWDs, where composition is given by limits of the induced bipartite diagrams.

All this is to say what a conjunctive query is but not how to compute it. There are many ways to evaluate a conjunctive query. The simplest, sketched in the previous section, is to take the cartesian product of the sets in the top layer of the bipartite diagram, then filter the tuples, keeping only those that project to equal values under the functions over any given set in the bottom layer. In a special case, this procedure is known to category theorists as “computing a pullback by taking an equalizer of a product.” However, it is probably the worst possible algorithm for computing a limit, generally being extremely inefficient.

The inefficiency arises from having to iterate over the elements of a cartesian product X_1 \times \cdots \times X_n, whose cardinality grows exponentially in n. To avoid this, the conjunctive query should be decomposed into a sequence of joins, a problem known as query planning. Catlab currently employs a simple greedy heuristic for choosing joins.

Joins, or equivalently pullbacks, may themselves be computed in many ways, of which the most common are (Mishra and Eich 1992):

1. Nested loop join: the naive algorithm that iterates over all pairs of elements
2. Sort-merge join: both vectors of attributes are sorted, then merged together by synchronized iteration
3. Hash join: a hash map (index of preimages) is built for one attribute, then the other attribute vector is iterated, looking up preimages for each element

All three join algorithms are implemented in Catlab, for two-way and multi-way joins. Both the sort-merge join and the hash join are generally much faster than the nested loop join. The hash join performs especially well when an attribute is already indexed in the attributed \mathsf{C}-set, as happens for the source and target functions in a graph.

Outlook

Despite its simplistic query planning, Catlab’s conjunctive queries on \mathsf{C}-sets are already fairly usable. Over time we will implement better query planning algorithms, as well as more general kinds of queries. Possibilities include unions of conjunctive queries, the class of queries expressible in coherent logic, and recursive queries, as in Datalog.

As we have seen, relational databases enjoy two key advantages over isolated data frames. First, relational schemas enable the data’s encoding to mirror its underlying relational structure, which eliminates redundancy in storage and promotes internal consistency. Second, declarative query languages make it easy to ask questions about the data and view it through different lenses. On the other hand, SQL databases and logic programming languages like Prolog and Datalog have generally suffered from the Achilles’ heel of all domain-specific languages (DSLs): you cannot step outside the DSL without abandoning the system entirely. Yet stepping outside the DSL is often necessary, since even the most expressive query languages have their limitations.

We think that \mathsf{C}-sets can offer the best of both worlds to data analysis, providing the benefits of the relational data model while existing as ordinary data structures in a general-purpose programming language. If you cannot express your query using the @relation macro, you can always just write the for loops or the map calls! Due to the design of the Julia programming language and the \mathsf{C}-sets in Catlab, doing so should cause no performance degradations. In this way, we hope that \mathsf{C}-sets will eventually become a valuable component of the JuliaData ecosystem.