25. Annales des examens

Les examens de NFE204 durent 3 heures, les documents et autres soutiens ne sont pas autorisés, à l’exception d’une calculatrice.

Le but de l’examen est de vérifier la bonne compréhension des concepts et techniques vus en cours. Dans les rares cas où un langage informatique est impliqué, nous n’évaluons pas les réponses par la syntaxe mais par la clarté, la concision et la précision.

Examen du 3 février 2015

Première partie : recherche d’information (8 pts)

Voici quelques extraits d’un discours politique célèbre (un peu modifié pour les besoins de la cause). Chaque extrait correspond à un document, numéroté \(a_i\).

  1. (a1) Moi, président de la République, je ne serai pas le chef de la majorité, je ne recevrai pas les parlementaires de la majorité à l’Elysée.
  2. (a2) Moi, président de la République, je ne traiterai pas mon Premier ministre de collaborateur.
  3. (a3) Moi, président de la République, les ministres de la majorité ne pourraient pas cumuler leurs fonctions avec un mandat parlementaire ou local.
  4. (a4) Moi, président de la République, il y aura un code de déontologie pour les ministres et parlementaires qui ne pourraient pas rentrer dans un conflit d’intérêt.

Questions.

  • Rappeler la notion de stop word (ou “mot vide”) et donner la liste de ceux que vous choisiriez dans les textes ci-dessus.

  • Outre ces mots vides, pouvez-vous identifier certains mots dont l’idf tend vers 0 (en appliquant le logarithme)? Lesquels?

  • Présentez la matrice d’incidence pour le vocabulaire suivant: majorité, ministre, déontologie, parlementaire. Vous indiquerez l’idf pour chaque terme (sans logarithme), et le tf pour chaque paire (terme, document). Bien entendu, on suppose que les termes ont été fait l’objet d’une normalisation syntaxique au préalable.

  • Donner les résultats classés par similarité cosinus basée sur les tf (on ignore l’idf) pour les requêtes suivantes.

    • majorité; expliquez le classement;
    • ministre; expliquez le classement du premier document;
    • déontologie et ministre; qu’est-ce qui changerait si on prenait en compte l’idf?
    • majorité et ministre; qu’obtiendrait-t-on avec une requête Booléenne? Commentaire?
  • Calculez la similarité cosinus entre a3 et a4; puis entre a3 et a1. Qui est le plus proche de a3?

Seconde partie : Pig et MapReduce (6 pts)

Un système d’observation spatiale capte des signaux en provenance de planètes situées dans de lointaines galaxies. Ces signaux sont stockés dans une collection Signaux de la forme Signaux (idPlanète, date, contenu).

Le but est de déterminer si ces signaux peuvent être émis par une intelligence extra-terrestre. Pour cela les scientifiques ont mis au point les fonctions suivantes:

  1. Fonction de structure: \(f_S(c): Bool\), prend un contenu en entrée, et renvoie true si le contenu présente une certaine structure, false sinon.
  2. Fonction de détecteur d’Aliens: \(f_D(<c>): real\), prend une liste de contenus structurés en entrée, et renvoie un indicateur entre 0 et 1 indiquant la probabilité que ces contenus soient écrits en langage extra-terrrestre, et donc la présence d’Aliens!

Bien entendu, il y a beaucoup de signaux: c’est du Big Data.

Questions.

  1. Ecrire un programme Pig latin qui produit, pour chaque planète, l’indicateur de présence d’Aliens par analyse des contenus provenant de la planète.
  2. Donnez un programme MapReduce qui permettrait d’exécuter ce programme Pig en distribué (indiquez la fonction de Map, la fonction de Reduce, dans le langage ou pseudo-code qui vous convient).
  3. Ecrire un programme Pig latin qui produit, pour chaque planète et pour chaque jour, le rapport entre contenus structurés et non structurés reçus de cette planète.

Troisième partie : questions de cours (6 pts)

