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 (

), on pourra donner cette estimation sous forme asymptotique. On rappelle qu'une application

est dans la classe

s'il existe une constante

telle que

, pour toutes les valeurs de

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

d'une table

d'arité

est noté attributs(

) et la table est notée

Une table

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 enre－ gistrement est un vecteur

de longueur l＇arité

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

à l＇indice

de l＇enregistrement est la valeur associée à l＇attribut

à l＇indice

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

associée à un indice

est notée

．

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

représentant un véhicule dans la table Vehicule，la valeur de

associée à l＇attribut IdVehicule est l＇identifiant du véhicule；la valeur de

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 compa－ gnie IBUS，un train de la compagnie SNCF et un avion de la compagnie Hop ！．

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 à

，à

et à

．

<Trajet1, Lille, Rennes, 5 oct. 2016, 09h00, 30990>
<Trajet2, Lille, Rennes, 5 oct. 2016, 10h00, 98300〉
<Trajet3, Lille, Rennes, 5 oct. 2016, 14h00, 1562>

Représentation des tables et des enregistrements en Python

Dans ce sujet, nous représentons un enregistrement d'une table d'arité

par une liste Python de longueur

. L'élément d'indice

de cette liste représente la valeur de l'enregistrement pour l'attribut d'indice

de la table.

Nous représentons une table d'arité

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 (1) renvoie la longueur de la liste 1 . On considérera que cette opération a un coût unitaire.
Ajout. L'opération 1. append ( x ) ajoute l'élément x à la fin de la liste 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'é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 1 [i] renvoie l'élément d'indice

de la liste 1 de longueur

. Cette opération ne peut être utilisée dans ce cadre qu'avec un indice compris entre 0 et

. 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

renvoie la concaténation des deux listes 11 et 12 . 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 1 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.

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

cette table identifié à son indice

dans le vecteur attributs

et une valeur

Il renvoie une table

associée aux mêmes attributs que

. Elle est constituée des enregistrements de

tels que la valeur de l'attribut d'indice

est égale à la valeur

. Cette table peut être vide.

Exemple.

(Trajet, 1 , Lille) renvoie une table

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

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

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

É é

prend en arguments une table

d'enregistrements et deux attributs de

identifiés à leurs indices respectifs

dans attributs(

). Notez qu'il est possible que

Il renvoie une table

associée aux mêmes attributs que

. Elle est constituée des enregistrements de

tels que la valeur pour l'attribut d'indice

est égale à la valeur pour l'attribut d'indice

. Cette table peut être vide.

Exemple.

É é

