\title{Spatial-Yap : un syst\`eme de base de donn\'ees spatiales d\'eductive}

\author{David Vaz et Michel Ferreira, traduit par Sidone Christophe}

\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\'ees d\'eductives est une extension de celui des bases de donn\'ees traditionnelles avec des possibilit\'es de d\'eduction. La connaissance n'est pas seulement repr\'esent\'ee par extension\footnote{D\'efinition des termes : \url{http://en.wikipedia.org/wiki/Extensional_definition}},  mais \'egalement par des r\`egles logiques intentionnelles. Une approche classique dans la construction d'un tel syst\`eme de base de donn\'ees d\'eductif est de coupler un syst\`eme de programmation logique avec un syst\`eme de base de donn\'ees relationnelle. 

%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\^ete Datalog~\cite{Ullman-89}, r\'eduit les donn\'ees attributs \`a un champ de valeurs atomiques, tel que nombres et chaines de caract\`eres, lesquels sont les donn\'ees typiques stock\'ees dans une base de donn\'ees. Cependant, les bases de donn\'ees actuelles g\`erent bien plus de structures de donn\'ees, telles que les attributs g\'eom\'etriques 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\'ecrivons l'extension du compilateur Yap Prolog~\cite{system-yap} un syst\`eme de programmation gratuit, open-source, pour qu'il g\`ere la donn\'ee spatiale, fournissant une solution dernier cri pour la mod\'eliser, la requ\^eter et l'extraire. Une proposition pour \'etendre Datalog vers Spatial Datalog a \'et\'e d\'ecrite dans la litt\'erature, dans le cadre des bases de donn\'ees 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\'erente et plus proche de la communaut\'e des bases de donn\'ees spatiales, car elle est bas\'ee sur des notions spatiales, plut\^ot que des in\'egalit\'es polynomiales. Spatial-Yap peut construire des relations spatiales logiques entre donn\'ees vectorielles et procure un environnement de programmation d\'eclaratif pour sa gestion, int\'egrant, par exemple, des sp\'ecifications de r\'ecursivit\'e, inh\'erente aux relations topologiques, et par un puissant ADT, comme outil logique. Bien que Spatial-Yap est bien plus orient\'e sur le d\'eclaratif que sur l'efficacit\'e, le syst\`eme est capable d'explorer les fonctions avanc\'ees de Yap, comme un traducteur Prolog vers SQL et un moteur bas\'e sur des essais, pour en am\'eliorer 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, tente d'impl\'ementer l'id\'ee de Colmerauer et Kowalski selon laquelle le calcul est contr\^ol\'e par inf\'erence~\cite{Kowalski-74}. La motivation du paradigme de la LP est de s\'eparer \emph{ce que} doit faire un programme du \emph{comment} il doit le faire. Cela a \'et\'e r\'esum\'e par la devise de Kowalski :

\begin{center}
algorithme = logique + contr\^ole.
\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\`eme et s'appuient sur le syst\`eme Prolog pour ex\'ecuter cette sp\'ecification. Prolog impl\'emente 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}.

ce qui veut dire: {\tt A} est {\tt Vrai} si {\tt B1} est {\tt Vrai} et {\tt B2}
est {\tt Vrai} ... et {\tt Bn} est {\tt Vrai}. Ces r\`egles donnent une interpr\'etation proc\'edurale qui se lit ainsi :

pour r\'esoudre(ex\'ecuter) {\tt A} r\'esoudre(ex\'ecuter) {\tt B1} et
r\'esoudre(ex\'ecuter) {\tt B2} ... et r\'esoudre(ex\'ecuter) {\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\'etation proc\'edurale pr\'ecise utilis\'ee dans les programmes Prolog est une forme r\'eduite de la r\'esolution 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\`emes de bases de donn\'ees d\'eductifs sont des syst\`emes de gestion de bases de donn\'ees qui sont aussi con\c{c}us autour d'un mod\`ele logique de donn\'ees et dont le langage de requ\^etes est une version \"set-oriented?\" de Prolog, connu sous le nom de Datalog. Les relations sont naturellement pens\'ees comme la \emph{valeur} du pr\'edicat logique et la puissance expressive des expressions logiques est utilis\'ee pour requ\^eter de telles relations. La part d\'eductive de tels syst\`emes vient du fait que les moteurs de Programmation Logique utilisent des \emph{intentions} (ou compr\'ehensions), pour exprimer des propri\'et\'es, et sont capables de mat\'erialiser 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{Exemple de Spatial-Yap.}
  \label{figure:Spatial-yap example.}
\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\'eduction, qui va d'intentions en extensions, est d'un point de vue calculatoire plus simple que le processus inverse qui consiste \`a aller d'extensions en intentions. Cependant, \^etre capable de d\'eriver une repr\'esentation intentionnel depuis des donn\'ees extensionnelles, en inf\'erant une r\`egle g\'en\'erale \`a 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 \`a l'intersection de l'Apprentissage Automatique et de la Programmation Logique. Les syst\`emes de PLI d\'eveloppent des pr\'edicats \`a partir d'exemples et d'une base de connaissances, dont on d\'eduit un programme logique qui confirme les exemples positifs et infirme les exemples n\'egatifs. Pour d\'eduire une th\'eorie avec les propri\'et\'es attendues, beaucoup de syst\`emes de PLI suivent une sorte d'approche \emph{generation-et-test} pour balayer \emph{l'ensemble des hypoth\`eses}. Une caract\'eristique importante de l'approche de la PLI pour la fouille de donn\'ees est d'\^etre multi-relationnelle, capable de formuler des th\'eories qui impliquent des donn\'ees ayant plusieurs relations, alors que beaucoup de techniques importantes de fouilles de donn\'ees sont seulement capables de d\'egager des structures pour une unique relation. Ceci est particuli\`erement int\'eressant pour la fouille de donn\'ees spatiales, qui est multi-relationnel (ou multi-couches) par d\'efinition.


\section{Un syst\`eme de base de donn\'ees spatiales d\'eductive}

%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\'esulte d'une interface complexe entre plusieurs composants. Les deux composants principaux sont le syst\`eme Yap Prolog et le SGBD MySQL, qui sont coupl\'es par une interface MYDDAS~\cite{Soares-05b} (pour Mysql/Yap Deductive DAtabase System). Cette interface est responsable du couplage des deux syst\`emes comme le montre la Figure ~\ref{figure:blueprint}. MYDDAS traduit les requ\^etes logiques en requ\^etes SQL de fa\c{c}on transparente, impl\'emente la conversion des attributs MySQL en notions Yap et explore le moteur YapTab pour r\'esoudre des requ\^etes r\'ecursives impliquant la base de donn\'ees. Le niveau de sophistication de cette interface est tr\`es \'elev\'e : la recherche de tuples relationnels est directement impl\'ement\'ee dans le choix des points WAM, supportant les op\'erateurs simplifi\'es~\cite{soares-padl06}. 

\begin{figure*}[htbp]
  \centering
  \includegraphics[width=0.7\textwidth]{proceedings/vaz/myddas_blue_print.jpg}
  \caption{Mod\`ele Spatial Yap.}
  \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\'ees spatiales d\'eductive, nous avons \'etendu l'interface MYDDAS afin qu'elle int\`egre des types g\'eom\'etriques MySQL. Deux composants suppl\'ementaires sont fondamentaux pour construire Spatial Yap : une librairie d'op\'erateurs spatiaux bas\'ee sur la librairie classique 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\'ees spatiales il est essentiel d'\^etre capable de repr\'esenter ces donn\'ees graphiquement. Repr\'esenter une carte comme un ensemble de notions Prolog est visuellement inacceptable du point de vue d'un utilisateur de SIG. Plus importante encore est la repr\'esentation d'une op\'eration spatiale, comme l'intersection de deux polygones d'un point de vue graphique. Les analyses spatiales r\'ealis\'ees par l'utilisateur et la repr\'esentation des ensembles de r\'esultats des requ\^etes spatiales n\'ecessitent l'ajout d'un composant de visualisation \`a tout syst\`eme de base de donn\'ees spatiale. Nous aurions pu utiliser un des FOSS existants, comme MapServer, mais nous avions besoin de quelque chose de plus simple qui fonctionne \`a un haut-niveau graphique, \'etroitement li\'e avec le haut-niveau textuel de notre syst\`eme Prolog. L'interaction entre ces deux fonctionnements haut-niveau \'etait notre objectif principal, plut\^ot qu'un affichage graphique sophistiqu\'e. La Figure~\ref{figure:spatial-yap example} montre une copie d'\'ecran 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\'ecrivons 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'\'etudier le comportement du trafic dans la ville de Porto, deuxi\`eme plus important du Portugal, avec un r\'eseau routier de 965 km, pr\'esent\'e Fig. ~\ref{figure:coverage}. Nous nous int\'eressons \`a la compr\'ehension de facteurs affectant le trafic, pas uniquement concernant le temps et le jour, mais aussi incluant des entit\'es g\'eographiques intrins\`eques,  comme la pr\'esence d'\'ecoles sur un tron\c{c}on de route et leur influence sur la congestion du trafic suivant certaines plages horaires. Un des objectifs plus ambitieux est la d\'erivation de la couche de signalisation routi\`ere, incluant les lumi\`eres et la localisation des stops et bas\'ee sur des mod\`eles de mobilit\'e mais aussi l'inf\'erence des possibles destinations des conducteurs pouvant automatiquement activer les syst\`emes de navigation bas\'es 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\'eraires calcul\'es sont aussi impl\'ement\'es en utilisant Spatial-Yap et son moteur. Les syt\`emes de PLI fournissent le support d'inf\'erence sur les donn\'ees g\'eospatiales, comme les logs GPS.

\subsection{Correction de la Classification Automatique des For\^ets bas\'ee 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\'eressant o\`u nous utilisons Spatial-Yap vise \`a la surveillance globale des changements de biodiversit\'e~\cite{Pereira06}. Les gouvernements ont comme objectif ambitieux de r\'eduire la baisse de la biodiversit\'e d'ici 2010, et les scientifiques sont confront\'es maintenant au d\'efi de l'acc\`es aux progr\`es r\'ealis\'es dans ce sens. Le projet europ\'een Corine Land Cover \footnote{Le Projet Europ\'een Corine Land Cover (CLC) : \url{http://terrestrial.eionet.eu.int/CLC2000}} (CLC) fournit des donn\'ees pour deux  ann\'ees diff\'erentes (1990 et 2000), utilisant 44 classes d'occupation du sol. Ces donn\'ees sont acquises \`a partir d'images satellites , gr\^ace \`a la vectorisation de chacune des 44 classes d'occupation du sol en polygones, r\'ealis\'ee automatiquement, par reconnaissance de couleurs.  Malheureusement les classes CLC ne sont pas les plus appropri\'ees pour surveiller la biodiversit\'e. Par exemple, la base CLC courante n'a que 3 classes pour la for\^et (feuillus, conif\`eres et mixtes). Par cons\'equent, une augmentation observ\'ee dans la zone foresti\`ere de feuillus pourrait \^etre due \`a une augmentation de la superficie d'une plantation d'esp\`eces exotiques, telles que l'Eucalyptus globulus, ou \`a une augmentation du nombre d'arbres dans les for\^ets natives de feuillus, les deux ph\'enom\`enes ayant des implications diff\'erentes en terme de biodiversit\'e. Le groupe de biologistes avec qui nous travaillons poss\`ede des cartes r\'egionales de la r\'egion de l'Alto Minho au Portugal (see Fig.~\ref{figure:cos2000}), aussi couverte par CLC. Ces cartes r\'egionales sont r\'ealis\'ees sur place avec des techniques de cartographie lentes et co\^uteuses et l'identification sur place des esp\`eces en for\^et permet un meilleur niveau de d\'etail dans la liste des classes. Notre projet essaie d'utiliser ces cartes r\'egionales afin de d\'eriver un ensemble de r\`egles spatiales logiques qui permettent la caract\'erisation d\'etaill\'ee des donn\'ees CLC pour la surveillance de la biodiversit\'e.

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

\section{Perspectives}

%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 \`a PostGreSQL est en cours. Notre but est d'\'etendre Prolog comme compilateur SQL, afin d'\^etre capable de transf\'erer dans le syst\`eme de base de donn\'ees la convergence des buts logiques, ce qui peut \^etre pr\'ef\'erable \`a 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 \^etre t\'el\'echarg\'e depuis \url{myddas.dcc.fc.up.pt}. Un manuel utilisateur et plusieurs articles avec des pr\'esentations plus approfondies de Spatial-Yap sont aussi disponibles sur cette m\^eme 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 \'et\'e partiellement soutenu par MYDDAS (POSC/EIA/59154/2004) et par des fonds accord\'es \`a LIACC \`a 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\'e par une bourse de doctorat de type 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}}
