\chapter{Evaluation}

\label{ch:results}

This chapter details the tests that were designed to evaluate the
Federation Engine as well as discusses the Engine's performance on
these tests. Section ~\ref{se:plan} details the rationale behind the
choice of test queries, their coverage, and the endpoints whose data
were used for running the test queries. The Discussion section
(~\ref{se:discussion}) provides some explanations for the test
results.

\section{Test Plan}

\label{se:plan}

As presented in chapter ~\ref{ch:architecture}, the novelty of this
system stems from the integration of various Semantic Web technologies
as well as the Optimizer. The evaluation assesses the system's
performance on these two distinct aspects. The metric used to evaluate
the system is the time it takes to perform various task associated
with the system. For the purposes of assessment, five distinct time
metrics were identified: Validation time - the duration from when the
client submits the query to when the Validator sends the query to the
Mapper; Mapping time - the time it takes for the Mapper to perform its
functions; Optimization time - the time it takes for optimization,
Transformation time - the sum of Mapping time and Optimization time;
Execution time - the time it takes for the Orchestrator to take an
optimized query, execute it against the various endpoints, and
recombine the various result sets; and Total time - the end-to-end
time. All times were calculated using the time function in Python's
time module.

For all tests, queries that would generate three subqueries based on
the mapping rules were used. Two different types of tests were
conceived; the first to evaluate the Optimizer, and the second to
evaluate the overall system. Every test was run three times and the
average time was calculated. The Federation Engine was hosted on a
64-bit virtual machine running Ubuntu 10.04 Lucid Lynx Server with 512
Megabits (MB) of Random Access Memory (RAM) and 10 Gigabytes (GB) of
hard disk space.

\section{Optimizer Tests}

The metrics used to assess the optimizer were Mapping Time,
Optimization Time, and Transformation time. The Optimizer functions
independently of query execution and only makes use of the endpoint
source descriptions to do the optimization. As such, all optimizer
tests were performed using a set of mock source descriptions, which
were auto-generated using a python script. A sample mock description is
presented in Appendix ~\ref{ch:mockdesc}.

\begin{center}
\begin{lstlisting}[caption={Optimization Test Query},label={lst:testquery}]
SELECT ?s1 ?s2 ?s3
WHERE {
?s1 p1 ?o1
?s2 p2 ?o2
?o2 p3 ?o3
}

Note: p1, p2, and p3 were replaced in each test with the
      predicates in the auto-generated source descriptions. 
\end{lstlisting}
\end{center}

\subsection{Number of Predicates vs. the Number of Triples per Predicate}

The first set of tests involved varying the number of
predicates and the triples. Three endpoints, each with a total of
300,000 triples were used for this test. A test was run such that the
sum of the products of the number of predicates in an endpoint and the
number of triples associated with each predicate added up to
300,000. For instance, if an endpoint had 30 predicates, it would have
10,000 triples associated with each endpoint. Four tests with the
number of predicates at each endpoint ranging from 3, 5, and 10 to
3000, 5000, and 10000 (across the three endpoints, and the
corresponding number of triples per endpoint such that the total
number of triples would be 300,000) were run. For each test iteration,
the query in Listing ~\ref{lst:testquery} was mapped and optimized.

The results for this test are shown in Figure
~\ref{fig:varying_predicates_number_graph}. Increasing the total
number of triples in an endpoint and the number of triples per
predicate for each of the four cases tested above did not have any
noticeable impacts on the Mapping and Optimization times.

\begin{figure}[float]
\begin{center}
\scalebox{0.45}{\includegraphics{images/num_predicates_vs_num_triples.pdf}}
%\rule[1pt]{12cm}{3pt}
\caption{Number of Predicates vs. Number of Triples per Predicate}
\label{fig:varying_predicates_number_graph}
\end{center}
\end{figure}

\subsection{Sharing of Variables between Subqueries to Different Endpoints}

