\title{Spatial-Yap : un système de base de données spatialement déductif}

\author{David Vaz et Michel Ferreira}

\maketitle

\section{Introduction}
%The paradigm of Deductive Databases extends traditional databases with
%deduction abilities. Knowledge is not only represented extensionally\footnote{Definition of terms: %\url{http://en.wikipedia.org/wiki/Extensional_definition}}
%but also through intensional logic rules. A typical approach in
%building such deductive database systems is to couple a logic
%programming system with a relational database system.

Le paradigme des bases de données déductives est une extension de celui des bases de données traditionnelles avec des possibilités de déduction. La connaissance n'est pas seulement représentée par extension\footnote{Définition des termes: \url{http://en.wikipedia.org/wiki/Extensional_definition},  mais également par des règles logiques intentionnelles. Une approche classique dans la construction d'un tel système de base de données déductif est de coupler un système de programmation logique avec un système de base de données relationnel. 

%The original query language, Datalog~\cite{Ullman-89}, restricted
%attribute data to ground atomic values, such as numbers and strings,
%which were the typical data stored in databases. However, current
%databases store much more structured data, such as the geometric
%attributes of spatial relations.

Le langage de requête Datalog~\cite{Ullman-89}, réduit les données attributs à un champ de valeurs atomiques, tel que nombres et chaines de caractères, lesquels sont les données typiques stockées dans une base de données. Cependant, les bases de données actuelles gèrent bien plus de structures de données, telles que les attributs géométriques des relations spatiales. 

%In this paper we describe the extension of the Yap Prolog~\cite{system-yap} compiler, a free, open-source logic programming system, 
%in order to handle spatial data, providing a state-of-the-art solution for its modeling, querying and mining. A proposal of extending Datalog 
%to Spatial Datalog has been described in the literature, in the framework of Constraint Databases~\cite{Kanellakis95}. 

Dans cet article, nous décrivons l'extension du compilateur Yap Prolog~\cite{system-yap} un système de programmation gratuit, open-source, pour qu'il gère la donnée spatiale, fournissant une solution dernier cri pour la modéliser, la requêter et l'extraire. Une proposition pour étendre Datalog vers Spatial Datalog a été décrite dans la littérature, dans le cadre des bases de données contraintes~\cite{Kanellakis95}.

%The approach followed in Spatial-Yap is different and closer to the spatial databases community, 
%as it is based on spatial terms, rather than on polynomial inequalities. Spatial-Yap can build spatial logic terms from vectorial data 
%in spatial relations, and provides a highly declarative programming environment for its handling, supported, for instance, by the natural 
%specification of recursion, inherent to topological relationships, and by a powerful ADT, as is the logic term. Although the current focus 
%in Spatial-Yap is much more on declarativity than on efficiency, the system is able to explore advanced features of Yap, such as a Prolog to
%SQL translator and a tabling engine based on tries, to improve performance.

L'approche suivie dans Spatial Yap est différente et plus proche de la communauté des bases de données spatiales, car elle est basée sur des notions spatiales, plutôt que des inégalités polynominales. Spatial-Yap peut construire des relations spatiales logiques entre données vectorielles et procure un environnement de programmation déclaratif pour sa gestion, intégrant, par exemple, des spécifications de récursivité, inhérente aux relations topologiques, et par un puissant ADT, comme outil logique. Bien que Spatial-Yap est bien plus orienté sur le déclaratif que sur l'efficacité, le système est capable d'explorer les fonctions avancées de Yap, comme un traducteur Prolog vers SQL et un moteur basé sur des essais, pour améliorer les performances.

\section{Programmation Logique et Programmation Logique Inductive}
%Logic programming (LP), of which Prolog is the canonical language, is
%an attempt to implement Colmerauer and Kowalski's idea that
%computation is controlled inference~\cite{Kowalski-74}. The motivation
%for the LP paradigm is to separate the specification of \emph{what}
%the program should do from \emph{how} it should be done. This was
%summarized by Kowalski's motto:

La Programmation Logique (LP), dont Prolog est le langage canonique, est la mise en pratique de l'idée de Colmerauer et Kowalski selon laquelle un algorithme est contrôlé par inférence~\cite{Kowalski-74}. La motivation du paradigme de la LP est de séparer \emph{ce que} doit faire un programme du \emph{comment} il doit le faire. Cela a été résumé par la devise de Kowalski :

\begin{center}
$algorithme = logique + contrôle$.
\end{center}

%Prolog programs use the logic to express the problem and rely on the
%Prolog system to execute this specification. Prolog implements a
%subset of first order logic known as Horn clause logic. A Prolog
%program is a set of relational rules of the form:

Les programmes Prolog utilisent la logique pour exprimer un problème et s'appuient sur le système Prolog pour exécuter cette spécification. Prolog implémente un sous-ensemble logique de premier ordre comme les clauses de Horn.

{\tt A :- B1, B2, ..., Bn.}

%meaning: {\tt A} is {\tt True} if {\tt B1} is {\tt True} and {\tt B2}
%is {\tt True} ... and {\tt Bn} is {\tt True}. These rules are given a
%procedural interpretation which reads as:

%to solve(execute) {\tt A} solve(execute) {\tt B1} and
%solve(execute) {\tt B2} ... and solve(execute) {\tt Bn}.

meaning: {\tt A} is {\tt True} if {\tt B1} is {\tt True} and {\tt B2}
is {\tt True} ... and {\tt Bn} is {\tt True}. Ces règles donnent une interprétation procédurale qui se lit ainsi :

to solve(execute) {\tt A} solve(execute) {\tt B1} and
solve(execute) {\tt B2} ... and solve(execute) {\tt Bn}.

%The precise procedural interpretation used in the execution of Prolog
%programs is a restricted form of SLD-resolution~\cite{Lloyd-87}.

L'interprétation procédurale précise utilisée dans les programmes Prolog est une forme réduite de la résolution SLD~\cite{Lloyd-87}.

%Deductive database systems are database management systems which are
%also designed around a logic model of data and whose query language is
%a set-oriented version of Prolog, known as Datalog. Database relations
%are naturally thought of as the \emph{value} of a logical predicate
%and the high expressive power of logic expressions is used to query
%such relations. The deductive part of such systems comes from the fact
%that the logic programming engines take \emph{intentions} (or
%comprehensions), which express properties, and are able to materialize
%these intentions in \emph{extensional} knowledge (relational tuples or
%facts). 

Les systèmes de bases de données déductifs sont des systèmes de gestion de bases de données qui sont aussi conçus autour d'un modèle logique de données et dont le langage de requêtes est une version \"set-oriented?\" de Prolog, connu sous le nom de Datalog. Les relations sont naturellement pensées comme la \emph{valeur} du prédicat logique et la puissance expressive des expressions logiques est utilisée pour requêter de telles relations. La part déductive de tels systèmes vient du fait que les moteurs de Programmation Logique utilisent des \emph{intentions} (ou compréhensions), pour exprimer des propriétés, et sont capables de matérialiser ces intentions dans des connaissances \emph{extensionelles} (tuples relationnels ou faits).

\begin{figure*}[htbp]
  \centering
  \includegraphics[width=0.5\textwidth]{proceedings/vaz/sg-interface.jpg}
  \caption{Spatial-Yap example.}
  \label{figure:Exemple spatial-yap}
\end{figure*}

%This process of deduction, which goes from intentions to extensions,
%is computationally much simpler than the reverse process of going from
%extensions to intentions. However, being able to derive an intentional
%representation from extensional data, inferring a general rule from
%examples, is also crucial. This is the goal of a logic programming
%paradigm known as Inductive Logic Programming (ILP)~\cite{Muggleton-90}.


Ce processus de déduction, qui va d'intentions en extensions, est d'un point de vue calculatoire plus simple que le processus inverse qui consiste à aller d'extensions en intentions. Cependant, être capable de dériver une représentation intentionnel depuis des données extensionnelles, en inférant une règle générale à partir d'exemples, est aussi crucial. C'est le but du paradigme de la Programmation Logique en tant que Programmation Logique Inductive (PLI)~\cite{Muggleton-90}.

%ILP is a research area formed at the intersection of Machine Learning
%and LP. ILP systems develop predicate descriptions from examples and
%background knowledge, thus deriving an hypothesized logic program
%which entails all the positive and none of the negative examples. To
%derive a theory with the desire properties, many ILP systems follow
%some kind of \emph{generate-and-test} approach to traverse the
%\emph{hypotheses space}. An important characteristic of the ILP
%approach to data mining is that it is multi-relational, being able to
%formulate theories which involve data in several relations, while many
%important data mining techniques are only able to look for patterns in
%a single relation. This is particularly useful for spatial data
%mining, which is inherently multi-relational (or multi-layered). 

La Programmation Logique Inductive (PLI) est un domaine de recherche à l'intersection de l'Apprentissage Automatique et de la Programmation Logique. Les systèmes de PLI développent des prédicats à partir d'exemples et d'une base de connaissances, dont on déduit un programme logique qui confirme les exemples positifs et infirme les exemples négatifs. Pour déduire une théorie avec les propriétés attendues, beaucoup de systèmes de PLI suivent une sorte d'approche \emph{generation-et-test} pour balayer \emph{l'ensemble des hypothèses}. Une caractéristique importante de l'approche de la PLI est d'être multi-relationnelle, capable de formuler des théories qui impliquent des données ayant plusieurs relations, alors que beaucoup de techniques importantes de datamining sont seulement capables de trouver des patrons dans une simple relation. ceci est particulièrement intéressant pour le data mining spatial, qui est multirelationnel (ou multicouches) par définition.


\section{Un système de base de données spatialement déductif}

%Spatial Yap results from a sophisticated interface between several
%components. The two main components are the Yap Prolog system and
%MySQL RDBMS, which are coupled through the MYDDAS
%interface~\cite{Soares-05b} (Mysql/Yap Deductive DAtabase System).
%This interface is responsible for coupling these two systems, as
%illustrated in Figure~\ref{figure:blueprint}. MYDDAS transparently
%translates logic queries into SQL statements, implements the
%conversion into Yap terms of MySQL attributes and explores the YapTab
%tabling engine for solving recursive queries involving database goals.
%The level of sophistication of this interface is very high, with the
%fetching of relational tuples being implemented directly in WAM
%choice-points, supporting pruning operators~\cite{soares-padl06}.

Spatial Yap résulte d'une interface complexe entre plusieurs composants. Les deux composants principaux sont le système Yap Prolog et le SGBD MySQL, qui sont couplés au travers d'une interface MYDDAS~\cite{Soares-05b} (pour Mysql/Yap Deductive DAtabase System). Cette interface est responsable du couplage des deux systèmes comme le montre la Figure ~\ref{figure:blueprint}. MYDDAS traduit les requêtes logiques en requêtes SQL de façon transparente, implémente la conversion des attributs MySQL en notions Yap et explore le moteur YapTab pour résoudre des requêtes récursives impliquant la base de données. Le niveau de sophistication de cette interface est très élevé, avec la recherche de tuples relationnels being implemented directly in WAM choice-points, supporting pruning operators~\cite{soares-padl06}. 

\begin{figure*}[htbp]
  \centering
  \includegraphics[width=0.7\textwidth]{proceedings/vaz/myddas_blue_print.jpg}
  \caption{Spatial Yap Blueprint.}
  \label{figure:blueprint}
\end{figure*}

%To build the spatial deductive database system we extended the MYDDAS
%interface to support MySQL Geometry Types. Two more components are
%fundamental to build Spatial Yap: a spatial operators library based on
%the well known GEOS library and a visualization component.

Afin de construire la base de données spatiale déductive, nous avons étendu l'interface MYDDAS afin qu'elle intègre des types géométriques MySQL. Deux composants supplémentaires sont fondamentaux pour construire Spatial Yap : une librairie d'opérateurs spatiaux basée sur la librairie (bien connue) GEOS et un composant de visualisation. 

%When dealing with spatial data it is essential to be able to
%graphically represent such data. Representing a map as a set of Prolog
%terms is visually unacceptable, from the point of view of a GIS
%user. Even more important is the representation of a spatial
%operation, such as the intersection of two polygons, in a graphical
%way. User-driven spatial analysis and the representation of spatial
%queries result sets require a visualization component to be added to
%any spatial database system. Here we could have used one of the
%existing FOSS, such as MapServer, but we rather needed something
%simpler that worked as a graphical spatial top-level, tightly coupled
%to the text top-level of our Prolog system. Interaction between these
%top-levels was our main goal, rather than sophisticated graphical
%display. Figure~\ref{figure:spatial-yap example} show a screenshot of
%the interaction between the two top-levels of Spatial-Yap.

Quand on manipule des données spatiales il est essentiel d'être capable de représenter ces données graphiquement. Représenter une carte comm un ensemble de notions Prolog est visuellement inacceptable du point de vue d'un utilisateur de SIG. Plus importante encore est la représentation d'une opération spatiale, comme l'intersection de deux polygones d'un point de vue graphique. Les analyses spatiales réalisées par l'utilisateur et la représentation des ensembles de résultats des requêtes spatiales nécessitent l'ajout d'un composant de visualisation à tout système de base de données spatiale. Nous aurions pu utiliser un des FOSS existants, comme MapServer, mais nous avions besoin de quelque chose de plus simple qui fonctionne à un haut-niveau graphique, étroitement lié avec le fonctionnement haut-niveau textuel de notre système Prolog. L'interaction entre ces deux fonctionnements haut-niveau était notre objectif principal, plutôt qu'un affichage graphique sophistiqué. La Figure~\ref{figure:spatial-yap example} montre une copie d'écran de l'interaction entre les deux parties haut-niveaux de Spatial-Yap. 

\section{Applications en cours}

%In this section we describe two undergoing projects where we are applying Spatial-Yap.

Dans cette section nous décrivons deux projets utilisant Spatial-Yap en cours.

\subsection{Etude du comportement du trafic dans la ville de Porto}

%The aim of this project is to study traffic behavior in the city of
%Porto, second largest in Portugal, with a road network totaling 965
%kms, shown in Fig.~\ref{figure:coverage}. We are interested in
%understanding factors affecting traffic, not only time and day
%related, but also including intrinsic geographic entities, such as the
%presence of a school in a street segment and its influence in traffic
%congestion time-slots. More ambitious goals include the automatic
%derivation of a road signalization layer, including traffic lights and
%stop signs locations, based on mobility patterns, or the inference of
%likely destinations of drivers that can automatically activate
%navigation systems, based on a background of usual routes.


Le but de ce projet est d'étudier le comportement du trafic dans la ville de Porto, deuxième plus important du Portugal, avec un réseau routier de 965 kms, présenté à la Fig. ~\ref{figure:coverage}. Nous nous intéressons à la compréhension de facteurs affectant le trafic, pas uniquement concernant le temps et le jour, mais aussi incluant des entités géographiques intrinsèques,  comme la présence d'écoles sur un tronçon de route et leur influence sur la congestion du trafic suivant certaines plages horaires. Des objectifs plus ambitieux incluent la dérivation de la couche de signalisation routière, incluant les lumières et la localisation des stops, basé sur des patrons de mobilité ou l'inférence des destinations appréciées des conducteurs qui peuvent automatiquement activer les systèmes de navigation basés sur un fond des routes usuels.

\begin{figure}[htbp]
  \centering
  \includegraphics[width=0.8\columnwidth]{proceedings/vaz/coverage.jpg}
  \caption{Road network of Porto.}
  \label{figure:coverage}
\end{figure}

%Routing algorithms and displaying of computed routes are also
%implemented using Spatial-Yap and its tabling engine. ILP systems
%provide the support for inference over geospatial data, such as GPS logs.

Des algorithmes de routage et l'affichage des itinéraires calculés sont aussi implémentés en utilisant Spatial-Yap et son moteur. Les sytèmes de PLI fournissent le support d'inférence sur les données géospatiales, comme les logs GPS.

\subsection{Correction de la Classification Automatique des Forêts basée sur l'Analyse Spatiale}

%Another interesting project where we are using Spatial-Yap aims at the
%global monitoring of biodiversity change~\cite{Pereira06}. Governments
%have set the ambitious target of reducing biodiversity loss by the
%year 2010, and scientists now face the challenge of accessing the
%progress made towards this target. The European Corine Land Cover
%(CLC) project\footnote{The European Corine Land Cover
%(CLC) project: \url{http://terrestrial.eionet.eu.int/CLC2000}}
%provides data for two different years (1990 and 2000), using 44
%land-cover classes. This data is obtained from satellite images and
%the vectorization in the polygons of each of the 44 land-cover classes
%is done automatically, based on color recognition.  Unfortunately, the
%land-cover classes of CLC are not the most appropriate to monitor
%biodiversity. For instance, currently CLC has only three classes for
%forest (broad-leaved, coniferous and mixed); therefore, an observed
%increase in broadleaved forest area could be due to an increase in
%plantation area of an exotic species, such as Eucalyptus globulus, or
%an increase in native broad-leaved forest, two phenomena with
%different implications for biodiversity. The group of biologists with
%whom we are working has detailed regional maps from the area of Alto
%Minho, in Portugal (see Fig.~\ref{figure:cos2000}), also covered by
%CLC. These regional maps are done based on expensive and slow on-site
%mapping techniques and on-site identification of forest species,
%allowing a much higher detail on the list of classes. Our project is
%trying to use these detailed regional maps to derive a set of spatial
%logic rules that allow the detailed characterization of CLC data for
%biodiversity monitoring. We are using Spatial-Yap and the APRIL ILP
%system over data-sets created based on the intersection of the
%regional maps and CLC maps. The inducted rules can then be used to
%improve the categorization of new CLC data, allowing its use for
%biodiversity monitoring.


Un autre projet intéressant où nous utilisons Spatial-Yap vise à la surveillance globale des changements de biodiversité~\cite{Pereira06}. Les gouvernements ont unobjectif ambitieux de réduire la baisse de biodiversité d'ici 2010, et les scientifiques sont confrontés maintenant au défi de l'accès à l'avancement réalisé dans ce sens. Le projet européen Corine Land Cover fournit des données pour deux  années différentes (1990 et 2000), utilisant 44 classes d'occupation du sol. Ces données sont acquises à partir d'images satellites , grâce à la vectorisation de chacun des 44 classes d'occupation du sol en polygones, réalisée automatiquement, par reconnaissance de couleurs.  Malheureusement les classes CLC ne sont pas les plus appropriées pour surveiller la biodiversité. Par exemple, la base CLC courante n'a que 3 classes pour la forêt (feuillus, conifères et mixtes). Par conséquent, une augmentation observée dans la zone forestière de feuillus pourrait être due à une augmentation de la superficie d'une plantation d'espèces exotiques, telles que l'Eucalyptus globulus, ou à une augmentation d'arbres dans les forêts natives de feuillus, les deux phénomènes ayant des implications différentes en terme de biodiversité. Le groupe de biologistes avec qui nous travaillons possède des cartes régionales de la région de l'Alto Minho au Portugal (see Fig.~\ref{figure:cos2000}), aussi couverte par CLC. Ces cartes régionales sont réalisées sur place avec des techniques de cartographie lentes et coûteuses et l'identification sur place des espèces en forêt permet un meilleur niveau de détail dans la liste des classes. Notre projet essaie d'utiliser ces cartes régionales afin de dériver un ensemble de règles spatiales logiques qui permettent la caractérisation détaillée des données CLC pour la surveillance de la biodiversité.

(CLC)\footnote{Le projet européen Corine Land Cover (CLC) : \url{http://terrestrial.eionet.eu.int/CLC2000}} 

\begin{figure}[htbp]
  \centering
  \includegraphics[width=0.8\columnwidth]{proceedings/vaz/altominho.jpg}
  \caption{Alto Minho Map.}
  \label{figure:cos2000}
\end{figure}

\section{Travaux futurs}

%A migration from MySQL to PostgreSQL is undergoing. Our goal is to
%extend the Prolog to SQL compiler in order to be able to transfer to
%the database system conjunctions of logic goals, that can take
%advantage of spatial indexing that currently is not available in
%Spatial-Yap.

La migration de MySQL à PostGreSQL est en cours. Notre but est d'étendre Prolog comme compilateur SQL, afin d'être capable de transférer dans le système de base de données la convergence des buts logiques, ce qui peut être préférable à l'indexation spatiale qui n'est pas actuellement disponible dans Spatial-Yap. 

%Spatial-Yap can be downloaded from \url{myddas.dcc.fc.up.pt}. A
%users manual and several papers with deeper presentations of
%Spatial-Yap are also available from the same webpage.

Spatial-Yap peut être téléchargé depuis \url{myddas.dcc.fc.up.pt}. Un manuel utilisateur et plusieurs articles avec des présentations plus approfondies de Spatial-Yap sont aussi disponibles sur cette même page.

\section{Remerciements}
%This work has been partially supported by MYDDAS
%(POSC/EIA/59154/2004) and by funds granted to LIACC through the
%Programa de Financiamento Plurianual, Funda\c{c}\~{a}o para a Ci\^{e}ncia e
%Tecnologia and Programa POSC. David Vaz is funded by FCT PhD grant
%SFRH/BD/29648/2006.

Ce travail a été partiellement soutenu par MYDDAS (POSC/EIA/59154/2004) et par des fonds accordés à LIACC à travers le Programa de Financiamento Plurianual, Funda\c{c}\~{a}o para a Ci\^{e}ncia e Tecnologia and Programa POSC. David Vaz est subventionné par FCT PhD grant SFRH/BD/29648/2006.

\begin{footnotesize}
\begin{thebibliography}{99}

\bibitem{Ullman-89}
J.~D. Ullman.
\newblock {\em {Principles of Database and Knowledge-Base Systems}}.
\newblock Computer Science Press, 1989.

\bibitem{system-yap}
V.~{Santos Costa}, L.~Damas, R.~Reis, and R.~Azevedo.
\newblock {\em {YAP User's Manual}}.
\newblock Available from \url{http://www.ncc.up.pt/~vsc/Yap+}.

\bibitem{Kanellakis95}
P.~C. Kanellakis, G.~M. Kuper, and P.~Z. Revesz.
\newblock Constraint query languages.
\newblock {\em J. Comput. Syst. Sci.}, 51(1):26--52, 1995.

\bibitem{Kowalski-74}
R.~Kowalski.
\newblock {Predicate Logic as a Programming Language}.
\newblock In {\em Information Processing}, pages 569--574. North-Holland, 1974.

\bibitem{Lloyd-87}
J.~W. Lloyd.
\newblock {\em {Foundations of Logic Programming}}.
\newblock Springer-Verlag, 1987.

\bibitem{Muggleton-90}
S.~Muggleton.
\newblock {Inductive Logic Programming}.
\newblock In {\em Conference on Algorithmic Learning Theory}, pages 43--62.
  Ohmsma, 1990.

\bibitem{Soares-05b}
T.~Soares, M.~Ferreira, and R.~Rocha.
\newblock {The MYDDAS Programmer's Manual}.
\newblock Technical Report DCC-2005-10, Department of Computer Science,
  University of Porto, 2005.

\bibitem{soares-padl06}
T.~Soares, R.~Rocha, and M.~Ferreira.
\newblock {Generic Cut Actions for External Prolog Predicates}.
\newblock In P.~V. Hentenryck, editor, {\em Proceedings of the 8th
  International Symposium on Practical Aspects of Declarative Languages,
  PADL'2006}, number 3819 in LNCS, pages 16--30, Charleston, South Carolina,
  USA, January 2006. Springer-Verlag.

\bibitem{Pereira06}
H.~M. Pereira and H.~D. Cooper.
\newblock Towards the global monitoring of biodiversity change.
\newblock {\em Trends in Ecology \& Evolution}, 21(3):123--129, March 2006.

\end{thebibliography}
\end{footnotesize}

\address{David Vaz\\ DCC-FC \& LIACC, University of Porto\\
%  \url{your homepage}\\
  \email{davidvaz AT dcc.fc.up.pt}}

\address{Michel Ferreira\\
  DCC-FC \& LIACC, University of Porto\\
%  \url{your homepage}\\
  \email{michel AT dcc.fc.up.pt}}
