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

Louis Jachiet 1, 2, 3 Pierre Genevès 1 Nils Gesbert 1 Nabil Layaïda 1
1 TYREX - Types and Reasoning for the Web
Inria Grenoble - Rhône-Alpes, LIG - Laboratoire d'Informatique de Grenoble
2 DIG - Data, Intelligence and Graphs
LTCI - Laboratoire Traitement et Communication de l'Information
Abstract : Graph databases have received a lot of attention as they are particularly useful in many applications such as social networks, life sciences and the semantic web. Various languages have emerged to query graph databases, many of which embed forms of recursion which reveal essential for navigating in graphs. The relational model has benefited from a huge body of research in the last half century and that is why many graph databases rely on techniques of relational query engines. Since its introduction, the relational model has seen various attempts to extend it with recursion and it is now possible to use recursion in several SQL or Datalog based database systems. The optimization of recursive queries remains, however, a challenge. We propose mu-RA, a variation of the Relational Algebra equipped with a fixpoint operator for expressing recursive relational queries. mu-RA can notably express unions of conjunctive regular path queries. Leveraging the fact that this fixpoint operator makes recursive terms more amenable to algebraic transformations, we propose new rewrite rules. These rules makes it possible to generate new query execution plans, that cannot be obtained with previous approaches. We present the syntax and semantics of mu-RA, and the rewriting rules that we specifically devised to tackle the optimization of recursive queries. We report on practical experiments that show that the newly generated plans can provide significant performance improvements for evaluating recursive queries over graphs.
Document type :
Conference papers
Complete list of metadatas

Cited literature [75 references]  Display  Hide  Download

https://hal.inria.fr/hal-01673025
Contributor : Tyrex Equipe <>
Submitted on : Thursday, November 28, 2019 - 1:49:17 PM
Last modification on : Monday, December 9, 2019 - 4:01:07 PM

File

paper.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : hal-01673025, version 4

Collections

Citation

Louis Jachiet, Pierre Genevès, Nils Gesbert, Nabil Layaïda. On the Optimization of Recursive Relational Queries: Application to Graph Queries. SIGMOD 2020 - ACM International Conference on Management of Data, Jun 2020, Portland, United States. pp.1-23. ⟨hal-01673025v4⟩

Share

Metrics

Record views

167

Files downloads

130