Algèbre relationnelle pour l'optimisation des requêtes

Lorsqu'une requête est placée, elle est d'abord analysée, analysée et validée. Une représentation interne de la requête est alors créée, telle qu'une arborescence de requêtes ou un graphe de requête. Ensuite, des stratégies d'exécution alternatives sont conçues pour récupérer les résultats des tables de la base de données. Le processus de choix de la stratégie d'exécution la plus appropriée pour le traitement des requêtes est appelé optimisation des requêtes.

Problèmes d'optimisation des requêtes dans DDBMS

Dans DDBMS, l'optimisation des requêtes est une tâche cruciale. La complexité est élevée car le nombre de stratégies alternatives peut augmenter de manière exponentielle en raison des facteurs suivants -

La présence d'un certain nombre de fragments.
Répartition des fragments ou des tables sur différents sites.
La vitesse des liens de communication.
Disparité dans les capacités de traitement local.

Par conséquent, dans un système distribué, l'objectif est souvent de trouver une bonne stratégie d'exécution pour le traitement des requêtes plutôt que la meilleure. Le temps d'exécution d'une requête est la somme des éléments suivants:

Il est temps de communiquer les requêtes aux bases de données.
Il est temps d'exécuter des fragments de requête locaux.
Il est temps de rassembler les données de différents sites.
Il est temps d'afficher les résultats dans l'application.

Traitement des requêtes

Le traitement des requêtes est un ensemble de toutes les activités allant du placement de la requête à l'affichage des résultats de la requête. Les étapes sont comme indiqué dans le diagramme suivant -

Algèbre relationnelle

L'algèbre relationnelle définit l'ensemble des opérations de base du modèle de base de données relationnelle. Une séquence d'opérations d'algèbre relationnelle forme une expression d'algèbre relationnelle. Le résultat de cette expression représente le résultat d'une requête de base de données.

Les opérations de base sont -

Projection
Selection
Union
Intersection
Minus
Join

Projection

L'opération de projection affiche un sous-ensemble de champs d'une table. Cela donne une partition verticale de la table.

Syntax in Relational Algebra

$$ \ pi _ {<{AttributeList}>} {(<{Table Name}>)} $$

Par exemple, considérons la base de données des étudiants suivante -

STUDENT
Roll_No	Name	Course	Semester	Gender
2	Amit Prasad	BCA	1	Masculin
4	Varsha Tiwari	BCA	1	Femme
5	Asif Ali	MCA	2	Masculin
6	Joe Wallace	MCA	1	Masculin
8	Shivani Iyengar	BCA	1	Femme

Si nous voulons afficher les noms et les cours de tous les étudiants, nous utiliserons l'expression d'algèbre relationnelle suivante -

$$ \ pi_ {Nom, Cours} {(ÉTUDIANT)} $$

Sélection

L'opération de sélection affiche un sous-ensemble de tuples d'une table qui satisfait certaines conditions. Cela donne une partition horizontale de la table.

Syntax in Relational Algebra

$$ \ sigma _ {<{Conditions}>} {(<{Nom de la table}>)} $$

Par exemple, dans le tableau Student, si nous voulons afficher les détails de tous les étudiants qui ont opté pour le cours MCA, nous utiliserons l'expression d'algèbre relationnelle suivante -

$$ \ sigma_ {Course} = {\ small "BCA"} ^ {(STUDENT)} $$

Combinaison d'opérations de projection et de sélection

Pour la plupart des requêtes, nous avons besoin d'une combinaison d'opérations de projection et de sélection. Il existe deux façons d'écrire ces expressions -

Utilisation d'une séquence d'opérations de projection et de sélection.
Utilisation de l'opération de changement de nom pour générer des résultats intermédiaires.

Par exemple, pour afficher les noms de toutes les étudiantes du cours BCA -

Expression d'algèbre relationnelle à l'aide d'une séquence d'opérations de projection et de sélection

$$ \ pi_ {Name} (\ sigma_ {Gender = \ small "Female" AND \: Course = \ small "BCA"} {(STUDENT)}) $$

Expression d'algèbre relationnelle à l'aide de l'opération de changement de nom pour générer des résultats intermédiaires

$$ FemaleBCAStudent \ leftarrow \ sigma_ {Gender = \ small "Female" AND \: Course = \ small "BCA"} {(STUDENT)} $$

$$ Result \ leftarrow \ pi_ {Name} {(FemaleBCAStudent)} $$

syndicat

Si P est le résultat d'une opération et Q est le résultat d'une autre opération, l'union de P et Q ($ p \ cup Q $) est l'ensemble de tous les tuples qui est soit dans P, soit dans Q ou dans les deux sans doublons .

Par exemple, pour afficher tous les étudiants qui sont au semestre 1 ou qui suivent un cours BCA -

