Sciences des données :

De la Logique du premier ordre à la Toile

Serge Abiteboul

Collège de France, INRIA Saclay, ENS Cachan

8/2/12

Monsieur l’Administrateur, 

Mes chers collègues,

Chers amis.

En cette journée internationale de la femme, j’aimerais dédier ma leçon inaugurale à l’étudiante en informatique, l’étudiante en mathématiques ou en sciences qui est si rare sur nos campus. Elle est assise au premier rang. Elle pianote peut-être un SMS en s’aidant de ses deux pouces. Elle est peut-être la « Petite Poucette » de Michel Serres, qui m’offre une transition vers une phrase parfaite pour situer l’objet de la leçon :

Je ne connais pas d’être vivant, de cellule, tissu, organe, individu et peut-être même espèce, dont on ne puisse pas dire qu’il stocke de l’information, qu’il traite de l’information, qu’il émet et qu’il reçoit de l’information. Michel Serres

L’information stockée, traitée, échangée, est au cœur de l’activité des êtres vivants, des objets du monde, des associations humaines. Les systèmes informatiques, en nous aidant à gérer de l’information, représentée sous forme numérique, ont transformé nos vies en profondeur. Gérard Berry^[1] a déjà parlé dans sa leçon inaugurale de la numérisation de l’information. Le sujet que j’ai le grand honneur d’aborder dans le cadre de la chaire « Informatique et sciences numériques » du Collège de France est la gestion d’informations numériques par des systèmes informatiques. J’espère que, dans la lignée de mes brillants prédécesseurs à cette chaire[2], je saurai transmettre la richesse et la beauté de la science informatique, et participer ainsi à l’enseignement du « savoir en train de se faire ».

Pour obtenir de l’information, nous pouvons interroger un système de gestion de bases de données. Pour ce faire, nous nous exprimons dans un langage informatique simple, peut-être graphique, peut-être même dans notre langue naturelle[3]. Le système traduit cette demande dans un langage formel. Par cela, nous entendons une syntaxe qui permet au système de préciser la demande de l’utilisateur, et une sémantique formelle qui donne un sens exact à cette syntaxe. La logique mathématique offre un tel langage formel. Nous évoquerons dans cette leçon les liens profonds entre ce que nous appellerons ici les sciences des données et la logique mathématique et plus précisément la « Logique du premier ordre », le terme technique du titre de cette leçon.

Aujourd’hui, c’est sur la Toile que l’utilisateur cherche le plus souvent de l’information. La Toile, le dernier terme du titre. Si l’anglais est prédominant en informatique, le français est parfois plus précis, plus élégant. Je préfère résolument « informatique » (pour science et technologie de l’information) à « computer science » (trop limitatif) et « courriel » à « email ». Je préfère aussi le mot « Toile » à l’anglicisme plus commun, « Web », parce que dans Toile, la référence à la toile d’araignée étymologique est si joliment complétée par le clin d’œil à la toile du peintre ou la toile de cinéma. Le mot Toile nous permet aussi de dépasser la vision trop restrictive d’un support particulier, le World Wide Web, pour envisager plus généralement un monde de contenus interconnectés à l’échelle de la planète. Il m’arrivera pourtant d’utiliser le mot Web dans des expressions comme « Web sémantique ».

Nous considèrerons les systèmes d’information de la Toile qui servent de point d’entrée vers des informations de nature globale. L’exemple le plus répandu d’un tel système est un moteur de recherche, comme celui de Google, qui offre un index sur des milliards de documents de la Toile, et en quelque sorte permet de voir la Toile comme une base de données gigantesque. Un système de réseau social comme Facebook sert lui de point d’entrée vers les données personnelles de ses centaines de millions d’utilisateurs.

Les systèmes d’information de la Toile comme les systèmes de gestion de données centralisées sont des médiateurs entre des individus intelligents peu soucieux de s’embarrasser de détails de programmation et des objets physiques comme des disques ou des clés USB. Nous nous intéressons donc à des systèmes intelligents qui gèrent de l’information, la comprennent et l’utilisent au service d’utilisateurs humains. Cette dernière phrase tient volontairement d’une vision anthropomorphique des systèmes informatiques. Nous interagissons avec des machines chaque jour un peu plus autonomes, des machines chaque jour de moins en moins distinguables des êtres humains. Si l’intelligence d’un système de gestion de bases de données est une étape modeste vers l’intelligence artificielle comme définie par Alan Turing, l’intelligence de la Toile est un questionnement récent, tant philosophique que scientifique. Nous parlerons dans cette leçon de l’apparition d’une connaissance collective nourrie de la mise en commun de grands volumes d’information, et nous imaginerons ce que pourra être la Toile de demain quand des millions, voire des milliards de machines interconnectées, raisonneront collectivement.

Cette leçon est organisée de la manière suivante. En premier lieu, nous visiterons quelques notions fondamentales sur les données, l’information et les connaissances. Dans un deuxième temps, nous parlerons de deux des plus belles réussites de l’informatique du 20^e siècle :

1. l’une concerne les données avec les systèmes de gestion de base de données relationnelles.

2. l’autre l’information avec les moteurs de recherche de la Toile.

Puis, nous considèrerons deux grands défis du 21^e siècle :

1. comment faire émerger des connaissances collectives de la Toile, et

2. comment passer à une Toile des connaissances.

Look Dave, I can see you're really upset about this. I honestly think you ought to sit down calmly, take a stress pill, and think things over[4]. HAL in 2001 : A Space Odyssey

1. Données, information et connaissances

Des mesures de température relevées chaque jour dans une station météo, ce sont des données. Une courbe donnant l'évolution dans le temps de la température moyenne dans un lieu, c’est une information. Le fait que la température sur Terre augmente du fait de l’activité humaine, c’est une connaissance. Ces trois notions sont très proches l’une de l’autre. Grossièrement, voici le sens que nous leurs donnerons[5] :

· Une donnée est une description élémentaire, typiquement numérique ici, d'une réalité. C’est par exemple une observation ou une mesure.

· A partir de données collectées, de l’information est obtenue en organisant ces données, en les structurant pour en dégager du sens.

· En comprenant le sens de l’information, nous aboutissons à des connaissances, c’est-à-dire à des « faits » considérés comme vrais dans l’univers d’un locuteur et à des « lois » (des règles logiques) de cet univers.

A la source de la représentation de données est le bit, une variable qui peut prendre la valeur 0 ou 1. Une donnée sera représentée par une séquence de bits. Par exemple, nous pouvons représenter la position d'un ascenseur dans un immeuble de six étages avec 3 bits : 000 pour le rez-de-chaussée, 001 pour le premier, etc., 110 pour le sixième (le nombre 6 en base 2). Nous représentons un caractère avec un octet, c’est-à-dire une séquence de 8 bits. (Il faut jusqu’à 4 octets par caractère pour certains alphabets et certains codages comme UTF-16.) Un texte peut être vu comme une suite d’octets. L’octet est la mesure élémentaire ; 10³ octets forment un kilooctet ; 10⁶ un méga ; 10⁹ un gigaoctet ; 10¹² un téraoctet ; etc.

Une suite de bits prise au hasard a peu de chance d’avoir un sens. Intéressons-nous plutôt aux données auxquelles nous pouvons donner un sens. Considérons par exemple une séquence de bits qui représenterait le tableau suivant :

Manon	Imperial College	London
Pierre	ENS	Cachan
Jérémie	Mines de Paris	Paris
Marie	ENS	Cachan
Myriam	Paris 11	Orsay

Un extraterrestre ne comprendrait sans doute rien à cette séquence de bits. Mais un programme, un éditeur de texte, a pu l’analyser et présenter ce tableau sous une forme qui nous est familière.

Des données à l’information. Les entrées de ce tableau sont des chaînes de caractères. Pour l’instant, il s’agit de données. Maintenant, nous pouvons spécifier que la première colonne contient les prénoms de doctorants d’une école d’été à Cargèse en Corse, la deuxième, leur université, et la dernière, la ville qui héberge leur université. En recevant un sens, ces données sont devenues des informations. Nous noterons que l’absence de données aussi est informative. Par exemple, nous n’avons pas de ligne, « Philippe, ENS, Cachan ». C’est aussi une information !

De l’information aux connaissances. Ces informations muent en connaissances quand nous les introduisons dans un univers logique. Chaque ligne devient une affirmation, par exemple « Manon, étudiante à l’Imperial College à Londres, a suivi cette école d’été ». Et si, par exemple, nous savons aussi que « cette table contient la liste complète de tous les doctorants de cette école d’été » et que « tous les doctorants de Cachan en informatique ont suivi cette école », nous pouvons en déduire que, soit Philippe n’est pas doctorant à Cachan, soit il n’est pas inscrit en informatique.

Nous sommes passés des données, aux informations, aux connaissances. Evidemment les frontières entre ces concepts sont floues. Ce monde que nous cherchons à modéliser avec des connaissances est complexe et nous échappe en partie. Par exemple, si certains pensent que Manon est étudiante à l’Imperial College, d’autres peuvent croire que cette affirmation est fausse.

Le stockage

Plusieurs types de supports permettent de stocker des données numériques notamment : la mémoire flash, le disque optique (qui inclut les CD et DVD), le disque dur (ou disque magnétique), la bande magnétique. Ces supports procurent de gros volumes de stockage « persistant[6] » contrairement aux mémoires vives, ou mémoires RAM pour « random access memory », faites de composants électroniques.

Nous allons fournir quelques chiffres pour fixer les idées. L’ordinateur sur lequel j’écris ce texte a une mémoire vive de quatre gigas et à la place d’un disque, pour stocker ses données persistantes, il utilise une centaine de gigas de mémoire flash, une nouvelle technologie plus rapide que le disque dur et aussi plus chère. Cela nous donne l’occasion de mentionner que la technologie ne cesse de se complexifier. Les chiffres bougent très vite pour ce qui est des matériels informatiques ; les prix baissent, les vitesses d’accès ou de transfert croissent ; les volumes augmentent[7]. Dans quelques années, un lecteur de ce texte sourira des quatre gigas de mémoire.

Il ne faut pas non plus oublier que les données que nous utilisons se trouvent de moins en moins stockées localement sur notre ordinateur, mais, de plus en plus, sur des machines connectées quelque part sur le réseau. Par exemple, le document qui sert de brouillon pour écrire ce texte est sur Google Docs, stocké sur le disque d’une machine inconnue dans une localisation elle-aussi inconnue. De ces données, nous dirons qu’elles sont « en nuages » (“on the cloud”)[8]. Fonctionnellement, il nous faudra donc distinguer entre l’accès à des données sur un réseau local très rapide qui prendra quelques millisecondes, et l’accès via Internet à des données peut-être à l’autre bout du monde qui pourra prendre une seconde ou plus.

Ces aspects techniques permettent de comprendre ce qu’il est possible de réaliser, comment et à quel prix. Nous les avons volontairement quelque peu simplifiés pour faciliter leur compréhension. Et pour ceux qui aiment se réfugier derrière le « Je ne comprends rien à l’informatique », quelques mots. La vision de l’informatique véhiculée par les médias souffre d’une trop grande fascination pour le matériel et la programmation. A mon avis, il importe peu de comprendre les détails du fonctionnement très complexe d’un processeur ou d’une carte graphique. Il est par contre essentiel de maitriser les bases de l’algorithmique et de sa mécanique du raisonnement. Il n’est pas non plus nécessaire de savoir programmer (même si une expérience de programmation avec un langage comme Caml peut faciliter la compréhension de l’algorithmique). Pour des questions de performance, il peut être utile de comprendre où l’information que nous utilisons est stockée, en mémoire, sur disque, ou sur le réseau. Surtout, il est indispensable de comprendre le sens de cette information, comment elle est représentée, comment elle est organisée.

Et quelques chiffres à retenir :

