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: 13071
Venue: VLDB
Year: 2022
Pagerank: 5.8896555e-05
Overall Rank: 6,387 | 56.19%
DOI: 10.14778/3554821.3554894

Incoming Non-self Citations Over Time

Authors

1. Amine Mhedhbi (University of Waterloo)
2. Semih Salihoğlu (University of Waterloo)

BibTeX Citation

@article{mhedhbi_vldb22,
        title = {{Modern Techniques for Querying Graph-Structured Relations: Foundations, System Implementations, and Open Challenges}},
        author = {Mhedhbi, Amine and Salihoğlu, Semih},
        journal = {PVLDB},
        series = {{VLDB} '22},
        volume = {15},
        number = {12},
        pages = {3762--3765},
        doi = {10.14778/3554821.3554894},
        url = {https://doi.org/10.14778/3554821.3554894},
        year = {2022}
}

Incoming Citations (Sorted by Pagerank)

Showing 5 of 5 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
8,920	Full-Power Graph Querying: State of the Art and Challenges	2023	VLDB	5.3483178e-05
9,944	Chimera: A system design of dual storage and traversal-join unified query processing for SQL/PGQ	2025	VLDB	5.1915905e-05
10,087	Worst-Case-Optimal Similarity Joins on Graph Databases	2024	SIGMOD	5.1558402e-05
11,030	GraphAr: An Efficient Storage Scheme for Graph Data in Data Lakes	2025	VLDB	5.093636e-05
11,064	Property Graph Standards: State of the Art & Open Challenges	2025	VLDB	5.093636e-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
211	EmptyHeaded: A Relational Engine for Graph Processing	2016	SIGMOD	0.00024797217
259	Database Cracking	2007	CIDR	0.00023119313
264	The Ubiquity of Large Graphs and Surprising Challenges of Graph Processing	2018	VLDB	0.00022980015
422	Umbra: A Disk-Based System with In-Memory Performance	2020	CIDR	0.00018732744
490	Design and Implementation of the LogicBlox System	2015	SIGMOD	0.000175757
809	Optimizing Subgraph Queries by Combining Binary and Worst-Case Optimal Joins	2019	VLDB	0.00013874588
1,058	Graphflow: An Active Graph Database	2017	SIGMOD	0.00012378784
1,857	Joins via Geometric Resolutions: Worst-case and Beyond	2015	PODS	9.6047945e-05
2,392	FDB: A Query Engine for Factorised Relational Databases	2012	VLDB	8.6404947e-05
3,357	Columnar Storage and List-based Processing for Graph Database Management Systems	2021	VLDB	7.4904874e-05
3,649	Query Planning for Evaluating SPARQL Property Paths	2016	SIGMOD	7.2251335e-05
4,340	GRFusion: Graphs as First-Class Citizens in Main-Memory Relational Database Systems	2018	SIGMOD	6.7539375e-05
4,892	Fast In-Memory SQL Analytics on Typed Graphs	2017	VLDB	6.4574091e-05
8,468	Making RDBMSs Efficient on Graph Workloads Through Predefined Joins	2022	VLDB	5.418656e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	1,740	Adopting Worst-Case Optimal Joins in Relational Database Systems	2020	VLDB
2	5,264	Implementation Strategies for Views over Property Graphs	2024	SIGMOD
3	1,555	Keyword Search in Databases: The Power of RDBMS	2009	SIGMOD
4	747	Querying Graph Databases	2013	PODS
5	3,357	Columnar Storage and List-based Processing for Graph Database Management Systems	2021	VLDB
6	7,887	Graph Data Management Systems for New Application Domains	2011	VLDB
7	11,745	Parallel Traversal of Graphs Stored in RDBMSs	2020	CIDR
8	3,872	All-in-One: Graph Processing in RDBMSs Revisited	2017	SIGMOD
9	11,067	Machine Learning for Graph Data Management and Query Processing	2025	VLDB
10	7,769	G-SQL: Fast Query Processing via Graph Exploration	2016	VLDB