Notes on Representing Knowledge and Querying Data using Double-Functorial Semantics

This paper is a (slight) formalization of the previous blog posts by Lambert and Patterson on knowledge representation in double categories. Unfortunately, it only briefly touches on the double category theory material developed by the same authors.

In the interest of developing examples, the paper drops lots of hints about deeper double-category theory ideas. For example, they use “extensions” and “restrictions” as “primitive” operations, although the concept is developed in their Appendix A.1.

I’d like to see this paper compare this approach to other proposes for categorical databases. They do consider “functional ologs” but only in passing. I’d like to see the following comparisons:

1. Graphical conjunctive queries. Fragment of first-order logic that only considers existential quantification and product.

2. ACsets. It’s strange that this paper does not reference ACsets and the double-category formulation of this structure.

The paper considers several query types. Selection is proposed as an operation on columns considered as extending along projection morphisms.

What does this mean? This paper seems to use extremely technical language to describe what should be simple concepts.

A double category D has tabulators if the external identity functor D0 → D1 has a right adjoint ⊤. This associates to each proarrow an object and a universal cell that we think of as a kind of comprehension scheme. Tabulators provide type creation in double categorical ologs by associating a type to a proarrow of those entities which satisfy the proposition represented by the given proarrow.

Partial maps are defined as a span with a monic leg. This is “kind of” dual to the categorical rewriting approach developed in another Patterson paper. In this approach, a cospan represents a rewriting rule with a monic leg that performs a “partial match” on the environment to see if the rule fires.