Practical and comprehensive formalisms for modelling contemporary graph query languages. Issue 102 (December 2021)

• Record Type: Journal Article
• Authors: Sharma, Chandan; Sinha, Roopak; Johnson, Kenneth
• Is Part Of: Information systems. Issue 102(2021)
• Publication Date: 2021-12
• Subjects: Graph query languages -- Conjunctive queries -- Union of conjunctive queries -- Tarski's algebra -- Cypher -- PGQL; Database management -- Periodicals; Electronic data processing -- Periodicals; Bases de données -- Gestion -- Périodiques; Informatique -- Périodiques; Database management; Electronic data processing; Periodicals; 005.7
• DOI: 10.1016/j.is.2021.101816
• Languages: English
• ISSNs: 0306-4379

Abstract

Abstract: The industry-wide adoption of graph databases has been hindered due to the fragmentation in syntax and semantics of available graph query languages. As a result, several projects have been proposed by industry and academia to develop a standard query language by integrating features from existing practical graph query languages. A significant factor that can impact query language integration is the lack of common theoretical language formalisms. We propose common formalisms by extending conjunctive queries and union of conjunctive queries with Tarski's relation algebra ( CQT / UCQT ). We use common graph query patterns to compare the expressive power of ( CQT / UCQT ) with two practical graph query languages - C y p h e r and P G Q L . The query languages are analysed on the core features of graph pattern matching and graph navigation, revealing the common and exclusive characteristics for these languages. Overall, our study serves as a formal basis for comparing existing graph query languages and assists the move towards query language integration and interoperability between available graph database technologies. 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.