Manipulations of Graphs with a Visual Query Language:
Application to a Geographical Information System
Brossier-Wansek A.*,** Mainguenaud M.** FRANCE TELECOM **Cellule d'Etudes en Géographie Numérique Institut National des Télécommunications 16bis Av. Prieur de la Côte d'Or
9 rue Charles FOURIER F94114 ARCUEIL Cedex - FRANCE
F91011 EVRY - FRANCE
+ 33 1 60 76 47 82
+ 33 1 60 77 20 06 (fax)
Email: Anne.Wansek@int-evry.fr, Michel.Mainguenaud@int-evry.fr
Abstract:
Operators for geographical databases can be classified into two categories: thematic-oriented operators and network-oriented operators. Thematic-oriented operators are based on geometric representations (e.g., intersection, inclusion, adjacency). Network-oriented operators are based on graph manipulations whatever the geometric representation is (e.g., a transitive closure of a graph).
In this paper we present network manipulations with a visual query language for a geographical database. A query is defined with a visual expression defined with a Query-By-Example approach. The user draws a graphic representing the properties results have to verify.
Keyword: Visual query language, Graph manipulations, Geographical Information System
In current research toward the design of more powerful tools for urban planning and remote sensing, different research groups are simultaneously concentrating their work on Geographical Information Systems (GIS). GIS needs are very well known [19]. Nevertheless, several problems are still open.
The need for a spatial query language has been identified. Traditionnally, operators for geographical databases are classified into two categories: thematic-oriented operators and network-oriented operators. This distinction is due to the lack of common data structures (and operators). Thematic-oriented operators are based on geometric representations (e.g., intersection, inclusion, adjacency). Network-oriented operators are based on graph manipulations whatever the geometric representation is (e.g., a transitive closure of a graph).
Visual languages are very promising. Propositions for such languages are detailed for example in [1,8,10,11,17,18]. A query language is said to be visual whenever the semantics of a query is expressed by a drawing. It is said to be declarative whenever a query specifies the properties to be verified by the results, but not the way of obtaining them (i.e., imperative). This paper is based on the Cigales experiment. Cigales [6,7] is a visual and declarative query language for GIS.
We focus, here, on the design of a visual query language to handle networks in a GIS. This issue is one of the most important to deal with when building spatial information systems. It will be increasingly true since the geographic information is now affecting non-specialist users and general applications such as tourism.
Part II presents a brief overview of the graph data model; Part III, the graph manipulation part of a visual query language for GIS; Part IV, the conclusion.
The user graph data model is based on graph theory [3] and is similar to the definition presented in [1, 8]. The database graph data model is based on the graph data model defined in [12,15]. Nevertheless, this data structuring is not visible from the user interface level. In this part, we present the user graph data model, its associated operators and a toy database used along this paper.
The user graph data model (i.e., visible from the interface level) is based on the concepts of nodes and edges. A graph is a triplet G (N, E, [[Psi]]) where N is a set of nodes, E is a subset of the Cartesian product N x N and [[Psi]] is an incidence function mapping E to N x N. The formal definition is presented in Figure II.1.
A graph G (N, E, [[Psi]]) is defined as follows:
N = {n1, ... , np}
E = { (ni, nj) / ni [[appartient]] N, nj [[appartient]] N }
(ni is said to be the initial node and nj is said to be
the end node for an edge (ni, nj))
Figure II.1 - Formal definition of a graph
A node is used to model for example a town. An edge is used to model for example a link between two towns. In this paper, a graph is considered as orientated (i.e., the order, initial node / end node, is relevant). Nodes and edges are labelled. Several edges may be defined with the same initial and end nodes. We do not limit this number but we do not allow an edge (ni, ni). We extend the graph definition with a labelling function, [[nu]], defined on nodes and with a labelling function, [[epsilon]], defined on edges. Let D1, ..., Dn be database domains. Figure II.2 presents the complete definition of the user graph data model.
[[nu]] : N -> Di x ... x Dj
[[epsilon]] : E -> Dk x ... x Dm
A graph G is defined by: G (N, E, [[Psi]], [[nu]], [[epsilon]])
Figure II.2 - Complete definition of a graph
Graph manipulations, accessible from the user interface, are divided into three classes: evaluation of paths, inclusion and intersection.
The evaluation of path is performed with a Path operator. This evaluation corresponds to the detection of acyclic paths between an origin and a destination. This path can be a direct link (i.e., a successor in a graph) or a more complex path (i.e., a transitive closure of a graph).
Three operators are defined to handle the inclusion. The first operator is an extraction of nodes in a path. The second operator is an inclusion between two sets of nodes. The third operator is an inclusion between two sets of edges.
Two operators are defined to handle the intersection. The first operator is an intersection of two sets of nodes. The second operator is an intersection of two sets of edges.
This paper deals with the Path operator. It presents the visual definition of a query involving this operator. A formal signature (taking into account constraints) of this operator is presented in [13]. Inclusion and intersection are handled as defined in [6,7].
To simplify the presentation, let us use the relational model extended with Abstract Data Types [20] as the data model of the user interface (i.e., to model the labelling functions [[nu]] and [[epsilon]]). The relational model is now widely accepted [21], but an object-oriented data model or a semantic data model could have been used. An abstract data type, Spatial_representation_type, models spatial representations (i.e., the domain of the Spatial_representation attribute). Figure II.3 presents the conceptual level of a toy database borrowed from a tourism application.
User's schema
Town (Name, Population, Economical_activity, Hotel_cost,
Spatial_representation)
Transport (Name, Company, Transport_cost, Departure_hour, Arrival_hour,
Spatial_representation)
Database schema
Town (Name, Population, Economical_activity, Hotel_cost,
Spatial_representation)
Transport (Name, Origin, Destination,
Company, Transport_cost, Departure_hour, Arrival_hour,
Spatial_representation)
Figure II.3 - The conceptual database
Let us define a graph G (N, E, [[Psi]], [[nu]], [[epsilon]]) modelled with the Town and Transport relations (i.e., the nodes and the edges). The user's schema is composed of two relations (i.e., the labelling functions [[nu]] and [[epsilon]]). Visual queries are defined on this schema. The database schema is composed of two relations. The Town relation models the node labelling function, [[nu]]. The Transport relation represents an element of the Cartesian Product, N x N, and the edge labelling function, [[epsilon]]. The formal modelling of a visual query is defined on this schema. To illustrate the query language, let us define seven queries on this database (see [4] for a logical benchmark to evaluate the expressive power of a query language for GIS).
Let Q1 be the following query: "What are the direct flights with the AF company from Paris to Lausanne such as the departure time is later than 10:00 am and earlier than 3:00 pm and such as the price is less than 500 FF?". Query Q1 requires evaluating the direct link operator. This query is a relational selection on the Transport relation.
Let Q2 be the following query: "What are the routes from Paris to Lausanne with the AF company such as the total transport cost is less than 800 FF and the total time of inter-connection is less than 2 hours?". Query Q2 requires the computation of a path operator in graph G with constraints on edges. This query is a transitive closure on relation Transport with two aggregate functions: the sum of the Transport_cost attribute and the sum of the differences between Departure_hour of edge i+1 and Arrival_hour of edge i.
Let Q3 be the following query: "What are the routes from Paris to Lausanne only visiting major towns (i.e., for each town, the population is larger than 100,000 inhabitants or the economical activity is tourism)?". Query Q3 requires a path operator with a constraint on nodes. This query is a selection on the Town relation, a join with the Transport relation and a transitive closure.
Let Q4 be the following query: "What are the routes from Paris to Lausanne such as the total cost (hotel+transport) is less than 1,000 FF?". Query Q4 requires a path operator with constraints on nodes and edges. This query is a transitive closure on relation Transport with an aggregate function using a join on relation Town.
Let Q5 be the following query: "What are the routes from Paris to Lausanne such as the total time of transport is less than 4 hours". Query Q5 requires a path operator (i.e., a transitive closure on relation Transport) with a constraint involving the first and the last edges (i.e., the difference between the departure hour from Paris and the arrival hour in Lausanne is less than 4 hours).
Let Q6 be the following query: "What are the routes from Paris to Lausanne (1) leaving Paris with the AF company; (2) and then using the train up to Lausanne or using the bus up to Lausanne?". Query Q6 requires a path operator (i.e., a transitive closure on relation Transport) with a regular expression on edges [8].
Let Q7 be the following query: "What are the routes from Paris to Lausanne (1) leaving Paris with the AF company; (2) then using the train or the bus such as at each stop, the cost of a hotel is less than 200 SF and (3) finally arriving to Lausanne by bus". Query Q7 requires a path operator (i.e., a transitive closure on relation Transport) with a regular expression involving nodes and edges.
The first section presents some visual query languages to manage graphs. All of them are based at the user level on the same definition of a graph. The second and third sections present the Cigales query language from the user's point of view, to solve queries using either the direct link operator (query Q1) or the path operator (queries Q2 up to Q7).
We present here a short overview of visual query languages to manage graphs. The two first one (G+ and QBD*) are designed to query a conventional database. The third one (Cigales) is designed to query a spatial database (i.e., with thematic-oriented operators).
G+ [8] is a language derived from a language called G. In G, a graphical query Q on a graph G is a set of labelled directed multi-graphs in which the node labels of Q may be either variables or constants and the edge labels are regular expression defined over n-tuples of variables and constants.
An edge which is labelled by a regular expression containing the positive closure operator (+) is drawn as a dashed edge in Q. A query is extended with a summary graph and summary operators. A summary graph tells the system how to restructure the answers before presenting them to the user. Summary operators allow to compute aggregate functions over paths and sets of paths.
The semantics of the graph query language is based on the existence of mappings known as homeomorphisms from query graphs to database graphs. Homeomorphisms formalize the idea of a subgraph of the database graph being "similar" to the query graph. A query graph represents a pattern; answering the query will require searching the database graph to find all subgraphs that are "similar" to the pattern.
Query Q1 is represented by a graph composed of two nodes labelled Paris and Lausanne. The edge is a tuple defined with constraints on the attributes (i.e., departure_hour, arrival_hour and price).
Nevertheless, the graphical visualisation of query Q6, for example, is not very intuitive (even if the basic concept is a regular expression). A user defines a regular expression from the keyboard. A Query-By-Example philosophy should be preferable.
The goal of QBD* (Query By Diagram*)[1] is to achieve user friendliness for a large amount of user types by means of a uniform graphical interface and a visual language. This system is based on four basic ideas: (1) to represent the intentional part of the database by means of a conceptual model (Entity-Relationship augmented by the introduction of generalization abstractions); (2) to employ a fully graphical environment as a user friendly interface with the system; (3) to study the formal properties of the graphical language by defining an isomorphic textual language; and (4) to extend the graphical constructs of the language in order to easily express a significant class of recursive queries (e.g., transitive closure).
QBD* is mainly a navigational language on ER diagrams. The operations of the relational algebra may be expressed directly by picking up symbols (entities or relationships) in the diagram and posing conditions on their attributes by means of a simple windowing mechanism. Recursive queries are also expressed by the same mechanism, the difference being the preselection of a particular icon that signals the beginning of a recursive session. In this way, the textual interaction is completely eliminated and the complexity of some query is transparent to the user.
The general structure of the query is based on the location of a distinguished concept, call the main concept (an entity or a relationship), that can be seen as the entry point of one or more subqueries. These subqueries express possible navigations from the main concept to other concepts in the schema. The subqueries can be combined by means of the usual union and intersection operators. Once the main concept has been selected, two different types of primitives are available for navigation in the schema. The first one allows the user to follow paths of concepts. The second one is used for comparing two concepts which are not directly connected to each other. Two such primitives can be arbitrarily nested.
Nevertheless, it is not clear how (1) queries involving conditions on the first and last edge are handled (query Q5); (2) aggregate function involving nodes and/or edges are handled (Query Q3, Q4).
Cigales is a visual and declarative query language for GIS based on a Query-By-Example approach. This language is visual because a query is defined by a drawing. This language is declarative because a query only defines the properties to be verified by the results. A detailed definition of the query language is presented in [7]. Cigales uses metaphores to avoid visual overload. Thus a visual query is a symbolization of a textual query.
Cigales is designed to be an upper layer of a spatial Data Base Management System (DBMS). Two metaphores, a zone and a line, represent database objects. Their semantics are defined by a Data Model Function (i.e., the definition of selection criteria applied to the labelling functions [[nu]] and [[epsilon]]). Five spatial operators are available at the user interface level: inclusion, intersection, adjacency, straigth line and path. Several other operators are available such as union, difference but the user is not awared of their existence. The drawing process automatically generates these operators. A query is graphically built from a combination of metaphores and operators. This query is, then, translated into a formal expression based on a functional language [13], to be compiled into DBMS understandable orders. Figure III.1 presents the graphical editor used to define a query. Cigales offers a unique path operator at the user-interface level. This operator stands either for the direct link operator and for the path operator. The relevant choice is performed by the user before defining the Data Model Function (Figure III.2).
A direct link operator requires specifying alphanumeric properties on edges of a graph (i.e., for the Transport relation in our example). The expressive power is equivalent to the From, Where, Group By and Having clauses of SQL.
A selection criterion is defined by a triplet (attribute, operator, value). An implicit conjunction is defined between triplets. Moreover, each attribute may also have a value defined as a conjunction (e.g., the departure hour is later than 10:00 am and earlier than 3:00 pm - query Q1). The disjunction is graphically defined with the notion of page (i.e., Page 1, Page 2, ..., Page i). Each page has the same structure and allows one to define alphanumeric properties. A horizontal scrollbar allows to move from one page to another. This disjunction may be defined on one attribute (the departure hour is earlier than 10:00 am or later than 3:00 pm). It may also involve several attributes (i.e., the population is greater than 100,000 inhabitants or the activity is tourism - query Q3). Details of other operators are presented in [5]. Figure III.3 presents the visualization of the Data Model Function associated with the direct link operator. This formalism is more intuitive for a non-specialist end user than SQL-like syntaxes.
Queries Q2, Q3, Q4, Q5, Q6 and Q7 require computing a path operator. These queries illustrate two kinds of constraints. Queries Q2, Q3, Q4 and Q5 define constraints involving a complete path. Query Q6 and Q7 define constraints involving an edge-by-edge definition of a path. Therefore, the Data Model Function associated with the path operator is composed of two parts: a "Global conditions" part and a "Transportation" part.
III.3.1. Constraints on a complete path ("Global conditions")
Three kinds of constraints can be defined on a complete path. A constraint may be defined on edges (e.g., query Q2), on nodes (e.g., query Q3) or on both edges and nodes (e.g., query Q4). Thus, the window defining the global conditions is divided into three parts.
Two kinds of constraints can be defined on edges. A constraint may involve a unary function (i.e., involving a unique parameter) or may involve a n-ary function (i.e., involving two or several parameters). The constraint: "the total transport cost of a travel is less than 800 FF of query Q2" is an example of a unary function (i.e., an aggregate function on the attribute Transport_cost). The constraint: "the total time of interconnection is less than two hours of query Q2" is an example of a n-ary function (i.e., an aggregate function involving a binary relationship between the attributes Arrival_hour and Departure_hour).
The constraint definition process involving a unary function is similar to the direct link definition process. The only difference is the addition of an aggregate function. This function is defined for each attribute depending on its type (i.e., alphanumeric, integer). Such a constraint is valid for each edge of a path (i.e., Each qualification - query Q3) or for the entire path (i.e., total cost of a travel - query Q2). Figure III.4 presents the Data Model Function for a unary function.
The constraint definition process involving a n-ary function relies on a visual sub-language. To simplify the presentation, let us consider a binary relationship. Cigales defines a generic schema of a path. This path presents four specific edges labelled 1, i, i+1, n. The user selects attributes corresponding to these edges. The two icons modelling the retained attributes appear in the form below the schema. The user defines the aggregate function (if it is needed), the mathematical operator, the comparison operator and a value (i.e., the sum of differences between the departure hour of edge i+1 and the arrival hour of edge i is less than two hours - query Q2 - or the difference between Arrival_hour of edge n and Departure_hour of edge 1 - Query Q5). Figure III.5 presents the Data Model Function for a n-ary function (Query Q2).
Two kinds of constraints can be defined on nodes: a constraint may involve a unary function or a n-ary function.
The constraint definition process involving a unary function is similar to the constraint definition process involving a unary function for an edge.
The constraint definition process involving a n-ary function is similar to the constraint definition process involving a n-ary function for an edge. The only difference relies on labels associated with the generic schema of a path. They are defined on nodes instead of on edges. Figure III.6 presents the Data Model Function associated with query Q3 "What are the routes from Paris to Lausanne only visiting major towns (i.e., for each town, the population is larger than 100,000 inhabitants or the economical activity is tourism)?".
The constraints involving both edges and nodes are similar to a n-ary function (at least one attribute for an edge and one for a node). The generic schema of a path is made of four components labelled edge i, node i, edge i+1, node i+1. The philosophy of the constraint definition process is similar to the previous definitions of n-ary functions. Figure III.7 presents the Data Model Function associated with query Q4 "What are the routes from Paris to Lausanne such as the cost (hotel+transport) is less than 1,000 FF?".
One can remark that results of queries involving aggregate functions can not be defined as the union of paths. As soon as a node (except the origin of the path and the destination of a path) belongs to two paths, the definition of the results as the union of paths leads to ambiguities [14] since results must be graphically presented.
III.3.2. Constraints edge-by-edge ("Transportation")
This second kind of constraints requires specifying a regular expression associated with a path. This edge-by-edge definition provides a very strong expressive power. As shown in [16], some classes of queries lead to a NP-complete problem. We restrict the expressive power to a sub-set of computable queries [9]. This part defines the retained expressive power and presents the graphical definition of these constraints.
III.3.2.1. Required expressive power
To simplify the presentation, let us consider a unique domain called D0. Let D0 be {d0, ..., dn}. Let [[nu]] be a one-to-one node labelling function that associates with each node a distinct value drawn from domain D0. Let [[epsilon]] be an edge labelling function which associates with each edge a distinct value drawn from domain D0.
An edge-by-edge constraint is defined with a regular expression. This expression is built from a triplet (Ni, Ek, Nj) label. Let Ni be the label associated with a node ni (a disjunction of elements of D0). Let Nj be the label associated with a node nj (a disjunction of elements of D0). Let Ek be the label associated with an edge ek defined between ni and nj (a disjunction of elements of D0). Let - (the hyphen) be any value of D0. The following rules define a query label:
(1) (Ni, Ek, Nj) is a query label (2) (Ni, Ek, -) is a query label (3) (-, Ek, Nj) is a query label (4) (-, Ek, -) is a query label (5) (Ni, - , Nj) is a query label (6) (Ni, -, -) is a query label (7) (-,-,Nj) is a query label (8) (-,-,-) is a query label (9) If A is a query label then [A]* is a query label (the repetition) (10) If A and B are query labels then A[[logicaland]]B is a query label (the sequence) (11) If A and B are query labels then (A[[logicalor]]B) is a query label (the alternative)
An edge-by-edge constraint is built from a recursive application of properties (1) to (11). For the time, we limit the expressive power of a regular expression modelling a path. At least one of the two properties (a) or (b) must be verified:
(a) The first node label is not a hyphen (i.e., a selection criterion is defined on a key) (b) The last node label is not a hyphen (i.e., a selection criterion is defined on a key).
Let us define a node label (Ni) or an edge label (Ek) as a disjunction of triplets (attribute operator value). Figure III.8 (respectively Figure III.9) presents the edge-by-edge constraint of query Q6 (respectively query Q7).
(Name = Paris, Company = AF, -) [[logicaland]]( ( (-,Company=Train,-) [[logicaland]] [(-,Company=Train,-)]* [[logicaland]] (-,Company=Train, Name=Lausanne) [[logicalor]] (-,Company=Train, Name=Lausanne) ) [[logicalor]] ( (-,Company = Bus,-) [[logicaland]] [(-,Company = Bus,-)]* [[logicaland]] (-,Company = Bus, Name = Lausanne) [[logicalor]]
(-,Company = Bus, Name = Lausanne) ) )
Figure III.8 - Edge-by-edge constraint of query Q6: "What are the routes from Paris to Lausanne (1) leaving Paris with the AF company; (2) and then using the train up to Lausanne or using the bus up to Lausanne?"
(Name = Paris, Company = AF, Hotel_cost < 200) [[logicaland]] [(Hotel_cost < 200, Company = Train [[logicalor]] Company = Bus, Hotel_cost < 200)]* [[logicaland]] (Hotel_cost < 200, Company = Bus, Name = Lausanne)
Figure III.9 - Edge-by-edge constraint of query Q7: "What are the routes from Paris to Lausanne (1) leaving Paris with the AF company; (2) then using the train or the bus such as at each stop, the cost of a hotel is less than 200 SF and finally arriving to Lausanne by bus"
Figure III.10 presents the Finite State Automaton (FSA) associated with query Q6. The conflict on Train (or Bus) is resolved since the choice of an edge determines an end node. Figure III.11 presents the FSA associated with query Q7.
Figure III.10 - FSA for query Q6
Figure III.11 - FSA for query Q7
III.3.2.2. Graphical representation
A visual query language must provide a visual representation of a regular expression. Thus, the interface must provide a graph drawing mechanism. The objectives are (1) to draw an edge-by-edge path; (2) to specify alphanumeric properties on nodes and edges according to the user's selection criteria.
The graphical definition of an edge-by-edge constraint is provided by a graph editor. This editor adopts the same look as the main query editor. Two areas are defined. A working area is located at the bottom. This area is used to build step-by-step sub-queries. A query area, located on the top, is used to merge sub-queries and to build a final query. Two metaphores (a zone and an arrow) obey to the same Data Model Function as for Cigales. This editor takes full advantage of the context in which a regular expression is defined: a path defined between an origin and a destination. Therefore, no operator is provided since the path definition process is on. Figure III.12 presents the graph editor.
The graphical edge-by-edge constraint is built step by step. A step defined in the working area corresponds to a sequence of query labels and must be validated (i.e., with a click on the validation button). The validation mechanism allows (1) the definition of the repetition factor (rule 9) and (2) the display of the graph drawing into the query area. The conjunction (rule 10) is implicit by a sequence of edges in the query area. The disjunction, while defining the Ni/j (respectively Ek) part of a label is provided by the Data Model Function with the mechanism of pages (i.e., company = Train [[logicalor]] company = Bus - query Q7). The disjunction in a regular expression (rule 11) is guided by the following assumption: "An end user thinks in term of disjunctive form". This disjunction is provided by a mechanism of pages for a complete path (i.e., each page represents a complete path - query Q6).
By this way, the graphical build up of a path provides a Query-By-Example definition process. Therefore a novice user easily handles a complex selection criteria (i.e., with multiple and/or conditions - query Q6). Moreover, the similitude between the Cigales editor and the graph editor about the query definition process facilitates the definition of a complex regular expression for a path. Figure III.13 (respectively Figure III.14) presents the graph editor for query Q6 (respectively Q7).
The number of applications using a Geographical Information System (GIS) is considerable. Therefore it is of prime importance to offer a powerful and friendly interface for end-users. By end-users, we mean people who may be experts in some domains other than programming (or querying) language and who want to use a GIS to meet their particular needs. Our focus is not so much on the spatial analysis itself, but on the computational environment in which it is embedded (i.e., query language expressive power, management of visual ambiguities). Visual programming languages are very promising since they are more natural than textual query languages (i.e., extended SQL) and they offer a higher level of abstraction. The interaction with a DBMS is more complex since this level of abstraction is higher. The implementation is still going on since the design of a user interface is an iterative process. The prototype[1] is developed using OSF/Motif (for the user interface), Yacc (for the analysis of the internal functional expression modelling a query), C programming language (for the query management) and an object-oriented DBMS, O2 [2], (to manage network-oriented queries) on Sun workstations.
This paper presents a brief overview of the user interface graph data model and the query definition process to manage network-oriented queries. Future work is to handle query results since several visual ambiguities may appear [14] as soon as an aggregate function is involved in the query.
Click here for Picture Figure III.1 - The graphical editor
Click here for Picture Figure III.2 - Direct link or Path operator?
Click here for Picture Figure III.3a - The Data Model Function - conjunction (the departure hour is later than 10:00 am and earlier than 3:00 pm - query Q1)
Figure III.3b - The Data Model Function - disjunction
(the departure hour is earlier than 10:00 am
or later than 3:00 pm)
Click here for Picture Figure III.4 - The Data Model Function - a unary function
(the total cost of a travel is less than 800 units - query Q2)
Click here for Picture Figure III.5a - Labelling of edge i+1 - departure hour
of edge i+1 (the sum of differences between the departure hour of edge i+1 and the arrival
hour of edge i is less than two hours - query Q2)
Click here for Picture Figure III.5b - Labelling of edge i - arrival hour of edge i
(the sum of differences between the departure hour of edge i+1 and the arrival
hour of edge i is less than two hours - query Q2)
Click here for Picture Figure III.5c - Definition of an aggregate function - the
sum of differences
(the sum of differences between the departure hour of edge i+1 and the arrival
hour of edge i is less than two hours - query Q2)
Figure III.6 - Query Q3
"What are the routes from Paris to Lausanne only visiting major towns (i.e.,
for each town, the population is larger than 100,000 inhabitants or
the economical activity is tourism)?"
Click here for Picture Figure III.7a - Labelling of edge i+1 - Transport_cost
What are the routes from Paris to Lausanne such as the cost (hotel+transport)
is less than 1,000 FF?
Click here for Picture Figure III.7b - Labelling of node i - Hotel_cost
Click here for Picture Figure III.7c - Definition of an aggregate function - Sum
Click here for Picture Figure III.12 - The graph editor
Click here for Picture Figure III.13a - Query Q6 - Page 1
"What are the routes from Paris to Lausanne (1) leaving Paris with the AF
company;
then using the train up to Lausanne"
Click here for Picture Figure III.13b - Query Q6 - Page 2
"What are the routes from Paris to Lausanne (1) leaving Paris with the AF
company;
then using the bus up to Lausanne?"
Click here for Picture Figure III.14a - Starting representation (a path from Paris
to Lausanne -
[7])
What are the routes from Paris to Lausanne (1) leaving Paris with the AF
company; (2) then using the train or the bus such as at each stop, the cost of
a hotel is less than 200 SF and (3) finally arriving to Lausanne by bus
Click here for Picture Figure III.14b - The choice of an edge
(labelled Company = AF)
Click here for Picture Figure III.14c - After the validation (first part of the path: leaving Paris
with AF)
Click here for Picture Figure III.14d - The choice of an edge (labelled Company = Train [[logicalor]]
Company = Bus) and a node (labelled Hotel_cost < 200)
Click here for Picture Figure III.14e - After the validation with a
repetition factor (dashed lines)
Click here for Picture Figure III.14f - After the choice of an edge (labelled Company = Bus) and the
validation
[1] Angelaccio M., Catarci T., Santucci G: QBD*: A Graphical Query Language
with Recursion, IEEE Transaction on Software Engineering, Vol 16, ndeg.10,
1990, p. 1150-1163
[2] Bancilhon F., Barbedette G., Benzaken V., Delobel C., Gamerman S.,
Lécluse C., Pfeffer P., Richard P., Velez F.: The Design and
Implementation of O2, an Object Oriented Database System, Proceedings of the
2nd Int. Workshop on Object-Oriented Data Base Systems, O2 Book, Morgan
Kaufmann, 1991
[3] Berge C.: Graphes, Gauthier-Villars, Paris, 1983
[4] Boursier P., Mainguenaud M.: Spatial Query Languages: Extended SQL vs.
Visual Languages vs. Hypermaps, 5th Symposium on Spatial Data Handling,
Charleston, USA, Aug. 1992
[5] Brossier-Wansek A.: La Sémantique d'une Métaphore dans un
Langage Visuel: Application à un Système d'Information
Géographique, ERGO/IA, Biarritz, France (in french), Oct. 1994
[6] Calcinelli D., Mainguenaud M.: The Management of the Ambiguities in a
Graphical Query Language for Geographical Information Systems, 2nd Symposium on
Large Spatial Databases, Zurich, Switzerland, Aug. 1991, Lecture Notes in
Computer Science ndeg. 525 (LNCS)
[7] Calcinelli D., Mainguenaud M. : CIGALES: A Visual Query Language for
Geographical Information System: the User Interface, Int. Journal of Visual
Languages and Computing, 5, 1994, 113-132
[8] Cruz IF, Mendelzon AO, Wood PT: A Graphical Query Language Supporting
Recursion, Proc. SIGMOD Conference, San-Francisco, USA, May 1987
and G+: Recursive Queries Without Recursion, Expert Database Systems,
645-666
[9] Garey MR, Johnson DS: Computers and Intractability A Guide to the Theory of
NP-Completeness, W.H. Freeman and Company, New York, 1979
[10] Kim HY and al: PICASSO: A Graphical Query Language, Software-Practice and
Experience, Vol 18(3), 169-203, March 1988, Ed. J. Wiley and Sons Ltd
[11] Kirby K.C., Pazner M.: Graphic Map Algebra, 4th Symposium on Spatial Data
Handling, Zürich, Switzerland, July 1990
[12] Langou B., Mainguenaud M.: Graph Data Operations for Network Facilities in
a Geographical Information System, 6th Symposium on Spatial Data Handling,
Edinburgh, UK, Sept. 1994
[13] Mainguenaud M.: From the User Interface to the Database Management System:
Application to a Geographical Information System, 5th Int. Conference on Human
Computer Interaction, Orlando, USA, Aug., 1993
[14] Mainguenaud M.: The Results of Geographical Information System Queries,
IEEE/CS Visual Languages'93, Bergen - Norway, Aug.,1993
[15] Mainguenaud M, Simatic XT: A Data Model to Deal with Multi-scaled
Networks, I.G.U.-U.G.I. Conference on Multi-scales Multi-uses, Brno -
Czechoslovakia 22-25 April 1991, Computer Environment and Urban System, Vol 16,
1992, ndeg.4, 281-288
[16] Mendelzon AO, Wood PT: Finding Regular Paths in Graph Databases, 15th Int.
Very Large Data Base Conference, Amsterdam, The Netherlands, Aug. 1989
[17] Myers BA (Ed.): Languages for Developing User Interfaces, Jones and
Bartlett Publishers, Boston, 1992
[18] Shu N.C.: Visual Programming, Van Nostrand Reinhold Cie, New York, 1988
[19] Smith TR, Menon S, Star JL, Ester JE: Requirements and Principles for the
Implementation and Construction of Large Scale GIS, Int. Journal of
Geographical Information System, Vol 1, nb. 1, 13-31, 1987
[20] Stemple D, Sheard T, Bunker R: Abstract Data Types in Databases:
Specification, Manipulation and Access, Int. Conference on Data Engeneering,
Los Angeles, USA, Feb. 1986
[21] Ullman JD: Principles of Database and Knowledge-base Systems, Computer
Science Press, Maryland, 1988
References
![later than 3:00 pm) Click here for Picture Figure III.4 - The Data Model Function - a unary function (the total cost of a travel is less than 800 units - query Q2) Click here for Picture Figure III.5a - Labelling of edge i+1 - departure hour of edge i+1 (the sum of differences between the departure hour of edge i+1 and the arrival hour of edge i is less than two hours - query Q2) Click here for Picture Figure III.5b - Labelling of edge i - arrival hour of edge i (the sum of differences between the departure hour of edge i+1 and the arrival hour of edge i is less than two hours - query Q2) Click here for Picture Figure III.5c - Definition of an aggregate function - the sum of differences (the sum of differences between the departure hour of edge i+1 and the arrival hour of edge i is less than two hours - query Q2) Figure III.6 - Query Q3 "What are the routes from Paris to Lausanne only visiting major towns (i.e., for each town, the population is larger than 100,000 inhabitants or the economical activity is tourism)?" Click here for Picture Figure III.7a - Labelling of edge i+1 - Transport_cost What are the routes from Paris to Lausanne such as the cost (hotel+transport) is less than 1,000 FF? Click here for Picture Figure III.7b - Labelling of node i - Hotel_cost Click here for Picture Figure III.7c - Definition of an aggregate function - Sum Click here for Picture Figure III.12 - The graph editor Click here for Picture Figure III.13a - Query Q6 - Page 1 "What are the routes from Paris to Lausanne (1) leaving Paris with the AF company; then using the train up to Lausanne" Click here for Picture Figure III.13b - Query Q6 - Page 2 "What are the routes from Paris to Lausanne (1) leaving Paris with the AF company; then using the bus up to Lausanne?" Click here for Picture Figure III.14a - Starting representation (a path from Paris to Lausanne - [7]) What are the routes from Paris to Lausanne (1) leaving Paris with the AF company; (2) then using the train or the bus such as at each stop, the cost of a hotel is less than 200 SF and (3) finally arriving to Lausanne by bus Click here for Picture Figure III.14b - The choice of an edge (labelled Company = AF) Click here for Picture Figure III.14c - After the validation (first part of the path: leaving Paris with AF) Click here for Picture Figure III.14d - The choice of an edge (labelled Company = Train [[logicalor]] Company = Bus) and a node (labelled Hotel_cost < 200) Click here for Picture Figure III.14e - After the validation with a repetition factor (dashed lines) Click here for Picture Figure III.14f - After the choice of an edge (labelled Company = Bus) and the validation References [1] Angelaccio M., Catarci T., Santucci G: QBD*: A Graphical Query Language with Recursion, IEEE Transaction on Software Engineering, Vol 16, ndeg.10, 1990, p. 1150-1163 [2] Bancilhon F., Barbedette G., Benzaken V., Delobel C., Gamerman S., Lécluse C., Pfeffer P., Richard P., Velez F.: The Design and Implementation of O2, an Object Oriented Database System, Proceedings of the 2nd Int. Workshop on Object-Oriented Data Base Systems, O2 Book, Morgan Kaufmann, 1991 [3] Berge C.: Graphes, Gauthier-Villars, Paris, 1983 [4] Boursier P., Mainguenaud M.: Spatial Query Languages: Extended SQL vs. Visual Languages vs. Hypermaps, 5th Symposium on Spatial Data Handling, Charleston, USA, Aug. 1992 [5] Brossier-Wansek A.: La Sémantique d'une Métaphore dans un Langage Visuel: Application à un Système d'Information Géographique, ERGO/IA, Biarritz, France (in french), Oct. 1994 [6] Calcinelli D., Mainguenaud M.: The Management of the Ambiguities in a Graphical Query Language for Geographical Information Systems, 2nd Symposium on Large Spatial Databases, Zurich, Switzerland, Aug. 1991, Lecture Notes in Computer Science ndeg. 525 (LNCS) [7] Calcinelli D., Mainguenaud M. : CIGALES: A Visual Query Language for Geographical Information System: the User Interface, Int. Journal of Visual Languages and Computing, 5, 1994, 113-132 [8] Cruz IF, Mendelzon AO, Wood PT: A Graphical Query Language Supporting Recursion, Proc. SIGMOD Conference, San-Francisco, USA, May 1987 and G+: Recursive Queries Without Recursion, Expert Database Systems, 645-666 [9] Garey MR, Johnson DS: Computers and Intractability A Guide to the Theory of NP-Completeness, W.H. Freeman and Company, New York, 1979 [10] Kim HY and al: PICASSO: A Graphical Query Language, Software-Practice and Experience, Vol 18(3), 169-203, March 1988, Ed. J. Wiley and Sons Ltd [11] Kirby K.C., Pazner M.: Graphic Map Algebra, 4th Symposium on Spatial Data Handling, Zürich, Switzerland, July 1990 [12] Langou B., Mainguenaud M.: Graph Data Operations for Network Facilities in a Geographical Information System, 6th Symposium on Spatial Data Handling, Edinburgh, UK, Sept. 1994 [13] Mainguenaud M.: From the User Interface to the Database Management System: Application to a Geographical Information System, 5th Int. Conference on Human Computer Interaction, Orlando, USA, Aug., 1993 [14] Mainguenaud M.: The Results of Geographical Information System Queries, IEEE/CS Visual Languages'93, Bergen - Norway, Aug.,1993 [15] Mainguenaud M, Simatic XT: A Data Model to Deal with Multi-scaled Networks, I.G.U.-U.G.I. Conference on Multi-scales Multi-uses, Brno - Czechoslovakia 22-25 April 1991, Computer Environment and Urban System, Vol 16, 1992, ndeg.4, 281-288 [16] Mendelzon AO, Wood PT: Finding Regular Paths in Graph Databases, 15th Int. Very Large Data Base Conference, Amsterdam, The Netherlands, Aug. 1989 [17] Myers BA (Ed.): Languages for Developing User Interfaces, Jones and Bartlett Publishers, Boston, 1992 [18] Shu N.C.: Visual Programming, Van Nostrand Reinhold Cie, New York, 1988 [19] Smith TR, Menon S, Star JL, Ester JE: Requirements and Principles for the Implementation and Construction of Large Scale GIS, Int. Journal of Geographical Information System, Vol 1, nb. 1, 13-31, 1987 [20] Stemple D, Sheard T, Bunker R: Abstract Data Types in Databases: Specification, Manipulation and Access, Int. Conference on Data Engeneering, Los Angeles, USA, Feb. 1986 [21] Ullman JD: Principles of Database and Knowledge-base Systems, Computer Science Press, Maryland, 1988](VDB_3b2.gif){kind=link}
