Arbres de requêtes

A partir des opérateurs de l’algèbre relationnelle disponibles pour effectuer les traitements sur les différents serveurs de base de données relationnelles, une requête écrite en langage SQL doit pouvoir être representée sour forme d’arbre de traitement de flux de données.

Les feuilles d’un arbre de requête représenteront les tables (ensembles) où se trouvent les informations utiles à la recherche. Les noeuds de l’arbre représenteront les opérateurs de l’algèbre relationnelle que l’on peut appliquer sur les informations. La racine de l’arbre représentera le résultat de la requête SQL, c’est à dire les informations recherchées par la question formulée en SQL. Une requête SQL peut avoir plusieurs arbres correspondant. Les serveurs de bases de données relationnelles disposent d’un optimiseur de requêtes afin de sélectionner le meilleur arbre de requêtes en fonction des informations disponibles dans la base.

Requêtes sur une table

Projection

• Question
• Solution

Arbre de requêtes : « récupérer le nom des personnes ».

Votre réponse :

Arbre de requêtes : graph1001.json

Tables Opérateurs unaires Opérateurs binaires

Vue d'ensemble

DROP TABLE IF EXISTS personnes; DROP TABLE IF EXISTS employes; CREATE TABLE personnes (id integer NOT NULL PRIMARY KEY AUTOINCREMENT, nom text, age SMALLINT); INSERT INTO personnes(nom,age) VALUES ('Dupont',20); INSERT INTO personnes(nom,age) VALUES ('Durand',25); INSERT INTO personnes(nom,age) VALUES ('Martin',35); INSERT INTO personnes(nom,age) VALUES ('Durand',40); CREATE TABLE employes(id INTEGER PRIMARY KEY AUTOINCREMENT, nom text, age SMALLINT); INSERT INTO employes(nom,age) VALUES ('Dupond',26); INSERT INTO employes(nom,age) VALUES ('Durand',25); INSERT INTO employes(nom,age) VALUES ('Martin',30); INSERT INTO employes(nom,age) VALUES ('Durant',46); ----

nom
Dupont
Durand
Martin
Durand

Une solution possible :

On applique une projection (\(\Pi\)) sur la colonne (nom) de la table personnes.

Ecriture en algèbre relationnelle :

• \(Q = \Pi_{(nom)}(personnes)\)

Restriction

• Question
• Solution

Arbre de requêtes : « récupérer les personnes de plus de trente ans».

Votre réponse :

Arbre de requêtes : graph1006.json

Tables Opérateurs unaires Opérateurs binaires

Vue d'ensemble

DROP TABLE IF EXISTS personnes; DROP TABLE IF EXISTS employes; CREATE TABLE personnes (id integer NOT NULL PRIMARY KEY AUTOINCREMENT, nom text, age SMALLINT); INSERT INTO personnes(nom,age) VALUES ('Dupont',20); INSERT INTO personnes(nom,age) VALUES ('Durand',25); INSERT INTO personnes(nom,age) VALUES ('Martin',35); INSERT INTO personnes(nom,age) VALUES ('Durand',40); CREATE TABLE employes(id INTEGER PRIMARY KEY AUTOINCREMENT, nom text, age SMALLINT); INSERT INTO employes(nom,age) VALUES ('Dupond',26); INSERT INTO employes(nom,age) VALUES ('Durand',25); INSERT INTO employes(nom,age) VALUES ('Martin',30); INSERT INTO employes(nom,age) VALUES ('Durant',46); ----

id	nom	age
3	Martin	35
4	Durand	40

Une solution possible :

On applique une condition (restriction : \(\sigma\)) sur les valeurs colonne (nom) de la table personnes.

Ecriture en algèbre relationnelle :

• \(Q = \sigma_{[age>30]}(personnes)\)

Opérations ensemblistes

Les opérations ensemblistes permettent de répondre à des questions du type :

• donne-moi des éléments qui se trouvent dans deux ensembles (l’union, \(\cup\))
• donne-moi des éléments qui sont commun à deux ensembles (l’intersection, \(\cap\))
• donne-moi des éléments qui se trouve dans un ensemble mais pas dans l’autre (la différence, \(\setminus\))

UNION

• Question
• Solution

Arbre de requêtes : « Récupérer les noms des personnes et des employes ».

Votre réponse :

Arbre de requêtes : graph1011.json

Tables Opérateurs unaires Opérateurs binaires

Vue d'ensemble

