X/ENS Informatique B MP-PC-PSI 2018

Thème de l'épreuve Implémentation de requêtes SQL en Python
Principaux outils utilisés listes et dictionnaires Python, requêtes basiques en SQL
Mots clefs Python, SQL

Corrigé

(c'est payant, sauf le début): - - - - - - - - - - - - - - - - - - - - - - - - - - -

Extrait gratuit du corrigé

(télécharger le PDF)
           

Énoncé complet

(télécharger le PDF)
                                      

Rapport du jury

(télécharger le PDF)
                          

Énoncé obtenu par reconnaissance optique des caractères


ÉCOLE POLYTECHNIQUE -- ÉCOLES NORMALES SUPÉRIEURES
ÉCOLE SUPÉRIEURE DE PHYSIQUE ET DE CHIMIE INDUSTRIELLES

CONCOURS D'ADMISSION 2018

FILIÈRES

MP HORS SPECIALITÉ INFO
PC et PSI

COMPOSITION D'INFORMATIQUE ­ B ­ (XELCR)
(Durée : 2 heures)
L'utilisation des calculatrices n'est pas autorisée pour cette épreuve.
Le langage de programmation sera obligatoirement P YTHON.

Introduction
Une requête sur une base de données est décrite au moyen d'un langage 
déclaratif. Le langage SQL est le plus connu. Pour évaluer une requête, un 
système de gestion de base de données (SGBD) établit un plan d'exécution 
combinant les opérateurs de l'algèbre relationnelle. L'objectif de ce sujet est 
l'étude de ces opérateurs.
Nous étudierons en partie I l'implémentation en Python de ces opérateurs. Nous 
appliquerons ensuite en partie II ces résultats à des requêtes SQL. Nous 
verrons en partie III comment
il est possible de tirer parti des propriétés des données pour améliorer les 
performances.
Les parties peuvent être traitées indépendamment. Néanmoins, chaque partie 
utilise des
notations et des fonctions introduites dans les parties précédentes.
Notion de complexité. La complexité, ou le coût, d'un algorithme ou d'une 
fonction Python est le nombre d'opérations élémentaires nécessaires à son 
exécution dans le pire cas.
Lorsque cette complexité dépend d'un ensemble de paramètres (n, p, . . . ), on 
pourra donner
cette estimation sous forme asymptotique. On rappelle qu'une application c(n, 
p, . . . ) est dans
la classe O ( f ) s'il existe une constante  > 0 telle que |c(n, p, . . . )| <  
× f (n, p, . . . ), pour
toutes les valeurs de n, p, . . . assez grandes. Nous préciserons plus loin le 
coût de chacune des
opérations utilisées dans ce sujet.

Bases de données, tables, attributs, enregistrements
Nous détaillons ici la représentation des données dans le modèle relationnel. 
Une base de
données est un ensemble de tables. Chaque table porte un nom et est associée à 
un vecteur
d'attributs de longueur au moins 1. Le nombre d'attributs d'une table est 
appelé l'arité de la
table. Le vecteur des attributs h a0 , a1 , . . . , ak-1 i d'une table T 
d'arité k est noté attributs( T ) et la
table est notée T [[ a0 , a1 , . . . , ak-1 ]].
1

Une table T [[ a0 , a1 , . . . , ak-1 ]] est constituée d'enregistrements. La 
taille d'une table est le
nombre des enregistrements qu'elle contient. Dans ce sujet, nous considérerons 
qu'un enregistrement est un vecteur hv0 , v1 , . . . , vk-1 i de longueur 
l'arité k de la table. Chaque élément de
ce vecteur est la valeur de cet enregistrement par rapport à l'attribut 
correspondant de la table.
La valeur vi à l'indice i de l'enregistrement est la valeur associée à 
l'attribut ai à l'indice i du
vecteur d'attributs de cette table. On pourra donc identifier un attribut et 
son indice et parler
de la valeur d'un enregistrement associée à un indice. La valeur d'un 
enregistrement e associée à un
indice i est notée e[i ].
 Nous considérons dans ce sujet que toutes les valeurs d'attributs sont des 
chaînes de
caractères et que la comparaison entre deux valeurs d'un attribut a un coût 
unitaire
quelles que soient ces valeurs.
Deux enregistrements représentés par des vecteurs contenant les mêmes valeurs 
aux
mêmes indices sont égaux.
 Une table peut contenir des enregistrements égaux. L'élimination des 
enregistrements
égaux est une opération complexe qui est l'objet de l'opérateur SQL appelé 
DISTINCT
que nous étudierons plus loin.
Exemple (Tables et enregistrements). Considérons une agence de voyages qui vend 
des trajets
et des chambres d'hôtel. La table
Vehicule[[IdVehicule, Type, Compagnie]]
contient les données relatives aux divers véhicules disponibles. Pour chaque 
enregistrement e
représentant un véhicule dans la table Vehicule, la valeur de e associée à 
l'attribut IdVehicule
est l'identifiant du véhicule ; la valeur de e associée à l'attribut Type est 
le type de véhicule ; la
valeur associée à l'attribut Compagnie est le nom de la compagnie qui gère ce 
véhicule.
Cette table contient trois enregistrements qui décrivent des véhicules : un bus 
de la compagnie IBUS, un train de la compagnie SNCF et un avion de la compagnie 
Hop !.

