Document Open Access Logo

Graphical Conjunctive Queries

Authors Filippo Bonchi, Jens Seeber, Pawel Sobocinski

PDF
Thumbnail PDF

File

LIPIcs.CSL.2018.13.pdf
  • Filesize: 1.13 MB
  • 23 pages

Document Identifiers

Author Details

Filippo Bonchi
  • University of Pisa, Italy
Jens Seeber
  • IMT School for Advanced Studies Lucca, Italy
Pawel Sobocinski
  • University of Southampton, UK

Cite As Get BibTex

Filippo Bonchi, Jens Seeber, and Pawel Sobocinski. Graphical Conjunctive Queries. In 27th EACSL Annual Conference on Computer Science Logic (CSL 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 119, pp. 13:1-13:23, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018) https://doi.org/10.4230/LIPIcs.CSL.2018.13

Abstract

The Calculus of Conjunctive Queries (CCQ) has foundational status in database theory. A celebrated theorem of Chandra and Merlin states that CCQ query inclusion is decidable. Its proof transforms logical formulas to graphs: each query has a natural model - a kind of graph - and query inclusion reduces to the existence of a graph homomorphism between natural models. 
We introduce the diagrammatic language Graphical Conjunctive Queries (GCQ) and show that it has the same expressivity as CCQ. GCQ terms are string diagrams, and their algebraic structure allows us to derive a sound and complete axiomatisation of query inclusion, which turns out to be exactly Carboni and Walters' notion of cartesian bicategory of relations. Our completeness proof exploits the combinatorial nature of string diagrams as (certain cospans of) hypergraphs: Chandra and Merlin's insights inspire a theorem that relates such cospans with spans. Completeness and decidability of the (in)equational theory of GCQ follow as a corollary. Categorically speaking, our contribution is a model-theoretic completeness theorem of free cartesian bicategories (on a relational signature) for the category of sets and relations.

Subject Classification

ACM Subject Classification
  • Theory of computation → Categorical semantics
Keywords
  • conjunctive query inclusion
  • string diagrams
  • cartesian bicategories

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

