C’est typiquement le genre d’article qui nécessite des corrections, des remarques et peut-être un débat. Alors n’hésitez pas.

Code et data

Pas de code sans données, car le but d’un code est de tourner et de produire des résultats et, pour ce faire, le code doit “manger” des données.

On peut voir le code dans sa forme la plus abstraite comme un algorithme dont le rôle serait de produire des preuves. Mais on peut aussi voir le code comme un algorithme qui ne fait pas simplement que valider et prouver mais également qui produit des changements d’états et des évènements qui, au sens littéral du terme, changent le monde.

On a ici un parallèle avec les “speech acts” de Searle et Austin dont Henry Story avait parlé dans son intervention au MeetUp Semantic Web de Février 2011.

Quiconque écrit un programme s’attend en effet à “changer le monde”, ne serait-ce que pour écrire “Hello World” sur un terminal. Changer le monde avec des algorithmes et du code, Microsoft, Google,  Facebook et d’autres l’on fait, et l’ensemble des développements en Open Source peut-être plus encore.

Pas de code sans données donc.  Or ces données sont stockées dans des supports de mémoires différents selon qu’elles sont en mémoire vive, sur un système de fichier, ou dans une base de donnée. Et chaque support de mémoire utilise un modèle de données qui n’est pas forcément le même. Ce qui nous ramène à la difficile collaboration entre les développeurs et les gestionnaires de base de données.

Si les développeurs et les administrateurs de base de données doivent collaborer, la réalité est parfois toute autre : les développeurs ne comprennent pas toujours le SQL et les RDB (bases de données relationnelles), et les DBA (administrateurs de base de données) ne voient les développeurs que comme de dangereux cowboys qui veulent massacrer l’intégrité de leur données (“mon précieux …”).

Le DBA

Le développeur

“Impedance mismatch”

La réalité est que les modèles de données utilisés dans les langages développement et dans les systèmes de stockage des données ne sont pas les mêmes : modèle objet et modèle tableau.

C’est ce qu’écrivait Yves-Marie Pondaven, que je citais également dans mon intervention au MeetUp Semantic Web de Décembre 2010, et dont je reproduis ci-après le schéma qu’il avait fait et dans lequel on voit que l’on passe son temps à basculer du modèle relationnel au modèle objet puis au modèle document et inversement.

Aussi disais-je que la plupart des CPUs de la planète sont occupés à faire des transformation et re-transformation entre des modèles de données différents. On peut donc au moins dire que cela a un impact en terme de performance mais aussi en terme environnemental non négligeable (de l’ordre de l’impact carbone sur la planète de toute l’industrie du transport aérien).


Cette question des différences entre les modèles de données n’est pas nouvelle, et elle a d’ailleurs fait l’objet d’une discussion intéressante entre Michel Volle et Laurent Bloch. Plus généralement, elle fait référence à “l’impedance mismatch” de George Copeland & David Maier 1984:

The problem with having two languages is“impedance mismatch ” One mismatch is conceptual – the data language and the programming languages might support widely different programming paradigms. […]

The other mismatch is structural -thelanguages don’t support the same data types, […]

Objets versus Tables

Avec les travaux d’Erik Meijer, de chez Microsoft Research, on peut essayer d’aller plus loin dans l’analyse de la situation, et je vais suivre à présent son argumentation, telle qu’il a exposé lors du WebWorkers Camp parisien du 16 avril 2011, et en faisant référence au papier qu’il a publié en Mars 2011 : A co-Relational Model of Data for Large Shared Data Banks.

L’objet-graphe et le stockage par clé/valeur (Key/Value)

Tout commence par une citation de Donald Knuth :

“I do consider assignment statements and pointer variables to be among computer science’s most valuable treasures.”

Pourquoi Meijer souligne-t-il ainsi l’importance des pointeurs pour ensuite assimiler l’équivalence entre le modèle objet et le stockage par clé-valeur ? :

“In the rest of this article we conveniently confuse the words object (graph) and key-value store.”

Deux choses ici :

  1. D’une part, l’équivalence entre objet et graphe.
  2. D’autre part, l’assimilation du modèle objet au mécanismes de stockage par clé-valeur.

Si l’objet est assimilé à un graphe c’est parce qu’une des caractéristiques de l’objet est d’avoir la structure d’un graphe, à savoir que les objets sont reliés entre eux par des relations qui, en l’occurence, sont dirigées (d’où la flèche) :

