% Template GRASS newsletter - Article
% Language: Latex
%

% Head

\title{Spatial-Yap:\\
  A Spatio-Deductive Database System}
%\subtitle{Your article subtitle}
\author{by David Vaz and Michel Ferreira}

\maketitle

\section{Introduction}

The paradigm of Deductive Databases extends traditional databases with
deduction abilities. Knowledge in not only represented extensionally
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.

The original query language, Datalog, 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. 

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{x}.
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.

Multi-relational data-mining is closely related to Logic Programming,
through the framework of Inductive Logic Programming. The
extensions developed in the context of Spatial-Yap allow the framework
of Inductive Logic Programming to be tightly coupled with spatial
databases, resulting in a major contribution for the field of spatial
data-mining.

\section{Logic Programming and Inductive Logic Programming}
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:

\begin{center}
$algorithm = logic + control$.
\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:

{\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}.

The precise procedural interpretation used in the execution of Prolog
programs is a restricted form of SLD-resolution~\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). 

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).

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). 

\section{A Spatio-Deductive Database System}

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}.

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.

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, but we rather needed something simpler, as the main
objective was not the graphical display. Another motivation to build a
graphical library was the absence of a graphical library, meeting our
terms, for prolog systems. There are some Prolog systems providing
native Graphical User Interfaces (GUI), such as SWI-Prolog with the
XPCE~\cite{system-swi-xpce}, and systems providing coupling interfaces
to external GUIs libraries such as TCL/TK. Our needs were slightly
different as we do not need to have a complete GUI, but simply a basic
drawing system conforming to the OGC99 spatial types.  This led to the
development of a graphical interface, Simple Graphics (SG), in the
context of Spatial-Yap, this simple interface is summarized in
Figure~\ref{table:SG API}. An example of this interface in use is in
Figure~\ref{figure:spatial-yap example}.

\begin{figure}[htbp]
  \begin{footnotesize}
  \centering
  \begin{tabular}{|c|l|}
    \hline
    {\bf Type} & {\bf Predicate} \\
    \hline \hline

    \multirow{4}{0.20\columnwidth}
    {SG module handling}
    & {\tt sg\_initialize(+Options)} \\
    & {\tt sg\_shutdown} \\
    & {\tt sg\_recenter}\\
    & {\tt sg\_export(+Type,+File)}\\
    \hline

    \multirow{5}{0.20\columnwidth}
    {Drawing Spatial Terms}
    & {\tt sg\_create(+SpatialTerm)} \\
    \cline{2-2}
    & {\tt sg\_color(+Red,+Green,+Blue)} \\
    & {\tt sg\_color(+Color)} \\
    & {\tt sg\_outline\_color(+Red,+Green,+Blue)} \\
    & {\tt sg\_outline\_color(+Color)}\\
    \hline

    \multirow{3}{0.20\columnwidth}
    {Yap and SG interaction}
    & {\tt sg\_pause(+N)} \\
    & {\tt sg\_yield} \\
    & {\tt sg\_repeat} \\
    \hline
  \end{tabular}
  \vspace{2mm}
  \caption{Simple Graphics Interface.}
  \label{table:SG API}
\end{footnotesize}
\end{figure}

\begin{figure}[htbp]
  \centering
  \includegraphics[width=0.9\columnwidth]{sg-interface.jpg}
  \caption{Spatial-Yap example.}
  \label{figure:spatial-yap example}
\end{figure}

\begin{figure*}[htbp]
  \centering
  \includegraphics[width=1.2\columnwidth]{myddas_blue_print.jpg}
  \caption{Spatial Yap Blueprint.}
  \label{figure:blueprint}
\end{figure*}

\section{Current Applications}

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

\subsection{Study of Traffic Behaviour in the City of Porto}

The aim of this project is to study traffic behavior in the city of
Porto~\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.

\begin{figure}[htbp]
  \centering
  \includegraphics[width=0.9\columnwidth]{coverage.jpg}
  \caption{User Coverage.}
  \label{figure:coverage}
\end{figure}

Routing algorithms and displaying of computed routes are also
implemented using Spatial-Yap and its tabling engine. We also use LP
to map GPS coordinates to street segments. GPS devices in urban-like
environments can report positions which show an error of more than 30
meters in relation to the actual position. This causes uncertainty as
to which road segment the log is actually traversing.  This is
represented as choice-points which are pruned by a Prolog cut, as soon
as the topological layer allows discarding those alternatives.

\subsection{Correction of Automatic Classification of Forests based on 
  Spatial Analysis}

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 (\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, 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.

%% faltam coisas

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

\section{Future Work}

We are currently expanding the MYDDAS interface to support PostgreSQL
and PostGIS, given MySQL is still immature in its Spatial Extensions
and PostGIS is accepted as the main FOSS RDBMS for GIS by the OSGeo
community.

If you want to find out more about this project please check
\url{http://myddas.dcc.fc.up.pt}


%% \begin{thebibliography}{99}

%% \bibitem[Herborg et~al. (2003) Herborg, Bentley, Clare, Rushton]{herborg:2003} 
%% L.M. Herborg, M.G. Bentley, A.S. Clare, S.P. Rushton (2003)
%% \newblock The spread of the Chinese mitten crab (Eriocheir sinensis) in
%% Europe; the predictive value of an historical data set.
%% \newblock {\em Hydrobiologia} 503: 21-28.

%% \end{thebibliography}

\begin{footnotesize}
\bibliographystyle{abbrv}
\bibliography{references}
\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}}

%%% Local Variables: 
%%% mode: latex
%%% TeX-master: main_document.tex
%%% End: 