Support de stockage	Temps d’accès	Taille
Mémoire vive	microsecondes	gigaoctets (10^9)
Disque dur	millisecondes	quelques centaines de gigaoctets au téra
Réseau local	millisecondes ou plus	téraoctets (10^12)
La Toile	décisecondes voire secondes	virtuellement ¥

Mesurer les zettaoctets à la cuillère à café

En alignant les bits, nous pouvons représenter des informations. Nous pouvons stocker de plus en plus d’informations pour les retrouver à la demande, telle une sauvegarde quasi illimitée de notre mémoire personnelle.

Nous pouvons aller au-delà des dimensions déjà mentionnées en alignant les bits :

kilo	méga	giga	téra	péta	exa	zetta	yotta
10^3	10^6	10^9	10^12	10^15	10^18	10^21	10^24

Discutons brièvement ces unités de mesures. Par exemple, cette leçon devrait peser quelques 100 000 octets, c’est-à-dire 100 kilooctets. Le kilooctet est une mesure « cool » car il est presque convenable de confondre 10³ = 1000 et 2¹⁰ = 1024, ce qui permet de passer facilement du système décimal, le plus commun, au système binaire, cher aux informaticiens. Une dizaine de nocturnes de Chopin sur mon téléphone prennent 75 mégaoctets. La vidéo de la remise de diplôme de ma fille et ses quelques gigaoctets nous conduisent aux frontières du gigantisme. Empruntant des chiffres de Michael Brodie[9], tous les livres jamais écrits ne demanderaient que 200 téraoctets en texte brut et la quantité de données produites par le « collisionneur de particules » du CERN en une minute est de l’ordre d’une centaine de pétaoctets. Pour représenter toutes les phrases jamais prononcées, il faudrait quelques exaoctets. Enfin, le zettaoctet, c’est l’ordre de grandeur du trafic par an sur Internet de nos jours, et c’est aussi celui du stockage disponible (en comptant tous les disques, bandes magnétiques, CD, DVD du monde entier) :

1 000 000 000 000 000 000 000 octets !

Le vertige des puissances de 10 ! Nous créons chaque année plus d’information que nous ne pouvons en stocker. Dans cette débauche d’information, deux problèmes surgissent :

1. Où trouver la bonne information dans cette masse ?

2. Comment choisir ce que l’on veut conserver ?

Bien sûr, il faudrait détailler, tenir compte de la nature de ce qui est stocké. La part des images grossit très vite, notamment à cause de la meilleure résolution des caméras de vidéosurveillance. Mais nous assistons aussi à une forte augmentation des contenus riches en sémantique, directement utilisables comme les bases de données et les métadonnées. La forme de l’information dans la plupart des exemples que nous avons pris est très simple. De l’information beaucoup plus complexe peut aussi être représentée numériquement comme celle contenue dans l'ADN d'une cellule vivante. D'une certaine façon, déterminer l'information mise en jeu dans un objet quelconque, depuis une bactérie jusqu'à un phénomène comme le cours des actions, ou le mouvement des
planètes, est une étape essentielle de notre compréhension de cet objet. Mais cela tient d’autres sciences que l’informatique, comme la biologie, les mathématiques financières, ou l’astronomie. Une fois cette information obtenue, des machines peuvent la stocker, l’échanger, l’analyser, etc. Nous atteignons les sciences des données.

Passée cette brève discussion sur la nature et le volume de l’information, nous nous tournons vers les systèmes de bases de données qui ont véritablement fondé le domaine, les systèmes relationnels.

2. Les systèmes relationnels et la Logique du premier ordre

Logic is the beginning of wisdom, not the end[10]. Mr. Spock, Star Trek

Nous parlerons dans cette partie de systèmes informatiques qui nous aident à gérer des données. Nous avons donc, d’un côté, un serveur de données quelque part sur la Toile, avec des disques et leurs pistes qui gardent précieusement des séquences de bits, des structures d’accès compliquées comme des index ou des arbres-B, des hiérarchies de mémoires avec leurs caches et, de l’autre, un utilisateur. Supposons que le serveur soit celui d’IMDb qui gère une base de données sur le cinéma. Supposons que l’utilisateur, disons Alice, veuille savoir quels films ont été réalisés par Alfred Hitchcock. Pour ce faire, elle spécifie des mots-clés ou remplit les champs d’un formulaire proposé par IMDb. Sa question voyage depuis son navigateur jusqu’au serveur de données. Là, cette question est transformée en un programme peut-être complexe qui s’exécute pour obtenir la réponse. Ce qui est important : ce programme, Alice n’a pas envie de l’écrire ; elle n’a pas à l’écrire.

Le système élémentaire qui permet de gérer des données est un système de fichiers. Un fichier est une séquence de bits qui peut représenter une chanson, une photo, une vidéo, un courriel, une lettre, un roman, etc. Votre ordinateur personnel et votre téléphone stockent leurs données dans des systèmes de fichiers. Et parfois quand vous ne savez plus où vous avez mis quelque chose, vous faites des « recherches » dans ces système de fichiers. C’est rudimentaire. Nous verrons pourtant qu’un moteur de recherche de la Toile ne fait pas autre chose, seulement il le fait sur un système de fichiers à l’échelle de la planète. Dans cette partie, nous parlerons de systèmes qui gèrent aussi des données mais qui sont bien plus sophistiqués que les systèmes de fichiers, les systèmes de gestion de bases de données. Ce sont des logiciels complexes, résultats de dizaines d’années de recherche et de développement. Ils permettent à des individus ou des programmes d’exprimer des requêtes pour interroger des bases de données ou pour les modifier. Nous nous focaliserons ici sur les plus répandus d’entre ces systèmes, les systèmes relationnels, parmi lesquels nous trouvons des logiciels commerciaux très répandus comme celui d’Oracle et des logiciels gratuits très utilisés comme MySQL.

Le calcul et l’algèbre relationnels

Un système de gestion de bases de données sert de médiateur entre des individus et des machines. Pour mieux s’adapter aux individus, il doit organiser et présenter les données de façon intuitive. Il doit aussi proposer un langage, pour exprimer des requêtes, facilement utilisable par des êtres humains. Ces exigences forment le point de départ du modèle relationnel[11]^,[12] proposé par Ted Codd, un chercheur d’IBM, dans les années 1970. Des mathématiciens avaient développé à la fin du 19^e siècle (bien avant l’invention de l’informatique et des bases de données) la Logique du premier ordre, pour formaliser le langage des mathématiques. Codd a eu l’idée d’adapter cette logique pour définir un modèle de gestion de données, le modèle relationnel.

Film			Séance
Titre	Réalisateur	Acteur	Titre	Salle	Heure
Casablanca	M. Curtiz	Humphrey Bogart	Casablanca	Lucernaire	19:00
Casablanca	M. Curtiz	Peter Lore	Casablanca	Studio	20:00
Les 400 coups	F. Truffaut	Jean-Pierre Léaud	Star Wars	Sel	20:30
Star Wars	G. Lucas	Harrison Ford	Star Wars	Sel	22:15

Figure 1 : Une base de données relationnelles

Dans le modèle relationnel, les données sont organisées en tableaux à deux dimensions que nous appellerons des relations. A la différence des mathématiciens, nous supposons les relations de taille finie. Comme illustration, nous utiliserons une base de données consistant en une relation Film et une relation Séance (Figure 1). Une ligne de ces relations est appelée un n-uplet où n est le nombre de colonnes. Par exemple, áStar Wars, Sel, 22:15ñ est un 3-uplet, un triplet, dans la relation Séance. Les colonnes ont des noms, appelés attributs, comme Titre.

Les données sont interrogées en utilisant comme langage le calcul relationnel. Le calcul relationnel (très fortement inspiré de la Logique du premier ordre) s’appuie sur des noms qui représentent des relations comme Film ou Séance, des entrées de ces relations comme « Star Wars », des variables comme t, h, et des symboles logiques, Ù (et), Ú (ou), Ø (non), Þ (implique), $ (existe), " (pour tout). Avec tout ça, des formules logiques peuvent être construites comme :

q_HB = $ t,d ( Film(t, r, « Humphrey Bogart ») Ù Séance(t, s, h) )

Si cela vous parait cryptique, en français, cela se lit : il existe un titre t et un réalisateur r tels que le n-uplet á t, r, « Humphrey Bogart » ñ se trouve dans la relation Film, et le n-uplet á t, s, h ñ dans Séance. Observez que s et h ne sont pas quantifiées dans la formule précédente ; nous dirons que ces deux variables sont libres. La formule q_HB peut être vue comme une requête du calcul relationnel. Elle se lit alors : donnez-moi les salles s et les horaires h, s’il existe un réalisateur r et un titre t tels que... En d’autres termes, « Où et à quelle heure puis-je voir un film avec Humphrey Bogart ? ». Ce langage, le calcul relationnel, permet d’exprimer des questions dans une syntaxe qui évite les ambiguïtés de nos langues naturelles. Si elles pouvaient aimer, les machines aimeraient la simplicité, la précision du calcul relationnel. En pratique, elles utilisent le langage SQL (pour Structured Query Language) qui exprime différemment les mêmes questions. Par exemple la question précédente s’exprime en SQL comme :

select salle, heure

from Film, Séance

where Film.titre = Séance.titre and acteur= «Humphrey Bogart»

C’est presque compréhensible. Non ? Et qu’Alice s’exprime en français ou qu’elle utilise une interface graphique, le système transforme sa question en requête[13] SQL.

La question du calcul relationnel précédente (ou en SQL) précise bien ce qu’Alice demande. Cette question a un sens précis, une sémantique. Elle définit une réponse, un ensemble de n-uplets. Nous ne préciserons pas comment dans cette leçon. Ce que la question ne dit pas c’est comment calculer la réponse. Pour le « comment », on utilise l’algèbre relationnelle introduite par Codd. Une étape importante consiste à transformer une question du calcul en une expression algébrique qui permet de calculer la réponse à cette question.

L’algèbre relationnelle consiste en un petit nombre d’opérations de base qui, appliquées à des relations, produisent de nouvelles relations. Ces opérations peuvent être composées pour construire des expressions algébriques de plus en plus complexes. Pour répondre à la question qui nous sert d’exemple, il nous faudra trois opérations, la jointure, la sélection et la projection, que nous composerons dans l’expression suivante de l’algèbre relationnelle :

E_HB = P_salle,heure (P_titre (s_{acteur = « Humphrey Bogart »}(Film)) Salle)

Figure 2 : l’évaluation d’une requête algébrique

Nous pourrons suivre l’évaluation de cette expression algébrique en Figure 2. L’opération de sélection, dénotée s, filtre une relation, ne gardant que les n-uplets satisfaisant une condition, ici acteur = « Humphrey Bogart ». L’opération de projection, dénotée P, permet aussi de filtrer de l’information d’une relation mais cette fois en éliminant des colonnes. L’opération peut-être la plus exotique de l’algèbre, la « jointure », dénotée , combine des n-uplets de deux relations. D’autres opérations non illustrées ici permettent de faire l’union et la différence entre deux relations ou de renommer des attributs. La puissance de l’algèbre relationnelle tient de la possibilité de composer ces opérations. C’est ce que nous avons fait dans l’expression algébrique E_HB qui permet d’évaluer la réponse à la question q_HB.

Notre présentation est rapide mais il est important que le lecteur comprenne l’intérêt de l’algèbre. Il est relativement simple d’écrire un programme qui évalue la réponse à une question du calcul relationnel. Il est plus délicat d’obtenir un programme qui calcule cette réponse efficacement. L’algèbre relationnelle découpe le travail. Un programme particulier très efficace peut être utilisé pour chacune des opérations de l’algèbre ; le résultat est obtenu en composant ces programmes. L’efficacité provient notamment de ce que les opérations considèrent des ensembles de n-uplets plutôt que les n-uplets un à un.

Codd a démontré le théorème suivant.

Théorème [Codd] : une question est exprimable en calcul relationnel si et seulement si elle peut être évaluée avec une expression de l’algèbre relationnelle, et il est facile de transformer une requête du calcul en une expression algébrique qui évalue cette requête.

