Sujet de Devoir : Bases de données
Licence 2 UPB– Statistiques et Économie appliquée
25 Avril 2025
Durée et critères d’évaluation
— Durée : 2 heures.
— Critères : rigueur de la modélisation, exactitude des expressions en algèbre relation-
nelle, clarté du déroulement algébrique de Dijkstra, précision de la mise en place et
des pivots du simplexe.
Contexte
Une entreprise de transport dispose d’un réseau logistique qu’elle souhaite modéliser
et optimiser exclusivement au sein d’une base de données relationnelle.
Exercice 1 : Modélisation de la base de données
Soit les tables de la base de donnée de gestion du transit d’un usager,
Noeud Champ Description
ID_Noeud Identifiant unique du nœud
Nom Nom du nœud
Ville Ville où se situe le nœud
Arc Champ Description
ID_Arc Identifiant unique de l’arc
ID_Noeud_Départ Référence au nœud de départ
ID_Noeud_Arrivée Référence au nœud d’arrivée
Distance Distance entre les deux nœuds (ex : en km)
Coût Coût du transport (peut dépendre de la distance)
Offre Champ Description
ID_Noeud Référence au nœud qui offre
Capacité_Disponible Quantité disponible à ce nœud
Demande Champ Description
ID_Noeud Référence au nœud qui demande
Quantité_Requise Quantité demandée à ce nœud
1. Définissez le schéma relationnel correspondant
2. Développe un MCD (Modèle Conceptuel des Données) avec entités, associations et
cardinalités pour cette table.
3. Énoncez les contraintes d’intégrité (PK, FK, domaines) nécessaires à la cohérence du
modèle.
4. Trouver les routes coûteuses : Donnez l’expression en algèbre relationnelle qui
permet d’obtenir les arcs dont le coût est strictement supérieur à 1000.
5. Trouver les nœuds avec une grande capacité à Abidjan Donnez l’expression
qui permet d’obtenir les nœuds situés dans la ville d’Abidjan et qui ont une capacité
disponible strictement supérieure à 500.
6. Afficher les trajets avec les noms des nœuds : Donnez l’expression qui permet
d’obtenir, pour chaque arc, son identifiant ainsi que les noms des nœuds de départ et
d’arrivée.
Exercice 2 : Optimisation du réseau
1. Créer une représentation simple du graphe : Définissez une vue relationnelle
nommée Adj(ID_Départ, ID_Arrivée, Distance) qui représente les connexions di-
rectes entre les nœuds du graphe, c’est-à-dire la matrice d’adjacence.
2. Simuler une étape de l’algorithme de Dijkstra : Écrivez une expression en algèbre
relationnelle qui représente une itération de l’algorithme de Dijkstra. Cette expression
doit mettre à jour la relation Dist(Noeud, Valeur) en se basant sur les données de Adj
et Dist.
3. Déterminer quand s’arrêter : Expliquez comment détecter que le calcul est terminé,
c’est-à-dire que la distance minimale à partir du nœud source a été trouvée pour tous
les nœuds atteignables.
4. Modéliser un problème de transport : Représentez le problème de transport
sous forme d’un programme linéaire, en utilisant la relation Transport(ID_Départ,
ID_Arrivée, Coût, Xij ). Décrivez la fonction objectif à minimiser ainsi que les contraintes
à respecter :
— les capacités d’offre disponibles à chaque nœud,
— et les quantités requises par les nœuds demandeurs.
5. Transformer les contraintes pour le simplexe : Convertissez les inégalités en
égalités en introduisant des variables d’écart, et préparez ainsi le tableau initial du
simplexe.
6. Choisir les variables dans une itération du simplexe : Décrivez comment iden-
tifier, lors d’une itération du simplexe,
— la variable entrante (celle qui améliore le plus la solution, donc au coût réduit le
plus négatif),
— et la variable sortante (celle qui limite le plus le mouvement, selon le pivot mini-
mal),
en utilisant des opérations relationnelles comme la sélection, la projection et la jointure.
7. Vérifier l’optimalité et interpréter la solution : Expliquez comment vérifier si la
solution actuelle est optimale (plus aucune amélioration possible). Ensuite, interpré-
tez les valeurs Xij non nulles : que signifient-elles concrètement dans le contexte du
transport ?
