COOKIES: By using this website you agree that we can place Google Analytics Cookies on your device for performance monitoring. |

University of Cambridge > Talks.cam > Logic and Semantics Seminar (Computer Laboratory) > Graphical Conjunctive Queries

## Graphical Conjunctive QueriesAdd 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)
- Computer Laboratory talks
- Computing and Mathematics
- FW26
- Logic and Semantics Seminar (Computer Laboratory)
- School of Technology
- Trust & Technology Initiative - interesting events
Note that ex-directory lists are not shown. |
## Other listsGates Cambridge Annual Lecture 7 March 2017 Pilot waves, Bohmian metaphysics, and the foundations of quantum mechanics Yana Toom - EU-Russia relations: a view from the European Parliament## Other talksDiagnostics and patient pathways in pancreatic cancer On the origin of human sociality: Ape minds and the evolution of Homo sapiens THE PYE STORY Making a Crowdsourced Task Attractive: Measuring Workers Pre-task Interactions Dielectric haloscopes: a new way to search for axion dark matter |