On the Optimization of Recursive Relational Queries: Application to Graph Queries

Summary: µ-RA: a relational-algebra with a fixpoint for recursive graph queries, enabling unions of conjunctive regular path queries. New rewrite rules exploit the fixpoint to produce execution plans unreachable by prior work; experiments show significant speedups for recursive graph evaluation. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID: 5842
Venue: SIGMOD
Year: 2020
Pagerank: 6.4193234e-05
Overall Rank: 4,972 | 65.89%
DOI: 10.1145/3318464.3380567

Incoming Non-self Citations Over Time

Authors

1. Louis Jachiet (Télécom Paris)
2. Pierre Genevès (Grenoble Institute of Technology; INRIA; National Centre for Scientific Research; University of Grenoble)
3. Nils Gesbert (Grenoble Institute of Technology; INRIA; National Centre for Scientific Research; University of Grenoble)
4. Nabil Layaïda (Grenoble Institute of Technology; INRIA; National Centre for Scientific Research; University of Grenoble)

BibTeX Citation

@inproceedings{jachiet_sigmod20,
        title = {{On the Optimization of Recursive Relational Queries: Application to Graph Queries}},
        author = {Jachiet, Louis and Genevès, Pierre and Gesbert, Nils and Layaïda, Nabil},
        series = {{SIGMOD} '20},
        booktitle = {Proceedings of the {ACM} {SIGMOD} International Conference on Management of Data},
        publisher = {Association for Computing Machinery},
        doi = {10.1145/3318464.3380567},
        url = {https://dl.acm.org/doi/10.1145/3318464.3380567},
        year = {2020}
}

Incoming Citations (Sorted by Pagerank)

Showing 8 of 8 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
6,950	SQL Nulls and Two-Valued Logic	2023	PODS	5.7303405e-05
8,502	MWP: Multi-Window Parallel Evaluation of Regular Path Queries on Streaming Graphs	2024	SIGMOD	5.4132367e-05
9,761	AvantGraph Query Processing Engine	2022	VLDB	5.2238304e-05
9,811	Schema-Based Query Optimisation for Graph Databases	2025	SIGMOD	5.214913e-05
10,361	DRPQ: Distributed Evaluation of Regular Path Queries On Streaming Graphs	2026	SIGMOD	5.093636e-05
10,690	Dynamic Pruning for Recursive Joins	2025	SIGMOD	5.093636e-05
11,225	Efficient Regular Simple Path Queries under Transitive Restricted Expressions	2024	VLDB	5.093636e-05
11,261	Efficient Enumeration of Recursive Plans in Transformation-based Query Optimizers	2024	VLDB	5.093636e-05

Outgoing Citations (Sorted by Pagerank)

Showing 17 of 17 cited papers.

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

Rank	Cited Paper	Year	Venue	Pagerank
1	Access Path Selection in a Relational Database Management System	1979	SIGMOD	0.0024089429
16	MAGIC SETS AND OTHER STRANGE WAYS TO IMPLEMENT LOGIC PROGRAMS (Extended Abstract)	1986	PODS	0.00060089598
63	An Amateur's Introduction to Recursive Query Processing Strategies	1986	SIGMOD	0.00038782376
124	A Query Language and Optimization Techniques for Unstructured Data	1996	SIGMOD	0.00030950263
300	GraphLog: a Visual Formalism for Real Life Recursion	1990	PODS	0.00022046803
312	A Graphical Query Language Supporting Recursion	1987	SIGMOD	0.00021733819
429	On the Implementation of a Simple Class of Logic Queries for Databases	1986	PODS	0.00018607152
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
900	G-CORE: A Core for Future Graph Query Languages	2018	SIGMOD	0.00013337186
1,575	Expressive Languages for Path Queries over Graph-Structured Data	2010	PODS	0.00010318258
1,921	Efficient Evaluation of Right-, Left-, and Multi-Linear Rules	1989	SIGMOD	9.4809066e-05
2,054	Evaluation Of Database Recursive Logic Programs As Recurrent Function Series	1986	SIGMOD	9.2516006e-05
2,594	Big Data Analytics with Datalog Queries on Spark	2016	SIGMOD	8.3646367e-05
3,649	Query Planning for Evaluating SPARQL Property Paths	2016	SIGMOD	7.2251335e-05
6,008	More Efficient Datalog Queries: Subsumptive Tabling Beats Magic Sets	2011	SIGMOD	6.0114207e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	13,099	Structural Query Optimization — A Uniform Framework For Semantic Query Optimization In Deductive Databases	1991	PODS
2	2,054	Evaluation Of Database Recursive Logic Programs As Recurrent Function Series	1986	SIGMOD
3	747	Querying Graph Databases	2013	PODS
4	4,425	EFFICIENT EVALUATION FOR A SUBSET OF RECURSIVE QUERIES (Extended Abstract)	1987	PODS
5	9,173	Optimizing Recursive Queries in SQL	2005	SIGMOD
6	13,158	Classification Of Recursive Formulas In Deductive Databases	1988	SIGMOD
7	143	Optimization of Nonrecursive Queries	1986	VLDB
8	312	A Graphical Query Language Supporting Recursion	1987	SIGMOD
9	9,811	Schema-Based Query Optimisation for Graph Databases	2025	SIGMOD
10	2,198	A Recursive Algebra and Query Optimization for Nested Relations	1989	SIGMOD