$$ Sem1Student \ leftarrow \ sigma_ {Semester = 1} {(STUDENT)} $$

$$ BCAStudent \ leftarrow \ sigma_ {Course = \ small "BCA"} {(STUDENT)} $$

$$ Résultat \ leftarrow Sem1Student \ cup BCAStudent $$

Intersection

Si P est le résultat d'une opération et Q est le résultat d'une autre opération, l'intersection de P et Q ($ p \ cap Q $) est l'ensemble de tous les tuples qui sont tous les deux dans P et Q.

Par exemple, étant donné les deux schémas suivants -

EMPLOYEE

EmpID	Nom	Ville	département	Un salaire

PROJECT

PId	Ville	département	Statut

Pour afficher les noms de toutes les villes où se trouve un projet et où réside également un employé -

$$ CityEmp \ leftarrow \ pi_ {City} {(EMPLOYEE)} $$

$$ CityProject \ leftarrow \ pi_ {City} {(PROJECT)} $$

$$ Résultat \ leftarrow CityEmp \ cap CityProject $$

Moins

Si P est le résultat d'une opération et Q est le résultat d'une autre opération, P - Q est l'ensemble de tous les tuples qui sont dans P et non dans Q.

Par exemple, pour lister tous les départements qui n'ont pas de projet en cours (projets avec statut = en cours) -

$$ AllDept \ leftarrow \ pi_ {Department} {(EMPLOYEE)} $$

$$ ProjectDept \ leftarrow \ pi_ {Department} (\ sigma_ {Status = \ small "en cours"} {(PROJECT)}) $$

$$ Résultat \ leftarrow AllDept - ProjectDept $$

Joindre

L'opération de jointure combine des tuples liés de deux tables différentes (résultats de requêtes) en une seule table.

Par exemple, considérons deux schémas, Client et Succursale dans une base de données bancaire comme suit -

CUSTOMER

CustID	AccNo	TypeOfAc	ID de branche	DateOfOuverture

BRANCH

ID de branche	Nom de la filiale	IFSCcode	Adresse

Pour lister les détails de l'employé avec les détails de la succursale -

$$ Result \ leftarrow CUSTOMER \ bowtie_ {Customer.BranchID = Branch.BranchID} {BRANCH} $$

Traduire des requêtes SQL en algèbre relationnelle

Les requêtes SQL sont traduites en expressions d'algèbre relationnelle équivalentes avant l'optimisation. Une requête est d'abord décomposée en blocs de requête plus petits. Ces blocs sont traduits en expressions d'algèbre relationnelle équivalentes. L'optimisation comprend l'optimisation de chaque bloc, puis l'optimisation de la requête dans son ensemble.

Exemples

Considérons les schémas suivants -

EMPLOYÉ

EmpID	Nom	Ville	département	Un salaire

PROJET

PId	Ville	département	Statut

TRAVAUX

EmpID	PID	Heures

Exemple 1

Pour afficher les détails de tous les employés qui gagnent un salaire MOINS que le salaire moyen, nous écrivons la requête SQL -

SELECT * FROM EMPLOYEE 
WHERE SALARY < ( SELECT AVERAGE(SALARY) FROM EMPLOYEE ) ;

Cette requête contient une sous-requête imbriquée. Donc, cela peut être divisé en deux blocs.

Le bloc intérieur est -

SELECT AVERAGE(SALARY)FROM EMPLOYEE ;

Si le résultat de cette requête est AvgSal, alors le bloc externe est -

SELECT * FROM EMPLOYEE WHERE SALARY < AvgSal;

Expression d'algèbre relationnelle pour le bloc interne -

$$ AvgSal \ leftarrow \ Im_ {AVERAGE (Salary)} {EMPLOYEE} $$

Expression d'algèbre relationnelle pour le bloc externe -

$$ \ sigma_ {Salaire <{AvgSal}>} {EMPLOYEE} $$

Exemple 2

Pour afficher l'ID de projet et le statut de tous les projets de l'employé 'Arun Kumar', nous écrivons la requête SQL -

SELECT PID, STATUS FROM PROJECT 
WHERE PID = ( SELECT FROM WORKS  WHERE EMPID = ( SELECT EMPID FROM EMPLOYEE 
            WHERE NAME = 'ARUN KUMAR'));

Cette requête contient deux sous-requêtes imbriquées. Ainsi, peut être décomposé en trois blocs, comme suit -

SELECT EMPID FROM EMPLOYEE WHERE NAME = 'ARUN KUMAR'; 
SELECT PID FROM WORKS WHERE EMPID = ArunEmpID; 
SELECT PID, STATUS FROM PROJECT WHERE PID = ArunPID;

(Ici, ArunEmpID et ArunPID sont les résultats de requêtes internes)