Référons-nous à wikipedia (article sur Object Graph) pour comprendre l’assimilation de l’objet-graphe à un mécanisme de stockage des données clé-valeur :

“An object graph is a directed graph, which might be cyclic. When stored in RAM, objects occupy different segments of the memory with their attributes and function table, while relationships are represented by pointers or a different type of global handler in higher-level languages.”

Un Objet est donc stocké en mémoire en encapsulant avec lui avec tout ce qui le caractérise (attributs et fonctions). Si cet objet-graphe est stocké dans différentes parties – ou segments – de la mémoire, les relations entre ces différentes parties, elles, sont représentés par des pointeurs (ou par des mécanismes plus généraux embarqués dans les langages de plus haut niveaux). Les pointeurs étant des types de données dont la valeur est l’adresse vers un autre objet stocké en mémoire.

Paradoxalement, le concept de pointeur rebute souvent les étudiants en informatique alors que l’architecture du web qu’ils utilisent tous les jours en est exactement la mise en oeuvre avec des ressources stockées qui sont accessibles via des relations qui sont représentées par des adresses, les URLs.

Voilà donc pour le côté “stockage en mémoire” des objets manipulés par les programmes. Basiquement, il s’agit d’un mode de stockage de type Key -Value qui représente une part importante de l’utilisation des bases NoSQL et sur lequel, je l’ai dit, repose l’architecture du web (de là à justifier le NoSQL comme mouvement surdéterminé par l’architecture du web, comme son milieu technologique d’émergence, il n’a qu’un pas).

Le stockage de données par tables

Passons maintenant au modèle utilisé par les bases de données relationnelles, représenté non plus par des objets mais par des tables.

Par rapport au modèle objet, la table va fractionner les données pour les lier d’une manière différente du modèle avec pointeur utilisé pour l’objet-graphe.

Alors que la manipulation des donnés en mémoire sous forme de graphe était au plus proche de leur mode de stockage physique en RAM, le modèle relationnel va “plaquer” un mode de stockage et de requêtage qui repose sur le modèle des tables. D’ailleurs, la première chose que l’on fait pour créer une base de données c’est d’écrire :

CREATE TABLE.

Ici il n’y a plus seulement une adresse pour une valeur (Key-Value), mais une valeur ( la primary key) dans plusieurs lignes. C’est la raison pour laquelle le modèle relationnel est aussi appelé Primary/Foreign Key.

Les contournements du modèle relationnel

Le modèle relationnel n’est pas évident dans sa compréhension et dans son utilisation. Meijer souligne tout cela par un raccourcit ironique :

  1. Le concepteur de base de données enlève la structure originairement hiérarchique et objet pour lui appliquer un modèle normalisé par Tables ;
  2. Le développeur doit ensuite retrouver la forme objet-graphe originale pour son développement. On a ainsi eu une vague d’ORM (Mapping Objet/Relationnel) qui, comme leur nom l’indique ajoutent une sur-couche objet au modèle relationnel afin que le programmeur puisse utiliser le stockage relationnel sans en connaître toutes les subtilités ;
  3. Même du côté de la base de données, celui qui l’implémente doit rajouter une couche de stockage objet-graphe et Clé-Valeur en construisant un index de la base de données, en marge du modèle par Tables, pour pré-calculer des réponses à des requêtes.

A croire que, dès qu’on veut utiliser les bases de données relationnelles, il faille changer de modèle de données pour en revenir au modèle objet-graphe et le stockage par Clé-Valeur.

Sortir de l’aporie

Jusqu’ici rien de bien nouveau dans le “dysfonctionnement relatif” entre modèle Objet et modèle Relationnel, si ce n’est la montée en puissance des base NoSQL. Mais celles-ci n’ont pas vraiment de modèle de requêtage très élaboré (pas de modèle mathématique) : en effet il y a plutôt des recettes de requêtage dans le monde NoSQL.

Là où Meijer est intéressant, c’est dans la manière dont il formule le problème pour dépasser la vision d’opposition entre SQL et NoSQL. De la logique d’opposition on bascule alors dans une logique de composition, et les choses deviennent beaucoup plus claires.

Meijer, tel Ménon, fait son petit schéma (fig. 6 pour le modèle objet, et fig.7 pour le modèle en tables) et constate que :

  • le modèle objet est défini par intension
  • le modèle table est défini par extension.
  • et surtout, on voit bien sur le schéma que le sens des flèches est inversé.