h98300, Bus, IBUSi
h1562, TGV, SNCFi
h30990, A320, Hop !i
Considérons d'autre part la table
Trajet[[IdTrajet, VilleD, VilleA, DateD, HeureD, IdVehicule]]
Cette table contient les trajets élémentaires possibles avec les valeurs des 
attributs associés :
l'identifiant du trajet, la ville de départ, la ville d'arrivée, la date du 
départ de ce trajet, l'heure
de départ du trajet, l'identifiant du véhicule utilisé pour le trajet. On 
rappelle que toutes ces
valeurs sont des chaînes de caractères.
Cette table contient 3 trajets possibles le 5 octobre 2016 pour aller de Lille 
à Rennes. Ils partent
respectivement à 9h00, à 10h00 et à 14h00.

hTrajet1, Lille, Rennes, 5 oct. 2016, 09h00, 30990i
hTrajet2, Lille, Rennes, 5 oct. 2016, 10h00, 98300i
hTrajet3, Lille, Rennes, 5 oct. 2016, 14h00, 1562i

2

Représentation des tables et des enregistrements en Python
Dans ce sujet, nous représentons un enregistrement d'une table d'arité k par 
une liste Python
de longueur k. L'élément d'indice i de cette liste représente la valeur de 
l'enregistrement pour
l'attribut d'indice i de la table.
Nous représentons une table d'arité k par une liste d'enregistrements. Une 
table vide est
représentée par une liste vide.
Voici par exemple une représentation en Python de la table Vehicule d'arité 3.
>>> Vehicule
[['98300', 'Bus', 'IBUS'], ['1562', 'TGV', 'SNCF'], ['30990', 'A320', 'Hop!']]
Notez qu'une table peut être représentée par plusieurs listes différentes. 
Voici une autre
représentation possible de cette table.
>>> Vehicule
[['1562', 'TGV', 'SNCF'], ['98300', 'Bus', 'IBUS'], ['30990', 'A320', 'Hop!']]

Rappel sur les listes Python
Nous rappelons brièvement les opérateurs sur les listes en Python.
 Il est attendu que les candidats rédigent leurs réponses à l'aide de ces 
fonctions seulement. En particulier, l'opérateur d'égalité entre listes ne doit 
pas être utilisé.
Longueur. L'opération len(l) renvoie la longueur de la liste l. On considérera 
que cette
opération a un coût unitaire.
Ajout. L'opération l.append(x) ajoute l'élément x à la fin de la liste l. On 
considérera que
cette opération a un coût unitaire, indépendamment de la longueur de la liste 
et de la
valeur de l'élément.
Extraction. L'opération l.pop( ) enlève le dernier élément de la liste l et 
renvoie cet élément. Une erreur est signalée si la liste est vide. On 
considérera que cette opération a un
coût unitaire, indépendamment de la longueur de la liste et de la valeur de 
l'élément.
Accès. L'opération l[i] renvoie l'élément d'indice i de la liste l de longueur 
n. Cette opération ne peut être utilisée dans ce cadre qu'avec un indice 
compris entre 0 et n - 1. On
considérera que cette opération a un coût unitaire, indépendamment de la 
longueur de
la liste et de la valeur de l'indice.
Concaténation. L'opération l1 + l2 renvoie la concaténation des deux listes l1 
et l2. Les
listes ne sont pas modifiées. On considérera que cette opération a un coût 
unitaire.
Itération. Il est possible de parcourir une liste l par la commande d'itération
for x in l: ...
Ce parcours respecte l'ordre des éléments apparaissant dans la liste. On 
considérera que
le coût d'un parcours est la somme des coûts des opérations effectuées, sans 
surcoût
additionnel.

3

I Implémentation des opérateurs
de l'algèbre relationnelle en Python
 Dans toute la suite, on supposera que les arguments des fonctions Python à 
rédiger sont
bien formés : toutes les listes représentant les enregistrements d'une table 
ont la même
longueur qui est l'arité de cette table, les entiers représentant des indices 
d'attributs
appartiennent bien à l'intervalle attendu, etc.

Sélection avec test d'égalité à une constante
L'opérateur Constante prend en arguments une table T d'enregistrements, un 
attribut de
cette table identifié à son indice i dans le vecteur attributs( T ) et une 
valeur c.
Il renvoie une table T  associée aux mêmes attributs que T. Elle est constituée 
des enregistrements de T tels que la valeur de l'attribut d'indice i est égale 
à la valeur c. Cette table peut
être vide.
Exemple. Constante (Trajet, 1, Lille) renvoie une table T  avec les mêmes 
attributs que la table
Trajet. Elle contient tous les voyages dont la ville de départ est Lille. Dans 
notre exemple, c'est
le cas de tous les voyages. La table T  contient donc les mêmes enregistrements 
que la table
Trajet.
Question I.1. Implémentez la fonction
SelectionConstante(table, indice, constante)
qui prend en arguments une table table représentée par une liste 
d'enregistrements, un entier
indice associé à un attribut de cette table table et une valeur constante. Elle 
renvoie une
nouvelle liste représentant la table Constante (table, indice, constante).

