Abstract

String diagrams are an intuitive and powerful notation with several different applications in computer science and related disciplines. In order to arrive at an implementation of diagrammatic reasoning, one needs a suitable data structure. In a LiCS’16 paper with Bonchi, Gadducci, Kissinger and Zanasi, we identified this as hypergraphs-with-interfaces, or—-categorically speaking—-discrete cospans of hypergraphs. This combinatorial presentation has the core of diagrammatic reasoning (i.e. the laws of symmetric monoidal categories) built in, and is therefore useful especially for rewriting, which reduces to a standard form of graph rewriting. In general, connections between categorical structures and combinatorial structures are often extremely useful.

In this talk I will argue that there is one important actor missing from the above story: logic. In recent work (arXiv:1804.07626) with Bonchi and Seeber, we identified a deep connection with a foundational logical calculus from database theory, the Calculus of Conjunctive Queries. Moreover, we showed that the algebraic theory of cartesian bicategories (Carboni and Walters) captures the notion of query inclusion. A classical result by Chandra and Merlin states that query inclusion is decidable: we derive this decidability result through a deep triangular relationship between categorical structure (cartesian bicategories), logic (conjunctive queries) and combinatorics (hypergraphs-with-interfaces).