Practical and comprehensive formalisms for modelling contemporary graph query languages

作者：

Highlights：

• There is a lack of explicit mapping between practical graph query languages and theoretical language formalisms.

• Current formalisms used by practical graph query languages are not expressive enough.

• Extension of conjunctive queries and union of conjunctive queries with Tarski’s relation algebra.

• Use of extended formalisms to compare the expressiveness of practical graph query languages.

• A comprehensive comparison of two practical graph query languages Cypher and PGQL.

摘要

•There is a lack of explicit mapping between practical graph query languages and theoretical language formalisms.•Current formalisms used by practical graph query languages are not expressive enough.•Extension of conjunctive queries and union of conjunctive queries with Tarski’s relation algebra.•Use of extended formalisms to compare the expressiveness of practical graph query languages.•A comprehensive comparison of two practical graph query languages Cypher and PGQL.

论文关键词：Graph query languages,Conjunctive queries,Union of conjunctive queries,Tarski’s algebra,Cypher,PGQL

论文评审过程：Received 8 February 2021, Accepted 1 June 2021, Available online 10 June 2021, Version of Record 19 June 2021.

论文官网地址：https://doi.org/10.1016/j.is.2021.101816