Informatique

III- Traduction des requêtes

Les opérateurs définis permettent de résoudre les requêtes du chapitre I.

Les requêtes de recherche de chemins sont résolues grâce aux opérateurs de sélection et de chemins, les requêtes d'augmentation de détails sont résolues par le biais des opérateurs de sélection et de développement, les requêtes connexes par le biais des opérateurs de sélection, d'intersection et d'inclusion.

Les critères et contraintes sont exprimées suivant le formalisme défini dans la grammaire 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 ou contrainte agrégative n'ont aucune signification en-dehors de l'opérateur de CHEMINS.

Les noeuds et arcs sur lesquels s'appliquent ces requêtes possèdent, en sus de leurs attributs décrits dans le chapitre II, un attribut "Type" ayant comme valeur "Noeud" ou "Arc".

Ces noeuds et arcs appartiennent à un graphe de référence (appelé Graphe_référence) représentant la base sur laquelle s'appliquent toutes les requêtes.

Un critère possède une partie noeud et une partie arc. La partie noeud (resp. arc) vide signifie que chaque noeud (resp. arc) vérifie le critère.

Une contrainte agrégative contient le type des éléments sur lesquels elle s’applique.

III-1. Requêtes de recherche de chemins

Les requêtes concernant la recherche de chemins nécessitent l'utilisation de l'opérateur de chemins. Sur chaque chemin recherché, des conditions (critères, contraintes régulières ou contraintes agrégatives) peuvent être définies sur les propriétés alphanumériques des entités géographiques modélisées par des sommets et des arcs dans le graphe. Les conditions de type contraintes régulières ou agrégatives sont notées en indice de l'opérateur, lorsqu'elles ne sont pas vides. Les conditions de type critère correspondent à l'application de l'opérateur de sélection sur le graphe sur lequel s'applique l'opérateur de chemins.

La requête R₁ ("Aller de Paris à Lyon en ne passant que par des villes de plus de 100000 habitants") correspond à l'application de l'opérateur de chemins avec un critère correspondant au choix des villes de plus de 100000 habitants. Cette requête peut être traduite de la manière suivante :

P_T ( ( [Type = "noeud" and Nom = "Paris"], Graphe_référence),

( [Type = "noeud" and Nom = "Lyon"], Graphe_référence),

( [(Type = "noeud" and Population > 100000)], Graphe_référence) )

La requête R₂ ("Aller de Paris à Lyon en utilisant uniquement des routes nationales et des autoroutes") peut être traduite de la manière suivante :

P_T ( ( [Type = "noeud" and Nom = "Paris"], Graphe_référence),

( [Type = "noeud" and Nom = "Lyon"], Graphe_référence),

( [ (Type = "arc" and (Type_transport = "Nationale" or Type_transport = "Autoroute"))], Graphe_référence) )

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") peut être traduite de la manière suivante :

P_T ( ( [Type = "noeud" and Nom = "Paris"], Graphe_référence),

( [Type = "noeud" and Nom = "Lyon"], Graphe_référence),

( [(Type = "noeud" and Population > 100000) and (Type = "arc" and

(Type_transport = "Nationale" or Type_transport = "Autoroute"))],Graphe_référence) )
La requête R₄ ("Aller de Paris à Lyon avec un coût d'hôtel moyen inférieur à 100F") peut être traduite de la manière suivante, en utilisant une contrainte agrégative :

P_{T [[(Type = "noeud")] and Avg (Coût_moyen_hôtel) < 100]}

( ( [Type = "noeud" and Nom = "Paris"], Graphe_référence),

( [Type = "noeud" and Nom = "Lyon"], Graphe_référence),

Graphe_référence )

La requête R₅ ("Aller de Paris à Lyon avec un coût de trajet moyen inférieur à 200F") peut être traduite de la manière suivante, en utilisant une contrainte agrégative :

P_{T [[(Type = "arc")] and Avg (Coût_transport) < 200 ]}

( ( [Type = "noeud" and Nom = "Paris"], Graphe_référence),

( [Type = "noeud" and Nom = "Lyon"], Graphe_référence),

Graphe_référence )

