Informatique

Chapitre III - Les opérateurs

Introduction

Les Systèmes d'Information Géographique (ou SIG) sont divisés en deux classes : les SIG traitant d'informations thématiques (e.g, villes, forêts) et les SIG traitant d'informations de type réseau (e.g, réseaux de transport, réseaux électriques). Un graphe (ensemble de noeuds et d'arcs labellés [10]) est la notion conceptuelle la plus aisée pour modéliser des informations orientées réseau.

Nous avons vu dans le chapitre I que les SIG de types réseaux existant actuellement sont incapables de répondre à certaines requêtes posées par un utilisateur. Un nouveau modèle de graphe [44], présenté dans le chapitre II, a donc été construit pour augmenter le pouvoir d'expression des langages de manipulation de données.

Ce modèle de graphe allie 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).

Plusieurs opérateurs sont définis sur ce modèle de graphe [39], [43]. Ces opérateurs doivent permettre de résoudre les requêtes définies dans le chapitre I.

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 d'obtenir des détails plus spécifiques ou moins de détails sur un graphe. 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. Ils se divisent en trois classes, correspondant aux requêtes les plus courantes adressées à un SIG [13] : l'évaluation d'un chemin, l'intersection de chemins et l'inclusion de chemins. Les résultats d'une requête sont présentés au plus haut niveau d'abstraction du graphe résultant de ces opérateurs.

Nous présentons dans une première partie les définitions communes à tous les opérateurs. La seconde partie présente les différentes catégories d'opérateurs. Chacun d'eux est détaillé, et son algorithme est présenté. L'illustration de chaque opérateur se réfère à l'exemple du chapitre II. La dernière partie présente la traduction des requêtes du chapitre I avec ces opérateurs.

I- Définitions sur les opérateurs

Les opérateurs sont définis en plusieurs catégories. Ces opérateurs sont fermés sur la notion de graphe. De plus, sur ces opérateurs peuvent être appliqués des conditions permettant d'affiner une recherche.

I-1. Définitions

Les opérateurs se repartissent en trois catégories : les opérateurs de base, les opérateurs élémentaires et les opérateurs de haut niveau. Les opérateurs de base (DEVELOP et UNDEVELOP) gèrent la notion d'abstraction du modèle de graphe. Les opérateurs élémentaires définissent des opérations sur les graphes et les sous-graphes (SELECTION, UNION, DIFFERENCE). Les opérateurs de haut niveau utilisent les opérateurs précédents pour interroger un SIG de type réseau (CHEMINS, INCLUSION, INTERSECTION).

Les opérateurs s'appliquent sur des ensembles de noeuds et d'arcs. Pour représenter ces ensembles, nous définissons une nouvelle classe, la classe Graphe, définie comme un ensemble de noeuds et d'arcs.
class Graphe

type tuple

(

noeuds : unique set (Noeud),

arcs : unique set (Arc)

)

end;

Chacun des opérateurs s'applique sur un ou plusieurs éléments de la classe Graphe. Un ensemble de graphes est le résultat rendu par un opérateur.

Notons que, conceptuellement, à l'intérieur d'un graphe, les objets (noeuds, arcs ou réseaux) sont partagés et non dupliqués. Par contre, d'un graphe à l'autre, les objets sont dupliqués.

Les opérateurs sont détaillés à l'aide de fonctions définies sur les graphes, les noeuds, les arcs ou les réseaux (la liste complète de ces fonctions se trouve en Annexes). Ils peuvent s'appliquer sur un ensemble de graphes (opérateurs unaires) ou sur deux ensembles de graphes (opérateur binaires) en fonction des spécifications définies dans le langage d'interrogation [15].
Afin de simplifier la présentation, les opérateurs spécifiés dans cette partie sont définis sur un graphe s'il s'agit d'opérateurs unaires, et sur deux graphes pour des opérateurs binaires.
Sur certains de ces opérateurs des conditions peuvent être appliquées. Ces conditions représentent soit des critères sur les noeuds et arcs des graphes rendus par les opérateurs, ou des contraintes sur l'ensemble des noeuds et des arcs de ces graphes. Les conditions permettent de réduire le nombre de graphes résultant d'un opérateur.
Pour simplifier la lecture, nous notons, sauf nécessité, le graphe G(N, E, n_G, e_G, y_G) par G(N,E).

