Graphical Conjunctive Queries

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

• Pawel Sobocinski, University of Southampton
• Friday 27 July 2018, 14:00-15:00
• FW26.

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

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:

• All Talks (aka the CURE list)
• Cambridge talks
• Computing and Mathematics
• Department of Computer Science and Technology talks and seminars
• FW26
• Interested Talks
• Logic and Semantics Seminar (Computer Laboratory)
• School of Technology
• Trust & Technology Initiative - interesting events
• bld31
• yk373's list

Note that ex-directory lists are not shown.