[ABD] Sujets et Corrigés

Dans ce dossier, vous pouvez trouver les sujets d'examen et d'interrogation de l'année universitaire 2016/2016. Quelques solutions ne sont pas détaillées et nécessitent des explications; nous en reviendrons plus tard.

Dossier des sujets.

A. U : 2017/2018 :

Corrigés des mico-interros que nous n'avons pas eu la chance de corrigé en salle :

[ABD] Structure primaire du fichier : Hachage avec chaînage externe

Le fichier dans une base des données est vu comme une suite ou un ensemble d'enregistrements. Ces enregistrements sont répartis sur plusieurs blocs. Vu la différence entre la taille de la base des données et le buffer utilisé par le SGBD dans la mémoire centrale pour effectuer les différentes opérations, il est nécessaire de choisir l'organisation la plus adéquate pour limiter le nombre d'accès disque qui sont des milliers de fois moins rapide que les accès à la mémoire centrale.
Cet objectif peut être atteint en utilisant deux approches :

• Par jouer sur l'arrangement des enrtegistrements dans le fichier. En effet, l'approche la plus intuitive est de ranger les enregistrements dans l'ordre de leur arrivée. Cette approche est la moins performante si elle n'est pas associée à une autre approche : la recherche devient très coûteuse parce qu'il faut parcourir tout le fichier à chaque fois. Alors, il faut ranger les enregistrements d'une manière à limiter les accès disque et rendre la recherche plus efficace.
• Par l'ajout d'une structure secondaire. Cette structure n'aura pas comme rôle le stockage des données comme le fichier primaire mais elle facilitera l'accès à ces données. Les index sont un exemple de ces structures.

Dans cet exemple de core, nous visons à simuler l'utilisation du hachage : une méthode qui s'inscrit dans la première appoche. Le hachage range les enregistrements suivant la valeur de l'un de ses champs, appelé clé de hachage. Ainsi, la position du nouvel enregistrement à insérer n'est pas la prochaine position vide, mais, c'est la position donnée par la fonction de hachage sur la valeur de la clé du hachage (généralement la clé primaire) pour le nouvel enregistrement. Par conséquent, les deux opérations d'écriture et de lecture se limitent à un seul accès disque.
Cette approche a deux inconvénients majeurs :

• Il faut avoir, au préalable, une estimation sur les données à sauvegarder. Il est aussi nécessaire de réserver un certain nombre de blocs même si le fichier est vide.
• Les collisions (les conflits) : lorsque deux enregistrements différents auront la même positions (les deux clés de hachage donnent la même valeur), on parle d'une collision (conflit). La résolution des conflit (quelque soit la méthode) peut limiter les performances obtenues par l'utilisation du hachage.

Dans le code du projet, nous allons utiliser le chaînage externe pour résoudre les conflits. Cette solution consiste à créer une liste linéaire chaînée dans cahque position. Cette liste va contenir toutes les valeurs en collision. Pour lire d'avantage sur cette approche, vous pouvez vous référer au cours de M. Zegour par ici.
Le projet est construit sur une seule classe : Page. Cette classe nous permet de stocker des données (des enregistrements) et de faire la recherche (une recherche séquentielle rapide). La Page contient aussi un pointeur vers la Page suivante : cela peut être utilisé pour le chaînage ou bien, tout simplement, ignoré.

public class Page {
    
    /**
     * La taille de la page.
     * Le nombre des enregistrements que la page peut contenir (le facteur de blocage, bfr).
     */
    public static final int TAILLE = 2;
    
    /**
     * Le contenu de la page.
     * Dans cet exemple, le contenu est réduit à une simple valeur (la clé de hachage) mais, en réalité, on parle d'un
     * enregistrement complet.
     */
    public int[] contenu;
    
    /**
     * Le degrée de remplissage de la page.
     * Pour connaître est ce qu'une page est pleine ou pas.
     */
    public int placesOccupees;
    
    /**
     * Un pointeur vers la page suivante.
     * Ce pointeur est nécessaire pour créer des listes linéaires chaînées des pages.
     */
    public Page suivant;

    /**
     * Constructeur par défaut.
     */
    public Page() {
        contenu = new int[TAILLE];
        for (int i = 0; i < contenu.length; i++) {
            contenu[i] = -1;
        }
        placesOccupees = 0;
        suivant = null;
    }

    public int[] getContenu() {
        return contenu;
    }

    public void setContenu(int[] contenu) {
        this.contenu = contenu;
    }

    public int getPlacesOccupees() {
        return placesOccupees;
    }