Question I.2. Donnez la complexité de votre implémentation de la fonction 
SelectionConstante
par rapport à la taille de la table table. Justifiez votre réponse en vous 
appuyant sur la structure
du programme.

Sélection avec test d'égalité entre deux attributs
L'opérateur Égalité prend en arguments une table T d'enregistrements et deux 
attributs de T
identifiés à leurs indices respectifs i et j dans attributs( T ). Notez qu'il 
est possible que i = j.
Il renvoie une table T  associée aux mêmes attributs que T. Elle est constituée 
des enregistrements de T tels que la valeur pour l'attribut d'indice i est 
égale à la valeur pour l'attribut
d'indice j. Cette table peut être vide.
Exemple. Égalité (Trajet, 1, 2) renvoie une table avec les mêmes attributs que 
la table Trajet. Elle
contient tous les voyages dont la ville de départ est la même que la ville 
d'arrivée. Le résultat
est une table vide.

4

Question I.3. Implémentez la fonction
SelectionEgalite(table, indice1, indice2)
qui prend en arguments une table table d'enregistrements et deux attributs 
identifiés
à leurs indices indice1 et indice2. Elle renvoie une nouvelle liste 
représentant la table
Égalité (table, indice1, indice2).

Projection sur des indices
L'opérateur  prend en arguments une table d'enregistrements T [[ a0 , a1 , . . 
. , ak-1 ]] d'arité k
et un vecteur L = hl0 , . . . , lk -1 i tel que 0 < k  k d'indices identifiant 
des attributs
h al0 , . . . , alk -1 i de la table T.
 On se restreint au cas où la liste L est ordonnée dans le sens croissant, sans 
répétition.
On supposera que les valeurs du vecteur L sont bien comprises entre 0 et k - 1.
L'opérateur  renvoie la table T  d'arité k associée au vecteur d'attributs h 
al0 , . . . , alk -1 i.
Les enregistrements de T  sont obtenus à partir des enregistrements de T en 
conservant uniquement les valeurs de ces enregistrements pour les attributs de 
T  . Deux enregistrements distincts
et différents de T peuvent ainsi créer deux enregistrements égaux dans T  .
Exemple. (Trajet, h1, 2i) renvoie une table associée aux attributs hVilleD, 
VilleAi.

hLille, Rennesi
hLille, Rennesi
hLille, Rennesi
Il se trouve dans ce cas précis que tous ces enregistrements sont égaux. La 
table n'en est pas
moins constituée de 3 enregistrements. Sa taille est 3.
Question I.4. Considérons une table d'enregistrements T [[ a0 , a1 , . . . , 
ak-1 ]] d'arité k. Implémentez
la fonction ProjectionEnregistrement(enregistrement, listeIndices) qui prend en 
arguments un enregistrement enregistrement de cette table et une liste 
listeIndices hl0 , . . . , lk -1 i
telle que 0 < k  k d'indices identifiant des attributs de cette table. Elle 
renvoie une nouvelle
liste représentant l'enregistrement h al0 , . . . , alk -1 i.
 On se restreint au cas où la liste listeIndices d'indices est ordonnée dans le 
sens croissant, sans répétition. On supposera également que tous les indices li 
de listeIndices
sont compris entre 0 et k - 1.

Question I.5. Implémentez la fonction Projection(table, listeIndices) qui prend 
en arguments une table table d'enregistrements d'arité k et une liste 
listeIndices hl0 , . . . , lk -1 i telle
que 0 < k  k d'indices identifiant des attributs de cette table dans 
attributs(table). Cette
fonction renvoie une nouvelle liste représentant la table (table, listeIndices).

5

Produit cartésien
L'opérateur X prend en arguments deux tables T1 et T2 d'enregistrements. La 
table T1 ,
d'arité k1 , est constituée de n1 enregistrements. La table T2 , d'arité k2 , 
est constituée de n2 enregistrements. La table T  résultante est d'arité k1 + 
k2 . Son vecteur d'attributs attributs( T  ) est la
concaténation des vecteurs d'attributs attributs( T1 ) et attributs( T2 ).
La table T  est constituée de n1 × n2 enregistrements. Ces enregistrements sont 
créés par
concaténation de chaque enregistrement de T1 avec chaque enregistrement de T2 . 
Les n1 premiers attributs sont ceux de T1 dans l'ordre de T1 , les n2 suivants 
sont ceux de T2 , dans l'ordre
de T2 . L'ordre des enregistrements ainsi synthétisés dans T  est arbitraire.
Exemple. X(Vehicule, Trajet) renvoie une table T  . Les enregistrements de T  
sont formés par la
concaténation deux à deux des enregistrements de la table Vehicule et de ceux 
de la table Trajet.

