Université Mons Hainaut
Première licence en informatique de gestion
Directeur du projet : M. Jef Wijsen
Olivier Christiaen
Septembre 2004

Interpréteur d'algèbre relationnelle

Objectif du projet

L'algèbre relationnelle

Critères de fonctionnement

Développement

Conclusions

UMH – LIG 1 > Interpréteur d'algèbre relationnelle > Sep 2004 > Olivier Christiaen	www.christiaen.org/sqf

Plan de la présentation

L'objectif du projet est de réaliser un outil didactique qui permettra aux étudiants en bases de données de saisir une requête en algèbre relationnelle et d'en voir le résultat.

Objectif du projet

UMH – LIG 1 > Interpréteur d'algèbre relationnelle > Sep 2004 > Olivier Christiaen	www.christiaen.org/sqf

L'algèbre relationnelle est une méthode d'extraction permettant la manipulation des tables (ou relations).

Son principe repose sur la création de nouvelles tables (tables résultantes).

6 opérations de base : sélection, projection, jointure, renommer, union, différence.

Algèbre relationnelle

UMH – LIG 1 > Interpréteur d'algèbre relationnelle > Sep 2004 > Olivier Christiaen	www.christiaen.org/sqf

>>

La sélection produit, à partir d'une relation, une relation résultante de même schéma mais ne comportant que les tuples qui répondent à la condition précisée en argument.

En sqf : @let CCOURS:COURS WHERE Prof=Mens

Algèbre relationnelle > Sélection

UMH – LIG 1 > Interpréteur d'algèbre relationnelle > Sep 2004 > Olivier Christiaen	www.christiaen.org/sqf

La projection produit, à partir d'une relation, une relation résultante de schéma différent en ne conservant de la relation initiale que les attributs mentionnés en opérandes et les tuples correspondants en éliminant les doublons éventuels.

En sqf : @let PROF:COURS PROJECT Prof

Algèbre relationnelle > Projection

UMH – LIG 1 > Interpréteur d'algèbre relationnelle > Sep 2004 > Olivier Christiaen	www.christiaen.org/sqf

La jointure produit, à partir de deux relations R1 et R2, une relation résultante de schéma différent dont les tuples sont obtenus en composant un tuple de R1 et de R2 lorsque ceux-ci ont la même valeur d'attribut pour des attributs de même nom.

S'il n'y a pas d'attribut en commun, l'effet de la jointure est un produit cartésien.

En sqf : @let DETAILS:COURS JOIN NOTES

Algèbre relationnelle > Jointure

UMH – LIG 1 > Interpréteur d'algèbre relationnelle > Sep 2004 > Olivier Christiaen	www.christiaen.org/sqf

Renommer produit, à partir d'une relation, une relation résultante dans laquelle l'attribut désigné a été renommé par la nouvelle valeur transmise.

En sqf :

@let CCOURS:COURS RENAME Nom AS Nom_cours

Algèbre relationnelle > Renommer

UMH – LIG 1 > Interpréteur d'algèbre relationnelle > Sep 2004 > Olivier Christiaen	www.christiaen.org/sqf

L'union produit, à partir de deux relations de même schéma, une relation résultante de même schéma ayant pour tuples ceux appartenant au deux ou à une des relations en éliminant les doublons éventuels.

En sqf :

@let C2000_2001:COURS_2000 UNION COURS_2001

Algèbre relationnelle > Union

UMH – LIG 1 > Interpréteur d'algèbre relationnelle > Sep 2004 > Olivier Christiaen	www.christiaen.org/sqf

La différence produit, à partir de deux relations de même schéma, une relation résultante de même schéma ayant pour tuples ceux appartenant à la première relation mais pas à la seconde.

En sqf : @let DIFF_C :Cours_2001 MINUS Cours_2000

Algèbre relationnelle > Différence

UMH – LIG 1 > Interpréteur d'algèbre relationnelle > Sep 2004 > Olivier Christiaen	www.christiaen.org/sqf

L'algèbre relationnelle ne comprend pas d'opérations qui permettent de créer une relation, d'y introduire des données ou d'en afficher le contenu.

Ces opérations indispensables pour une projet automatisé sont définies dans SQF.