    public void setPlacesOccupees(int placesOccupees) {
        this.placesOccupees = placesOccupees;
    }

    public Page getSuivant() {
        return suivant;
    }

    public void setSuivant(Page suivant) {
        this.suivant = suivant;
    }

    /**
     * Vérifie si la page contient une valeur ou pas.
     * @param valeur La valeur à rechercher dans la page.
     * @return Vrai si la page contient la valeur, faux autrement.
     */
    public boolean contient(int valeur){
        boolean contient = false;
        int i = 0;
        while(i < TAILLE && !contient){
            if(contenu[i] == valeur)
                contient = true;
            i++;
        }
        return contient;
    }
    
    /**
     * Ajouter une valeur à la page.
     * A la fin  de l'exécution, la page va contenir la valeur (soit elle l'a contenue dès le début ou bien après son ajout).
     * Si la page est pleine, la valeur faux est retournée pour indiquer que l'opération d'ajout à échoué.
     * @param valeur La valeur à ajouter à la page.
     * @return Vrai si l'opération d'ajout a réussi, Faux autrement.
     */
    public boolean ajouterValeur(int valeur){
        boolean reponse = false;
        
        if(contient(valeur))
            reponse = true;
        
        if(!contient(valeur) && placesOccupees < TAILLE){
            contenu[placesOccupees] = valeur;
            placesOccupees++;
            reponse = true;
        }
        
        return reponse;
    }
    
    /**
     * Une représentation du contenu de la page sous forme d'une chaîne de caractère.
     * Seulement le contenu est inclu.<br/>
     * Si la page suivante n'est pas null, elle sera aussi inclue. Le chaînage est représenté par le symbole "==>".
     * @return La chaîne qui représente la page.
     */
    @Override
    public String toString() {
        StringBuilder sb = new StringBuilder();
        
        sb.append("Page {\n");
        for (int i = 0; i < contenu.length; i++) {
            sb.append("\t" + contenu[i] + "\n");
        }
        sb.append("}");
        
        if(getSuivant() != null){
            sb.append(" == > " + getSuivant().toString());
        }
        sb.append("\n");
        
        return sb.toString();
    }
        
}

Le projet contient deux gestionnaires :

• Un gestionnaire séquentiel : qui range les enregistrements dans l'ordre de leur arrivée.
• Un gestionnaire qui utilise le hachage par chaînage externe.

Ce dernier voit chaque position comme une liste linéaire chaînée et tente d'ajouter la nouvelle valeur au fichier en commençant par la première page et en passant vers la page suivante en utilisant le pointeur "suivant".
Si on arrive à la fin de la liste (suivant == null) sans pouvoir ajouter l'élément, alors un nouveau noeud est ajouté à la liste et l'élément est ajouté à ce dernier noeud :

    public void ajouterValeur(int valeur) {
        int position = hach(valeur);
        Page page = pages[position];

        while(!page.ajouterValeur(valeur)){
            if(page.getSuivant() == null)
                page.setSuivant(new Page());
            page = page.getSuivant();
        }
    }