Qu’avons nous appris de Codd ? Pas grand-chose du point de vue des mathématiques. Le calcul relationnel est emprunté aux logiciens. Une algébrisation (légèrement différente) avait même déjà été proposée par Tarski. Mais d’un point de vue informatique, Codd a posé les bases de la médiation autour des données entre individus et machines. Grâce à son résultat, nous savons que nous pouvons exprimer une question en calcul relationnel, qu’un système peut traduire cette question en expression algébrique et calculer efficacement sa réponse. Pourtant, quand Codd proposa cette approche, la réaction des ingénieurs qui géraient alors de gros volumes de données et de grandes applications, fut unanime : « trop lent ! Ça ne passera pas à l’échelle ». Ils se trompaient. Pour traduire l’idée de Codd en une industrie de milliards de dollars, il manquait l’optimisation de requête. Après des années d’effort, les chercheurs sont parvenus à faire fonctionner les systèmes relationnels avec des temps de réponse acceptables. Avec ces systèmes, le développement d’applications gérant des données devenait beaucoup plus simple ; cela se traduisait par un accroissement considérable de la productivité des programmeurs d’applications gérant des gros volumes de données.

L’optimisation de requête

Il existe une infinité d’expressions algébriques qui évaluent une même requête. Si elles sont syntaxiquement différentes, elles définissent la même question. D’un point de vue sémantique, elles sont équivalentes. Optimiser une requête consiste à la transformer en une autre qui donne les mêmes réponses, mais qui soit la moins coûteuse possible (typiquement en temps). D’un point de vue pratique, il nous faut choisir un « plan d’exécution », c’est-à-dire une expression algébrique avec des précisions sur l’algorithme à utiliser pour évaluer chacune des opérations. Un plan d’exécution, c’est quasiment un programme pour calculer la réponse. Un premier problème est que l’ « espace de recherche », c’est-à-dire l’espace dans lequel nous voulons trouver le plan d’exécution, est potentiellement gigantesque. Pour éviter de le parcourir entièrement, nous allons utiliser des « heuristiques », c’est-à-dire des méthodes qui, si elles ne garantissent pas de trouver le plan optimal, donnent assez rapidement des plans satisfaisants. Ces heuristiques utilisent souvent des règles de bon sens comme « il faut réaliser les sélections le plus tôt possible ». L’autre difficulté est que pour choisir le plan le moins chronophage, l’optimiseur (c’est-à-dire le programme en charge de l’optimisation) doit être capable d’estimer le coût de chaque plan candidat et c’est une tâche complexe à laquelle le système ne peut se permettre d’accorder trop de ressources. Donc, l’optimiseur fait « de son mieux ». Et typiquement les optimiseurs de systèmes comme Oracle ou DB2 font des merveilles sur des requêtes simples. C’est bien moins glorieux pour les requêtes complexes, par exemple mettant en jeu des quantificateurs universels comme la question : quels sont les acteurs qui n’ont joué que dans des comédies ? Heureusement, en pratique, la plupart des questions posées sont simples.

Sous-jacent dans la discussion sur l’optimisation de requête est la question de la difficulté d’obtenir une certaine information. Nous rencontrons la notion de « complexité ». Depuis Gödel, nous savons qu’il est des propositions qui ne peuvent être ni démontrées ni réfutées, qu’il est des problèmes qui ne peuvent être résolus. Cette notion d’indécidabilité commence péniblement à arriver jusqu’au grand public. Ce même public ne voit dans le fait qu’une requête prend plus ou moins longtemps que des raisons purement techniques. Evidemment, le temps de calcul dépend de la puissance du serveur, de la vitesse du disque ou de la qualité de l’optimiseur. Mais au-delà de tels aspects, il est des tâches qui demandent intrinsèquement plus de temps que d’autres. Par exemple, nous pouvons afficher à l’écran le gogol, le nombre consistant en un 1 suivi de 100 zéros, en quelques fractions de secondes, mais nous ne nous amuserions pas à afficher tous les nombres de 1 au gogol, 1, 2, … 10¹⁰⁰. Cela prendrait trop de temps. Même parmi les problèmes dont la réponse est courte (par exemple, la réponse est « oui » ou « non »), il en est qui, bien que décidables, sont intrinsèquement bien plus complexes que d’autres ; il en est même que nous ne savons pas résoudre en temps raisonnable. Parfois, cette difficulté trouve même son utilité. Le système cryptographique RSA repose sur le fait que nous ne savons pas factoriser (en général) un très grand entier en nombres premiers, en un temps raisonnable et qu’il est donc très difficile de décrypter un message sans en connaître la clé secrète.

La complexité est un aspect particulièrement important pour le traitement de gros volumes de données. Pour une requête particulière, nous voulons savoir :

· quel temps il faut pour la réaliser ? complexité en temps,

· quel espace disque (ou quelle mémoire) est nécessaire ? complexité en espace.

Evidemment ces quantités dépendent de la taille de la base de données. Si la requête prend un temps t et que nous doublons la taille n de nos données, nous faut-il attendre le même temps (temps constant), le double de temps (temps linéaire en n), ou est-ce que le temps grandit de manière polynomiale (en n^k où n est la taille des données) voire exponentielle (en kⁿ) ? Ce n’est pas anodin : sur de gros volumes de données, une complexité en temps n^k exigera une grosse puissance de calcul, et une complexité en kⁿ sera rédhibitoire.

Deux remarques nous permettent de préciser cette notion de complexité :

1. la complexité dans les données. En informatique, la complexité se mesure par la taille du problème, ici ce serait la taille des données plus la taille de la requête. Mais les requêtes étant typiquement nettement plus petites, il est bien plus instructif de ne considérer la complexité qu’en fonction de la taille des données. Nous parlerons de complexité dans les données.

2. les bornes inférieure et supérieure. Si un programme répond à une requête en temps n² dans la taille n des données, cela prouve seulement qu’il est possible d’y répondre en temps n², ce qui donne une borne supérieure. Peut-être existe-t-il un autre programme qui calcule la réponse plus rapidement, peut-être en temps constant. Si nous pouvons montrer qu’un temps n´log(n) au minimum est nécessaire, cela donne une borne inférieure. Par exemple, pour calculer le nombre de n-uplets de la jointure entre deux relations, n´log(n) se trouve être à la fois une borne inférieure et supérieure[14].

De nombreuses classes de complexité ont été étudiées. Intuitivement, une classe de complexité regroupe tous les problèmes qui peuvent être résolus sans dépasser certaines ressources disponibles, typiquement le temps ou l’espace. Par exemple, vous avez peut-être entendu parler de la classe P, temps polynomial. Il s’agit de l’ensemble des problèmes qu’il est possible de résoudre dans un temps n^k où n est la taille des données et k un entier arbitraire. Au-delà de P, nous atteignons les temps NP (pour non-déterministe polynomial[15]) et EXPTIME (temps exponentiel), des temps prohibitifs ? Pourtant, il faut relativiser. Les systèmes informatiques résolvent routinièrement des problèmes parmi les plus complexes de NP. Et, a contrario, pour 1.5 téraoctets de données, n³ est encore aujourd’hui hors d’atteinte, même en disposant de tous les ordinateurs de la planète.

Avant de poursuivre sur d’autres aspects du modèle relationnel, interrogeons-nous sur les origines de l’énorme succès des systèmes relationnels :

1. Les requêtes sont fondées sur le calcul relationnel, un langage logique, simple et compréhensible pour des humains surtout dans des variantes comme SQL.

2. Une requête du calcul relationnel est facilement traduisible en une expression de l’algèbre relationnelle simple à évaluer pour des machines.

3. Il est possible d’optimiser l’évaluation d’expressions de l’algèbre relationnelle car cette algèbre n’offre qu’un modèle de calcul limité.

4. Enfin, nous verrons que, pour ce langage relativement limité, le parallélisme permet de passer à l’échelle de très grandes bases de données.

Pour insister sur les deux derniers points qui sont essentiels, nous pourrions choisir pour les bases de données le slogan : « ici on ne fait que des choses simples mais on les fait vite. » Nous allons voir que nous les faisons aussi en lien étroit avec la logique.

Logique et complexité

Il se trouve qu’il est des liens profonds entre des classes de complexité et des classes de problèmes exprimables dans des logiques. Fagin a par exemple montré que NP coïncidait avec « la Logique existentielle du second ordre » (dans laquelle une variable représente un ensemble). Nous allons mentionner certains de ces liens. Même si nous allons essayer de gommer au maximum les détails techniques, cette discussion pourra paraître un peu ardue. Nous encourageons pourtant le lecteur à essayer de saisir la beauté de certains ponts entre la logique que nous voyons ici comme le langage permettant aux êtres humains de dialoguer avec des machines et les calculs que ces machines réalisent mécaniquement avec des ressources limitées.

Les requêtes relationnelles sont évaluables en P. Cela suggère la question suivante : est-il possible d’exprimer avec le calcul relationnel tout ce qu’une machine pourrait calculer en temps polynomial ? Il se trouve que non ! La requête suivante est dans P mais n’est pas exprimable dans le calcul relationnel : étant donné un graphe G, et deux points a, f de ce graphe, est-ce qu’il existe un chemin de a à f ? Aussi surprenant que cela puisse paraître, si nous pouvons avec le calcul relationnel demander s’il existe un chemin de longueur 3 ou même k, pour un k fixé, il faudrait pour un chemin de longueur arbitraire une disjonction infinie : un chemin de longueur 1 ou 2 ou 3 ou … Pour corriger ce problème, nous pouvons ajouter au langage un mécanisme qui permette de réitérer une requête du calcul relationnel jusqu’à un point fixe. Par exemple, pour la requête précédente, partant de l’ensemble T = { a }, nous ajoutons à T les points que nous pouvons joindre à partir de T en suivant un arc de G, et ce tant que T grandit. Quand le point fixe est atteint, il ne reste plus qu’à vérifier si f est dans T.

Le langage ainsi obtenu est appelé fixpoint. Comme les programmes ne font qu’ajouter des n-uplets dans des relations et n’inventent jamais de valeurs, la complexité reste dans P. Le langage obtenu en autorisant les programmes à supprimer des n-uplets est appelé while. Sa complexité est pspace : il peut être réalisé en utilisant un espace polynomial dans la taille des données. Un tel programme peut entrer dans une boucle, ne jamais s’arrêter[16], et donc ne jamais atteindre de point fixe. Ces langages permettent d’exprimer des requêtes très complexes. Pourtant, belle déception, des requêtes hyper-simples ne sont pas exprimables en fixpoint, pas même en while. C’est le cas par exemple de la requête : est-ce que le graphe G a un nombre pair de nœuds ? J’ai longtemps travaillé dans ce domaine notamment avec mon collègue Victor Vianu de UC San Diego. Nous avons caractérisé ce qui peut être calculé avec ces langages. Nous avons notamment prouvé[17] que fixpoint était égal à while si et seulement si P était égal à pspace, établissant ainsi un pont entre des logiques et des classes de complexité[18].

Nous notons en passant que si pspace « a l’air » bien plus puissant que P, nous ne savons pas s’ils sont différents. Nous ne savons d’ailleurs pas non plus si P ¹ NP, le problème ouvert le plus célèbre de l’informatique. Si nos connaissances progressent en théorie de la complexité, de nombreux défis persistent, fascinants et complexes. Et pour conclure cette discussion sur les liens entre logique et complexité, nous mentionnerons un autre problème ouvert : obtenir une logique qui capture exactement les requêtes dans P, intuitivement les requêtes auxquelles il est possible de répondre dans un temps raisonnable. En pratique, cela voudrait dire disposer d’un langage qui ne permettrait d’exprimer que des requêtes dans P, mais qui permettrait d’exprimer toutes les requêtes de P. S’il est probable qu’un tel langage serait de fait peu utilisable en pratique, le problème est si beau qui relie le logiquement exprimable et le rapidement calculable.