I-2. Les critères et les contraintes

Les requêtes concernant la recherche de chemins calculent une fermeture transitive d'un sommet à un autre d'un graphe. Ces requêtes sont essentielles pour des SIG de type réseau. Sur chaque chemin recherché, des conditions peuvent être définies sur les propriétés alphanumériques des entités géographiques modélisées par des noeuds et des arcs dans le graphe.

Une condition est une expression syntaxique issue d'une grammaire. Elle peut porter sur les propriétés alphanumériques de chaque noeud et/ou arc du graphe (critères) ou sur les propriétés d'un ensemble de noeuds et/ou d'arcs (contraintes agrégatives). Elle peut également imposer un ordre dans la vérification des conditions sur les noeuds et/ou les arcs (contraintes régulières). Dans tous les cas, la vérification d'une condition est une fonction booléenne appliquée sur un graphe et sur l'expression issue de la grammaire, qui indique si cette condition est vérifiée ou non pour ce graphe.
Les critères représentent des propriétés devant être vérifiées par les valeurs des attributs de chaque objet. Par exemple, un critère possible sur les noeuds pourrait être "ville de plus de 100000 habitants", ou encore un critère sur les arcs pourrait être "route nationale". La position de chaque objet vis-à-vis du critère (vérifie ou ne vérifie pas le critère) est examinée.
Les contraintes agrégatives représentent des propriétés sur les valeurs des attributs d'un ensemble d'objets. Les objets sont considérés ensemble et non plus individuellement. Par exemple, la contrainte consistant à trouver "les chemins de Paris à Lyon avec un coût de trajet moyen inférieur à 200F" représente une agrégation sur l'ensemble des arcs de plus haut niveau d'abstraction composant ce chemin. Cette contrainte impose que la moyenne des coûts sur chacun des arcs du chemin soit inférieure à 200F.
Les contraintes régulières représentent des propriétés sur les valeurs des attributs d'un ensemble d'objets. Les objets sont considérés dans leur succession (un arc "succédant" à un noeud si ce noeud est son extrémité initiale, et un noeud "succédant" à un arc s'il est extrémité finale de cet arc). Par exemple, la contrainte consistant à trouver "les chemins de Paris à Lyon en utilisant des autoroutes jusqu'à Blois, puis des routes nationales de Blois à Lyon" est une contrainte régulière imposant l'existence d'arcs uniquement de type autoroute précédant le noeud Blois, et d'arcs uniquement de type route nationale après Blois.
Les conditions sont formalisés suivant une grammaire établie dans [41]. Elles sont définies dans le chapitre I. La grammaire est présentée en Annexes.
Les conditions de type critère s'appliquent sur tous les opérateurs. Pour chacun de ces opérateurs, l'application de ces conditions sur un graphe G équivaut à l'application de l'opérateur de SELECTION avec ces conditions sur le graphe G, puis à l'application de l'opérateur en question sur le graphe résultant de cette sélection.

Les conditions de type contrainte régulière n'ont aucune signification en-dehors de l'opérateur de CHEMINS. Ces contraintes expriment une notion de succession de noeuds et d'arcs qui a un sens uniquement dans le cas d'une recherche de chemins.

De la même manière, les conditions de type contrainte agrégative ne sont pas applicables en-dehors de l'opérateur de CHEMINS. En effet, elles demandent d'examiner toutes les combinaisons possibles entre tous les noeud et arcs des graphes (problème exponentiel fonction du nombre de noeuds et d'arcs d'un graphe). Dans le cas de l'opérateur de chemins, ces contraintes s'appliquent sur la totalité des noeuds et des arcs des graphes rendus et non plus sur toutes les combinaisons possibles entre ces noeuds et arcs.

Par la suite, seules les conditions de type contrainte agrégative et contrainte régulière sont détaillées sur l'opérateur de CHEMINS. Les conditions de type critère sont détaillées uniquement sur l'opérateur de SELECTION.