Cours complet pour apprendre les systèmes de gestion de bases de données

Rappelez le fonctionnement d'une E/S disque et calculez le temps nécessaire en fonction de la vitesse de rotation et du temps de déplacement de bras unitaire. Fixez les paramètres à des valeurs correspondant aux technologies courantes.

Quel est le temps nécessaire pour exécuter les requêtes en attente suivant leur ordre d'arrivée (stratégie FIFO) ?

Déterminez les quatre meilleures permutations possibles des requêtes minimisant le temps d'E/S disques. Parmi ces quatre séquences, quelle est la meilleure ? Pourquoi ?

Donnez le principe d'un algorithme permettant de trouver la séquence optimale. Quel doit être son temps de réponse maximal pour qu'il puisse être utilisé ?

Calculez le temps nécessaire pour exécuter les cinq instructions d'E/S en attente en choisissant à chaque fois d'exécuter la requête la plus proche des têtes de lecture-écriture.

L'utilisation de disques RAID permet d'accélérer les E/S disques. Discutez des différents types de RAID et de leur intérêt pour accélérer les cinq requêtes.

Discutez le choix de la taille du paquet.

Proposez quelques fonctions de hachage afin de déterminer le numéro de paquet à partir du numéro de produit. Discutez de l'intérêt de ces fonctions selon le mécanisme d'attribution des numéros de produits.

Lorsqu'un paquet est plein, un produit devant être inséré dans ce paquet est écrit en débordement. Proposez différentes solutions pour la gestion des débordements. Pour chacune d'elles, calculez le nombre moyen d'entrées-sorties nécessaires pour écrire un nouvel article et lire un article existant.

On utilise le hachage extensible. Rappelez l'algorithme d'écriture d'un nouvel article et de lecture d'un article. Calculez le nombre d'entrées-sorties nécessaires pour écrire un nouvel article et lire un article existant.

Même question avec le hachage linéaire.

Rappelez la définition d'un arbre B et d'un arbre B+. Illustrez ces définitions en construisant un arbre B et un arbre B+ pour stocker l'alphabet dans des arbres d'ordre 2. Quel est l'intérêt d'un arbre B+ par rapport à un arbre B ?

Calculez le nombre de comparaisons de clés nécessaires à la recherche d'une lettre dans un arbre B et B+ d'ordre 2. Ce nombre est-il différent pour un arbre d'ordre 3 ?

Généralisez les résultats à un arbre d'ordre m contenant n clés.

Il est possible de comprimer les clés dans un arbre B ou B+ en enregistrant pour chaque clé seulement la différence par rapport à la précédente. Préciser alors le format de chaque entrée dans l'arbre B. Donnez les algorithmes de recherche et d'insertion d'une clé dans un arbre B ou B+ en prenant en compte la compression.

VSAM implémente les arbres B+ en essayant de les calquer à la structure des disques. Discutez de l'intérêt de cette approche et de ses inconvénients. Calculez le nombre d'entrées-sorties nécessaires pour lire un article dans un fichier avec un seul niveau d'index maître. Même question pour les insertions d'articles.

Une recherche dans un fichier simplement indexé par un arbre B sur une clé non discriminante (clé secondaire) peut être coûteuse. Pourquoi ? Proposez des approches pour réduire le temps d'entrées-sorties disques nécessaire.

Donnez l'arbre obtenu en partant d'une racine vide après insertion des articles de clé :

{Marcel, Marius, Martine, Maurice, Marcelle, Maude, Marc, Marguerite, Mathilde, Maxime, Marielle, Martial, Mariette, Marina, Matthieu, Mattias} dans l'ordre indiqué.

Donnez l'arbre obtenu si la liste des articles est triée selon l'ordre des clés :

{Marc, Marcel, Marcelle, Marguerite, Marielle, Mariette, Marina, Marius, Martial, Martine, Mathilde, Matthieu, Mattias, Maude, Maurice, Maxime}.

Proposez une procédure de construction de l'arbre B+ par construction directe des feuilles et des sommets intermédiaires à partir d'un fichier trié des articles.

On remarque que dans un arbre B+ les clés dans les sommets non-feuilles ne servent que d'aiguilleurs dans la recherche d'un article de clé donnée. On utilise cette remarque pour augmenter le nombre de couples clé/pointeur dans les sommets non-feuilles en remplaçant les clés par un préfixe de ces clés.

Donnez la règle qui permet de déterminer le plus petit préfixe possible qui conserve la propriété d'aiguiller correctement la recherche dans l'arbre.

Donnez l'arbre obtenu en utilisant des préfixes par insertions répétées comme dans la question 1.

Discutez les avantages et les inconvénients de cette méthode pour de petits fichiers et pour de grands fichiers.

Quels sont la meilleure méthode et le nombre correspondant d'entrées/sorties disques nécessaires pour répondre aux recherches suivantes :

• Q1. (A = "valeur")
• Q2. ("valeur" < A)
• Q3. (C = "valeur")
• Q4. (B = "valeur")
• Q5. ("valeur 1" < C < "valeur 2").
• Q6. (C = "valeur 1") ET (E = "valeur 2")

On suppose le fichier des vins indexés par un arbre B sur la clé secondaire DEGRÉ. Proposez un format d'entrée pour un tel index. Justifiez votre solution.

Les degrés étant nombreux car continus entre 0 et 20, comment peut-on réduire leur nombre ?

Proposez un algorithme permettant de répondre aux requêtes précisant DEGRÉ > $v, où $v désigne un réel compris entre 0 et 20.

Ce fichier est aussi indexé sur les clés secondaires CRU et MILLÉSIME. Proposez trois méthodes pour résoudre des requêtes du type CRU = $c AND MILLÉSIME = $m, l'une utilisant les deux index, les deux autres un seul ($c et $m sont deux constantes). Essayez d'estimer le coût en entrées-sorties de chacune d'elles. Donnez des heuristiques simples pour choisir l'une ou l'autre.

De manière générale, proposez un algorithme capable d'évaluer efficacement des recherches avec critères multiples conjonctifs (AND).

Étendre l'approche au cas de critères multiples connectés avec des AND et des OR.