h98300, Bus, IBUS, Trajet1, Lille, Rennes, 5 oct. 2016, 09h00, 30990i
h98300, Bus, IBUS, Trajet2, Lille, Rennes, 5 oct. 2016, 10h00, 98300i
h98300, Bus, IBUS, Trajet3, Lille, Rennes, 5 oct. 2016, 14h00, 1562i
h1562, TGV, SNCF, Trajet1, Lille, Rennes, 5 oct. 2016, 09h00, 30990i
h1562, TGV, SNCF, Trajet2, Lille, Rennes, 5 oct. 2016, 10h00, 98300i
h1562, TGV, SNCF, Trajet3, Lille, Rennes, 5 oct. 2016, 14h00, 1562i
h30990, A320, Hop !, Trajet1, Lille, Rennes, 5 oct. 2016, 09h00, 30990i
h30990, A320, Hop !, Trajet2, Lille, Rennes, 5 oct. 2016, 10h00, 98300i
h30990, A320, Hop !, Trajet3, Lille, Rennes, 5 oct. 2016, 14h00, 1562i
Question I.6. Implémentez la fonction ProduitCartesien(table1, table2) qui 
prend en arguments deux tables table1 et table2 d'enregistrements. Elle renvoie 
une nouvelle liste représentant la table X(table1, table2).

Jointure
L'opérateur  prend en arguments deux tables, T1 d'arité k1 et de taille n1 , et 
T2 d'arité k2
et de taille n2 . Il prend aussi en arguments un attribut de T1 identifié par 
son indice i1 tel que
0  i1 < k1 dans le vecteur attributs( T1 ) noté A1 et un attribut de T2 
identifié par son indice i2
tel que 0  i2 < k2 dans le vecteur attributs( T2 ) noté A2 . Posons A2 = h a0 , 
. . . , ai2 , . . . , ak2 -1 i.
La table T  résultante est d'arité k1 + k2 - 1. Son vecteur d'attributs 
attributs( T  ) est la concaténation du vecteur A1 et du vecteur A2 défini par 
h a0 , . . . , ai2 -1 , ai2 +1 , . . . , ak2 -1 i, obtenu en
effaçant la coordonnée i2 de A2 .
La table T  est constituée d'au plus n1 × n2 enregistrements. Les 
enregistrements de T  sont
créés par concaténation des enregistrements e1 de T1 et e2 de T2 tels que e1 
[i1 ] = e2 [i2 ], en supprimant la valeur d'indice k1 + i2 pour éviter la 
répétition avec celle d'indice i1 . L'enregistrement
résultant de cette opération est appelé jointure des deux enregistrements e1 et 
e2 . Notez qu'il est
possible que plusieurs couples (e1 , e2 ) produisent des jointures égales dans 
T  .
Exemple. (Vehicule, Trajet, 0, 5) renvoie les enregistrements qui décrivent les 
voyages de
chaque véhicule suivi des informations le concernant.

h98300, Bus, IBUS, Trajet2, Lille, Rennes, 5 oct. 2016, 10h00i
h1562, TGV, SNCF, Trajet3, Lille, Rennes, 5 oct. 2016, 14h00i
h30990, A320, Hop !, Trajet1, Lille, Rennes, 5 oct. 2016, 09h00i
6

Question I.7. Implémentez la fonction
Jointure(table1, table2, indice1, indice2)
qui prend en arguments deux tables table1 et table2 et deux entiers 
représentant respectivement la position d'un attribut de table1 et celle d'un 
attribut de table2. Elle renvoie une
nouvelle liste représentant la table (table1, table2, indice1, indice2).
 On pourra commencer par implémenter une fonction qui prend en arguments deux
enregistrements e1 et e2 et deux indices i1 et i2 tels que e1 [i1 ] = e2 [i2 ] 
et qui renvoie leur
jointure au sens ci-dessus.

Question I.8. Donnez la complexité de votre implémentation de
Jointure(table1, table2, indice1, indice2)
par rapport aux tailles et arités respectives des tables table1 et table2. 
Justifiez votre réponse
en vous appuyant sur la structure du programme.

Distinct
Nous ajoutons aux opérateurs précédents un nouvel opérateur Distinct qui 
n'appartient pas
à l'algèbre relationnelle classique. Cet opérateur permet de supprimer les 
répétitions d'enregistrements égaux dans une table T. Il renvoie une table T  
qui est associée aux mêmes attributs
que T. Cette table contient exactement un représentant pour chaque classe 
d'enregistrements
égaux de T.
Exemple. Distinct((Trajet, h1, 2i)) renvoie une table avec un unique 
représentant de chaque
couple possible de villes de départ et d'arrivée. Cette table ne contient qu'un 
seul enregistrement : hLille, Rennesi.
Question I.9. Implémentez la fonction
SupprimerDoublons(table)
qui prend en argument une table table. Elle renvoie une nouvelle liste 
représentant la table
Distinct(table).
 On rappelle que l'opérateur Python d'égalité entre listes ne doit pas être 