Concision et précision s’il vous plaît.

  • En recherche d’information, qu’est-ce que le rappel? qu’est-ce que la précision?

  • Deux techniques fondamentales vues en cours sont la réplication et le partitionnement. Rappelez brièvement leur définition, et indiquez leurs rôles respectifs. Sont-elles complémentaires? Redondantes?

  • Qu’est-ce qu’une architecture multi-nœuds, quels sont ses avantages et inconvénients?

  • Vous avez 500 TOs de données, et vous pouvez acheter des serveurs pour votre cloud avec chacun 32 GO de mémoire et 10 TOs de disque. Le coût unitaire d’un serveur eest de 500 Euros.

    Quelle est la configuration de votre grappe de serveurs la moins coûteuse (financièrement) et combien de temps prend au minimum la lecture complète de la collection avec cette solution?

  • Même situation: quelle est la configuration qui assure le maximum d’efficacité, et quel est son coût financier?

  • Rappelez le principe de l’éclatement d’un fragment dans le partitionnement par intervalle.

Examen du 14 avril 2015

Première partie : recherche d’information (8 pts)

Voici notre base documentaire:

  • d1: Le loup et les trois petits cochons.
  • d2: Spider Cochon, Spider Cochon, il peut marcher au plafond. Est-ce qu’il peut faire une toile? Bien sûr que non, c’est un cochon.
  • d3: Un loup a mangé un mouton, les autres moutons sont restés dans la bergerie.
  • d4: Il y a trois moutons dans le pré, et un autre dans la gueule du loup.
  • d5: L’histoire extraordinaire des trois petits loups et du grand méchant cochon.

On va se limiter au vocabulaire loup, mouton, cochon.

  • Donnez la matrice d’incidence booléenne (seulement 0 ou 1) avec les termes en ligne (NB: on suppose une phase préalable de normalisation qui élimine les pluriels, majuscules, etc.)

  • Expliquez par quelle technique, avec cette matrice d’incidence, on peut répondre à la requête booléenne “loup et cochon mais pas mouton”. Quel est le résultat?

  • Maintenant donnez une matrice d’incidence contenant les tf, et un tableau donnant les idf (sans le log), pour les trois termes précédents.

  • Donner les résultats classés par similarité cosinus basée sur les tf (on ignore l’idf) pour les requêtes suivantes.

    • cochon;
    • loup et mouton;
    • loup et cochon.
  • On ajoute le document d6: “Shaun le mouton: une nuit de cochon”.

    Quel est son score pour la requête “loup et mouton”, quel autre document a le même score et qu’est-ce qui change si on prend en compte l’idf?

  • Pour la requête “loup et cochon” et les documents d1 et d5, qu’est-ce qui change si on ne met pas de restriction sur le vocabulaire (tous les mots sont indexés)?

Seconde partie : Pig et MapReduce (6 pts)

Une organisation terroriste, le Spectre, envisage de commettre un attentat dans une station de métro. Heureusement, le MI5 dispose d’une base de données d’échanges téléphoniques et ses experts ont mis au point un décryptage qui identifie la probabilité qu’un message provienne du Spectre d’une part, et fasse référence à une station de métro d’autre part.

Après décryptage, les messages obtenus ont la forme suivante:

{
 "id": "x1970897",
 "émetteur": "Joe Shark",
 "contenu": "Hmm hmm hmmm",
 "probaSpectre": 0.6,
 "station": "Covent Garden"
 }

Il y en a des milliards: vous avez quelques heures pour trouver la solution.

  1. Spécifier les deux fonctions du programme MapReduce qui va identifier la station-cible la plus probable. Ce programme doit sélectionner les messages émis par le Spectre avec une probabilité de plus de 70%, et produire, pour chaque station le nombre de tels messages où elle est mentionnée.
  2. Quel est le programme Pig qui exprime ce traitement MapReduce?
  3. On veut connaître les 5 mots les plus couramment employés par chaque émetteur dans le contenu de ses messages. Expliquez, avec la formalisation de votre choix, comment obtenir cette information (vous avez le droit d’utiliser un opérateur de tri).

Troisième partie : questions de cours (6 pts)

  • En recherche d’information, que signifient les termes “faux positifs” et “faux négatifs”?
  • Je soumets une requête \(t_1, t_2, \cdots, t_n\). Quel est le poids de chaque terme dans le vecteur représentant cette requête? La normalisation de ce vecteur est elle importante pour le classement (justifier)?
  • Donnez trois bonnes raisons de choisir un système relationnel plutôt qu’un système NoSQL pour gérer vos données.
  • Donnez trois bonnes raisons de choisir un système NoSQL plutôt qu’un système relationnel pour gérer vos données.
  • Rappeler la règle du quorum (majorité des votants) en cas de partitionnement de réseau, et justifiez-la.
  • Dans un traitement MapReduce, peut-on toujours se contenter d’un seul reducer? Avantages? Inconvénients?