Je rappelle brièvement qu’une définition par intension décrit la liste des propriétés qui doivent être vérifiées pour qu’un élément appartienne à l’ensemble ainsi défini. Dans la définition par extension c’est la liste des éléments qui définit l’identité de l’ensemble :

“Toute classe d’éléments peut être définie en extension (en nommant ou en désignant chaque individu qui en fait partie) ou en intension, par une description (spécification d’un certain nombre de prédicats) qui définit la classe. L’intension s’identifie ainsi au concept.”

Par exemple, la classe des rois de France peut être désigné extensionnellement en donnant une liste de noms, ou intensionnellement par le concept « roi de France » (c’est-à-dire le prédicat, la propriété « être un roi de France »).” Intension et Extension, Wikipedia.

En informatique, toute donnée doit être porteuse d’une identité qui la distingue de toute autre donnée. Toute donnée, c’est à dire toute information disponible pour un calcul, doit disposer d’une identité. Et celle-ci passe par un référent (par exemple un identifiant), qui n’est autre qu’une métadonnée (Cf. Sur les métadonnées).

Il se trouve qu’avec le modèle objet-graphe, la métadonnée qui sert de référent pour l’identité de l’objet n’est pas une valeur mais l’adresse d’une valeur (le pointeur). Alors qu’avec le modèle en Tables, la métadonnée est une valeur (c’est la clé primaire).

La métadonnée qui sert de référent peut donc être définie par intension ou part extension :

  • par intension, on a une clé qui est une adresse
  • par extension, on a une valeur (clé primaire) qui est présente dans toutes les lignes des tables qui constituent l’identité de l’objet.

On comprend aisément la forte contrainte d’intégrité requise pour les bases de données relationnelles : une modification doit se déployer sur l’ensemble du système, de manière extensive, pour en garantir l’intégrité. Avantage à la maîtrise des données mais difficultés à passer à l’échelle du web.

Mais avec son petit schéma, Meijer, remarque que le modèle Objet et le modèle Table sont fort similaires : ce sont des graphes orientés, mais avec une orientation inverse :

Ne manque plus qu’à Erik Meijer de chercher “Mathematics arrow reverse” dans Google pour tomber sur la page Wikipedia de la théorie mathématique des catégories.

Théorie mathématique des catégories et le concept de dualité : “NoSQL is CoSQL”

De la théorie mathématique des catégories, Meijer retient le concept de dualité, ou catégorie duale :

À partir d’une catégorie opposée ou duale, en prenant les mêmes objets, mais en inversant le sens des flèches.

Plus précisément :

Il est clair que la catégorie duale de la catégorie duale est la catégorie de départ :

Cette dualisation extrêmement simple permet de symétriser la plupart des énoncés, ce qui peut être douloureux pour les débutants…

Ce “détour” par les mathématiques permet finalement à Meijer d’affirmer que :

  • SQL et NoSQL ne sont pas incommensurables et incompatibles ;
  • NoSQL s’appuie en fait sur un modèle de donnée qui reléve d’une catégorie duale où l’on a les mêmes objets mais en inversant le sens des flèches ;
  • Donc NoSQL est en fait CoSQL ;
  • A partir de là, on peut fonder les modes de requêtes NoSQL sur une théorie mathématique, comme s’était le cas pour SQL, ce qui permettra non seulement de standardiser les requêtes pour différentes bases NoSQL mais aussi de fonctionner pour les bases SQL.

Le rôle d’une interface est précisément de faire cohabiter des modèles différents, qui ne sont certes pas opposé et incompatibles sans quoi l’existence même d’interface ne saurait être possible.

Avec son langage de requêtage “universel” LINK, Meijer ne fait rien d’autre que d’avoir trouvé, via le recours aux théories mathématiques, une interface entre des modèles qui étaient présentés comme apparemment opposés. L’interface est à ce tire une composition.

Bien qu’étant universel sur le papier, LINK reste toutefois implémenté dans le monde .NET. Il faudrait donc une implémentation de cette démarche pour chaque langage pour parler vraiment d’un langage de requête universel.

Langage fonctionnels purs et monades

On connaît l’implication de Meijer dans la valorisation, la promotion des langages fonctionnels et notamment de Haskell (je vous renvoie à mon article Apprendre Haskell dans lequel je donnais les liens vers les tutoriels video de Meijer sur Haskell).

En fait, l’approche qu’il a implémenté avec LINK lui a été soufflé par les monades en Haskell. Pourquoi celà ?