utilisé dans ce
sujet. Il est seulement possible de tester l'égalité de deux valeurs associées 
à un même
attribut.
Question I.10. Donnez la complexité de votre implémentation de
SupprimerDoublons(table)
par rapport à la taille et l'arité de la table table. Justifiez votre réponse 
en vous appuyant sur
la structure du programme.
7

II

Implémentation de requêtes SQL en Python

Les données de notre agence de voyage sont enregistrées par les tables 
suivantes.
Vehicule(IdVehicule, Type, Compagnie) : enregistre les véhicules disponibles -- 
l'identifiant du véhicule, son type et sa compagnie.
Trajet(IdTrajet, VilleD, VilleA, IdVehicule) : enregistre les trajets 
élémentaires possibles --
l'identifiant du trajet, la ville de départ, la ville d'arrivée ainsi que le 
véhicule utilisé.
Ticket(IdTicket, IdTrajet, Place, Date, Heure, Prix) : enregistre les tickets 
disponibles --
l'identifiant du ticket, l'identifiant du trajet auquel ce ticket donne accès, 
le numéro de
la place, la date, l'horaire et le prix.
Hotel(IdHotel, Classe, Ville) : enregistre les hôtels connus -- l'identifiant 
de l'hôtel, sa
classe et sa ville.
Chambre(IdReservation, IdHotel, Date, Prix) : enregistre les chambres d'hôtel 
qui sont disponibles -- l'identifiant de réservation à utiliser, l'identifiant 
de l'hôtel où se trouve la
chambre, la date et le prix.
L'objectif de cette partie est d'étudier l'implémentation de requêtes SQL en 
combinant les
fonctions de l'algèbre relationnelle présentées dans la partie I. Tout 
commentaire expliquant et
justifiant la traduction sera apprécié.
Par convention, la liste Python représentant une table aura le même nom que 
cette table.
On représentera un attribut avec sa position. Par exemple, l'attribut IdTrajet 
de la table Trajet
est représenté par l'entier 0.
Dans chaque cas, le résultat de la requête sera affecté à une variable nommée 
resultat. Par
exemple, la requête SQL
SELECT Vehicule.Compagnie FROM Vehicule
pourra être implémentée par
resultat = Projection(Vehicule,[2])
en supposant que la variable Python Vehicule représente la table Vehicule. Dans 
des cas plus
complexes, on pourra simplifier l'expression en utilisant des variables 
auxiliaires pour stocker
la valeur de certaines sous-expressions, comme dans l'exemple suivant.
r1 = Vehicule
resultat = Projection(r1, [2])
 Il est attendu que les candidats rédigent leurs réponses en combinant 
uniquement les
fonctions de l'algèbre relationnelle présentées dans la partie I, à l'exclusion 
de toute
autre fonction ou structure de contrôle Python.
Question II.1. Proposez une implémentation pour la requête suivante.
SELECT *
FROM Trajet
WHERE Trajet.VilleD = Rennes

8

Question II.2. Proposez une implémentation pour la requête suivante.
SELECT *
FROM Trajet, Vehicule

Question II.3. Proposez une implémentation pour la requête suivante.
SELECT *
FROM Trajet, Vehicule
WHERE Trajet.IdVehicule = Vehicule.IdVehicule

Question II.4. Proposez une implémentation pour la requête suivante.
SELECT Classe, Ville, Date, Prix
FROM Hotel JOIN Chambre
ON Hotel.IdHotel = Chambre.IdHotel

Question II.5. Proposez une implémentation pour la requête suivante.
SELECT Hotel.IdHotel
FROM Hotel, Trajet, Ticket
WHERE Hotel.Ville = Trajet.VilleA
AND Trajet.IdTrajet = Ticket.IdTrajet
AND Ticket.Prix = '50'

Question II.6. Proposez une implémentation pour la requête suivante.
SELECT *
FROM Chambre
WHERE Chambre.Prix = '100'
AND Chambre.IdHotel IN
(SELECT Hotel.IdHotel
FROM Hotel, Trajet, Ticket
WHERE Hotel.Ville = Trajet.VilleA
AND Trajet.IdTrajet = Ticket.IdTrajet
AND Ticket.Prix = '50')

III

Amélioration des performances

Il est possible dans certains cas d'améliorer l'implémentation d'une requête en 
tenant
compte de propriétés particulières de la représentation des données ou en 
utilisant des structures de données supplémentaires. Dans cette partie, nous 
allons montrer que l'on peut amé9

liorer les performances en triant les données avant de les traiter ou en 
utilisant des tables associatives (dictionnaires) auxiliaires.