SQF comprend quatre instructions pour :

1.	créer une relation :
@relation nom_relation:attribut1,attribut2,…attributZ

2.	insérer des données dans une relation :
@data nom_relation:data1,data2,…dataZ

3.	exécuter une opération de l'algèbre relationnelle :
@let nom_relation:<operation alg rel>

4.	afficher le contenu d'une relation
@print nom_relation:

Algèbre relationnelle > Simple Query Format

UMH – LIG 1 > Interpréteur d'algèbre relationnelle > Sep 2004 > Olivier Christiaen	www.christiaen.org/sqf

Facilité d'utilisation

Syntaxe simple

Indépendance d'autre logiciel

Multi plateforme

Code accessible et compréhensible

Critères de fonctionnement

UMH – LIG 1 > Interpréteur d'algèbre relationnelle > Sep 2004 > Olivier Christiaen	www.christiaen.org/sqf

Fonctionnement > Fonctionnement attendu

UMH – LIG 1 > Interpréteur d'algèbre relationnelle > Sep 2004 > Olivier Christiaen	www.christiaen.org/sqf

Développement > Approche

UMH – LIG 1 > Interpréteur d'algèbre relationnelle > Sep 2004 > Olivier Christiaen	www.christiaen.org/sqf

Distinction nette des deux phases

Indépendance de logiciels tiers (SGBD)

Algorithmes d'analyse éprouvés

Solution portable

Développement > Approche

UMH – LIG 1 > Interpréteur d'algèbre relationnelle > Sep 2004 > Olivier Christiaen	www.christiaen.org/sqf

Analyse lexicale et syntaxique des fichiers en entrée

Définition des structures de données

Ecriture du code assurant l'exécution des opérations de l'algèbre

Intégration de ces modules dans une seule application : l'interpréteur.

Développement > Etapes

UMH – LIG 1 > Interpréteur d'algèbre relationnelle > Sep 2004 > Olivier Christiaen	www.christiaen.org/sqf

Le but de l'analyse lexicale est de reconnaître et de transformer une suite de symboles en terminaux.

Flex (Lex) est un utilitaire qui permet de générer automatiquement un analyseur lexical à partir d'une spécification basée sur un ensemble d'expressions régulières et produit en sortie le texte source d'un programme C.

UMH – LIG 1 > Interpréteur d'algèbre relationnelle > Sep 2004 > Olivier Christiaen	www.christiaen.org/sqf

Développement > Analyse lexicale

>>

UMH – LIG 1 > Interpréteur d'algèbre relationnelle > Sep 2004 > Olivier Christiaen	www.christiaen.org/sqf

Développement > extrait spécification Flex SQF

...

Chiffre [0-9]

Lettre [A-Za-z_]

Espace [ ]

Mot	({Lettre}+({Lettre}|{Chiffre})*)|{Chiffre}+

Liste_mots ({Mot}[,])+{Mot}

Comparaison [=<>]

%%

[ \t] {}

[\n] {num_ligne++;}

"WHERE" {return OP_WHERE;}

"PROJECT" {return OP_PROJECT;}

...

"@relation " {return SQF_RELATION;}

"@data " {return SQF_DATA;}

"@let " {return SQF_LET;}

"@print" {return SQF_PRINT;}

{Mot} {

yylval.val_char=(char *) malloc((1+yyleng)*sizeof(char));

strcpy(yylval.val_char, yytext);

return Mot;

}

{Liste_mots}{

yylval.val_char=(char *)malloc((1+yyleng)*sizeof(char));

strcpy(yylval.val_char, yytext);

return Liste_mots;

}

...

L'objectif de cette analyse est de regrouper les terminaux fournis par l'analyse lexicale en phrases grammaticales

Définition de la syntaxe de SQF (formalisme EBNF):

<sequence_sqf>	::=	<commande_sqf>+

<commande_sqf>	::=	<sqf_relation> | <sqf_data> | <sqf_let> | <sqf_print>

<sqf_relation>	::=	@relation <mot> : <tuple>

<sqf_data>	::=	@data <mot> : <tuple>

<sqf_print>	::=	@print <mot> :

