Document Open Access Logo

A Researcher’s Digest of GQL (Invited Talk)

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

PDF
Thumbnail PDF

File

LIPIcs.ICDT.2023.1.pdf
  • Filesize: 0.88 MB
  • 22 pages

Document Identifiers

Author Details

Nadime Francis
  • Laboratoire d'Informatique Gaspard Monge, Université Gustave Eiffel, CNRS, France
Amélie Gheerbrant
  • IRIF, Université Paris Cité, CNRS, Paris, France
Paolo Guagliardo
  • School of Informatics, University of Edinburgh, UK
Leonid Libkin
  • University of Edinburgh, UK
  • RelationalAI, France
  • ENS, PSL University, France
Victor Marsault
  • Laboratoire d'Informatique Gaspard Monge, Université Gustave Eiffel, CNRS, France
Wim Martens
  • Universität Bayreuth, Germany
Filip Murlak
  • University of Warsaw, Poland
Liat Peterfreund
  • Laboratoire d'Informatique Gaspard Monge, Université Gustave Eiffel, CNRS, France
Alexandra Rogova
  • IRIF, Université Paris Cité, CNRS, Paris, France
  • Data Intelligence Institute of Paris, Inria
Domagoj Vrgoč
  • University of Zagreb, Coratia
  • Pontificia Universidad Católica de Chile, Santiago, Chile

Funding

This work is supported by: a Leverhulme Trust Research Fellowship; EPSRC grant S003800; French ANR projects grants ANR-18-CE40-0031 (QUID), ANR-19-CE48-0019 (EQUUS), and ANR-21-CE48-0015 (Verigraph); German Research Foundation (DFG) projects 431183758 and 369116833; ANID Millennium Science Initiative Program, Code ICN17_002; ANID Fondecyt Regular project 1221799; NCN grant 2018/30/E/ST6/00042.

Acknowledgements

The authors are grateful to members of the ISO/IEC JTC1 SC32 WG3 committee and especially Fred Zemke for many comments on our formalization of the language.

Cite AsGet BibTex

Nadime Francis, Amélie Gheerbrant, Paolo Guagliardo, Leonid Libkin, Victor Marsault, Wim Martens, Filip Murlak, Liat Peterfreund, Alexandra Rogova, and Domagoj Vrgoč. A Researcher’s Digest of GQL (Invited Talk). In 26th International Conference on Database Theory (ICDT 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 255, pp. 1:1-1:22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)
https://doi.org/10.4230/LIPIcs.ICDT.2023.1

Abstract

GQL (Graph Query Language) is being developed as a new ISO standard for graph query languages to play the same role for graph databases as SQL plays for relational. In parallel, an extension of SQL for querying property graphs, SQL/PGQ, is added to the SQL standard; it shares the graph pattern matching functionality with GQL. Both standards (not yet published) are hard-to-understand specifications of hundreds of pages. The goal of this paper is to present a digest of the language that is easy for the research community to understand, and thus to initiate research on these future standards for querying graphs. The paper concentrates on pattern matching features shared by GQL and SQL/PGQ, as well as querying facilities of GQL.

Subject Classification

ACM Subject Classification
  • Theory of computation → Database theory
  • Theory of computation → Database query languages (principles)
  • Information systems → Graph-based database models
  • Information systems → Structured Query Language
Keywords
  • GQL
  • Property Graph
  • Query Language
  • Graph Database
  • Pattern matching
  • Multi-Graph

Metrics

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

