Informatique

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

Alors que les SIG physiques de type réseau partent d'un mode de stockage de l'information géographique et construisent un modèle sur ces couches basses, les SIG logiques de type réseau partent d'un modèle conceptuel et cherchent ensuite le modèle de stockage qui va correspondre à ce modèle. Du fait des contraintes imposées par les modes de stockage, ce modèle conceptuel peut rester un modèle sans lien avec une carte géographique. L'information géographique contenue dans ce modèle sera alors stockée dans un format interne au modèle.

Ces SIG appartiennent à un domaine de recherche encore très jeune qui n'a vu le jour que récemment avec le développement croissant des moyens de transport. Des systèmes comme le système mis en place par l'INSA de Lyon et destiné à gérer des parcs touristiques [57], ou encore le système étudié dans [46] appartiennent à cette catégorie de SIG. Nous illustrerons cet ensemble de SIG par le système GraphDB, le système GRAM et par l'étude de systèmes introduisant la notion d'intégration de niveaux d'échelles à ce niveau conceptuel.

II-2.1 Le système GraphDB

Le système GraphDB [33, 34] est un système de gestion de bases de données relationnelles étendues destiné à concevoir, de façon simple, des applications géométriques et géographiques. Basé sur le système GRAL [31, 32], il propose d'étendre la notion de type dans les systèmes de gestion de bases de données (relationnelles) classiques, en introduisant la notion de généralisation sur les objets types, et en définissant une hiérarchie de types associée. Ceci permet, entre autres, de tenir compte de la notion de connectivité dans les graphes et d'introduire la notion de questions généralisées. De plus, ce système définit les opérations sur un graphe comme étant des opérations algébriques dans le langage d'interrogation du système. Un graphe est considéré comme un ensemble de sommets et d'arcs où chaque sommet et chaque arc peut lui-même représenter un chemin défini par une expression algébrique.

Le concept central de GraphDB et sa particularité par rapport aux langages algébriques des bases de données relationnelles classiques est son langage algébrique de requêtes basé sur une algèbre multi-sortes.