Et pour conclure cette partie, nous allons discuter deux aspects essentiels de la gestion de données : les transactions et le parallélisme.

Transactions

To serve and protect data[19], Anonyme

La modernisation des chaînes de fabrication a été principalement causée dans un premier temps par l’électronique et l’automatique. Avant de s’imposer aussi dans la production, l’informatique a elle profondément pénétré l’industrie en modifiant radicalement la manière dont des transactions, comme les commandes ou la paye, étaient gérées de manière automatique. Une transaction informatisée est la forme dématérialisée d’un contrat. Son coût peut se trouver incomparablement plus faible que celui d’une transaction réelle mettant en jeu des déplacements de personnes sur des échelles de temps bien plus longues. Avec des fonctionnalités considérablement élargies par le recours à l’informatique, les transactions se retrouvent au cœur de nombreuses applications qui ont largement contribué à populariser les systèmes relationnels comme, par exemple, les applications bancaires.

Les systèmes relationnels répondent aux besoins des transactions en supportant la notion de transaction relationnelle. Une transaction relationnelle garantit qu’une séquence d’opérations se réalise correctement, par exemple en empêchant qu’une somme d’argent ne s'évanouisse dans la nature (avec un compte en banque débité sans qu'un autre ne soit crédité). Même l’occurrence d’une panne[20] ne doit pas pouvoir conduire à une exécution incorrecte. Il nous faut donc formaliser la notion d’exécution correcte. Evidemment, il serait impossible de le faire précisément s’il fallait tenir compte des millions de choses que font de tels systèmes. Mais l’informatique comme les mathématiques dispose d’un outil fantastique : l’« abstraction ». Nous pouvons considérer ce que fait un système relationnel sous l’angle des transactions relationnelles et des modifications qu’elles apportent aux données, en faisant abstraction de toutes les autres tâches qu’il réalise. Il devient alors possible de définir formellement la notion d’exécution correcte.

Nous pouvons mentionner d’autres tâches que les systèmes relationnels accomplissent à coté de l’évaluation de requêtes et de la gestion de transactions relationnelles. Ils gèrent également :

· les contraintes d’intégrité (telles que « tout responsable de projet doit être enregistré dans la base des personnels »),

· les déclencheurs ou « triggers » (tels que « si quelqu’un modifie la liste des utilisateurs, envoyer un message au responsable de la sécurité »),

· les droits des utilisateurs (pour contrôler qui a le droit de lire ou de modifier quoi),

· les vues (pour s’adapter aux besoins d’utilisateurs particuliers),

· l’archivage (pour pouvoir retrouver des données périmées depuis des lustres),

· le nettoyage des données (pour éliminer les doublons, les incohérences).

Parallélisme

Pour gérer de gros volumes de données, l’utilisation du parallélisme s’avère essentiel. De plus en plus les machines sont multi processeurs. Mais nous insisterons ici surtout sur l’utilisation de plusieurs machines travaillant simultanément sur une tâche commune. Ce type d’approches est tout particulièrement fondamental pour la Toile qui met en jeu des volumes considérables d’information :

· parallélisme entre peut-être les dizaines, centaines voire milliers de serveurs d’une « grappe[21] » ;

· parallélisme entre les millions de serveurs de la Toile qui fonctionnent indépendamment mais interagissent en permanence.

Pour conclure cette partie, deux exemples en guise d’illustration, pour faire sentir au lecteur la puissance du parallélisme :

· Plutôt que de regrouper les comptes de ses clients dans un centre informatique unique, une entreprise peut choisir de les laisser gérer dans ses centres régionaux. Regrouper les données sur une machine unique avec des performances comparables, demanderait un serveur très sophistiqué, donc plus cher. Notons aussi qu’une organisation distribuée s’accorde mieux à un management plus décentralisée de l’entreprise.

· Deux types d’organisations sont possibles pour la diffusion de films. Dans une première, chaque film est conservé sur un serveur unique. Si le nombre de clients augmente ou si un film est trop populaire, le serveur est vite saturé. Dans une autre organisation, une architecture pair-à-pair, chaque machine est un pair, c’est-à-dire à la fois serveur et client. Si un pair demande un film, il peut stocker ce film et le transmettre plus tard à d’autres. Plus un film est populaire, plus il devient disponible sur un grand nombre de machines, et plus son téléchargement devient facile et rapide.

Nous avons considéré dans cette partie la gestion de données dans des systèmes relationnels. Nous nous intéressons maintenant aux systèmes d’information de la Toile, et pour commencer aux plus répandus d’entre eux, les moteurs de recherche de la Toile.

3. Les moteurs de recherche de la Toile

Internet : on ne sait pas ce qu'on y cherche mais on trouve tout ce qu'on ne cherche pas. Anne Roumanoff

Le World Wide Web, introduit par Tim Berners-Lee et Robert Cailliau vers 1990, s’appuie sur des documents hypermédia. C’est la Toile à laquelle nous nous sommes si rapidement habitués. L’information est en langue naturelle et les textes vaguement structurés avec les balises HTML pour, par exemple, des titres ou des énumérations. Des ancres sur lesquelles l’internaute peut cliquer conduisent à d’autres pages HTML mais aussi à des images, de la musique, des vidéos. Dans cette partie, nous allons parler d’un des plus beaux succès de la Toile, le moteur de recherche. Le moteur de recherche de la Toile nous permet de fuir la navigation fastidieuse sur le graphe des pages et le monde de l’hypertexte pour nous plonger dans une bibliothèque numérique universelle. Nous allons expliquer comment fonctionne un tel moteur. Le lecteur pourra trouver plus de détails dans l’article historique de Sergeï Brin et Larry Page[22] ou dans notre ouvrage récent[23].

Le moteur de recherche s’intéresse à une vision de la Toile comme bibliothèque universelle. L’internaute cherche une information. Même si la Toile n’a sûrement pas de réponses à toutes ses questions, cette information se trouve peut-être dans les masses d’informations et de connaissances véritablement extraordinaires réunies. Tels des enfants, nous nous émerveillons devant les dizaines de milliards de documents de la Toile. Mais un enfant apprend, depuis son plus jeune âge, à évaluer, classer, filtrer la masse considérable d’informations qu’il rencontre. Et nous ? Si le moteur de recherche ne nous aidait pas à nous focaliser sur un petit nombre de pages, que ferions-nous ? L’exploit technique c’est de retrouver en un instant, grâce à son index, les pages de la Toile qui hébergent les mots demandés. La magie, c’est de proposer parmi les dizaines, voire centaines de millions de pages possibles, les quelques pages qui contiennent si souvent ce que l’internaute recherche. Nous examinons tour à tour ces deux facettes des moteurs de recherche.

Un index de la Toile

La mission de Google : organiser les informations à l'échelle mondiale dans le but de les rendre accessibles et utiles à tous. Google

Un index de la Toile associe à chaque mot la liste des pages qui contiennent ce mot. Par exemple, une entrée dans cet index serait :

Casablanca ® http://www.imdb.com/title/tt0034583/, http://films.com/Bogart/ ,...

qui indique que le mot « Casablanca » est présent notamment dans ces pages des sites IMDb et films.com. Si vous donnez au moteur de recherche plusieurs mots comme « Casablanca Bogart Bergman », il calculera la liste des pages de la Toile qui contiennent tous ces mots.

Une sérieuse difficulté est la taille de cet index : des dizaines de téraoctets de données pour quelques milliards de pages. Un serveur d’un tel index rencontre deux problèmes de passage à l’échelle :

1. Pour indexer plus de pages, le serveur a besoin de plus en plus de stockage pour garder l’index, et chaque requête devient de plus en plus coûteuse à évaluer.

2. Si le nombre d’utilisateurs croît, le serveur reçoit de plus en plus de requêtes.

Dans les deux cas, le serveur est vite submergé. Pour résoudre ce problème nous allons utiliser le parallélisme et une technique fondamentale de l’informatique, la technique du hachage.

Pour illustrer la technique, nous allons utiliser K=10 machines M₁, …, M₁₀ et une fonction H qui, appliquée à un mot, retourne un entier choisi aléatoirement entre 1 et 10 (et qui retourne, pour un mot donné, à chaque fois le même entier). Cette fonction est appelée fonction de hachage. La responsabilité d’un mot w est donnée à la machine H(w). Supposons qu’un « crawler » (un programme qui parcourt la Toile en quête de pages) découvre le mot « France » sur une page d’URL p. L’entrée de l’index, qui dit que la page p contient ce mot, est stockée sur la machine H(« France »), disons M₇. Les données sont donc partagées relativement équitablement entre les dix machines ce qui résout le premier problème. Supposons maintenant que quelqu’un veuille les données correspondant au mot « France », il interroge la machine M₇. Les requêtes sont donc elles-aussi partagées relativement équitablement entre les dix machines, ce qui résout le second problème. Il nous faut évidemment réaliser un index sur chaque machine. Typiquement, nous pouvons là-aussi utiliser une technique de hachage, centralisé cette fois.

Maintenant si la taille des données que nous voulons indexer ou le nombre de clients grandissent, il suffit d’ajouter des machines. Par exemple, Google utilise des milliers de machines dans des « fermes »[24] et disperse ses fermes aux quatre coins du monde. Le parallélisme nous a permis le passage à l’échelle. Vous avez dit brillant ?

Pourquoi est-ce que cela marche ? Grâce au parallélisme. De manière générale, pouvons-nous prendre n’importe quel algorithme et l’accélérer à volonté en utilisant plus de machines ? La réponse est non ! Tous les problèmes ne sont pas aussi aisément parallélisables. Il se trouve que la gestion d’index est un problème très simple, très parallélisable[25] (« embarrassingly parallel »). Donc, nous pouvons sans frémir envisager d’indexer de plus en plus de pages, des dizaines de milliards ou plus.

Un point fixe et quelques algorithmes

Playboy: Is your company motto really "Don't be evil"?

Brin: Yes, it's real.

Playboy: Is it a written code?

Brin: Yes. We have other rules, too.

Page: We allow dogs, for example[26].

Sergey Brin et Larry Page, fondateurs de Google. Interview dans le magazine Playboy, 2004

Le cœur du problème reste maintenant de choisir parmi les millions de pages qui contiennent les mots de la requête. C’est essentiel car un utilisateur ira rarement au-delà des dix ou vingt premiers résultats qui lui seront proposés. Au départ, les moteurs de recherche comme Alta Vista utilisaient, pour classer les pages, des techniques basées uniquement sur leurs contenus comme dans les bibliothèques numériques traditionnelles. Une page était jugée plus intéressante si le terme apparaissait dans un titre, ou en caractère gras. Ces moteurs utilisaient des mesures statistiques du style de TF-IDF (pour Term Frequency-Inverse Document Frequency) qui évaluent l'importance d'un terme dans un document relativement à un corpus de documents. Plus le terme est répété dans le document plus il « pèse ». Et, plus le terme est rare dans le corpus plus il pèse. Ce genre de techniques qui marchent bien sur de petits corpus s’est avéré assez décevant pour la Toile.

Les jeunes créateurs de Google ont eu l’idée de baser l’ordre des pages sélectionnées sur une connaissance collective présente de manière implicite dans la masse des pages. Plus précisément, ils ont utilisé une technique classique en mathématiques, la marche aléatoire. C’est cette idée inspirée de travaux antérieurs notamment de Jon Kleinberg[27] qui est à l’origine de l’algorithme PageRank de Google, et du succès industriel de cette société, l’un des plus étonnants de l’histoire de l’humanité.

La marche aléatoire.

