7 jours d'essai offerts
Cet ouvrage et des milliers d'autres sont disponibles en abonnement pour 8,99€/mois

THÈSE
Pour obtenir le grade de
DOCTEUR DE L’UNIVERSITÉ DE GRENOBLE
Spécialité : Doctorat MSTII/informatique
Arrêté ministériel : 7 août 2006
Présentée par
« Víctor Cuevas-Vicenttín »
Thèse dirigée par « Christine Collet » et
codirigée par « Genoveva Vargas-Solar »
préparée au sein du Laboratoire d’Informatique de Grenoble
dans l'École Doctorale Mathématiques, Sciences et
Technologies de l'Information, Informatique
Evaluation de Requêtes
Hybrides Basée sur la
Coordination de Services
Thèse soutenue publiquement le « XX-XX-2011 »,
devant le jury composé de :
Civilité, Prénom, NOM
Fonction et lieu de la fonction, rôle (Président, Rapporteur, Membre)
Civilité, Prénom, NOM
Fonction et lieu de la fonction, rôle (Président, Rapporteur, Membre)
Civilité, Prénom, NOM
Fonction et lieu de la fonction, rôle (Président, Rapporteur, Membre)
Civilité, Prénom, NOM
Fonction et lieu de la fonction, rôle (Président, Rapporteur, Membre)
Civilité, Prénom, NOM
Fonction et lieu de la fonction, rôle (Président, Rapporteur, Membre)
Civilité, Prénom, NOM
Fonction et lieu de la fonction, rôle (Président, Rapporteur, Membre)
tel-00630601, version 1 - 10 Oct 2011VíctorCuevas-Vicenttín
EVALUATION OF HYBRID QUERIES BASED ON SERVICE COORDINA-
TION
186pages.
Impression: thesis.tex–13/6/2011–17:53
tel-00630601, version 1 - 10 Oct 2011tel-00630601, version 1 - 10 Oct 2011tel-00630601, version 1 - 10 Oct 2011Remerciements
Je tiens à remercier sincèrement à ma directrice de thèse Christine Collet et à ma codirectrice Gen-
oveva Vargas-Solar pour leur collaboration dans la réalisation de ce travail. Egalement je remercie
l’attentiondesrapporteursdethèseetdesautresmembresdujury.
Grenoble,29Avril2011
VictorCuevas-Vicenttin
5
tel-00630601, version 1 - 10 Oct 2011tel-00630601, version 1 - 10 Oct 2011Tableofcontents
Tableofcontents 7
Listoftables 11
Listoffigures 13
1 Introduction 15
1.1 Contextandmotivation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15
1.1.1 DBMSsandqueryprocessing . . . . . . . . . . . . . . . . . . . . . . . . . . . 15
1.1.2 ArchitectureofDBMSs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17
1.1.3 Queryevaluationprocess . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18
1.2 Objectiveandapproach . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19
1.2.1 Motivationexample . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20
1.2.2 Prospectiveapproachforevaluatinghybridqueries . . . . . . . . . . . . . . . . 21
1.3 Maincontributions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21
1.4 Documentorganization . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22
2 Queryprocessingandhybridqueries 25
2.1 Queryprocessingindynamicenvironments . . . . . . . . . . . . . . . . . . . . . . . . 25
2.1.1 Datamodels . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25
2.1.2 Dynamicenvironments . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27
2.1.3 Datacommunicationpatterns . . . . . . . . . . . . . . . . . . . . . . . . . . . 28
2.1.4 Querytaxonomy . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29
2.2 Snapshotqueries . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30
2.2.1 Factualqueries . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30
2.2.2 Snapshotspatio-temporalqueries . . . . . . . . . . . . . . . . . . . . . . . . . 31
2.2.3 Location-awarequeries . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 34
2.3 Continuousqueries . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35
2.3.1 Streamqueries . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 36
2.3.2 Mobilelocation-awarequeries . . . . . . . . . . . . . . . . . . . . . . . . . . . 40
2.4 Service-orientedcomputingandqueryprocessing . . . . . . . . . . . . . . . . . . . . . 42
2.4.1 Queryprocessingarchitectures . . . . . . . . . . . . . . . . . . . . . . . . . . . 43
2.4.2 Service-orientedqueryprocessing . . . . . . . . . . . . . . . . . . . . . . . . . 45
2.5 Conclusions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 47
3 Adatamodelforhybridqueries 49
3.1 Dataanddataservicestypes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 49
3.1.1 Complexvalues . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 49
3.1.2 Services . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 51
3.1.3 On-demanddataservices . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 52
7
tel-00630601, version 1 - 10 Oct 20113.1.4 Streamingdataservices. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 52
3.2 Operators . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 54
3.2.1 Windowoperators . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 55
3.2.2 Recursivecomplexvalueoperators . . . . . . . . . . . . . . . . . . . . . . . . 56
3.2.3 Combinationoperators . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 62
3.2.4 Nestingandunnestingoperations . . . . . . . . . . . . . . . . . . . . . . . . . 65
3.2.5 Setoperations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 67
3.3 Hybridqueries . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 68
3.3.1 Characterizationofhybridqueries . . . . . . . . . . . . . . . . . . . . . . . . . 68
3.3.2 HSQLalanguageforhybridqueries . . . . . . . . . . . . . . . . . . . . . . . . 69
3.4 Conclusions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 72
4 EvaluatingaHybridQueryasaServiceCoordination 73
4.1 Representationofahybridqueryasaworkflow . . . . . . . . . . . . . . . . . . . . . . 73
4.1.1 Queryworkflowmodel . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 73
4.1.2 Graphrepresentationofqueryworkflows . . . . . . . . . . . . . . . . . . . . . 74
4.1.3 Hybridqueryworkflows . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 75
4.2 GenerationofanHSQLqueryworkflow . . . . . . . . . . . . . . . . . . . . . . . . . . 79
4.2.1 Representationofjoindependenciesasahypergraph . . . . . . . . . . . . . . . 81
4.2.2 BP-GYOreductionofthehypergraphtoobtainajoinparsetree . . . . . . . . . 85
4.2.3 Joinworkflowgenerationbyparsetreetraversal . . . . . . . . . . . . . . . . . . 88
4.3 Evaluationofaqueryworkflowasaservicecoordination . . . . . . . . . . . . . . . . . 92
4.3.1 Serviceprovisioning . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 92
4.3.2 Simplecomputationservices . . . . . . . . . . . . . . . . . . . . . . . . . . . . 93
4.3.3 Compositeservices . . . . . . . . . . . . . . . . . . . . . . . . . . 93
4.3.4 Implementedcompositecomputationservices . . . . . . . . . . . . . . . . . . . 95
4.3.5 Flexibilityofcomputationservices . . . . . . . . . . . . . . . . . . . . . . . . . 98
4.3.6 Serviceinteroperationandcommunication . . . . . . . . . . . . . . . . . . . . 99
4.4 Compositecomputationservicesworkflowmodel . . . . . . . . . . . . . . . . . . . . . 100
4.4.1 Workflowmodelconstructs . . . . . . . . . . . . . . . . . . . . . . . . . . . . 100
4.4.2 Workflowgraphconstructionrules . . . . . . . . . . . . . . . . . . . . . . . . . 104
4.5 Conclusions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 106
5 HYPATIA:aservice-basedhybridqueryprocessor 109
5.1 OverviewofHYPATIA . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 109
5.2 Complexvaluesanddataservicesimplementation . . . . . . . . . . . . . . . . . . . . . 110
5.2.1 Complexvaluesimplementation . . . . . . . . . . . . . . . . . . . . . . . . . . 111
5.2.2 Dataservices . . . . . . . . . . . . . . . . . . . . . . . . . . . 112
5.3 GenerationofhybridqueryworkflowsfromHSQLqueries . . . . . . . . . . . . . . . . 117
5.3.1 ParsingHSQLqueries . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 117
5.3.2 Generationofhybridqueryworkflows . . . . . . . . . . . . . . . . . . . . . . . 118
5.4 Executionofhybridqueryworkflows. . . . . . . . . . . . . . . . . . . . . . . . . . . . 121
5.4.1 Dataserviceoperators . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 122
5.4.2 Basiccomputationservices . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 122
5.4.3 Simple . . . . . . . . . . . . . . . . . . . . . . . . . . . . 123
5.4.4 Compositecomputationservices . . . . . . . . . . . . . . . . . . . . . . . . . . 124
5.4.5 Not-service-basedqueryoperators . . . . . . . . . . . . . . . . . . . . . . . . . 125
8
tel-00630601, version 1 - 10 Oct 20115.5 GUIandworkflowvisualization . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 128
5.5.1 Visualizationofhybridqueryworkflows . . . . . . . . . . . . . . . . . . . . . . 128
5.5.2 Vofoperatorworkflows . . . . . . . . . . . . . . . . . . . . . . . . 130
5.6 Testbedsandexperimentalresults . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 131
5.6.1 FriendFinder . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 131
5.6.2 NEXMark . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 133
5.6.3 Experimentalresults . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 134
5.7 Conclusions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 136
6 Conclusionsandperspectives 137
6.1 Mainresultsandcontributions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 137
6.2 Perspectives . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 138
Bibliography 141
A HSQLsyntax 161
B ASMsyntax 165
C SemanticsofASM-basedServiceCoordinationModel 169
C.1 Overviewofservicecoordination . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 169
C.2 Coordinationmodelcharacterization . . . . . . . . . . . . . . . . . . . . . . . . . . . . 170
C.3 BasicASMconcepts . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 172
C.3.1 Abstractstates . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 172
C.3.2 Transitionrules . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 173
C.4 ASM-basedservicecoordinationmodel . . . . . . . . . . . . . . . . . . . . . . . . . . 174
C.4.1 RestrictionsonbasicASMs . . . . . . . . . . . . . . . . . . . . . . . . . . . . 174
C.4.2 ExtensionsonbasicASMs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 175
C.4.3 Languagesemantics . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 178
D HYPATIAinstallation 181
9
tel-00630601, version 1 - 10 Oct 2011tel-00630601, version 1 - 10 Oct 2011