Examen du 15 juin 2015

Première partie : documents structurés (6 pts)

Une application s’abonne à un flux de nouvelles dont voici un échantillon.

<myrss version="2.0">
  <channel>
    <item>
        <title>Angela et nous</title>
        <description>Un nouveau sommet entre la France et l'Allemagne
            est prévu en Allemagne la semaine prochaine pour relancer l'UE.
        </description>
        <links>
            <link>lemonde.fr</link>
            <link>lesechos.fr</link>
        </links>
    </item>
    <item>
        <title>L'Union en crise</title>
        <description> L'Allemagne, la France, l'Italie doivent à nouveau se
            réunir pour étudier les demandes de la Grèce.
        </description>
        <links>
            <link>lefigaro.fr</link>
        </links>
    </item>
    <item>
        <title>Alexis à l'action</title>
        <description>Le nouveau premier ministre de la Grèce
            a prononcé son discours d'investiture.
        </description>
        <links>
            <link>libe.fr</link>
        </links>
    </item>
    <item>
        <title>Nos cousins transalpins</title>
        <description>La France et l'Italie partagent plus qu'une frontière
            commune: le point de vue de l'Italie.
        </description>
        <links>
            <link>courrier.org</link>
        </links>
    </item>
  </channel>
</myrss>

Chaque nouvelle (item) résume donc un sujet et propose des liens vers des médias où le sujet est développé. Les quatre éléments item seront désignés respectivement par d1, d2, d3 et d4.

  1. Donnez la forme arborescente de ce document (ne recopiez pas tous les textes: la structure du document suffit).
  2. Proposez un format JSON pour représenter le même contenu (idem: la structure suffit).
  3. Dans une base relationnelle, comment modéliser l’information contenue dans ce document?
  4. Quelle est l’expression XPath pour obtenir tous les éléments link?
  5. Quelle est l’expression XPath pour obtenir les titres des items dont l’un des link est lemonde.fr?

Deuxième partie : recherche d’information (6 pts)

On veut indexer les nouvelles reçues de manière à pouvoir les rechercher en fonction d’un pays. Le vocabulaire auquel on se restreint est donc celui des noms de pays (Allemagne, France, Grèce, Italie).

  1. Donnez une matrice d’incidence contenant les tf pour les quatre pays, et un tableau donnant les idf (sans appliquer le log). Mettez les noms de pays en ligne, et les documents en colonne.

  2. Donner les résultats classés par similarité cosinus basée sur les tf (on ignore l’idf) pour les requêtes suivantes. Expliquez brièvement le classement.

    • Italie;
    • Allemagne et France ;
    • France et Grèce.
  3. Reprenons la dernière requête, “France et Grèce” et les documents d2 et d3. Qu’est-ce que la prise en compte de l’idf changerait au classement?

Troisième partie : MapReduce (4 pts)

Voici quelques analyses à exprimer avec MapReduce et Pig.

  1. On veut compter le nombre de nouvelles consacrées à la Grèce publiées par chaque média. Décrivez le programme MapReduce (fonctions de Map et de Reduce) qui produit le résultat souhaité. Donnez le pseudo-code de chaque fonction, ou indiquez par un texte clair son déroulement.

    Vous disposez d’une fonction contains($texte, $mot) qui renvoie vrai si $texte contient $mot.

  2. Quel est le programme Pig qui exprime ce traitement MapReduce?

Quatrième partie : questions de cours (6 pts)

Questions reprises des Quiz.

Examen du 1er juillet 2016 (FOD)

Exercice corrigé: documents structurés et MapReduce (8 pts)

Note

Ce premier exercice (légèrement modifié et étendu) est corrigé entièrement. Les autres exercices consistaient en un énoncé classique de recherche d’information (8 points) et 4 brèves questions de cours (4 points).

Le service informatique du Cnam a décidé de représenter ses données sous forme de documents structurés pour faciliter les processus analytiques. Voici un exemple de documents centrés sur les étudiant.e.s et incluant les Unités d’Enseignement (UE) suivies par chacun.e.

 [{
    "_id": 978,
    "nom": "Jean Dujardin",
    "annee": "2016",
      "UE": [{"ue":11, "note": 12},
              {"ue":27, "note": 17},
               {"ue":37,  "note": 14}
              ]
   },
  {
  "_id": 476,
  "nom": "Vanessa Paradis",
  "annee": "2016",
  "UE": [{"ue": 13, "note": 17},
          {"ue":27, "note": 10},
          {"ue":76,  "note": 11}
       ]
  }
]