Imaginez un « surfeur de la Toile ». Il part d’une page, disons la page www.inria.fr/. Ensuite, il se balade sur la Toile en choisissant à chaque étape, au hasard, un des liens de la page, et en cliquant sur ce lien. Si la page n’a pas de lien, il choisit aléatoirement une page n’importe où sur la Toile. Et il continue encore et encore, pour toujours. Quelle est à l’infini sa probabilité de se trouver sur une page précise ? C’est ce que nous définirons comme la popularité de cette page. Intuitivement, si une page est populaire (comme la page www.lemonde.fr/), de nombreuses pages la référencent et la probabilité de se retrouver sur cette page est bien plus grande que de se retrouver sur une page d’une bloggeuse inconnue (comme Alice). A priori, une définition abstraite, un joli concept de mathématiques totalement inutile ? Non. Car il se trouve qu’en pratique cette popularité correspond assez bien aux attentes des internautes.

Reste à calculer cette popularité. Pour cela, nous allons la mettre en équation. Supposons que nous indexions dix milliards de pages. Nous les numérotons de 1 à N = dix milliards. Dans une approche classique en mathématiques, imaginons que nous connaissons déjà cette popularité. Nous disposons donc d’un vecteur pop, où pour chaque page i, pop[i] est la popularité de la page. (C’est la probabilité de se trouver sur cette page ; notons que å_{i=1 à N} pop[i] = 1.) Chaque page distribue disons 90% de sa popularité équitablement entre toutes les pages vers laquelle elle pointe, et les 10% qui restent entre toutes les pages indexées. Si une page est un cul-de-sac (elle ne conduit nulle part), elle partage toute sa popularité entre toutes les pages indexées. En ignorant quelques détails, cela nous conduit à une matrice Q qui capture ces « échanges » de popularité et à une équation de point fixe :

pop = Q ´ pop,

une notation bien compacte pour un système de dix milliards d’équations à dix milliards d’inconnues. Il se trouve que ce système a pour solution le vecteur des popularités. Et là, banco ! Une technique connue nous permet de calculer cette solution. 

Le point fixe

Dans l’absence d’autre information, partons du vecteur pop₀ défini par pop₀[i] = 1/N, c’est-à-dire que toutes les pages sont supposées également populaires. Et définissons :

pop₁ = Q´ pop_{0 ;} pop₂ = Q ´ pop_{1 ;} pop₃ = Q ´ pop₂ …

En poursuivant ce calcul, nous convergeons sur un point fixe qui se trouve être la solution de notre équation. Nous avons calculé le vecteur de popularité ! (Comme, en pratique, nous pouvons nous contenter de peu de précision, 6 ou 7 itérations suffisent.)

Vous avez dit élémentaire ? Pas tant que ça. Même si la matrice est très « creuse[28] », pour réaliser ce calcul efficacement avec des volumes de données pareils, il faut des algorithmes très sophistiqués, une ingénierie de fou. Ce n’est peut-être plus des mathématiques mais c’est de l’informatique de toute beauté.

Et pour conclure sur les moteurs de recherche

Nous avons présenté une version très simplifiée d’un moteur de recherche. Les moteurs de recherche modernes combinent TF-IDF et la popularité des pages que nous venons de définir à bien d’autres critères pour choisir quelles pages classer en tête. Chaque jour, les moteurs de recherche sont plus sophistiqués[29] pour mieux répondre aux attentes des internautes. Ils se compliquent ne serait-ce que pour contrer les attaques comme celles des « spamdexeurs » qui trichent pour être apparaître plus hauts dans les résultats. Ils nous posent aussi des problèmes essentiels. Pour n’en citer que quelques uns :

· L’interrogation de la Toile est basée sur des listes de mots-clés, une langue primitive quasiment sans grammaire. Il est sûrement possible de faire mieux.

· Une mesure qui privilégie la popularité des pages a pour effet d’encourager l’uniformité, les pages populaires devenant de plus en plus populaires et les autres sombrant dans l’anonymat. C’est certainement discutable tout comme le fait que la popularité utilisée par les moteurs de recherche actuels semble ignorer si la page est citée pour sa qualité (son exactitude) ou pas.

· Faut-il exclure des pages, parce qu’elles sont racistes, vulgaires, fausses (pourquoi pas), et pour favoriser un client ou ne pas déplaire à un gouvernement (au secours !) ?

· Enfin, il est quelque chose d’extrêmement embarrassant dans la puissance considérable que les moteurs de recherche ont de par leur contrôle de l’information surtout dans un contexte de quasi monopole (au moins en Europe). Devons-nous leur faire confiance sans comprendre le secret de leur classement ? Et pourquoi ce secret ?

Je me trouvais dans le groupe de recherche sur les systèmes d’information à Stanford en 1995 quand deux jeunes étudiants, Sergei Brin et Larry Page y travaillaient sur le prototype du moteur de recherche Google. J’ai été tout de suite conquis par leur proposition d’utiliser la popularité des pages. Il m’a fallu par contre m’habituer à l’idée de garder l’index en mémoire. Une telle technique aurait été irréaliste quelques années plus tôt, car elle aurait conduit à utiliser un nombre improbable de machines très coûteuses. En 1995, la gestion de l’index en mémoire devenait envisageable avec un nombre raisonnable de machines bon marché. Cela illustre bien qu’en informatique, les champs du possible évoluent en permanence.

De retour en France, j’ai conçu avec deux étudiants, Mihai Preda et Gregory Cobena, un algorithme pour calculer la popularité des pages[30]. Concevoir cet algorithme, prouver qu’il calcule bien le point fixe de l’équation, l’implémenter sur une grappe de machines, fixer les bogues, l’optimiser, expérimenter, atteindre le milliard de pages. Je n’avais jamais touché à de tels volumes de données. C’est parmi une de mes plus fantastiques expériences de chercheur.

Plusieurs sociétés se partageaient dans les années 90 le marché des moteurs de recherche. Les utilisateurs allaient plébisciter le moteur de Google. Comme base à ce succès extraordinaire, nous pourrions mentionner une ingénierie exceptionnelle pour faire fonctionner des milliers de machines 24 heures sur 24, des modèles commerciaux révolutionnaires, des techniques de management originales fondées sur le culte de la créativité. Mais en ce qui me concerne, je préfère me rappeler qu’au début, il y avait juste un point fixe et quelques algorithmes.

4. Réseaux et connaissances collectives

Avoir ou ne pas avoir de réseau : that’s the question. Bruno Latour

L’écriture nous a permis d’ « externaliser » en partie notre mémoire. L’imprimerie nous a permis de transmettre cette mémoire externe. La Toile a diminué considérablement les coûts de transmission de l’information. Surtout, elle a permis à chacun d’apporter sa contribution personnelle au patrimoine collectif (avec des réserves comme la fracture numérique dont nous parlerons plus loin). La consommation passive d’information du début de la Toile a ainsi cédé la place à des contributions actives par des internautes de plus en plus nombreux. Alice passe ses soirées sur Facebook à chatter avec une poignée d’amis quand son fils est sur World of Warcraft avec des copains du monde entier, qu’il n’a jamais rencontrés « pour de vrai ». Elle publie son blog. Il twitte à longueur de journée.

La Toile, c’est donc aussi une juxtaposition de milliards d’individus et de tous leurs réseaux. Après les réseaux de machines, les réseaux de contenus, nous atteignons les réseaux d’utilisateurs. Parmi les systèmes récents les plus répandus, nombreux sont ceux qui s’attachent à intensifier les échanges d’informations entre des individus à l’intérieur de leurs réseaux, depuis les jeux en ligne jusqu’aux logiciels de réseaux sociaux comme Facebook ou Google+. Les jeunes ont adopté avec passion les réseaux sociaux. Les seniors, après un temps d’hésitation, avec beaucoup de temps libre et peut-être autant d’envie de contacts sociaux, s’y engouffrent avec enthousiasme.

Ces nouveaux systèmes n’ont plus pour cible l’universalité de la Toile, mais les individus et les groupes plus ou moins bien définis auxquels ils appartiennent. Ils redéfinissent les distances entre individus et proposent d’autres proximités. Prenons une personne qui nous est inconnue. Il nous suffit d’un nom, et si le nom est trop commun de quelques vagues indications, pour que sa vie se déroule devant nous. Pour peu que cette personne soit un peu visible sur la Toile, elle envahit notre vie, avec ce qu’elle publie, ce qui se dit d’elle, par ses mille liens avec les autres et les traces qu’elle laisse un peu partout. Il n’est même pas nécessaire que la « cible » soit célèbre[31]. Nous nageons dans ce qui pourrait être un paradis pour biographe d’antan, ou peut-être un cauchemar, car a disparu la place du rêve.

Ces systèmes soulèvent un grand nombre de sujets de recherche, parfois à la frontière de l’informatique et de la sociologie. Nous allons insister ici sur un aspect particulièrement passionnant, l’émergence de connaissances collectives[32]. Nous allons brièvement considérer plusieurs approches qui sont utilisées pour obtenir de telles connaissances :

1. La notation, par exemple, de produits ou d’entreprises par des internautes ;

2. L’évaluation de l’expertise des internautes ;

3. La recommandation, par exemple, de produits ;

4. La collaboration entre internautes pour réaliser collectivement une tâche qui les dépasse individuellement ; et

5. Le crowdsourcing qui met des humains au service de systèmes informatiques.

La notation

L’internaute est invité à noter d’autres internautes, des services, des produits, et participe ainsi à la construction d’une connaissance collective. Par exemple, eBay permet aux acheteurs de donner leur avis sur les vendeurs de sa plateforme (et réciproquement). Cela conduit à une fantastique incitation à fournir un excellent service au risque, sinon, d’être mal noté et de perdre des clients. Les systèmes fourmillent qui utilisent les avis de leurs utilisateurs comme ViaMichelin pour les restaurants ou AlloCiné pour les films. Notons que, dans ces deux cas, les critiques qui notaient jusqu’alors les restaurants ou les films perdent une forme de monopole. Des systèmes plus expérimentaux essaient d’extraire des connaissances plus fines que des notes, à partir d’avis textuels. Nous rencontrons là les difficultés à analyser des sentiments d’un texte.

Ces systèmes de notation ont aussi leur place au niveau global de la Toile. Par exemple, le système Delicious demande aux internautes d’associer des mots-clés (de la sémantique) aux pages. Une mesure de popularité, comme celle discutée dans la partie précédente, peut aussi être vue comme tenant de la notation : une référence à une page est interprétée comme une note positive, une critique participant autant qu’une louange à la popularité d’une page. A ce propos, il a été dit qu’une société de service délivrait volontairement de mauvais services à certains de ses clients pour que ceux-ci en parlent sur la Toile et augmentent ainsi la popularité, donc la visibilité, de la société en question. Même si cette information non vérifiée n’est peut-être qu’une des légendes de la Toile, le fait que la popularité ignore le sens des références est dérangeant. En analysant les liens de la Toile suivant un système de notation plus riche (avec des notes négatives), ce biais pourrait être corrigé.

L’évaluation de l’expertise

Une technique essentielle pour évaluer la qualité d’une information est de déterminer la qualité de la source, la confiance que nous pouvons avoir dans les informations que cette source fournit en général. Pour illustrer ce type de techniques, nous mentionnerons un travail récent sur la corroboration[33]. Imaginons un système où des internautes introduisent des connaissances. Ils peuvent se tromper. Pourtant, s’ils ne faisaient que spécifier des connaissances positives comme « Alice possède une 2CV », rien ne pourrait empêcher le système de croire tout ce que disent les internautes, y compris toutes leurs erreurs. Pour que le système puisse commencer à douter, il faut que des internautes se contredisent, et pour cela, qu’ils se mettent à publier des informations négatives comme « Alice ne possède pas de BMW ». En général, les internautes ne veulent pas perdre de temps à entrer explicitement de telles informations notamment parce que la liste des informations fausses est bien au-delà de l’accessible. Pourtant, les internautes publient des informations négatives sans le savoir. Par exemple, le fait qu’« Alice est née à Romorantin » indique qu’elle n’est pas née à Sèvres, du fait d’une « dépendance fonctionnelle », c’est-à-dire d’une loi que doivent satisfaire les données (ici, la loi qui spécifie qu’une personne ne peut pas être née à deux endroits distincts).

