Evaluation des requêtes hybrides basées sur la coordination des services, Evaluation of hybrid queries based on service coordination

Victor Cuevas Vicenttin

Description

Sous la direction de Christine Collet, Genoveva Vargas-solar
Thèse soutenue le 08 juillet 2011: Grenoble
Les récents progrès réalisés en matière de communication (réseaux hauts débits, normalisation des protocoles et des architectures à objets répartis, explosion de l'internet) conduisent à l'apparition de systèmes de gestion de données et services largement répartis. Les données sont produites à la demande ou de manière continue au travers de divers dispositifs statiques ou mobiles. Cette thèse présente une approche pour l'évaluation de requêtes dites hybrides car intégrant différents aspects des données mobiles, continues, cachées rencontrées dans des environnements dynamiques. Notre approche consiste à représenter une telle requête comme une coordination de services comprenant des services de données et de calcul. Une telle coordination est définie par le flux de la requête et ceux d'opérateurs sur les données (e.g. join, select, union). Un flux de requête représente une expression construite avec les opérateurs de notre modèle de données. Ce flux est construit par un algorithme de ré-écriture à partir de la requête spécifiée dans notre langage de requête HSQL Les flux dit opérateurs composent des services de calcul afin de permettre l'évaluation d'un opérateur particulier. Le processeur de requêtes basées sur les services hybrides que nous avons développé met en mise en œuvre et valide nos propositions.
-Traitement de requêtes
-Coordination des services
-Bases de données
Recent trends in information technologies result in a massive proliferation of data which are carried over different kinds of networks, produced in either on-demand or streaming fashion, generated and accessible by a variety of devices, and that can involve mobility aspects. This thesis presents an approach for the evaluation of hybrid queries that integrate the various aspects involved in querying continuous, mobile and hidden data in dynamic environments. Our approach consists of representing such an hybrid query as a service coordination comprising data and computation services. A service coordination is specified by a query workflow and additional operator workflows. A query workflow represents an expression built with the operators of our data model. This workflow is constructed from a query specified in our proposed SQL-like query language, HSQL, by an algorithm we developed based on known results of database theory. Operator workflows enable to compose computation services to enable the evaluation of a particular operator. HYPATIA, a service-based hybrid query processor, implements and validates our approach.
-Query processing
-Service coordination
-Databases
Source: http://www.theses.fr/2011GRENM026/document

Sujets

• Base de données

Informations

• Publié par: Thesee
• Nombre de lectures: 22
• Langue: Français
• Poids de l'ouvrage: 3 Mo

Extrait

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