Le code source du projet peut être obtenu par ici. Dans ce projet, nous allons créer les deux gestionnaires, faire des insértion et ensuite effectuer des recherches (on recherche les même éléments. On peut voir rapidement que l'approche séquentielle peut atteindre 7 accès disques tant dit que l'appproche par hachage ne dépasse jamais 2 accès disques.
Il est possible d'exécuter directement le fichier jar du projet qui se trouve dans le dossier "dist":

java -jar ABD06.jar 

Si l'affichage est trop vite, il est possible de mettre la sortie du projet dans un fichier texte par la commande suivante.

java -jar ABD06.jar >> test.txt

[ABD] Gestion du buffer : FIFO vs. LRU

Le buffer est un espace mémoire dans la mémoire centrale (généralement, la RAM) qui est utilisé pour stocker temporairement les pages chargées à partir des fichiers qui constituent la base de données. Il est très similaire, dans son principe, au principe de pagination et de la mémoire virtuelle utilisées par les Systèmes d'Exploitation.
Il est utilisé parce que la taille de la base de données dépace largement l'espace disponible dans la mémoire centrale pour effectuer les différents traitements.
Néanmoins, le problème est beaucoup plus simple vu que la pagination concerne seulement des données et non pas un mélange de données et de traitements (les processus) tel qu'il est le cas avec les Systèmes d'Exploiatation. Pour cela, les algorithmes largement utilisés sont seulement deux : FIFO et LRU.
Les deux algorithme visent à choisir la page à remplacer lorsqu'on veut accéder à une nouvelle page et le buffer est plein (ne contient pas d'emplacements vides).
L'algorithme FIFO consiste à remplacer la page la plus ancienne. Il est intuitive et simple : lorsqu'une nouvelle page arrive, on remplace la page qui a passé le plus du temps dans la mémoire. Il est simple à implémenter : il suffit d'utiliser une structure de file simple. Néanmoins, il n'est pas adapté à un contexte de données. En effet, des données telles que les comptes des utilisateurs et leurs privilèges et droits d'accès sont chargées dès le lancement du système et doivent rester toujours disponibles.
L'algorithme LRU est notre deuxième algorithme et l'algorithme le plus utilisé dans le contexte des données. Il se base sur l'affirmation qui dit que : "Si on accède à une donnée à un instant t, il est très probable qu'on aura besoin d'accéder à la même donnée à un moment proche t + dt". Par exemple, il est possible de lire des informations d'un client pour lui vérifier son état financier pour ensuite lui accorder un nouveau crédit et qu'on aura besoin à nouveau de ses informations pour imprimer les états de sortie.
Pour implémenter ces deux algorithmes, plusieurs approches peuvent être suivies. Dans cet article, nous nous intéressons à une approche très simple qui n'utilise pas la structure de file mais sur un simple compteur associé à un tableau d'indices pour pouvoir connaître la page la plus ancienne dans le cas de l'algorithme FIFO ou bien la page la moins récemment utilisée dans le cas de l'algorithme LRU.
Entre les deux approches, quelques lignes de codes changent seulement. En effet, la différence réside dans la mise à jour de l'indice d'une page :

• Dans le cas de l'algorithme FIFO : l'indice prend sa valeur au moment de chargement de la page et ne change pas. Le compteur n'est incrémenté que dans le cas d'un défaut de page. La page avec l'indice le plus petit est la page la plus ancienne.

public void chargerPage(int numero) {

        // Recherche si la page est déjà chargée
        int i = 0;
        boolean trouve = false;
        while (i < pagesOccupees && !trouve) {
            if (pages[i] == numero) {
                trouve = true;
            } else {
                i++;
            }
        }

        if (trouve) {
            // On ne fait rien
        } else {
            
            // Voir est ce qu'il y a des places vides
            if (pagesOccupees < TAILLE_MEMOIRE) {
                
                pages[pagesOccupees] = numero;
                indices[pagesOccupees] = compteur;
                pagesOccupees++;

            } else {
                // Si le buffer est déja rempli

                // Recherche de l'indice minimale
                int valeurMin = indices[0];
                int positionMin = 0;
                for (int j = 0; j < indices.length; j++) {
                    if(indices[j] < valeurMin){
                        positionMin = j;
                        valeurMin = indices[j];
                    }
                }
                
                // On la remplace
                pages[positionMin] = numero;
                indices[positionMin] = compteur;
            }
            
            defautsDePage++;
            compteur++;
        }
}

• Dans le cas de l'algorithme LRU : le compteur doit garder trace de l'utilisation de la page et non pas du moment de son chargement ainsi le compteur est incrémenté à chaque opération d'accès même s'il ne s'agit pas d'un défaut de page et dans ce cas l'indice de la page est mis à jour même si la page est déjà dans le buffer. La page avec l'indice le plus petit est la page la moins récemment utilisée.

public void chargerPage(int numero) {

        // Recherche si la page est déjà chargée
        int i = 0;
        boolean trouve = false;
        while (i < pagesOccupees && !trouve) {
            if (pages[i] == numero) {
                trouve = true;
            } else {
                i++;
            }
        }

        if (trouve) {
            // L'unique différence entre FIFO et LRU
            // L'indice de la page est mis à jour et le compteur est incrémenté même si la page est déjà en mémoire.
            indices[i] = compteur;
            compteur++;
        } else {
            
            // Voir est ce qu'il y a des places vides
            if (pagesOccupees < TAILLE_MEMOIRE) {
                
                pages[pagesOccupees] = numero;
                indices[pagesOccupees] = compteur;
                pagesOccupees++;

            } else {
                // Si le buffer est déja rempli

                // Recherche de l'indice minimale
                int valeurMin = indices[0];
                int positionMin = 0;
                for (int j = 0; j < indices.length; j++) {
                    if(indices[j] < valeurMin){
                        positionMin = j;
                        valeurMin = indices[j];
                    }
                }
                
                // On la remplace
                pages[positionMin] = numero;
                indices[positionMin] = compteur;
            }
            
            defautsDePage++;
            compteur++;
        }
}