Dans le travail cité précédemment, nous utilisons les informations incluant des négations provenant de dépendances fonctionnelles. Nous estimons la véracité des connaissances, en déduisons les taux d’erreurs de chaque internaute, ce qui nous procure une meilleure estimation de la véracité des connaissances, d’où des taux d’erreurs plus précis pour chaque internaute, etc. Nous continuons ce processus jusqu’à atteindre un point fixe (un de plus). Ce travail illustre bien comment il est possible de dégager collectivement des connaissances.

Comme la notation, l’évaluation de l’expertise a sa place sur la Toile. C’est en particulier le cas pour ce qui concerne les informations publiées par la presse. Des blogs, comme celui de Maitre Eolas pour les affaires juridiques, font maintenant autorité. De simples internautes sont de plus en plus amenés à remplacer les journalistes, comme récemment en Tunisie ou en Syrie. Cela ne rend que plus crucial le besoin de croiser les informations, de les vérifier. Nous pouvons imaginer que demain des programmes participeront à déterminer les réputations en termes d’information dans cet espace-temps de la Toile qui donne le tournis.

La recommandation

Un système comme Meetic utilise les données fournies par ses clients pour organiser des rencontres, pour les apparier. Un système comme Netflix recommande des films. Pour ce faire, ces systèmes réalisent typiquement des analyses statistiques dans le cadre classique très général de la fouille de données. Ils essaient de mettre en évidence des « proximités » entre clients dans Meetic ou entre clients et produits dans Netflix. Ils peuvent regrouper des personnes parce qu’elles partagent les mêmes goûts même si elles ne se sont jamais rencontrées, ou découvrir des affinités inattendues entre produits. L’exemple souvent cité est que les clients de couches-culottes achètent statistiquement beaucoup de bières. Les classifications des clients et des produits s’enrichissent donc mutuellement et participent ainsi à établir de nouvelles proximités entre individus et produits.

De telles analyses sont réalisées à très grandes échelles par exemple par Amazon ou Google. Elles sont encore souvent mathématiquement peu fondées et leurs résultats sont rarement satisfaisants. Réaliser des analyses statistiques de qualité, sur des volumes de données de plus en plus grands, est un des défis du domaine de la gestion d’information.

La collaboration

Wikipédia est un bel exemple d’édition coopérative. Un grand nombre d’internautes collaborent pour développer une encyclopédie. Tout le monde peut participer. Il est facile d’imaginer la cacophonie résultant des incompétences, des désaccords, des intérêts personnels. La tâche semble impossible. Pourtant si la qualité de son contenu est parfois contestée, il est passionnant de voir la place considérable prise si rapidement par Wikipédia dans la diffusion des connaissances[34]. Le recours à une foule d’auteurs a permis de dépasser la notion classique d’encyclopédie avec une couverture bien plus large. Nous trouvons de tout dans Wikipédia depuis la biographie de Clémence Castel, une héroïne de Koh-Lanta, jusqu’à la preuve du Lemme de l’Etoile, un résultat fondamental de théorie des langages. Les erreurs y sont nombreuses… Il y en a aussi dans les encyclopédies traditionnelles.

Wikipédia est loin d’être le seul exemple de telles collaborations. Tout aussi étonnant est l’aboutissement des logiciels réalisés par des communautés de développeurs dans le cadre des logiciels libres, comme le système d’exploitation Linux. Et nous commençons à voir des communautés s’organiser pour construire des corpus de données ouvertes comme le Web des données (en anglais, ”linked data”) du Consortium World Wide Web.

Le crowdsourcing

Nous utiliserons ici le terme anglais[35] « crowdsourcing » Il s’agit de publier sur la Toile des problèmes que des programmes ne savent pas bien résoudre ; des internautes proposent alors des réponses, typiquement moyennant finance. Des systèmes comme le Mechanical Turk[36] d’Amazon permettent de tels contacts. Les compétences de la foule ont été utilisées par exemple pour rechercher sans succès l’un des plus célèbres chercheurs du domaine des bases de données, Jim Gray, disparu avec son yacht au large des îles Farallon. Les internautes devaient observer des photos satellites à la recherche d’indices. En utilisant un jeu vidéo, Foldit, des internautes sont en revanche arrivés à décoder la structure d’une enzyme proche de celle du virus du sida[37]. Ils ont réalisé ce qui bloquait experts et ordinateurs, comprendre comment cette enzyme se repliait dans un espace en trois dimensions pour construire sa structure. Le jeu se marie ici au réseau, dans le plus pur esprit des réseaux sociaux.

L’originalité de tels dispositifs est que l’individu se retrouve au service d’un système informatique, qui l’utilise, par exemple, pour compléter sa base de connaissances ou résoudre des contradictions dans cette base.

Le pouvoir des masses d’internautes

群众是真正的英雄[38]. Mao Tsé-Toung

Ces approches conduisent en général à résoudre des problèmes complexes d’analyse de données impliquant un grand nombre de personnes et de gros volumes d’information. L’évaluation de la « qualité » est au cœur du sujet, la qualité d’une information, la qualité d’une source (un internaute, un service). Et, de plus en plus, l’individu est au centre du dispositif, passivement par exemple via son profil ou activement par exemple en spécifiant ce qu’il sait, ce qu’il croit, ce qu’il aime.

Confronté à des systèmes s’attachant à construire une connaissance collective, l’internaute ignore le plus souvent quelles données ont été utilisées et ne comprend parfois pas comment le résultat a été obtenu. Il peut être alors amené à trouver les informations proposées, surprenantes, magiques, inquiétantes. La difficulté d’expliquer les résultats est une faiblesse souvent présente dans les approches que nous venons de discuter et qui en limite les usages.

Un autre problème sérieux de ces approches est lié aux atteintes à la confidentialité de l’information. Pour mieux servir leurs utilisateurs, ces systèmes doivent réunir le plus d’information possible sur eux. Un réseau social comme Facebook construit par exemple une base de connaissances sur chacun de ses clients. L’internaute est de plus en plus souvent amené à fournir des informations pour bénéficier de la gratuité de services. Les systèmes vont même jusqu’à s’échanger des informations sur leur clients ; toujours pour mieux les servir ? Cela conduit à des conflits d’intérêts. Un système de réseau social doit choisir entre le besoin de protéger les données de ses clients (au risque sinon de les perdre) et son avidité naturelle pour les données confidentielles. De son coté, l’internaute aimerait bien que les informations le concernant restent le plus confidentiel possible mais il est aussi friand de services très personnalisés.

Pour conclure cette partie, oublions temporairement ces problèmes pour nous émerveiller de voir des algorithmes faire surgir des informations disponibles sur la Toile des connaissances dont nous n’imaginions pas l’existence. Ceci nous conduit à un domaine plus ancien mais qui, avec la Toile, se découvre une nouvelle jeunesse, la gestion de connaissances. C’est le sujet de notre prochaine partie.

5. La Toile des connaissances

[39]תָּמוּת מֹות מִמֶּנּוּ אֲכָלְךָ בְּיֹום כִּי מִמֶּנּוּ תֹאכַל לֹא וָרָע טֹוב הַדַּעַת וּמֵעֵץ

Le domaine des bases de connaissances existait depuis longtemps quand est née la Toile. Mais si les bases de données étaient déjà alors une industrie florissante, les bases de connaissances peinaient à se faire une place au soleil. Cette place, elles sont en train de l’acquérir avec la Toile. Nous parlerons dans cette partie de la Toile des connaissances.

La Toile des documents est fondée sur le fait que les gens aiment écrire, lire, dire, écouter du texte dans leurs langues naturelles. Aujourd’hui, les internautes communiquent principalement entre eux à l’aide de texte. Pourquoi et comment passer à une Toile des connaissances ? Et tout d’abord, qu’est-ce que c’est ?

Le Web sémantique

Dans sa forme la plus homéopathique, il s’agit d’expliquer le sens de documents textuels de la Toile, d’éléments qui les composent, ou, comme nous le verrons plus loin, de services informatiques disponibles sur la Toile (les services Web). Cela peut se faire en publiant des métadonnées, c’est-à-dire des données qui expliquent les données. Par exemple, pour le document que vous êtes en train de lire, nous pourrions publier :

auteur = Serge Abiteboul ;

nature = leçon inaugurale ;

institution = Collège de France ;

date = Mars 2012 ;

langue = français.

A l’intérieur des documents, des étiquettes sémantiques peuvent aussi être attachées à des fragments constitutifs d’un texte pour les expliquer. Par exemple, accolée à la chaîne de caractères Woody Allen, l’étiquette dbpedia:Woody_Allen précise qu’il s’agit d’une personne référencée dans « dbpedia », une base de connaissances très utilisée. Nous trouverons notamment dans cette ontologie qu’il s’agit du célèbre cinéaste qui a réalisé Manhattan.

Les bases de connaissances comme dbpedia sont appelées des « ontologies ». En simplifiant, une ontologie se compose de phrases comme celles-ci :

1. classes Personne, Réalisateur, Cinéaste

2. Réalisateur sous classe de Personne

3. Réalisateur synonyme de Cinéaste

4. dbpedia:Woody_Allen est un Réalisateur

5. relation a_réalisé

6. dbpedia:Woody_Allen a_réalisé film:Manhattan

qui spécifient des classes d’objets (1), des inclusions ou des égalités entre classes (2,3), l’appartenance d’un objet à une classe (4), des relations entre objets (5), des instances de ces relations (6).

Utiliser un texte brut découvert sur la Toile sans explication s’apparente à utiliser les résultats d’une expérience scientifique en ignorant les conditions de sa réalisation, ses unités de mesure, etc. Des étiquettes introduites dans le texte, basées sur des ontologies, précisent le sens de ce texte, l’enrichissent en y ajoutant de la sémantique. Par exemple, l’étiquette dbpedia:Woody_Allen attachée à une phrase indique que la phrase parle de Woody Allen, un réalisateur, un cinéaste, une personne, et pas du musicien Allen Woody. Et cette phrase devient une réponse à la question sous forme de mots-clés « cinéaste Woody Allen Manhattan » même si elle ne contient ni le mot cinéaste ni le mot Manhattan. Par contre, une phrase parlant d’un séjour de Allen Woody (précisant qu’il s’agit du musicien dbpedia:Allen_Woody) à Manhattan ne serait pas comprise comme une réponse. L’ontologie permet donc de répondre de façon plus fine aux requêtes.

Sur la Toile, n’importe qui peut publier ses propres ontologies. Des experts utilisent des terminologies spécifiques suivant leurs langues, leurs domaines, leurs cultures, etc., dans la pure tradition de tour de Babel. Cette diversité est une richesse mais elle complique la recherche de connaissances. La même information peut être représentée de multiples manières. Surtout, nous sommes sur la Toile et nous allons trouver des masses de faits erronés. Ce qui est encore plus compliqué à gérer, c’est que des sites peuvent publier des règles qui mettent en péril nos propres connaissances. Par exemple, qu’allons-nous faire si quelqu’un affirme que « Personne est un synonyme de Film » ? Si nous ne pouvons l’interdire, nous devons faire en sorte que cela ne pollue pas nos raisonnements.

Cela conduit à toute une gamme de problèmes passionnants : comment utiliser des ontologies pour mieux répondre aux questions des internautes ? Comment « aligner » des ontologies, c’est-à-dire établir des liens entre leurs concepts et leurs relations, pour « intégrer » des informations venues de sources indépendantes ? Comment gérer les incohérences ? Comment évaluer la qualité des connaissances ?

De l’acquisition de connaissances

