.. _chap-bddoc:
   
###########################
Bases NoSQL (JSON): MongoDB
###########################

Nous allons consacrer ce chapitre à une base dite "documentaire" qui représente les données
au format JSON. Il s'agit de MongoDB, un des systèmes NoSQL les plus populaires du moment.
MongoDB est particulièrement apprécié pour sa capacité à passer en mode *distribué* pour
répartir le stockage et les traitements: nous verrons cela ultéieurement. Ce chapitre se
concentre sur MongoDB vu comme une base *centralisée* pour le stockage de documents JSON.

L'objectif est d'apprécier les capacités d'un système de ce type (donc, non relationnel)
pour les fonctionnalités standard attendues d'un système de gestion de bases de données. Comme nous
le verrons, MongoDB n'impose pas de schéma, ce qui peut être vu comme un avantage initialement,
mais s'avére rapidement pénalisant puisque la charge du contrôle des données
est reportée du côté de l'application; MongoDB propose un langage d'interrogation qui 
lui est propre (donc, non standardisé), pratique mais limité; enfin MongoDB n'offre aucun support
transactionnel. 

Les données utilisées en exemple ici sont celles de notre base de films, que 
vous pouvez récupérer sur le site du Webscope,  http://webscope.bdpedia.fr/index.php?ctrl=xml.
Choisissez bien entendu les exports en JSON. Si vous disposez de documents JSON plus proches
de vos intérêts,
vous êtes bien entendu invités à les prendre comme base d'essai.

*******************************
S1: installation, mise en route
*******************************

MongoDB est un système libre de droits (pour sa version de base), téléchargeable à http://www.mongodb.org/downloads.

Installation de MongoDB
=======================

Si le système n'est pas déjà installé, téléchargez la version correspondant à votre système
d'exploitation, et décompressez l'archive récupérée. Vous obtenez un répertoire nommé ``mongo``, agrémenté
du numéro de version et autres indicateurs. Nous le désignerons par ``mongodir`` pour faire simple: 
vous devriez ajouter ``mongodir/bin`` dans la variable d'environnement ``PATH``. Par exemple,
si vous utilisez le *bash shell*:

.. code-block:: bash

    export MONGO_HOME=/usr/local/mongo2.6
    export PATH=$PATH:$MONGO_HOME/bin

MongoDB fonctionne en mode classique client/serveur. Pour lancer le serveur, exécutez simplement 
la commande ``mongod`` qui se trouve dans ``bin``, et c'est tout. Ce qui donne, sous un système Unix, à partir du
répertoire courant ``mongodir``:

.. code-block:: bash

   bin/mongod &

Ou tout simplement ``mongod`` si le répertoire ``bin``  est dans votre ``PATH``, comme recommandé. 
Si tout se passe bien, le démarrage du serveur se concrétise pas des messages divers
se terminant par::

   [initandlisten] waiting for connections on port 27017

Le serveur ``mongod`` est donc en attente sur le port 27017. Maintenant, il nous faut une
application cliente.

Clients MongoDB
===============

Il s'agit bien des *applications* clientes. Nous avons en gros deux possibilités: l'interpréteur de commande
``mongo`` ou une application graphique plus agréable à utiliser. Parmi ces dernières, deux choix
recommandables sont ``RockMongo``, une application Web d'administration de MongoDB à peu près
équivalente à phpMyAdmin, et RoboMongo, plus facile d'installation. 

Le client ``mongo``
~~~~~~~~~~~~~~~~~~~

L'interpréteur de commande se lance
comme suit:

.. code-block:: bash

   $ mongo
     MongoDB shell version: 2.4.7
     connecting to: test
     > 