Le code complet peut être téléchargé par ici
Le dossier contient un projet NetBeans ouvrable, sinon, vous avez toujours la possibilité de construire un nouveau projet dans les autres éditeurs en utilisant le dossier "src".
Il est possible d'exécuter le jar directement, sans recompilation, il suffit d'utiliser la commande :

java -jar ABD05.jar 

Si vous pensez que l'affichage est un peu rapide, vous pouvez mettre la sortie dans un fichier texte si vous exécutez la commande suivante :

java -jar ABD05.jar >> test.txt

Le dossier ./dist/javadoc contient la documentation générée si vous voulez voir les différentes structures utilisées.
Le code contient un bug : les valeurs initiales sont des "0" à ne pas confondre avec la page numéro "0".

[ABD] Charte à respecter

Charte dactylographique et structure du rapport.

ABD [Mise à Jour - 2020 - CoVid-19] - Administration des Bases des Données (Présentation générale - Les présentations du cours)

"Montrer les tendances actuelles dans le domaine d'administration des bases des données".

[Java][BlueJ] Manipulation graphique des Classes et des Objets sous BlueJ

BlueJ est un excellent outil pour apprendre à programmer en Java. Nous avons déjà cité une excellente fonctionnalité qui permet d'exécuter un code Java sans se méfier de la fonction main et de la classe qui la contient.
Dans cet bref article, nous allons présenter quelques manipulations possibles grâce à l'éditeur graphique de BlueJ.
L'éditeur graphique de BlueJ permet de visualiser les différentes classes du projet en cours ainsi que les liens et les dépendances qui les relient. Il permet un affichage proche de celui de UML (il est possible d'installer une extension qui rend le diagramme confirme au diagramme des classes d'UML).
Les classes et les liens peuvent être créés graĉe aux outils disponibles à gauche. Ce panel contient quatre (04) commandes :

• Créer une nouvelle classe,
• Créer un lien d'héritage,
• Créer un lien d'utilisation,
• Compiler la(les) classe(s).

Prenons un exemple et créons une classe "Employe" (employé). Pour cela, il suffit de cliquer sur l'outil "New class". Une petite fenêtre s'affiche pour permettre de choisir le type de classe à créer (classe, interface, etc.) et de saisir le nom de la nouvelle classe. La classe créée est visualisée et mise en haut à droite de l'éditeur graphique.

Il est possible d'éditer le code de la classe en faisant un double-clique. Le code s'affiche dans une fenêtre séparée. Dans notre exemple, nous avons fait les modifications suivantes :

Cette même fenêtre permet d'afficher la documentation Javadoc générér pour la classe en cours. Il suffit de changer le mode d'affiche de "Source" à "Documentation" :

En deuxième étape, nous allons créer une deuxième classe appellée "Manager" et en utilisant l'éditeur graphique nous allons créer un lien d'héritage entre les deux classes "Employe" et "Manager".

En ouvrant l'éditeur du code, nous constatons que la mention "extends" est bien définie dans la déclaration de la nouvelle classe "Manager".

Il est possible de montrer le lien d'utilisation entre deux classes. Créons par exemple une nouvelle classe "Entreprise".

Pour cette entreprise, nous allons définir un attribut "m" qui est le "Manager" de cette entreprise :

En sauvegardant cette nouvelle classe et en revenant vers l'éditeur graphique, nous constatons que BlueJ a mis à jour le modèle en ajoutant le lien d'utilisation entre les deux classes "Entreprise" et "Manager".

L'éditeur graphique permet aussi quelques manipulations sur les classes créées. Ces manipulations nécessitent la compilation des classes par un clic sur la commande "Compile" à gauche de l'écran. Si une classe contient des erreurs, elle sera marquée par un point d'exclamation rouge.
Une fois les classes compilées, il est possible d'accéder aux différentes fonctionnalités par un clic-droite sur la classe concernée. Cela nous permet de :

• Invoquer les méthodes statiques,
• Invoquer les constructeurs pour créer des instances de la classe,
• Inspecter la classe : voir les différentes variables statiques et leurs valeurs.

Créons une instance de la classe "Employe". Pour cela, nous allons choisir le constructeur qui exige deux paramètres :

L'objet créé avec le nom choisi s'affiche en bas à gauche de l'écran dans la zone dédiée aux instances (objets) des classes.

Il est possible de l'inspecter :

