
\title{Spatial-Yap: A Spatio-Deductive Database System}
\author{David Vaz and 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.

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.

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

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

\begin{figure*}[htbp]
  \centering
  \includegraphics[width=0.5\textwidth]{proceedings/vaz/sg-interface.jpg}
  \caption{Spatial-Yap example.}
  \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}.

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




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

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.



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

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

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

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

\section{Future Work}

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.

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.

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

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