Tables triées par rapport à un indice
Une table d'arité k est représentée par une liste d'enregistrements, eux-mêmes 
représentés
par des listes à k éléments. Supposons tout d'abord avoir à disposition une 
fonction
TrieTableIndice(table, indice)
qui trie par ordre croissant suivant l'ordre lexicographique les 
enregistrements de la liste table
d'arité k par rapport à la valeur de l'attribut d'indice indice dans le vecteur 
des attributs de
cette table. On suppose que la valeur indice est strictement inférieure à k.
Par exemple, la liste Trajet ci-dessous est triée par rapport à l'attribut 
d'indice 1 pour
l'ordre lexicographique < sur les chaînes de caractères de Python.
>>> Trajet
[['30990', 'A320', 'Hop!'], ['98300', 'Bus', 'IBUS'], ['1562', 'TGV', 'SNCF']]
Question III.1. Implémentez la fonction VerifieTrie(table, indice) qui renvoie 
True si la table
table est triée pour l'indice indice et False sinon.

Question III.2. Considérez la fonction de la question I.1.
SelectionConstante(table, indice, constante)
Hypothèse. On suppose que la liste représentant la table table est triée selon 
l'indice
indice.
Proposez une implémentation de cette fonction qui utilise cette hypothèse pour 
améliorer
les performances. Elle sera nommée comme suit :
SelectionConstanteTrie(table, indice, constante)

Question III.3. Considérez la fonction de la question I.7.
Jointure(table1, table2, indice1, indice2)
Hypothèse. On suppose dans cette question que les enregistrements de la table 
table1 ont
des valeurs deux à deux distinctes pour l'attribut d'indice indice1, et de même 
pour les
enregistrements de la table table2 avec l'indice indice2.
On suppose de plus que la liste représentant la table table1 est triée selon 
l'indice
indice1 et que celle représentant la table table2 est triée selon l'indice 
indice2.
Proposez une implémentation de cette fonction qui utilise cette hypothèse pour 
améliorer
les performances. Elle sera nommée comme suit :
JointureTrie(table1, table2, indice1, indice2)

10

Question III.4. Donnez la complexité de votre implémentation en vous appuyant 
sur la structure
du programme. Donnez des exemples pour lesquels cette nouvelle approche est 
plus performante. Y a-t-il des cas où elle n'est pas plus performante ?

Utilisation d'un dictionnaire (index)
Dictionnaires Python
Un dictionnaire est une structure de données de Python qui permet d'associer à 
une clé c
une valeur v. On parle aussi de table d'association. Dans notre cas, les clés 
sont des chaînes de
caractères et les valeurs sont des listes d'entiers.
Nous donnons ici quelques opérations permettant de manipuler les dictionnaires 
en Python.
 Il est attendu que les candidats rédigent leurs réponses en utilisant 
exclusivement ces
opérations pour manipuler les dictionnaires.
Création d'un dictionnaire. L'opération dico = {} crée le dictionnaire dico et 
l'initialise à
vide. Cette opération a un coût unitaire.
Ajout d'une association. L'opération dico[c] = liste ajoute au dictionnaire une 
association entre la clé c et la liste liste. Si une association existait déjà 
pour la clé dans le
dictionnaire, celle-ci est perdue. Cette opération a un coût unitaire, 
indépendamment
de l'état du dictionnaire et des valeurs de la clé et de la liste.
Extraction d'une clé. L'opération dico[c] renvoie la liste associée à la clé c 
dans le dictionnaire dico. Cette opération n'est autorisée que si la clé c est 
effectivement associée à une
valeur dans le dictionnaire dico. Si aucune association n'existe pour la clé, 
une erreur se
produit. Cette opération a un coût unitaire, indépendamment de l'état du 
dictionnaire
et de la valeur de la clé.
Test de présence. L'opération c in dico renvoie True si la clé c est associée à 
une valeur
dans le dictionnaire dico et False sinon. Cette opération a un coût unitaire, 
indépendamment de l'état du dictionnaire et de la valeur de la clé.
On peut itérer sur les clés présentes dans un dictionnaire dico par la commande
for c in dico: ...
Voici un exemple d'utilisation.
>>> dico = {}
>>> dico['aaa'] = [1]
>>> dico['bbb'] = [2]
>>> dico['ccc'] = [3]
>>> dico['aaa'].append(4)
>>> dico['ccc'] = [5]
>>> for c in dico: print c, '', dico[c]
aaa  [1, 4]
bbb  [2]
ccc  [5]
>>> dico['ddd']
KeyError: 'ddd'

11

Utilisation de dictionnaires pour indexer les bases de données
Une autre idée pour explorer les tables efficacement est d'utiliser des 
dictionnaires.
Considérons une table T d'arité k et de taille n représentée par une liste 
Python d'enregistrements [e0 , . . . , en-1 ]. Soit L cette liste. Considérons 
un indice i d'attribut de T tel que 0  i < k.
On peut associer à T et i un dictionnaire Python Dico T,i de la manière 
suivante. Les clés
de ce dictionnaire sont les valeurs possibles pour les valeurs v qui 
apparaissent pour l'attribut
d'indice i dans la table T. L'image associée à une clé v est la liste des 
positions dans L des
enregistrements e tels que e[i ] = v.
Si l'attribut d'indice i de T ne prend la valeur v pour aucun enregistrement, 
cette clé n'est
pas enregistrée dans le dictionnaire. L'image d'une clé est donc une liste non 
vide.
Exemple (Dictionnaire associé à une table). Considérons la table
Vehicule[[IdVehicule, Type, Compagnie]]
avec les enregistrements suivants.