Un fichier haché peut aussi être indexé selon plusieurs attributs. Comment peut-on améliorer l'algorithme précédent pour supporter aussi des fichiers hachés ?

On désire placer un fichier de lignes de commandes de format (NC, NP, TYPE, QUANTITÉ, PRIX) par hachage multiattributs. NC désigne le numéro de commande, NP le numéro de produit et TYPE le type du produit. Sachant que 50 % des recherches se font sur NC, 20% sur NP et 30% sur le type de produit, proposez des fonctions de hachage optimum afin de placer un tel fichier dans 100 paquets.

Proposez un algorithme général pour répondre aux requêtes multicritères précisant deux des attributs hachés parmi les trois, par exemple NC et TYPE.

Généralisez l'algorithme pour traiter des requêtes multicritères avec AND et OR, comme vu à l'exercice précédent.

Les fichiers hachés peuvent aussi être indexés par des arbres B. Discutez des formats d'adresses d'articles intéressants pour gérer les index en conjonction au hachage. Intégrez les résultats de l'exercice précédent à l'algorithme de la question 3. En déduire un algorithme général pour traiter des requêtes multicritères sur des fichiers hachés sur plusieurs attributs et indexés.

Précisez le format d'un index bitmap et des structures associées. Calculez la taille d'un tel index. Proposez des méthodes de compression pour un tel index.

Donnez les algorithmes d'insertion et suppression d'un enregistrement dans un fichier avec index bitmap.

Un index bitmap sur un attribut A est idéal pour accélérer des recherches sur critère de la forme :

A = $a0 OR A = $a1 OR … A = $an

Précisez l'algorithme de recherche.

On peut gérer plusieurs index bitmap pour un même fichier, sur des attributs A, B, etc. Précisez les types de critères pouvant être traités par des index bitmap.

On considère un fichier avec index bitmap et index secondaires sous la forme d'arbre B. Que doit référencer une entrée dans un index secondaire pour être combinable avec les index bitmap ? Donnez un algorithme général de recherche multicritères prenant en compte les index secondaires et les index bitmap.

Donnez le schéma CODASYL correspondant à ce diagramme.

Donnez le graphe des occurrences correspondant au plan simplifié, à trois rues (X, Y, Z) et quatre carrefours (C1, C2, C3, C4), suivant :

Donnez le programme en DML CODASYL permettant de trouver tous les carrefours avec feu de la rue Albert Einstein.

Donnez le programme en DML CODASYL permettant de trouver toutes les rues qui sont directement accessibles depuis la rue Albert Einstein (donc qui l'intersectent où s'y raccordent). Une rue n'est pas accessible si elle est en sens interdit.

Sachant que les poids lourds partent d'un dépôt situé dans la rue A, doivent rejoindre le client situé rue B et ne doivent circuler que dans des rues de largeur supérieure à 10 mètres, donner le programme en DML CODASYL et pseudocode qui recherche tous les itinéraires possibles en ne les donnant qu'une fois avec leur longueur et le nombre de feux. On précise que la partie pseudocode devra rester à un niveau de quelques blocs de commentaires et devra résoudre le problème de la détection des boucles.

Proposez un placement des types d'articles dans un ou plusieurs fichiers pour accélérer les performances. Donnez le nombre d'entrées-sorties disque nécessaires pour traiter la question 4.

Donnez le schéma réseau en DDL CODASYL correspondant au diagramme entité-association représenté figure 1. On précise que les entités PRODUITS et FOURNISSEURS sont rangées dans un même fichier FOU via le set VEND, alors que les instances de CLIENTS sont rangées dans le fichier CLI.

Écrire les programmes en DML CODASYL correspondant aux requêtes suivantes :

1. Nom des fournisseurs vendant des produits de type « informatique ».
2. Nom des clients ayant acheté de tels produits.
3. Noms des produits et liste des fournisseurs associés ayant vendu au client de N°SS 153300017012.
4. Chiffre d'affaires total réalisé avec le client Dupond Jules.

Utiliser du pseudo-Pascal ou pseudo-C si nécessaire.

Donnez un schéma relationnel pour la base de données représentée.

Exprimer en SQL les requêtes correspondant aux questions étudiées au 2.

Pour les schémas représentés, proposez un algorithme de traduction automatique de requête SQL de type restriction-projection-jointure en programme DML CODASYL. Pour cela, on traduira chaque requête en un arbre d'opérations de l'algèbre relationnelle optimisé de manière adéquate ; ensuite, on traduira des groupes d'opérateurs choisis en programmes DML avec du pseudo-PASCAL ou pseudo-C.

Étudiez le ré-engineering de la base réseau proposée en base relationnelle. Discutez des difficultés. Proposez une démarche.

Donnez le schéma de la base de données relationnelle représentant directement ce diagramme entité-association (une entité générant une relation, une association générant une relation), avec les clés et les contraintes référentielles nécessaires.

Exprimer en calcul de tuples les requêtes suivantes :

1. Donnez tous les attributs de S pour les tuples dont l'attribut C3 est compris entre 100 et 200.
2. Donnez les attributs C1 et C2 de S, E1 et E2 de T tels que les tuples de S et T soient associés par un tuple de ST1 d'attribut D1 supérieur à 10.
3. Même question, mais on souhaite en plus qu'il existe un tuple de R correspondant à chaque tuple de S sélectionné, via l'association RS, ayant un attribut A2 positif.
4. Donnez les tuples de T associés par RS à tout tuple de R et au moins à un tuple de T par ST1 ou ST2.

Exprimer ces mêmes requêtes en calcul de domaines.

Exprimer ces mêmes requêtes en QBE.

Exprimer ces mêmes requêtes en SQL.

Exprimer sous la forme d'un arbre de calcul de l'algèbre relationnelle les requêtes suivantes :

1. Donnez le nom, le prénom, la date de l'accident pour chaque personne blessée fatalement dans un accident du département 75 dans une voiture Citroën.
2. Trouver les personnes qui ont été blessées dans tous les accidents où elles étaient conductrices.

Que retrouve l'arbre algébrique suivant ?

Calculez le coût en entrées/sorties disques de l'arbre de la question précédente avec les hypothèses suivantes :

