English
Ni if, ni while ; ni map, ni reduce
L'algèbre relationnelle comme alternative à la programmation impérative et fonctionnelle.
Introduction
Je fais la promotion de l'algèbre relationnelle depuis plus de 20 ans maintenant. J'ai par exemple écrit Relations as First-Class Citizen il y a plus de 10 ans. Avec mon collègue Felix nous avons lancé https://www.relational-algebra.dev/ plus récemment pour documenter la librairie Bmg utilisée dans le backend de Klaro Cards.
L'algèbre relationnel est souvent cataloguée "bases de données only". Personne ne semble voir que c'est un outil indépendant, qui peut être appliqué en programmation classique avec d'excellents résultats : moins verbeux, plus productif et plus correct. C'est ce que je propose de montrer ici.
L'exemple
On va repartir de l'exemple du post précédent mais le complexifier un peu. On souhaite calculer les colonnes du Kanban "organisé par mois", mais également les groupes de cartes à afficher dans chaque colonne. L'utilisateur doit pouvoir afficher ou cacher les colonnes vides.
Avant de continuer la lecture, je vous invite à prendre un moment pour vous. Comment programmeriez-vous cette fonctionnalité ?
- Elle est simple : grouper les blog posts par mois
- Mais pas simpliste : il nous faut tous les mois entre deux dates, même ceux sans blog post
Vous pouvez retourner voir la solution précédente qui calculait les colonnes nécessaires. Dans ce blog post je ne vais pas améliorer l'algorithme Typescipt donné en fin d'article. Je vais plutôt détailler pas à pas comment utiliser l'algèbre relationnelle pour une solution sans boucle, sans if, sans map ni reduce.
Une approche data-driven
Une chose qui va peut-être vous choquer, car inhabituelle en programmation orientée objet, c'est qu'on va suivre une approche résolument orientée données, ou informationnelle. Autrement dit, je ne vais pas déranger de classe ou d'objet Article ou autre concept du domaine comme KanbanColumn. Ces classes et objets sont un détail d'implémentation (si cette phrase pique un peu, rendez-vous à la dernière section de cet article).
Notre problème et sa solution sont illustrés comme suit.
A l'entrée, nous avons des articles de blog dans une Relation :
+----+------------------+----------------------------------+
| id | publication_date | title |
+----+------------------+----------------------------------+
| 1 | 2025-01-02 | Out of the Tar Pit |
| 2 | 2025-01-17 | Relations as First-Class Citizen |
| 3 | 2025-03-11 | Bmg, a Relational Algebra |
+----+------------------+----------------------------------+
soit, en javascript, ou ici ruby :
articles = [
{ id: 1, publication_date: "2025-01-02", title: "Out of the Tar Pit" },
{ id: 2, publication_date: "2025-01-17", title: "Relations as First-Class Citizen" },
{ id: 3, publication_date: "2025-03-11", title: "Bmg, a Relational Algebra" }
]
Et le résultat qu'on cherche doit ressembler à la Relation ci-dessous (elle contient des "sous"-Relations comme valeurs, ce qui est parfaitement permis par la théorie).
Cette Relation capture l'information suivante :
- le mois de janvier a vu deux articles être publiés, "Out of the Tar Pit" le 02 et "Relations as First-Class Citizen" le 17 ;
- le mois de février n'a vu aucun publication ;
- le mois de mars une publication, "Bmg, a Relational Algebra" le 11.
Ou en résumé: Le mois [month], les [articles] indiqués on été publiés. Dans la suite, je mettrai chaque fois cette "sémantique informationnelle" en commentaire. Elle est essentielle dans l'approche : elle permet de raisonner sur ce qu'on veut, mais également de documenter sa solution.
// Le mois [month], les [articles] indiqués on été publiés
+------------+--------------------------------------------------------------+
| month | articles |
+------------+--------------------------------------------------------------+
| 2025-01-01 | +----+------------------+----------------------------------+ |
| | | id | publication_date | title | |
| | +----+------------------+----------------------------------+ |
| | | 1 | 2025-01-02 | Out of the Tar Pit | |
| | | 2 | 2025-01-17 | Relations as First-Class Citizen | |
| | +----+------------------+----------------------------------+ |
| |
| 2025-02-01 | +----+------------------+----------------------------------+ |
| | | id | publication_date | title | |
| | +----+------------------+----------------------------------+ |
| | +----+------------------+----------------------------------+ |
| |
| 2025-03-01 | +----+------------------+----------------------------------+ |
| | | id | publication_date | title | |
| | +----+------------------+----------------------------------+ |
| | | 3 | 2025-03-11 | Bmg, a Relational Algebra | |
| | +----+------------------+----------------------------------+ |
+------------+--------------------------------------------------------------+
soit, en javascript ou ruby :
result = [
{
month: "2025-01-01",
articles: [
{ id: 1, publication_date: "2025-01-02", title: "Out of the Tar Pit" },
{ id: 2, publication_date: "2025-01-17", title: "Relations as First-Class Citizen" }
]
},
{
month: "2025-02-01",
articles: [
]
},
{
month: "2025-03-01",
articles: [
{ id: 3, publication_date: "2025-03-11", title: "Bmg, a Relational Algebra" }
]
}
]
Aperçu de l'implémentation
La solution tient en quelques lignes seulement. Vous pouvez aussi retrouver le code complete sur github. Pas d'inquiétude, on va regarder tout cela en détails dans les sections suivantes.
# 1. Compute the month of each article
monthly_articles = articles.extend({
month: ->(t) { t[:publication_date].beginning_of_month },
})
# 2. Find min and max month
minmax = monthly_articles.summarize([], {
:min => Bmg::Summarizer.min(:month),
:max => Bmg::Summarizer.max(:month),
}).one
# 3. Generate all months of interest
all_months = Bmg::Relation.generate(minmax[:min], minmax[:max], step: ->(d){ d.next_month }, as: :month)
# 4. Find, for each month, the articles published
articles_per_month = all_months.image(monthly_articles, :articles, [:month])
# 5. Remove empty months
result = articles_per_month.exclude(->(t) { t[:articles].empty? })
Comme le code le suggère, on découpe le problème en sous-problèmes :
- Calculer le mois de chaque publication, à l'aide d'
extend - Trouver le premier et dernier mois, à l'aide de
summarize - Générer la liste complète des mois à considérer, à l'aide de
generate - Ajouter à chacun sa liste d'articles, à l'aide de
image - Optionnel: supprimer les mois vides, à l'aide de
restrictouexclude
Malgré le fait que j'utilise le terme "liste" ci-dessous, nous n'allons utiliser que des Relations et les opérateurs indiqués. Ils prennent tous une Relation en entrée et génèrent une Relation en sortie. Je montre tous les résultats intermédiaires.
Calculer le mois de chaque publication
L'opérateur extend étend sa relation d'entrée avec un ou plusieurs attributs calculés. Ici, on calcule simplement la date de début de mois grâce à ActiveRecord#beginning_of_month qui apparait maintenant sous un nouvel attribut month :
monthly_articles = articles.extend({
month: ->(t) { t[:publication_date].beginning_of_month },
})
// La publication [id] a été publiée au mois de [month]
+----+------------------+----------------------------------+------------+
| id | publication_date | title | month |
+----+------------------+----------------------------------+------------+
| 1 | 2025-01-02 | Out of the Tar Pit | 2025-01-01 |
| 2 | 2025-01-17 | Relations as First-Class Citizen | 2025-01-01 |
| 3 | 2025-03-11 | Bmg, a Relational Algebra | 2025-03-01 |
+----+------------------+----------------------------------+------------+
Trouver les premier et derniers mois
L'opérateur summarize nous permet de trouver les deux mois qui formeront les frontières du Kanban. C'est un peu l'équivalent de SELECT MIN(...) GROUP BY ... en SQL : il permet de "résumer" l'information représentée dans une relation. On va l'utiliser ici avec un ensemble vide d'attributs de regroupement ([]) et spécifier qu'on souhaite calculer le plus petit (min) et plus grand (max) mois :
minmax_relation = monthly_articles.summarize([], {
:min => Bmg::Summarizer.min(:month),
:max => Bmg::Summarizer.max(:month),
})
Le résultat est le suivant avec sa sémantique informationnelle en commentaire
// Le premier mois où un article a été publié est [min] et le dernier est [max]
// (chacun représenté par son premier jour)
+------------+------------+
| min | max |
+------------+------------+
| 2025-01-01 | 2025-03-01 |
+------------+------------+
Générer la liste complète des mois à considérer
Nous allons ici appliquer la même technique que dans l'article de blog précédent, l'équivalent de generate_series en PostgreSQL :
minmax = minmax_relation.one
months = Bmg::Relation.generate(minmax[:min], minmax[:max], step: ->(d){ d.next_month }, as: :month)
La première ligne utilise one un opérateur non relationnel qui extrait le seul et unique enregistrement d'une relation.
{ min: '2025-01-01', max: '2025-03-01' }
L'opérateur generate génère une relation (sans en prendre une autre en entrée). Ici on lui donne nos deux dates min et max et une fonction d'incrément, et elle génère la relation suivante :
// Le mois [month] se situe entre deux mois où des articles ont été publiés
+------------+
| month |
+------------+
| 2025-01-01 |
| 2025-02-01 |
| 2025-03-01 |
+------------+
Ajouter à chacun sa liste d'articles
Pour cette dernière étape, on fait appel à un opérateur un peu magique, image. Cet opérateur étend sa relation d'entrée - la "liste" des mois - avec un nouvel attribut articles. Ce dernier sera la sous-relation obtenue en filtrant les articles qui ont la même valeur pour l'attribut commun (:month). C'est similaire à un LEFT JOIN + ARRAY_AGG en PostgreSQL :
articles_per_month = months.image(monthly_articles, :articles, [:month])
// Le mois [month], les [articles] indiqués on été publiés
+------------+--------------------------------------------------------------+
| month | articles |
+------------+--------------------------------------------------------------+
| 2025-01 | +----+------------------+----------------------------------+ |
| | | id | publication_date | title | |
| | +----+------------------+----------------------------------+ |
| | | 1 | 2025-01-02 | Out of the Tar Pit | |
| | | 2 | 2025-01-17 | Relations as First-Class Citizen | |
| | +----+------------------+----------------------------------+ |
| |
| 2025-02 | +----+------------------+----------------------------------+ |
| | | id | publication_date | title | |
| | +----+------------------+----------------------------------+ |
| | +----+------------------+----------------------------------+ |
| |
| 2025-03 | +----+------------------+----------------------------------+ |
| | | id | publication_date | title | |
| | +----+------------------+----------------------------------+ |
| | | 3 | 2025-03-11 | Bmg, a Relational Algebra | |
| | +----+------------------+----------------------------------+ |
+------------+--------------------------------------------------------------+
Une autre manière de comprendre image est de le voir comme un raccourci pour extend + restrict (restrict est introduit dans la section suivante) :
articles_per_month = months.extend({
articles: ->(t) { monthly_articles.restrict(month: t[:month]) }
})
Cacher ou afficher les mois vides
Si l'on souhaite cacher les mois vides, on peut utiliser l'opérateur restrict pour les filtrer après coup (c'est un peu comme un WHERE en SQL):
result = articles_per_month.restrict(->(t) { !t[:articles].empty? })
ou plus élégamment exclude, son opposé :
result = articles_per_month.exclude(->(t) { t[:articles].empty? })
// Le mois [month], les [articles] indiqués on été publiés
+------------+--------------------------------------------------------------+
| month | articles |
+------------+--------------------------------------------------------------+
| 2025-01 | +----+------------------+----------------------------------+ |
| | | id | publication_date | title | |
| | +----+------------------+----------------------------------+ |
| | | 1 | 2025-01-02 | Out of the Tar Pit | |
| | | 2 | 2025-01-17 | Relations as First-Class Citizen | |
| | +----+------------------+----------------------------------+ |
| |
| 2025-03 | +----+------------------+----------------------------------+ |
| | | id | publication_date | title | |
| | +----+------------------+----------------------------------+ |
| | | 3 | 2025-03-11 | Bmg, a Relational Algebra | |
| | +----+------------------+----------------------------------+ |
+------------+--------------------------------------------------------------+
Une alternative un peu moins naïve revient à ne pas faire l'effort de calculer tous les mois avec generate si c'est pour les supprimer ensuite. La section suivante propose une alternative qui va dans ce sens.
Aller plus loin
La section précédente a montré comment appliquer l'algèbre relationnelle pure à la problématique du regroupement des articles par mois. Dans cette section, on élargit le cadre : comment encapsuler l'ensemble dans une fonction, et comment la tester ?
Le programme complet
Si l'on souhaite une fonction qui prend les articles et retourne le groupement recherché, avec ou sans les mois vides, on peut encapsuler l'ensemble du code ainsi :
def group_articles_per_month(articles, hide_empty_columns = false)
monthly_articles = articles.extend({
month: ->(t) { t[:publication_date].beginning_of_month },
})
all_months = if hide_empty_columns
monthly_articles.project([:month])
else
minmax = monthly_articles.summarize([], {
:min => Bmg::Summarizer.min(:month),
:max => Bmg::Summarizer.max(:month),
}).one
Bmg::Relation.generate(minmax[:min], minmax[:max], step: ->(d){ d.next_month }, as: :month)
end
all_months.image(monthly_articles, :articles, [:month])
end
Dans cette variante, l'opérateur project est utilisé pour extraire de la relation de départ les mois avec au moins un article publié. Cet opérateur ne retourne jamais de doublons, donc le mois de janvier n'apparaît qu'une fois :
// monthly_articles.project([:month])
// Le mois de [month] a au moins un article publié
+------------+
| month |
+------------+
| 2025-01-01 |
| 2025-03-01 |
+------------+
D'où viennent les données au départ ?
L'intérêt de l'approche c'est que l'origine des articles n'a pas vraiment d'importance. Il peut s'agit d'un literal (par exemple dans un test unitaire) :
articles = Bmg::Relation.new([...])
result = group_articles_per_month(articles)
Un fichier json fera également l'affaire, si l'on convertit la date de publication en instance de la classe Date. L'opérateur transform permet d'appliquer une transformation à toutes les valeurs d'un attribut. Bmg supporte l'utilisation d'une classe qui possède une méthode parse :
articles = Bmg::Relation
.json_file("articles.json")
.transform(publication_date: Date)
# shortcut for .transform(publication_date: ->(str) { Date.parse(str) })
result = group_articles_per_month(articles)
Enfin, les relations peuvent évidemment provenir d'une base de données SQL :
database = Sequel.connect('sqlite://blog.sqlite3')
articles = Bmg.sequel(:articles, database)
result = group_articles_per_month(articles)
Tester la solution
Dans le post précédent j'ai déjà parlé de post-conditions dans la spécification, qui guidaient l'effort de testing. Je vous propose dans cette section de les passer en revue, toujours en utilisant l'algèbre relationnelle.
Cet effort de testing est un peu surfait, puisqu'il revient en partie à déconstruire ce qu'on vient de construire. Ca reste un bel exercice d'algèbre. On va commencer par s'aider un peu pour la suite en ajoutant le mois suivant pour chaque ligne :
result = group_articles_per_month(articles).extend({
:next_month => ->(t) { t[:month].next_month }
})
Testing d'un seul cas
Sur base de l'exemple, un premier test permet de vérifier intuitivement qu'on a les résultats qu'on souhaite. Si l'on compte simplement les résultats, on peut prendre l'approche suivante :
assert_equal(
result.count,
3
)
assert_equal(
result
.transform({
:articles => :count,
:month => :to_s
})
.y_by_x(:articles, :month),
{
"2025-01-01" => 2,
"2025-02-01" => 0,
"2025-03-01" => 1
}
)
Dans cet exemple la méthode y_by_x permet de quitter le monde relationnel et d'obtenir un mapping entre le nom des mois et le nombre de publications pour chacun.
Solution complète
La solution est complète si tous les articles de départ sont présent dans le résultat final. En d'autres termes, qu'aucun ne manque :
assert_empty (
articles
.not_matching(result.ungroup(:articles), [:id])
)
On utilise l'opérateur not_matching qui est l'équivalent de WHERE NOT EXISTS en SQL avec une clause d'égalité sur l'id.
Solution correcte
La solution est correcte si la date de publication de chaque article est bien du mois indiqué. C'est-à-dire qu'il n'existe aucun article qui viole cette contrainte :
assert_empty (
result
.ungroup(:articles)
.exclude(Predicate.between(:publication_date, :month, :next_month))
)
On utilise l'opérateur ungroup qui défait en quelque sorte ce qu'image a fait précédemment et redonne une Relation "plate".
Solution continue
La solution est continue si tous les mois sont représentés entre le mois min et le mois max. En d'autres termes, si tous les mois sont aussi un mois suivant, à l'exception du premier :
assert_empty (
result
.exclude(month: minmax[:min])
.not_matching(
result
.project([:next_month])
.rename(next_month: :month),
[:month]
)
)
Les opérateurs project et rename nous permettent de comparer les résultats à eux-mêmes. C'est sans doute la condition la moins intuitive. Pensez qu'elle teste l'assertion suivante : à l'exception du premier, il n'existe pas de mois qui ne soit pas le suivant d'un autre.
Solution minimale
Enfin, la solution est minimale si les premier et dernier mois ont au moins un article.
assert_empty (
result
.restrict(Predicate.in(:month, minmax.values))
.restrict(Predicate.empty(:articles))
)
Conclusion
J'ai présenté ici une approche relationnelle pour résoudre un problème simple, mais pas trivial, de regroupement de données. La solution est originale dans le sens où elle n'utilise aucune construction de programmation impérative (if, repeat, while, until, foreach) ni de programmation fonctionnelle (map, reduce, fold), ni de récursion. L'approche relationnelle est à la fois puissante, élégante, et peu verbeuse. Elle permet à la fois de mettre en oeuvre la solution et de tester la spécification en termes de post-conditions.
J'espère que cet article vous aura plu et vous aura montré quelque chose que vous ne connaissiez pas encore :-) Vous pouvez retrouver l'ensemble du code sur github.
La librairie Bmg est utilisée ici et offre l'algèbre relationnelle aux programmeurs Ruby. Elle est inspirée d'une algèbre plus théorique Tutorial D, proposée par Chris Date & Hugh Darwen dans leur livres sur le relationnel, et implémentée dans l'outil Rel. Si l'approche et/ou Bmg vous plait, sachez que j'ai récemment démarré une implémentation Typescript, à laquelle vous êtes invité à contribuer sur github: https://github.com/enspirit/bmg.js
Enfin, si vous appréciez ce travail, le meilleur moyen de nous soutenir est d'utiliser Klaro Cards.
Annexe : classes et objets, un détail d'implémentation ?
Si vous êtes un adapte de l'orienté object, vous vous posez sans doute la question : pourquoi n'introduire aucune classe Article, Mois, Liste<Article> ou KanbanColumn<Article> pour représenter les concepts du domaine ?
L'approche "résolument orientée données" introduite ici reflète ce qui "coule" d'un composant architectural à l'autre : de l'information. En effet, backend et frontend ne s'échangent pas des classes et des objets. Ils s'échangent des données qui capturent l'information utile.
C'est en ce sens que j'ai osé indiquer que les classes et les objets étaient un détail d'implémentation : on peut construire un logiciel où frontend et backend collaborent parfaitement sans jamais partager les classes et les objects. Ces derniers ne sont pas essentiels. Par contre, on ne peut pas créer ce logiciel sans que l'information soit partagée. Elle, c'est sûr, est essentielle.
On retrouve d'ailleurs ici le principe d'essentialité cher à Codd lors du Great Debate. Mais ça, c'est pour un autre blog post.