La requête R₆ ("Aller de Paris à Lyon avec un coût de voyage moyen (coût de trajet et coût d'hôtel) inférieur à 300F") peut être traduite de la manière suivante, en utilisant une contrainte agrégative :

P_{T [[(Type = "noeud") and (Type = "arc")] and Avg (Coût_moyen_hôtel + Coût_transport) < 300]}

( ( [Type = "noeud" and Nom = "Paris"], Graphe_référence),

( [Type = "noeud" and Nom = "Lyon"], Graphe_référence),

Graphe_référence )
La requête R₇ ("Aller de Paris à Lyon en passant par Blois puis par StPierre le Moûtier") peut être traduite de la manière suivante, en utilisant l'automate représentant une contrainte régulière :

P_{T Automate [ {[Type = "noeud" and Nom = "Paris"]} {[ Type = "arc" ]} ({[ Type = "noeud" ]} {[ Type = "arc" ]})*}

<sub>{[Type = "noeud" and Nom = "Blois"]} {[ Type = "arc" ]} ({[ Type = "noeud" ]} {[ Type = "arc" ]} )*

{[Type = "noeud" and Nom = "St Pierre le Moûtier"]} {[ Type = "arc" ]}

({[ Type = "noeud" ]} {[ Type = "arc" ]})* {[ Type = "noeud" and Nom = "Lyon" ]} ]</sub>

( ( [Type = "noeud" and Nom = "Paris"], Graphe_référence),

( [Type = "noeud" and Nom = "Lyon"], Graphe_référence),

Graphe_référence )

La requête R₈ ("Aller de Paris à Lyon en utilisant des autoroutes puis des routes nationales") peut être traduite de la manière suivante, en utilisant l'automate représentant une contrainte régulière :

P_{T Automate [{[Type = "noeud" and Nom = "Paris"]} {[ Type = "arc" and Type_transport = "Autoroute"]}}

<sub>({[ Type = "noeud" ]} {[ Type = "arc" and Type_transport = "Autoroute"]})*

{[ Type = "noeud" ]} {[ Type = "arc" and Type_transport = "Nationale"]}

({[ Type = "noeud" ]} {[ Type = "arc" and Type_transport = "Nationale"]})+*

{[ Type = "noeud" and Nom = "Lyon" ]} ]</sub>

( ( [Type = "noeud" and Nom = "Paris"], Graphe_référence),

( [Type = "noeud" and Nom = "Lyon"], Graphe_référence),

Graphe_référence )

La requête R₉ ("Aller de Paris à Lyon en utilisant des autoroutes jusqu'à Blois, puis des routes nationales de Blois à Lyon") peut être traduite de la manière suivante, en utilisant l'automate représentant une contrainte régulière :

P_{T Automate [{[Type = "noeud" and Nom = "Paris"]} {[ Type = "arc" and Type_transport = "Autoroute" ]}}

<sub>({[Type = "noeud"]} {[Type = "arc" and Type_transport = "Autoroute"]})*

{[Type = "noeud" and Nom = "Blois"]} {[ Type = "arc" ]}

({[Type = "noeud"]} {[Type = "arc" and Type_transport = "Nationale"]})+*

{[ Type = "noeud" and Nom = "Lyon" ]} ]</sub>

( ( [Type = "noeud" and Nom = "Paris"], Graphe_référence),

( [Type = "noeud" and Nom = "Lyon"], Graphe_référence),

Graphe_référence )

La requête R₁₀ ("Quelles villes de plus de 100000 habitants peut-on atteindre par des routes nationales depuis Paris ?") peut être traduite de la manière suivante :

P_T ( ( [Type = "noeud" and Nom = "Paris"], Graphe_référence),

Graphe_vide,

( [(Type = "noeud" and Population > 100000) and

(Type = "arc" and Type_transport = "Nationale")], Graphe_référence) )
La requête R₁₁ ("De quelles villes de plus de 100000 habitants peut-on partir pour atteindre Lyon par des routes nationales ?") peut être traduite de la manière suivante :

P_T ( Graphe_vide,

( [Type = "noeud" and Nom = "Lyon"], Graphe_référence),

( [(Type = "noeud" and Population > 100000) and

(Type = "arc" and Type_transport = "Nationale")], Graphe_référence) )

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

