Graphical Conjunctive Queries

Add to your list(s) Download to your calendar using vCal

• Pawel Sobocinski, University of Southampton
• Friday 10 August 2018, 14:00-15:00
• FW11.

If you have a question about this talk, please contact Victor Gomes.

This talk has been canceled/deleted

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).

This talk is part of the Logic and Semantics Seminar (Computer Laboratory) series.

This talk is included in these lists:

This talk is not included in any other list

Note that ex-directory lists are not shown.