On the Optimization of Recursive Relational Queries - Télécom Paris Accéder directement au contenu
Communication Dans Un Congrès Année : 2018

On the Optimization of Recursive Relational Queries

Louis Jachiet
Nils Gesbert
  • Fonction : Auteur
  • PersonId : 899056
Pierre Genevès
Nabil Layaïda

Résumé

Graph databases have received a lot of attention recently as they are particularly useful in many applications such as social networks or for the semantic web. Various languages have emerged to query such graph databases. At the heart of many of those query languages, there is a construction to navigate through the graph which allows some form of recursion. The relational model has benefited from a huge body of research in the last half century and that is why many graph databases either rely on (or have adopted the techniques of) relational based 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. In this paper, we introduce μ-RA, a variation of the Re- lational Algebra that allows for the expression of relational queries with recursion. μ-RA can express unions of con- junctive regular path queries as well as certain non-regular properties. We present its syntax, semantics and the rewriting rules we specifically devised to tackle the optimization of recursive queries. A prototype evaluator implementing these rewriting rules is shown to be more efficient than previous approaches.

Domaines

Web
Fichier principal
Vignette du fichier
rpq.pdf (788.64 Ko) Télécharger le fichier
Origine : Fichiers produits par l'(les) auteur(s)
Loading...

Dates et versions

hal-01673025 , version 1 (28-12-2017)
hal-01673025 , version 2 (17-12-2018)
hal-01673025 , version 3 (08-01-2019)
hal-01673025 , version 4 (28-11-2019)
hal-01673025 , version 5 (29-02-2020)
hal-01673025 , version 6 (19-06-2021)

Identifiants

Citer

Louis Jachiet, Nils Gesbert, Pierre Genevès, Nabil Layaïda. On the Optimization of Recursive Relational Queries. BDA 2018, 34ème Conférence sur la Gestion de Données - Principes, Technologies et Applications, Oct 2018, Bucarest, Romania. ⟨10.1145/nnnnnnn.nnnnnnn⟩. ⟨hal-01673025v2⟩
2230 Consultations
1936 Téléchargements

Altmetric

Partager

Gmail Facebook X LinkedIn More