Licence CC BY-NC

Des arbres avec SQL et les nombres premiers

Ou comment se passer de self-JOIN

Ce billet présente une façon rigolote d’implémenter une arborescence grâce aux nombres premiers. La technique marche mais elle n’a pas été spécialement prévue pour fonctionner sérieusement en production.

Avec une base de données relationnelle il n’est pas toujours possible d’implémenter et de manipuler des données de nature récursive (comme des arbres) aisément. La modélisation à base d’auto-références est possible, mais la manipulation s’en retrouve quelque peu alourdie, d’autant plus quand les CTE récursives ne sont pas supportées.

Ce billet présente un exemple vraisemblable qui fera office de fil conducteur : l’implémentation d’un système de commentaires dans une BDD, et sa manipulation en SQL. Chaque commentaire peut avoir un ou plusieurs enfants, il s’agit des réponses à ce commentaire. Les enfants peuvent à leur tour avoir des réponses, et ainsi de suite. Il apparaît donc des fils (ou threads) de commentaires, à la façon de HN, Lobste.rs ou encore Reddit.

Un exemple de fils de commentaires qui se répondent dans un débat sur Hacker News
Un exemple de fils de commentaires qui se répondent dans un débat sur Hacker News

Représentation des nœuds

L’approche est la suivante : chaque commentaire (matérialisé par une ligne, ou row) se passe de référence (au sens SQL) et utilise plutôt un entier qui encode d’un seul coup tous ses ancêtres, pourvu qu’on en fasse la décomposition en facteurs premiers. Ce nombre est désigné par parents.

Voici l’allure possible d’une telle table (simplifiée) :

id | parents  |                text
---+----------+----------------------------------------
2  |        1 | 
3  |        2 | First comment
5  |        2 | Second comment
7  |        2 | Third comment
11 |       10 | First comment on the second comment
13 |        6 | First comment on the first comment
17 |        6 | Second comment on the first comment
19 |       14 | Comment on third comment
23 |      266 | Comment on comment on third comment
29 |       10 | Second comment on the second comment
31 |      290 | Comment on the second comment on the second comment
37 |     8990 | Comment on comment on the second comment on the second comment
41 |   332630 | Second comment on comment on comment on the second comment on the second comment
43 | 13637830 | Comment on second comment on comment on comment on the second comment on the second comment
47 |   332630 | First comment on comment on comment on the second comment on the second comment

Chaque commentaire est désigné par une paire (id, parents) qui suit deux règles :

  • id est un nombre premier et est attribué de façon unique à chaque commentaire ;
  • parents est le produit id×parentsid × parents du parent direct du commentaire donné.

Il est maintenant possible de comprendre en quoi parents encode non seulement un parent direct, mais aussi tous les ancêtres d’un commentaire : la décomposition de parents donne en effet la liste de tous les ID des ancêtres. Le contenu de la table est intuitivement représenté par le schéma suivant :

Une représentation hiérarchique du contenu de la table vue précédemment
Une représentation hiérarchique du contenu de la table vue précédemment

Retrouver les parents

Retrouvons le fil ascendant du commentaire d’ID 47 dont voici la ligne dans la table :

id | parents  |                text
---+----------+-----------------------------------------------
47 |   332630 | First comment on comment on comment on the...

La décomposition de parents est 332630=2×5×29×31×37332630 = 2 × 5 × 29 × 31 × 37. Ses parents sont donc les commentaires portant respectivement les ID 2, 5, 29, 31 et 37. La requête suivante permet de les obtenir :

SELECT * FROM comment WHERE id IN (2, 5, 29, 31, 37);
id | parents |                              text                              
---+---------+----------------------------------------------------------------
2  |       1 | 
5  |       2 | Second comment
29 |      10 | Second comment on the second comment
31 |     290 | Comment on the second comment on the second comment
37 |    8990 | Comment on comment on the second comment on the second comment

Le parcours se représente graphiquement comme cela :

Le fil ascendant à partir du commentaire 47
Le fil ascendant à partir du commentaire 47

La décomposition en facteurs premiers peut être exécutée dans le code applicatif qui appelle la base de données. Mais il serait bien entendu confortable de définir une fonction SQL pour exécuter une requête telle que : SELECT * FROM comment WHERE id IN PrimeFactors(332630);.

Pour compter le nombre total de commentaire(s) dans le fil, il suffira d’un COUNT.

Retrouver les enfants

Retrouver les enfants directs d’un commentaire désigné par (id, parents) revient à retrouver tous les commentaires de forme (_, parents × id). Les enfants du commentaire d’ID 5, de paire (5, 2), sont ainsi les commentaires qui ont leur colonne parents sur 5×2=105 × 2 = 10, soit en SQL :

SELECT * from comment WHERE parents = 5 * 2;
id | parents |                 text                 
---+---------+--------------------------------------
11 |      10 | First comment on the second comment
29 |      10 | Second comment on the second comment

Il s’agit bien des commentaires d’ID 11 et 29.

Insertion d’un nouveau commentaire

L’insertion d’un nouveau commentaire, vraisemblablement avec un parent connu (fût-il la racine), n’est pas aussi simple.

Les bases de données permettent généralement d’attribuer de nouvels ID générés au fur et à mesure des insertions, sans que l’applicatif appelant n’ait à s’en soucier. La BDD garantit l’unicité de chaque ID et les incrémente correctement, même en cas de deux INSERT concurrents.

Bien entendu, il ne serait pas envisageable qu’il n’en soit pas de même avec notre système d’attribution d’ID premiers. Il faut ruser et trouver une façon.