• La relation VÉHICULE comporte 1 000 000 tuples dont 850 sont des Honda Civic ; elle est placée par hachage statique sur le N°VÉH ; elle possède un index secondaire sur le TYPE qui est un arbre B⁺ à 3 niveaux.
• Les index secondaires du système utilisé retournent la clé primaire (ou clé de placement) et non pas directement l'adresse physique.
• La relation VÉHPART comporte 100 000 tuples ; elle est placée sous forme d'arbre B⁺ sur le N°ACC (index primaire).
• La relation BLESSÉ comporte 40 000 tuples dont 10 000 sont des blessés légers ; elle est placée en séquentiel avec un facteur de blocage (moyen) de 20 tuples par page.
• Les jointures sont faites par l'algorithme des boucles imbriquées.
• Tous les résultats intermédiaires tiennent en mémoire centrale ; une page de mémoire correspond à un bloc de disque.

Que devient le coût des entrées/sorties si la mémoire est limitée à m pages ?

Exprimez en algèbre relationnelle étendue les questions suivantes sur la base de données des jouets :

1. Donnez la liste des fabricants qui ont livré au moins un jouet de type A et de prix supérieur à 1 000 F ainsi que le nom des jouets correspondants livrés.
2. Donnez la liste des fabricants qui n'ont pas livré de jouets.
3. Donnez la somme des quantités livrées par chaque fabricant (caractérisé par NOMF et ADRESSE).

On se propose d'optimiser l'algorithme d'intersection de deux relations R1 et R2. Proposez trois algorithmes permettant de réaliser cet opérateur dans les cas sans index, respectivement basés sur :

1. le produit cartésien des deux relations ;
2. le tri des deux relations ;
3. le hachage des relations avec tableaux de bits.

En supposant qu'il existe trois tampons d'une page en mémoire, que les relations comportent respectivement r1 et r2 pages (r1 < r2) et que la relation intersection est composée de i pages, calculez approximativement le coût en E/S de chaque algorithme. On supposera que les tableaux de bits tiennent en mémoire et qu'ils permettent d'éliminer un pourcentage b des tuples de la deuxième relation.

On se propose d'étudier l'algorithme de groupage d'une relation R. Proposez trois algorithmes permettant de réaliser cet opérateur dans les cas sans index, respectivement basés sur :

1. la comparaison des tuples de la relation (proche du produit cartésien) ;
2. le tri de la relation ;
3. le hachage de la relation avec comparaisons internes aux paquets.

En supposant qu'il existe trois tampons d'une page en mémoire, que la relation comporte r pages et que la relation groupée est composée de g pages, calculez approximativement le coût en E/S de chaque algorithme.

Exprimer la question suivante en SQL sur la base de données des jouets :

Donnez les chiffres d'affaires de chaque fabricant (caractérisé par son NOMF et son ADRESSE) de poupées (NOMJ LIKE « Poupée »).

Exprimer cette question en algèbre relationnelle étendue.

Donnez un arbre d'opérateurs d'algèbre relationnelle optimisé permettant de calculer la réponse à cette question. On ajoutera pour cela l'opérateur de groupage (noté par un rectangle) aux opérateurs classiques.

Proposez sous la forme d'un graphe un ensemble de clés étrangères pour cette base de données.

Exprimer en algèbre relationnelle puis en SQL les requêtes suivantes :

1. références des articles de type 'électroménager' en rayon au second étage,
2. nom des employés travaillant dans un rayon proposant des articles de type jouet pour une quantité totale supérieure à 1 000.

Exprimer en SQL les requêtes suivantes :

1. nom des employés qui gagnent plus que leur responsable,
2. étages qui ne vendent que des vêtements.

Exprimer en calcul de tuple puis en SQL la requête suivante :

1. nom et salaire du responsable le mieux payé.

Indiquez les clés étrangères éventuelles de chaque relation.

Donnez les expressions de l'algèbre relationnelle qui permettent de calculer les requêtes suivantes :

1. Nom des planchistes de niveau 'Confirmé' qui ont navigué le '20/07/99' sur un spot où le vent moyen était supérieur à force 4 sur une planche de moins de 2,75 m.
2. Nom des planchistes qui ne sont pas sortis le '20/07/99'.
3. Nom des planchistes qui ont essayé tous les types de planches de la marque 'FANA-BIC'. On suppose que tous les types sont dans la relation MATOS.

Donnez les expressions de calcul de tuples correspondant aux trois requêtes précédentes.

Donnez les ordres SQL correspondant aux requêtes suivantes :

1. Nom des planchistes qui ont essayé tous les types de planches de la marque 'FANA-BIC'. On suppose que tous les types sont dans la relation MATOS.
2. Pour chaque spot de la base, en indiquant son nom, donner le nombre de jours de vent au moins de force 4 pour l'année 94.
3. Pour chaque marque de matériel représentée par au moins 10 planches, indiquer le nombre d'utilisateurs 'Confirmé' ou 'Expert'.

Donnez le nom des clients et le nombre de personnes correspondant pour les réservations de l'hôtel « Bellevue » à « Courchevel ».

Pour chaque station de Haute-Savoie, donner le nombre de lits en catégorie « trois étoiles ».

Pour chaque station de Haute-Savoie, donner le nombre de chambres réservées le samedi 11/02/95.

Quels sont les noms des hôtels de catégorie « deux étoiles » de « Méribel » qui sont complets la semaine du 12/02/2000 au 18/02/2000 ?

Quelles sont les régions dont toutes les stations sont à plus de 1500 m d'altitude ?

Quels sont les clients qui sont allés dans toutes les stations du « Jura » ?

Exprimer en SQL les requêtes suivantes sur la base :