Question 1: documents et base relationnelle

Question

Sachant que ces documents sont produits à partir d’une base relationnelle, reconstituez le schéma de cette base et indiquez le contenu des tables correspondant aux documents ci-dessus.

Il y a clairement une table Inscription (id, nom année) et une table Note (idInscription, ue, note). Il y a probablement aussi une table UE mais elle n’est pas strictement nécessaire pour produire le document ci-dessus.

Question 2: restructuration de documents

Question

Proposez une autre représentation des mêmes données, centrée cette fois, non plus sur les étudiants, mais sur les UEs.

Voilà, à compléter avec les UEs 13 et 37.

 [
  {
    "_id": 387,
    "UE": 11,
    "inscrits": [
       {"nom": "Jean Dujardin", "annee": "2016", "note": 12}
     ]
    },
    {
    "_id": 3809,
    "UE": 27,
    "inscrits": [
       {"nom": "Jean Dujardin", "annee": "2016", "note": 17},
       {"nom": "Vanessa Paradis", "annee": "2016", "note": 10},
     ]
    },
    {
    "_id": 987,
    "UE": 76,
    "inscrits": [
       {"nom": "Vanessa Paradis", "annee": "2016", "note": 11}
     ]
    }
]

Question 3: MapReduce et la notion de document “autonome”

Question

On veut implanter, par un processus MapReduce, le calcul de la moyenne des notes d’un étudiant. Quelle est la représentation la plus appropriée parmi les trois précédentes (une en relationnel, deux en documents structurés), et pourquoi?

La première représentation est très bien adaptée à MapReduce, puisque chaque document contient l’intégralité des informations nécessaires au calcul. Si on prend le document pour Jean Dujardin par exemple, il suffit de prendre le tableau des UE et de calculer la moyenne. Donc, pas besoin de jointure, pas besoin de regroupement. Le calcul peut se faire intégralement dans la fonction de Map, et la fonction de Reduce n’a rien à faire.

C’est l’iiustration de la notion de document autonome: pas besoin d’utiliser des références à d’autres documents (ce qui mène à des jointures en relationnel) ou de distribuer l’information nécsesaire dans plusieurs documents (ce qui mène à des regroupements en MapReduce).

Si on a choisit de construire les documents structurés en les centrant sur le UEs, il y a beaucoup plus de travail, comme le montre la question suivante.

Question 4: MapReduce, outil de restructuration/regroupement

Question

Spécifiez le calcul du nombre d’étudiants par UE, en MapReduce, en prenant en entrée des documents centrés sur les étudiants (exemple donné ci-dessus).

Cette fois, il va falloir utiliser toutes les capacités du modèle MapReduce pour obtenir le résultat voulu. Comme suggéré par la question précédente, la représentation centrée sur les UE serait beaucoup plus appropriée pour disposer d’un document autonome contenant toutes les informations nécessaires. C’est exactement ce que l’on va faire avec MapReduce: transformer la représentation centrée sur les étudiants en représentation centrée sur les UEs, le reste est un jeu d’enfant.

La fonction de Map

Une fonction de Map produit des paires (clé, valeur). La première question à se poser c’est: quelle est la clé que je choisis de produire? Rappelons que la clé est une sorte d’étiquette que l’on pose sur chaque valeur et qui va permettre de les regrouper.

Ici, on veut regrouper par UE pour pouvoir compter tous les étudiants inscrits. On va donc émettre une paire intermédiaire pour chaque UE mentionnée dans un document en entrée. Voici le pseudo-code.

function fonctionMap ($doc) # doc est un document centré étudiant
{
  # On parcourt les UEs du tableau UEs
  for    [$ue in $doc.UEs] do
     emit ($ue.id, $doc.nom)
  done
}

Quand on traite le premier document de notre exemple, on obtient donc trois paires intermédiaires:

{"ue:11", "Jean Dujardin"}
{"ue:27", "Jean Dujardin"}
{"ue:37", "Jean Dujardin"}

Et quand on traite le second document, on obtient:

{"ue:13", "Vanessa Paradis"}
{"ue:27", "Vanessa Paradis"}
{"ue:76", "Vanessa Paradis"}