DROP TABLE IF EXISTS personnes; DROP TABLE IF EXISTS employes; CREATE TABLE personnes (id integer NOT NULL PRIMARY KEY AUTOINCREMENT, nom text, age SMALLINT); INSERT INTO personnes(nom,age) VALUES ('Dupont',20); INSERT INTO personnes(nom,age) VALUES ('Durand',25); INSERT INTO personnes(nom,age) VALUES ('Martin',35); INSERT INTO personnes(nom,age) VALUES ('Durand',40); CREATE TABLE employes(id INTEGER PRIMARY KEY AUTOINCREMENT, nom text, age SMALLINT); INSERT INTO employes(nom,age) VALUES ('Dupond',26); INSERT INTO employes(nom,age) VALUES ('Durand',25); INSERT INTO employes(nom,age) VALUES ('Martin',30); INSERT INTO employes(nom,age) VALUES ('Durant',46); ----

nom
Dupond
Dupont
Durand
Durant
Martin

Une solution possible :

On applique une condition (restriction : \(\sigma\)) sur les valeurs colonne (nom) de la table personnes.

Ecriture en algèbre relationnelle :

• \(P_1 = \Pi_{(nom)}(personnes)\)
• \(P_2 = \Pi_{(nom)}(employes)\)
• \(Q = \cup(P_1,P_2)\)

INTERSECT

• Question
• Solution

Arbre de requêtes : « Récupérer les noms des personnes qui sont employes »

Votre réponse :

Arbre de requêtes : graph1016.json

Tables Opérateurs unaires Opérateurs binaires

Vue d'ensemble

DROP TABLE IF EXISTS personnes; DROP TABLE IF EXISTS employes; CREATE TABLE personnes (id integer NOT NULL PRIMARY KEY AUTOINCREMENT, nom text, age SMALLINT); INSERT INTO personnes(nom,age) VALUES ('Dupont',20); INSERT INTO personnes(nom,age) VALUES ('Durand',25); INSERT INTO personnes(nom,age) VALUES ('Martin',35); INSERT INTO personnes(nom,age) VALUES ('Durand',40); CREATE TABLE employes(id INTEGER PRIMARY KEY AUTOINCREMENT, nom text, age SMALLINT); INSERT INTO employes(nom,age) VALUES ('Dupond',26); INSERT INTO employes(nom,age) VALUES ('Durand',25); INSERT INTO employes(nom,age) VALUES ('Martin',30); INSERT INTO employes(nom,age) VALUES ('Durant',46); ----

nom
Durand
Martin

Une solution possible :

On applique une condition (restriction : \(\sigma\)) sur les valeurs colonne (nom) de la table personnes.

Ecriture en algèbre relationnelle :

• \(P_1 = \Pi_{(nom)}(personnes)\)
• \(P_2 = \Pi_{(nom)}(employes)\)
• \(Q = \cap(P_1,P_2)\)

EXCEPT

• Question
• Solution

Arbre de requêtes : « Récupérer les noms des personnes qui ne sont pas employes »

Votre réponse :

Arbre de requêtes : graph1021.json

Tables Opérateurs unaires Opérateurs binaires

Vue d'ensemble

DROP TABLE IF EXISTS personnes; DROP TABLE IF EXISTS employes; CREATE TABLE personnes (id integer NOT NULL PRIMARY KEY AUTOINCREMENT, nom text, age SMALLINT); INSERT INTO personnes(nom,age) VALUES ('Dupont',20); INSERT INTO personnes(nom,age) VALUES ('Durand',25); INSERT INTO personnes(nom,age) VALUES ('Martin',35); INSERT INTO personnes(nom,age) VALUES ('Durand',40); CREATE TABLE employes(id INTEGER PRIMARY KEY AUTOINCREMENT, nom text, age SMALLINT); INSERT INTO employes(nom,age) VALUES ('Dupond',26); INSERT INTO employes(nom,age) VALUES ('Durand',25); INSERT INTO employes(nom,age) VALUES ('Martin',30); INSERT INTO employes(nom,age) VALUES ('Durant',46); ----

nom
Dupont

Une solution possible :

On applique une condition (restriction : \(\sigma\)) sur les valeurs colonne (nom) de la table personnes.

Ecriture en algèbre relationnelle :

• \(P_1 = \Pi_{(nom)}(personnes)\)
• \(P_2 = \Pi_{(nom)}(employes)\)
• \(Q = \setminus(P_1,P_2)\)