Les requêtes concernant l'augmentation des détails d'un graphe nécessitent l'utilisation des opérateurs de développement, de regroupement, et de sélection. Ces requêtes ont pour but d'obtenir plus ou moins de détails sur un chemin donné.

La requête D₁("Détailler Blois dans le chemin de Paris à Lyon, pour visualiser le chemin employé à l'intérieur de Blois") peut être traduite de la manière suivante :

Develop ( ( [Type = "noeud" and Nom = "Blois"],

P_T ( ( [Type = "noeud" and Nom = "Paris"], Graphe_référence),

( [Type = "noeud" and Nom = "Lyon"], Graphe_référence),

Graphe_référence) ),

P_T ( ( [Type = "noeud" and Nom = "Paris"], Graphe_référence),

( [Type = "noeud" and Nom = "Lyon"],Graphe_référence), Graphe_référence))

La requête D₂ ("Détailler l'arc entre Fontainebleau et Tours dans le chemin de Paris à Lyon, pour visualiser le chemin employé entre Fontainebleau et Tours") peut être traduite de la manière suivante :

Develop ( ( [Type = "arc" and Nom = "Fontainebleau-Tours par *N152"],

P_T ( ( [Type = "noeud" and Nom = "Paris"], Graphe_référence),

( [Type = "noeud" and Nom = "Lyon"], Graphe_référence),

Graphe_référence) ),

P_T ( ( [Type = "noeud" and Nom = "Paris"], Graphe_référence),

( [Type = "noeud" and Nom = "Lyon"], Graphe_référence),

Graphe_référence) )
La requête D₃ ("Détailler l'ensemble du chemin de Paris à Lyon") correspond à l'application de l'opérateur Develop* sur tous les noeuds et arcs du chemin de Paris à Lyon. Cette requête peut être traduite de la manière suivante :

Develop* ( P_T ( ( [Type = "noeud" and Nom = "Paris"], Graphe_référence),

( [Type = "noeud" and Nom = "Lyon"], Graphe_référence),

Graphe_référence),

P_T ( ( [Type = "noeud" and Nom = "Paris"], Graphe_référence),

( [Type = "noeud" and Nom = "Lyon"], Graphe_référence),

Graphe_référence) )
La requête D₄ ("Enlever les détails correspondant à Blois dans le chemin de Paris à Lyon") correspond à appliquer l'opérateur de regroupement sur un noeud ou un arc appartenant au réseau_associé de Blois. Cette requête peut être traduite de la manière suivante :

Undevelop ( ( [Type = "noeud" and Nom = "Caserne M.de Saxe"],

Develop ( ( [Type = "noeud" and Nom = "Blois"],

P_T ( ([Type="noeud" and Nom="Paris"],Graphe_référence),

([Type="noeud" and Nom="Lyon"], Graphe_référence),

Graphe_référence) ),

P_T ( ( [Type = "noeud" and Nom = "Paris"], Graphe_référence),

( [Type = "noeud" and Nom = "Lyon"], Graphe_référence),

Graphe_référence) ) ),

Develop ( ( [Type = "noeud" and Nom = "Blois"],

P_T ( ([Type="noeud" and Nom="Paris"],Graphe_référence),

([Type="noeud" and Nom="Lyon"], Graphe_référence),

Graphe_référence) ),

P_T ( ( [Type = "noeud" and Nom = "Paris"], Graphe_référence),

( [Type = "noeud" and Nom = "Lyon"], Graphe_référence),

Graphe_référence) ) )

La requête D₅ ("Enlever les détails correspondant à l'arc entre Fontainebleau et Tours dans le chemin de Paris à Lyon") correspond à appliquer l'opérateur de regroupement sur un noeud ou un arc appartenant au réseau_associé du master_arc Fontainebleau-Tours par *N152. Cette requête peut être traduite de la manière suivante :