• Q1. Quelles sont les frises du troisième siècle ? Donnez leur numéro et leur description.
• Q2. Même question avec en plus le nom du musée où elles sont exposées.
• Q3. Noms et prénoms des auteurs d'ouvrage(s) référençant des objets de la civilisation Dorienne.
• Q4. Quelles statues sont exposées dans la ville où elles ont été découvertes ? Donnez le numéro et la description.
• Q5. Donnez le nom actuel des villes (s'il en existe) dont le nom actuel est le même que le nom ancien d'une autre ville.
• Q6. Donnez le nombre de statues trouvées dans chaque site de la civilisation phénicienne.
• Q7. Quels sont les sites d'Athènes qui ont fourni plus d'objets que le site 5 n'en a fournis ?
• Q8. Noms et prénoms des auteurs des ouvrages qui référencent tous les objets trouvés dans le site 2 de Thèbes.

Soit la requête SQL suivante :

SELECT P.TITRE, P.DATE
FROM   PUBLICATION P, AUTEUR A, COOPERATION C,
       REFERENCE R, OBJET O, MUSEE M
WHERE  A.NOM = 'Vieille'
   AND A.PRENOM = 'Pierre'
   AND A.NUM-AUT = C.NUM-AUT
   AND C.NUM-PUB = P.NUM-PUB
   AND P.EDITEUR = 'Éditions archéologiques modernes'
   AND P.NUM-PUB = R.NUM-PUB
   AND R.NUM-OBJ = O.NUM-OBJ
   AND O.TYPE = 'Mosaïque'
   AND O.NUM-MUSEE = M.NUM-MUSEE
   AND M.NOM = 'Le Louvre'

Proposez deux arbres algébriques différents pour exécuter cette requête. Le premier arbre sera optimisé au mieux en utilisant les heuristiques de restructuration algébrique et le second sera le pire possible.

On suppose qu'il y a dans la base 10 000 publications, 100 éditeurs distincts, 1 000 auteurs de noms différents (pas d'homonymes), 2000 coopérations, 100 000 objets, 200 types d'objets différents, 1 000 000 de références et 100 musées de noms différents (pas d'homonyme).

On suppose de plus que toutes les distributions sont uniformes et indépendantes.

En prenant comme unité de coût la comparaison pour les sélections et les jointures, en supposant qu'il n'y a pas d'index et en admettant que toutes les jointures se font par produit cartésien, calculer le coût d'exécution des deux arbres que vous avez proposés.

Si vous étiez autorisé à créer un seul index pour accélérer cette requête, lequel choisiriez-vous ? Pourquoi ?

Définir en SQL2 les contraintes d'intégrité suivantes :

1. La qualité d'un nageur est excellente, bonne ou médiocre (contrainte de domaine).
2. Toute baignade a été effectuée par un nageur existant dans la base sur une plage existante (contraintes référentielles).
3. Le type et la région d'une plage déterminent sa pollution de manière unique (dépendance fonctionnelle).
4. La somme des durées des baignades d'un nageur par jour ne doit pas excéder deux heures.

Précisez quels types de contraintes d'intégrité peuvent être vérifiées après chaque ordre de mise à jour (INSERT, DELETE, UPDATE) ceux qui nécessitent d'attendre la fin de transaction.

Proposez des algorithmes pour traiter chaque type de contraintes d'intégrité, soient exécutés après la mise à jour, soient en fin de transaction. Montrer qu'il est possible de combiner les deux types de vérification.

Les contraintes avec agrégats comme la somme des durées des baignades sont coûteuses à vérifier à chaque mise à jour. Proposez une méthode basée sur des données redondantes afin de réduire ce coût.

Donnez la définition de FILM en SQL2 en précisant les contraintes de domaine, de clé (primaire ou candidate), et de clé étrangère.

Même question pour GÉNÉRIQUE si on suppose qu'un acteur peut jouer plusieurs rôles dans un même film.

Exprimer la contrainte généralisée suivante : « Le budget d'un film doit être supérieur à la somme des salaires des acteurs jouant dans ce film ».

Écrire un déclencheur qui met à jour automatiquement le numéro de film dans toutes les relations où il est utilisé si ce numéro est modifié dans la relation FILM.

On ajoute un attribut NBSALLES à FILM qui indique le nombre de salles où le film est actuellement visible.

Utiliser des déclencheurs pour gérer automatiquement ce nombre de salles.

Définir les vues VENTEPRO (NC,NP,NV, QTEV, PRIXU) et VENTETOT (NC, PRIXT) spécifiées comme suit :

• VENTEPRO donne pour chaque client, pour chaque produit et pour chaque vente la quantité de produit vendu et le prix unitaire du produit correspondant.
• VENTETOT donne pour chaque client le montant total en francs (PRIXT) des ventes effectuées.

On écrira les questions SQL permettant de créer ces vues à partir des relations de base.

Montrer que la vue VENTETOT peut être définie à partir de la vue VENTEPRO. Donnez sa définition en SQL à partir de VENTEPRO.

On introduit un opérateur partitionnement représenté par un rectangle préparant l'application du GROUP BY sur une relation, utilisable dans les arbres relationnels ; cet opérateur partitionne horizontalement la relation sur les attributs paramètres en effectuant simplement un tri sur ces attributs : il s'agit donc en fait d'un opérateur de tri. En addition, on permet l'usage de fonctions agrégats et arithmétiques dans les projections. Appliquées aux relations partitionnées suite à l'opérateur précédent, les fonctions agrégats accomplissent les calculs d'agrégats selon le dernier partitionnement effectué.

Donnez l'arbre relationnel optimisé permettant de retrouver les clients ayant acheté pour plus de 10 000 F de produits avec la liste des produits qu'ils ont achetés.

La modification de questions sur des vues (avec ou sans agrégat) ne permettant pas toujours d'optimiser, une autre méthode d'implantation de vues peut être basée sur la matérialisation de la vue comme une relation implantée sur disque (vue concrète). Le problème qui se pose est alors de mettre à jour la vue concrète lors des mises à jour des relations de base. Une technique possible consiste à générer des déclencheurs (triggers).

Exprimer en SQL les déclencheurs permettant de maintenir les relations VENTEPRO et VENTETOT lors de l'insertion d'un nouveau produit ou d'une nouvelle vente dans la base.

De manière générale, préciser les règles à générer pour maintenir une vue lors d'insertions dans une relation de base. On pourra considérer les cas suivants :

1. La vue est sans agrégat, c'est-à-dire issue de projection, jointure et restriction des relations de base.
2. La vue est avec agrégat.

