Modèles de données & langages de requête

Le modèle de données est sans doute la partie la plus importante du développement logiciel, car son effet est profond : il influence non seulement la façon dont le code est écrit, mais aussi la manière dont nous pensons le problème que nous résolvons. Toute application empile des modèles les uns sur les autres : vous modélisez le monde réel en objets et structures de données ; ces structures s'expriment dans un modèle générique (documents JSON, tables relationnelles, graphe) ; ce modèle s'exprime à son tour en octets sur le disque, eux-mêmes traduits en courants électriques. Chaque couche masque la complexité de celle du dessous en offrant une interface propre.

Aucun modèle n'est neutre : chacun incorpore des hypothèses sur la façon dont il sera utilisé. Certaines opérations y sont faciles, d'autres impossibles ; certaines sont rapides, d'autres lentes ; certaines transformations semblent naturelles, d'autres tordues. Ce chapitre compare les trois grandes familles de modèles généralistes — relationnel, document et graphe — puis les langages qui les interrogent, en insistant sur le pourquoi et les compromis : il s'agit de comprendre quand utiliser quoi.

Le modèle relationnel et la montée du NoSQL

Le modèle le plus connu reste celui de SQL, fondé sur le modèle relationnel (relational model) proposé par Edgar Codd en 1970 : les données sont organisées en relations (en SQL : des tables), chaque relation étant une collection non ordonnée de tuples (lignes). Dès le milieu des années 1980, les SGBD relationnels (RDBMS) sont devenus l'outil de choix, et leur domination dure depuis 25 à 30 ans. Leur but originel était de cacher les détails d'implémentation derrière une interface propre, là où les modèles concurrents (hiérarchique, réseau) forçaient le développeur à raisonner sur la représentation interne.

Dans les années 2010, le NoSQL est la dernière tentative pour renverser cette domination. Le terme est malheureux : il ne désigne aucune technologie précise, c'était à l'origine un hashtag Twitter pour un meetup de 2009, réinterprété depuis en Not Only SQL. Plusieurs forces poussent à son adoption :

