Graphical Conjunctive Queries — Filippo Bonchi, Jens Seeber & Pawel Sobocinski (2018; CSL 2018). arXiv:1804.07626 (v1, PDF).
Introduces a string-diagrammatic language for conjunctive queries with the same expressive power as the usual calculus, and proves that the laws of Carboni–Walters cartesian bicategories are sound and complete for query inclusion. The completeness proof recasts Chandra–Merlin: diagrams are cospans of hypergraphs, and inclusion reduces to the existence of a hypergraph homomorphism.
Sources: the paper, arXiv:1804.07626v1, checked against the arXiv listing. Index: Papers.
Key definitions and results
- Definitions 1, 3, 4: models, semantics, query equivalence and inclusion for CCQ
- Propositions 2, 8, 9: sorted presentation; CCQ and GCQ are equally expressive
- Definition 6: models of GCQ
- Definition 16, Theorem 17: the cartesian bicategory axioms are complete for query inclusion
- Definition 19, Example 20: cartesian bicategory;
- Theorem 31: GCQ diagrams are cospans of hypergraphs
- Theorem 37: the preorder-enriched (Yoneda-style) analogue of Theorem 17
Concept notes
Conjunctive Query, Cartesian Bicategory