Next, the impact of different types of queries on the optimizer was
assessed. For this, the three source descriptions with 300, 500, and
1000 predicates, respectively, were used. The following cases were
tested: Variable subjects and objects with no variables sharing
between endpoints; Variable subjects and objects with two endpoints
sharing variable; and, Variable subjects and objects with variable
sharing between all endpoints. The three test cases are illustrated in
Listing ~\ref{lst:var_sharing}.

\begin{center}
\begin{lstlisting}[caption={Variable Sharing between Subqueries},label={lst:var_sharing},float]
#Variables - No Sharing
SELECT ?s1 ?s2 ?s3
WHERE {
?s1 p1 ?o1
?s2 p2 ?o2
?s3 p3 ?o3
}

#Variables - Some Sharing
SELECT ?s1 ?s2 ?s3
WHERE {
?s1 p1 ?o1
?o1 p2 ?o2
?s3 p3 ?o3
}

#Variables - Full Sharing
SELECT ?s1 ?s2 ?s3
WHERE {
?s1 p1 ?o1
?o1 p2 ?o2
?o2 p3 ?s1
}
\end{lstlisting}
\end{center}

The results are shown in Figure ~\ref{fig:variables_sharing}. Similar
tests were conducted with bound subjects and objects. The queries are
in Listing ~\ref{lst:bound_subs_objs_sharing}. Notice in the queries that the
values for subjects and objects need not be present in the endpoint
for successful optimization. The optimizer only cares whether the
subjects and objects are variables or not. It has no knowledge of the
contents of an endpoint beyond the predicates in the source
descriptions. A separate graph for the results are not provided
because the results were identical to the tests with variable subjects
and objects.

\begin{figure}
\begin{center}
\scalebox{0.45}{\includegraphics{images/variables_sharing_between_endpoints.pdf}}
%\rule[1pt]{12cm}{3pt}
\caption{Variables Sharing between Service-Subqueries}
\label{fig:variables_sharing}
\end{center}
\end{figure}

\begin{center}
\begin{lstlisting}[caption={Variable Sharing between Subqueries (Bound Subjects/Objects)},label={lst:bound_subs_objs_sharing}, float]
#Bound Subjects/Objects - No Sharing
SELECT ?s1 ?s2 ?s3
WHERE {
<http://www.alpha.org/as:193856> p1 ?o1
?s2 p2 <http://www.alpha.org/as:193856>
?s3 p3 ?o3
}

#Bound Subjects/Objects - Some Sharing
SELECT ?s1 ?s2 ?s3
WHERE {
<http://www.alpha.org/as:234?> p1 ?o1
?o1 p2 <http://www.beta.org/bo:341209>
?s3 p3 ?o3
}

#Bound Subjects/Objects - Full Sharing
SELECT ?s1 ?s2 ?s3
WHERE {
<http://www.alpha.org/as:183095> p1 ?o1
<http://www.beta.org/bs:IGe23> p2 <http://www.alpha.org/as:183095>
?o2 p3 <http://www.beta.org/bs:IGe23>
}
\end{lstlisting}
\end{center}

\subsection{Number of Triples}

Three tests were run to observe whether increasing the total
number of triples and the number of triples per predicate, while
holding the number of predicates constant, had any effect on
optimization times. This time the three source descriptions with 30,
50, and 100 predicates, respectively, were used. 

First, tests were run with 30,000, 300,000, 3,000,000, 30,000,000, and
300,000,000 total triples, and the corresponding number of triples per
predicate. For example, the 50 predicate endpoint had 600,000 triples
per predicate for the test with total triples of 30,000,000. The
results are shown in Figure ~\ref{fig:number_triples}.

\begin{figure}
\begin{center}
\scalebox{0.45}{\includegraphics{images/num_triples.pdf}}
%\rule[1pt]{12cm}{3pt}
\caption{Total Number of Triples/Number of Triples per Predicate}
\label{fig:number_triples}
\end{center}
\end{figure}

% Furthermore, a few tests were run while varying the sizes and
% structures of the Basic Graph Patterns (BGPs) that were directed at
% each endpoint. The queries used for these tests are shown in Listing
% ~\ref{lst:variable_bgp_size}. The timing data from running these
% queries are shown in Figure ~\ref{fig:variable_bgp_size}.