Donnez les règles permettant de maintenir les relations VENTEPRO et VENTETOT lors d'une suppression d'un produit ou d'une vente dans la base.

De manière générale, préciser les règles à générer pour maintenir une vue sans agrégat, puis avec agrégat, lors d'une suppression dans une relation de base. Discutez selon les cas. Préciser les attributs qu'il est nécessaire de rajouter à la vue afin d'être capable de gérer correctement les suppressions.

Donnez les commandes SQL permettant de créer les vues suivantes :

BUVEURSB (NB, NOM, PRENOM, NV, DATE, QUANTITE)

décrivant les buveurs de Beaujolais,

VINSB (NV, CRU, MILLESIME, DEGRE)

décrivant les vins de Beaujolais bus par au moins un buveur.

Il est précisé que la vue VINSB est mettable à jour et que l'on souhaite la vérification des tuples insérés dans la vue par rapport au reste de la base.

Un utilisateur ayant droit d'interroger à partir des vues précédentes pose la question suivante :

« Donnez le nom des buveurs ayant bu du Beaujolais de millésime 1983 en quantité supérieure à 100, le même jour ».

Exprimez cette question telle que doit le faire l'utilisateur en SQL. Exprimez également la question modifiée portant sur les relations BUVEURS, VINS et ABUS que traitera le système.

De manière générale, proposez en quelques boîtes, sous la forme d'un organigramme, un algorithme permettant de transformer une question posée sur une vue en une question exprimée sur la base.

À partir de l'exemple, découvrir et énoncer quelques problèmes soulevés par la mise à jour à travers une vue référençant plusieurs tables :

1. Ajout d'un tuple dans BUVEURSB ;
2. Suppression d'un tuple dans BUVEURSB.

Exprimez cette requête :

1. en calcul relationnel de domaine ;
2. en calcul relationnel de tuple ;
3. en SQL.

Représentez la question sous forme d'un arbre d'opérations algébriques.

Proposez un arbre optimisé par restructuration algébrique pour cette question.

Soit v, d et s les tailles respectives en tuples des relations VILLE, DEPARTEMENT et SPECIALITE. En supposant l'uniformité des distributions des valeurs d'attributs, calculez une approximation de la taille du résultat de la question précédente en nombre de tuples. On pourra introduire tout paramètre supplémentaire jugé nécessaire.

Donnez les arbres algébriques relationnels optimisés par les heuristiques classiques des BD relationnelles (descente des projections et restrictions) permettant d'exécuter cette question.

On choisit l'arbre qui effectue les jointures dans l'ordre R1 avec R2 puis avec R3. En considérant l'utilisation d'un algorithme de jointure par produit cartésien (boucles imbriquées), calculez le temps d'exécution en nombre d'E/S de cet arbre en fonction de la taille en page des relations R1, R2 et R3, du nombre moyen de tuples par page T, du nombre de valeurs distinctes et non distinctes des attributs utilisés. On supposera pour cela une distribution uniforme des valeurs d'attributs. Tout paramètre supplémentaire jugé nécessaire pourra être introduit.

Proposez un ensemble d'index plaçants et non plaçants optimaux pour la base de données et la question considérée.

Calculez alors le temps d'exécution de la question.

On pourra supposer pour simplifier que tous les index sont à deux niveaux et on négligera les temps de calcul.

On considère alors la question :

SELECT U2,V2
FROM R1, R2, R3
WHERE R3.U1 = R2.V2 AND R2.V1 = R1.T1 AND R3.U3 = 100.

Donnez tous les arbres relationnels effectuant les projections dès que possible permettant d'exécuter cette question.

Calculez le coût en nombre d'entrées-sorties des trois arbres effectuant la restriction d'abord dans le cadre d'un SGBD relationnel implémentant les restrictions par balayage et les jointures par parcours d'index ou boucles imbriquées. On précise qu'il existe un index sur les clés U1 de R3 et V1 de R2 et pas d'autre index. La taille de chaque relation R1, R2 et R3 est respectivement r1, r2 et r3. On supposera une distribution uniforme des valeurs d'attributs. Le nombre de valeurs distinctes d'un attribut est obtenu par la fonction DIST (par exemple, DIST(U2) est le nombre de valeurs distinctes de U2). Ce nombre peut être calculé.

Même question avec des jointures par hachage.

Avec un algorithme par hachage ou par boucles imbriquées, il est possible de commencer une jointure avant d'avoir fini la précédente. Expliquez ces algorithmes dits de type pipeline.

Dans quel cas est-il intéressant d'utiliser un algorithme de type pipeline ?

On généralise ce type de requêtes à N relations Rn, Rn-1, …, R1. Donnez la forme générale d'une requête. Calculez le nombre de plans possibles pour une telle requête.

Proposez un algorithme en pseudocode, utilisant au mieux l'index de jointure, permettant de répondre à la question (bêta est une constante et il n'y a pas d'index sur V2) :

SELECT U.U2
FROM U, V
WHERE U1 = V1 AND V2 = beta

Calculez le coût en nombre d'entrées-sorties de cet algorithme en fonction des tailles de U et de V (respectivement u et v tuples), de la sélectivité de la jointure (j), de la taille de l'identifiant (i octets), de la taille du paquet de hachage pour UV (1 paquet = 1 page de p octets) et du taux de remplissage moyen du paquet (dénoté t).

On suppose que le système gère un index de U sur U1 et de V sur V1 à la place de l'index de jointure. Détailler l'algorithme pour répondre à la question précédente en utilisant la jointure par index. Calculez le coût d'une telle jointure. On précise que :

1. le nombre d'octets occupés par chaque valeur de U1 ou U2 est dénoté a ;
2. le nombre de valeurs distinctes de U1 est DIST(U1), celui de U2 est DIST(U2) ;
3. les index sont des arbres B+ à deux niveaux (feuille + racine).

Comparer à la solution index de jointure vue en 1.

Donnez en UML la définition d'un schéma objet équivalent à cette base relationnelle. Exprimez ce schéma en ODL.

Puisque DOCTEUR et INFIRMIER sont des EMPLOYEE, proposez un nouveau schéma objet utilisant l'héritage pour la base hospitalière.