Toutes ces paires sont alors transmises à “l’atelier d’assemblage” qui les regroupe sur la clé. Voici la liste des groupes (un par UE).

{"ue:11", ["Jean Dujardin"]}
{"ue:13", "Vanessa Paradis"}
{"ue:27", ["Jean Dujardin", "Vanessa Paradis"]}
{"ue:37", "Jean Dujardin"}
{"ue:76", "Vanessa Paradis"}

Il reste à appliquer la fonction de Reduce à chaque groupe.

function fonctionReduce ($clé, $tableau)
{
  return ($clé, count($tableau)
}

Et voilà.

Question 5: MapReduce = group-by SQL

Question

Quelle serait la requête SQL correspondant à ce dernier calcul sur la base relationnelle ?

Avec SQL, c’est direct, à condition d’accepter de faire des jointures.

select u.id, u.titre, count(*)
from Etudiant as e, Inscription as i, UE as u
where e.id = i.idEtudiant
and   u.id = i.idUE
group by u.id, u.titre

Examen du 1er février 2017 (Présentiel)

Première partie : documents structurés (5 pts)

Un institut chargé d’analyser l’opinion publique collecte des articles parus dans la presse en ligne, ainsi que les commentaires déposés par les internautes sur ces articles. Ces informations sont stockées dans une base relationnelle, puis mises à disposition des analystes sous la forme de documents JSON dont voici deux exemples.

{
 "_id": 978,
"_source": "lemonde.fr",
"date": "07/02/2017",
"titre": "Le président Trump décide d'interdire l'entrée de tout étranger aux USA",
"contenu": "Suite à un décret paru ....",
"commentaires": [
     {"internaute": "chocho@monsite.com",
    "note": 5,
    "commentaire": "Les décisions du nouveau président sont inquiétantes ..."
    },
    {"internaute": "alain@dugenou.com",
    "note": 2,
    "commentaire": "Arrêtons de critiquer ce grand homme..."
    }
  ]
}
{
"_id": 54,
"source": "nimportequoi.fr",
"date": "07/02/2017",
"titre": "La consommation de pétrole aide à lutter contre le réchauffement",
"contenu": "Contrairement à ce qu'affirment les media officiels ....",
"commentaires": [
    {"internaute": "alain@dugenou.com",
     "note": 5,
    "commentaire": "Enfin un site qui n'a pas peur de dire la vérité ..."
    }
 ]
}

Les notes vont de 1 à 5, 1 exprimant un fort désacord avec le contenu de l’article, et 5 un accord complet.

  1. À votre avis, quel est le schéma de la base relationnelle d’où proviennent ces documents? Montrez comment les informations des documents ci-dessus peuvent être représentés avec ce schéma (ne recopiez pas tous les textes, donnez les tables avec quelques lignes montrant la répartition des données).
  2. On collecte des informations sur les internautes (année de naissance, adresse). Où les placer dans la base relationnelle? Dans le document JSON?
  3. On veut maintenant obtenir une représentation JSON centrée sur les internautes et pas sur les sources d’information. Décrivez le processus Map/Reduce qui transforme une collection de documents formatés comme les exemples ci-dessus, en une collection de documents dont chacun donne les commentaires déposés par un internaute particulier.

Deuxième partie : recherche d’information (4 pts)

On veut indexer les articles pour pouvoir les analyser en fonction des candidats qu’ils mentionnent. On s’intéresse en particulier à 4 candidats: Clinton, Trump, Sanders et Bush. Voici 4 extraits d’articles (ce sont nos documents \(d_1\), \(d_2\), \(d_3\), \(d_4\)).

  • L’affrontement entre Trump et Clinton bat son plein. Clinton a-t-elle encore une chance?
  • Tous ces candidats, Clinton, Trump, Sanders et Bush, semblent encore en mesure de l’emporter.
  • La surprise, c’est Sanders, personne ne l’attendait à ce niveau.
  • Ce que Bush pense de Trump? A peu de choses près ce que ce dernier pense de Bush.

Questions:

  1. Donnez une matrice d’incidence contenant les tf pour les quatre candidats, et un tableau donnant les idf (sans appliquer le \(\log\)). Mettez les noms de candidats en ligne, et les documents en colonne.

    Réponse:

      d1 d2 d3 d4
    Clinton (2) 2 1 0 0
    Trump (4/3) 1 1 0 1
    Sanders (2) 0 1 1 0
    Bush (2) 0 1 0 2
  2. Donner les résultats classés par similarité cosinus basée sur les tf (on ignore l’idf) pour les requêtes suivantes. Expliquez brièvement le classement.

    • Bush
    • Trump et Clinton
    • Trump et Sanders

    Réponse:

    Les normes

    • \(||d_1|| = \sqrt{4+ 1} = \sqrt{5}\)
    • \(||d_2|| = \sqrt{1+1+1+1} = 2\)
    • \(||d_3|| = \sqrt{1}\)
    • \(||d_4|| = \sqrt{1+4}=\sqrt{5}\)

    Les cosinus (requête non normalisée).

    • Bush: d2 : \(\frac{1}{2}=0,5\) ; d4 : \(\frac{2}{\sqrt{5}} \simeq 0,89\) ; d4 est premier car il mentionne deux fois Bush.

    • Trump et Clinton: d1 : \(\frac{2+1}{\sqrt{5}}\); d2 : \(\frac{1+1}{2}\); d4 : \(\frac{1}{\sqrt{5}}\);

      d1 est premier comme on pouvait s’y attendre: il parle exclusivement de Trump et Clinton. Viennent ensuite d2 puis d4.

    • Trump et Sanders

      • d1 : \(\frac{1}{\sqrt{5}}\)
      • d2 : \(\frac{2}{2}\)
      • d3 : \(\frac{1}{1}\)
      • d4 : \(\frac{1}{\sqrt{5}}\)

    d2 et d3 arrivent à égalité. Intuitivement, il parlent tous les deux “à moitié” de Trump et Sanders. d1 et d4 parlent de Trump ou de Sanders et aussi des autres candidats.

  3. Reprenons la requête, “Trump et Clinton” et le premier document du classement. Quelle légère modification de ce document lui donnerait une mesure cosinus encore plus élevée? Expliquez pourquoi.

Réponse: Il suffit d’ajouter une fois la mention de Trump.
  1. Je fais une recherche sur “Sanders”. Pouvez-vous indiquer le classement sans faire aucun calcul? Expliquez.

    Réponse: Sanders apparaît dans les documents d2 et d3, et d3 ne parle que de lui alors que d@ parle de tous les candidats. D’où le classement.

Troisième partie : systèmes distribués (3 pts)

On considère un système Cassandra avec un facteur de réplication F= 3 (donc, 3 copies d’un même document). Appelons W le nombre d’acquittements reçus pour une écriture, R le nombre d’acquittements reçus pour une lecture.

  1. Décrivez brièvement les caractéristiques des configurations suivantes:

    • R=1, W=3
    • R=1,W=1

    Réponse: La première configuration assure des écritures synchrones, et se contente d’une lecture qui va prendre indifféremment l’une des trois versions. La lecture est cohérente.

    La seconde privilégie l’efficacité. On aquitte après une seule écriture, on lit une seule copie (peut-être pas la plus récente).

  2. Quelle est la formule sur R, W et F qui assure la cohérence immédiate (par opposition à la cohérence à terme) du système? Expliquez brièvement.

Réponse: W+R = F+1. Voir le cours.

Quatrième partie : MapReduce (4 pts)

Toujours sur nos documents donnés en début d’énoncé (première partie): on veut analyser, pour la source “lemonde.fr”, le nombre de commentaires ayant obtenus respectivement 1, 2, 3, 4 ou 5.

  • Décrivez la modélisation MapReduce de ce calcul. Donnez le pseudo-code de chaque fonction, ou indiquez par un texte clair son déroulement.
  • Donnez la forme de la chaîne de traitement (workflow), avec des opérateurs Pig ou Spark, qui implante ce calcul.

Cinquième partie : questions de cours (4 pts)

  • Qu’entend-on par “bag of words” pour le modèle des documents textuels en recherche d’information?
  • Expliquez la notion de noeud virtuel dans la distribution par consistent hashing.
  • Que signifie, pour une structure de partitionnement, être dynamique. Avons-nous étudié un système où le partitionnement n’était pas dynamique?
  • Donnez une définition de la scalabilité.

Examen du 6 février 2018 (Présentiel)

Première partie : modélisation NoSQL (7 pts)

Pour cette partie, nous allons nous pencher sur le petit tutoriel proposé par la documentation en ligne de Cassandra, et consacré à la modélisation des données dans un contexte BigData. L’application (très simplifiée) est un service de musique en ligne, avec le modèle de données de la figure Fig. 25.1.

_images/musicservice.png

Fig. 25.1 Le cas d’école Cassandra

On a donc des chansons, chacune écrite par un artiste, et des playlists, qui consistent en une liste ordonnée de chansons.

  • Commencer par proposer le schéma relationnel correspondant à ce modèle. Il est sans doute nécessaire d’ajouter des identifiants. Donnez les commandes SQL de création des tables. (1 pt).

    Réponse:

    create table Artiste (id int not null, name varchar(50), age int, primary key(id))
    create table Song (id int not null, title varchar(50), lyrics text, primary key(id))
    create table Playlist (id int not null, creator varchar(50), primary key(id))
    create table SongInPlaylist (id_playlist int not null,
       id_song int not null, position int, primary key(id_playlist, id_song))
    
  • Le tutoriel Cassandra nous explique qu’il faut concevoir le schéma Cassandra en fonction des access patterns, autrement dit des requêtes que l’on s’attend à devoir effectuer. Voici les deux access patterns envisagés:

    • Find all song titles
    • Find all songs titles of a particular playlist

    Lesquels de ces access patterns posent potentiellement problème avec un système relationnel dans un contexte BigData et pourquoi ? Vous pouvez donner les requêtes SQL correspondantes pour clarifier votre réponse (1 pt).

    Réponse: le premier implique un parcours séquentiel de la table Song: à priori un système relationnel peut faire ça très bien. La seconde implique une jointure: les systèmes relationnels font ça très bien aussi mais ça ne passe pas forcément à très grande échelle. C’est en tout cas l’argument des systèmes NoSQL.

  • Le tutoriel Cassandra nous propose alors de créer une unique table

    CREATE TABLE playlists (
      id_playlist int,
    creator text,
    song_order int,
    song_id int,
    title text,
    lyrics text,
    name text,
    age int,
    PRIMARY KEY  (id_playlist, song_order ) );
    

    Discutez des avantages et inconvénients en répondant aux questions suivantes: combien faut-il d’insertions (au pire) pour ajouter une chanson à une playlist, en relationnel et dans Cassandra? Que peut-on dire des requêtes qui affichent une playlist, respectivement en relationnel et dans Cassandra (donnez la requête si nécessaire)? Combien de lignes dois-je mettre à jour quand l’âge d’un artiste change, en relationnel et en Cassandra? Conclusion? (2 pts)

    Réponse: Il faut (au pire, c’est à dire si la chanson, l’artiste, la playlist n’existent pas au préalable) 4 insertions en relationnel, une seule avec Cassandra. Pour la recherche, jointures indispensables en relationnel. Pour les mises à jour en revanche, en relationnel, il suffit juste de mettre à jour la ligne de l’artiste dans la table Artist. En Cassandra il faudra mettre à jour toutes les lignes contenant l’artiste dans la table Playlists.

  • Vous remarquez que l’identifiant de la table est composite (compound en anglais): (id_playlist, song_order ). Voici ce que nous dit le tutoriel:

    A compound primary key consists of the partition key and the clustering key. The partition key determines which node stores the data. Rows for a partition key are stored in order based on the clustering key.

    Sur la base de cette explication, quelles affirmations sont vraies parmi les suivantes:

    • Une chanson est stockée sur un seul serveur (vrai/faux)?
    • Les chansons d’une même playlist sont toutes sur un seul serveur (vrai/faux)?
    • Les chansons stockées sur un serveur sont triées sur leur identifiant (vrai/faux)?
    • Les chansons d’une même playlist sont stockées les unes après les autres (vrai/faux)?

    Réponse: réponses 2 et 4. L’identifiant de la playlist définit le serveur de stockage. De plus, les chansons d’une même playlist sont stockées dans l’ordre et contigument. Cf. Fig. 25.2.

    Faites un petit dessin illustrant les caractéristiques du stockage des playlists dans un système Cassandra distribué (2 pts).

    _images/correction-exam-0218.jpg

    Fig. 25.2 Le stockage optimal d’une playlist dans Cassandra

  • Pour finir, reprenez les access patterns donnés initialement. Lesquels vont pouvoir être évalués très efficacement avec cette organisation des données, lesquels posent des problèmes potentiels de cohérence (1 pt)?

    Réponse: réponses 2 et 4. L’access patterns qui peut être évalué facilement est “find all songs titles of a particular playlist” car il suffit d’avoir

    l’id_playlist pour afficher les chansons. L’évaluation de l’autre pattern est plus difficile et surtout plus longue car il faut parcourir tous les enregistrements et ensuite retirer les doublons pour pouvoir afficher toutes les chansons de la base

Deuxième partie : recherche d’information (5 pts)

On veut maintenant équiper notre système d’une fonction de recherche plein texte.

  • Un premier essai avec le langage CQL de Cassandra est évalué à partir d’un jeu de tests. On obtient les indicateurs du tableau suivant:

      Pertinent Non pertinent
    Positif 200 50
    Négatif 100 1800

    Sur 250 chansons ramenées dans le résultat, 200 sont pertinentes, 50 ne le sont pas, et il en manque en revanche 100 qui seraient pertinentes.

    Quel est le rappel de votre système? Quelle est sa précision? (1 pt)

  • Essayons de faire mieux en associant Cassandra à ElasticSearch pour pouvoir faire de la recherche avec classement. Voici quelques extraits de grandes chansons françaises.

    • Y a vraiment qu’l’amour qui vaille la peine
    • Que je t’aime, que je t’aime, que je t’aime
    • Dix ans de chaînes sans voir le jour, c’était ma peine forçat de l’amour
    • C’est (c’est) pas la peine c’est (c’est) (c’est) pas la peine

On va considérer que la phase d’indexation unifie les termes “amour” et “aime”. Sans faire de calcul, expliquez le résultat attendu (classement compris) pour les recherches suivantes (2 pts)

  • amour
  • peine
  • peine et aime
  • Un de vos collègues n’a pas suivi le cours NFE204 et vous affirme que la similarité cosinus entre un vecteur-document v et un vecteur-requête q est définie par la formule suivante:

    \[cos { } \theta = \sum_{i=1}^n v[i] \times q[i]\]

    \(x[i]\) désigne le nombre d’occurrences du i*ème terme dans un vecteur *x. Expliquez pourquoi votre collègue a tort, et prouvez en prenant un des exemples de recherche ci-dessus que le résultat avec cette formule serait différent de celui attendu (2 pts).

Troisième partie : Comprendre MapReduce tu devras (5 pts)

À une époque très lointaine, en pleine guerre intergalactique, deux Jedis isolés ne peuvent communiquer que par des messages cryptés. Le protocole de cryptage est le suivant: le vrai message est mélangé à N faux messages, N étant très très grand pour déjouer des services de décryptage de l’Empire. Les messages sont tous découpés en mots, et l’ensemble est transmis en vrac sous la forme suivante:

{"idMessage": "Xh9788&&", "mot": "force"}

Les Jedi disposent d’une fonction secrète \(f()\) qui prend l’identifiant d’un message et renvoie vrai ou faux.

  • Vous devez fournir à Maître Y. le programme MapReduce qui reconstituera le contenu des vrais messages envoyés par Obiwan K. à partir d’un flux massifs de documents ayant la forme précédente. On accepte pour l’instant que les mots d’un message ne soient pas dans l’ordre. Donnez ce programme sous la forme que vous voulez, pourvu que ce soit clair (1 pt).
  • Quel est à votre avis (expliquez) le degré maximal de parallélisme que l’on peut obtenir pour ce traitement (2 pts)?

Le degré maximal de parallélisme est limité par le nombre de serveur reducer, et dans ce cas il est de 1 car pour obtenir le message complet il doit être traité et stocké que sur le disque d’un seul reducer

  • Notez que, même après reconstitution, les mots d’un message sont dans n’importe quel ordre. Maître Y. a la faculté unique de lire et d’écrire des messages dans n’importe quel ordre, mais comment remettre dans l’ordre les mots des messages reçus par Obiwan K.? Proposez une extension de la forme des messages et du programme MapReduce pour que chaque message soit reconstitué dans l’ordre (2 pts).

Quatrième partie : questions de cours (3 pts)

  • Dans quelle architecture distribuée peut-on aboutir à des écritures conflictuelles? Donnez un exemple.
  • Que signifie, pour une structure de partitionnement, être dynamique. Avons-nous étudié un système où le partitionnement n’était pas dynamique?
  • Quel est le principe de la reprise sur panne dans Spark?