(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.

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

É é

table，indice1，indice2）．

Projection sur des indices

L＇opérateur

prend en arguments une table d＇enregistrements

d＇arité

et un vecteur

tel que

d＇indices identifiant des attributs

de la table

．

On se restreint au cas où la liste

est ordonnée dans le sens croissant，sans répétition． On supposera que les valeurs du vecteur

sont bien comprises entre 0 et

．
L＇opérateur

renvoie la table

d＇arité

associée au vecteur d＇attributs

． Les enregistrements de

sont obtenus à partir des enregistrements de

en conservant unique－ ment les valeurs de ces enregistrements pour les attributs de

．Deux enregistrements distincts et différents de

peuvent ainsi créer deux enregistrements égaux dans

．

Exemple．

（Trajet，

）renvoie une table associée aux attributs

VilleD，VilleA〉．
〈Lille，Rennes〉
〈Lille，Rennes〉
〈Lille，Rennes〉
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

d＇arité

．Implémentez la fonction ProjectionEnregistrement（enregistrement，listeIndices）qui prend en argu－ ments un enregistrement enregistrement de cette table et une liste listeIndices

telle que

d＇indices identifiant des attributs de cette table．Elle renvoie une nouvelle liste représentant l＇enregistrement

．

On se restreint au cas où la liste listeIndices d＇indices est ordonnée dans le sens crois－ sant，sans répétition．On supposera également que tous les indices

de listeIndices sont compris entre 0 et

．

Question I．5．Implémentez la fonction Projection（table，listeIndices）qui prend en argu－ ments une table table d＇enregistrements d＇arité

et une liste listeIndices

telle que

d＇indices identifiant des attributs de cette table dans attributs（table）．Cette fonction renvoie une nouvelle liste représentant la table

（table，listelndices）．

Produit cartésien

L＇opérateur

prend en arguments deux tables

d＇enregistrements．La table

， d＇arité

，est constituée de

enregistrements．La table

，d＇arité

，est constituée de

enre－ gistrements．La table

résultante est d＇arité

．Son vecteur d＇attributs attributs（

）est la concaténation des vecteurs d＇attributs attributs（

）et attributs（

）．

La table

est constituée de

enregistrements．Ces enregistrements sont créés par concaténation de chaque enregistrement de

avec chaque enregistrement de

．Les

pre－ miers attributs sont ceux de

dans l＇ordre de

，les

suivants sont ceux de

，dans l＇ordre de

．L＇ordre des enregistrements ainsi synthétisés dans

est arbitraire．
Exemple．X（Vehicule，Trajet）renvoie une table

．Les enregistrements de

sont formés par la concaténation deux à deux des enregistrements de la table Vehicule et de ceux de la table Trajet．

Question I．6．Implémentez la fonction ProduitCartesien（table1，table2）qui prend en argu－ ments 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，

d＇arité

et de taille

，et

d＇arité

et de taille

．Il prend aussi en arguments un attribut de

identifié par son indice

tel que

dans le vecteur attributs（

）noté

et un attribut de

identifié par son indice

tel que

dans le vecteur attributs

noté

．Posons

．

La table

résultante est d＇arité

．Son vecteur d＇attributs attributs（

）est la conca－ ténation du vecteur

et du vecteur

défini par

，obtenu en effaçant la coordonnée

．

La table

est constituée d＇au plus

enregistrements．Les enregistrements de

sont créés par concaténation des enregistrements

tels que

，en suppri－ mant la valeur d＇indice

pour éviter la répétition avec celle d＇indice

．L＇enregistrement résultant de cette opération est appelé jointure des deux enregistrements

．Notez qu＇il est possible que plusieurs couples（

）produisent des jointures égales dans

．
Exemple．

（Vehicule，Trajet， 0,5 ）renvoie les enregistrements qui décrivent les voyages de chaque véhicule suivi des informations le concernant．

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

et deux indices

tels que

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

. Il renvoie une table

qui est associée aux mêmes attributs que

. Cette table contient exactement un représentant pour chaque classe d'enregistrements égaux de

Exemple. Distinct(

(Trajet,

)) 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 :

Lille, Rennes〉.

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.

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])

(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

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é-
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é

est représentée par une liste d'enregistrements, eux-mêmes représentés par des listes à

é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é

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 à

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)

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é

une valeur

. 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.
(2) 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

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 in dico: print , ' ', dico[c]
aaa
bbb [2]
ccc [5]

dico['ddd']
KeyError: 'ddd'

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

d'arité

et de taille

représentée par une liste Python d'enregistrements

. Soit

cette liste. Considérons un indice

d'attribut de

tel que

On peut associer à

un dictionnaire Python

de la manière suivante. Les clés de ce dictionnaire sont les valeurs possibles pour les valeurs

qui apparaissent pour l'attribut d'indice

dans la table

. L'image associée à une clé

est la liste des positions dans

des enregistrements

tels que

Si l'attribut d'indice

ne prend la valeur

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.

Soit dico le dictionnaire Dico

associé à l'attribut Type de position 1.
Nous avons

>>> for $c$ in dico: print $c$, ' $\lrcorner \rightarrow \sqcup$ ', dico[c]
Bus $\rightarrow$ [0]
A320 $\rightarrow$ [2]
TGV $\rightarrow$ [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.

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

. 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?