The 2026 Alonzo Church Award for Outstanding Contributions to Logic and Computation is presented to Pablo Barceló, Leonid Libkin, Wim Martens, Juan Reutter, Miguel Romero, Moshe Vardi, and Domagoj Vrgoč for laying foundations of logical languages for querying property graphs that found adoption in the SQL and GQL international standards within a decade.
The awardee papers are:
1. Leonid Libkin, Wim Martens, Domagoj Vrgoc, Querying Graphs with Data, Journal of the ACM, Volume 63, Issue 2, pages 1–53, 2016.
2. Juan Reutter, Miguel Romero, Moshe Vardi, Regular Queries on Graph Databases, Theory of Computing Systems, Volume 61, Issue 1, pages 31–83, 2017.
3. Pablo Barcelo, Leonid Libkin, Juan Reutter, Querying Regular Graph Patterns, Journal of the ACM, Volume 61, Issue 1, pages 1–54, 2014.
The Contribution
Graph databases have risen to a high level of prominence and will play an ever increasing role in data processing tasks. Implemented by industry giants (Oracle, Amazon, Google, SAP, Neo4j), they led to two new ISO standards. One is an extension of the SQL standard called SQL/PGQ enabling SQL to query property graphs. The other is a native graph query language called GQL: the only query language standardized by ISO after SQL.
Unlike SQL, whose core is first-order logic, SQL/PGQ and GQL developed in an almost theoretical vacuum. The standard committee looked in the scientific literature for results to guide them, and identified 4 key influences. Two, dating back to the 1980-90s, are about the ubiquitous regular path queries, which fall short of the needs of modern query languages. For this, two key new additions were needed: querying graph topology and data at the same time, and querying complex paths of arbitrary length. These were provided by papers 1 and 2, and their key constructs were incorporated into the new standards. Conference versions of these papers, included in the 4 key influences, received test-of-time awards, acknowledging their role in providing theoretical foundations for new industrial query languages.
The third paper addresses a key challenge of compositionality in graph languages. Its main contribution is a compact representation of query results as automata, effectively transforming them into new graph databases. The paper gained significant interest among industry players interested in expanding GQL with graph-to-graph queries, and was recognized by two major awards for the doctoral thesis that formed its basis.
Given the foundational contributions of these papers, and astonishingly quick adoption of theoretical contributions by the entire relational and graph database industry behind SQL and GQL standards, these papers highly deserve to be recognized by the Alonzo Church Award.