Graphical Conjunctive Queries

Understand

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.