References

  1. Samson Abramsky and Bob Coecke. Categorical quantum mechanics. CoRR, abs/1401.4973, 2008. URL: http://arxiv.org/abs/0808.1023.
  2. Foto N. Afrati, Matthew Damigos, and Manolis Gergatsoulis. Query containment under bag and bag-set semantics. Inf. Process. Lett., 110(10):360-369, 2010. URL: http://dx.doi.org/10.1016/j.ipl.2010.02.017.
  3. John Baez and Jason Erbele. Categories in control. Theory and Application of Categories, 30:836-881, 2015. Google Scholar
  4. Jean Bénabou. Introduction to bicategories. In Reports of the Midwest Category Seminar, pages 1-77. Springer, 1967. Google Scholar
  5. Filippo Bonchi, Fabio Gadducci, Aleks Kissinger, Paweł Sobociński, and Fabio Zanasi. Rewriting modulo symmetric monoidal structure. In Proceedings of the 31st Annual ACM/IEEE Symposium on Logic in Computer Science, pages 710-719. ACM, 2016. Google Scholar
  6. Filippo Bonchi, Pawel Sobocinski, and Fabio Zanasi. Full abstraction for signal flow graphs. In POPL 2015, pages 515-526. ACM, 2015. Google Scholar
  7. Roberto Bruni, Ivan Lanese, and Ugo Montanari. A basic algebra of stateless connectors. Theoretical Computer Science, 366(1-2):98-120, 2006. Google Scholar
  8. Roberto Bruni, Hernán C. Melgratti, and Ugo Montanari. A connector algebra for P/T nets interactions. In CONCUR 2011, volume 6901 of LNCS, pages 312-326. Springer, 2011. URL: http://dx.doi.org/10.1093/jigpal/6.2.349.
  9. Roberto Bruni, Hernán C. Melgratti, Ugo Montanari, and Paweł Sobociński. Connector algebras for C/E and P/T nets' interactions. Log Meth Comput Sci, 9(16), 2013. Google Scholar
  10. Roberto Bruni, Ugo Montanari, Gordon D. Plotkin, and Daniele Terreni. On hierarchical graphs: Reconciling bigraphs, gs-monoidal theories and gs-graphs. Fundam. Inform., 134(3-4):287-317, 2014. Google Scholar
  11. Aurelio Carboni, G Max Kelly, Robert FC Walters, and Richard J Wood. Cartesian bicategories ii. Theory and Applications of Categories, 19(6):93-124, 2008. Google Scholar
  12. Aurelio Carboni and Robert FC Walters. Cartesian bicategories i. Journal of pure and applied algebra, 49(1-2):11-32, 1987. Google Scholar
  13. Donald D Chamberlin and Raymond F Boyce. Sequel: A structured english query language. In Proceedings of the 1974 ACM SIGFIDET (now SIGMOD) workshop on Data description, access and control, pages 249-264. ACM, 1974. Google Scholar
  14. Ashok K Chandra and Philip M Merlin. Optimal implementation of conjunctive queries in relational data bases. In Proceedings of the ninth annual ACM symposium on Theory of computing, pages 77-90. ACM, 1977. Google Scholar
  15. Surajit Chaudhuri and Moshe Y. Vardi. Optimization of Real conjunctive queries. In Catriel Beeri, editor, Proceedings of the Twelfth ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems, May 25-28, 1993, Washington, DC, USA, pages 59-70. ACM Press, 1993. URL: http://dl.acm.org/citation.cfm?id=153850, URL: http://dx.doi.org/10.1145/153850.153856.
  16. Edgar F Codd. A relational model of data for large shared data banks. Communications of the ACM, 13(6):377-387, 1970. Google Scholar
  17. B. Coecke and A. Kissinger. Picturing Quantum Processes. A First Course in Quantum Theory and Diagrammatic Reasoning. Cambridge University Press, 2016. Google Scholar
  18. A. Corradini, U. Montanari, F. Rossi, H. Ehrig, R. Heckel, and M. Loewe. Algebraic approaches to graph transformation, part i: Basic concepts and double pushout approach. In Handbook of Graph Grammars, pages 163-246. World Scientific, 1997. Google Scholar
  19. Enric Cosme-Llópez and Damien Pous. K4-free graphs as a free algebra. In 42nd International Symposium on Mathematical Foundations of Computer Science, MFCS 2017, August 21-25, 2017 - Aalborg, Denmark, volume 83 of LIPIcs, pages 76:1-76:14, 2017. Google Scholar
  20. Peter J Freyd and Andre Scedrov. Categories, allegories, volume 39. Elsevier, 1990. Google Scholar
  21. Dan R. Ghica and Aliaume Lopez. A structural and nominal syntax for diagrams. CoRR, abs/1702.01695, 2017. http://arxiv.org/abs/1702.01695, URL: http://dx.doi.org/10.4204/EPTCS.266.4.
  22. Victor Mikhaylovich Glushkov. The abstract theory of automata. Russian Mathematical Surveys, 16(5):1, 1961. Google Scholar
  23. Yannis E. Ioannidis and Raghu Ramakrishnan. Containment of conjunctive queries: Beyond relations as sets. ACM Trans. Database Syst., 20(3):288-324, 1995. URL: http://dx.doi.org/10.1145/211414.211419.
  24. T. S. Jayram, Phokion G. Kolaitis, and Erik Vee. The containment problem for REAL conjunctive queries with inequalities. In Stijn Vansummeren, editor, Proceedings of the Twenty-Fifth ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems, June 26-28, 2006, Chicago, Illinois, USA, pages 80-89. ACM, 2006. URL: http://dl.acm.org/citation.cfm?id=1142351, URL: http://dx.doi.org/10.1145/1142351.1142363.
  25. Emmanuel Jeandel, Simon Perdrix, and Renaud Vilmart. A complete axiomatisation of the zx-calculus for clifford+ t quantum mechanics. arXiv preprint arXiv:1705.11151, 2017. Google Scholar
  26. Swastik Kopparty and Benjamin Rossman. The homomorphism domination exponent. Eur. J. Comb., 32(7):1097-1114, 2011. URL: http://dx.doi.org/10.1016/j.ejc.2011.03.009.
  27. Stephen Lack. Composing props. Theory and Applications of Categories, 13(9):147-163, 2004. Google Scholar
  28. Saunders Mac Lane. Categories for the working mathematician, volume 5. Springer Science &Business Media, 2013. Google Scholar
  29. Paul-André Melliès and Noam Zeilberger. A bifibrational reconstruction of lawvere’s presheaf hyperdoctrine. In Proceedings of the 31st Annual ACM/IEEE Symposium on Logic in Computer Science, LICS '16, New York, NY, USA, July 5-8, 2016, pages 555-564, 2016. URL: http://dx.doi.org/10.1145/2933575.2934525.
  30. Kang Feng Ng and Quanlong Wang. A universal completion of the zx-calculus. arXiv preprint arXiv:1706.09877, 2017. Google Scholar
  31. Mehrnoosh Sadrzadeh, Stephen Clark, and Bob Coecke. The frobenius anatomy of word meanings I: subject and object relative pronouns. CoRR, abs/1404.5278, 2014. Google Scholar
  32. Vladimiro Sassone and Paweł Sobociński. A congruence for Petri nets. Electronic Notes in Theoretical Computer Science, 127(2):107-120, 2005. Google Scholar
  33. Alfred Tarski. On the calculus of relations. The Journal of Symbolic Logic, 6(3):73-89, 1941. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact