BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//Talks.cam//talks.cam.ac.uk//
X-WR-CALNAME:Talks.cam
BEGIN:VEVENT
SUMMARY:Graphical Conjunctive Queries - Pawel Sobocinski\, University of S
 outhampton 
DTSTART:20180810T130000Z
DTEND:20180810T140000Z
UID:TALK108907@talks.cam.ac.uk
CONTACT:Victor Gomes
DESCRIPTION:String diagrams are an intuitive and powerful notation with se
 veral different applications in computer science and related disciplines. 
 In order to arrive at an implementation of diagrammatic reasoning\, one ne
 eds 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 comb
 inatorial presentation has the core of diagrammatic reasoning (i.e. the la
 ws of symmetric monoidal categories) built in\, and is therefore useful es
 pecially for rewriting\, which reduces to a standard form of graph rewriti
 ng. In general\, connections between categorical structures and combinator
 ial structures are often extremely useful.\n\nIn this talk I will argue th
 at there is one important actor missing from the above story: logic. In re
 cent work (arXiv:1804.07626) with Bonchi and Seeber\, we identified a deep
  connection with a foundational logical calculus from database theory\, th
 e Calculus of Conjunctive Queries. Moreover\, we showed that the algebraic
  theory of cartesian bicategories (Carboni and Walters) captures the notio
 n 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 bi
 categories)\, logic (conjunctive queries) and combinatorics (hypergraphs-w
 ith-interfaces).
LOCATION:FW11
END:VEVENT
END:VCALENDAR