La base par défaut est ``test``. Cet outil est en fait un interpréteur javascript (ce qui est cohérent
avec la représentation JSON) et on peut donc lui soumettre des instructions en Javascript, ainsi que
des commandes propres à MongoDB. Voici quelques instructions de base.

  * Pour se placer dans une base::
  
      use <nombase>
    
  * Une base est constituée d'un ensemble de *collections*, l'équivalent d'une table en relationnel. Pour créer
    une collection::
    
      db.createCollection("movies")
       
  * La liste des collections est obtenue par::
  
      show collections
      
  * Pour insérer un document JSON dans une collection (ici, *movies*)::
  
      db.movies.insert ({"nom": "nfe024"})
     
    Il existe donc un objet (javascript) implicite, ``db``, auquel on soumet des demandes d'exécution de certaines méthodes.
    
  * Pour afficher le contenu d'une collection::
  
      db.movies.find()
     
    C'est un premier exemple d'une fonction de recherche avec MongoDB. On obtient des objets (javascript, encodés en JSON)
    
    .. code-block:: javascript
    
         { "_id" : ObjectId("5422d9095ae45806a0e66474"), "nom" : "nfe024" }
    
    MongoDB associe un identifiant unique à chaque document, de nom conventionnel ``_id``, et lui attribue
    une valeur si elle n'est pas indiquée explicitement. 
    
  * Pour insérer un autre document::
  
      db.movies.insert ({"produit": "Grulband", prix: 230, enStock: true})  
      
    Vous remarquerez que la structure de ce document n'a rien à voir avec le précédent: *il n'y a pas
    de schéma (et donc pas de contrainte) dans MongoDB*. On est libre de tout faire (et même de faire
    n'importe quoi). Nous sommes partis pour mettre n'importe quel objet dans notre collection ``movies``,
    ce qui revient à reporter les problèmes (contrôles, contraintes, tests sur la structure) vers l'application.
   
  * On peut affecter un identifiant *explicitement*::
    
      db.movies.insert ({_id: "1", "produit": "Kramölk", prix: 10, enStock: true})
      
  * On peut compter le nombre de documents dans la collection::
   
      db.movies.count()
   
  * Et finalement, on peut supprimer une collection::
  
     db.movies.drop()
     
C'est un bref aperçu des commandes.  On peut se lasser au bout d'un certain temps d'entrer
des commandes à la main, et préferer utiliser une interface grahique. Il n'existe
pas d'interface *native* fournie par 10gen, l'entreprise qui développe MongoDB, 
mais on trouve beaucoup d'outils en Open Source (cf. la liste http://docs.mongodb.org/ecosystem/tools/administration-interfaces/).

Le client ``RoboMongo``
~~~~~~~~~~~~~~~~~~~~~~~

RoboMongo est un client graphique disponible pour toutes les plate-formes à ``robomongo.org``. C'est
sans doute le choix à privilégier. l'installation est très simple, l'outil semble assez complet et en
évolution rapide. La figure :ref:`robomongo`  montre l'interface en action.

   .. _robomongo:
   .. figure:: ../figures/RoboMongo.png
      :width: 80%
      :align: center
   
      L'interface RoboMongo
      
      
Le client ``RockMongo``
~~~~~~~~~~~~~~~~~~~~~~~~
   
C'est une application PHP disponible ici: http://www.rockmongo.com. Il vous faut
donc un serveur Apache/PHP, probablement déjà disponible sur votre machine. Si ce n'est
pas le cas, c'est tellement standard que vous devriez pouvoir l'installer en 2 clics.

Il est nécessaire d'installer l'extension PHP de connexion à MongoDB. La méthode varie selon
votre système: la page http://rockmongo.com/wiki/installation donne les indications nécessaires.

En ce qui concerne RockMongo, récupérez la dernière version sur le site ci-dessus, installez-là
dans votre répertoire ``htdocs``, et laissez la configuration par défaut. En accédant à
``http://localhost/rockmongo`` (en supposant que ``rockmongo`` soit le nom du répertoire
dans ``htdocs``), vous devriez accéder à une fenêtre de connexion. Le compte par
défaut est ``admin`` / ``admin``. Une fois connecté, l'affichage devrait ressembler
à celui de la figure :ref:`rockmongo`.

   .. _rockmongo:
   .. figure:: ../figures/rockmongo.png
      :width: 80%
      :align: center
   
      L'interface RockMongo
      
.. Important:: Ce qui précède est valable pour une installation sur une machine locale, avec 
   un serveur ``mongod`` en local également.
   
L'interface ressemble à celle de phpMyAdmin, pour ceux qui connaissent. En particulier, 
la barre à gauche montre la liste des bases de données existantes, 

Création de notre base
======================

Nous allons insérer des documents plus sérieux pour découvrir les fonctionnalités de MongoDB. Notre
base de films nous fournit des documents JSON, comme celui-ci par exemple:

.. code-block:: javascript

    {
      "_id": "movie:100",
      "title": "The Social network", 
      "summary": "On a fall night in 2003, Harvard undergrad and 
         programming genius Mark Zuckerberg sits down at his  
         computer and heatedly begins working on a new idea. (...)",
      "year": 2010, 
      "director": {"last_name": "Fincher",
                    "first_name": "David"},
      "actors": [ 
        {"first_name": "Jesse", "last_name": "Eisenberg"}, 
        {"first_name": "Rooney", "last_name": "Mara"}
       ]
    }

Comme il serait fastidieux de les insérer un par un, nous allons utiliser l'utilitaire
d'import de MongoDB. Il prend en entrée un tableau JSON contenant la liste des objets
à insérer. Dans notre cas, nous allons utiliser l'export JSON de la base Webscope
dont le format est le suivant.

.. code-block:: javascript

    [
     {
      "_id": "movie:1",
      "title": "Vertigo",
      "year": "1958",
      "director": 	{
	    "_id": "artist:3",
	    "last_name": "Hitchcock",
	    "first_name": "Alfred",
	    "birth_date": "1899"	
	  },
      "actors": [
	   {
	    "_id": "artist:15",
	    "first_name": "James",
	    "last_name": "Stewart",
	   },
	   {
	    "_id": "artist:16",
	    "first_name": "Kim",
	    "last_name": "Novak",
	   }
	  ]
    },
    {
      "_id": "movie:2",
      "title": "Alien",  
      ...
    }
  ]
  
En supposant que ce tableau est sauvegardé dans ``movies.json``, on peut l'importer
dans la collection ``movies`` de la base ``nfe204`` avec la commande suivante:

.. code-block:: bash

    mongoimport -d nfe204 -c movies --file movies.json --jsonArray   
    
Ne pas oublier l'argument ``jsonArray`` qui indique à l'utilitaire d'import qu'il s'agit d'un tableau
d'objets à créer individuellement, et pas d'un unique document JSON.

Exercices
=========

.. admonition:: Exercice: mise en route de MongoDB

   Votre tâche est simple: installer MongoDB, le client RockMongo ou RoboMongo  (ou un autre de votre choix), 
   reproduire les commandes ci-dessus et créer une base ``movies`` avec nos films.
   Profitez-en pour vous familiariser avec l'interface graphique.
   
   Vous pouvez également créer une base ``moviesref`` avec deux collections: une pour les films
   et l'autre pour les artistes, les premiers référençant les seconds. Les commandes
   d'import devraient être les suivantes:
     
   .. code-block:: bash
   
       mongoimport -d moviesref -c movies --file movies-refs.json --jsonArray 
       mongoimport -d moviesref -c artists --file artists.json --jsonArray

*************************
S2: requêtes avec MongoDB
*************************


Supports complémentaires:

  * `Présentation: requêtes MongoDB  <http://b3d.bdpedia.fr/files/slmongodb.pdf>`_
  * Vidéo: à venir
  
  
