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

Graphical Conjunctive Queries

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

  • UserPawel Sobocinski, University of Southampton
  • ClockFriday 27 July 2018, 14:00-15:00
  • HouseFW26.

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.

Tell a friend about this talk:

This talk is included in these lists:

Note that ex-directory lists are not shown.

 

© 2006-2018 Talks.cam, University of Cambridge. Contact Us | Help and Documentation | Privacy and Publicity