Rendre compatible ce qui est incompatible est précisément le rôle des monades en Haskell. Puisque le langage est pur et fonctionnel (aucun effet de bord et immutabilité) il ne peut interagir avec le monde et le changer, il faut définir un lieu d’où les effets de bord (comme l’impression sur un terminal) seront quand même possibles.

Les effets de bord sont souvent dûs à des erreurs du point de vue des Types des données manipulés. Par exemple la fonction qui affiche l’heure n’est pas pure car à chaque fois qu’on demande la valeur, la fonction produit un résultat différent (l’heure tourne). Donc, un travail sur le Type System peut contourner la difficulté en considérant que la fonction ne revoie pas un INT mais un CHAR : on a contourné l’effet de bord en maîtrisant la définition par intension de la fonction dans la configuration des types.

Pour bien comprendre l’intérêt de cette question, on peut y retrouver un usage dans les architectures RESTful. Ainsi “Idempotence” en REST signifie “Pureté” en langage fonctionnel : la valeur d’une fonction ne change pas dans le temps (pas d’effet de bord). Par où l’on voit que le style d’architecture REST est un style qui s’appuie sur une architecture fonctionnelle pure par défaut : POST n’est pas une fonction idempotente (pure) car elle va modifier l’état du système.

Mais toute approche fonctionnelle pure doit composer avec le non-pur. Les programmes sont faits pour changer les états de systèmes et pour changer le monde. Les monades sont faîtes pour effectuer cette composition en créant des Types qui vont décrire ces effets de bord (IO, Exception, Animation, Collection). Les exceptions sont intégrées et gérées par le système qui conserve ainsi sa pureté grâce à son Type System (il n’y a pas que Haskell qui utilise cette approche par monades, Java aussi avec “throws Exceptions”).

Les monades transforment ce qui est mutable en quelque chose d’immutable (mutable et immutable étant les termes informatiques anglais utilisés).

En fait, je me demande si la modification que l’on fait avec les monades ne consisterait pas à définir de nouveaux Types non plus par intension mais par extension.

SQL et CoSQL à la lumière du concept de métastabilité.

Meijer rapproche l’articulation, qui est composition, entre SQL et NoSQL à celle du Ying et du Yang chinois, l’un désignant l’ouvert et l’autre le fermé. Puis il expose la dualité, au sens mathématique du terme, entre SQL et CoSQL, entre le fermé et l’ouvert :

On reconnaît dans cette distinction celle que j’avais essayé de faire entre technologies de gestion et technologies relationnelles, c’est à dire entre stabilité et métastabilité (Cf. Les technologies relationnelles dans les systèmes d’information et Métastabilité et archtitectures logicielles )

Le sens des flèches : des flèches du web au PageRank de l’index de Google.

Ouverture et métastabilité du web.

J’ai déjà rappelé l’anecdote à propos de Tim Berners Lee qui n’avait pas trouvé d’investisseur lors du Symposium sur les systèmes hypertextes en venant présenter son invention : le web.
Ceux qui pensaient en matière de technologies de gestion et de système clos et stable ne comprenaient pas l’intérêt d’un système métastable comme le web qui ne garantissait pas l’intégrité du système. Par exemple on peut faire des liens vers des ressources qui n’existent pas et provoquer une erreur. Seulement voilà, cet effet de bord est prévu dans le web, c’est précisément l’erreur 404 que connaît et intègre le système (utilisation du principe de la monade) et qui fait qu’un lien brisé n’a jamais empêché le web de fonctionner.

Google : à rebrousse-poils du web

Le projet backrub, qui fut l’ancêtre de Google et du PageRank, prenait le web à rebrousse-poil en se proposant d’identifier les pages HMTL qui lient une page donnée (Cf. L’idée qui fonda Google). C’est prendre le web à rebrousse-poil car les liens HTML sont reconstitués à l’envers : dans un cas la page HTML est le “parent” qui contient les liens vers les pages “enfants”, dans l’autre c’est les pages “enfants” qui lient vers la page “parent” pour lui donner un poids (un ranking).

A ce titre, on peut dire que le modèle d’affaire de Google s’est constitué mathématiquement comme une dualité du web, selon la théorie des catégories : Google = Co(Web).

*

Il serait intéressant de rejouer ce raisonnement en y intégrant ce qu’écarte Meijer, à savoir les bases NoSQL qui ne sont pas sur le modèle document clé-valeur mais sous une forme d’un graphe typé. C’est à dire en prenant en compte les éléments de la présentation (slides) An Overview of Data Management Paradigms: Relational, Document, and Graph, de Marko Rodriguez.