Informatique

Conclusion

Les opérateurs présentés sont utilisés sur un modèle de graphe alliant les concepts de la théorie des graphes (noeud, arc, graphe) au paradigme des bases de données orientées objet (notion d'abstraction). Un noeud (modélisant une ville par exemple) peut représenter l'abstraction d'un ou de plusieurs réseaux (modélisant des réseaux de transport locaux). De la même façon, un arc peut représenter l'abstraction d'un réseau (modélisant une ligne de transport). Ces opérateurs permettent de résoudre les requêtes définies dans le chapitre I, sous réserve de l'existence des fonctions permettant la vérification des contraintes agrégatives et régulières.

Les opérateurs de base (DEVELOP et UNDEVELOP) sont directement liés au concept d'abstraction dans le modèle de graphe choisi. Ils permettent de résoudre des requêtes d'augmentation et de diminution de détails. Les opérateurs élémentaires (SELECTION, UNION et DIFFERENCE) correspondent aux manipulations des graphes et des sous-graphes. Ils permettent de résoudre des requêtes connexes à une recherche de chemin. Les opérateurs de haut niveau (CHEMINS, INCLUSION, INTERSECTION) correspondent aux opérateurs visibles pour l'utilisateur.
Ces opérateurs permettent d'utiliser des graphes présentés au plus haut niveau d'abstraction, et donc contenant un nombre de noeuds et d'arcs réduits. Toutes les informations contenues dans ces graphes sont néanmoins prises en compte puisque le résultat rendu par chaque opérateur tient compte de tous les niveaux d'abstraction, et donc de toute la richesse du graphe en question.

A l'image des opérateurs géométriques utilisés dans les Systèmes d'Information Géographique thématiques qui se préoccupent uniquement de la composante spatiale au détriment de la composante alphanumérique, les opérateurs définis ici se préoccupent essentiellement des aspects structurels du réseau (topologie), indépendamment des aspects alphanumériques.

Les opérateurs construits sur le modèle de graphe choisi permettent de résoudre les requêtes présentées dans le Chapitre I. Cette résolution s'effectue par le biais d'une grammaire formalisant la requête et l'application des critères et des contraintes sur les opérateurs.

Le modèle de graphe choisi pour base de notre travail est implanté à l’aide du Système de Gestion de Base de Données Orienté-Objet O₂ [8, 50]. Le choix de ce SGBD a été guidé par la notion d’héritage, présente dans les SGBD Orienté Objet, et par les travaux de recherche déjà en cours sur O₂ [23]. Ce modèle de graphe est à la base du projet de recherche Cigales qui sert de cadre à notre étude [14, 41, 42]. Une requête est posée au système Cigales par le biais de son interface graphique, couplant opérateurs thématiques et opérateurs de type réseau. Cette requête graphique est ensuite optimisée et traduite en une succession d'appels aux opérateurs construits grâce au système O₂. Cette succession d'appels fournit le résultat de la requête initiale, visualisé par l'intermédiaire de O₂Looks, l'interface graphique de O₂.

Remerciements 2

INTRODUCTION 7

Chapitre I - Etat de l’art 12

Introduction 12

I- Définitions 12

I-1. Définitions sur l'information géographique 13

I-1.1 L'information géographique 13

I-1.2 Acquisition et stockage de l'information géographique 15

I-1.2.1 Acquisition de l'information géographique 15

I-1.2.2 Modèles de stockage de l'information géographique 16

I-1.2.2.1 Le modèle raster 17

I-1.2.2.2 Le modèle vecteur 19

I-1.2.2.3 Raster ou vecteur ? 21

I-1.2.3 Les cartes et bases de données de référence des SIG 23

I-1.3 Les normes sur l'information géographique 27

I-1.4 Conclusion 28

I-2. Définitions sur les graphes 29

I-3. Requêtes pour les SIG de type réseau 39

I-3.1 Recherche de chemins 40

I-3.2 Augmentation des détails 43

I-3.3 Requêtes connexes 44

I-3.4 Exemple de référence 46

II- Les propositions existantes de SIG de type réseau 48

II-1. Les SIG physiques de type réseau 48

II-1.1 Les SIG physiques format raster 48

II-1.2 Les SIG physiques format vecteur 50

II-1.2.1 Les systèmes embarqués 50

II-1.2.2 Les systèmes commerciaux thématiques et réseaux 54

II-1.2.3 Les SIG destinés à un large public 58

II-1.3 Conclusion 61

II-2. Les SIG logiques de type réseau 61

II-2.1 Le système GraphDB 62

II-2.2 Le modèle GRAM 69

II-2.3 Conclusion 77

II-3. L'intégration de niveaux d'échelles 77

II-3.1 L'intégration physique 78

II-3.2 L'intégration logique 82

Conclusion 87

Chapitre II - Le modèle de graphe 89

Introduction 89

I- Le modèle de données 89

I-1. Les composants de base 90

I-1.1 Les Noeuds 90

I-1.2 Les Arcs 91

I-1.3 Les Réseaux 92

I-2. Le second niveau d'abstraction 94

I-2.1 Les Réseaux_associés 95

I-2.2 Les Master_noeuds 96

I-2.3 Les Master_arcs 97

I-3. Conclusion 98

II- La gestion des différents niveaux d'abstraction 98

II-1. La hiérarchie des noeuds 99

II-2. La hiérarchie des arcs 101

II-3. La hiérarchie des réseaux 103

III- Récapitulatif : les différentes classes du modèle 107

IV- Exemple de référence 109

Conclusion 117

Chapitre III - Les opérateurs 119

Introduction 119

I- Définitions sur les opérateurs 120

I-1. Définitions 120

I-2. Les critères et les contraintes 121

II- Les Opérateurs 122

II-1. Les Opérateurs de Base 122

II-1.1 L'opérateur de développement DEVELOP 123

II-1.1.1 Notion de développement et structure de données 123

II-1.1.2 Spécification de l'opérateur DEVELOP 125

II-1.1.3 Illustration par un exemple 127

II-1.1.4 Généralisation de l'opérateur DEVELOP 130

II-1.2 L'opérateur de regroupement UNDEVELOP 133

II-1.2.1 Notion de regroupement et structure de données 133

II-1.2.2 Spécification de l'opérateur UNDEVELOP 135

II-1.2.3 Illustration par un exemple 138

II-1.2.4 Généralisation de l'opérateur UNDEVELOP 139

II-1.3 Conclusion 141

II-2. Les Opérateurs Elémentaires 142

II-2.1 L'opérateur de SELECTION 142

II-2.1.1 Notion d'invalidation et structure de données 143

II-2.1.2 Spécification de l'opérateur de SELECTION 144

II-2.1.3 Illustration par un exemple 151

II-2.2 L'opérateur d'UNION 155

II-2.2.1 Notion de prépondérance 156

II-2.2.2 Spécification de l'opérateur d'UNION 156

II-2.2.3 Illustration par un exemple 168

II-2.3 L'opérateur de DIFFERENCE 172

II-2.3.1 Spécification de l'opérateur de DIFFERENCE 173

II-2.3.2 Illustration par un exemple 179

II-3. Les Opérateurs de Haut Niveau 183

II-3.1 L'opérateur de CHEMINS 183

II-3.1.1 Notion d'approximation et structure de données 187

II-3.1.2 Spécification de l'opérateur de CHEMINS 188

II-3.1.3 Illustration par un exemple 198

II-3.2 L'opérateur d'INCLUSION 206

II-3.2.1 Propriétés des opérateurs d'INCLUSION 206

II-3.2.2 L'opérateur d'INCLUSION de noeuds 207

II-3.2.3 L'opérateur d'INCLUSION d'arcs 209

II-3.2.4 L'opérateur d'INCLUSION de noeuds et d'arcs 211

II-3.2.5 Illustration par un exemple 213

II-3.3 L'opérateur d'INTERSECTION 215

II-3.3.1 Propriétés des opérateurs d'INTERSECTION 216

II-3.3.2 L'opérateur d'INTERSECTION de noeuds 217

II-3.3.3 L'opérateur d'INTERSECTION d'arcs 221

II-3.3.4 L'opérateur d'INTERSECTION de noeuds et d'arcs 226

II-3.3.5 Illustration par un exemple 232

III- Traduction des requêtes 234

III-1. Requêtes de recherche de chemins 235

III-2. Requêtes d'augmentation de détails 238

III-3. Requêtes connexes 240

Conclusion 243

CONCLUSION 245

Bibliographie 248