Full-Power Graph Querying: State of the Art and Challenges

Summary: Positions a continuum between structured graph querying (SPARQL, GPML/PG) and graph keyword search, contrasting expressiveness, semantics and computational complexity. Analyzes keyword‑scoring lessons and language mechanisms to combine precise constraints with exploratory connection search, and outlines open challenges. (summarized by gpt-5-mini on Feb 09 2026)

Paper ID: haeaf21a8dd8e6815
Venue: VLDB
Year: 2023
Pagerank: 5.3795421e-05
Overall Rank: 8,188 | 44.97%
DOI: 10.14778/3611540.3611577
PDF: Download (CC BY-NC-ND 4.0)

Incoming Non-self Citations Over Time

Authors

1. Ioana Manolescu (INRIA; Institut Polytechnique de Paris)
2. Madhulika Mohanty (INRIA; Institut Polytechnique de Paris)

BibTeX Citation

@article{manolescu_vldb23,
        title = {{Full-Power Graph Querying: State of the Art and Challenges}},
        author = {Manolescu, Ioana and Mohanty, Madhulika},
        journal = {PVLDB},
        series = {{VLDB} '23},
        volume = {16},
        number = {12},
        pages = {3886--3889},
        doi = {10.14778/3611540.3611577},
        url = {https://doi.org/10.14778/3611540.3611577},
        year = {2023}
}

Incoming Citations (Sorted by Pagerank)

Showing 2 of 2 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
9,811	Property Graph Standards: State of the Art & Open Challenges	2025	VLDB	5.1233734e-05
11,042	An Extended Tutorial and Vocabulary for Relational Language Design in an Era of AI-Assisted Query Generation	2026	VLDB	4.9769913e-05

Outgoing Citations (Sorted by Pagerank)

Showing 18 of 18 cited papers.

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

Rank	Cited Paper	Year	Venue	Pagerank
38	DISCOVER: Keyword Search in Relational Databases	2002	VLDB	0.00047373961
81	XRANK: Ranked Keyword Search over XML Documents	2003	SIGMOD	0.00036330407
217	Efficient IR-Style Keyword Search over Relational Databases	2003	VLDB	0.00024454844
270	BLINKS: Ranked Keyword Searches on Graphs	2007	SIGMOD	0.00022588961
290	ObjectRank: Authority-Based Keyword Search in Databases	2004	VLDB	0.00021944946
293	Bidirectional Expansion For Keyword Search on Graph Databases	2005	VLDB	0.00021933539
860	G-CORE: A Core for Future Graph Query Languages	2018	SIGMOD	0.00013401414
942	SPARK: Top-k Keyword Query in Relational Databases	2007	SIGMOD	0.00012950177
1,494	Graph Pattern Matching in GQL and SQL/PGQ	2022	SIGMOD	0.00010497226
1,883	BANKS: Browsing and Keyword Searching in Relational Databases	2002	VLDB	9.4358776e-05
1,907	EASE: An Effective 3-in-1 Keyword Search Method for Unstructured, Semi-structured and Structured Data	2008	SIGMOD	9.3936687e-05
2,731	Keyword Search in Graphs: Finding r-cliques	2011	VLDB	8.0802025e-05
5,175	Querying in the Age of Graph Databases and Knowledge Graphs	2021	SIGMOD	6.2402956e-05
5,534	Efficient and Progressive Group Steiner Tree Search	2016	SIGMOD	6.0906268e-05
6,487	Modern Techniques for Querying Graph-Structured Relations: Foundations, System Implementations, and Open Challenges	2022	VLDB	5.7661458e-05
8,352	ConnectionLens: Finding Connections Across Heterogeneous Data Sources	2018	VLDB	5.3476532e-05
8,516	Exploring the Data Wilderness through Examples	2019	SIGMOD	5.3239705e-05
9,854	Discovering Diversified Paths in Knowledge Bases	2018	VLDB	5.1185582e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	289	Graphs-at-a-time: Query Language and Access Methods for Graph Databases	2008	SIGMOD
2	2,484	Querying Semantic Web Data with SPARQL	2011	PODS
3	6,487	Modern Techniques for Querying Graph-Structured Relations: Foundations, System Implementations, and Open Challenges	2022	VLDB
4	7,990	Graph Querying Meets HCI: State of the Art and Future Directions	2017	SIGMOD
5	9,082	Machine Learning for Graph Data Management and Query Processing	2025	VLDB
6	2,882	Expressive and Flexible Access to Web-Extracted Data: A Keyword-based Structured Query Language	2010	SIGMOD
7	4,468	Schemaless and Structureless Graph Querying	2014	VLDB
8	720	Querying Graph Databases	2013	PODS
9	5,175	Querying in the Age of Graph Databases and Knowledge Graphs	2021	SIGMOD
10	3,313	Keyword Search on Structured and Semi-Structured Data	2009	SIGMOD