Provenance-Based Algorithms for Rich Queries over Graph Databases - Données et Connaissances Massives et Hétérogènes Accéder directement au contenu
Communication Dans Un Congrès Année : 2021

Provenance-Based Algorithms for Rich Queries over Graph Databases

Yann Ramusat
  • Fonction : Auteur
  • PersonId : 1087951

Résumé

In this paper, we investigate the efficient computation of the provenance of rich queries over graph databases. We show that semiring-based provenance annotations enrich the expressiveness of routing queries over graphs. Several algorithms have previously been proposed for provenance computation over graphs, each yielding a trade-off between time complexity and generality. Here, we address the limitations of these algorithms and propose a new one, partially bridging a complexity and expressiveness gap and adding to the algorithmic toolkit for solving this problem. Importantly, we provide a comprehensive taxonomy of semirings and corresponding algorithms, establishing which practical approaches are needed in different cases. We implement and comprehensively evaluate several practical applications of the problem (e.g., shortest distances, top-shortest distances, Boolean or integer path features), each corresponding to a specific semiring and algorithm, that depends on the properties of the semiring. On several real-world and synthetic graph datasets, we show that the algorithms we propose exhibit large practical benefits for processing rich graph queries.
Fichier principal
Vignette du fichier
p16.pdf (675.09 Ko) Télécharger le fichier
Origine : Fichiers produits par l'(les) auteur(s)

Dates et versions

hal-03140067 , version 1 (12-02-2021)

Licence

Paternité - Pas d'utilisation commerciale - Pas de modification

Identifiants

  • HAL Id : hal-03140067 , version 1

Citer

Yann Ramusat, Silviu Maniu, Pierre Senellart. Provenance-Based Algorithms for Rich Queries over Graph Databases. EDBT 2021 - 24th International Conference on Extending Database Technology, Mar 2021, Nicosia / Virtual, Cyprus. ⟨hal-03140067⟩
297 Consultations
399 Téléchargements

Partager

Gmail Facebook X LinkedIn More