Algorithmes de résolution de requête

3.1.1 La projection

SELECT id, nom FROM etudiants;

def projection(table, champs):
    """
    Renvoie la table (sous forme de flux) obtenue à partir des tuples contenus
    dans ~table~ en n'y conservant que les attributs (les clés) qui sont
    contenus dans ~champs~.

    Renvoie une exception si un attribut de ~champs~ n'est pas un attribut des
    tuples de ~table~.
    """
    yield {}

def exemple_projection():
    """Exemple d'utilisation de la projection."""
    schema = {'a': (1, 10), 'b': (40, 100), 'c': (20,30)}
    for tuple_res in projection(table(schema ,nb=100),
                                ['a', 'c']):
        print(tuple_res)

SELECT id, (note1 + note2)/2 AS moyenne FROM etudiants;

def transformation(table, f):
    """Renvoie un flux obtenu en appliquant ~f~ à chacun des tuples composant
~table~."""
    yield {}

def exemple_transformation():
    schema = {'a': (1, 10), 'b': (40, 100), 'c': (20,30)}
    f = lambda tp: {'a': tp['a'], 'm': (tp['b']+tp['c'])//2}
    for tuple_res in transformation(table(schema,nb=100), f):
        print(tuple_res)

def projection2(table, champs):

    """
    Renvoie la table (sous forme de flux) obtenue à partir des tuples contenus
    dans ~table~ en n'y conservant que les attributs (les clés) qui sont
    contenus dans ~champs~.

    Renvoie une erreur si un attribut de ~champs~ n'est pas un attribut des
    tuples de ~table~.
    """
    yield {}

3.1.2 L'union

SELECT * FROM table1 UNION ALL SELECT * FROM table2 ;

def union(t1, t2):
    """Construit un flux qui énumère les éléments de ~t1~ puis ceux de ~t2~."""
    yield {}

def exemple_union():
    """Exemple d'utilisation de la fonction union."""
    schema1 = {'a':(30, 100), 'b': (10, 50)}
    schema2 = {'a': (40, 50), 'n': (100, 200), 'm': (0,10)}
    f = lambda tp: {'a': tp['a']//2, 'b': (tp['m']*tp['m'])//4}
    for tp in union(table(schema1, nb = 10),
                    transformation(table(schema2,nb=10),f)):
        print(tp)

3.1.3 La sélection

SELECT * FROM etudiants WHERE date_inscription <= 2020 AND date_inscription >= 2018;

def selection(table, pred):
    """Construit le flux des éléments de ~table~ qui satisfont le prédicat
       ~pred~ (fonction des tuples dans les booléens)."""
    yield {}

def exemple_selection():
    for un_tuple in selection(table({'a': (30, 100), 'b': (10, 50)}, nb=10),
               lambda tp: tp['a'] > 50 and tp['b'] < 45):
        print(un_tuple)

3.1.4 La sélection en présence d'index

1. Quelques fonctions pour créer et utiliser des tables sur disque
   

   Les fonctions utiles pour le TP sont les suivantes (elles se trouvent dans le module disque) :

   • mem_sur_disque(table, fichier) : sauvegarde table dans fichier,
   • lire_sur_disque(fichier) : renvoie le flux des tuples de la table contenue dans fichier,
   • index_fichier(fichier, attribut) : renvoie un dictionnaire qui à chaque valeur v associe la liste des adresses dans fichier des tuples associant v à attribut.
   • trouver_sur_disque(fichier, adresses) : renvoie le flux des tuples dans fichier ayant des adresses physiques dans adresses.

   Typiquement nous utiliserons ces fonctions de la manière suivante :

   schema = {'a' : (0,10), 'b' : (1,10000000)}
   tbl = table(schema, nb=1000000)
   fichier = "/tmp/tbl.table"
   mem_sur_disque(tbl, fichier)
   idx = index_fichier(fichier, 'a')
   b0 = trouve_sur_disque("/tmp/tbl.table",idx[0])
   print(sum(t['b'] for t in b0))
   

   • On commence par définir la forme des tuples
   • On produit le flux de la table
   • On choisit le fichier où nous allons sauvegarder les données
   • On enregistre la table sur disque dans le fichier
   • On crée un index des tuples du fichier pour l'attribut 'a'
   • On crée le flux des tuples de la table pour lesquels 'a' a pour valeur 0 à l'aide de l'index
   • On imprime la somme des valeurs de l'attribut 'b' des tuples sélectionnés
2. Calcul d'une sélection à partir d'un index
   

   Vous allez maintenant écrire la fonction selection_index(fichier, idx, valeurs) suivante :

   def selection_index(fichier, idx, valeurs) :
       """
       On suppose que ~fichier~ contient des tuples dont l'une des colonnes est
       indexée par ~idx~. La fonction renvoie le flux des tuples qui associe a la
       colonne indexée une valeur dans la séquence ~valeurs~.
   
       Attention : si un élément de ~valeurs~ n'est pas référencé dans ~idx~, on
       souhaite qu'il n'y ait pas d'erreur.
       """
       yield {}
   

   Voici un exemple d'utilisation de cette fonction où on sélectionne dans une table (générée pour l'occasion et indexée suivant l'attribut a) les tuples qui associent une valeur entre 2 et 4 à l'attribut a :

   def exemple_selection_index():
       schema = {'a' : (0,10), 'b' : (1,10000000)}
       tbl = table(schema, nb=1000000)
       fichier = "/tmp/tbl.table"
       mem_sur_disque(tbl, fichier)
       idx = index_fichier(fichier, 'a')
       for tp in selection_index(fichier, idx, range(2,5)):
           print(tp)
   
   

3.2.1 Produit cartésien

SELECT * FROM table1 CROSS JOIN table2;

SELECT * FROM table1, table2;

1. Appariement de tuples
   

   Nous allons tout d'abord voir comment nous allons réaliser l'appariement de deux tuples. Idéalement nous souhaiterions que cet appariement consiste à faire l'union des dictionnaires : chaque clé de l'un des dictionnaires est dans le dictionnaire résultat et celui-ci associe à la clé la valeur qui lui est associée par l'un des tuples de départ. Si les deux tuples n'ont aucun attribut en commun, alors il n'y a pas de difficulté. Dans le cas contraire, nous décidons (un peu arbitrairement) de donner la priorité au second tuple : nous allons associer, dans le résultat, les valeurs du second tuple aux clés communes aux deux tuples.

   Complétez la fonction ci-dessous.

   def appariement(t1, t2):
       """Renvoie un tuple ayant pour clé les clés de ~t1~ et de ~t2~.
   
       Lorsqu'une clé n'apparaît que dans un tuple la valeur que lui associe ce
       tuple est celle associée à la clé dans le résultat.
   
       À une clé qui apparaît dans les deux tuples, le résultat associe la valeur
       que lui associe ~t2~.
       """
       return {}
   

2. L'algorithme de double boucle
   

   Pour générer le produit cartésien nous allons utiliser un algorithme qui utilise deux boucles imbriquées :

   1. Une boucle parcourt la première table en sélectionant un tuple tp à chaque tour.
   2. La seconde boucle, à l'intérieur de la première, parcourt la seconde table et renvoie le flux des tuples de cette table, appariés avec tp.

   Écrivez cet algorithme dans le squelette de code suivant :

   def produit_cartesien(table1, table2):
       """Construit le flux de tuples obtenus en appariant tous les tuples de
       ~table1~ et de ~table2~.
   
       Ce flux correspond au produit cartésien des deux tables produit par l'algorithme double boucle :
       - ~table1~ est la table utilisée dans le boucle extérieure,
       - ~table2~ est la table utilisée dans la boucle intérieure.
       """
       yield {}
   

3. Un problème avec les flux en mémoire
   

   Exécutez le bloc de code suivant :

   tb1 = table({'a': (1,1)}, nb=2)
   tb2 = table({'b': (2,2)}, nb=2)
   for tp in produit_cartesien(tb1,tb2):
       print(tp)
   

   • Combien de tuples auriez-vous du obtenir ?
   • À votre avis, quel est le problème ?
4. Implémentation du produit cartésien à partir de tables contenues dans des fichiers
   

   Implémentez la fonction suivante pour des tables contenues dans des fichiers en évitant le problème observé dans la partie précédente.

   def produit_cartesien_fichier(fichier1, fichier2):
       """Construit le flux de tuples obtenus en appariant tous les tuples contenus
       dans les fichiers ~fichier1~ et ~fichier2~.
   
       Ce flux correspond au produit cartésien des deux tables contenues dans les
       fichiers produit par l'algorithme double boucle :
       - la table contenue dans ~fichier1~ est utilisée dans la boucle extérieure,
       - la table contenue dans ~fichier2~ est la table utilisée dans la boucle intérieure.
   
       """
       yield {}
   

   Exécutez le code ci-dessous pour vérifier que vous obtenez le bon comportement.

   tb = [table({'a': (1,1)}, nb=2), table({'b': (2,2)}, nb=2)]
   fichiers = ["/tmp/tb1.table", "/tmp/tb2.table"]
   for i in range(2): mem_sur_disque(tb[i], fichiers[i])
   for tp in produit_cartesien_fichier(fichiers[0],fichiers[1]): print(tp)
   

3.2.2 La jointure

1. Jointure theta
   

   Nous allons ici utiliser les fonctions selection et produit_cartesien_fichier pour calculer la jointure theta. Il s'agit de récupérer le flux des tuples de produit cartésien satisfaisant une certaine propriété.

   Complétez le code ci-dessous :

   def jointure_theta(fichier1, fichier2, pred):
       """Renvoie le flux des appariements de tuples contenus dans les tables des
       fichiers ~fichier1~ et ~fichier2~" qui satisfont la propriété du prédicat
       ~pred~ (fonction des tuples dans les booléens)."""
       yield {}
   

2. Jointure naturelle double boucle
   

   La jointure naturelle consiste à n'apparier que les tuples qui associent les mêmes valeurs à leurs attributs communs. En sql, cela correspond aux requêtes de la forme :

   SELECT * FROM table1 NATURAL JOIN table2;
   

   Complétez le code-ci-dessous :

   def jointure_naturelle(fichier1, fichier2):
       """Renvoie le flux des tuples de la jointure naturelle des tables contenues
       dans ~fichier1~ et ~fichier2~.
   
       Il s'agit des appariements des tuples provenant des tables contenues dans
       ~fichier1~et ~fichier2~ qui associent les mêmes valeurs à leurs attributs
       communs.
       """
       yield {}
   

3. Jointure naturelle/theta double boucle avec une (petite) table en mémoire
   

   Lors de l'exécution de l'algorithme double boucle, l'une des tables n'est lue qu'une seule fois alors que la seconde est lue plusieurs fois. Quelle est la table qui est lue plusieurs fois :

   1. La table parcourue dans la boucle extérieure ?
   2. La table parcourue dans la boucle intérieure ?

   Lorsque l'une des deux tables est suffisamment petite pour tenir en mémoire, il peut être plus efficace de la charger en mémoire. À votre avis, pour limiter le nombre d'accès au disque dur, quelle table vaut-il mieux charger en mémoire ?

   1. La table parcourue par la boucle extérieure ?
   2. La table parcourue par la boucle intérieure ?

   Nous allons utiliser cette idée pour implémenter l'algorithme double boucle en chargeant l'une des deux tables en mémoire. Complétez le code ci-dessous. Vous modifierez également la documentation pour préciser quel fichier est chargé en mémoire.

   def jointure_naturelle_mem(fichier1, fichier2):
       """Renvoie le flux des tuples de la jointure naturelle des tables contenues
       dans ~fichier1~ et ~fichier2~.
   
       L'un des deux fichiers est chargé en mémoire afin qu'il ne soit lu qu'une
       seule fois.
   
       Il s'agit des appariements des tuples provenant des tables contenues dans
       ~fichier1~et ~fichier2~ qui associent les mêmes valeurs à leurs attributs
       communs.
   
       """
       yield {}
   

4. La jointure avec une table indexée
   

   Nous allons maintenant nous intéresser à un type particulier de jointure. Des jointures qui se font avec la condition que deux attributs des tables à joindre aient la même valeur. Il s'agit de requêtes de la forme :

   SELECT * FROM table1 JOIN table2 ON table1.A = table2.B;
   

   Pour cette partie nous adoptons les hypothèses suivantes :

   1. pour simplifier, les deux tables utilisées n'ont pas d'attributs en commun.
   2. la colonne B de table2 est indexée.

   Afin de profiter de l'indexation de table2, nous pouvons parcourir table1 et pour chaque tuple chercher dans l'index les adresses physiques des tuples de table2 qui peuvent s'apparier avec ce tuple.

   En utilisant l'idée que nous venons d'esquisser, compléter la fonction ci-dessous. Pour rappel :

   • si index est un index pour la colonne col de la table contenue dans fichier et k est une clé de l'index, alors index[k] est la liste des adresses dans fichier des tuples qui à col associent la valeur k.
   • trouve_sur_disque(fichier, adr) renvoie le flux des tuples de fichier aux adresses contenues dans adr.

   def jointure_index(table1, col1, fichier2, index):
       """Renvoie le flux des tuples de la jointure de la ~table1~ et de la table
       contenue dans ~fichier2~ sous la condition que les valeurs de l'attribut
       ~col1~ de ~table1~ soient identiques aux valeurs de l'attribut ~col2~ la
       table de ~fichier2~.
   
       ~index~ est un index de l'attribut ~col2~ dans ~fichier2~.
       """
       yield {}
   

   NB : cet algorithme pourrait assez facilement se généraliser pour les jointure theta dans lesquelles l'une des conditions est l'égalité des valeurs des attributs A et B.

5. La jointure avec deux tables indexées
   

   Ici nous cherchons à résoudre la même requête que dans la question précédente avec l'hypothèse supplémentaire que nous disposons d'un index pour l'attribut A de table1. Au lieu de parcourir les tables, nous allons parcourir les deux index pour calculer la jointure.

   Compléter la fonction ci-dessous :

   def jointure_double_index(fichier1, index1, fichier2, index2):
       """Renvoie le flux de tuples obtenue par la jointure des tables contenues dans
        ~fichier1~ et ~fichier2~ avec la condition que les valeurs indexées par
        ~index1~ pour ~table1~ soient égaux aux valeurs indexées par ~index2~ pour
        ~table2~."""
       yield {}
   

6. La jointure par fusion de flux triés
   

   Nous poursuivons encore avec la même requête, mais cette fois, au lieu de supposer que nous disposons d'index pour les attributs sur lesquels porte la condition d'égalité, nous supposons que les tables sont triées dans l'ordre croissant selon la valeur des attributs concernés.

   Lorsque deux tables sont triées par rapport aux attributs sur lesquels on effectue la jointure, celle-ci est plus simple à calculer. On peut en effet parcourir chacune des tables en progressant suivant les valeurs des tuples. En particulier, cela permet de ne parcourir chaque table qu'une seule fois. Cela nous permet d'implémenter cette méthode de jointure directement sur des flux et non plus depuis des fichiers.

   Voici une description de l'algorithme que nous allons implémenter :

   1. nous allons charger en mémoire tous les tuples en tête de table1 qui associent la même valeur à l'attribut A,
   2. nous faisons de même pour les tuples en tête de table2 qui associent la même valeur à l'attribut B,
   3. suivant la façon dont se comparent la valeur de l'attribut A commune aux tuples de table1 en mémoire à celle de l'attribut B des tuples de table2 en mémoire, nous produisons les appariements, ou nous continuons d'avancer dans l'une des tables.

   NB : faites bien attention à ne pas oublier de tuples pour calculer la jointure. En particulier, il faut que les premiers tuples ayant une valeur différente de celle des tuples mémorisés lors des étapes 1. et 2. participent bien à la jointure. Pensez bien à les conserver en mémoire.

   Complétez le code ci-dessous :

   def jointure_triee(table1, col1, table2, col2):
       """Implémente la jointure de ~table1~ et ~table2~ sous la condition que les
       valeurs de l'attribut ~col1~ de ~table1~ soient égales aux valeurs de
       l'attribut ~col2~ de ~table2~.
   
       On suppose que ~table1~ est triée suivant les valeurs croissantes de ~col1
       et que ~table2~ est triée suivant les valeurs croissantes de ~col2~.
       """
       yield {}
   

3.3.1 Calcul du minimum

def minimum_table(table, col):
    """Renvoie la plus petite des valeurs associées à l'attribut ~col~ dans ~table~.
    Si ~table~ est vide, renvoie None.
    """
    return None

3.3.2 Calcul de moyenne

def moyenne_table(table, col):
    """Renvoie la moyenne des valeurs que les tuples de ~table~ associent à
    l'attribut ~col~.
    Si ~table~ est vide, renvoie None.
    """
    return None

3.3.3 Calcul d'écart type

def ecart_type_table(table, col):
    """Renvoie l'écart type des valeurs que les tuples de ~table~ associent à
    l'attribut ~col~.
    Si ~table~ est vide, renvoie None.
    """
    return None