• un besoin de scalabilité supérieure (jeux de données très volumineux, débit d'écriture élevé) ;
• une préférence pour le logiciel libre plutôt que les produits commerciaux ;
• des opérations de requête spécialisées mal couvertes par le relationnel ;
• la frustration face à la rigidité des schémas relationnels.

Le décalage objet-relationnel

La plupart du code applicatif s'écrit dans des langages orientés objet, d'où une critique récurrente de SQL : si les données vivent dans des tables, il faut une couche de traduction maladroite entre les objets du code et les lignes/colonnes de la base. Ce désaccord s'appelle le décalage d'impédance (impedance mismatch) — un terme emprunté à l'électronique, où le transfert de puissance entre deux circuits est maximal lorsque leurs impédances correspondent. Les frameworks de correspondance objet-relationnel (object-relational mapping, ORM) comme Hibernate réduisent le code répétitif, mais n'effacent pas la différence.

Prenons un CV de type profil LinkedIn. L'objet entier est identifié par un user_id. Des champs comme first_name apparaissent exactement une fois par utilisateur : ce sont des colonnes. Mais chacun a eu plusieurs emplois, formations, moyens de contact : il existe une relation un-à-plusieurs (one-to-many) du profil vers ces éléments. Trois façons de la représenter :

• la représentation normalisée classique (SQL antérieur à SQL:1999) place positions, education et contact_info dans des tables séparées, avec une clé étrangère vers users ;
• les versions récentes de SQL autorisent des types structurés ou du XML/JSON multivalués dans une seule ligne, indexables et interrogeables ;
• ou encore : encoder ces données en un document JSON/XML rangé dans une colonne texte, à charge pour l'application d'en interpréter le contenu (mais alors la base ne peut plus interroger l'intérieur).

Pour une structure essentiellement autonome comme un CV, une représentation JSON est tout à fait adaptée. Les bases orientées document (MongoDB, RethinkDB, CouchDB, Espresso) supportent ce modèle.

{
  "user_id": 251,
  "first_name": "Bill",
  "last_name": "Gates",
  "summary": "Co-chair of the Bill & Melinda Gates… Active blogger.",
  "region_id": "us:91",
  "industry_id": 131,
  "positions": [
    { "job_title": "Co-chair", "organization": "Gates Foundation" },
    { "job_title": "Co-founder, Chairman", "organization": "Microsoft" }
  ],
  "education": [
    { "school_name": "Harvard University", "start": 1973, "end": 1975 }
  ],
  "contact_info": {
    "blog": "http://thegatesnotes.com",
    "twitter": "http://twitter.com/BillGates"
  }
}

Cette représentation a une meilleure localité (locality) que le schéma multi-tables : pour récupérer un profil relationnel, il faut soit plusieurs requêtes, soit une jointure compliquée entre users et ses tables subordonnées. En JSON, toute l'information est au même endroit, une seule requête suffit. Les relations un-à-plusieurs dessinent un arbre que le JSON rend explicite.

Plusieurs-à-un, plusieurs-à-plusieurs et normalisation

Dans le document ci-dessus, region_id et industry_id sont des identifiants, pas les chaînes « Greater Seattle Area » ou « Philanthropie ». Pourquoi ? C'est une question de duplication. Avec un ID, l'information lisible par un humain n'est stockée qu'à un seul endroit ; tout ce qui s'y réfère utilise l'identifiant. Et un ID, dépourvu de sens humain, n'a jamais besoin de changer — tandis que toute information signifiante peut devoir changer un jour ; si elle est dupliquée, chaque copie doit alors être mise à jour, au prix d'une surcharge en écriture et d'un risque d'incohérence. Supprimer cette duplication est l'idée clé de la normalisation (normalization).

Or normaliser exige des relations plusieurs-à-un (many-to-one) : beaucoup de gens vivent dans une même région, travaillent dans un même secteur. Ces relations s'accommodent mal du modèle document. En relationnel, référencer des lignes par ID est naturel car les jointures sont faciles. En document, les jointures sont rarement nécessaires pour les arbres un-à-plusieurs, et leur support est souvent faible : si la base ne sait pas joindre, vous devez émuler la jointure dans le code applicatif par des requêtes multiples — déplaçant le travail de la base vers l'application.

Pire : même une application qui démarre sans jointure tend à voir ses données s'interconnecter à mesure qu'on ajoute des fonctionnalités. Si les organisations et écoles deviennent des entités (avec leur page, leur logo), ou si l'on ajoute des recommandations (qui doivent référencer le profil de leur auteur pour refléter sa photo à jour), on introduit des relations plusieurs-à-plusieurs (many-to-many) qui exigent des références et des jointures.

Relationnel ou document : quel code applicatif ?

Pour le modèle plusieurs-à-un et plusieurs-à-plusieurs, relationnel et document ne sont pas fondamentalement différents : l'élément lié est référencé par un identifiant unique (clé étrangère côté relationnel, référence de document côté document), résolu à la lecture par une jointure ou des requêtes de suivi. Voici le même profil, normalisé en SQL, dont la lecture complète réclame une jointure multiple.

SELECT u.first_name, u.last_name,
       p.job_title, p.organization,
       r.region_name
FROM users u
LEFT JOIN positions p ON p.user_id = u.user_id
LEFT JOIN regions   r ON r.id      = u.region_id
WHERE u.user_id = 251;

Quel modèle mène au code le plus simple ? Cela dépend des relations entre les données :

Critère	Modèle document	Modèle relationnel
Structure naturelle	Arbre un-à-plusieurs chargé en bloc	Données régulières, tabulaires
Jointures	Support faible, à émuler dans l'app	Natives et optimisées
Plusieurs-à-plusieurs	Maladroit (dénormalisation à maintenir)	Bien supporté
Localité	Forte (un document = un bloc)	Lectures multi-index
Souplesse de schéma	Schema-on-read (implicite)	Schema-on-write (explicite)

Si vos données ont une structure de document (arbre un-à-plusieurs chargé d'un coup), le document évite le découpage (shredding) — éclater une structure en plusieurs tables — qui complique le schéma et le code. À l'inverse, dès que les relations plusieurs-à-plusieurs sont fréquentes, émuler les jointures dans l'application alourdit le code et dégrade les performances. Il n'existe aucune réponse universelle ; pour des données très interconnectées, le document est carrément pénible, le relationnel acceptable, et le graphe le plus naturel.

Schéma à la lecture ou à l'écriture

La plupart des bases document, comme le support JSON des bases relationnelles, n'imposent aucun schéma. On les dit parfois « sans schéma » (schemaless), mais c'est trompeur : le code qui lit les données suppose toujours une certaine structure. Il y a donc un schéma implicite, simplement non vérifié par la base. Le terme exact est schéma à la lecture (schema-on-read) — la structure est interprétée au moment de la lecture — par opposition au schéma à l'écriture (schema-on-write), l'approche relationnelle où le schéma est explicite et garanti par la base.

C'est l'analogue, côté bases de données, du typage dynamique (à l'exécution) face au typage statique (à la compilation). La différence saute aux yeux lors d'un changement de format. Supposons que vous vouliez scinder un champ name en first_name et last_name. Côté document, vous écrivez simplement les nouveaux documents avec les nouveaux champs, et le code gère les anciens à la lecture :

if (user && user.name && !user.first_name) {
  // Documents antérieurs au 8 déc. 2013 : pas de first_name
  user.first_name = user.name.split(" ")[0];
}

Côté schéma statique, vous effectuez une migration. Le ALTER TABLE s'exécute en quelques millisecondes sur la plupart des SGBD (sauf MySQL, qui recopie toute la table) ; mais le UPDATE qui réécrit chaque ligne reste lent sur n'importe quelle base.

ALTER TABLE users ADD COLUMN first_name text;
UPDATE users SET first_name = split_part(name, ' ', 1); -- PostgreSQL

Le schema-on-read brille quand les données sont hétérogènes : multitude de types d'objets qu'on ne peut pas mettre chacun dans sa table, ou structure dictée par un système externe que vous ne contrôlez pas. Là, un schéma gênerait plus qu'il n'aiderait. Mais quand tous les enregistrements partagent la même structure, le schéma reste un mécanisme utile pour documenter et faire respecter cette structure.

Les deux mondes convergent : depuis le milieu des années 2000, la plupart des bases relationnelles supportent XML, et PostgreSQL comme DB2 supportent JSON. Côté document, RethinkDB propose des jointures. Une base hybride, capable de gérer du document tout en effectuant des requêtes relationnelles, est une bonne voie pour l'avenir.

Langages de requête : déclaratif contre impératif

L'introduction du relationnel a apporté une nouveauté : SQL est un langage déclaratif (declarative), là où IMS et CODASYL s'interrogeaient en code impératif (imperative). Un langage impératif dit à la machine comment procéder, opération par opération, dans un ordre donné. Pour filtrer les requins d'une liste :

function getSharks() {
  const sharks = [];
  for (let i = 0; i < animals.length; i++) {
    if (animals[i].family === "Sharks") {
      sharks.push(animals[i]);
    }
  }
  return sharks;
}

Un langage déclaratif, lui, dit seulement quoi : le motif des données voulues (conditions, tri, regroupement, agrégation), sans dire comment l'obtenir.

SELECT * FROM animals WHERE family = 'Sharks';

Cette différence n'est pas qu'esthétique. Le déclaratif est plus concis, mais surtout il cache les détails d'implémentation du moteur, ce qui permet d'introduire des optimisations sans toucher aux requêtes. La requête impérative fige l'ordre des animals : la base ne peut pas réorganiser les enregistrements en arrière-plan sans risquer de casser le code. La requête SQL ne garantit aucun ordre, donc la base a toute latitude pour optimiser. Enfin, le déclaratif se prête au parallélisme : comme le code impératif impose un ordre d'exécution, seul un langage qui décrit le résultat (et non l'algorithme) peut être parallélisé librement par la base.

MapReduce : un intermédiaire

MapReduce est un modèle de programmation pour traiter de gros volumes en masse sur de nombreuses machines, popularisé par Google. Certaines bases NoSQL (MongoDB, CouchDB) en proposent une forme limitée pour des requêtes en lecture. Il n'est ni vraiment déclaratif ni pleinement impératif : la logique s'exprime par des fragments de code que le framework appelle de façon répétée, via les fonctions map et reduce du monde fonctionnel. Pour compter les requins observés par mois :

db.observations.mapReduce(
  function map() {
    const year  = this.observationTimestamp.getFullYear();
    const month = this.observationTimestamp.getMonth() + 1;
    emit(year + "-" + month, this.numAnimals);
  },
  function reduce(key, values) {
    return Array.sum(values);
  },
  { query: { family: "Sharks" }, out: "monthlySharkReport" }
);

map est appelée une fois par document filtré et émet une paire clé-valeur ; les valeurs partageant la même clé sont passées à reduce. Ces fonctions doivent être pures (pas d'accès à la base, pas d'effet de bord), ce qui permet à la base de les exécuter n'importe où, dans n'importe quel ordre, et de les rejouer en cas d'échec. La contrepartie : il faut écrire deux fonctions coordonnées, souvent plus difficile qu'une seule requête, et le déclaratif offre plus de marge à l'optimiseur. C'est pourquoi MongoDB a fini par ajouter un langage déclaratif, le pipeline d'agrégation — moralité : un système NoSQL finit parfois par réinventer SQL sans le dire.

db.observations.aggregate([
  { $match: { family: "Sharks" } },
  { $group: {
      _id: { year:  { $year:  "$observationTimestamp" },
             month: { $month: "$observationTimestamp" } },
      totalAnimals: { $sum: "$numAnimals" }
  } }
]);

Les modèles en graphe

Si les relations plusieurs-à-plusieurs deviennent très courantes et que les connexions se complexifient, il devient naturel de modéliser les données en graphe (graph). Un graphe comporte deux types d'objets : des sommets (vertices), aussi appelés nœuds ou entités, et des arêtes (edges), aussi appelées relations ou arcs. Réseaux sociaux, graphe du web, réseaux routiers : autant d'exemples sur lesquels opèrent des algorithmes connus (plus court chemin, PageRank). Surtout, un graphe peut stocker des types d'objets complètement différents dans un même magasin — Facebook maintient un graphe unique mêlant personnes, lieux, événements, check-ins, commentaires.

Property graph et Cypher

Dans le graphe de propriétés (property graph) (Neo4j, Titan), chaque sommet a un identifiant, ses arêtes entrantes et sortantes, et un ensemble de propriétés (paires clé-valeur). Chaque arête a un identifiant, son sommet de départ (queue) et d'arrivée (tête), un label décrivant le type de relation, et ses propres propriétés. On peut le voir comme deux tables relationnelles, l'une pour les sommets, l'autre pour les arêtes, avec des index sur les deux extrémités.

Trois traits font la force du modèle : n'importe quel sommet peut être relié à n'importe quel autre (aucun schéma ne restreint les associations) ; on peut parcourir le graphe efficacement dans les deux sens ; et des labels distincts permettent de stocker plusieurs types de relations dans un même graphe propre. Cela donne une grande souplesse, idéale pour des structures hétérogènes (la France a des régions et départements, les États-Unis des comtés et États) et pour l'évolutivité (evolvability) : on étend le graphe sans douleur.

Cypher est le langage déclaratif de Neo4j. La notation fléchée (Idaho) -[:WITHIN]-> (USA) crée une arête WITHIN. Pour trouver les personnes ayant émigré des États-Unis vers l'Europe :

MATCH
  (person) -[:BORN_IN]->  () -[:WITHIN*0..]-> (us:Location {name:'United States'}),
  (person) -[:LIVES_IN]-> () -[:WITHIN*0..]-> (eu:Location {name:'Europe'})
RETURN person.name

Le :WITHIN*0.. signifie « suivre une arête WITHIN, zéro fois ou plus », comme l'opérateur * d'une expression régulière. C'est crucial : une LIVES_IN peut pointer vers une ville, une région, un État… le nombre de sauts n'est pas connu d'avance. Comme tout langage déclaratif, Cypher laisse l'optimiseur choisir la stratégie (partir des personnes, ou partir des deux lieux et remonter les arêtes entrantes).

Les bases graphe ne sont pas un retour de CODASYL : tout sommet peut être relié à tout autre (pas de schéma figé), on accède directement à un sommet par son ID ou par un index, il n'y a pas d'ordre imposé, et les requêtes sont déclaratives plutôt qu'impératives et fragiles.

Triple-stores, SPARQL et Datalog

Le modèle des triplets (triple-store) est quasi équivalent au property graph, avec un autre vocabulaire. Toute information y tient en énoncés à trois parties : (sujet, prédicat, objet). Dans (Jim, likes, bananas), Jim est le sujet, likes le prédicat, bananas l'objet. Le sujet est un sommet. L'objet est soit une valeur primitive — et alors (lucy, age, 33) équivaut à une propriété {age: 33} sur le sommet lucy —, soit un autre sommet — et alors le prédicat est une arête, comme dans (lucy, marriedTo, alain). Le format Turtle l'écrit lisiblement :

@prefix : <urn:example:>.
_:lucy  a :Person;   :name "Lucy";          :bornIn _:idaho.
_:idaho a :Location; :name "Idaho";         :type "state";   :within _:usa.
_:usa   a :Location; :name "United States"; :type "country".

Ce modèle est souvent associé au web sémantique et au format RDF (Resource Description Framework), idée raisonnable (publier des données lisibles par les machines) mais sur-vendue au début des années 2000 et jamais vraiment concrétisée. Peu importe : les triplets restent un bon modèle interne, indépendamment du web sémantique. SPARQL est leur langage de requête ; il précède Cypher, qui lui a emprunté son filtrage par motif, et il est encore plus concis :

PREFIX : <urn:example:>
SELECT ?personName WHERE {
  ?person :name ?personName.
  ?person :bornIn  / :within* / :name "United States".
  ?person :livesIn / :within* / :name "Europe".
}

Enfin, Datalog est bien plus ancien (étudié dès les années 1980) et fournit le fondement sur lequel les langages suivants se construisent ; on le retrouve dans Datomic et Cascalog. Son modèle généralise les triplets en écrivant prédicat(sujet, objet), par exemple within(idaho, usa). On y procède par petits pas, en définissant des règles qui dérivent de nouveaux prédicats, possiblement récursifs :

within_recursive(Loc, Name) :- name(Loc, Name).
within_recursive(Loc, Name) :- within(Loc, Via),
                               within_recursive(Via, Name).
migrated(Name, BornIn, LivingIn) :-
    name(Person, Name),
    born_in(Person, BornLoc), within_recursive(BornLoc, BornIn),
    lives_in(Person, LivingLoc), within_recursive(LivingLoc, LivingIn).

?- migrated(Who, 'United States', 'Europe'). /* Who = 'Lucy'. */

Une règle s'applique si tous les prédicats à droite du :- trouvent une correspondance ; son membre de gauche est alors ajouté à la base. Cette approche demande une autre manière de penser, mais elle est puissante car les règles se combinent et se réutilisent entre requêtes : moins commode pour une requête ponctuelle, mais bien meilleure quand les données sont complexes.

À retenir

• Le modèle de données structure la pensée autant que le code ; chacun incorpore des hypothèses, et le bon choix dépend des relations entre vos données — c'est une affaire de compromis.
• Document : excellent pour des structures autonomes en arbre (un-à-plusieurs), avec une forte localité et un schéma à la lecture souple ; maladroit dès que les relations plusieurs-à-plusieurs se multiplient, car les jointures y sont faibles.
• Relationnel : met les données à plat, gère nativement jointures et relations plusieurs-à-un/plusieurs-à-plusieurs, impose un schéma à l'écriture ; les deux modèles convergent (JSON dans le relationnel, jointures en document).
• Déclaratif (SQL, Cypher, SPARQL) contre impératif : dire quoi plutôt que comment cache l'implémentation, libère l'optimiseur et autorise le parallélisme ; MapReduce occupe un entre-deux à base de fonctions pures map/reduce.
• Graphe (property graph + Cypher, triple-store + SPARQL, Datalog) : le modèle naturel quand tout peut être relié à tout — relations nombreuses, plusieurs-à-plusieurs, hétérogènes — et où le nombre de sauts d'un parcours n'est pas connu d'avance.
• Aucun modèle universel : on émule l'un avec l'autre au prix de la maladresse, d'où des systèmes différents pour des usages différents.