Maintenant que nous comprenons l’intérêt de disposer de connaissances en plus de textes, la question difficile devient « comment acquérir ces connaissances ? ». Le plus souvent les mêmes individus, qui aiment publier sur la Toile dans leur langue naturelle, apprécient peu les contraintes d’un éditeur de connaissances. Un expert chimiste va par exemple « entrer » dans une base (en utilisant un éditeur) ses connaissances sur les molécules qu’il étudie. Il a une raison objective de le faire : l’avancement de la science. Et ce genre de publication dans des bases de données contribue aujourd’hui à une visibilité scientifique au même titre que des publications dans des journaux scientifiques. Mais les cas d’internautes entrant volontairement et gratuitement des connaissances dans un système restent rares et, le plus souvent, les tâches de construction de bases de connaissances sont laissées à des logiciels.

Prenons par exemple la base de connaissance Yago, développée à partir de la version anglaise de l’encyclopédie Wikipédia que nous avons déjà mentionnée. Wikipédia est au départ une collection de textes. Pour améliorer sa précision, ses éditeurs encouragent l’introduction de fragments de connaissances. (Allez sur la page Wikipédia de Woody Allen et cliquez sur l’onglet « Modifier » pour vous en convaincre.) C’était donc un excellent point de départ pour développer une vraie base de connaissances. Cette base, appelée Yago, a été construite à l’aide d’un logiciel développé à l’Institut Max Planck[40]. En 2011, Yago avait déjà 2 millions d’entités et 20 millions de relations entre ces entités.

Si la Toile reste très largement dominée par HTML et le texte, les bases de connaissances de demain sont déjà en construction à partir de l’énorme ressource que constitue la masse de documents textuels. Il s’agit essentiellement de comprendre les textes et d’en « extraire » des connaissances. La tâche est complexe parce qu’elle met en jeu la compréhension de la langue. Les extracteurs de connaissance font des erreurs et il est difficile de leur en vouloir : ils partent de textes qui fourmillent d’imprécisions et d’erreurs et de faits comme « Jérusalem est la capitale d’Israël » qui peuvent être controversés. L’intégration des connaissances de plusieurs sources est aussi délicate, comme l’est la vérification des connaissances obtenues. Tout cela met en jeu une gamme de techniques complexes, notamment les techniques de corroboration ou de crowdsourcing dont nous avons déjà parlées.

Et demain ? A coté des documents textuels, il faut s’attendre à voir proliférer des millions de bases de données ou de connaissances, de toutes tailles, de toutes natures, de qualités variables, et des liens entre elles. Le problème aura peut-être changé mais resteront les questions fondamentales : où trouver une information spécifique et quel site est fiable ?

Les services Web

La publication de connaissances permet de mieux répondre aux requêtes. Surtout, elle rend possible l’utilisation de la Toile par des machines. Prenons la requête très simple suivante : « qui a réalisé le film Manhattan ? ». Un utilisateur humain n’aura aucun mal à trouver la bonne réponse sur la Toile, par exemple en utilisant IMDb. Ce sera plus compliqué pour une machine. Par contre, un logiciel pourra dialoguer avec d’autres logiciels et comprendre des réponses comme :

( dbpedia:Woody_Allen, a_réalisé, film:Manhattan )

Nous appellerons services Web des logiciels connectés à Internet dialoguant avec d’autres logiciels, s’échangeant des données structurées suivant les protocoles de la Toile.

A la base de tout ça, nous trouvons des standards. Une anecdote nous permettra de souligner leur intérêt. Nous voulions utiliser un programme de classification de documents développé par des collègues. Pour pouvoir faire fonctionner ce logiciel, il fallait d’abord installer plusieurs librairies de programmes, certaines incompatibles avec notre environnement de développement. Le cauchemar habituel de l’installation de logiciel. Heureusement, quelqu’un a eu l’idée (pas si évidente au début des années 1990) d’utiliser le programme de classification comme service Web. Les collègues ont installé leur logiciel sur une machine connectée au réseau et quelques instants plus tard, nous pouvions utiliser le service. Sans les standards de la Toile, il nous aurait sans doute fallu des jours de travail frustrant et improductif.

Mais revenons à notre cinéphile. Il utilise un service, disons TMLF, pour TrouveMoiLeFilm. Notre cinéphile précise (en s’appuyant sur des ontologies) ce qu’il veut : voir le film Manhattan. TMLF cherche pour lui des offres de ce film en Vidéo à la Demande en utilisant les descriptions de services de la Toile (aussi basées sur des ontologies). TMLF compare les prix, les prestations de chaque service, en tenant compte des abonnements de la personne, de ses préférences, etc. Dans cette tâche, TMLF collabore avec d’autres services et échange avec eux des données, des connaissances. Et au final, TMLF peut démarrer le film sur la télé familiale. La Toile, qui était l’apanage de l’être humain, s’est ainsi mise au service de services de la Toile, et les services de la Toile au service de tous.

L’inférence

Comprendre le sens des données, répondre plus précisément aux requêtes, voilà des avantages apportés par les bases de connaissances. Mais le plus fascinant d’un point de vue technique est la possibilité de s’appuyer sur la logique pour inférer automatiquement de nouvelles connaissances. Pour expliquer cela, nous allons réexaminer la notion de fait. Nous avons rencontré jusqu’à présent des faits extensionnels, comme Séance(Star Wars, Sel, 22:15), qui correspondent à des n-uplets stockés dans la base de données. La base de données est donc dépositaire de tous les faits extensionnels du monde. Introduisons maintenant des connaissances sous forme de lois (de règles) comme :

SouhaiteVoir( Alice, t ) ¬ Film( t, Hitchcock, a ), not Vu( Alice, t )

que l’on peut lire « si t est le titre d’un film d’Hitchcock, a un acteur de ce film, et si Alice n’a pas vu ce film, alors elle souhaiterait le voir ». A partir de telles règles et de faits comme Psychose est un film d’Hitchcock et Alice ne l’a pas vu, nous allons pouvoir inférer un fait comme « Alice souhaiterait voir le film Psychose », un fait qui n’est stocké dans aucune base de données. Nous parlerons de faits intentionnels. C’est ce genre de règles toutes simples qui permet à des logiciels de raisonner.

Observez que répondre à une requête est devenu plus compliqué. Il faut maintenant inférer des faits qui permettent d’inférer d’autres faits, ainsi de suite. Evidemment, il faut éviter d’inférer tous les faits possibles, car cela demanderait trop de temps et trop d’espace mémoire ou de stockage. Parmi les plus beaux algorithmes du domaine, nous trouvons d’ailleurs des algorithmes inspirés de la programmation logique qui permettent d’éviter d’inférer des faits inutilement[41]. Nous n’aurons pas le temps de les décrire dans cette leçon.

Penser global

L’inférence est essentielle dans le cadre d’une Toile des connaissances en devenir, notamment pour mieux répondre aux requêtes ou pour intégrer de l’information provenant de sources hétérogènes. Nous pouvons imaginer demain des millions, des milliards de systèmes qui échangent des connaissances, infèrent des connaissances. Il faut pourtant raison garder. Il ne s’agit pas ici de raisonnements très compliqués comme par exemple ceux d’une démonstration mathématique, mais juste d’échanges d’information. Se posent pourtant d’énormes défis techniques : comment raisonner avec de pareils volumes de connaissances ? Comment ne pas être simplement submergés par les faits inférés ? Comment garantir la qualité des informations ? Leur confidentialité ? Comment expliquer les faits obtenus ?

Et puis notre environnement va changer. Il va nous falloir apprendre à vivre dans un monde où nous serons entourés de systèmes qui raisonnent, s‘échangent des connaissance, interagissent avec nous. Comment cela va-t-il modifier notre manière même de savoir, de penser ?

Conclusion

Where is the wisdom we have lost in knowledge? Where is the knowledge we have lost in information[42]?

T.S. Eliot

Le passage de biens concrets à des informations numériques relativement immatérielles permet de souligner une particularité fondamentale de l’informatique : l’informatique est une science de l’immatériel. En cela, elle diffère des sciences du matériel comme la physique, la chimie, les sciences de la vie et de la terre, par les techniques et souvent les mathématiques qu’elle utilise. Cela induit, pour l’industrie informatique, ses propres particularités tant pour la fabrication, la distribution ou la maintenance des produits que pour les modèles commerciaux. C’est cette immatérialité que nous avons rencontrée presqu’à chaque page de cette leçon.

La Toile est multiforme. Elle vit sur un Internet que nous souhaiterions le plus neutre[43] possible. Elle est omniprésente. Il est devenu quasi impossible de vivre sans : de trouver du travail, de travailler, de se loger, de gérer ses comptes bancaires, de faire partie d’une association, presque d’avoir des amis, etc. Nous sommes nombreux à partager la nostalgie du monde romantique, idéaliste, anarchiste, anarchique, de la Toile ouverte des débuts. La Toile évolue inexorablement vers des espaces plus fermés[44] notamment sous la pression de la monétarisation des contenus. Elle reste à la fois la plus belle des dentelles, tissu de toutes connaissances humaines et le terreau des plus horribles fantasmes, de toutes les violences. Elle est aussi l’univers d’une croissance arrogante dans ses imprécisions et ses incohérences qui noient les perles d’humanité et d’une alchimie improbable qui transforme la masse en qualité.

Ce que nous avons appris ces dernières années de la Toile, c’est qu’au-delà d’une collection universelle de documents, elle offrait une gamme infinie d’applications à inventer. Nous avons vu arriver le Web des téléphones « intelligents », que nous sommes nombreux à avoir adoptés avec enthousiasme tout en nous inquiétant de leurs aspects anxiogènes. Même s’il partage des protocoles informatiques avec la Toile classique, ce monde est souvent en contradiction avec la philosophie d’une Toile « libre, gratuite et universelle », les applications payantes devenant la norme. Nous avons parlé du Web des réseaux sociaux et du Web sémantique. Si nous avions eu plus de temps, nous aurions considéré le Web des objets et de l’intelligence ambiante qui a transformé le commerce avec les RFID (pour Radio-Frequency IDentification) et dont on nous promet qu’il va « révolutionner » notre habitat. Et nous assistons au fantastique succès du Web des mondes virtuels, notamment avec des jeux vidéo.

Si nous avons essayé d’éviter une présentation béatement optimiste des technologies de gestion de données, nous avons beaucoup insisté dans ce texte sur les succès technologiques notamment dans le contexte de la Toile. Nous évoquerons brièvement certains écueils, en essayant de mettre en évidence des sujets de recherche qu’ils suggèrent.

Eviter la noyade dans un océan de données

Cela a été un des fils conducteurs de ce texte. Un des grands défis des années à venir est de développer les technologies qui permettront de trouver, évaluer, valider, vérifier, hiérarchiser l’information pour aider l’internaute à obtenir « la bonne information, au bon moment ». Cela implique de poursuivre les recherches dans des domaines comme l’évaluation de la réputation, la recommandation, ou la personnalisation.

Accès à l’information pour tous

Des « fractures numériques » existent. La fracture générationnelle, grossièrement, entre ceux qui sont nés avant et après Internet, tend à disparaître avec des objets comme l’iPad. La fracture entre urbains et ruraux pourrait disparaître facilement avec un peu de volonté politique, les ruraux adoptant ces nouvelles technologies avec au moins autant d’appétit que les citadins. Les fractures sociales[45] et nord-sud sont autrement plus préoccupantes. L’informatique peut aider à les réduire avec des logiciels toujours plus simples à utiliser, des logiciels surtout libres. Mais il s’agit d’abord d’un problème d’éducation. En France, nous assistons à des progrès pour ce qui est de l’enseignement de l’informatique. Le chemin encore à parcourir reste considérable. Il faut aussi que la bibliothèque gratuite du coin de la rue cède la place à la bibliothèque numérique, gratuite et universelle de la Toile. L’utopie est devenue réalisable : l’accès pour tous à toute la culture et toutes les connaissances.

Démocratie ou pas