h98300, Bus, IBUSi
h1562, TGV, SNCFi
h30990, A320, Hop !i
h1789, TGV, SNCFi
Soit dico le dictionnaire Dico Vehicule,1 associé à l'attribut Type de position 
1.
Nous avons
>>> for c in dico: print c, '', dico[c]
Bus  [0]
A320  [2]
TGV  [1, 3]
>>> dico['Ariane6']
KeyError: 'Ariane6'

Application à la sélection
Question III.5. Implémentez la fonction CreerDictionnaire(table, indice) qui 
prend en arguments une table table et un indice indice d'attribut de table. 
Elle renvoie un dictionnaire de
la table table pour l'attribut d'indice indice.

Question III.6. Considérez la fonction de la question I.1.
SelectionConstante(table, indice, constante)
Implémentez la fonction
SelectionConstanteDictionnaire(table, indice, constante, dico)
qui a la même fonctionnalité que SelectionConstante, mais qui prend en plus en 
argument
un dictionnaire dico de la table table pour l'indice indice.

12

Question III.7. Comparez la complexité de la fonction 
SelectionConstanteDictionnaire avec
celle de la fonction SelectionConstante. Donnez des exemples pour lesquels 
cette nouvelle
approche est plus performante. Y a-t-il des cas où elle n'est pas plus 
performante ?
Application à la jointure
Question III.8. Considérez la fonction de la question I.7.
Jointure(table1, table2, indice1, indice2)
Implémentez la fonction
JointureDictionnaire(table1, table2, indice1, indice2, dico2)
qui a la même fonctionnalité que Jointure, mais qui prend en plus en argument 
un dictionnaire
dico2 pour la table table2 par rapport à l'indice indice2.

Question III.9. Donnez la complexité de votre implémentation par rapport aux 
tailles et arités respectives des tables table1 et table2 ainsi que par rapport 
à la longueur maximale d'une liste
renvoyée par le dictionnaire dico2, qui sera notée k2 . Justifiez votre réponse 
en vous appuyant
sur la structure du programme.

Question III.10. L'opérateur de jointure prend en arguments deux tables qui 
jouent des rôles analogues. Il serait donc possible d'utiliser un dictionnaire 
pour table1 au lieu d'un dictionnaire
pour table2. Comment pourrait-on choisir la table à indexer pour obtenir les 
meilleures performances ?

13

Extrait du corrigé obtenu par reconnaissance optique des caractères



X/ENS Informatique B MP-PC-PSI 2018 -- Corrigé
Ce corrigé est proposé par Emma Kerinec (ENS Lyon) ; il a été relu par Cyril
Ravat (professeur en CPGE) et Vincent Puyhaubert (professeur en CPGE).

Ce sujet regroupe une collection de requêtes SQL élémentaires et leur 
traduction en algèbre relationnelle, qu'il faut implémenter en Python. Aucune 
connaissance
théorique spécifique n'est requise ; seule la maîtrise primaire de la syntaxe 
SQL est
nécessaire. Le sujet est idéal pour s'entraîner sur des requêtes SQL simples, 
ainsi
que sur les principes basiques des algorithmes et leur implémentation en Python.
La première partie doit être abordée avant les deux suivantes, lesquelles 
peuvent en
revanche être traitées indépendamment l'une de l'autre.
· La première partie introduit l'utilisation des listes et des tables afin de 
définir
des fonctions servant de briques de base pour les parties suivantes, notamment
la jointure de tables et la sélection d'éléments selon différents critères.
· La deuxième partie met en évidence le lien entre ces fonctions et les 
principales
requêtes SQL ; il faut alors se servir de la partie précédente pour implémenter
quelques requêtes SQL simples.
· La dernière partie propose d'améliorer les fonctions définies dans la première
partie en exploitant des propriétés de tri concernant les tables ou grâce à 
l'introduction de dictionnaires.
Si ce sujet est d'une difficulté moyenne, il a sans doute déconcerté les 
candidats
ayant fait l'impasse sur le langage SQL. Il introduit efficacement les concepts 
utilisés,
notamment la structure hors-programme de dictionnaire, ainsi que tous les outils
associés auxquels doivent se restreindre les candidats. Malgré l'évocation de 
tris dans
la dernière partie, ce sujet est abordable en fin de première année.

