A Simple Algorithm for Worst Case Optimal Join and Sampling - CRISTAL-LINKS
Pré-Publication, Document De Travail Année : 2024

A Simple Algorithm for Worst Case Optimal Join and Sampling

Un algorithme simple pour la jointure dans le pire cas et l'échantillonnage uniforme

Oliver Irwin
Sylvain Salvati

Résumé

We present an elementary branch and bound algorithm with a simple analysis of why it achieves worstcase optimality for join queries on classes of databases defined respectively by cardinality or acyclic degree constraints. We then show that if one is given a reasonable way for recursively estimating upper bounds on the number of answers of the join queries, our algorithm can be turned into algorithm for uniformly sampling answers with expected running time Õ(UP/OUT) where UP is the upper bound, OUT is the actual number of answers and Õ(•) ignores polylogarithmic factors. Our approach recovers recent results on worstcase optimal join algorithm and sampling in a modular, clean and elementary way.
Fichier principal
Vignette du fichier
capelli_et_al_2024_simple_algorithm_for_worstcase_join_and_sampling.pdf (636.01 Ko) Télécharger le fichier
Origine Fichiers produits par l'(les) auteur(s)
licence

Dates et versions

hal-04707428 , version 1 (24-09-2024)

Licence

Identifiants

Citer

Florent Capelli, Oliver Irwin, Sylvain Salvati. A Simple Algorithm for Worst Case Optimal Join and Sampling. 2024. ⟨hal-04707428⟩
23 Consultations
7 Téléchargements

Altmetric

Partager

More