Voici une proposition d’implémentation : avoir une table de nombres premiers pré-calculés et indexé (ici jusqu’à 100 000 non inclus, ce qui donne 9592 ID à attribuer en tout), lesquels serviront à calculer les futurs ID.

SELECT * FROM primes;
n  
----
2
3
5
7
11
13
17
...
99929
99961
99971
99989
99991
(9592 rows)

Avec la table primes, il est possible, en une transaction, de trouver un nouvel ID et de l’attribuer en vue de l’insertion, comme ceci, par exemple :

-- Trouver le prochain en se basant sur l'existant
WITH newid AS (
    SELECT n
    FROM primes 
    WHERE n > (SELECT max(id) FROM comment)
    LIMIT 1;
)  -- Puis l'utiliser dans l'INSERT
INSERT INTO comment
    (id, parents, text) VALUES 
    ((SELECT n FROM newid), :parents, :text);

Moins de 10 000 ID possibles, cela peut sembler peu. Mais rappelons que notre table est ici volontairement simpliste pour clarifier le propos principal. Dans une implémentation réelle, il n’y aurait non pas qu’un seul espace de commentaire, mais plutôt un espace de commentaire pour chaque contenu (via clé étrangère sur le contenu commenté, dans la table).

id | parents  | content_id |               text
---+----------+----------------------------------------
2  |        1 |            |
3  |        2 |         42 | ...
5  |        2 |         42 | ...
3  |        2 |         69 | ...

L’identifiant de référence ne serait alors plus juste id mais plutôt le couple (id, content_id), qu’il est possible d’indexer et de mettre sous contrainte UNIQUE avec une BDD sérieuse. Chaque contenu aurait ainsi une capacité de 9592 commentaires maximum dans son espace commentaire, ce qui semble raisonnable.

Remarques

Comme vu, cette approche simplifie grandement certaines manipulations, mais elle n’est pas exempte de quelques complications en retour.

Il convient aussi de mettre en garde quant à une autre faiblesse de l’approche : la cohérence structurelle n’est plus garantie, puisque les références gérées ne sont pas exploitées.

Enfin, même si le parcours ascendant sur tous les ancêtres est possible en une seule requête simple, on remarque que le parcours descendant, lui, n’offre pas un tel luxe. Seuls les enfants directs sont accessibles simplement (mais ils le sont tous, en une seule requête).

L’approche présentée a surtout le mérite d’être amusante.



Référence

Serhiy Morozov, Hossein Saiedian and Hanzhang Wang (Janvier 2014). Reusable Prime Number Labeling Scheme for Hierarchical Data Representation in Relational Database. Journal of Computing and Information Technology. p.3, sect. 2. (DOI: 10.2498/cit.1002310)

(le papier est librement téléchargeable sur le site du journal)

5 commentaires

À chaque fois que je vois des gens croire avoir trouvé un truc utile basé sur des produits de facteurs premiers, ça ne marche pas en pratique parce que les nombres résultants croissent de façon exponentielle, et donc on a soit (1) des overflows soit (2) des performances lamentables parce que les nombres deviennent trop gros.

Comment cette proposition évite-t-elle cet éceuil ?

Note: je ne suis pas rassuré par la référence, pour une idée relativement évidente, vers un article de recherche de 2014 dans un journal de second rang. (En fait l’article parle d’un peu plus que ça, mais quand même ça fait peur.)

À chaque fois que je vois des gens croire avoir trouvé un truc utile basé sur des produits de facteurs premiers, ça ne marche pas en pratique parce que les nombres résultants croissent de façon exponentielle, et donc on a soit (1) des overflows soit (2) des performances lamentables parce que les nombres deviennent trop gros.

Comment cette proposition évite-t-elle cet éceuil ?

Absolument aucune et j’ai oublié de mentionner cet inconvénient dans mes remarques de fin. Ici, pour une poignée de commentaires, on remarque qu’on a déjà parents égal à 13 637 830 !

Je préfère repréciser, en plus de la note d’avertissement qui introduit le billet, que le propos ici n’est absolument pas en faveur de cette approche. C’est plutôt le contraire, et les faiblesses que j’évoque lui donnent, je pense, le coup de grâce.

Si ta question est sérieuse, je ne peux donc pas y répondre puisqu’il n’a jamais été question d’éviter un quelconque écueil en vue d’une méthode utilisable en pratique.

Pour une véritable solution à base de SQL pur, il y a les CTE récursives, voire des véritables implémentations de traversée de graphe pour ceux qui ont la chance d’utiliser une BDD qui les supporte (sur Oracle, je crois ?). Dans des cas simples comme la restitution d’un espace commentaire hiérarchisé, je suis à peu près certain que les performances de ces approches plus orthodoxes sont tout à fait raisonnables.

+1 -0

J’avoue avoir bugué sur le fait que les lignes d’exemple n’étaient pas ordonnées par "fil" mais par "niveau", et encore, avec leurs textes, c’est pas super simple de s’y retrouver…

Sinon, pour des arbres moins simples, il reste toujours la représentation intervallaire, qui permet aussi de se passer de self-JOIN

+0 -0

Bonjour,

Merci pour cette petite découverte !

Petite question: est-ce qu’on pourrait implémenter la même chose en utilisant des champs de bits au lieu de nombres premiers ? ET question plus compliquée, est-ce que ça permettrait de stocker des valeurs plus petites ou justement pas ? Je n’en suis pas convaincu… je ne suis pas non plus convaincu que ça rendrait la méthode plus efficace.

+0 -0
Connectez-vous pour pouvoir poster un message.
Connexion

Pas encore membre ?

Créez un compte en une minute pour profiter pleinement de toutes les fonctionnalités de Zeste de Savoir. Ici, tout est gratuit et sans publicité.
Créer un compte