<sqf_let>	::=	@let <mot> : <relational operation>

<relational expression>	::=	<nom relation> | <relational operation> | (<relational expression>)

<relational operation>	::=	<select> | <project> | <join> | <rename> | <union> | <difference>

<select>	::=	<relational expression> WHERE <mot> <comparaison> <mot>

<project>	::=	<relational expression> PROJECT <tuple>

<join>	::=	<relational expression> JOIN <relational expression>

<rename>	::=	<relational expression> RENAME <mot> AS <mot>

<union>	::=	<relational expression> UNION <relational expression>

<difference>	::=	<relational expression> MINUS <relational expression>

<tuple>	::=	<mot> | <liste_mots>

<mot>	::=	<lettre>+(<lettre>|<chiffre>)* | <chiffre>+

<liste_mots>	::=	(<mot>,)+ <mot>

<comparaison>	::= = | < | >

UMH – LIG 1 > Interpréteur d'algèbre relationnelle > Sep 2004 > Olivier Christiaen	www.christiaen.org/sqf

Développement > Analyse syntaxique

La relation

nom - nombre de colonnes - nombre de tuples - nombre de	tuples actifs - le nombre maximum de tuples -
un tableau de pointeur sur des tuples

Le tuple

état - longueur du tuple - un tableau de chaînes de caractères

Le dictionnaire des relations

nombre de relations existantes

tableau de pointeur sur les entrées du dictionnaire :

nom de la relation

adresse de la relation

Toute manipulation de relation(s) nécessite l'accès au dictionnaire.

UMH – LIG 1 > Interpréteur d'algèbre relationnelle > Sep 2004 > Olivier Christiaen	www.christiaen.org/sqf

Développement > Structures des données

Les fonctions principales recourent à des fonctions auxiliaires.

Chaque opération de l'algèbre est implémentée dans une fonction.

UMH – LIG 1 > Interpréteur d'algèbre relationnelle > Sep 2004 > Olivier Christiaen	www.christiaen.org/sqf

Développement > Code d'exécution des opérations

void union_rel(char * nom_relation1, char * nom_relation2,char * nom_relation_res);

relation* creer_relation(char * nom_relation, char * champs_rel);

>>

Bison utilise des règles inspirées du formalisme BNF et permet d'y associer une action.

UMH – LIG 1 > Interpréteur d'algèbre relationnelle > Sep 2004 > Olivier Christiaen	www.christiaen.org/sqf

Développement > extrait spécification Bison SQF

...

sequence_sqf	: commande_sqf

| sequence_sqf commande_sqf

;

commande_sqf	: sqf_relation

| sqf_data

| sqf_let

| sqf_print

;

sqf_relation	: SQF_RELATION Mot ':' tuple	{creer_relation($2,$4);}

;

sqf_data	: SQF_DATA Mot ':' tuple	{ajouter_tuple($2,$4);}

;

sqf_let	: SQF_LET Mot ':' relational_operation {executer_operation($2,$4);free($4);}

;

...

relational_expression : Mot	{$$ = garnir_struct(0,$1,"","","");}

| relational_operation	{executer_operation($1->nom_resultante,$1);}

| '('relational_expression')	{$$=$2;strcpy($$->nom_resultante,$2->nom_resultante);}

;

...

r_union	: relational_expression OP_UNION relational_expression

{$$ = garnir_struct(5,$1->nom_resultante,$3->nom_resultante,"","");}

;

tuple	: Mot {$$=$1;}

| Liste_mots {$$=$1;}

;

...

UMH – LIG 1 > Interpréteur d'algèbre relationnelle > Sep 2004 > Olivier Christiaen	www.christiaen.org/sqf

Développement > Intégration

UMH – LIG 1 > Interpréteur d'algèbre relationnelle > Sep 2004 > Olivier Christiaen	www.christiaen.org/sqf

Conclusions

Concrétisation du projet

Correspond aux critères initiaux

Travail de recherche : étude préliminaire

Importance de la méthodologie

Développement de nouvelles compétences

Logiciels libres

www.christiaen.org/sqf

Olivier Christiaen

2004-09-08T07:17:39

Olivier Christiaen