Indications
Partie I
I.5 Observer que les enregistrements d'une table sont indépendants.
I.6 Parcourir les deux tables et utiliser la concaténation.
I.7 Parcourir les deux tables et comparer les bons attributs, ne pas oublier de
supprimer l'attribut associé au second indice.
I.9 Comparer chaque enregistrement de la table à tous ceux déjà retenus dans le
résultat.
Partie II
II.1 Utiliser la fonction SelectionConstante définie dans la partie précédente.
II.2 L'opération demandée est le produit cartésien de Trajet et Véhicule.
II.3 On peut enchaîner les fonctions élémentaires.
II.4 Attention aux indices des colonnes après jointure.
II.5 Il vaut mieux faire une double jointure suivie d'une unique sélection.
II.6 Penser à réutiliser le résultat précédent, sous forme de jointure.
Partie III
III.1 Parcourir la table en comparant les enregistrements consécutifs.
III.2 Quel est l'algorithme classique de recherche sur les listes triées ?
III.3 Parcourir en parallèle les deux tables et les synchroniser.

I.1 On parcourt tous les enregistrements de table, et on ajoute dans le résultat
ceux dont la valeur pour l'indice indice vaut constante.
def SelectionConstante(table, indice, constante):
resultat = []
for enr in table:
if enr[indice] == constante:
resultat.append(enr)
return resultat
I.2 Dans la fonction précédente, il n'y a pas d'opération coûteuse en dehors de 
la
boucle for. Celle-ci s'exécute len(table) fois et on effectue deux opérations 
élémentaires au plus à chaque étape. Ainsi,
La complexité de la fonction SelectionConstante est en O(len(table)).
I.3 Parcourons tous les enregistrements de la table table et ajoutons dans le 
résultat ceux dont la valeur pour l'indice indice1 est égale à celle pour 
l'indice indice2.
def SelectionEgalite(table, indice1, indice2):
resultat = []
for enr in table:
if enr[indice1] == enr[indice2]:
resultat.append(enr)
return resultat
I.4 Il suffit de parcourir la liste listeIndices en créant un nouvel 
enregistrement
auquel on ajoute les valeurs de enregistrement pour les indices souhaités, 
donnés
dans listeIndices.
def ProjectionEnregistrement(enregistrement, listeIndices):
resultat = []
for indice in listeIndices:
resultat.append(enregistrement[indice])
return resultat
I.5 Il suffit d'appliquer la fonction précédente à tous les éléments de table, 
car
ceux-ci sont indépendants, et de rassembler les nouveaux enregistrements dans 
une
nouvelle table que l'on renvoie en fin de programme.
def ProjectionTable(table, listeIndices):
resultat = []
for enr in table:
proj = ProjectionEnregistrement(enr, listeIndices)
resultat.append(proj)
return resultat
I.6 L'utilisation de deux boucles for permet de créer toutes les concaténations 
d'un
élément de table1 et d'un élément de table2, qui sont successivement ajoutés à 
une
nouvelle table.
def ProduitCartesien(table1, table2):
resultat = []
for enr1 in table1:
for enr2 in table2:
resultat.append(enr1 + enr2)
return resultat

I.7 Comme dans la question précédente, on parcourt les couples d'enregistrements
à l'aide de deux boucles. Si les attributs de ces deux enregistrements 
coïncident,
on concatène au premier enregistrement une copie du second dans laquelle seul 
l'attribut d'indice i2 n'a pas été recopié. Le résultat de cette concaténation 
est ensuite
ajouté dans la nouvelle table.
def JointEnregistrements(enr1, enr2, indice2):
return (enr1 + enr2[0:indice2] + enr2[indice2 + 1:])
L'utilisation d'une fonction annexe n'est pas obligatoire.
def Jointure(table1, table2, indice1, indice2):
resultat = []
for enr1 in table1:
for enr2 in table2:
if enr1[indice1] == enr2[indice2]:
jointure = JointEnregistrements(enr1, enr2, indice2)
resultat.append(jointure)
return resultat
On peut aussi utiliser une boucle for pour la jointure :
def JointEnregistrements(enr1, enr2, indice2):
resultat = enr1[:]
for i in range(len(enr2)):
if i != indice2:
resultat.append(enr2[i])
return resultat
L'astuce enr1[ :] sert à créer une copie de enr1 ; il ne faudrait pas que les
modifications apportées à resultat modifient également l'argument enr1.
I.8 La fonction Jointure fait intervenir deux boucles. La première boucle for
s'exécute len(table1) fois. Pour chaque étape, une nouvelle boucle for s'exécute
len(table2) fois, en effectuant une lecture de liste et une copie d'un 
enregistrement
de table2. Finalement,
La complexité de la fonction Jointure est en
O(len(table1) · len(table2) · len(table2[0])).
I.9 La nouvelle table sans doublons se construit au fur et à mesure. 
Initialisée au
premier enregistrement table[0], on ajoute ensuite successivement les autres 
enregistrements, en vérifiant toutefois à chaque fois qu'il n'y a pas déjà un 
élément
identique dans la nouvelle table. Cette vérification se fait de manière naïve, 
en comparant la nouvelle valeur à insérer à toutes les autres déjà 
sélectionnées.
def Egalite(enr1, enr2):
# Renvoie True ssi les deux enregistrements sont égaux
for indice in range(len(enr1)):
if enr1[indice] != enr2[indice]:
return False
return True
def SupprimerDoublons(table):