A la différence des algèbres classiques (mono-sorte) où les différentes opérations (jointure, sélection...) s'appliquent sur un seul type d'élément (les relations), une algèbre multi-sortes possède plusieurs "sortes" (plusieurs types d'éléments) sur lesquelles peuvent s'appliquer des opérations.

Ces opérations, qu'elles soient applicables sur une ou plusieurs sortes, sont définies comme des fonctions. Ceci permet de les combiner entre elles. Une requête consiste donc en une combinaison de fonctions respectant, en entrée et en sortie, les différentes sortes admises par le langage.
L'avantage d'un tel système est de fournir un système de types bien structuré et d'introduire une notion de généricité par un système d'héritage des sortes. GraphDB propose également des fonctions arithmétiques et agrégatives en sus des opérations relationnelles classiques.

GraphDB est également un système extensible, grâce à ce concept d'algèbre multi-sortes. Un développeur peut :

- ajouter des types de données et des opérations au langage de requêtes,

- ajouter la représentation d'un type au système,

- ajouter de nouvelles représentations de relations ainsi que des index afin d'augmenter les capacités de stockage ou de recherche,

- ajouter l'implémentation d'opérations spécifiques à un type de données,

- ajouter de nouvelles règles pour décrire l'implémentation d'une nouvelle opération et pour supporter l'optimisation de cette opération.
Pour les applications géographiques, des sortes de base (BOOL, INT, REAL, STR, POINTS, LINES, REGIONS, EXT, GEO, NUM) sont définies à partir desquelles il sera possible de construire les autres sortes. Une sorte représente un type de données. Chaque type de données représente un domaine de valeurs possibles. Ces types sont organisés suivant une arborescence. Cette arborescence permet d'identifier des sur-types et des sous-types.

Ainsi, l'arborescence de types suivante :

est notée : LINES EXT GEO, REGIONS EXT GEO, POINTS GEO et EXT est appelé un sous-type de GEO.

LINES et REGIONS sont également appelés des types liés (car il existe EXT tel que LINES EXT et REGIONS EXT). Leur plus petit super-type commun existe alors (il s'agit de EXT) et est unique.
Toute opération définie sur un super-type est aussi applicable sur chacun de ses sous-types. Ceci permet d'introduire la notion de généricité de types.
A partir de la hiérarchie de ces types de données, il sera possible de définir la hiérarchie des types des objets.

Un objet est simplement une liste de données : O=1,...,T_m> (avec 0 £ m)

De ce fait, la hiérarchie des types de données induit une hiérarchie des types des objets :

O₁=T₁...T_n est appelé un sous-type de O₂=U₁...U_m, ssi m £ n et T_i £ U_i pour 1 £ i £ m.

Ainsi,
.

Un super-type O₃ commun à deux types de donnés O₁ et O₂ est un type de niveau plus élevé dans la hiérarchie des types que O₁ et O₂, et tel que O₁ et O₂ appartiennent à la filiation de ce super-type.

Ceci permet de formaliser l'héritage d'attributs (car O₁ et O₂ possèdent tous les attributs de O₃ plus quelques uns qui leur sont propres) et en même temps la hiérarchie des objets.

Cet héritage d'attributs est similaire à celui des Systèmes de Gestion de Base de Données Orientés Objet.

La hiérarchie des objets offre la possibilité de faire de la généralisation dynamique. Le résultat d'une fonction opérant sur deux objets O₁ et O₂ est alors un objet O₃ dont le type est le plus petit super-type commun aux types de O₁ et O₂.
A partir de cette définition d'objet sont définis des classes. Une classe possède un type et une extension. L'extension contient tous les objets correspondant à cette classe.

Trois sortes de classes existent dans la base de données : les classes simples (simple classes), les classes liens (link classes) et les classes chemins (path classes).

Les classes simples correspondent à la définition des sommets d'un graphe. Les objets de ces classes sont définis par un oid (au sens défini dans le domaine des bases de données) et par des valeurs correspondant au type de la classe en question.

Les classes liens correspondent à la définition des arcs d'un graphe. Les objets de ces classes sont définis par un oid, par des valeurs correspondant au type de la classe, et par deux oids identifiant deux objets de classes simples. Ces deux oids identifient les extrémités initiales et finales des liens.

Les classes chemins correspondent à la définition de chemins dans un graphe. Les objets de ces classes correspondent à une expression de lien et possèdent un oid et des valeurs correspondant au type de la classe en question. L'expression de lien est une expression régulière sur les valeurs des attributs d'objets de classes liens (objets correspondant aux arcs du chemin). Elle correspond à la description d'un automate sur les classes liens.

Pour chacune de ces trois sortes de classes, il est possible de créer des sous-classes qui héritent (au sens de l'héritage orienté objet) du type de leur super-classe, ou dont le type est un sous-type du type de leur super-classe, ou dont le type est le type de leur super-classe concaténé à un nouveau type (spécialisation de type). Dans le cas des classes liens, l'héritage est également applicable sur les extrémités initiales et finales du lien. Dans le cas des classes chemins, la spécialisation de type est impossible.

Un graphe est de la forme (S, L, source, destination), où S est un ensemble d'objets de classes simples, L un ensemble d'objets de classes liens, source une fonction donnant l'extrémité initiale de chaque objet de L, et destination une fonction donnant l'extrémité finale de chaque objet de L.
Ainsi, pour définir un réseau routier, il suffit de créer des classes simples (Point), puis de créer des sous-classes correspondant à un réseau routier (si la requête correspond à la recherche d'un chemin routier), par exemple, Jonction, Sortie et Ville. A partie de ces classes simples, des classes liens (Voie, Section_autoroute, Route_nationale et Route_départementale) sont créées. Ces classes sont définies entre deux éléments de la super-classe simple Point, ce qui permet de créer des liens entre deux éléments des sous-classes simples Jonction, Sortie et Ville. Les éléments de classes chemins correspondent à un ensemble de Section contenant des Jonctions et des Sorties. Le graphe correspondant au réseau routier contiendra des objets des classes Jonction, Sortie, Ville, Section_autoroute, Route_nationale et Route_départementale.
create class Point = position : POINTS;

create Point class Jonction with nom : STRING;

(Jonction possède en plus de l'attribut position l'attribut nom)

create Point class Sortie = numéro : INTEGER;

(Sortie redéfinit l'attribut position)

create Jonction class Ville with activité : STRING,

population : INTEGER;
create link class Voie = route : LINES,

nom : STRING,

coût : INTEGER

from Point to Point;

create Voie link class Section_autoroute with nb_voies : INTEGER,

prix_au_km : INTEGER

from Point to Point;

create Voie link class Route_nationale with nb_voies : INTEGER,

vitesse_max : INTEGER

from Point to Point;

create Voie link class Route_départementale with vitesse_max : INTEGER

from Point to Point;

create path class Autoroute = nom : STRING

as Voie+;

(Autoroute est définie par une expression régulière sur des Voies)
Plusieurs opérateurs sont définis dans le modèle GraphDB : un opérateur de sélection, un opérateur de dérivation, un opérateur de réécriture d'opérations, un opérateur d'union, un opérateur d'identification de sous-graphes dans un graphe, et un opérateur de recherche de plus court chemin dans un graphe. Ces opérateurs s'appliquent sur un graphe défini comme étant le graphe de base par défaut.
L'opérateur de sélection permet de retrouver des objets dans un graphe, en les sélectionnant suivant la valeur de leurs attributs. Il permet de résoudre les requêtes de type C₁ et C₂.

Ainsi, la requête C₁ ("Quelles sont les plus grandes villes touristiques françaises ?") s'exprimera par l'expression :

Ville ( population > 100000 | activité = "tourisme")

Et la requête C₂ ("Quelles sont les autoroutes dont le coût de trajet est très cher ?") par l'expression :

Section_autoroute ( prix_au_km > 10 )
L'opérateur de dérivation (On...Where...Derive) correspond à une requête SQL simple (le "On" correspond au "From" SQL, le "Where" au "Where" SQL, et le "Derive" au "Select" SQL). Il permet de définir de nouvelles classes (opération de projection), à partir d'objets d'anciennes classes (opération de jointure) sélectionnés suivant la valeur de leurs attributs (opération de sélection).
L'opérateur de réécriture permet de restreindre les types des classes en ne laissant plus apparaître que certains attributs de ces classes.
L'opérateur d'union transforme une collection hétérogène d'objets provenant de classes différentes en un ensemble uniforme d'objets de même type. Le type de ce nouvel ensemble est le plus petit super-type commun entre les différents types des classes précédentes. Cette opération ne change pas les objets eux-mêmes, mais permet d'obtenir une classe unique en résultat d'un opérateur quelconque.
L'opérateur de plus court chemin, shortest_path, permet de trouver le plus court chemin entre deux objets de classes simples. Cet opérateur utilise un algorithme (algorithme A*) basé sur une fonction évaluant la distance entre un sommet et le sommet destination du chemin à rechercher. Cette distance est toujours estimée à la même valeur, choisie par l'utilisateur. La valeur par défaut de cette fonction est 0. L'algorithme de plus court chemin se trouve alors réduit à l'algorithme de Dijkstra.

Sachant que GraphDB utilise l'algèbre relationnelle étendue comme langage de requête, cet opérateur est défini de la façon suivante :

SIMPLEOBJECT x SIMPLEOBJECT -> SEQ shortest_path

où SIMPLEOBJECT représente un objet de classe simple, et SEQ une séquence hétérogène d'objets de classes simples et de classes liens.

L'opérateur shortest_path prend également comme paramètres un type de chemin qui définit la structure précise de la séquence résultante, une fonction ("fun") assignant un coût à chaque objet de classes liens, et la fonction évaluant une distance depuis chaque sommet (objet de classe simple) jusqu'au noeud destination du chemin.

Grâce à cet opérateur, il est possible de résoudre des requêtes correspondant à la recherche d'un chemin dans un graphe. Notons que les objets paramètres de l'opérateur shortest_path doivent exister dans la base, ce qui interdit la résolution de requêtes de type R₁₀ et R₁₁.
La requête R₁ ("Aller de Paris à Lyon en ne passant que par des villes de plus de 100000 habitants") peut être résolue en utilisant l'opérateur de recherche du plus court chemin et l'opérateur d'identification de sous-graphes dans un graphe. Notons que cet opérateur élimine dans le graphe tous les objets de classes simples ne correspondant pas au critère, et tous les objets de classes liens et chemins liés à ces objets de classes simples.
subgraph (Ville where Ville (population > 100000))

Ville ("Paris") Ville ("Lyon") shortest_path [ Voie+ ]

La requête R₂ ("Aller de Paris à Lyon en utilisant uniquement des routes nationales et des autoroutes") peut être résolue en appliquant simplement l'opérateur de plus court chemin sur une expression régulière.
Ville ("Paris") Ville ("Lyon") shortest_path [ (Route_nationale|Section_autoroute)+ ]
La requête R₃ ("Aller de Paris à Lyon en ne passant que par des villes de plus de 100000 habitants et en utilisant uniquement des routes nationales et des autoroutes") est une combinaison des deux requêtes précédentes.
subgraph (Ville where Ville (population > 100000))

Ville ("Paris") Ville ("Lyon") shortest_path [ (Route_nationale|Section_autoroute)+ ]

La requête R₅ ("Aller de Paris à Lyon avec un coût de trajet minimum") peut être résolue en définissant une fonction de coût convenable sur les éléments de la classe Voie.
Ville ("Paris") Ville ("Lyon") shortest_path [ Voie+ ]

rewrite [ fun (s : section) s.coût ] min

La requête R₈ ("Aller de Paris à Lyon en utilisant des autoroutes puis des routes nationales") peut être résolue en définissant une expression régulière sur les classes Section_autoroute et Route_nationale.
Ville ("Paris") Ville ("Lyon") shortest_path [ (Section_autoroute)+ (Route_nationale)+ ]

Les requêtes R₄ et R₆ ne peuvent pas être résolue car aucune fonction de coût n'est définie sur les éléments de classes simples.

Les requêtes R₇ et R₉ sont également irrésolubles car l'expression algébrique définissant un chemin ne contient que des éléments de classes lien.
La requête C₅ ("Quelles sont les villes traversées lors du chemin de Paris à Lyon qui sont parmi les plus grandes villes touristiques françaises ?") peut être résolue utilisant l'opérateur de plus court chemin pour définir les chemins de Paris à Lyon, et l'opérateur de dérivation pour sélectionner les villes de ce chemin qui sont parmi les plus grandes villes touristiques françaises.
on Ville in [Ville ("Paris") Ville ("Lyon") shortest_path [ Voie+ ] ]

where Ville.population >100000 and Ville.activité = "Tourisme"

derive Ville.nom
La requête C₆ ("Quelles sont les voies de communication empruntées lors du chemin de Paris à Lyon qui sont parmi les autoroutes les plus chères ?") peut également être résolue utilisant l'opérateur de plus court chemin pour définir les chemins de Paris à Lyon, et l'opérateur de dérivation pour sélectionner les voies de ce chemin qui sont parmi les autoroutes les plus chères.
on Section_autoroute in [Ville ("Paris") Ville ("Lyon") shortest_path [ Voie+ ] ]

where Section_autoroute.prix_au_km > 10

derive Section_autoroute.nom
Les requêtes C₃ et C₄ sont irrésolubles du fait du manque d'opérateur d'intersection et d'inclusion entre graphes.

De plus, si GraphDB possède bien une notion de généricité, cette notion n'induit aucune notion d'augmentation de détails. Les requêtes de types D₁ à D₆ sont donc irrésolubles.

Requête	R1	R2	R3	R4	R5	R6	R7	R8	R9	R10	R11
GraphDB	O	O	O	N	O	N	N	O	N	N	N

Requête

D1

D2

D3

D4

D5

D6

C1

C2

C3

C4

C5

C6

GraphDB

N

N

N

N

N

N

O

O

N

N

O

O

II-2.2 Le modèle GRAM

GRAM [1, 2, 3] est un modèle de gestion de base de données organisées en sommets et arcs. Il définit un langage algébrique, basé sur des expressions mathématiques régulières (appelées expressions régulières), et permettant de trouver un chemin dans un graphe.

Dans Gram, un schéma de base de données est représenté par un graphe, auquel correspond une expression algébrique régulière. Chaque sommet et arc du graphe est identifié par un label. Un sommet est alors appelé un noeud. Le label représente le noeud ou l'arc dans l'expression algébrique régulière correspondant au graphe. Le label des arcs représente une distance, un type de transport, un coût de transport... mais il peut également représenter un attribut d'un noeud (par exemple, l'adresse d'un hôtel). Entre deux noeuds peuvent exister plusieurs arcs, mais ces arcs doivent tous posséder un label différent.


Figure I-22. Schéma d'une base de données

Ainsi, le schéma de la figure précédente correspond à l'expression régulière :

VILLE premier_arrêt ETAPE (prochain_arrêt ETAPE)* fin_trajet VILLE.

où les labels "premier_arrêt", "prochain_arrêt", "fin_trajet" peuvent correspondre à un type de transport et un coût de transport, par exemple.

Une telle expression est alors appelée l'expression d'un chemin (une "walk expression", ou we), et tous les éléments de la base de données vérifiant une we sont appelés des chemins ("walk"). Ainsi, le chemin suivant :

"PARIS (Autoroute,70) BLOIS (Départementale,30) Tours (Nationale,20) STPIERRE LE MOUTIER (Nationale,40) LYON"

vérifiera l'expression régulière ci-dessus.
Un chemin se définit comme une séquence de noeuds et d'arcs n₀a₀n₁a₁...n_(i-1) a_(i-1)n_i dans laquelle chaque arc est incident aux deux noeuds le suivant et le précédant immédiatement (c'est un chemin au sens de la théorie des graphes). Une walk expression est une expression régulière sur les labels des noeuds et des arcs.

A partir de là sont construits les hyperwalks et les hyperwalk expressions. Un hyperwalk représente un ensemble de chemins (walk) possédant des sommets en commun. Par exemple, l'ensemble suivant :

{Paris.(Autoroute,70).Blois, Blois.Rue_Angleterre.Château}

est un hyperwalk où le premier chemin vérifie l'expression : VILLE type_transp VILLE' et le second l'expression VILLE' adr MONUMENT.

Une hyperwalk expression (notée hwe) est une somme de walk expressions. Ces walk expressions doivent posséder au moins un noeud en commun, afin que le graphe représentant l'hwe soit connecté. Certaines conditions sont également imposées sur cet ensemble d'éléments en commun.

Par exemple, si le schéma de la base de données correspond au graphe suivant :

Figure I-23. Schéma de référence
où "type_transp" est composé de deux éléments : un type (type_transp.type) et un coût de transport (type_transp.coût), et où "adr" représente une adresse postale (adr.post) et un coût (d'hôtel ou de monument, noté adr.coût), alors l'hyperwalk suivant :


Figure I-24. Un hyperwalk
correspondant à ce schéma, vérifie l'hwe suivante : ETAPE adr HOTEL + ETAPE adr MONUMENT.

Dans ce schéma, les noeuds HOTEL et MONUMENT ne sont rattachés qu'au seul noeud ETAPE. Cette notion permet d'introduire la notion d'échelles différentes : HOTEL et MONUMENT représentent une échelle de données inférieure à l'échelle où se situe ETAPE. ETAPE représente donc une généralisation de HOTEL et MONUMENT.

L'hwe correspondant au schéma de référence est :

H_réf = VILLE type_transp ETAPE (type_transp ETAPE)* type_transp VILLE'

+ ETAPE adr HOTEL + ETAPE adr MONUMENT

Un sous-ensemble de cette hwe est également une hwe. Dans tout ce qui suit, nous notons H₂ l'hwe "VILLE type_transp ETAPE (type_transp ETAPE)* type_transp VILLE'" représentant un sous-ensemble de l'hwe de référence.

Une fois que ces hwe et hyperwalks ont été définis, il est possible de les utiliser pour interroger la base de données : une requête est une expression algébrique constituée par la combinaison d'hyperwalks et d'opérateurs unaires et/ou binaires. Une requête est une expression de la forme F(S) ou F(S,S'), où S et S' sont des ensembles d'hyperwalks (un ensemble d'hyperwalks représente une instance d'une hwe, et est noté I(h) où h est une hwe) et où F est un opérateur. Le résultat est encore un ensemble d'hyperwalks, ce qui autorise la combinaison d'opérateurs.

Le langage de requêtes sur le graphe est basé sur l'algèbre de chemins (walk) définie précédemment et il autorise à :

- sélectionner des chemins suivant une expression régulière sur les types des noeuds et des arcs;

- sélectionner des chemins suivant les valeurs des noeuds et des arcs;

- construire de nouveaux chemins par projection et concaténation;

- joindre deux chemins partageant au moins deux noeuds.

Les opérateurs de ce langage permettent de résoudre des requêtes sur les graphes. Les opérateurs peuvent être unaires (projection, sélection et renommage) ou binaires (jointure, concaténation, union, intersection et différence).
Les hwe peuvent posséder plusieurs occurrences d'un même type. Le renommage (noté R) consiste à renommer des noeuds et/ou des arcs afin de pouvoir les différencier dans les hwe. Par exemple, renommer "VILLE.type_transp.VILLE" en "VILLE.type_transp.VILLE'" permettra de trouver des chemins d'une ville à une autre ville différente de la première. Par contre, cela ne permettra pas d'éviter les cycles à l'intérieur de ces chemins.

De même, renommer l'hyperwalk expression de référence "VILLE type_transp ETAPE (type_transp ETAPE)* type_transp VILLE' + ETAPE adr HOTEL + ETAPE adr MONUMENT" permettra de distinguer les différents arcs et noeuds de cette expression :

R_{(ETAPE (type_transp' ETAPE)* type_tranp" VILLE'))} I(H_réf) =

I(VILLE type_transp ETAPE (type_transp' ETAPE)* type_transp" VILLE'

+ ETAPE adr HOTEL + ETAPE adr MONUMENT)

La sélection (s) autorise à évaluer une fonction booléenne (selon des conditions de sélection) sur les labels des hyperwalks (le label d'un hyperwalk étant constitué par la succession des labels des walks qui le composent).

La sélection permet donc de trouver tous les hyperwalks d'un ensemble, satisfaisant une hyperwalk expression et répondant à certaines conditions. La condition de sélection est composée de fonctions (dist, less...), d'égalité (=), du signe "Il existe" ($), et des signes "ou" (Ú), "et" (Ù), et de la négation (not).

Ainsi la sélection

s(Paris(VILLE)ÙLyon(VILLE'))(S)

où S est un ensemble d'hyperwalks satisfaisant

H₂=VILLE type_transp ETAPE (type_transp ETAPE)* type_transp VILLE'

permettra de trouver tous les chemins de Paris à Lyon, car elle renvoie un ensemble d'hyperwalks et non un unique hyperwalk.

La sélection permet de trouver les chemins répondant à la requête R₁ ("Aller de Paris à Lyon en ne passant que par des villes de plus de 100000 habitants"), mais aussi tous les chemins de Paris à Lyon, possédant des cycles et ne passant que par des villes de plus de 100000 habitants :

s_{(Paris(VILLE)ÙLyon(VILLE')Ùpop100000(ETAPE))} (I(H₂))

où pop100000 est une fonction (définie par le concepteur de l'application) qui s'applique sur VILLE et renvoie un booléen vrai ou faux suivant si la ville a plus ou moins de 100000 habitants.
De même, la sélection permet de trouver les chemins répondant à la requête R₂ ("Aller de Paris à Lyon en utilisant uniquement des routes nationales et des autoroutes"), mais aussi les chemins avec cycles permettant d'aller de Paris à Lyon en utilisant uniquement des routes nationales et des autoroutes :

s_{(Paris(VILLE)ÙLyon(VILLE')Ù(Nationale(type_transp.type)ÚAutoroute(type_transp.type))} (I(H2))

La sélection permet également de trouver les chemins répondant à la requête R₃ ("Aller de Paris à Lyon en ne passant que par des villes de plus de 100000 habitants et en utilisant uniquement des routes nationales et des autoroutes"), mais aussi les chemins avec cycles permettant d'aller de Paris à Lyon ne passant que par des villes de plus de 100000 habitants et utilisant uniquement des routes nationales et des autoroutes :

s_{(Paris(VILLE)ÙLyon(VILLE')Ùpop100000(ETAPE)Ù(Nationale(type_transp)ÚAutoroute(type_transp)))} (I(H2)))

Les requêtes connexes peuvent également être résolues grâce à la sélection. La requête C₁, par exemple, ("Quelles sont les plus grandes villes touristiques françaises (population > 100000) ?"), se résoudra par l'expression suivante (une ville étant touristique si elle possède un monument à visiter) :

s_{(pop100000(ETAPE))} I(ETAPE adr MONUMENT)

et la requête C₂ ("Quelles sont les autoroutes dont le coût de trajet est très cher (coût > 10F/km) ?") par l'expression :

s_{(Autoroute(type_transp.type)Ùcoût10(type_transp.coût))} I(H₂)

où coût10 est une fonction qui s'applique sur le label d'un arc et renvoie vrai ou faux suivant si l'arc en question est d'un coût supérieur ou inférieur à 10F/km.

Les autres opérateurs utilisables dans Gram sont la projection, la jointure, la concaténation, l'union, la différence et l'intersection.

La projection (notée P) permet de sélectionner des sous-graphes d'un graphe. En effet, une sous-expression d'une hwe r est une hwe r' (on note r'£ r) telle que r=u.r'.v où u et v peuvent être égaux à e (r' est une sous-partie, un sous-schéma de r). La projection d'un ensemble S d'hyperwalks satisfaisant l'hwe r est alors un ensemble S' d'hyperwalks satisfaisant l'hwe r'. H₂ est donc la projection de H_réf sur "VILLE type_transp ETAPE (type_transp ETAPE)* type_transp VILLE'".
La jointure (notée Å) est l'opération permettant de concaténer deux graphes : en joignant deux hwe, il sera possible d'obtenir un graphe plus important en nombre de noeuds et en nombre d'arcs.

Ainsi, si S est un ensemble d'hyperwalks satisfaisant l'hwe suivante :

H₂=VILLE type_transp ETAPE (type_transp ETAPE)* type_transp VILLE'

alors obtenir tous les éléments de S qui satisfont :

r'=s_{(coût200(HOTEL))}I(ETAPE adr HOTEL)

(c'est-à-dire trouver tous les trajets qui passent dans une ville où se trouve un hôtel de coût inférieur à 200 francs, où "coût200" est une fonction qui s'applique sur un HOTEL et renvoie vrai ou faux suivant si l'hôtel est d'un coût inférieur ou supérieur à 200 francs), consiste à effectuer la jointure de S avec l'expression r' précédente.

La requête C₃ ("Les villes traversées lors du chemin de Paris à Lyon sont-elles parmi les plus grandes villes touristiques françaises ?") s'exprimera donc de la façon suivante :

s_{(Paris(VILLE)ÙLyon(VILLE'))}I(H2)

Å s_{(pop100000(ETAPE))} I(ETAPE adr MONUMENT)
La requête C₄ ("Les voies de communication empruntées lors du chemin de Paris à Lyon sont-elles parmi les autoroutes les plus chères ?") s'exprimera de la façon suivante :

s_{(Paris(VILLE)ÙLyon(VILLE')ÙAutoroute(type_transp.type))}I(H2)

Å s_{(Autoroute(type_transp.type)Ùcoût10(type_transp.coût))} I(H₂)
La concaténation (notée Q) est rendue possible grâce à la structure des données de GRAM. Si r est une hwe de la forme u.t et r' une hwe de la forme t.v, alors la concaténation de r et r' (notée rQr') est u.t.v. Cette concaténation permet de mettre bout à bout deux graphes ayant au moins un noeud commun respectivement en fin et en début de graphe.

Soit S un ensemble d'hyperwalks satisfaisant l'hwe suivante :

r=VILLE type_transp ETAPE

et S' un ensemble d'hyperwalks satisfaisant :

r'=ETAPE adr HOTEL + ETAPE adr MONUMENT

(S' représente les villes avec leurs hôtels et restaurants)

L'obtention des hôtels et monuments pouvant être "visités" durant les étapes d'un voyage résulte de la concaténation chaque hyperwalk h de S avec chaque hyperwalk h' de S'; le résultat de cette opération sera un ensemble d'hyperwalks répondant à cette condition et satisfaisant donc l'hwe suivante :

VILLE type_transp ETAPE adr HOTEL + VILLE type_transp ETAPE adr MONUMENT.

Sans tenir compte du problème de cycles pouvant apparaître dans les chemins résultants, la concaténation va permettre de résoudre des requêtes régulières (requêtes R₇, R₈ et R₉). Ainsi, la requête R₇ ("Aller de Paris à Lyon en passant par Blois puis par StPierre le Moûtier") va se traduire par l'expression suivante :

s_{(Paris(VILLE)ÙBlois(VILLE'))} I(H₂)

Q s_{(Blois(VILLE')ÙStPierre_le_Moûtier(VILLE"))} I(H₃)

Q s_{(StPierre_le_Moûtier(VILLE")ÙLyon(VILLE"'))} I(H₄)

où H₂=VILLE type_transp ETAPE (type_transp ETAPE)* type_transp VILLE', et où H₃ est obtenue en renommant VILLE' en VILLE" et VILLE en VILLE' dans H₂, et H₄ en renommant VILLE en VILLE" et VILLE' en VILLE"' dans H₂. Le résultat de la requête de GRAM est un ensemble de chemins comportant les chemins (sans cycle) répondant à la requête R₇ et les chemins répondant à la requête "Aller de Paris à Lyon en passant par Blois puis par StPierre le Moûtier, les chemins trouvés comportant éventuellement des cycles".
De la même manière, la requête R₈ ("Aller de Paris à Lyon en utilisant des autoroutes puis des routes nationales") va se traduire par l'expression suivante :

s_{(Paris(VILLE)ÙAutoroute(type_transp.type))} I(H₂)

Q s_{(Lyon(VILLE")ÙNationale(type_transp.type))} I(H₃)

Le résultat de la requête de GRAM est un ensemble de chemins comportant les chemins (sans cycle) répondant à la requête R₈ et les chemins répondant à la requête "Aller de Paris à Lyon en utilisant des autoroutes puis des routes nationales, les chemins trouvés comportant éventuellement des cycles".

La requête R₉ ("Aller de Paris à Lyon en utilisant des autoroutes jusqu'à Blois, puis des routes nationales de Blois à Lyon") va se traduire par l'expression suivante :

s_{(Paris(VILLE)ÙBlois(VILLE')ÙAutoroute(type_transp.type))} I(H₂)

Q s_{(Blois(VILLE')ÙLyon(VILLE")ÙNationale(type_transp.type))} I(H₃)

Le résultat de la requête de GRAM est un ensemble de chemins comportant les chemins (sans cycle) répondant à la requête R₉ et les chemins répondant à la requête "Aller de Paris à Lyon en utilisant des autoroutes jusqu'à Blois puis des routes nationales de Blois à Lyon, les chemins trouvés comportant éventuellement des cycles".

Les opérateurs d'union (È), de différence (\) et d'intersection () opèrent sur deux hyperwalks. Soient S et S' deux ensembles d'hyperwalks satisfaisant l'hwe r, l'union de S et de S' (SÈS') retournera alors l'ensemble des hyperwalks appartenant à S ou à S', l'intersection de S et de S' retournera l'ensemble des hyperwalks appartenant à la fois à S et à S', et la différence entre S et S' retournera l'ensemble des hyperwalks appartenant à S et n'appartenant pas à S'.

Ainsi, la requête C₅ ("Quelles sont les villes traversées lors du chemin de Paris à Toulon qui sont parmi les plus grandes villes touristiques françaises ?") se résoudra de la manière suivante :

(s_{(Paris(VILLE)ÙLyon(VILLE'))} I(H₂)) (s_{(pop100000(ETAPE))} I(ETAPE adr MONUMENT))
Et la requête C₆ ("Quelles sont les voies de communication empruntées lors du chemin de Paris à Lyon qui sont parmi les autoroutes les plus chères ?") se résoudra de la manière suivante :

(s_{(Paris(VILLE)ÙLyon(VILLE'))} I(H₂)) (s_{(Autoroute(type_transp.type)Ùcoût10(type_transp.coût))} I(H₂))

GRAM permet également de ne pas préciser de critères sur les sommets origine et destination du chemin à rechercher, ce qui permet de résoudre les requêtes de type R₁₀ et R₁₁.

Par contre, il ne permet pas de résoudre les requêtes agrégatives R₄, R₅ et R₆ car il ne possède aucune fonction de calcul de coût d'un chemin : toutes ses fonctions s'appliquent sur un unique élément du graphe (arc ou sommet).

Sans tenir compte du fait que GRAM fournit également, en réponse à une requête de recherche de chemins, des chemins avec cycles, les requêtes de types R₁, R₂, R₃, R₇, R₈ et R₉ sont résolubles. Dans le cas des graphes acycliques, GRAM permet effectivement de résoudre ces requêtes.
GRAM est utilisé lors de la navigation dans les hypertextes [3]. Ces hypertextes sont organisés sous la forme des graphes définis précédemment. A ce niveau-là, certaines notions sont rajoutées au modèle de base de GRAM : les liens virtuels qui permettent de garder en mémoire tous les noeuds connectés par un chemin allant jusqu'à un point précis du graphe (les noeuds répondant à une recherche de chemin sont gardés en mémoire), les liens inverses qui permettent de remonter à partir du dernier noeud atteint par une question (si la question était, par exemple, quels sont les lieux touristiques atteignables depuis la ville de Paris, le lien inverse permettrait d'obtenir toutes les villes permettant d'atteindre Paris), des fonctions permettant d'atteindre directement les noeuds visités lors d'une recherche de chemin, une fonction de restriction par l'imposition de critère (ne parcourir que les villes de France lors de la recherche d'un chemin de Paris à Lyon, par exemple).

GRAM intègre également une fonction de zoom qui permet à partir d'une ville ("VILLE") par exemple de visualiser tous les monuments de cette ville ("Monument") uniquement en appliquant sur cette ville l'opération zoom. Cette fonction est rendue possible par le fait que VILLE représente une généralisation de MONUMENT, car une VILLE contient des MONUMENTS. Cependant, cette notion de zoom permet simplement de poser des requêtes à l'ensemble de ces monuments, sans avoir besoin de les parcourir un à un.

GRAM implique une notion de hiérarchisation des données : un noeud d'une hyperwalk expression peut représenter le point d'entrée vers un autre graphe qui représentera un sous-réseau de ce noeud. Par exemple, le noeud "VILLE" dans l'exemple précédent contient un lien vers un autre graphe formé des sommets "Monument" et "Hôtel". Les sommets "Monument" et "Hôtel" peuvent être atteints uniquement en passant par le sommet "VILLE".
Cette notion représente un début de notion de "multi-détails". Cependant, cette notion n'est pas suffisante pour permettre de poser des requêtes d'augmentation et de diminution de détails à la base de données : tous les chemins d'une ville à une autre (de Paris à Lyon), s'ils passent par une troisième ville (Blois) ne passent pas à l'intérieur de cette ville. Il est simplement possible, à partir de cette troisième ville, d'atteindre d'autres objets n'appartenant pas au chemin trouvé (des Monuments). Les requêtes de type D sont donc totalement irrésolubles.

Requête	R1	R2	R3	R4	R5	R6	R7	R8	R9	R10	R11
GRAM	O*	O*	O*	N	N	N	O*	O*	O*	O	O

Requête

D1

D2

D3

D4

D5

D6

C1

C2

C3

C4

C5

C6

GRAM

N

N

N

N

N

N

O

O

O

O

O

O

* : uniquement dans le cas des graphes acycliques

II-2.3 Conclusion

Les SIG logiques de type réseau intègrent relativement bien les requêtes de recherche de chemins, ainsi que les requêtes connexes à cette recherche. Cependant ils n'offrent toutefois pas la possibilité d'augmenter les détails dans un graphe. L'intégration de différents niveaux d'échelles n'est encore définie dans aucun modèle de données.

Requête	R1	R2	R3	R4	R5	R6	R7	R8	R9	R10	R11
GraphDB	O	O	O	N	O	N	N	O	N	N	N
GRAM	O*	O*	O*	N	N	N	O*	O*	O*	O	O

Requête

D1

D2

D3

D4

D5

D6

C1

C2

C3

C4

C5

C6

GraphDB

N

N

N

N

N

N

O

O

N

N

O

O

GRAM

N

N

N

N

N

N

O

O

O

O

O

O

* : uniquement dans le cas des graphes acycliques

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

Avec l'accroissement des réseaux (réseau routier de la France, réseau routier de l'Europe...), les constructeurs de SIG de type réseau prennent conscience de la nécessité de posséder différents niveaux d'échelles pour leurs données. Ainsi, si StPierre le Moûtier n'apparaît que sur des cartes au 1/10.000, il n'est cependant pas nécessaire de chercher le chemin de Paris à Lyon en passant par StPierre le Moûtier sur une carte au 1/10.000. Il est plus judicieux de chercher ce chemin sur deux cartes, une au 1/200.000 et une au 1/10.000. De la même manière, effectuer un zoom sur une carte consiste à passer d'un niveau d'échelle à l'autre. D'où la nécessité d'intégrer plusieurs niveaux d'échelle dans le SIG.

Tout comme il existe deux sortes de SIG de type réseau (logiques et physiques), il existe deux façons d'intégrer plusieurs niveaux d'échelles : soit à un niveau physique en essayant de trouver un modèle commun à plusieurs cartes, soit à un niveau conceptuel en intégrant la notion d'abstraction au modèle de données géographiques.

II-3.1 L'intégration physique

Les SIG physiques de type réseau ne sont actuellement pas capables de gérer la notion de multi-échelles. Cependant, des projets de recherche d'intégration de plusieurs cartes apparaissent. Ainsi le système SAGACE de la SAGEM intègre une notion de multi-échelles. Cette intégration n'est cependant pas réalisé de manière automatique en construisant une carte à partir d'une autre, mais manuellement, en intégrant un niveau d'échelle, puis un second et en passant d'un niveau à l'autre. Le projet GéO₂ par contre tente d'effectuer cette intégration automatiquement.

GéO₂ [23, 51, 52, 55] est un prototype de SGBD géographique construit autour du SGBD Orienté Objet O₂. Il rajoute à ce système des types de données géométriques (points, lignes, surfaces), et au langage de requêtes les fonctions (union, distance...) et prédicats (adjacence, chevauchement...) associés à des données. Conçu à l'Institut Géographique National (IGN), il constitue un modèle géographique où les données spatiales (point, ligne, surface) sont indépendantes de l'objet qu'elles représentent (tronçon de routes, rivières...). GéO₂ permet de rendre indépendants les niveaux conceptuels et internes des Bases de Données Géographiques. GéO₂ permet d'intégrer la notion de multi-échelles au monde des bases de données géographiques.
Une base de données multi-échelles est une base de données indépendante de l'échelle de représentation des données géographiques. Une base de données multi-échelles a pour principe essentiel de rester valide sur une très large gamme d'échelles. Or les bases de données géographiques actuelles n'utilisent pas, pour la plupart, cette possibilité car leurs données proviennent de cartes existantes définies à une échelle donnée.

GéO₂ a pour but de proposer un modèle indépendant de l'échelle : ce modèle intègre des données issues de la BD Carto (échelle au 1/100.000) et de la BD Topo (échelle au 1/25.000).

GéO₂ possède deux modèles de définitions : un modèle conceptuel, et un modèle interne au système. Ces deux niveaux de définition sont totalement indépendants.
Dans le modèle conceptuel, tout objet géographique est décrit à deux niveaux d'information :

- un niveau descriptif (sémantique) contenant les caractéristiques des objets (largeur d'une route, type de revêtement du sol...);

- un niveau géométrique qui fournit la localisation des objets et en gère les aspects métriques et topologiques. L'aspect métrique définit la localisation de l'objet à l'aide de primitives géométriques telles que le point, la ligne et le polygone. L'aspect topologique définit les relations entre les primitives métriques (organisation en graphe, par exemple).

Le modèle sémantique est basé sur le modèle Entité-Association [18], étendu à l'aide des mécanismes d'héritage et de propagation, ainsi que d'un modèle de localisation défini par un type abstrait de données nommé Geometry. Le mécanisme d'héritage est basé sur les concepts de spécialisation et de généralisation [67] : le type "Village" est une spécialisation du type "Ville", et le type "Ville" est une généralisation du type "Village". Le mécanisme de propagation est introduit dans le modèle à l'aide d'une association de composition qui permet d'associer une entité complexe à ses composants (par exemple, une route nationale est une entité complexe composée par un ensemble de tronçons de route). Le mécanisme de propagation permet de propager automatiquement sur toutes les entités complexes, des attributs calculés à partir des attributs définis sur les entités simples (par exemple, la longueur d'une route nationale est déduite par la somme des longueurs des tronçons de route qui la composent).

Le modèle de localisation doit permettre à l'utilisateur de s'abstraire au maximum des mécanismes utilisés pour implémenter et gérer la localisation (gestion de la topologie ou gestion de la géométrie) des entités géographiques. Le type abstrait de données Geometry est le plus petit type incluant les points, les lignes et les polygones qui est fermé pour les opérations géométriques classiques (union, intersection). Toutes les fonctions spatiales s'appliquent sur des objets de ce type et retournent un objet de ce type. Toute entité définie dans le modèle sémantique peut être localisée à l'aide d'un attribut ayant comme domaine de définition le type Geometry. Ceci permet aux entités du modèle sémantique d'être indépendantes de leur représentation géométrique.

Ainsi, un tronçon de route peut être définie (avec le formalisme O₂) de la façon suivante :

class Tronçon_de_Route (longueur : integer, nom : string, géom : Geometry)
Le modèle interne de GéO₂ permet d'implémenter les différentes structures de données susceptibles d'être utilisées dans les SIG. Un des objectifs de GéO₂ est de pouvoir utiliser facilement telle ou telle structure de données et de rendre transparent ce choix par le biais de l'héritage. Le modèle interne de GéO₂ décrit les primitives géométriques (figures de la géométrie classique comme les lignes, les points et les polygones) et les couches qui définissent l'organisation de ces primitives. Dans chaque couche géométrique, des relations différentes entre primitives existent. Ces couches géométriques seront utilisées suivant les applications à traiter.

Les couches géométriques sont au nombre de trois :

- une couche de type spaghetti dans laquelle les primitives se limitent au stockage des coordonnées, de façon indépendante les unes des autres. Aucune relation n'existe entre les primitives géométriques. Ce type de structure ne permet aucun traitement d'analyse sur les données et est utilisé essentiellement à des vues de graphisme.
- une couche de type réseau correspondant à un modèle de réseau non planaire. Les faces d'un graphe ne peuvent pas être définies puisqu'un arc peut "passer au-dessus" d'un autre arc sans qu'il y ait obligatoirement une intersection : la primitive surfacique (polygone) est donc définie par son périmètre et non par sa surface.

Une relation topologique particulière existe : la relation "a pour sommet suivant" qui relie une primitive ponctuelle et une primitive linéaire, et la relation "a pour arc suivant" qui relie deux primitives linéaires. Cette couche est dédiée aux applications possédant une forte composante aspect navigationnel dans un graphe.

- une couche carte topologique correspondant à un modèle de graphe planaire. La primitive surfacique est bien définie et la notion de face (relation "face droite" ou "face gauche") existe. Cette couche permet aux applications de traiter des cas d'analyse spatiale (zones d'adjacence, partage de limites entre parcelles...).
Une couche géométrique peut être vue comme une abstraction regroupant l'ensemble des primitives géométriques représentant les entités géographiques. Certaines fonctions seront associées aux types des entités, tandis que d'autres, réalisables uniquement dans une couche donnée sont associées au niveau des couches géométriques.
Un lien de cardinalité est établi entre le niveau sémantique et le niveau géométrique du modèle conceptuel de GéO₂, un attribut de type Geometry étant défini comme étant un ensemble de primitives géométriques (points, lignes ou polygones). Une entité peut donc éventuellement avoir plusieurs représentations géométriques, chaque représentation appartenant à une couche géométrique. Ceci permet de poser à la fois des requêtes de type analyse spatiale (requêtes thématiques), et des requêtes de type réseau aux mêmes données (sémantiquement identiques).
Le but de GéO₂ n'est pas de pouvoir résoudre des requêtes posées par un utilisateur, mais de construire un modèle de données capable de pouvoir gérer différents niveaux d'échelles, de fusionner en une seule base de données des informations récoltées à des échelles différentes. L'objectif de ce système est d'intégrer les caractéristiques sémantiques des objets provenant de la BD Topo et de la BD Carto, afin de réaliser un unique modèle sémantique, mais de conserver distinctes les couches géométriques des deux BD.
L'intégration des deux modèles sémantiques distincts se fait à l'aide des mécanismes d'héritage et d'agrégation-généralisation. Les deux schémas sémantiques sont transformés (éventuellement en créant des nouveaux types "généralisants") afin de ne plus en former qu'un seul. Chaque entité du modèle sémantique possède un attribut de localisation. Tout le problème d'agrégation-généralisation se pose sur cet attribut. Trois règles ont été mises en place dans GéO₂ :

- lorsqu'un type d'entité (aires de péages autoroutiers) correspond à plusieurs types d'entités (type équipement_routier pour la BDCarto, et Aire_péage pour la BDTopo), une relation d'agrégation est construite entre ces types. L'attribut de localisation apparaîtra à plusieurs niveaux. Pour chaque entité, il est possible d'obtenir une localisation grossière ou plus fine, la géométrie la plus fine étant obtenue par l'agrégation d'éléments plus précis.

Ainsi, dans l'exemple suivant, une géométrie grossière correspond à l'attribut geom_BDCarto, alors qu'une géométrie plus précise (plus "spécialisée") correspond aux éléments Aire et Péage possédant chacun un élément geom_BDTopo.


Figure I-25. Types d'entités correspondants
- Lorsque les types d'entités sont équivalents, c'est-à-dire lorsqu'ils portent le même nom et contiennent les mêmes entités géographiques, une double géométrie est mise en place sur l'entité. Il y aura alors deux attributs de localisation sur un unique type d'entité.


Figure I-26. types d'entités équivalents
- lorsque les types d'entités portent le même nom mais ne contiennent pas les mêmes entités géographiques (ils sont quasi-équivalents), une relation d'agrégation est construite entre les types d'entités. Ce cas correspond à une différence d'échelle importante entre les types d'entités (un tronçon de route BDCarto correspond à une échelle beaucoup moins précise qu'un tronçon de route BDTopo).



Figure I-27. types d'entités quasi-équivalents
La notion d'agrégation, alliée à la notion de couches géométriques permet donc de construire une base de données multi-échelles.

GéO₂ étudie la construction de cette BD multi-échelles. Il ne construit aucune requête sur ces données. L'ensemble de requêtes défini précédemment ne sera donc pas applicable ici.

II-3.2 L'intégration logique

La composante recherche de chemins avec une notion d'échelle n'existe réellement sur aucun des SIG logiques étudiés. Cette composante est cependant essentielle, les données géographiques n'étant pas toujours saisies à la même échelle. Certains systèmes d'information géographique tentent toutefois d'intégrer la composante "échelle" à leurs données. Le système GRAM, par exemple, modélise cette composante en faisant dépendre les données d'une échelle inférieure (réseau des bus de la ville de Paris) des données d'une échelle supérieure (ville de Paris).

L'intégration de différents niveaux d'échelles au niveau des SIG logiques est similaire au principe du multi-échelles dans le domaine de l'intelligence artificielle. En effet, le raisonnement humain, lorsqu'il recherche un chemin d'un point à un autre, "hiérarchise" souvent le problème : rechercher un chemin depuis la Porte de la Chapelle à Paris jusqu'au Parc de la Tête d'Or à Lyon consiste souvent à rechercher le chemin depuis la Porte de la Chapelle jusqu'à la sortie de Paris, puis à rechercher le chemin de Paris jusqu'à Lyon, et enfin à rechercher le chemin depuis l'entrée de Lyon jusqu'au Parc de la Tête d'Or. De la même manière, un conducteur routier commence par regarder le chemin à effectuer dans sa globalité, puis, lorsqu'il est sur le chemin, il regarde la sortie d'autoroute à emprunter. Ces deux exemples nécessitent l'utilisation de deux échelles différentes de données. Nous présenterons, pour ces systèmes du domaine de l'intelligence artificielle, un modèle de raisonnement, et un modèle conceptuel de données permettant de retrouver un chemin dans un graphe.
De nombreux projets de recherche en intelligence artificielle s'intéressent à la façon dont l'utilisateur raisonne, en particulier à la façon dont il hiérarchise ses problèmes afin de les résoudre petit à petit. Une bonne illustration de ce principe de hiérarchisation est le parcours d'un réseau routier.

Le type de raisonnement utilisé pour retrouver un chemin dans l'espace peut être modélisé à l'aide de différents niveaux de détails, chaque niveau étant plus précis que le niveau supérieur précédent, et chaque niveau représentant une généralisation du niveau inférieur suivant.

Chaque niveau de raisonnement est donc dépendant des autres niveaux. Pour un réseau ferroviaire, par exemple, il pourrait n'y avoir que deux niveaux : un niveau d'instructions précises et un niveau de conduite, le plan de route étant établi par des tierces personnes.
Le modèle conceptuel défini dans [58] identifie trois niveaux de compréhension d'un chemin routier. Ces trois niveaux sont basés sur les différentes tâches qui peuvent être trouvées dans le processus de navigation : établir un plan de route général, donner et recevoir des instructions plus précises sur la route immédiate à suivre, et conduire. Un conducteur utilise pour sa conduite des cartes mentales correspondant à ces trois niveaux. Chacun de ces niveaux est modélisé à l'aide de spécifications algébriques. Seuls les niveaux sont modélisés : aucun opérateur n'est défini sur ces niveaux car tel n'est pas le but de ce modèle. Le chemin routier étudié est le système autoroutier français.

Le premier niveau de compréhension, le niveau prévisionnel, est modélisé à l'aide de noeuds et d'arcs. Il représente la prévision du chemin à parcourir (villes à traverser, routes à emprunter). Il permet de représenter la connectivité existant entre les différents arcs. Ce niveau est utilisé pour trouver un chemin de haut niveau et juger de la faisabilité ou non du trajet (en terme de coût, de distance...). Trois objets sont définis dans ce niveau : Autoroute (ensemble d'arcs entre deux noeuds), Place (noeud du graphe où passe un autoroute), et Echangeur (noeud où passe plus d'une autoroute).

Figure I-28. Niveau prévisionnel
Le second niveau est le niveau des instructions. Il contient les mêmes données que précédemment auxquelles sont rajoutées les notions de direction et de croisement. Un noeud du premier niveau représentera un ensemble de flèches dans le second niveau (cas d'un rond-point par exemple, ou d'un échangeur d'autoroute), tout comme dans le standard GDF. Ce niveau représente les instructions qu'un copilote pourrait donner au conducteur pour suivre le chemin (au rond-point tourner à la première à droite....).


Figure I-29. Niveau des instructions
Le troisième niveau représente le niveau du conducteur. Il rajoute au niveau précédent les notions d'entrée et de sortie d'une route, d'aire de rangement, de ponts, de lignes médianes sur la route... Il représente le niveau de ce que le conducteur voit réellement et qui lui sont utiles pour conduire.


Figure I-30. Niveau du conducteur
Ce modèle montre l'importance du multi-échelles de raisonnement dans un système géographique. Le multi-échelles spatial pour les SIG correspond à un système de raisonnement multi-échelles. Ce type de raisonnement est la façon la plus naturelle de raisonner dans le domaine de la géographie.
Le modèle présenté dans [17] illustre un autre principe de hiérarchisation (également appliqué dans [16]). Le but de cette étude est de montrer l'existence d'un raisonnement spatial qui applique un principe de hiérarchie pour subdiviser les tâches ou l'espace. L'exemple précédent représente un principe de hiérarchie appliqué à la subdivision des tâches. L'exemple choisi par [17], illustré sur le réseau routier, représente un principe de hiérarchie appliqué à la subdivision de l'espace. Ce principe de hiérarchie s'applique là où des algorithmes classiques de recherche de chemins dans des graphes ne sont pas efficaces car appliqués sur des graphes très importants (en taille). L'application du raisonnement spatial hiérarchisé autorise à trouver rapidement un chemin dans de très grands réseaux.
Cette méthode est intéressante car chaque niveau de la hiérarchie en question contient le même type d'objets et d'opérations. La différence se trouve uniquement dans la résolution et le détail de cette résolution. Dans cette méthode, un réseau est approximé par une grille. Chaque intersection de la grille représente un noeud du graphe, et chaque branche de la grille un arc entre deux noeuds. Cette grille est subdivisée en plusieurs autres grilles plus petites, et ainsi de suite. Une grille se trouve à un niveau donné de la hiérarchie. Prenons par exemple une grille de niveau 0 (le plus haut niveau). Les quatre points extrêmes de cette grille sont notés A₀, B₀, C₀, D₀. Cette grille est subdivisée en plusieurs autres grilles, de taille constante, dont chacune des extrémités s'appelle A₁, B₁, C₁, D₁... Le niveau 1 de la hiérarchie contient la grille de niveau 0 et toutes les grilles divisant la grille de niveau 0. Une "sous-grille" est appelée une cellule. Chaque arc d'une grille de niveau 0 a une longueur d fixée. La distance entre chaque point d'une grille est donc constante et égale à d, d/n, d/n²... (où n représente le nombre de subdivisions imposé pour une grille). Les points sont donc placés sur cette grille en approximant leur distance pour la faire correspondre à un multiple de d, d/n, d/n².... Il s'agit là d'une représentation logique de l'information, qui peut également correspondre à une représentation physique.


Figure I-31. Une grille de niveau 1
Il est possible de passer d'un niveau à un autre uniquement par l'intermédiaire des points extrêmes des cellules (A_i, B_i, C_i, D_i).

Supposons par exemple que l'usager veuille aller de la Porte de la Chapelle de Paris au Parc de la Tête d'Or à Lyon. Le réseau national français pourra être représenté par une grille dont un des noeuds (par forcément un des noeuds extrêmes) sera Lyon. Paris sera représenté par une cellule et possédera donc quatre points d'entrée possibles. La cellule représentant Paris identifiera le réseau routier parisien, et Porte de la Chapelle sera l'un des noeuds de cette cellule. Le chemin consistera donc à aller de la Porte de la Chapelle de Paris au noeud extrême de la cellule le plus proche, puis à aller de ce noeud extrême au noeud identifiant Lyon, dans la grille du niveau 0, et du noeud identifiant Lyon au noeud de la cellule de niveau 1 identifiant le Parc de la Tête d'Or à Lyon.

Figure I-32. Chemin de la Porte de la Chapelle à Paris au Parc de la Tête d'Or à Lyon
Ce modèle représente un principe de raisonnement hiérarchique : l'utilisateur pensera qu'il lui faut d'abord aller de la Porte de la Chapelle à Paris à la sortie de Paris, puis de Paris à Lyon, et de l'entrée de Lyon au Parc de la Tête d'Or. Il ne représente pas une véritable organisation multi-échelles spatiales puisqu'il est impossible de visualiser les informations du niveau 1 (c'est-à-dire les réseaux internes aux villes, par exemple), sans visualiser les informations du niveau 0 (c'est-à-dire tout le réseau des villes). De plus, dans la pratique, et sur des cartes comportant un nombre considérable de données, ce raisonnement est inapplicable car il nécessite de réorganiser la carte suivant un quadrillage, opération fort coûteuse en temps. Cependant, il donne une bonne indication de ce qu'il est nécessaire d'utiliser dans un SIG pour opérer une recherche de chemin de la même manière que l'utilisateur recherche un chemin lui-même.
Cette intégration de différents niveaux d'échelles de raisonnement permet de montrer le raisonnement normal d'un utilisateur face à une recherche de chemin sur une carte. Il est souhaitable d'utiliser ce type de raisonnement dans les systèmes d'information géographique afin d'intégrer différents niveaux d'échelles spatiales.