Skip to Main content Skip to Navigation
New interface
Conference papers

A Cost Estimation Technique for Recursive Relational Algebra

Muideen Lawal 1 Pierre Genevès 1 Nabil Layaïda 1 
1 TYREX - Types and Reasoning for the Web
Inria Grenoble - Rhône-Alpes, LIG - Laboratoire d'Informatique de Grenoble
Abstract : With the increasing popularity of data structures such as graphs, re-cursion is becoming a key ingredient of query languages in analytic systems. Recursive query evaluation involves an iterative application of a function or operation until some condition is satisfied. It is particularly useful for retrieving nodes reachable along deep paths in a graph. The optimization of recursive queries has remained a challenge for decades. Recently, extensions of Codd's classical relational algebra to support recursive terms and their optimisation gained renewed interest [10]. Query optimization crucially relies on enumeration of query evaluation plans and on cost estimation techniques. Cost estimation for recursive terms is far from trivial, and received less attention. In this paper, we propose a new cost estimation technique for recursive terms of the extended relational algebra. This technique allows to select an estimated cheapest query plan, in terms of computing resources usage e.g. memory footprint, CPU and I/O and evaluation time. We evaluate the effectiveness of our cost estimation technique on a set of recursive graph queries on both generated and real datasets of significant size, including Yago: a graph with more than 62 millions edges and 42 million nodes. Experiments show that our cost estimation technique improves the performance of recursive query evaluation on popular relational database engines such as PostgreSQL.
Complete list of metadata

Cited literature [17 references]  Display  Hide  Download
Contributor : Tyrex Equipe Connect in order to contact the contributor
Submitted on : Friday, November 13, 2020 - 3:23:00 PM
Last modification on : Tuesday, August 2, 2022 - 4:24:32 AM
Long-term archiving on: : Sunday, February 14, 2021 - 7:19:28 PM


Files produced by the author(s)



Muideen Lawal, Pierre Genevès, Nabil Layaïda. A Cost Estimation Technique for Recursive Relational Algebra. CIKM 2020 - 29th ACM International Conference on Information and Knowledge Management, Oct 2020, Virtual Event, France. pp.1-4, ⟨10.1145/3340531.3417460⟩. ⟨hal-03004218⟩



Record views


Files downloads