Modern Techniques for Querying Graph-Structured Relations: Foundations, System Implementations, and Open Challenges

Summary: Survey of graph-structured relation querying: foundations, system implementations, and open challenges. Focus on graph workloads, GDBMSs and graph-augmented RDBMSs, with worst-case optimal joins and factorized query processing; discusses implementation gaps and research directions. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID: 12883
Venue: VLDB
Year: 2022
Pagerank: 4.9801324e-05
Overall Rank: 6,639 | 53.82%
DOI: 10.14778/3554821.3554894

Incoming Non-self Citations Over Time

Authors

1. Amine Mhedhbi
2. Semih Saliho11lu

Incoming Citations (Sorted by Pagerank)

Showing 5 of 5 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
8,750	Full-Power Graph Querying: State of the Art and Challenges	2023	VLDB	4.456315e-05
9,790	Chimera: A system design of dual storage and traversal-join unified query processing for SQL/PGQ	2025	VLDB	4.2818172e-05
9,940	Worst-Case-Optimal Similarity Joins on Graph Databases	2024	SIGMOD	4.2456408e-05
10,803	GraphAr: An Efficient Storage Scheme for Graph Data in Data Lakes	2025	VLDB	4.1945683e-05
10,839	Property Graph Standards: State of the Art & Open Challenges	2025	VLDB	4.1945683e-05

Outgoing Citations (Sorted by Pagerank)

Showing 14 of 14 cited papers.

Citations counted here include only citations to other VLDB/SIGMOD/CIDR/PODS papers in this database.

Rank	Cited Paper	Year	Venue	Pagerank
331	The Ubiquity of Large Graphs and Surprising Challenges of Graph Processing	2018	VLDB	0.00027214222
342	EmptyHeaded: A Relational Engine for Graph Processing	2016	SIGMOD	0.00026795977
408	Database Cracking	2007	CIDR	0.00023953844
613	Design and Implementation of the LogicBlox System	2015	SIGMOD	0.00019181325
735	Umbra: A Disk-Based System with In-Memory Performance	2020	CIDR	0.00017452467
1,333	Optimizing Subgraph Queries by Combining Binary and Worst-Case Optimal Joins	2019	VLDB	0.00012523806
1,756	Graphflow: An Active Graph Database	2017	SIGMOD	0.00010664542
2,296	Joins via Geometric Resolutions: Worst-case and Beyond	2015	PODS	9.0776226e-05
3,082	FDB: A Query Engine for Factorised Relational Databases	2012	VLDB	7.6014248e-05
4,012	Columnar Storage and List-based Processing for Graph Database Management Systems	2021	VLDB	6.5335884e-05
4,280	Query Planning for Evaluating SPARQL Property Paths	2016	SIGMOD	6.2948356e-05
4,360	GRFusion: Graphs as First-Class Citizens in Main-Memory Relational Database Systems	2018	SIGMOD	6.256733e-05
5,338	Fast In-Memory SQL Analytics on Typed Graphs	2017	VLDB	5.5629772e-05
8,600	Making RDBMSs Efficient on Graph Workloads Through Predefined Joins	2022	VLDB	4.4876776e-05

Semantically Similar Papers

Overall Rank	Paper	Year	Venue	Pagerank
2,275	Adopting Worst-Case Optimal Joins in Relational Database Systems	2020	VLDB	9.1262202e-05
5,659	Implementation Strategies for Views over Property Graphs	2024	SIGMOD	5.3847762e-05
1,564	Keyword Search in Databases: The Power of RDBMS	2009	SIGMOD	0.00011350495
1,037	Querying Graph Databases	2013	PODS	0.00014502493
4,012	Columnar Storage and List-based Processing for Graph Database Management Systems	2021	VLDB	6.5335884e-05
7,865	Graph Data Management Systems for New Application Domains	2011	VLDB	4.6326563e-05
11,548	Parallel Traversal of Graphs Stored in RDBMSs	2020	CIDR	4.1945683e-05
3,988	All-in-One: Graph Processing in RDBMSs Revisited	2017	SIGMOD	6.5589605e-05
10,843	Machine Learning for Graph Data Management and Query Processing	2025	VLDB	4.1945683e-05
7,760	G-SQL: Fast Query Processing via Graph Exploration	2016	VLDB	4.6589413e-05