Précisons tout d'abord que le langage de requête sur des collections est spécifique à MongoDB. Essentiellement,
c'est un langage de recherche dit "par motif" (*pattern*). 
Il consiste à interroger *une* collection en donnant un  objet (le "motif/*pattern*", en JSON) dont chaque 
attribut est interprété comme une contrainte sur la
structure des objets à rechercher. 
Voici des exemples, plus parlants que de longues explications. Nous travaillons sur la
base contenant les films complets, sans référence (donc, celle nommée ``nfe204`` 
si vous avez suivi les instructions précédentes).

Sélections
==========

Commençons par la base: on veut parcourir toute une collection. On utilise
alors ``find()``  dans argument.

.. code-block:: javascript

    db.movies.find ()

Si'il y a des millions de documents, cela risque de prendre du temps... D'ailleurs,
comment savoir combien de documents comprend le résultat?

.. code-block:: javascript

    db.movies.count ()

Comme en SQL (étendu),
les options ``skip`` et ``limit`` permettent de "paginer" le résultat. La requête
suivante affiche 12 documents à partir du dixième inclus.

.. code-block:: javascript

    db.movies.find ().skip(9).limit(12)

Implicitement, cela suppose qu'il existe un ordre sur le parcours des documents. Par défaut,
cet ordre est dicté par le stockage physique: MongoDB fournit les documents dans l'ordre
où il les trouve (dans les fichiers). On peut trier explicitement, ce qui rend
le résultat plus déterministe. La requête suivante trie les documents sur le titre du film,
puis pagine le résultat.

.. code-block:: javascript

    db.movies.find ().sort({"title": 1}).skip(9).limit(12)

La spécification du tri repose sur un objet JSON, et ne prend en compte que les
noms d'attribut sur lesquels s'effectue le tri.  La valeur (ici, celle du titre)
ne sert qu'à indiquer si on trie de manière ascendante (valeur 1) ou descendante (valeur -1).

Attention, trier n'est pas anodin. En particulier, tout tri implique que le
système constitue l'intégralité du résultat au préalable, ce qui induit
une latence (temps de réponse) potentiellement élevée. Sans tri, le système
peut délivrer les documents au fur et à mesure qu'il les trouve. 

Critères de recherche
~~~~~~~~~~~~~~~~~~~~~

Si on connaît l'identifiant, on effectue la recherche ainsi.

.. code-block:: javascript

    db.movies.find ({"_id": "movie:2"})

Une requête sur l'identifiant ramène (au plus) un seul document. Dans un tel cas, on
peut utiliser ``findOne``.

.. code-block:: javascript

    db.movies.findOne ({"_id": "movie:2"})