La Toile et les systèmes informatiques peuvent se mettre au service des gouvernants pour « fliquer » leurs citoyens, voire les opprimer. Ils peuvent aussi permettre d’établir une démocratie des contrepouvoirs avec des réseaux de militants qui contrôlent, surveillent, dénoncent, et notent les pouvoirs publics et, par là-même, qui contribuent à améliorer le fonctionnement de la démocratie. Les choix sont principalement politiques mais les scientifiques ont un rôle à jouer dans l’établissement de ces contrepouvoirs. Il s’agit en particulier de développer les technologies permettant de contrôler les puissants : les Etats, les multinationales.

Et la vie privée ?

Nous prenons de plus en plus conscience des risques que nous courrons à disperser sur la Toile des informations que nous voudrions garder confidentielles. L’un de ces risques les plus aigus est peut-être l’usurpation d’identité. C’est le rôle de la science de développer les outils qui nous permettent, en s’appuyant sur des lois qui protègent les données personnelles, de regagner le contrôle sur notre information. Il s’agit bien sûr pour les gouvernements de légiférer, mais il est important que nous nous accordions aussi sur une étique de la protection de la vie privée.

Pour des individus meilleurs ou pires ?

Est-ce que les outils informatiques nous rendent plus heureux ? Plus intelligents ? Plus productifs ? Le rapprochement des distances avec certains peut-il devenir la cause de l’éloignement des autres, au risque d’enfermer l’individu dans des communautés dévoreuses de son identité ? Au contact de toute cette virtualité, y-a-il un risque de perdre tout contact avec la « vraie » vie ? Est-ce qu’une rencontre est moins vraie sur la Toile qu’au bistrot du coin ? Et peut-être la mère de toutes les questions, allons-nous utiliser ces outils[46] pour ne plus penser ou, au contraire, pour mieux penser et être plus créatifs.

Les réponses à ces questions dépendent beaucoup des nouveaux outils informatiques qui restent à inventer, avec peut-être plus encore qu’avant, la préoccupation de mieux servir les utilisateurs, et pourquoi pas de les rendre meilleurs. D’un point de vue technique, un des défis est de pouvoir offrir à l’individu tous les avantages des systèmes de la Toile les plus avancés, notamment les réseaux sociaux ou les systèmes de recommandation, sans qu’il ait besoin d’aliéner le contrôle des informations qui le concernent, comme c’est trop le cas aujourd’hui. Un autre défi est d’améliorer la production collective de connaissances. Il faut aussi nous permettre de mieux utiliser toutes ces connaissances dans nos prises de décisions, en mieux les intégrant dans les outils logiciels que nous utilisons au quotidien comme le téléphone, le courrier ou l’agenda électronique.

Prediction is very difficult, especially about the future[47]. Niels Bohr

Et demain ?

Sous la pression de jeunes pousses très dynamiques et de jeunes géants comme Facebook ou Google, les technologies de la Toile se sont développées très rapidement. Comme souvent en informatique, des solutions vite fait mal fait ont été bricolées. Si le domaine de la gestion de données montre aujourd’hui un dynamisme étincelant, il tient pourtant encore de la forêt vierge quand nous atteignons la Toile : il est compliqué d’en dresser l’état de l’art ; il n’est pas simple de l’enseigner ; il n’est pas évident de prévoir quelles tendances sont là pour durer. Les bases logiques, qui faisaient la beauté du modèle relationnel, se présentent encore dans le désordre pour ce qui est de la Toile. Une solution globale est à inventer. Les liens avec la logique, la théorie de la complexité, la théorie des langages et des automates, sont à revisiter. De nouvelles théories sont sans doute à établir. Les systèmes que nous utilisons sont à améliorer ; de nouvelles fonctionnalités sont à inventer. Un vaste programme !

Il n’est pas possible, ni souhaitable, de renoncer à la Toile comme il n’a pas été possible de refuser l’écriture ou l’imprimerie. Et malgré tous les écueils de la Toile, je veux continuer à croire qu’elle participera à féconder un meilleur futur. Quant aux aspects plus techniques, je me hasarderai à prédire que la prochaine étape des sciences des données, que l’on retiendra, a déjà commencé : c’est la Toile des connaissances. Elle a déjà été annoncée plusieurs fois. Elle arrive lentement mais elle arrive vraiment.

Des données, à l’information, aux connaissances, le cheminement est naturel.

Remerciements. Nous tenons à remercier le Collège de France, l’INRIA ainsi que le Conseil de Recherche Européen, via le projet Webdam sur « Foundations of Web data Management ». Nous tenons aussi à remercier Martín Abadi, Jérémie Abiteboul, Manon Abiteboul, Gilles Dowek, Emmanuelle Fleury, Laurent Fribourg, Sophie Gamerman, Bernadette Goldstein, Florence Hachez-Leroy, Tova Milo, Marie-Christine Rousset, Luc Segoufin, Pierre Senellart et Victor Vianu pour leurs commentaires sur ce texte.

---

[1] Pourquoi et comment le monde devient numérique, leçon inaugurale au Collège de France, G. Berry. 2008.

[2] Penser, modéliser et maîtriser le calcul informatique, leçon inaugurale au Collège de France, G. Berry. 2010. La sécurité informatique, leçon inaugurale au Collège de France, M. Abadi. 2011.

[3] Nous entendons par langues naturelles des langues élaborées dans le temps par des groupes de locuteurs, comme le français ou l’anglais. Ceci est moins par opposition avec des langues « construites » comme l’espéranto qu’avec des langages formels comme la Logique du premier ordre, SQL ou Java.

[4] Écoute Dave. Je vois bien que tu es très affecté par tout cela. Et je pense vraiment que tu devrais reprendre tes esprits, prendre un calmant et essayer de faire le point.

[5] Définir précisément ces notions n’est pas chose facile. Voir par exemple, The Philosophy of Information, Luciano Floridi, Oxford University Press, 2011.

[6] Ses données persistent après que l’ordinateur soit éteint.

[7] Les évolutions suivantes ont été observées approximativement jusqu’à présent. Pour les capacités de stockage, la densité de mémoire pour les disques durs double chaque année (Loi de Kryder). Pour ce qui est des circuits, la densité de transistors sur une puce de silicium double tous les deux ans (Loi de Moore).

[8] De manière générale, quand une application est hébergée quelque part sur la Toile, nous parlerons d’informatique en nuages.

[9] Michael L. Brodie. www.michaelbrodie.com.

[10] La logique est le commencement de la sagesse, pas sa fin.

[11] Foundations of databases, S. Abiteboul, R. Hull, V. Vianu. Addison-Wesley. 1995. www.webdam.inria.fr/Alice

[12] Databases, M. Benedikt et P. Senellart, E. K. Blum et A. V. Aho, éditeurs, Computer Science. The Hardware, Software and Heart of It. Springer-Verlag, 2012.

[13] SQL va plus loin que le calcul relationnel. Par exemple, il permet d’ordonner les résultats et d’appliquer des fonctions simples comme la somme ou la moyenne.

[14] Pour ces complexités « faibles », le modèle de calcul précis est important. Nous parlons ici de calcul sur des machines RAM.

[15] Un exemple de problème difficile dans NP est celui du voyageur de commerce. Etant données des villes, des routes entre ces villes, et les longueurs de ces routes, trouver le plus court chemin pour relier toutes les villes.

[16] Comme il y a un nombre fini d’états possibles, il est possible de détecter si le programme est entré dans une boucle, mais au prix d’un travail supplémentaire.

[17] Generic Computation and Its Complexity, Serge Abiteboul, Victor Vianu, STOC 1991:209-219.

[18] Dans notre discussion, nous supposons que le domaine n’est pas ordonné. Le problème est différent si nous considérons que le domaine est ordonné. Vardi a montré qu’alors, fixpoint permet de calculer exactement toutes les requêtes dans P, et que while exprime exactement celles dans pspace.

[19] Servir et protéger les données.

[20] Les applications qui tournent sur le système relationnel contiennent des bogues. Le système lui-même contient ses propres bogues. Enfin les matériels peuvent dysfonctionner.

[21] Une grappe de serveurs ou une ferme de calcul (cluster en anglais) consiste en un regroupement d’ordinateurs, appelés nœuds, collaborant pour résoudre un problème particulier.

[22] The Anatomy of a Large-Scale Hypertextual Web Search Engine. S. Brin, L. Page. WWW Conference. 1998.

[23] Web data management, S. Abiteboul, I. Manolescu, P. Rigaux, M.-C. Rousset, P. Senellart, Cambridge University Press. 2011. www.webdam.inria.fr/Jorge.

[24] Google appelle ses centres de données, des fermes. Le nombre de fermes et le nombre de processeurs dans chaque ferme sont secrets. On parle de dizaines de fermes et des sources du début des années 2000 créditaient la plus grande ferme de 6000 processeurs.

[25] Ce problème fait partie de la classe AC0, c’est-à-dire la classe des problèmes que l’on peut résoudre avec des circuits de profondeur constante et un nombre de portes ET et OU polynomial dans la taille de l’entrée. L’évaluation de requêtes de l’algèbre relationnelle est d’ailleurs dans sa totalité dans AC0. 

[26] Playboy : La devise de votre société est vraiment « Ne faites pas le mal » ? Brin : Oui, c'est vrai. Playboy : Est-ce un code écrit ? Brin : Oui. Nous avons d'autres règles, aussi. Page : Nous acceptons les chiens, par exemple.

[27]Authoritative sources in a hyperlinked environment. J. Kleinberg. Journal of the ACM. 1999.

[28] Une matrice est creuse si la plupart de ses coefficients sont à zéro. Pour un milliard de pages, si chaque page a une trentaine de liens en moyenne, la matrice a environ 30 milliards d’entrées non vides sur un milliard de milliards d’entrées. Elle est très creuse. Mais même dans une représentation optimisée, elle reste gigantesque.

[29] Le PageRank de Google actuel utiliserait des dizaines de critères combinés dans une formule gardée secrète.

[30]Adaptive On-Line Page Importance Computation. S. Abiteboul, M. Preda, G. Cobena. WWW Conference. 2003.

[31] Voir www.le-tigre.net/Marc-L.html.

[32] Sagesse en réseaux : la passion d’évaluer. G. Origgi. www.laviedesidees.fr. 2008.

[33] Corroborating information from disagreeing views. A. Galland, S. Abiteboul, A. Marian, P. Senellart. International Conference on Web Search and Web Data Mining. 2010.

[34] Wikipédia existe en 281 éditions et sa version anglaise a plus de 3 millions d’articles en juin 2011 (selon Wikipédia).

[35] Les traductions trouvées sur la Toile, comme « externalisation ouverte », ne nous ont pas convaincus.

[36] Référence au Turc mécanique, un automate joueur d'échecs de la fin du 18^e siècle, en réalité un canular.

[37] Predicting protein structures with a multiplayer online game, Seth Cooper et al., Nature, 2010.

[38] Les masses sont les véritables héros.

[39] Mais de l'arbre de la connaissance du bien et du mal, tu n'en mangeras pas ; car, au jour que tu en mangeras, tu mourras certainement. Genèse 2:17.

[40] YAGO2: A Spatially and Temporally Enhanced Knowledge Base from Wikipedia, www.mpi-inf.mpg.de/yago-naga/yago/.

[41] Recursive Axioms in Deductive Databases, The Query/Subquery Approach. Laurent Vieille. Expert Database Conf. 1986:253-267.

[42] Où est la sagesse que nous avons perdue dans la connaissance ? Où est cette connaissance que nous avons perdue en information ?

[43] La neutralité du Net est le principe qui garantit l'égalité de traitement de tous les flux de données sur Internet. Ce principe exclut toute discrimination à l'égard de la source, de la destination ou du contenu de l'information transmise sur le réseau. [Wikipedia]

[44] The Web Is Dead. Long Live the Internet, Chris Anderson and Michael Wolff, Wired, 2010

[45] En France, en 2009, 40% de la population n'utilisait jamais l'informatique, CREDOC.

[46] Is Google making us Stoopid? The Atlantic. 2008.

[47] Il est difficile de faire des prévisions, surtout pour l’avenir.