Undevelop ( ( [Type = "arc" and Nom = "Vouvray-Tours par N152"],

Develop ( ([Type = "arc" and Nom = "Fontainebleau-Tours par *N152"],

P_T (([Type = "noeud" and Nom = "Paris"], Graphe_référence),

( [Type = "noeud" and Nom = "Lyon"], Graphe_référence),

Graphe_référence) ),

P_T ( ( [Type = "noeud" and Nom = "Paris"], Graphe_référence),

( [Type = "noeud" and Nom = "Lyon"], Graphe_référence),

Graphe_référence) ) ),

Develop ( ( [Type = "arc" and Nom = "Fontainebleau-Tours par *N152"],

P_T (([Type = "noeud" and Nom = "Paris"], Graphe_référence),

( [Type = "noeud" and Nom = "Lyon"], Graphe_référence),

Graphe_référence) ),

P_T ( ( [Type = "noeud" and Nom = "Paris"], Graphe_référence),

( [Type = "noeud" and Nom = "Lyon"], Graphe_référence),

Graphe_référence) ) )
La requête D₆ ("Enlever les détails correspondant aux noeuds et arcs du chemin de Paris à Lyon") peut être traduite de la manière suivante :
Undevelop* ( P_T ( ( [Type = "noeud" and Nom = "Paris"], Graphe_référence),

( [Type = "noeud" and Nom = "Lyon"], Graphe_référence),

Graphe_référence),

Develop* ( P_T ( ( [Type = "noeud" and Nom = "Paris"], Graphe_référence),

( [Type = "noeud" and Nom = "Lyon"], Graphe_référence),

Graphe_référence),

P_T ( ( [Type = "noeud" and Nom = "Paris"], Graphe_référence),

( [Type = "noeud" and Nom = "Lyon"], Graphe_référence),

Graphe_référence) ) )

III-3. Requêtes connexes

Les requêtes connexes à la recherche de chemin regroupent toutes les requêtes qui peuvent être posées sur le chemin résultant d'une recherche de chemin (sélection de sommets et/ou d'arcs, inclusion et intersection d'ensembles de sommets et/ou d'arcs). Ces requêtes s'apparentent aux requêtes des Systèmes de Gestion de Bases de Données classiques (e.g. sélection de tuples dans une relation) et aux requêtes de la théorie des ensembles (e.g. sélection de sommets dans un ensemble de sommets).

La requête C₁ ("Quelles sont les plus grandes villes touristiques françaises (population > 100000) ?") peut être traduite de la manière suivante :

( [Type = "noeud" and Population > 100000], Graphe_référence)

La requête C₂ ("Quelles sont les autoroutes dont le coût de trajet est très cher (coût > 10 F/km) ?") peut être traduite de la manière suivante :

( [Type = "arc" and Type_transport = "Autoroute" and Coût_transport > 10], Graphe_référence)

La requête C₃ ("Les villes traversées lors du chemin de Paris à Lyon sont-elles parmi les plus grandes villes touristiques françaises ?") peut être traduite de la manière suivante :

P_{ic_n} ( P_T ( ( [Type = "noeud" and Nom = "Paris"], Graphe_référence),

( [Type = "noeud" and Nom = "Lyon"], Graphe_référence),

Graphe_référence),

( [Type = "noeud" and Population > 100000], Graphe_référence) )
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 ?") peut être traduite de la manière suivante :

P_{ic_e} ( P_T ( ( [Type = "noeud" and Nom = "Paris"], Graphe_référence),

( [Type = "noeud" and Nom = "Lyon"], Graphe_référence),

Graphe_référence),

( [Type = "arc" and Type_transport = "Autoroute" and Coût_transport > 10],

Graphe_référence) )

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 traduite de la manière suivante :

P_{is_n} ( P_T ( ( [Type = "noeud" and Nom = "Paris"], Graphe_référence),

( [Type = "noeud" and Nom = "Lyon"], Graphe_référence),

Graphe_référence),

( [Type = "noeud" and Population > 100000], Graphe_référence) )

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 être traduite de la manière suivante :

P_{is_e} ( P_T ( ( [Type = "noeud" and Nom = "Paris"], Graphe_référence),

( [Type = "noeud" and Nom = "Lyon"], Graphe_référence),

Graphe_référence),

( [Type = "arc" and Type_transport = "Autoroute" and Coût_transport > 10],

Graphe_référence) )