Cette fonction renvoie toujours *un* document (au plus), alors que la fonction ``find`` renvoie
un *curseur* sur un ensemble de documents (même si c'est un singleton). La différence est
surtout importante quand on utilise une API pour accéder à MongoDB avec un
langage de programmation.

Sur le même modèle, on peut interroger n'importe quel attribut.

.. code-block:: javascript

    db.movies.find ({"title": "Alien"})
    
Ca marche bien pour des attributs atomiques (une seule valeur), mais comment faire pour interroger
des objets ou des tableaux imbriqués? On utilise dans ce cas des chemins, un peu à la XPath,
mais avec une syntaxe plus "orienté-objet". Voici comment on recherche les films
de Quentin Tarantino.

.. code-block:: javascript

     db.movies.find ({"director.last_name": "Tarantino"})
     
Et pour les acteurs, qui sont eux-mêmes dans un tableau? Ca fonctionne de la même manière.

.. code-block:: javascript

     db.movies.find ({"actors.last_name": "Tarantino"})
     
La requête s'interprète donc comme: "Tous les films dont *l'un* des acteurs se nomme Tarantino".

Conformément aux principes du semi-structuré, on accepte sans protester la référence à des attributs
ou des chemins qui n'existent pas. En fait, dire "ce chemin n'existe pas" n'a pas grand sens 
puisqu'il n'y a pas de schéma, pas de contrainte sur la structure des objets, et que donc
tout chemin existe potentiellement: il suffit de le créer. La requête suivante ne ramène rien,
mais ne génére pas d'erreur.

.. code-block:: javascript

     db.movies.find ({"actor.last_name": "Tarantino"})

.. important:: 
     Contrairement à une base relationnelle, une base semi-structurée ne proteste pas quand
     on fait une faute de frappe sur des noms d'attributs.
     
Quelques raffinements permettent de dépasser la limite sur le prédicat *d'égalité*  implicitement
utilisé ici pour comparer les critères donnés et les objets de la base. Pour les chaînes
de caractères, on peut introduire des expressions régulières. Tous les films dont
le titre commence par ``Re``? Voici:

.. code-block:: javascript

    db.movies.find ({"title": /^Re/}, {"actors": null, "summary": 0} )
    
Pas d'apostrophes autour de l'expression régulière. On peut aussi effectuer des recherches par intervalle.

.. code-block:: javascript

    db.movies.find( {"year": { $gte: "2000", $lte: "2005" } }, {"title": 1} )

.. important: Il n'y a pas de schéma, et donc les attributs ne sont pas *typés*. Ici,
   l'année des films est représentée par une *chaîne de caractères* dans nos objets JSON,
   et il faut donc faire la comparaison avec des chaînes de caractères. Rien ne nous l'indique,
   et aucun contrôle n'est (et ne peut) être effectué.   
   
Projections
~~~~~~~~~~~

Jusqu'à présent, les requêtes ramènent l'intégralité des objets satisfaisant les critères de recherche. On
peut aussi faire des *projections*, en passant un second argument à la fonction *find()*.

.. code-block:: javascript

     db.movies.find ({"actors.last_name": "Tarantino"}, {"title": true, "actors": 'j'} )

Le second argument est un objet JSON dont les attributs sont ceux à conserver dans le résultat. La valeur
des attributs dans cet objet-projection ne prend que deux interprétations. Toute valeur autre que 0 ou ``null``
indique que l'attribut doit être conservé. Si on choisit au contraire d'indiquer les attributs à *exclure*,
on leur donne la valeur 0 ou ``null``. Par exemple, la requête suivante retourne les films sans les acteurs
et sans le résumé.

.. code-block:: javascript

    db.movies.find ({"actors.last_name": "Tarantino"}, {"actors": null, "summary": 0}) 
    

Opérateurs ensemblistes
~~~~~~~~~~~~~~~~~~~~~~~

Les opérateurs du langage SQL ``in``, ``not in``, ``any`` et ``all`` se retrouvent
dans le langage d'interrogation. La différence, notable, est que SQL applique
ces opérateurs à des *relations* (elles-mêmes obtenues par des requêtes)
alors que dans le cas de MongoDB, ce sont des tableaux JSON. MongoDB ne
permet pas d'imbriquer des requêtes.

Voici un premier exemple: on cherche les films dans
lesquels joue au moins un des artistes 
dans une liste (on suppose que l'on connaît l'identifiant).

.. code-block:: javascript

    db.artists.find({"actors._id": {$in: ["artist:34","artist:98","artist:1"]}})

Gardez cette recherche en mémoire: elle s'avèrera utile pour contourner
l'absence de jointure en MongoDB. Le ``in`` exprime le fait que *l'une*
des valeurs du premier tableau (``actors._id``) 
doit être égale à l'une des valeurs de l'autre. Il correspond
implicitement, en SQL, à la clause ``ANY``. Pour exprimer le fait que 
*toutes* les valeurs de premier tableau se retrouvent dans le second
(en d'autres termes, une inclusion), on utilise la clause ``all``.

.. code-block:: javascript

    db.movies.find({"actors._id": {$all: ["artist:23","artist:147"]}})

Le ``not in`` correspond à l'opérateur ``$nin``. 

.. code-block:: javascript

    db.artists.find({"_id": {$nin: ["artist:34","artist:98","artist:1"]}})

Comment trouver les films qui n'ont pas d'attribut ``summary``? 

.. code-block:: javascript

    db.movies.find({"summary": {$exists: false}}, {"title": 1})

Opérateurs Booléens
~~~~~~~~~~~~~~~~~~~

Par défaut, quand on exprime plusieurs critères, c'est une conjonction (``and``)
qui est appliquée. On peut l'indiquer explicitement. Voici la syntaxe
(les films tournés avec Leonardo DiCaprio en 1997):

.. code-block:: javascript

    db.movies.find({$and : [{"year": "1997"}, {actors.last_name: "DiCaprio"]} )
    
L'opérateur ``and`` s'applique à un tableau de conditions. Bien entendu il
existe un opérateur ``or``  avec la même syntaxe. Les films
parus en 1997 *ou* avec Leonardo DiCaprio.

.. code-block:: javascript

    db.movies.find({$or : [{"year": "1997"}, {actors.last_name: "DiCaprio"]} )

Voici pour l'essentiel en ce qui concerne les recherches portant sur *une* collection
et consistant à sélectionner des documents. Grosso modo, on obtient
la même expressivité que pour SQL dans ce cas. Que faire quand on
doit croiser des informations présentes dans *plusieurs* collections? En relationnel,
on effectue des jointures. Avec Mongo, il faut bricoler.
    
Jointures
=========

La jointure, au sens de: associer des objets *distincts*, provenant en général de *plusieurs*
collections, pour appliquer des critères de recherche croisés, 
n'existe pas en MongoDB. C'est une limitation
très importante du point de vue de la gestion de données. On peut considérer qu'elle est cohérente
avec une approche documentaire dans laquelle les documents sont supposés indépendants les uns des autres,
avec une description interne suffisamment riche pour que toute recherche porte sur le 
contenu du document lui-même. Cela étant, on peut imaginer toutes sortes de situations où
une jointure est nécessaire dans une aplication de traitement de données. 

Le serveur ne sachant pas effectuer de jointures, on en est réduit à les faire côté client,
comme illustré sur la figure :ref:`jointure-serveur-client`. Cela
revient essentiellement à appliquer l'algorithme de jointures par boucle imbriquées en stockant
des données temporaires dans des structures de données sur le client, et en effectuant des échanges
réseaux entre le client et le serveur, ce qui dans l'ensemble est inefficace. 


.. _jointure-serveur-client:
.. figure:: ../figures/jointure-serveur-client.png
      :width: 80%
      :align: center
   
      Jointure côté serveur et côté client
      
Comme l'interpréteur ``mongo`` permet de programmer en Javascript, nous pouvons en fait
illustrer la méthode assez simplement. Considérons la requête: "Donnez tous les films dont
le directeur est Clint Eastwood". 

.. note:: Nous travaillons sur la base ``moviesref`` dans laquelle
  un film ne contient que la *référence* au metteur en scène, ce qui évite les redondances, mais complique
  la reconstitution de l'information.

La première étape dans la jointure côté client consiste à chercher l'artiste Clint Eastwood
et à le stocker dans l'espace mémoire du client (dans une variable, pour dire les choses simplement).

.. code-block:: javascript

    eastwood = db.artists.findOne({"first_name": "Clint", "last_name": "Eastwood"})

On dispose maintenant d'un objet ``eastwood``. Une seconde requête va récupérer les films
dirigés par cet artiste.

.. code-block:: javascript

    db.movies.find({"director._id": eastwood['_id']}, {"title": 1})

Voilà le principe. Voyons maintenant plus généralement comment on effectue
l'équivalent des jointures en SQL. Prenons la requête suivante:

.. code-block:: sql

   select m.titre, a.*  from Movie m, Artist a
   where m.id_director = a.id
   
On veut donc les titres des films et le réalisateur. On va devoir coder, *du côté
client*, un algorithme de jointure par boucles imbriquées. Le voici, sous
le shell de MongoDB (et donc en programmation javascript).

.. code-block:: javascript

    var lesFilms = db.movies.find()
    while (lesFilms.hasNext()) {
      var film = lesFilms.next();
      var mes = db.artists.findOne({"_id": film.director._id});
      printjson(film.title);
      printjson(mes);
    }

On a donc une boucle, et une requête imbriquée, exécutée autant de fois qu'il y a de films.
C'est exactement la méthode qui serait utilisée
*par le serveur* si ce dernier implantait les jointures. L'exécuter du côté
client induit un surcoût en programmation, et en échanges réseau entre le client
et le serveur.

Exercices
=========


.. admonition:: Exercice: requêtes sur la base des films. 

   Sur votre base ``movies``, 
  
            * tous les titres;
            * tous les titres des films parus après 2000;
            * le résumé de Spider-Man;                       
            * qui est le metteur en scène de *Gladiator*?
            * titre des films avec Kirsten Dunst;
            * quels films ont un résumé?
            * les films qui ne sont ni des drames ni des comédies.
            * affichez les titres des films et les noms des acteurs.
            * dans quels films Clint Eastwood est-il acteur mais pas réalisateur (aide: utilisez
              l'opérateur de comparaison ``$ne``).
            * **Difficile**: Comment chercher les films dont le metteur en scène est *aussi* un acteur?            
              Pas sûr que ce soit possible sans recourir à une auto-jointure, côté client... 
                       
   .. ifconfig:: mongoquery in ('public')

      .. admonition:: Correction
 
          Correction        
            
            * ``db.movies.find({}, {"title": 1})``
            * ``db.movies.find({"year": {$gt: "2000"}}, {"title": 1, "year": 1})``
            * ``db.movies.find({"title": "Spider-Man"}, {"summary": 1})``
            * ``db.movies.find({"title": "Gladiator"}, {"director": 1})``
            * ``db.movies.find({"actors.last_name": "Dunst"}, {"title": 1})``
            * ``db.movies.find({"summary": {$exists: true}}, {"title": 1})``
            * ``db.movies.find({"genre": {$nin: ["Drame", "Comédie"]}}, {"title": 1, "genre": 1})``
            * ``db.movies.find({}, {"title": 1, "actors.first_name": 1, "actors.last_name": 1})``
            * ``db.movies.find({"actors.last_name": "Eastwood", "director.last_name": {$ne: "Eastwood"}}, {"title": 1})``
            
            
.. admonition:: Exercice: requêtes sur votre base

   Si vous avez constitué une base de documents JSON (bureautique, météo, données
   géolocalisées Google), je vous encourage à l'importer dans MongoDB et à
   tester des requêtes qui vous semblent typique d'une application basée
   sur ces données. 
      
        
************************
S3: MapReduce et MongoDB
************************


Supports complémentaires:

  * `Présentation: MapReduce et MongoDB  <http://b3d.bdpedia.fr/files/slmongomr.pdf>`_
  * Vidéo: à venir
  
  
Les requêtes vues jusqu'à présent prennent en entrée *une* collection et produisent en sortie
un sous-ensemble des documents de la collection, eux-même éventuellement
"réduits" par une projection.

Nous abordons maintenant un processus plus  complet pour le traitement d'une collection,
que nous allons appeler *chaîne de traitement* par traduction de "*data processing pipelines*".
Le principe général est de soumettre chaque document d'une collection 
à une séquence d'opérations, comme par exemple:

  * un *filtrage*, en ne gardant le document que s'il satisfait certains critères; 
  * une *restructuration*, en changeant la forme du document;
  * une *annotation*, par ajout au document de propriétés calculées;
  * un *regroupement* avec d'autres documents sur certains critères;
  * des *opérations d'agrégation* sur des groupes de documents.
  
Une chaîne de traitement permet *entre autres* de calculer des agrégations, comme
le ``group by`` de SQL.  Leur pouvoir d'expression va au-delà, notamment
par la possibilité d'ajouter en cours de route des attributs calculés, ou
de changer complètement la structure des informations manipulées. Enfin,
et c'est essentiel, ces chaînes sont conçues pour pouvoir s'exécuter
dans un environnement distribué, avec un effet de passage à l'échelle
obtenu par la parallélisation. Ce dernier aspect sera abordé ultérieurement.

La spécification d'une chaîne de traitement s'appuie sur un paradigme 
nommé MapReduce que nous rencontrerons de manière récurrente. 
Nous nous en tenons au contexte centralisé (un seul serveur) dans ce qui suit,
ce qui permet d'introduire les concepts sans les surcharger.

MapReduce: le principe
======================

Le principe est ancien et provient de la programmation fonctionnelle. Il se résume
ainsi: étant donné une collection d'items (ça peut être n'importe quoi -- pour
nous ce sera des documents), on va appliquer un traitement en deux phases:

  * dans la première phase (*map*), une fonction :math:`F_{map}` est appliquée à chaque 
    item de la collection, et produit une valeur placée dans un *accumulateur* (une
    zone mémoire);
  * dans une seconde phase, les valeurs placées dans l'accumulateur sont traitées
    par  une fonction d'agrégation (*reduce*)  :math:`F_{red}`, produisant une valeur finale.
    
Un exemple très simple est le *count()*: durant la phase de *map* on produit
la valeur 1 que l'on place dans l'accumumateur; durant la phase de *reduce*
on fait la somme: le résultat est le nombre d'items. En SQL, cela donnerait

.. code-block:: sql

   select count(*) from Collection 
   
Un premier raffinement consister à *partitionner* les valeurs produites
par le *map* en plusieurs groupes. Il suffit de modifier la fonction 
:math:`F_{map}` pour qu'elle produise non plus une valeur, mais
une paire *(k, v)*, où *k* est l'identifiant du groupe et
*v* la valeur à placer dans le groupe. L'identifiant du groupe
est déterminé à partir de l'item traité. Si, par exemple, l'item
a un attribut *année*, on peut créer un groupe par année en produisant
la paire *(année, item)* avec :math:`F_{map}`. Avec ce raffinement,
la fonction :math:`F_{red}` s'applique à chaque groupe. Si c'est
la fonction *count()* par exemple, on obtient l'équivalent de la requête SQL suivante.

.. code-block:: sql

   select count(*) from Collection group by annee 

Second raffinement: au lieu de produire *une* valeur pour *un* item,
la fonction   :math:`F_{map}` peut "émettre" 0, 1 ou plusieurs valeurs.
Par exemple, si l'item en entrée est un texte,  :math:`F_{map}` peut
émettre une paire (clé, valeur) pour chaque terme rencontré dans le texte,
la valeur étant un indicateur comme, par exemple, le nombre d'occurrences
du terme. Cette fois il n'y a plus d'équivalent SQL: MapReduce 
s'apparente au *group by* dans le mécanisme de calcul, mais
la possibilité d'appliquer des fonctions quelconques, et 
celle de restructurer complètement les données pendant la phase de *map*,
le rendent beaucoup plus puissant.

Un traitement MapReduce repose sur la notion de *fonction de second ordre*.
Pas de panique: cela signifie simplement que l'environnement
(*framework*) fournit deux fonctions, *map()* et *reduce()*, qui prennent
chacune en entrée, respectivement, les fonctions  :math:`F_{map}`
et :math:`F_{red}` mentionnées ci-dessus. Ce sont des fonctions qui 
prennent en argument d'autres fonctions et les appliquent aux données,
d'où la notion de "second-ordre".

.. note:: Pour votre culture: la caractérisation d'un *framework* (du moins
   quand on est attaché à utiliser un vocabulaire précis) est justement celle d'un environnement
   basé sur un modèle d'exécution pré-défini. Ce modèle applique des fonctions fournies
   par le développeur qui n'est donc pas en charge du *contrôle* (pris en charge par
   le framework) mais de la *spécification*. On parle *d'inversion de contrôle*,
   et un exemple typique est fourni par les *frameworks* MVC. Fin de la parenthèse.
   
Résumons avec la figure :ref:`mapreduce-mongo`, et plaçons-nous
maintenant dans le cadre de nos bases documentaires. Nous avons
une collection de documents :math:`d_1, d_2, \cdots, d_n`. La fonction
:math:`F_{map}` produit, de manière générale, des documents :math:`dj_i`
(notez les doubles flêches: un  document en entrée peut engendrer plusieurs
documents en sortie du *map*) et les place dans un groupe :math:`G_j, j \in [1, k]`. Quand
la phase de *map* est terminée (et pas avant!), on peut passer
à la phase de *reduce* qui applique successivement :math:`F_{red}`
aux documents de chaque groupe. On obtient, pour chaque groupe,
une valeur (un document de manière générale) :math:`v_j`.  

.. _mapreduce-mongo:

.. figure:: ../figures/mapreduce-mongo.png
      :width: 80%
      :align: center
   
      MapReduce (en centralisé)

Voici pour la théorie. En complément, notons dès maintenant
que ce mécanisme a une double propriété extrêmement intéressante:

  * il est très *générique*,
  * il se *parallélise* très facilement. 
  
Pour ce dernier aspect,
il est important que chaque document soit traité *indépendamment* du contexte. Concrètement,
l'application de :math:`F_{map}` à un document *d* doit donner un résultat qui
ne dépend ni de la position de *d* dans la collection, ni de ce qui s'est passé
avant ou après dans la chaîne de traitement, ni de la machine ou du système, etc. 
En pratique, cela signifie que
la fonction :math:`F_{map}` ne conserve pas un *état* qui pourrait varier et influer
sur le résultat produit quand elle est appliquée à *d*. 

Si cette propriété n'était
pas respectée, on ne pourrait pas paralléliser et conserver un résultat invariant.
Si :math:`F_{map}` dépendait par exemple du système d'exploitation, de l'heure,
ou de n'importe quelle variable extérieure au document traité (un *état*),
l'exécution en parallèle aboutirait à des résultats non déterministes.

Passons à la pratique, en restant dans un contexte centralisé.

Un premier exemple
==================

Nous allons produire un document par réalisateur, avec la liste
des films qu'il/elle a réalisé. Conceptuellement, nous créons
un groupe par réalisateur, plaçons dans ce groupe les films
pendant la phase de *map* et construisons le document final dans la phase
de *reduce*. 

La spécification consiste à définir les deux fonctions
à appliquer (:math:`F_{map}` et :math:`F_{red}`).
Voici la fonction de *map*.

.. code-block:: javascript

    var mapRealisateur = function() {
                  emit(this.director._id, this.title);
          };
          
En javascript, les fonctions peuvent se stocker dans des variables. 
L'instruction ``emit`` produit une paire (clé, valeur), constituée
ici de l'identifiant du réalisateur, et du titre du film. Notez
que la fonction ne prend aucun argument: implictement, elle
dispose comme contexte du document auquel elle s'applique,
désigné par ``this``. Et c'est tout.

Voici la fonction de *reduce*.

.. code-block:: javascript
          
   var reduceRealisateur = function(directorId, titres) {
      var res = new Object();
      res.director = directorId;
      res.films = titres;
      return res;
    };

Une fonction de *reduce* prend deux arguments: l'identifiant du groupe auquel elle
s'applique (ici, ``directorId``) et la liste (un tableau en javascript)
des valeurs produites par le *map*.

Dans notre exemple, nous construisons la valeur de résultat comme
un objet ``res`` auquel on affecte deux propriétés: ``director`` 
et ``titres``.

Il ne reste plus qu'à lancer un traitement, avec la fonction ``mapReduce``
sur la collection ``movies``. Voici la syntaxe.

.. code-block:: javascript
          
    db.movies.mapReduce(mapRealisateur,  reduceRealisateur, {out: {"inline": 1}} )

Le premier paramètre est la fonction de *map*, le second la fonction de *reduce*,
et le troisième indique la sortie, ici l'écran.

À ce stade vous brûlez sans doute d'envie de tester cette exécution. Allez-y: vous
devriez obtenir, pour chaque groupe, un résultat de la forme suivante.

.. code-block:: javascript

		{
			"_id" : "artist:3",
			"value" : {
				"director" : "artist:3",
				"films" : [
					"Vertigo",
					"Psychose",
					"Les oiseaux",
					"Pas de printemps pour Marnie",
					"Fenêtre sur cour",
					"La mort aux trousses"
				]
			}
		}
    
Devinez de quel réalisateur il s'agit? Ici, ça se devine (?), mais en général on
aimerait bien disposer au moins du nom. Reportez-vous aux exercices.

MongoDB propose plusieurs options pour l'exécution d'un traitement
MapReduce. La plus utile (et la plus générale, présente dans tous
les systèmes) consiste à prendre en entrée non pas une collection
entière, mais le résultat d'une requête. On passe pour cela un objet
``query`` dans le document-paramètre en troisième position. Voici
un exemple. 

.. code-block:: javascript

    db.movies.mapReduce(mapRealisateur,  reduceRealisateur, 
             {out: {"inline": 1}, query: {"country": "USA"}} )

Une autre possibilité intéressante est le calcul *incrémental*
d'un traitement MapReduce. En bref, on peut stocker le
résultat dans une nouvelle collection, avec mettre à jour
cette collection, sans avoir à tout recalculer, quand de nouveaux
documents apparaissent dans la collection en entrée. Il
s'agit d'une spécificité MongoDB, donc nous n'allons
pas insister dessus: reportez-vous à la documentation.

Jointures avec MapReduce
========================

MapReduce est un mécanisme de base qui peut être utilisé pour implanter
des opérateurs de plus haut niveau. La méthode utilisée pour transposer
une opération comme la jointure en MapReduce n'est pas forcément
très élégante, mais elle a le mérite de bénéficier de la *scalabilité*
du calcul (par parallélisation/distribution) dans des systèmes conçus
pour gérer de grands vollumes de données. Elle est aussi représentative
de la transposition en MapReduce de traitements plus sophistiqués,
même si elle passe par des contournements peu satisfaisants.

Nous montrons donc cette méthode. Notre
base est celle contenant les films *avec références*, et nous avons déjà
vu que la technique consistant à implanter côté client, bien
qu'effective, ne passe pas à l'échelle.

Le but est de partir des films avec une référence vers l'artiste / réalisateur,
et d'obtenir pour chaque film le document complet représentant ce réalisateur (nom,
date de naissance, etc.) 

Première étape: nous devons accéder  dans un même traitement MapReduce
aux films (dans *movies*) et aux artistes (dans *artists*). Malheureusement,
le MapReduce de MongoDB semble ne pouvoir prendre qu'une seule collection
en entrée (les autres systèmes n'ont pas cette limitation). Nous 
allons donc commencer par copier les données dans une collection commune,
nommée *jointure*:

.. code-block:: bash

     mongoimport -d moviesref -c jointure --file movies-refs.json --jsonArray
     mongoimport -d moviesref -c jointure --file artists.json --jsonArray
  
Voici maintenant le code des deux fonctions de *map* et de *reduce*. La fonction de
*map* est donnée ci-dessous: essayez de la comprendre, en vous aidant
des commentaires internes donnés par la suite.

.. code-block:: javascript
 
    var mapJoin = function() {
      // Est-ce que la clé du document contient le mot "artist"?
      if (this._id.indexOf("artist") != -1) {
        // Oui ! C'est un artiste. Ajoutons-lui son type.
        this.type="artist";        
        // On produit une paire avec pour clé celle de l'artiste
        emit(this._id, this);
      }
      else {
        // Non: c'est un film. Ajoutons-lui son type.
       this.type="film";
       // Simplifions un peu le document pour l'affichage
       delete this.summary;
       delete this.actors;
        // On produit une paire avec pour clé celle du metteur en scène
       emit(this.director._id, this);
     }
    };

Donc, la fonction s'appliquera en entrée à notre collection *jointure* qui contient
maintenant des documents *artistes* et des documents *films*. La fonction
doit d'abord savoir à quel type de document elle  a affaire. Dans notre cas, c'est
simple, les clés des artistes sont de la forme ``artist:xx`` et les
clés des films de la forme ``movie:yy``. C'est ce que teste la fonction
Javascript *indexOf*.

La fonction produit donc, à l'attention du *reduce*, soit un document 
*artist*, soit un document *film* (notez que nous les "annotons"
avec leur type pour rendre les choses plus faciles ensuite). Nous voulons regrouper les
metteurs en scène avec les films qu'ils/elles ont réalisés: *on
y arrive en émettant les documents à  regrouper avec la même valeur
de clé*.

Ici, on émet les artistes avec leur identifiant, et les films avec l'identifiant
de leur metteur en scène. Le résultat est donc bien celui souhaité. Si cela
vous semble obscur, réfléchissez soigneusement et prenez un exemple.

.. note:: Et pour les artistes qui n'ont jamais réalisé de film? Et bien ils
   seront solitaires dans leur groupe. On n'a pas vraiment moyen de les éliminer
   à ce stade, car on ne sait pas décider si un artiste, considéré isolément, est
   ou non un réalisateur.
   
*Il s'agit du mécanisme de base d'une implantation à base de MapReduce*. Le préalable
à toute manipulation conjointe de documents distincts est de le regrouper
avec le *map* pour les traiter ensemble avec le *reduce*.   

Voici maintenant la fonction de *reduce*.

.. code-block:: javascript
          
   var reduceJoin = function(id, items) {
   
     var director = null, films={result: []}
      
     // Commençons par chercher l'artiste dans cette liste    
     for (var idx = 0; idx < items.length; idx++) {
       if (items[idx].type=="artist") {
            director = items[idx];
        }
     }             
           
     // Maintenant, 'director' contient l'artiste : on l'affecte aux films   
     for (var idx = 0; idx < items.length; idx++) {
        if (items[idx].type=="film"  && director != null) {
            items[idx].director = director;
            films.result.push (items[idx]);
         }             
      }
      return films; 
    };

On dispose en entrée d'une liste "d'items", dont on sait qu'elle contient
un artiste (au plus) et des films (peut-être aucun, peut-être plusieurs).
On effectue donc la jointure *localement*. On identifie d'abord le metteur
en scène, et on le place dans la variable ``director``. Puis on affecte
ce document à l'attribut ``director`` de chaque film. 

On retourne finalement un objet ``films`` contenant le résultat de la jointure
locale. Pour des raisons liées à des limitations du MapReduce sous MongoDB, nous
ne pouvons pas (i) émettre plusieurs documents dans une exécution de
la fonction ou même (ii) émettre un tableau de documents. Nous avons
donc dû "encapsuler" ce tableau dans la valeur retournée. Vous étiez
prévenu: ce n'est pas très élégant.

Il reste à exécuter ce traitement MapReduce, avec l'instruction suivante.

.. code-block:: javascript
 
    db.jointure.mapReduce(mapJoin, reduceJoin, {out: {"inline": 1}});

Regardez bien le résultat. La fonction de *reduce* produit des paires clé-valeur,
la clé étant l'identifiant de l'artiste, et la valeur est celle produite par
notre fonction *reduce()*. Dans le cas des artistes qui ne sont pas réalisateurs,
l'artiste est émis tel quel: MongoDB n'appelle pas la fonction *reduce()*
pour des groupes contenant un seul document.

*Ce qu'il faut retenir avant tout*, c'est le mécanisme qui permet d'associer
des documents initialement distincts. MapReduce n'étant pas conçu (au départ) pour
ce genre de manipulation, il faut accepter quelques inconvénients, et bricoler quelque
peu. Ici, l'application client devrait "nettoyer" le résultat obtenu, mais pour
l'essentiel l'objectif visé est atteint.
  
Exercices
========= 


   
.. admonition:: Exercice: implanter le *sum()*.

    Implantez en MapReduce le calcul équivalent à
    
    .. code-block:: sql
    
       select sum(*) from movies

    Puis faites la même chose pour
   
    .. code-block:: sql
    
          select sum(*) from movies group by genre
   
.. admonition:: Exercice: afficher le nom du réalisateur

    Reprenez l'exemple (mapRealisateur, joinRealisateur), et effectuez
    les modifications suivantes:
    
      * modifiez les fonctions pour afficher le *nom* du réalisateur avec la liste de ses films.
        (Astuce: la clé émise par la fonction de *map* peut être un *objet* avec plusieurs valeurs).
      * appliquez le traitement aux films français parus avant 2000 (attention, les années
        sont codées comme des chaînes de caractères).
     
.. admonition:: Exercice: compter les termes d'un texte

   Objectif: construire un groupe pour chaque terme (mot) apparaissant
   dans le titre d'un film, et lui associer des informations. Voici une version
   de base. La fonction de *map*:
   
    .. code-block:: javascript
   
       var mapTermes = function() {
         var tokens = this.title.match(/\S+/g)
         for (var i = 0; i < tokens.length; i++) { 
                  emit(tokens[i], this.title);
          }
       }


   La fonction de *reduce*:
             
    .. code-block:: javascript
  
       var reduceTermes = function(terme, titres) {
          var res = new Object();
          res.terme = terme;
          res.titres = titres;
          return res;
       };
   
   Commencez par vérifier que cela fonctionne, regardez les mots qui apparaissent dans
   plusieurs titres. Ensuite, traitez le *résumé* de chaque film, et faites les calculs
   suivants:
   
     * Pour chaque terme, affichez le titre du film et le nombre d'occurrences dans le résumé
       du film.
     * Pour chaque terme, affichez de plus le nombre total d'occurences du terme dans la collection.
     * Enfin, identifiez les termes qui apparaissent très souvent et sont peu significatifs
       ("de", "un", "le", etc.). Faitez-en une liste et éliminez-les du résultat.
      
    Quand vous serez arrivés au bout, vous aurez fait un bon pas vers un algorithme
    de construction d'un index plein texte sur votre base documentaire.
 
            
.. admonition:: Exercice: classification de documents (basique)

   Nous voulons grouper les films. Ecrivez le traitement MapReduce pour
   
     * un classement par genre,
     * un classement par décennie (les années 70, les années 80, etc.)
     
   Si vous vous sentez en forme, réflechissez au problème suivant: comment
   appliquer un algorithme de classification kMeans sur les films (pour
   les grouper par période par exemple) ou les artistes (les grouper
   par génération par exemple). Bon *brainstorming*, mais pas d'inquiétude,
   nous y reviendrons.  
 
 
.. admonition:: Exercice: encore une jointure
 
   Reprenez l'implantation de la jointure décrite précédemment, et
   transformez-là pour calculer celle des films et des *acteurs*.