% Example file for the use of the ICECS2005 style file
% --------------------------------------------------------------------------
\documentclass{article}
\usepackage{icecs2005}
% 
% For including EPS figures
%\usepackage{epsfig}
%
% or better use
\usepackage{graphicx} 
\newtheorem{definition}{Definition}[section]
\newtheorem{example}{Example}[section]
\newtheorem{hypothese}{Hypothesis}[section]
\newtheorem{property}{Property}[section]
\newtheorem{proof}{Proof}[section]
\newtheorem{remark}{Remark}[section]

% Title.
% ------
\title{Evolutive Complex Scheduling in Interaction Networks for Quality Improvment in Geographical Data Base Updating}
\name{Hakima Kadri-Dahmani$^{(1)}$, Cyrille Bertelle$^{(2)}$, G\'erard H.E. Duchamp$^{(1)}$, Aomar Osmani$^{(1)}$}
\address{$^{(1)}$ LIPN - University of Paris 13 - 99, avenue Jean-Baptiste Cl\'ement - 93430 Villetaneuse - France \\
$^{(2)}$ LIH - University of Le Havre - 25 rue Ph. Lebon - BP 540 - 76058 Le Havre cedex - France
}
%
% Single address.
% ---------------
% \name{Author(s) Name(s)\thanks{Thanks to XYZ agency for funding.}}
% \address{Author Affiliation(s)}
%
% For example:
% ------------
%\address{School\\
%   Department\\
%   Address}
%
% Four authors and two addresses example (uncomment and modify for two-address case).
% ------------------------------------------------------------------------------------
% \twoauthors
%  {Hakima KADRI-DAHMANI, Gérard H.E. DUCHAMP}
%   {LIPN - University of Paris 13\\
%   99, avenue Jean-Baptiste Clément\\
%   93430 Villetaneuse - France}
%  {Cyrille BERTELLE}
%   {LIH - University of Le Havre\\
%   25 rue Ph. Lebon - BP 540\\
%   76058 Le Havre cedex - France}
%
\begin{document}
%
%For smaller size font use the following option 
%\ninept
%
\maketitle
%

%This paper deals with the study of geo-information evolution; the diversity and the complexity of the problems that arise are addressed. We present a brief state of the art of works related to the updating process in geographic information systems. We discuss what are their respective contributions and specific weak points. Finally, we introduce a generic solution we perceive to the problem of geographic database updating. We also justify the advantage of this solution which  relies on the fact that the evolution of the geographic information is taken into account concurrently to the design of the system and not afterwards. Our challenge is to provide a computational model that make the maintenance of such systems easier.

\begin{abstract}
The aim of this paper is to propose a scheduling processus for the mechanism of geographical data bases updating in term of improvement of its quality. Because of the complex interacting network of the components involved in each updating cycle of this mechanism, a traditional analytic solver cannot success in most cases. So we propose to use an evolutionary computation based on a genetic algorithm which is well adapted for the complex interaction network of the involved components. A genetic algorithm may allow to improve the updating quality in increasing the validation rate of a transaction. 
%Because the resulting satisfaction rate obtained by the scheduling follow an irregular function, we research to minimize it using a genetic algorithm. 
%Because of the major irregularity of this scheduling, a genetic algorithm is then proposed and allow to improve the updating quality in increasing the validation rate of a transaction. 
%This work has been developped and implemented in the laboratory COGIT from IGN-France (Institut G\'eographique National).%Geographical Data Bases (GDB) have been developped since some years as the essential part of Geographical Information Systems (GIS). One major problem about their practice today deals with their updatings and this paper propose an automatic processus to make them, in respect of their consistency.
%We propose in this paper an automatic processus to allow their updating, in respect of their coherence. An integrated model based on a kernel composed of 3 modules (reasoning-based engine, data base integration and scheduler) is used. 
%These modules are (i) a reasoning engine, (ii) an integration module and (iii) a scheduler. 
%A canonical decomposition of each updating operation from a transaction, allows to describe all topological influences within a finite table. A processus of propagation is computed to obtain a local stable influence zone centered on each object involved in the updating. The consistency maintenance is based on a incremental computation which check the consistency of the GDB after each canonical operation. %In function of the degree of the infraction from the consistency, the updating transaction can be cancelled. A whole updating transaction will generate a great number of elementary operations and an appropriate scheduling of them can increase the rate of validation of the transactions, satisfying the maintenance of the whole GDB. 
%a complete process scheduling can be decisive on the the transaction validation,satisfying the maintenance of the whole GDB. 
%we propose a scheduling to ordre them. 
\end{abstract}

\vspace*{0.5in}
\vspace*{-\baselineskip}
%
\section{INTRODUCTION}
\label{sec:intro}
\begin{figure}[htbp]
\begin{center}
%\rotatebox{-90} 
{\includegraphics[scale=0.60]{CoherenceHorizontale.eps}}
\caption{Updating within consistency maintenance}
\label{coherence}
\end{center}
\end{figure}

Geomatics finds its roots in numeric geographical information defined in \cite{hkdphd} as :

\begin{definition}
Geographical information is the composition of a set of heterogeneous informations which are strongly linked to be able to describe the characteristic of a scene in the meaning of: localisation, geometry, topology and semantic.
\end{definition}

\begin{figure*}[htbp]
\begin{center}
\includegraphics[scale=0.5]{Architecture-en.eps}
\caption{EVOLA architecture}
\label{evola}
\end{center}
\end{figure*}


One of the most adequat support for this information is geographical data bases which have to involve, using a conceptual model, geometric data and semantic data. The Geographical Data Bases (GDB) based on vector representation are generally composed of layered classes of objects. Each layer is associated to a thematic like road tracing, fluvial tracing, buildings, vegetation,etc. The constant evolution of the real world which must be represented in such geographical data bases needs to regularly update the data. The knowledge which will serve the updating is generally associated to the concerned semantic layer. Each semantic layer has its own updating frequency which can differ from one layer to another. This heterogeneity can be the cause of some problems on the consistency maintenance of the whole GDB. In the figure \ref{coherence}, we describe the updating generated by a new road arrangement. The first part of this figure shows the initial map configuration. The second part shows a first uncorrect updating without checking the whole consistence, generating superposition of a new road portion over existing buildings (left bottom of the road crossing). The last part shows a correct updating after the propagation of some topological constraints between the layer of the road tracing and of the layer of the buildings position.



This example shows that a GDB must be represented with an interaction network of components to allow the right propagation of constraints within updating processes.

In \cite{hkdphd}, a system was proposed as an automatic solution to the 
% 
% In the next section,  we present, brevely, the updating mechanism proposed in [1] as an automatic solution to the 
problem of maintenance of the GDB's consistency at the time of its update. 
In this paper, we present briefly this system architecture.
In the section 3, we locate the scheduling problem in this mechanism. Finally, in section 4, we introduce a solution that we propose to the scheduling problem during the geographical data bases updating. We also justify the advantage of this solution based on a genetic algorithm which is well adapted for the complex interaction network of the involved components. A genetic algorithm may allow to improve the updating quality in increasing the validation rate of a transaction.

%we describe the modelisation proposed for a GDB allowing further updating operation. 
%We propose for that a original language for constraints description. 
%In the section 3, we will describe the essential characteristics of the modelisation of updating information and of topological relations allowing the use of table of topological influences which will be the main element allowing the propagation processus. 
%We define what is the geographical databases updating problem and . We present, brively, the updating mechanism proposed in \cite{} as an automatic solution for the maitain of in ge....
%The section 4 presents the mecanisms of the updating. 
%The section 5 present the implementation developped, called EVOLA
%and in which 
%In this implementation, we will show how the scheduling manage the whole processus and 
%we propose a scheduling based on a genetic algorithm to improve the quality of the updating, increasing the validation rate in respect of the consitency maintenance of the GDB.   
% \section{GEOGRAPHICAL DATA BASE MODELISATION  FOR UPDATING \\IN RESPECT OF CONSISTENCY}
% 
% To allow the updating of a GDB, we need to conceive it to satisfy this objective, especially concerning the constraints representation.
%  
% \subsection{GDB conceptuals models}
% 
% % \begin{figure*}[htbp]
% % \begin{center}
% % %\rotatebox{-90} 
% % \includegraphics[scale=0.8]{MetaModele.eps}
% % \caption{UML description of GDB}
% % \label{umlmodel}
% % \end{center}
% % \end{figure*}
% 
% The proposed model for a GDB able to evolve through updating operations, is composed of a quadruplet 
% $$(\mathcal{V,~D,~R,~C})$$ 
% where (i) $\mathcal{V}$ is the set of the class used, (ii) $\mathcal{D}$ is the definition domain of the variable of $\mathcal{V}$ as GDB basic objects which are decomposed in four class: geometric primitives (point, line or area), geometric objects (composed with primitives), elementary semantic objects and complex semantic objects (aggregation of elementary semantic objects).
% 
% The interaction network over the GDB elements is based on relations between these elements. We classify these realtions in two main parts:
% \begin{enumerate}
% \item {\it Spatial relations}: they are essential for the constraints propagation description. 
% They are composed of {\it composition relations} which allow to describe aggregation of some objects and {\it dependance relations} which describe that the modification of one object can lead to the modification of other ones;
% \item{\it Topological relations}: they describe the type of topological connection between objects. 
% We proposed to use the 9-intersection from Egenhofer and Herring \cite{EH}. 
% In this model, we use a topology which consists to define for each object $p_i$, the inset noted  $p_i^\circ$, the closure set noted  $\overline{p_i}$, the outline set noted $\partial p_i$ and the exterior set noted $p_i^-$.
% This model can be represented by the matrix formulation 
% 
% \begin{center}
% \begin{math}
% \bordermatrix{ &\cr
% 	       & $P$(\partial p_k \cap \partial p_l) & $P$(\partial p_k \cap p_l^\circ) & $P$(\partial p_k \cap p_l^-) \cr
% 	       & $P$(p_k^\circ \cap \partial p_l)    & $P$(p_k^\circ \cap p_k^\circ)    & $P$(p_k^\circ \cap p_l^-)    \cr
% 	       & $P$(p_k^- \cap \partial p_l)        & $P$(p_k^- \cap p_l^\circ)        & $P$(p_k^- \cap  p_k^-)      \cr}
% \end{math}
% \end{center}
% 
% The figure \ref{9int} shows some specific situations that these matrix formulation allow to describe.       
% \end{enumerate}
% 
% \begin{figure}[htbp]
% \begin{center}
% %\rotatebox{-90} 
% \includegraphics[scale=0.5]{matrices.eps}
% \caption{Topological situations described by the 9-intersection model}
% \label{9int}
% \end{center}
% \end{figure}
% 
% 
%   
% %\subsection{GDB updating}
% 
% \subsection{Constraints representation}
% We represent the following constraints: structural, temporel, spatial and semantic ones. We define also for each constraint its importance which means that some of them have to be always satisfy and others can be raised, using exception processes. We formally define each constraint between two objects as a 5-uple composed of (i) the first object class, (ii) the second object class, (iii) the relation associated to the constaint, (iv) its importance  and (v) an exception field which allow to raise some constraints.
% 
% %The UML representation of the GDB modelisation is described in the figure \ref{umlmodel}.
% 
% %\section{OPERATIONAL MODELS FOR UPDATING}
% 
% \subsection{Updating informations and their canonical decomposition}
% 
% The updating informations proposed in the model is based on 8 {\it complex operations} which are complex creation, complex suppression, scission, fusion, aggregation, geometric modification, complexe descritive modification, stability. We have shown \cite{hkdphd} that each complex operation can be decomposed as a sequence of some of the 4 canonical operations: creation, suppression, descriptive modification and identity.
% 
% Finally the basic updating unity is the {\it transaction} wich is a set of {\it sequences} of canonical operations.
% 
% %\subsection{Modelisation of topological relations}

\section{EVOLA: \\updating system architecture}
The system called EVOLA \cite{hkdphd} has been developped in the laboratory COGIT of IGN-France (Institut G\'eographique National). EVOLA is a tool which allows automatic updating of geographical data bases. 
%Its conception is based on the model previousely proposed. 


The EVOLA general achitecture is summarized in the figure \ref{evola}. In this figure, 4 parts are mentioned and describe the work needed to use it and the processes involved. 
\begin{itemize}
\item The need of reorganizing the GDB to conform it to the model described previously and allowing the updating is mentionned by the part $(A)$. 
\item The part $(B)$ (resp. $(C)$) mentions that we need to model the updating informations (resp. the constraints representations) as previously described to adapt them to the system.
\item The part $(D)$ corresponds to the updating processus which is composed of a 3-modules kernel: {\it the reasoning-based engine, 
%has the goal to verify that the constraints are checked and so give a diagnostic for the consistency maintenance;  
the integration module,
% implements the propagation algorithm and proceed to the data updating if the consistency maintenance has been checked by the reasoning-base engine; 
the scheduler}. 
%receive updating informations which have been already computed by an adaptor. This adaptator receive a transaction and create from it a sequence of canonical operations. The scheduler receive also at each step the new operations to proceed following the propagation processus. All these operations have to be ordered to avoid the rejection of the updating corresponding to the non validation of the consitency of the GDB.    
\end{itemize}


%\begin{figure*}[htbp]
\begin{figure*}[t]
\begin{center}
%\rotatebox{-90} 
{\includegraphics[scale=0.35]{scheduling_problem2.eps}}
\caption{Scheduling Problem}
\label{scheduling problem}
\end{center}
\end{figure*}

We can see in Figure \ref{evola} how the different components do interact during the updating integration processus. First of all, the system receives an external set of updating operations from an external application. These evolutions may be expressed in the application format or in EVOLA format. If the first case, the set of evolution is passed to the {\it Adapter}. This last one converts it in the EVOLA format, corresponding to a set of specifical canonical operations (creation, supression, descriptive modification and identity). Then the {\it sheduler} computes the best order to execute in the right sequence the whole set of these canonical operations. When the {\it Integration Module} receives the set of evolutions, it has to execute the different updating operations included in this set. This execution must be free from conflicts otherwise the Integration Module has to detect them and to take decisions as regards these conflicts. To detect the conflicts, it uses the {\it Reasoning module} which, basing itself on the {\it constraints database} and the algorithms of consistence preservation, decides of the manner of modifications integration on the data of the database. at the end of each sequence of operations, a report of the various treatments of the operations is saved in the {\it Journal}. This report specifies for each operation, if it was carried out successfully or not. In the case of failure of the operation, the journal specifies the kind of conflit generated by this operation and the constraints which was violated.\\ 


\section{SCHEDULING PROBLEM}
The solution proposed in \cite{hkdphd} to realize updating of geographical data bases and to check their consistency consists in the use of incremental processing. Each step of incremental processing consists in (i) the execution of a canonical operation and (ii) the propagation of its influence on the whole geographical data base and (iii) checking consistency of the geographical data base.  ....which relies on the fact the rate of geographical data base inconsistency, at the time of its update, strongly depends on the order of execution of the updating operations.  
%that updating geographical data bases may causes the evolution of the geographic information is taken into account concurrently to the design of the system and not afterwards. Our challenge is to provide a computational model that make the maintenance of such systems easier.


Consider the representation of the geographical scene in a geographical data base, corresponding to the part "initial configuration" in the figure \ref{scheduling problem}. 
Consider that a user of this geographical data base needs to update it because of changes in the scene. 
The modification consists in the creation of the building A and the deletion of the building B.
The part "Conflict" of the figure \ref{scheduling problem} shows that the addition of the building A in the database before the deletion of the building B, generates conflict. This conflict lies in the building A passing over the building B. Depending on the kind of the conflict, the whole input updating sequence may be cancelled. In the other case, the input updating sequence processus will continue and the conflict may disappears later (figure \ref{scheduling problem}, part "Final configuration")., i.e. during the execution of an other updating operation from the sequence (the deletion of the building B ). Although the conflict may disappears in another cycle of updates, it needs a specific treatment at the time of the cycle during which it was created.  
Elsewhere, if the sequence order differs: if the user starts by deleting the building B, as shown in the part "No Conflict" of the figure  \ref{scheduling problem}, and then creating the building A, no conflict is generated (figure \ref{scheduling problem}, part "Final configuration").

The example shows that the execution of the second sequence (the deletion of B before the the creation of A) is less expensive than the execution of the first sequence (Tthe deletion of B after the the creation of A). Moreover, this order allows the validation of the updating when the second one may cancel it. 

The goal of the scheduler defined in the EVOLA architecture is to compute the best order of the operations inside the input sequence. 





% \begin{figure}[htbp]
% \begin{center}
% %\rotatebox{-90} 
% {\includegraphics[scale=0.60]{MBatiInitial2.eps}}
% \caption{3}
% \label{coherence}
% \end{center}
% \end{figure}
% \begin{figure}[htbp]
% \begin{center}
% %\rotatebox{-90} 
% {\includegraphics[scale=0.60]{MBatiSup.eps}}
% \caption{4}
% \label{coherence}
% \end{center}
% \end{figure}
% \begin{figure}[htbp]
% \begin{center}
% %\rotatebox{-90} 
% {\includegraphics[scale=0.60]{MCreCoherent.eps}}
% \caption{Updating within consistency maintenance}
% \label{coherence}
% \end{center}
% \end{figure}
% \begin{figure}[htbp]
% \begin{center}
% %\rotatebox{-90} 
% {\includegraphics[scale=0.60]{MGraBatiSup.eps}}
% \caption{5}
% \label{coherence}
% \end{center}
% \end{figure}

\section{EVOLA: \\updating system scheduled \\by genetic algorithm}
The scheduler has to minimize the apparition of conflicts. A conflict consists in the violation of a constraint. A constraint is defined on some relations between GDB objects. In the EVOLA tool, these relations are essential for the constraints propagation descriptionand can be represented with an interaction network over the GDB elements.     
We divide these relations in two main parts:

\begin{enumerate}
 \item {\it Semantic relations}:  They are composed of {\it composition relations} which allow to describe aggregation of some objects and {\it dependance relations} which describes the fact that the modification of one object can lead to the modification of other ones;
 \item{\it Topological relations}: they describe the type of topological connection between objects. 
 We propose to use the 9-intersection model from Egenhofer and Herring \cite{EH}. 
% In this model, we use a topology which consists to define for each object $p_i$, the inset noted  $p_i^\circ$, the closure set noted  $\overline{p_i}$, the outline set noted $\partial p_i$ and the exterior set noted $p_i^-$.
\end{enumerate}

The interaction network is, in that way, built with the support of a graph of relations. As the updating is based on a propagation mechanism as described in \cite{hkdphd}, the graph will structurally evolve during the computation. This dynamic evolution will generate some irregularities in the function we have to minimize and which computes the number of conflicts. This kind of problems is well-known to be strongly solved with classical optimisation methods, especially with analytical ones, and genetic algorithms are a good alternative processes to solve them. \\

The  genetic algorithm proposed here consists to define a population of individuals which are all potential solutions for the scheduler. These solutions are represented as chromosoms constituted as the sequence of all the canonical operations given to the system by the adapters. Each canonical operation is an allel and we use the 3 classical genetic operators: duplication (with selection processus), cross-over and mutation. The fitness function has to minimize the apparitions of conflicts and so to maximize the validation rate for all the operations in a sequence. A canonical operation is validated if it doesn't generate any conflict.

\section{Implementation and Experiments}
The whole system has been originaly developed in the COGIT laboratory where it has been implemented. This system is in operational practice and has been connected to the framework OXYGENE \cite{oxygene} of this laboratory. A methodology for its validation has been developped and has proved that the mechanisms are efficient, even if some rejections could be avoided with a better scheduling. The genetic algorithm engine is still under development and validation and it will improve the quality of the whole system.

An experiment has been developped on the IGN GDB concerning the Angers French town zone. Using some matching technics between two of these GDB from 1994 and 1996, we have built a set of updating informations. A {\it precision} indicator is computed as the rate between the right decisions and all the decisions taken by the EVOLA system. From a specific experiment based on 30 canonical operations, we have obtained a precision indicator equal to 0.948 which is sufficient to validate the whole processus. A detailed description about validation can be found in \cite{hkdphd}.   


%il faut parler de la solution 

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% \section{MECANISMS FOR UPDATING}
% 
% The mecanisms are based on a general incremental processus in which a propagation algorithms is implemented, associated with a consistency maintenance checking.
%  
% \subsection{Incremental processus}
% 
% The incremental processus consists in decomposing each elementary updating operation in 2 parts: the first is the implementation of a canonical operation and the computation of its propagation, the second is the checking of the consistency maintenance. If this checking is right the GDB is updated elsewhere the GDB is not modified.   
% % \begin{figure*}[htbp]
% % \begin{center}
% % \includegraphics[scale=0.5]{MyIntegration.eps}
% % \caption{Incremental updating}
% % \end{center}
% % \end{figure*}
% 
% \subsection{Table of influences} 
% 
% Using the canonical decomposition of updating informations, we can define a {\it table of topological influences} which allow to obtain, from an operation applied to an specific object, what are the effects on the other objects in its neighbouring. Corresponding to the 3 geometric primitives and the 4 canonical operations, we obtain a finite table which can describe all the situations.   
% 
% \begin{table}[htbp]
% \begin{center}
% \begin{tabular}{|p{0.55cm}|p{0.55cm}|p{1.3cm}|p{1.2cm}|p{2.3cm}|}
% \hline   $p$     & $p'$    & $Op(p)$     & $R^T(p,p')$   & Influence \\
% \hline \hline   Area   & Area & Suppress. & In        & \{ID, Suppress.\} \\
% \hline
% \end{tabular}
% \caption{An exemple of one line in the table of topological influences}
% \label{toti}
% \end{center}
% \end{table}
% 
% In the exemple corresponding to one line of the table of topological influences shown in the table \ref{toti}, the situation is the suppression of the area object $p$ which containts another area object $p'$ and that can lead to one of the following operations for this second object, that is remove it or not. To know what is the resulting operation, we need to explore the semantic influence which is itself manage by another {\it table of semantic influences}.   
% 
% \subsection{Local Propagation Mecanism}
% 
% We consider an object $O_c$ and an associated updating operation, $op$.
% The mecanism of propagation is applied in a local zone centered on the object $O_c$, called working zone from where we extract the set of other objects under the influence of the first one. Using the table of topological influences, we can deduce from the set of other objects, their associated operations for which we will have to manage an updating operation. This mechanism is recursif but we limit the exploration inside the working zone. A full algorithm description of this method is given in \cite{hkdphd}.  
% 
% \subsection{From local to global consistency maintenance}
% 
% The local propagation allows to avoid to explore the whole geographic data base. Now, we need to build a processus that will compute the adapted working zone that permit to tell that the local consistency maintenance is enough to insure the global consistency maintenance. For that purpose we propose an algorithm that we called {\it dilatation method} and that consist to progressively increase the working area like a new disk centered on the initial object $O_c$ and which radius is augmented step by step with the value $p$ until that a further increase will not compute new objects involved in the propagation processus. That leads us to define this computed area as the {\it stability area} associated to the object $O_c$.
% % 
% % \begin{definition}
% % The stability area, $\mathcal{Z}^s$, concerning the updating of the object $O_c$ with a operation $op_c$, is
% % $$\mathcal{Z}^s = {\mathcal{Z}^t}_{e^*},\ where$$ 
% % \begin{eqnarray} 
% % e^* = Min \{ e \in R^{+*} / \forall f \in R^{*+},~f \geq e,\nonumber \\ 
% % ~Result(O_c, op_c, e)~ = ~Result(O_c, op_c, f)\} \nonumber
% % \end{eqnarray}
% % \end{definition}
% 
% To prove that the local consistency maintenance can be sufficient for the global consistency maintenance, we had to define some hypothesis about the regularity of the objects repartition. The properties given in the following are proove in \cite{hkdphd}.
% 
% \begin{definition}
% A finite set of planar points is called p-dense if the Delaunay triangulation over all the set of points has no edges longer than p. 
% \end{definition}
% 
% %So we can proove the property:
% 
% \begin{property}
% If the influence area of the point $O_c$ is {\it p-dense} then the dilatation method with a step egal to $p$ computed from $O_c$ give the stability area of this point
% \end{property}
% 
% \begin{property}
% The local consistency over the stability area for an object $O_c$ will insure the consistency of the whole Data Base.
% \end{property}
% 
% This first theoritical result allows us to implement in an efficient way, the whole updating system,  with the postulat that the natural geographical data follow this hypothesis of regular distribution, using an adapted step of resolution for the dilatation method. 
% 
%\section{EVOLA implementation: \\updating system scheduled \\by genetic algorithm}

%The system called EVOLA has been developped in the laboratory COGIT of IGN-France (Institut G\'eographique National). 

%\subsection{General architecture}

%The EVOLA general achitecture is summarized in the figure \ref{evola}. In this figure, 4 parts are mentioned and describe the work needed to use it and the processes involved. $A$ mentions the need of reorganize the GDB to conform it to the model described previously and allowing the updating. $B$ (resp. $C$) mentions that we need to model the updating informations (resp. the constraints representations) as previously described to adapt them to the system. $D$ corresponds to the updating processus with is composed of a 3-modules kernel:
%\begin{itemize}
%\item {\it the reasoning-based engine} has the goal to verify that the constraints are checked and so give a diagnostic for the consistency maintenance;  
%\item {\it the integration module} implements the propagation algorithm and proceed to the data updating if the consistency maintenance has been checked by the reasoning-base engine; 
%\item {\it the scheduler} receive updating informations which have been already computed by an adaptor. This adaptator receive a transaction and create from it a sequence of canonical operations. The scheduler receive also at each step the new operations to proceed following the propagation processus. All these operations have to be ordered to avoid the rejection of the updating corresponding to the non validation of the consitency of the GDB.    
%\end{itemize}
%We can see in Figure \ref{Archi_sys} how the different components interact during the integration. First of all, the system receives an external set of evolution from an application. These evolutions are expressed in the application format. If this format is the one that we propose in our work(see Section 2), then the evolutions are directly passed on to the Integration Module. On the other hand, if the format is different (for example, the  evolutions in the IGN are expressed in XML format) then the set of evolution is passed to the Adapter. This last one, converts it in the Lambda format which can be understood by our Integration Module and recovers as well the identifiers as the operation parameters which it needs for the maintenance of the order in which the update information arriveds. It needs also to keep the dependences between the different operations. When the Integration Module received the set of evolutions, it has to execute the different updating operations included in this set. This execution must be free from conflicts otherwise the Integration Module has to detect them and to take decision with regards to these conflicts. To detect the conflicts, it uses the Reasoning module which, basing itself on the constraints database and the algorithms of consistence preservation, decides of the manner of modifications integration on the data of the database.\\ 



 

%(to be finished ... it's here that we talk of genetic algorithm in very few lines !!!!)  
%\subsection{Scheduling computation based on genetic algorithms}

% \section{GLOBAL VS. LOCAL UPDATING}
% 
% \section{SPATIAL AND TOPOLOGICAL NETWORKS FOR LOCAL MODELING IN GDB UPDATING}
% 
% \section{INCREMENTAL UPDATING USING LOCAL NETWORK}
% 
% \section{EVOLUTIVE SCHEDULING MODELING FOR GDB UPDATING QUALITY}

\section{CONCLUSION} 
This paper has described an effective processus for the updating of geographical data bases. We have presented how the consistency of the GDB can be violated if a wrong scheduling is computed. A whole architecture explaining the place of the scheduler in the incremental process, has been shown. The automatic updating proposed is based on a propagation method. This method leads to a dynamic evolution of constraints formulation between the GDB elements. We propose a genetic algorithm to implement the computation that the scheduler has to do to improve the validation rate of each updating transaction. Satisfying results have been obtained in some experiments made on IGN geographical data bases, even if the genetic computation is still in progress.   

\nocite{*}
\bibliographystyle{IEEEbib}
\bibliography{mcs05_hkd}

\end{document}
%%%%%%%%%%%%%%%
\begin{abstract}
The abstract should appear at the top of the left-hand column of text, about 0.5 inch (12 mm) below the title area and no more than 3.125 inches (80 mm) in length.  Leave a 0.5 inch (12 mm) space between the end of the abstract and the beginning of the main text.  The abstract should contain about 100 to 150 words, and should be identical to the abstract text submitted  electronically. All manuscripts must be in English, printed in black ink.
\end{abstract}
\vspace*{0.5in}
\vspace*{-\baselineskip}
%
\section{Introduction}
\label{sec:intro}
These guidelines include complete descriptions of the fonts, spacing, and related information for producing your proceedings manuscripts. Please follow them and if you have any questions, direct them to ICECS 2005 Conference Secretariat: icecs2005@icecs2005.rnrt.tn.

\section{Formatting your paper}
\label{sec:format}
Papers should be formatted for standard A4 size (210 x 297 mm) paper. All printed material, including text, illustrations, and charts, must be kept within a print area of 172 mm (6.75 inches) wide by 247 mm (9.7 inches) high. Do not write or print anything outside the print area. The top margin must be 25 mm (1 inch), except for the title page where top margin is 35 mm. The left margin must be 19mm (0.75 inch). All text must be in a two-column format.
Columns are to be 82 mm (3.25 inches) wide, with 8 mm (0.31 inch) space between them. Text must be fully justified.

\section{Page Title Section}
\label{sec:pagestyle}
The paper title (on the first page) should begin 35 mm (1- 3/8 inches) from the top edge of the page, centered, all capital letters, and in 14-point, boldface type. The authors' name(s) appear below the title in italics capital and lower case letters.  The authors' affiliation(s) appear below the names in capital and lower case letters. Papers with multiple authors and affiliations may require two or more lines for this information.

\section{TYPE-STYLE AND FONTS}
\label{sec:typestyle}
To achieve the best rendering both in the proceedings and from the CD-ROM, we strongly encourage you to use Times-Roman font.  In addition, this will give the proceedings a more uniform look.  Use a font that is no smaller than nine point type throughout the paper, including figure captions. A font size of 10 points is recommended.

Please do not double-space your paper.  True-Type 1 fonts are preferred.

The first paragraph in each section should not be indented, but all the following paragraphs within the section should be indented as these paragraphs demonstrate.

\section{MAJOR HEADINGS}
\label{sec:majhead}
Major headings, for example, ``1. Introduction'', should appear in all capital
letters, bold face, centered in the column, with one blank line before, and one blank line after. Use a period (``.'') after the heading number, not a colon.

\subsection{Subheadings}
\label{ssec:subhead}
Subheadings should appear in boldface capital and lower case letters. They should start at the left margin of the column with one blank line before, and one blank line after.

\subsubsection{Sub-subheadings}
\label{sssec:subsubhead}
Sub-subheadings, as in this paragraph, are discouraged. However, if you
must use them, they should appear in italics lower case letters (with only the first letter from the first word capitalized). They should start at the left margin of the column with one blank line before, and with paragraph text beginning directly on the following line.

\section{PRINTING YOUR PAPER}
\label{sec:print}
To test your paper before electronic submission, print your properly formatted text on high-quality A4 size white printer paper. Letter size (11 x 8.5 inches) will work too, but remember that the bottom edge of the paper will be 18 mm shorter so the formatting will seem to be off. Horizontal margins should be close to the A4 format since the difference is only 6mm. If the last page of your paper is only partially filled, arrange the columns so that they are evenly balanced if possible, rather than having one long column.

In LaTeX, to start a new column (but not a new page) and help balance the
last-page column lengths, you can use the command ``$\backslash$pagebreak'' as
demonstrated on this page (see the LaTeX source file).

\section{PAGE NUMBERING}
\label{sec:page}
Please do {\bf not} paginate your paper.  Page numbers, session numbers, and
conference identification will be inserted when the paper is included in the
proceedings.


\section{ILLUSTRATIONS, GRAPHS, AND PHOTOGRAPHS}
\label{sec:illust}
Illustrations must appear within the designated margins.  They may span the two
columns.  If possible, position illustrations at the top of columns, rather
than in the middle or at the bottom.  

All halftone illustrations must be clear in black and white. Color illustrations will appear in the CD-ROM version of the proceedings, but the printed version will be produced in black and white. Therefore, make sure that your illustrations are acceptable when printed in black and white. If you would like to produce a separate black and white version of your paper for use in the printed proceedings, please contact the conference secretariat. 

Caption and number every illustration. Figures and tables should be numbered consecutively and  separately from each other. The illustration number should be a bold Arabic number followed by a period. The caption itself should not be in bold and should be centred below the figure or above the table. 

Below is an example of how to include a figure with sub-figures.
% An example of how to insert images. Delete the ``\vspace'' line,
% uncomment the preceding line ``\centerline...'' and replace ``imageX.ps''
% with a suitable PostScript file name.
% -------------------------------------------------------------------------
\begin{figure}[htb]

\begin{minipage}[b]{1.0\linewidth}
  \centering
% \centerline{\epsfig{figure=image1.ps,width=8.5cm}}
  \vspace{1.5cm}
  \centerline{(a) Result 1}\medskip
\end{minipage}
%
\begin{minipage}[b]{.48\linewidth}
  \centering
% \centerline{\epsfig{figure=image3.ps,width=4.0cm}}
  \vspace{1.5cm}
  \centerline{(b) Results 2}\medskip
\end{minipage}
\hfill
\begin{minipage}[b]{0.48\linewidth}
  \centering
% \centerline{\epsfig{figure=image4.ps,width=4.0cm}}
  \vspace{1.5cm}
  \centerline{(c) Result 3}\medskip
\end{minipage}
%
\caption{Example of placing a figure with experimental results in sub-figures.}
\label{fig:res}
%
\end{figure}

An example of including tables is illustrated below. Note that the caption here is on top of the illustration. 
\begin{table}[htb]
\caption{Example of placing a table.}
\label{tab:res}
\begin{center}
\begin{tabular}{|c||c|c|c|}
\hline
Result &  Result & Result & Result \\ \hline \hline
1 & 2 & 3 & 4 \\ \hline
\end{tabular}
\end{center}
\end{table}

% To start a new column (but not a new page) and help balance the last-page
% column length use \vfill\pagebreak.
% -------------------------------------------------------------------------
\vfill
\pagebreak


\section{EQUATIONS}
\label{sec:equations}
Number equations consecutively with Arabic numbers in parentheses placed at the right hand margin of each column. Following is an example
\begin{equation}
a = b + c.
\end{equation}


\section{FOOTNOTES}
\label{sec:foot}
Use footnotes sparingly (or not at all!) and place them at the bottom of the column on the page on which they are referenced. Use 9-point type, single-spaced. To help your readers, avoid using footnotes altogether and include necessary peripheral observations in the text (within parentheses, if you prefer, as in this sentence).

\section{COPYRIGHT FORMS}
\label{sec:copyright}
You must fax your fully completed, signed IEEE copyright release form when you submit your final paper for publication. We {\bf must} have this form before your paper can be published in the proceedings. The copyright form is available as a Word file and a PDF file.

\section{REFERENCE FORMATTING}
\label{sec:ref}
List and number all bibliographical references at the end of the paper. The references can be numbered in alphabetical order or in order of appearance in the document.  When referring to them in the text, type the corresponding reference number in square brackets as shown at the end of this sentence \cite{smith}.


% References can be produced using the bibtex program from suitable
% BiBTeX files (here: strings, refs, manuals). The IEEEbib.bst bibliography
% style file from IEEE produces unsorted bibliography list.
% -------------------------------------------------------------------------
%\bibliographystyle{IEEEbib}
%\bibliography{strings,refs,manuals}
%----------------------------------------------
% Alternatively, you can use the \thebibliography environment directly, as
% illustrated below.

\begin{thebibliography}{1}

\bibitem{smith} A.B. Smith, C.D. Jones, and E.F. Roberts, ``Journal article title,'' {\em
Journal Name,} vol. 1, no. 3, pp. 1--10, Mar. 2000.

\bibitem{jones} C.D. Jones, A.B. Smith, and E.F. Roberts, {\em Book Title},
Publisher, Location, 2000.

\bibitem{smith2} A.B. Smith, C.D. Jones, and E.F. Roberts, ``Conference paper title,''
in {\em Proc. Conference Name}, Location, Dates, vol. I, pp. 11--14.

\end{thebibliography}

\end{document}