Les expressions d'algèbre relationnelle pour les trois blocs sont -

$$ ArunEmpID \ leftarrow \ pi_ {EmpID} (\ sigma_ {Name = \ small "Arun Kumar"} {(EMPLOYEE)}) $$

$$ ArunPID \ leftarrow \ pi_ {PID} (\ sigma_ {EmpID = \ small "ArunEmpID"} {(WORKS)}) $$

$$ Result \ leftarrow \ pi_ {PID, Status} (\ sigma_ {PID = \ small "ArunPID"} {(PROJECT)}) $$

Calcul des opérateurs d'algèbre relationnelle

Le calcul des opérateurs d'algèbre relationnelle peut être effectué de différentes manières, et chaque alternative est appelée access path.

L'alternative de calcul dépend de trois facteurs principaux -

Type d'opérateur
Mémoire disponible
Structures de disque

Le temps d'exécution d'une opération d'algèbre relationnelle est la somme de -

Il est temps de traiter les tuples.
Il est temps de récupérer les tuples de la table du disque vers la mémoire.

Étant donné que le temps de traitement d'un tuple est beaucoup plus court que le temps de récupération du tuple à partir du stockage, en particulier dans un système distribué, l'accès au disque est très souvent considéré comme la métrique pour calculer le coût de l'expression relationnelle.

Calcul de la sélection

Le calcul de l'opération de sélection dépend de la complexité de la condition de sélection et de la disponibilité d'index sur les attributs de la table.

Voici les alternatives de calcul en fonction des index -

No Index- Si la table n'est pas triée et n'a pas d'index, le processus de sélection implique l'analyse de tous les blocs de disque de la table. Chaque bloc est mis en mémoire et chaque tuple du bloc est examiné pour voir s'il satisfait à la condition de sélection. Si la condition est satisfaite, elle est affichée comme sortie. C'est l'approche la plus coûteuse puisque chaque tuple est mis en mémoire et chaque tuple est traité.
B+ Tree Index- La plupart des systèmes de base de données sont construits sur l'index B + Tree. Si la condition de sélection est basée sur le champ, qui est la clé de cet index B + Tree, alors cet index est utilisé pour récupérer les résultats. Cependant, le traitement des instructions de sélection avec des conditions complexes peut impliquer un plus grand nombre d'accès aux blocs de disque et, dans certains cas, une analyse complète de la table.
Hash Index- Si des index de hachage sont utilisés et que son champ clé est utilisé dans la condition de sélection, la récupération des tuples à l'aide de l'index de hachage devient un processus simple. Un index de hachage utilise une fonction de hachage pour trouver l'adresse d'un compartiment dans lequel la valeur de clé correspondant à la valeur de hachage est stockée. Afin de trouver une valeur de clé dans l'index, la fonction de hachage est exécutée et l'adresse du compartiment est trouvée. Les valeurs de clé du bucket sont recherchées. Si une correspondance est trouvée, le tuple réel est extrait du bloc de disque dans la mémoire.

Calcul des jointures

Lorsque nous voulons joindre deux tables, disons P et Q, chaque tuple de P doit être comparé à chaque tuple de Q pour tester si la condition de jointure est satisfaite. Si la condition est satisfaite, les tuples correspondants sont concaténés, éliminant les champs en double et ajoutés à la relation de résultat. C'est donc l'opération la plus coûteuse.

Les approches courantes pour le calcul des jointures sont:

Approche en boucle imbriquée

C'est l'approche de jointure conventionnelle. Il peut être illustré par le pseudocode suivant (Tables P et Q, avec les tuples tuple_p et tuple_q et l'attribut de jointure a) -

For each tuple_p in P 
For each tuple_q in Q
If tuple_p.a = tuple_q.a Then 
   Concatenate tuple_p and tuple_q and append to Result 
End If 
Next tuple_q 
Next tuple-p

Approche de tri-fusion

Dans cette approche, les deux tables sont triées individuellement en fonction de l'attribut de jointure, puis les tables triées sont fusionnées. Des techniques de tri externe sont adoptées car le nombre d'enregistrements est très élevé et ne peut pas être logé dans la mémoire. Une fois que les tables individuelles sont triées, une page de chacune des tables triées est mise en mémoire, fusionnée en fonction de l'attribut de jointure et les tuples joints sont écrits.

Approche par hachage

Cette approche comprend deux phases: la phase de partitionnement et la phase de sondage. En phase de partitionnement, les tables P et Q sont divisées en deux ensembles de partitions disjointes. Une fonction de hachage commune est décidée. Cette fonction de hachage est utilisée pour affecter des tuples aux partitions. Dans la phase de sondage, les tuples d'une partition de P sont comparés aux tuples de la partition correspondante de Q. S'ils correspondent, alors ils sont écrits.

↰ Previous page Next page ↱