Comme il est possible d'invoquer ses méthodes (les méthodes non statiques).
Si une méthode est invoquée et qu'elle retourne une valeur, elle est affichée dans une fenêtre séparée. A titre d'exemple, nous allons invoquer la méthode tatique "description" de la classe "Employe" :

BlueJ offre plusieurs autres fonctionnalités. La plus essentielle est la possibilité d'installer (et de développer) des extensions. Plusieurs extensions très performantes sont déjà disponibles, jetez un coup d'oeil par ici.
BlueJ se montre comme une solution très efficace (particulièrement pour les enseignants) pour l'apprentissage de la programmation en Java et pour l'apprentissage de la programmation Orientée Objet.

[Java] [BlueJ] Commencer avec Java sans passer par les Classes

Apprendre un premier langage de programmation n'est pas (toujours) une tâche facile. Il est important de saisir :

• Les notions de la programmation comme les variables, les constantes et les structures de contrôle.
• Les notions liées au langage utilisé. En effet, il est rare de trouver un langage qui respecte à la lettre les propositions théoriques sans avoir des caractéristiques particulières.

Dans ce sens, l'apprentissage de Java est lié, dans la majorité des universités (au moins Algériennes) à l'apprentissage de la programmation Orientée Objet. Les étudiants doivent assimiler des notions liées à la programmation Orientée Objet comme "la classe", "l'objet" et "l'instantiation", comme ils doivent saisir les notions liées au langage Java comme la fameuse fonction :

public static void main(String args[]){
}

Cette fonction qui doit faire part d'une classe.
Ainsi, il sera difficile, suivant cette approche, de séparer les notions de la programmation Orientée Objet des notions propres au langage Java.
La pratique suivie aujourd'hui est de demander aux étudiants de commencer par un exemple (le fameux "Hello World") sans chercher à comprendre les différents mots-clés utilisés, alors, l'étudiant va réussir à écrire un programme et de l'exécuter sans vraiment comprendre :

• public : et les principes d'encapsulation,
• static : et la différence entre des méthodes propres à la classe et des méthodes propres aux objets, et pour comprendre cette différence, il faut comprendre la notion d'instanciation et du mot-clé "new".
• String agrs[] : "pourquoi ce tableau est en paramètre? Quel est son rôle?"
• System.out.println : "pourquoi tous ces points? Est-ce un enregistrement?"

Ce problème peut être évité avec d'autres langages. En effet, si on veut créer le fameux Hello World dans le langage Pascal, il suffit d'écrire :

Program HelloWorld;
Begin
 WriteLn('Hello World');
End.

Dans ce cas, il n'est pas très difficile d'expliquer ou de justifier les quatre (04) mots-clés cités : Program, Begin, Write et End.

Une solution : BlueJ

Pendant les premiers chapitres, ce qui est demandé des étudiants est d'écrire des programmes pour manipuler les types des données, les variables et les structures de contrôle en modifiant à chaque fois le corps de la méthode main sans y toucher. La question qui se pose est : existe-t-il un outil qui permet de prendre un bout de code et de l'insérer dans une méthode main (ou autre) et de l'exécuter d'une manière transparente par rapport à l'apprenant? La réponse est, heureusement, Oui. BlueJ peut le faire.
BlueJ est un éditeur Java open source. Il permet de créer des projets Java, de les compiler et de générer la Javadoc. Il donne aussi la possibilité de faire une édition graphique des classes et de leurs dépendances en manipulant un diagramme des classes (proche de celui en UML).
Parmi les fonctionnalités offertes, nous trouvons un espace particulier appelé le Code Pad. En l'utilisant, nous pouvons exécuter des bouts de code Java sans se méfier de la création d'une classe et d'une méthode main là-dedans.

Il est ainsi possible de se concentrer sur les mots-clés et les notions de base avant de passer vers les notions plus complexes de la programmation Orientée Objet. En plus, la console est affichée dans une fenêtre séparée mais propre à l'éditeur ce qui évite de faire appel à des éditeurs plus lourds ou bien d'utiliser la ligne de commande.

Il est possible de créer, localement, des variables. Dans cet exemple, nous créons un entier nommé (x) qui prend la valeur 10 :

Chaque ligne est exécutée en la validant, malgré cela, il est possible de créer des bloques. Il suffit de ne pas valider la ligne par la touche "Entrée" et de faire un retour à la ligne par la combinaison "Shift+Entrée".

Il est possible de manipuler des objets de l'API standard. Pour cela, il faut mettre la déclaration complète vu qu'il n'est pas possible de faire un "import".

BlueJ permet aussi une manipulation visuelle des objets. Nous présenterons ces fonctionnalités dans un autre article.