Exprimez en OQL la requête suivante : « Nom et prénom des cardiologues soignant un malade Parisien (dont l'adresse contient 'Paris') dans le service de 'Chirurgie générale ».

Essayez de simplifier le schéma objet en introduisant des attributs multivalués. Proposez des requêtes OQL utilisant des collections dépendantes.

Discutez de l'intérêt de choisir un SGBD objet ou objet-relationnel. Effectuez un choix.

Complétez la représentation UML de la base en précisant les cardinalités des associations.

Définir le schéma de la base en C++. Bien lire le texte et la question 4 afin de prévoir les structures et méthodes capables d'y répondre.

Écrire des programmes C++ naviguant dans la base et répondant aux requêtes suivantes :

• Q1 : Nom du père Noël qui vous a visité et prix total des jouets que vous avez reçus à Noël (on suppose que vous êtes un enfant).
• Q2 : Distance parcourue par le père Noël Georges Gardarin et liste des jouets distribués.
• U1 : Mettre à jour la base par enregistrement d'une nouvelle tournée pour un père noël donné.

Proposez une représentation objet de ce schéma en utilisant UML. Discutez les propriétés de votre représentation. Donnez la définition en ODL correspondante.

Écrire les méthodes nécessaires pour faire une affectation d'une pièce à un modèle d'avion avec l'indication de la liste des ingénieurs chargés du suivi. Les méthodes seront écrites en Smalltalk, C++ ou Java persistant (ODMG) ou en pseudocode pour ceux qui ne sont pas à l'aise avec les concepts de l'un de ces langages objet. Attention à l'encapsulation.

Certaines pièces sont en fait des modules composés d'autres pièces ou d'autres modules. Proposez une modification du schéma pour Pièce.

Écrire une méthode qui donne la liste de tous les ingénieurs impliqués dans le suivi d'un module, soit directement soit au titre d'un composant. On pourra utiliser la méthode prédéfinie union de la classe générique Set qui prend un autre Set en paramètre.

Rappelez les extensions nécessaires à l'algèbre relationnelle pour exprimer les requêtes objet. Proposez des exemples génériques de requêtes illustrant chaque extension.

Soit une succession de classes T1, T2, …, Tn reliées par des associations [M-N] via des attributs de rôle nommés A, B, …, X, comme représenté ci-dessous :

Quels algorithmes proposeriez-vous pour traiter efficacement la requête SQL3 de parcours de chemins :

SELECT *
FROM C1, C2, … Cn
WHERE C1.A = OID(C2)
  AND C2.B = OID(C3)
  …
  AND Cn-1.X = OID(Cn) ?

On pourra aussi exprimer cette requête en OQL.

Proposez une définition du schéma de la base en ODL.

Exprimer les questions suivantes en OQL :

• Q1. Sélectionner les noms, pays, populations et surfaces des régions de plus de 10 000 km² et de moins de 50 000 habitants.
• Q2. Dessiner les cartes des régions traversées par la RN7.
• Q3. Donnez le nom des régions, dessinez régions et forêts pour toutes les régions traversées par une route d'origine PARIS et d'extrémité NICE.

Rappelez les opérations d'une algèbre d'objets complexes permettant d'implémenter le langage OQL. Donnez les arbres algébriques correspondants aux questions Q1, Q2 et Q3.

Proposez un schéma UML pour cette base de données. On ajoutera les méthodes appropriées pour illustrer. On supprimera tous les pointeurs cachés (clés de jointures) qui seront remplacés par des associations. Définir ce schéma directement en SQL3, en utilisant des références et des collections imbriquées.

Exprimer en SQL3 les questions (a), (b), (c) et (d).

Comparer l'implémentation objet-relationnelle avec une implémentation directe en relationnel.

Reprendre les questions 1, 2 et 3 en utilisant ODL et OQL à la place de SQL3. Comparer les solutions.

Définir cette base en ODL puis en SQL3.

Exprimer les requêtes suivantes en OQL puis SQL3 :

• Q1  : Nom du père Noël qui vous a visité et prix total des jouets que vous avez reçus à Noël (on suppose que vous êtes un enfant).
• Q2  : Distance parcourue par le père Noël Georges Gardarin et liste des jouets distribués.

Pour chacune des questions précédentes, proposez un arbre algébrique optimisé permettant de l'exécuter.

Rappelez la définition d'un index de chemin. Proposez deux index de chemins permettant d'accélérer l'exécution des questions Q1 et Q2.

Exprimer en OQL les questions suivantes :

• Q1  : ensemble des numéros de sécurité sociale et noms de personnes âgées de plus de 40 ans possédant au moins un véhicule de couleur rouge.
• Q2  : liste des noms de compagnies employant des personnes de plus de 40 ans possédant une voiture rouge.

Donnez un arbre d'opérations d'algèbre d'objets complexes optimisé par heuristique simple permettant d'exécuter la question Q2.

La jointure de deux classes C1 et C2, telles que Personnes et Voitures reliées par une association orientée multivaluée du type A—>>C1 peut être réalisée par un algorithme de parcours de pointeurs ou de jointure sur comparaison d'identifiant classique. Nous les appellerons « jointure avant JV » (par pointeur) et « jointure arrière JR » (par valeur). Détailler ces deux algorithmes en pseudocode.

On constate que la jointure de N classes reliées par des associations peut être réalisée par un seul opérateur de jointure n-aire, traversant le graphe en profondeur d'abord, appelé ici DFF. Détailler cet algorithme en pseudocode.

En dénotant page(Ci) et objet(Ci) le nombre respectif de pages et d'objets d'une classe Ci, par fan(Ci, Cj) le nombre moyen de pointeurs par objet de Ci vers Cj, en supposant un placement séquentiel sans index des objets, calculez le coût de chacun des algorithmes JR, JV et DFF. On pourra introduire d'autres paramètres si nécessaire.

Donnez l'arbre algébrique correspondant à la requête : quels sont les enfants de M. Martin, de numéro 152487.

Donnez l'arbre algébrique correspondant à la requête : quels sont les petits-enfants de M. Martin, de numéro 152487.

Donnez l'arbre algébrique étendu correspondant à la requête : quels sont les descendants de M. Martin, de numéro 152487.

Pour cette dernière question on étendra les arbres algébriques de la façon suivante :

• un nœud supplémentaire de test permettra de spécifier un branchement conditionnel ;
• une boucle dans l'arbre sera autorisée ;
• un test pourra porter sur le résultat de l'opération précédente, par exemple (résultat = vide ?).

Attention à la condition d'arrêt du calcul.

Soit le programme DATALOG :

• p1(X,X) ← p2(X,Y)
• p2(X,Y) ← p3(X,X), p4(X,Y)

et la base de données :

• p3(a,b), p3(c,a), p3(a,a), p3(c,c), p4(a,d), p4(a,b), p4(b,c), p4(c,a).

XXIV-37-1-1. Question 1▲

XXIV-37-1-2. Question 2▲

Soit le programme DATALOG :

• anc(X,Y) ← par(X,Y)
• anc(X,Y) ← anc(X,Z), par(Z,Y)

la base de données :

• par(baptiste,léon), par(léon,lucie), par(janine,léon), par(étienne,cloé),
• par(lucie,cloé), par(baptiste,pierre), par(janine,pierre), par(pierre,bernard),
• par(bernard,nicolas), par(bernard,lucien), par(bernard,noémie), par(lucien,éric).

et la requête :

• ? anc(bernard,Y)

XXIV-37-2-1. Question 1▲

XXIV-37-2-2. Question 2▲

XXIV-37-2-3. Question 3▲

Écrire un programme DATALOG calculant la relation :

DIRIGE(NSSC, NSSD)

donnant quel employé dirige directement ou indirectement quel autre employé (le numéro de sécurité sociale NSSC dirige le numéro de sécurité sociale NSSD), ceci pour tous les employés.

Transformer le programme DATALOG obtenu à la question 1 en appliquant la méthode des ensembles magiques pour trouver les employés dirigés par Toto.

Modifier le programme trouvé à la question 1 pour calculer la relation

DIRIGE(NSSC, NSSD, NIVEAU)

NIVEAU est le niveau hiérarchique du chef (1 chef direct, 2 chef du chef direct, etc.). Dans quel cas ce programme a-t-il un modèle infini ?

Donnez le graphe Règle-But et le graphe d'opérateurs relationnels correspondant à la question ? DIRIGE(Toto, x, 2) pour le programme trouvé en 3.

Écrire en DATALOG avec ensemble la question permettant de calculer la table

STATISTIQUE (NSER, CHEF, SALMAX, SALMIN, SALMOY)

donnant pour chaque service, le nom du chef, le salaire maximum, le salaire minimum et le salaire moyen, ceci pour tous les services dont le salaire minimum dépasse 7 000 F.

En utilisant les ensembles magiques, donnez le programme de règles transformées permettant de calculer la réponse à cette question.

Simplifier le programme obtenu par élimination des règles redondantes. Peut-on proposer une méthode générale permettant d'éviter de transformer des règles redondantes ?

Donnez un programme DATALOG avec fonctions (utiliser en particulier les fonctions OID et DRAW) permettant de générer et tracer tous les parcours allant de la ville de nom A à la ville de nom B en parcourant moins de K km.

Discutez de l'optimisation de ce programme.

On désire calculer le coût d'un billet de train. Le coût est proportionnel au nombre de km parcourus. Il existe des billets normaux, des billets réduits, des billets T.G.V., et des billets T.G.V. réduits. La majoration sur les lignes T.G.V. est un coût de réservation initial plus un coût proportionnel à la longueur du trajet. La réduction est un pourcentage du prix appliqué au seul coût proportionnel à la distance parcourue. Proposez une organisation en classes et sous-classes pour les billets de train. Programmer en pseudo C++ une méthode TARIF qui calcule le prix de chaque billet. On précise qu'il est possible d'appeler une méthode d'une classe (qui peut être une superclasse) par la syntaxe classe::méthode (…).

Proposez une intégration de la méthode TARIF dans le programme réalisé à la question 1 afin de calculer le prix de chaque itinéraire de moins de x km permettant d'aller de A à B et de choisir le moins coûteux.

Dessiner le graphe de précédence. Que peut-on en conclure ?

On suppose que les demandes se font dans l'ordre global suivant :

E2(A) L2(B) L6(D) E5(C) E3(A) L5(A) L1(C) L2(D) L3(C) E4(C) E3(D)
L4(B) L1(B)

Aucune transaction n'a relâché de verrous. L'algorithme utilisé est le verrouillage deux phases. Donnez le graphe d'attente. Que se passe-t-il ?

On rappelle que pour l'algorithme d'estampillage multiversion, les accès doivent être effectués dans l'ordre des estampilles des transactions, sauf les lectures qui peuvent se produire en retard. Une lecture en retard obtient la version qu'elle aurait dû lire si elle était arrivée à son tour. Les écritures en retard provoquent par contre un abandon de transaction.

Toujours avec l'ordre des accès de Q2, que se passe-t-il en estampillage multiversion ?

Pour gérer le multiversion, on suppose que l'on dispose d'une table en mémoire pouvant contenir 100 000 versions avec les estampilles correspondantes (pour l'ensemble des granules). De plus on conserve sur disque la dernière version produite de chaque granule.

On se propose de modifier l'algorithme d'estampillage multiversion de la façon suivante : chaque nouvelle version d'un granule mis à jour est écrite sur disque tandis que la version précédente est recopiée dans la table en mémoire. Cette table est gérée comme une file circulaire : chaque nouvelle version entrée chasse la version la plus ancienne (tous granules confondus). Lors d'une lecture, on recherche dans la table (ou sur disque) la version nécessaire si elle est disponible. Une lecture peut donc échouer et conduire à un abandon.

Donnez en pseudocode les algorithmes LIRE et ÉCRIRE correspondants.

Donnez un exemple d'exécution simultanée des transactions T1 et T3 non sérialisable. Tracer le graphe de précédence associé.

Montrer que la commutativité de l'opération d'addition garantit la correction de toute exécution simultanée de T1 et T2.

La commutativité des opérations permet donc d'accepter des exécutions simultanées non a priori sérialisable. On se propose de munir chaque classe persistante d'un contrôleur de concurrence utilisant une matrice de commutativité des opérations et un vecteur d'opérations en cours par transaction.

Définir les primitives nécessaires à un tel contrôle de concurrence.

Préciser les algorithmes sous-jacents.

Que fait ce programme ? Précisez le début et la fin de la (des) transaction(s).

Que se passe-t-il si on supprime l'instruction exec sql commit ?

Précisez les effets du rollback.

On lance plusieurs instances simultanées du programme précédent. Une transaction ne peut pas lire (et encore moins modifier) les données mises à jour par une transaction non validée. Pourquoi ?

Précisez les complications des procédures de reprise qu'impliquerait la levée de cette limitation, c'est-à-dire le non-respect de la propriété d'isolation des mises à jour.

Donnez le schéma relationnel de la base. Écrire le code de la transaction débit/crédit sous la forme de requêtes SQL.

Le système démarre après un point de reprise et exécute quatre instances de la transaction débit/crédit notées T1, T2, T3, T4. T1 crédite 1 000 F sur votre compte avec succès. T2 tente de créditer 2 000 F mais échoue, T3 crédite 3 000 F avec succès et T4 débite 4 000 F avec succès. Donnez le format du journal (images après et avant comme dans ARIES) après exécution de ces quatre transactions.

Ce journal est géré en mémoire. Quand est-il écrit sur disque ?

Le système tombe en panne après validation (commit) de T4. Que se passe-t-il lors de la procédure de reprise ?

Chaque agence bancaire possède un serveur gérant sa base de données. Écrire le code d'une transaction s'exécutant depuis un client C et effectuant le transfert de m francs depuis un compte d'une agence A sur le compte d'une agence B. Préciser les messages échangés entre client et serveurs dans le cas d'exécution avec succès d'une telle transaction, puis dans le cas où le site A ne répond plus lors de la première phase du commit.

Le site client lance la transaction de transfert qui est bien exécutée sur A et B. Malheureusement, le site client se bloque juste avant l'envoi de la demande de validation (COMMIT). Préciser l'état du système (messages échangés et journaux). Que se passe-t-il alors ?

Afin de sortir des situations de blocage, proposez une extension au protocole de validation à deux phases en ajoutant une phase et en introduisant un état intermédiaire basculant automatiquement en échec de la transaction après un délai d'attente.

Écrire la commande permettant de transmettre les droits de lecture et insertion sur la relation VINS à l'usager FANTOMAS, en lui garantissant le droit de transmettre ces droits.

Écrire la commande permettant de supprimer le droit précédent.

Afin de rendre plus souple l'attribution de droits, on introduit la notion de rôle. Précisez les commandes nécessaires à la gestion des rôles.

Les droits donnés aux usagers sont mémorisés dans une relation DROITS. Proposez un schéma pour la relation DROITS.

Décrivez en quelques lignes ou par un organigramme les principes des algorithmes d'accord de droit (GRANT), de suppression de droits (REVOKE) et de vérification d'un droit.

Soit la relation R (A, B, C, D, E, F, G, H) avec la liste de dépendances fonctionnelles suivantes :

DF = { A→B, A→C, D→E, F→A, F→C, F→G, AD→C, AD→H }

XXIV-46-1-1. Question 1▲

XXIV-46-1-2. Question 2▲

XXIV-46-1-3. Question 3▲

Soit la liste suivante de données élémentaires utilisées pour construire une base de données Commandes :

On suppose que l'on commence par former une unique relation Commandes avec les données précédentes pour attributs.

XXIV-46-2-1. Question 1▲

XXIV-46-2-2. Question 2▲

XXIV-46-2-3. Question 3▲

En considérant chaque classe, donnez le graphe des dépendances fonctionnelles entre attributs. Ajouter au graphe des arcs représentant les dépendances hiérarchiques de 1 vers N représentés par des arcs à tête multiple (du style -->>). Compléter ce graphe par les dépendances interclasses fonctionnelles ou hiérarchiques.

À partir du graphe précédent, déduire un schéma relationnel en 3^e forme normale permettant de représenter la base de données objet initiale.

Préciser les contraintes d'unicité de clé du schéma relationnel. Spécifier ensuite les contraintes référentielles permettant d'imposer l'existence d'une station pour insérer une piste puis l'existence d'une piste pour insérer une bosse.

Proposez un langage de définition de contraintes permettant d'exprimer les mêmes contraintes dans le monde objet. Illustrez sur la base objet initiale.

Donnez la liste des dépendances fonctionnelles non triviales entre données élémentaires sous la forme d'un graphe. S'assurer qu'il ne reste aucune dépendance fonctionnelle qui puisse se déduire des autres par transitivité (les enlever s'il en reste).

Proposez un schéma normalisé en 3FN pour la base DÉGUSTATION à partir de l'ensemble des dépendances fonctionnelles et à l'aide de l'algorithme vu en cours.

Exprimez en SQL les requêtes suivantes sur le schéma proposé :

1. Quels sont les vins de 1991 de la région du Piémont (en Italie) qui ont reçu au moins une note supérieure à 17 lors de la dégustation du 14/05/1994 ?
2. Quelle est la note moyenne décernée tous vins confondus par chaque membre (dégustateur) ?
3. Quels sont les crus qui n'ont pas reçu de note inférieure à 15 pour le millésime 1989 ?
4. Quels sont les dégustateurs qui ont participé à tous les événements ?

Donnez une expression des requêtes a) c) et d) en algèbre relationnelle (en utilisant de préférence la notation graphique vue en cours).

Proposez un schéma physique pour le schéma relationnel précédent. On suppose que l'on peut placer en séquentiel (avec index primaire non plaçant), par des index primaires plaçant de type arbre B+ ou par hachage classique. Choisir un mode de placement pour chaque relation en le justifiant.

Proposez les index secondaires les mieux à même d'accélérer la manipulation de la base. Indiquer les organisations d'index retenues dans chaque cas et donner les justifications des choix réalisés.