GPC: A Pattern Calculus for Property Graphs

Nadime Francis, Amélie Gheerbrant, Paolo Guagliardo, Leonid Libkin, Victor Marsault, Wim Martens, Filip Murlak, Liat Peterfreund, Alexandra Rogova, Domagoj Vrgoc

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract / Description of output

The development of practical query languages for graph databases runs well ahead of the underlying theory. The ISO committee in charge of database query languages is currently developing a new standard called Graph Query Language (GQL) as well as an extension of the SQL Standard for querying property graphs represented by a relational schema, called SQL/PGQ. The main component of both is the pattern matching facility, which is shared by the two standards. In many aspects, it goes well beyond RPQs, CRPQs, and similar queries on which the research community has focused for years. Our main contribution is to distill the lengthy standard specification into a simple Graph Pattern Calculus (GPC) that reflects all the key pattern matching features of GQL and SQL/PGQ, and at the same time lends itself to rigorous theoretical investigation. We describe the syntax and semantics of GPC, along with the typing rules that ensure its expressions are well-defined, and state some basic properties of the language. With this paper we provide the community a tool to embark on a study of query languages that will soon be widely adopted by industry
Original languageEnglish
Title of host publicationProceedings of the 42nd ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems (PODS ’23)
PublisherACM Association for Computing Machinery
ISBN (Electronic)9798400701276
Publication statusPublished - 18 Jun 2023
Event42nd ACM Symposium on Principles of Database Systems - Seattle , United States
Duration: 18 Jun 202323 Jun 2023

Publication series

NamePODS '23
PublisherAssociation for Computing Machinery


Symposium42nd ACM Symposium on Principles of Database Systems
Abbreviated titlePODS 2023
Country/TerritoryUnited States
Internet address

Keywords / Materials (for Non-textual outputs)

  • graph databases
  • graph query languages
  • GQL
  • pattern matching
  • syntax and semantics
  • expressive power
  • complexity
  • type systems


Dive into the research topics of 'GPC: A Pattern Calculus for Property Graphs'. Together they form a unique fingerprint.
  • Prix du meilleur article BDA 2023

    Francis, Nadime (Recipient), Gheerbrant, Amelie (Recipient), Guagliardo, Paolo (Recipient), Libkin, Leonid (Recipient), Marsault, Victor (Recipient), Martens, Wim (Recipient), Murlak, Filip (Recipient), Peterfreund, Liat (Recipient), Rogova, Alexandra (Recipient) & Vrgoc, Domagoj (Recipient), 25 Oct 2023

    Prize: Prize (including medals and awards)


Cite this