Schema-Based Query Optimisation for Graph Databases

Summary: Schema-based type inference for recursive graph queries; leverages graph schemas to enrich and guide evaluation. Soundness and completeness ensure semantic preservation while delivering performance gains on social networks, life sciences, and business analytics. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID: 7127
Venue: SIGMOD
Year: 2025
Pagerank: 5.214913e-05
Overall Rank: 9,811 | 32.69%
DOI: 10.1145/3709722

Incoming Non-self Citations Over Time

Authors

1. Chandan Sharma (CNRS; Grenoble Institute of Technology; INRIA; University of Grenoble)
2. Pierre Genevès (CNRS; Grenoble Institute of Technology; INRIA; University of Grenoble)
3. Nils Gesbert (CNRS; Grenoble Institute of Technology; INRIA; University of Grenoble)
4. Nabil Layaïda (CNRS; Grenoble Institute of Technology; INRIA; University of Grenoble)

BibTeX Citation

@inproceedings{sharma_sigmod25,
        title = {{Schema-Based Query Optimisation for Graph Databases}},
        author = {Sharma, Chandan and Genevès, Pierre and Gesbert, Nils and Layaïda, Nabil},
        series = {{SIGMOD} '25},
        booktitle = {Proceedings of the {ACM} {SIGMOD} International Conference on Management of Data},
        publisher = {Association for Computing Machinery},
        doi = {10.1145/3709722},
        url = {https://dl.acm.org/doi/10.1145/3709722},
        year = {2025}
}

Incoming Citations (Sorted by Pagerank)

Showing 1 of 1 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
10,143	Raqlet: Cross-Paradigm Compilation for Recursive Queries	2026	CIDR	5.093636e-05

Outgoing Citations (Sorted by Pagerank)

Showing 33 of 33 cited papers.

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

Rank	Cited Paper	Year	Venue	Pagerank
16	MAGIC SETS AND OTHER STRANGE WAYS TO IMPLEMENT LOGIC PROGRAMS (Extended Abstract)	1986	PODS	0.00060089598
137	Relational Databases for Querying XML Documents: Limitations and Opportunities	1999	VLDB	0.00029877792
348	Regular Path Queries with Constraints	1997	PODS	0.00020518814
395	Containment and Equivalence for an XPath Fragment [Extended Abstract]	2002	PODS	0.00019298983
426	The LDBC Social Network Benchmark: Interactive Workload	2015	SIGMOD	0.00018692185
490	Design and Implementation of the LogicBlox System	2015	SIGMOD	0.000175757
530	An Analytical Study of Large SPARQL Query Logs	2018	VLDB	0.0001709169
547	Cypher: An Evolving Query Language for Property Graphs	2018	SIGMOD	0.00016731552
686	Query Containment for Conjunctive Queries With Regular Expressions	1998	PODS	0.00014948634
900	G-CORE: A Core for Future Graph Query Languages	2018	SIGMOD	0.00013337186
1,155	Projecting XML Documents	2003	VLDB	0.00011933524
1,591	SQLGraph: An Efficient Relational-Based Property Graph Store	2015	SIGMOD	0.00010255536
1,630	On the Decidability of Query Containment under Constraints	1998	PODS	0.00010180625
1,661	PG-Schema: Schemas for Property Graphs	2023	SIGMOD	0.00010079134
1,836	Graph Pattern Matching in GQL and SQL/PGQ	2022	SIGMOD	9.6489549e-05
1,963	Building an Efficient RDF Store Over a Relational Database	2013	SIGMOD	9.3915212e-05
2,066	Rewriting of Regular Expressions and Regular Path Queries	1999	PODS	9.2348082e-05
2,433	Vertexica: Your Relational Friend for Graph Analytics!	2014	VLDB	8.5869161e-05
2,861	PG-Keys: Keys for Property Graphs	2021	SIGMOD	8.0212883e-05
3,285	Type-Based XML Projection	2006	VLDB	7.5597856e-05
3,308	Path Constraints on Semistructured and Structured Data	1998	PODS	7.5381026e-05
4,369	Semantic Query Optimization in the Presence of Types	2010	PODS	6.7390374e-05
4,537	On Testing Satisfiability of Tree Pattern Queries	2004	VLDB	6.6417534e-05
4,972	On the Optimization of Recursive Relational Queries: Application to Graph Queries	2020	SIGMOD	6.4193234e-05
5,425	GPC: A Pattern Calculus for Property Graphs	2023	PODS	6.223218e-05
6,310	Type Inference for Datalog and its Application to Query Optimisation	2008	PODS	5.9176726e-05
6,926	On the Decidability of Containment of Recursive Datalog Queries - Preliminary report	2004	PODS	5.7382018e-05
7,041	DiscoPG: Property Graph Schema Discovery and Exploration	2022	VLDB	5.7194994e-05
9,012	Towards Theory for Real-World Data	2022	PODS	5.3323444e-05
9,761	AvantGraph Query Processing Engine	2022	VLDB	5.2238304e-05
10,043	SHARQL: Shape Analysis of Recursive SPARQL Queries	2020	SIGMOD	5.1703259e-05
10,044	The (Almost) Complete Guide to Tree Pattern Containment	2015	PODS	5.1703259e-05
10,045	SOR: A Practical System for Ontology Storage, Reasoning and Search	2007	VLDB	5.1703259e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	2,854	Extracting and Analyzing Hidden Graphs from Relational Databases	2017	SIGMOD
2	9,173	Optimizing Recursive Queries in SQL	2005	SIGMOD
3	13,158	Classification Of Recursive Formulas In Deductive Databases	1988	SIGMOD
4	4,425	EFFICIENT EVALUATION FOR A SUBSET OF RECURSIVE QUERIES (Extended Abstract)	1987	PODS
5	10,103	Optimizing Differentially-Maintained Recursive Queries on Dynamic Graphs	2022	VLDB
6	7,214	Schema Mappings for Data Graphs	2017	PODS
7	294	Graphs-at-a-time: Query Language and Access Methods for Graph Databases	2008	SIGMOD
8	3,572	Summary Graphs for Relational Database Schemas	2011	VLDB
9	747	Querying Graph Databases	2013	PODS
10	4,972	On the Optimization of Recursive Relational Queries: Application to Graph Queries	2020	SIGMOD