References

  1. Serge Abiteboul, Richard Hull, and Victor Vianu. Foundations of Databases. Addison-Wesley, 1995. Google Scholar
  2. Renzo Angles, Angela Bonifati, Stefania Dumbrava, George Fletcher, Alastair Green, Jan Hidders, Bei Li, Leonid Libkin, Victor Marsault, Wim Martens, Filip Murlak, Stefan Plantikow, Ognjen Savkovic, Michael Schmidt, Juan Sequeda, Slawek Staworko, Dominik Tomaszuk, Hannes Voigt, Domagoj Vrgoc, Mingxi Wu, and Dusan Zivkovic. PG-Schema: Schemas for property graphs, 2022. URL: http://arxiv.org/abs/2211.10962.
  3. Renzo Angles, Angela Bonifati, Stefania Dumbrava, George Fletcher, Keith W. Hare, Jan Hidders, Victor E. Lee, Bei Li, Leonid Libkin, Wim Martens, Filip Murlak, Josh Perryman, Ognjen Savkovic, Michael Schmidt, Juan F. Sequeda, Slawek Staworko, and Dominik Tomaszuk. PG-Keys: Keys for property graphs. In SIGMOD '21: International Conference on Management of Data, pages 2423-2436. ACM, 2021. URL: https://doi.org/10.1145/3448016.3457561.
  4. Marcelo Arenas, Pablo Barceló, Leonid Libkin, Wim Martens, and Andreas Pieris. Database Theory. Open source at https://github.com/pdm-book/community, 2022.
  5. Jorge A. Baier, Dietrich Daroch, Juan L. Reutter, and Domagoj Vrgoč. Evaluating navigational RDF queries over the web. In HT, pages 165-174. ACM, 2017. URL: https://doi.org/10.1145/3078714.3078731.
  6. Denilson Barbosa, Alberto O. Mendelzon, Leonid Libkin, Laurent Mignet, and Marcelo Arenas. Efficient incremental validation of XML documents. In ICDE, pages 671-682. IEEE Computer Society, 2004. URL: https://doi.org/10.1109/ICDE.2004.1320036.
  7. Véronique Benzaken and Evelyne Contejean. A coq mechanised formal semantics for realistic SQL queries: formally reconciling SQL and bag relational algebra. In CPP, pages 249-261. ACM, 2019. URL: https://doi.org/10.1145/3293880.3294107.
  8. Diego Calvanese, Giuseppe De Giacomo, Maurizio Lenzerini, and Moshe Y. Vardi. Containment of conjunctive regular path queries with inverse. In KR, pages 176-185. Morgan Kaufmann, 2000. Google Scholar
  9. Diego Calvanese, Giuseppe De Giacomo, Maurizio Lenzerini, and Moshe Y. Vardi. Reasoning on regular path queries. SIGMOD Rec., 32(4):83-92, 2003. URL: https://doi.org/10.1145/959060.959076.
  10. Shumo Chu, Konstantin Weitz, Alvin Cheung, and Dan Suciu. HoTTSQL: proving query rewrites with univalent SQL semantics. In PLDI, pages 510-524. ACM, 2017. URL: https://doi.org/10.1145/3062341.3062348.
  11. Isabel F. Cruz, Alberto O. Mendelzon, and Peter T. Wood. A graphical query language supporting recursion. In SIGMOD Conference, pages 323-330. ACM Press, 1987. URL: https://doi.org/10.1145/38713.38749.
  12. Alin Deutsch, Nadime Francis, Alastair Green, Keith Hare, Bei Li, Leonid Libkin, Tobias Lindaaker, Victor Marsault, Wim Martens, Jan Michels, Filip Murlak, Stefan Plantikow, Petra Selmer, Oskar van Rest, Hannes Voigt, Domagoj Vrgoc, Mingxi Wu, and Fred Zemke. Graph pattern matching in GQL and SQL/PGQ. In SIGMOD Conference, pages 2246-2258. ACM, 2022. URL: https://doi.org/10.1145/3514221.3526057.
  13. Alin Deutsch, Yu Xu, Mingxi Wu, and Victor E. Lee. Aggregation support for modern graph analytics in TigerGraph. In SIGMOD Conference, pages 377-392. ACM, 2020. URL: https://doi.org/10.1145/3318464.3386144.
  14. Mary F. Fernandez, Daniela Florescu, Alon Y. Levy, and Dan Suciu. A query language for a web-site management system. SIGMOD Rec., 26(3):4-11, 1997. URL: https://doi.org/10.1145/262762.262763.
  15. Diego Figueira, Adwait Godbole, Shankara Narayanan Krishna, Wim Martens, Matthias Niewerth, and Tina Trautner. Containment of simple conjunctive regular path queries. In KR, pages 371-380, 2020. URL: https://doi.org/10.24963/kr.2020/38.
  16. Nadime Francis, Amélie Gheerbrant, Paolo Guagliardo, Leonid Libkin, Victor Marsault, Wim Martens, Filip Murlak, Liat Peterfreund, Alexandra Rogova, and Domagoj Vrgoč. GPC: A pattern calculus for property graphs. In PODS'23, 2023. To appear. Google Scholar
  17. Nadime Francis, Alastair Green, Paolo Guagliardo, Leonid Libkin, Tobias Lindaaker, Victor Marsault, Stefan Plantikow, Mats Rydberg, Martin Schuster, Petra Selmer, and Andrés Taylor. Formal semantics of the language Cypher, 2018. URL: http://arxiv.org/abs/1802.09984.
  18. Nadime Francis, Alastair Green, Paolo Guagliardo, Leonid Libkin, Tobias Lindaaker, Victor Marsault, Stefan Plantikow, Mats Rydberg, Petra Selmer, and Andrés Taylor. Cypher: An evolving query language for property graphs. In SIGMOD Conference, pages 1433-1445. ACM, 2018. URL: https://doi.org/10.1145/3183713.3190657.
  19. GQL influence graph. https://www.gqlstandards.org/existing-languages, 2023. Accessed: 2023-01-17.
  20. Alastair Green, Paolo Guagliardo, and Leonid Libkin. Property graphs and paths in GQL: Mathematical definitions. Technical Reports TR-2021-01, Linked Data Benchmark Council (LDBC), October 2021. URL: https://doi.org/10.54285/ldbc.TZJP7279.
  21. Alastair Green, Paolo Guagliardo, Leonid Libkin, Tobias Lindaaker, Victor Marsault, Stefan Plantikow, Martin Schuster, Petra Selmer, and Hannes Voigt. Updating graph databases with Cypher. Proc. VLDB Endow., 12(12):2242-2253, 2019. URL: https://doi.org/10.14778/3352063.3352139.
  22. Paolo Guagliardo and Leonid Libkin. A formal semantics of SQL queries, its validation, and applications. Proc. VLDB Endow., 11(1):27-39, 2017. URL: https://doi.org/10.14778/3151113.3151116.
  23. Andrey Gubichev, Srikanta J. Bedathur, and Stephan Seufert. Sparqling Kleene: Fast property paths in RDF-3X. In GRADES. CWI/ACM, 2013. URL: https://doi.org/10.1145/2484425.2484443.
  24. A. Gupta and I.S. Mumick. Materialized Views: Techniques, Implementations, and Applications. MIT Press, 1999. Google Scholar
  25. Aidan Hogan, Cristian Riveros, Carlos Rojas, and Adrián Soto. A worst-case optimal join algorithm for SPARQL. In ISWC (1), volume 11778 of Lecture Notes in Computer Science, pages 258-275. Springer, 2019. URL: https://doi.org/10.1007/978-3-030-30793-6_15.
  26. Egor V. Kostylev, Juan L. Reutter, and Domagoj Vrgoc. Containment of queries for graphs with data. J. Comput. Syst. Sci., 92:65-91, 2018. URL: https://doi.org/10.1016/j.jcss.2017.09.005.
  27. Leonid Libkin, Wim Martens, and Domagoj Vrgoč. Querying graphs with data. Journal of the ACM, 63(2):14:1-14:53, 2016. URL: https://doi.org/10.1145/2850413.
  28. Wim Martens, Matthias Niewerth, Tina Popp, Stijn Vansummeren, and Domagoj Vrgoč. Representing paths in graph database pattern matching, 2022. URL: http://arxiv.org/abs/2207.13541.
  29. Alberto O. Mendelzon, George A. Mihaila, and Tova Milo. Querying the world wide web. In Proceedings of the Fourth International Conference on Parallel and Distributed Information Systems, December 18-20, 1996, Miami Beach, Florida, USA, pages 80-91. IEEE Computer Society, 1996. URL: https://doi.org/10.1109/PDIS.1996.568671.
  30. Alberto O. Mendelzon and Peter T. Wood. Finding regular simple paths in graph databases. SIAM J. Comput., 24(6):1235-1258, 1995. URL: https://doi.org/10.1137/S009753979122370X.
  31. Dung T. Nguyen, Molham Aref, Martin Bravenboer, George Kollias, Hung Q. Ngo, Christopher Ré, and Atri Rudra. Join processing for graph patterns: An old dog with new tricks. In GRADES, pages 2:1-2:8. ACM, 2015. URL: https://doi.org/10.1145/2764947.2764948.
  32. Juan L. Reutter, Miguel Romero, and Moshe Y. Vardi. Regular queries on graph databases. Theory Comput. Syst., 61(1):31-83, 2017. URL: https://doi.org/10.1007/s00224-016-9676-2.
  33. Marko A. Rodriguez. The Gremlin graph traversal machine and language. In DBPL, pages 1-10. ACM, 2015. URL: https://doi.org/10.1145/2815072.2815073.
  34. Oskar van Rest, Sungpack Hong, Jinha Kim, Xuming Meng, and Hassan Chafi. PGQL: a property graph query language. In GRADES, page 7. ACM, 2016. URL: https://doi.org/10.1145/2960414.2960421.
  35. Domagoj Vrgoč. Evaluating regular path queries under the all-shortest paths semantics, 2022. URL: http://arxiv.org/abs/2204.11137.
  36. Wikipedia contributors. GQL graph query language, 2020. URL: https://en.wikipedia.org/wiki/GQL_Graph_Query_Language.
  37. Nikolay Yakovets, Parke Godfrey, and Jarek Gryz. Query planning for evaluating SPARQL property paths. In SIGMOD Conference, pages 1875-1889. ACM, 2016. URL: https://doi.org/10.1145/2882903.2882944.
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 Imprint Privacy Contact