\section{Federation Tests}

A set of tests were run to assess the end-to-end performance of the
Federation Engine and to test whether the optimization had worked. All
time metrics described in section ~\ref{se:plan} were measured in
these tests. As in the case with the Optimizer tests, queries that
would generate three or more subqueries were used to run these
tests. However, unlike the Optimizer tests, there needed to be actual
endpoints and datasets to execute the subqueries against. The
motivation for the type of queries and the datasets were taken
from~\cite{quilitz08querying}.

Four SPARQL
endpoints~\footnote{http://mcherian.xvm.mit.edu:8000/sparql,
  http://matminton.xvm.mit.edu:9000/sparql,
  http://matminton.xvm.mit.edu:9090/test/, and
  http://air.csail.mit.edu:9000/sparql} were set up using
4store~\footnote{http://4store.org/} - a scalable RDF database - for
testing the performance of the Federation Engine. They were populated
with datasets from
DBPedia~\footnote{http://wiki.dbpedia.org/Downloads36}. The 4store
endpoints are used are shown in Table ~\ref{tbl:endpoints}. E1, E2,
and E3 are hosted on 64-bit virtual machines(VM) running Ubuntu Server
10.04. E1 is hosted on a VM, which has 4 GB of hard drive space and
256 MB of RAM. E2 and E3 are co-hosted on a single VM, which has 10 GB
of hard drive space and 256 MB of RAM. E4 is hosted on a server
(details...). The source descriptions for these endpoints were created
by issuing a number of queries, the results to which contained
predicate and statistical information, directly at the endpoints.

To compare unoptimized query execution against optimized query
execution, a duplicate of the Web Interface was created. The source
code of the two interfaces were identical, except for the the set of subqueries
that was executed (optimized for optimized execution and vice versa).

\begin{table}
\caption{Datasets for Federation}
\centering
\begin{tabular}{c l}
\hline\hline
Endpoint & Dataset (Number of Triples) \\
\hline
E1 & DBPedia Person Data (1.7 million)  \\
E2 & DBPedia Article Categories (12 million) \\
E3 & DBPedia Category Labels (632,000) \\
E4 & DBPedia Infoboxes (13.8 million) \\ [1ex]
\hline
\end{tabular}
\label{tbl:endpoints}
\end{table}

Four queries (shown in Listings ~\ref{lst:endtoendquery1},
~\ref{lst:endtoendquery2}, ~\ref{lst:endtoendquery3}, and
~\ref{lst:endtoendquery4}) of varying difficulty were created. These
were submitted to two instances of the Web Interface.

\begin{center}
\begin{lstlisting}[caption={Q1: German Musicians Who Were Born In Berlin},label={lst:endtoendquery1}]
# German Musicians who were born in Berlin
PREFIX dbpedia: <http://dbpedia.org/ontology/>
PREFIX dbp_resource: <http://dbpedia.org/resource/>
PREFIX dbp_category: <http://dbpedia.org/resource/Category:>
PREFIX dc_terms: <http://purl.org/dc/terms/>
PREFIX foaf: <http://xmlns.com/foaf/0.1/>
PREFIX rdfs: <http://www.w3.org/2000/01/rdf-schema#>  
SELECT ?person ?name ?birthday
WHERE
{
  ?person foaf:name ?name .
  ?person dbpedia:birthDate ?birthday .
  ?person dbpedia:birthPlace dbp_resource:Berlin
  ?person dc_terms:subject dbp_category:German_musicians .
  OPTIONAL {
  dbp_category:German_musicians rdfs:label ?label .
  }
}
\end{lstlisting}
\end{center}
\begin{center}
\begin{lstlisting}[caption={Q4: Presidents of the United States \& Their Vocations},label={lst:endtoendquery4}]
# Presidents of the United States and their Vocations
PREFIX dbpedia: <http://dbpedia.org/ontology/>
PREFIX dbp_category: <http://dbpedia.org/resource/Category:>
PREFIX dc_terms: <http://purl.org/dc/terms/>
PREFIX foaf: <http://xmlns.com/foaf/0.1/>                                
SELECT ?name ?job
WHERE {
  ?person foaf:name ?name .
  ?p dbpedia:occupation ?job .
  ?p dc_terms:subject dbp_category:Presidents_of_the_United_States .
} \end{lstlisting}
\end{center}

These queries were selected for the varying sizes of the result sets
they produced and the number and combinations of endpoints the
subqueries had to be sent off to during execution.

It was noted that the Validation and Mapping Times were identical while running optimized and unoptimized versions of all four queries. This was in line with expectations as the Federation Engine code as well as query structures involved in both cases are the same. 

\begin{center}
\begin{lstlisting}[caption={Q2: Athletes Who Played Professional Baseball \& Basketball},label={lst:endtoendquery2},float]
# People who played professional baseball and basketball        
PREFIX dbpedia: <http://dbpedia.org/ontology/>    
PREFIX dbpedia_category: <http://dbpedia.org/resource/Category:>
PREFIX dc: <http://purl.org/dc/elements/1.1/>
PREFIX dc_terms: <http://purl.org/dc/terms/>
PREFIX foaf: <http://xmlns.com/foaf/0.1/>
PREFIX rdf: <http://www.w3.org/1999/02/22-rdf-syntax-ns#>
PREFIX rdfs: <http://www.w3.org/2000/01/rdf-schema#>
SELECT ?name              
WHERE 
{          
  ?p dc_terms:subject dbpedia_category:Minor_league_baseball_players .
  ?p foaf:name ?name .                     
  ?p dc_terms:subject dbpedia_category:American_basketball_players .    
} 
\end{lstlisting}
\end{center}
\begin{center}
\begin{lstlisting}[caption={Q3: Hollywood Actors Who Were Born In Paris},label={lst:endtoendquery3},float]
#Paris born Movie Stars
PREFIX dbpedia: <http://dbpedia.org/ontology/>   
PREFIX dbp_resource: <http://dbpedia.org/resource/>                   
PREFIX dc: <http://purl.org/dc/elements/1.1/>                      
PREFIX foaf: <http://xmlns.com/foaf/0.1/>
PREFIX rdf: <http://www.w3.org/1999/02/22-rdf-syntax-ns#>
PREFIX rdfs: <http://www.w3.org/2000/01/rdf-schema#>     
SELECT ?name ?m                       
WHERE 
{            
  ?m dbpedia:starring ?p .           
  ?p dbpedia:birthPlace dbp_resource:Paris .                   
  ?p foaf:name ?name .      
  FILTER (?city = dbp_resource:Paris)            
}
\end{lstlisting}
\end{center}                      

\begin{figure}[float]
\begin{center}
\scalebox{0.44}{\includegraphics{images/end_to_end_transformation_times.pdf}}
%\rule[1pt]{12cm}{3pt}
\caption{Transformation Times}
\label{fig:endtoendtranstime}
\end{center}
\end{figure}

\begin{table}[float]
\caption{Queries, Endpoints, \& Result Set Sizes}
\centering
\begin{tabular}{c l c c c}
\hline\hline
Query & Endpoints & RS Size(expected) & RS Size(optimized) & RS Size(unoptimized)\\
\hline
Q1 & E1, E2, E3 & 1 & 1 & 1  \\
Q2 & E1, E4 & 1 & 1 & 1  \\
Q3 & E2, E4 & 8 & 8 & 8 \\
Q4 & E1, E2, E4 & 69 & 69 & 1 \\ [1ex]
\hline
\end{tabular}
\label{tbl:queries}
\end{table}

\begin{figure}[float]
\begin{center}
\scalebox{0.44}{\includegraphics{images/end_to_end_total_times.pdf}}
%\rule[1pt]{12cm}{3pt}
\caption{Total (End-to-End) Times}
\label{fig:endtoendtotaltime}
\end{center}
\end{figure}

Table ~\ref{tbl:queries} shows all the
endpoints needed to answer a query, the expected size of the result
set, and the sizes of the result sets obtained from the execution of
the optimized and unoptimized versions of the query. These numbers were calculated by manually issuing the subqueries to the endpoints and tabulating the size of the result set.

The expected result sizes and the actual result sizes are included to
track a behavior often seen in most well-established SPARQL
endpoints. Such endpoints limit the number of results it outputs to
prevent poorly designed queries from consuming a large amount of
system resources. Therefore, even when an unoptimized query is fired
against an endpoint, a result set is returned in a reasonable amount
of time, instead of a hung query. However, because of the limit on the
results, the returned result set would only be a subsection of the
amount of data that matches the Basic Graph Pattern in the
query. During testing, this limit could have been done away with as
the endpoints were set up purely for testing purposes. However, the
decision was made to leave the limits in place to simulate real-world
behavior.

Figure ~\ref{fig:endtoendtranstime} compares the
Transformation times of the optimized and non-optimized
versions. Figure ~\ref{fig:endtoendtotaltime} compares the Total time
between the two.

\section{Discussion}

\label{se:discussion}

\subsection{Optimizer Tests}

The results of the Optimizer tests provide several insights. As seen in Figure ~\ref{fig:number_triples}, the total
number of triples and the number of triples per predicate had no
impact on the Mapping or Optimization times. This result was indeed in
line with pre-test expectations. The mapping rules contain no
statistical information; hence varying the statistical information
such as number of triples should not have any effect on the Mapping
time, which is the time it takes for mapping and rewriting the query
by scanning the mapping rules file. The Optimizer, on the other hand,
does make use of endpoint statistics. However, it only uses this
information to do basic arithmetic operations to rank the various
endpoints. Therefore, it was expected that the range of the numbers
used in testing (30,000 to 300,000,000) should not have any effect on
the time taken for optimization.

By the above line of reasoning, it is clear why the Mapping times and
Optimization times increased when the number of predicates
increased (see Figure ~\ref{fig:varying_predicates_number_graph}). As the number of predicates increases, both the Mapper and
the Optimizer have to read in and parse larger mapping rules file and
source descriptions, respectively, to perform their functions.

Furthermore, the number of bound variables in queries and the level of
sharing of variables between subqueries had little impact on the
timing values, as seen in Figure ~\ref{fig:variables_sharing}. First of all, the Mapper functions are independent of
these two characteristics. And, once again, it was not surprising that
the optimization times were unaffected. Regardless of whether the
variables are bound or not, and irrespective of whether two or more
subqueries share variables, the optimizer performs the same number of
checks and iterations when it parses a query with SERVICE bound
subqueries. Hence, the extent of sharing of subjects and objects, and
the number of bound subjects and objects would not have any impact on
the optimization times.

The various Optimizer tests reveal that increasing the size of the
mapping and source description files have a significant impact on
mapping and optimization times. Varying other aspects of queries and
endpoints had little effects on said times. Therefore, it is possible
that decreasing the scan/parse times for the file would have
significantly improve the performance of the Federation Engine on the
whole. The use of a faster file I/O library could go a long way
towards achieving this goal. However, this possibility was not
explored in this research.

\subsection{Federation Tests}

The results of the Federation tests were more interesting than the
ones from testing the Optimizer by itself. The obvious observation was
the fact that Transformation times (Figure
~\ref{fig:endtoendtranstime}) were noticeably higher across all four
queries for the Engine with the Optimizer when compared to the one
without it. There is no surprise here because the Transformation time
is the sum of Mapping time and Optimization time, and Optimization
time is zero for the federator without the optimizer. However, notice
that the Transformation time is only a fraction of the Total time.

A first glance at Total times (Figure ~\ref{fig:endtoendtotaltime})
gives the impression that the unoptimized federator did better than
the optimized one in 3 out of 4 queries. However, a closer look
reveals some interesting outcomes. As the complexity of the query
increased, the Total time advantage that the unoptimized version has
markedly disappear. While the unoptimized version did 50\% better than
its optimized counterpart in Q1, by Q3 the advantage diminishes to
about 13\%, and in Q4 the optimized query takes 50\% to return the
result set after query submission.

The other key observation from the Federation tests is seen by
comparing the Total time (Figure ~\ref{fig:endtoendtotaltime}) to the
expected and actual number of results (Table ~\ref{tbl:queries}). Note that
for Q4, the expected size of the result set was 69. While the
optimized version, did return all 69, the unoptimized version returned
a result set of size 1. What happened here was that the federator
without the optimizer sent the subquery that contains the triple {\em
  ?p dbpedia:occupation ?job} in its WHERE clause to be executed
first. However, because this subquery has a low selectivity (with a
result set size of approximately 140,000), the endpoint hit its upper
bound and returned only a subset of the results. And, this result set
only had one U.S. President in it, which caused the conjunctions with
the subsequent subqueries to return exactly one result.

The Federation tests demonstrate that, although the addition of the
Optimizer contributes to an increase in Total time, this increase is a
price worth paying. Even with a marginal increase in the complexity,
the disadvantage of having the Optimizer starts to disappear and we
also see that without it in line, incomplete result sets would be
returned.

Another lesson learned from testing relates to SPARQL endpoints.
Initially, the plan was to use existing SPARQL endpoints to run the
queries. Three or four endpoints, which shared Graph elements, would
be chosen and queries designed such that the Mapper would generate
subqueries that hit three or more of them. Choosing popular existing
endpoints would also buttress the practical relevance of the
Federation Engine. Moreover, it would have involved not repeating work
that is not fundamental to the design or implementation of the
Federation Engine. As a result, a few of the Bio2RDF
endpoints~\footnote{http://www.freebase.com/view/user/bio2rdf/public/sparql}
were identified. However, the task of identifying the overlap between
Graphs on different endpoints was more daunting than initially
expected. The large size of the datasets meant that the queries
required to extract endpoints' predicate and statistical information
required to create the source description files did not run to
completion.

Both the Optimizer and Federation tests are very pertinent to the
proposed application of the Federation Engine at the Massachusetts
Department of Education in chapter ~\ref{ch:usecase}. The database
that holds student MCAS information, for instance, would contain
approximately 12 millions triples~\footnote{550,000 students * 3
  tests/year * 7 testing years = 11.55 million} of raw test
data. School districts would maintain student demographic information
databases that contain, on average, approximately 75,000
triples~\footnote{(550,000 students/391 districts) * 52 student
  characteristics = 73,146}. The test demonstrate that even if the
number of triples were to increase an order of magnitude, the
Optimizer would continue to perform sufficiently. Moreover, the
hardware that hosts the education datasets would be much more powerful
and feature-rich than the virtual machines used for evaluating the
Federation Engine. 

However, the effects of the size of data transferred between
endpoints on federation capabilities are still unknown. A
query similar to the one described in Listing ~\ref{lst:sample} might
involve tens or even hundreds of school endpoints. Even in those cases
where the number of endpoints is in the single digits, the data
transferred might be much larger than what was encountered during
testing. For instance, MCAS math scores from all previous years of all
tenth grade students from a particular school (approximately
1800~\footnote{300 students * 6 years = 1800 data points}) might have
to be pulled to observe an interesting pattern. The Federation
Engine's performance under such circumstances cannot be assessed until
a commercial scale test system is deployed at the DESE and in
districts around the Commonwealth.

\section{Limitations}

Although the Optimizer and the Federation Engine as a whole proved
quite successful in the various tests, this system has a few
shortcomings. First, if a user wished to execute queries beyond the
sample ones provided on the Web Interface, she would find it very
difficult to do so. It would require knowledge of the underlying
ontology and the predicates contained in the endpoints registered with
the Federation Engine. However, currently this information is not
being furnished to the user in any form.

Second, the Optimizer is based on an algorithm that makes use of a
simple cost model. This set up would prove insufficient for queries
that are much more complex than the ones explored in testing.

Third, the requirement for bound predicates limits the types of
queries that a user is able to execute using the Federation Engine. This
limitation can prevent the engine from gaining a large user base.
