GLL-based Context-Free Path Querying for Neo4j

Aidan Hogan D. Vrgoč

9 Juni 2024

The tutorial provides an in-depth overview of recent advances in algorithms and data structures for processing graph database queries. The focus will be on scalable algorithms that have been demonstrated to work over real world knowledge graphs. We will also present detailed performance comparisons of classical and recent algorithms. The tutorial will be divided into four sections. The first section will motivate the use of graph databases for querying knowledge graphs, and will introduce the attendees to graph data models and the query language landscape. The second section will discuss how to efficiently evaluate graph patterns, introducing the worst-case optimal join techniques and comparing them to classical join algorithms. The third section will discuss techniques for efficiently evaluating path queries and for constructing compact representations of potentially exponential sets of paths. In the final section we will introduce recent advances in compressed data structures that ease the high memory requirements of worst-case optimal join algorithms and also provide a template for evaluating path queries in a highly optimised manner.

Jingren Zhou Wenyuan Yu Longbin Lai + 4 lainnya

28 Maret 2025

This technical report extends the SIGMOD 2025 paper"A Modular Graph-Native Query Optimization Framework"by providing a comprehensive exposition of GOpt's advanced technical mechanisms, implementation strategies, and extended evaluations. While the original paper introduced GOpt's unified intermediate representation (GIR) and demonstrated its performance benefits, this report delves into the framework's implementation depth: (1) the full specification of GOpt's optimization rules; (2) a systematic treatment of semantic variations (e.g., homomorphism vs. edge-distinct matching) across query languages and their implications for optimization; (3) the design of GOpt's Physical integration interface, enabling seamless integration with transactional (Neo4j) and distributed (GraphScope) backends via engine-specific operator customization; and (4) a detailed analysis of plan transformations for LDBC benchmark queries.

2021

GTFS (General Transit Feed Specification) is a standard of Google for public transportation schedules. The specification describes stops, routes, dates, trips, etc. of one or more public transportation company for a city or a country. Examining a GTFS feed it can be considered as a graph. In addition in the last decades new database management systems was born in order to support the big data era and/or help to write program codes. Their collective name is the NoSQL databases, which covers many types of database systems. One type of them is the graph databases, from which the Neo4j is the most widespread. In this paper I try to find the answer for the question how the Neo4j can support the usage of the GTFS. The most obvious usage of the GTFS is the route planning for which the Neo4j offers some algorithms. I built some storage structures on which the tools provided by Neo4j can be effectively used to plan routes on GTFS data.

Michael J. Carey Glenn Galvizo

13 Mei 2024

The increasing prevalence of large graph data has produced a variety of research and applications tailored toward graph data management. Users aiming to perform graph analytics will typically start by importing existing data into a separate graph-purposed storage engine. The cost of maintaining a separate system (e.g., the data copy, the associated queries, etc …) just for graph analytics may be prohibitive for users with Big Data. In this paper, we introduce Graphix and show how it enables property graph views of existing document data in AsterixDB, a Big Data management system boasting a partitioned-parallel query execution engine. We explain a) the graph view user model of Graphix, b) $\text{gSQL}^{++}$, a novel query language extension for synergistic document-based navigational pattern matching, and c) how edge hops are evaluated in a parallel fashion. We then compare queries authored in $\text{gSQL}^{++}$ against versions in other leading query languages. Finally, we evaluate our approach against a leading native graph database, Neo4j, and show that Graphix is appropriate for operational and analytical workloads, especially at scale.

Mohanna Shahrad Yunjia Zheng Yu Ting Gu + 1 lainnya

13 Mei 2024

Views are widely used in relational databases to facilitate query writing, give individualized abstractions to different user groups, and improve query execution time with materialization techniques. This paper explores how views could be defined and used in graph database systems (GDBS) with a similar purpose to what can be found in relational systems. We perform our analysis using Neo4j and its query language Cypher which has many of the features typically found in graph query languages, aiming to pave the way for integrating view management into a wider range of GDBS.