\chapter{A Secure SPARQL Federation Paradigm}

\label{ch:architecture}

Thus far, the various benefits of a secure SPARQL federation systems
have been illustrated by comparing it against existing technologies
and exploring its application at the Massachusetts Department of
Education. Now it is time to look at the SPARQL federation model in
more detail. This chapter details the design of the Federation
Engine. The features of the various components of the system are
described as are the rationale behind various design choices.

\section{Architecture}

\label{se:arch}

As alluded to in chapter ~\ref{ch:background}, the primary motivation of
this thesis work was to bring together various Semantic Web
technologies and provide an integrated environment that demonstrates the
benefits of the secure SPARQL federation paradigm. In addition, this
thesis also provides an optimization algorithm for optimizing and
rewriting SPARQL queries. The architecture was first laid out
in~\cite{cherian10sparqlfed}. A few updates have been made to the
initial design and the complete architecture is described in the following subsections.

The system is illustrated in Figure~\ref{fig-arch}. Its main components are the
i) Validator (section ~\ref{sse:valid}), which validates the query provided by the user;
ii) the Mapper (section ~\ref{sse:map}), which splits the query to several subqueries based on descriptions of endpoints;
iii) the Optimizer (section ~\ref{sse:opt}), which reorders the
subqueries according to the optimization metrics; iv) the Orchestrator
(section ~\ref{sse:orch}), which executes the subqueries and integrates the various
result sets; and, v) the Proof Generator (section ~\ref{sse:proofgen}), which generates
a proof for each secure SPARQL endpoint based on client supplied credentials and
endpoint descriptions, if necessary. The Federation Engine also has in its
possession the source descriptions (section ~\ref{sse:sdesc}) of the endpoints
that have registered with it. The Map Generator utility (section ~\ref{sse:mapgen})
generates a set of mapping rules based on these sources descriptions, which is
used by the Mapper. The data in the endpoints are in RDF, which means that query
results from multiple endpoints can be easily integrated using common variable
bindings.

The system functions as follows: A client submits a query to the Federation
Engine on a web-form. The Validator validates the query and forwards it to the
Mapper. The Mapper rewrites the query into various subqueries based on the
source descriptions known to the Federation Engine. Once the mapping is
done, the Optimizer performs the optimization and reorders the subqueries. If any of
the endpoints in the query plan requires specific credentials for data access,
the user is prompted to supply them at this point. Then, the Proof Generator
generates a proof based on the user supplied credentials. The optimized list of subqueries,
along with any generated proofs, is forwarded to the Orchestrator. The
Orchestrator accepts the optimized list of queries, sends the subqueries along with proofs to the
various endpoints, integrates the different result sets, and forwards the final
result to the client on the web-form.

% \begin{figure*}[!t]
%   \centerline{\epsfig{file=images/architecture.jpg, height=2.7in}}
%   \caption{System Architecture}
%   \label{fig-arch}
% \end{figure*}

\begin{figure}
\begin{center}
\scalebox{0.7}{\includegraphics{images/architecture_rot.pdf}}
\rule[3pt]{12cm}{3pt}
\caption{System Architecture}
\label{fig-arch}
\end{center}
\end{figure}

Some of the benefits of this architecture have already been presented in chapter
~\ref{ch:usecase}. The following subsections, which explain the architecture in
further detail, elucidate these benefits more.

\subsection{SSL}
The Federation Engine uses the SSL protocol to communicate with a user
who wants to query the orchestration engine. The use of SSL ensures
that the data transfers between the client and the engine happens via
a secure channel. Such transfers would protect the confidentiality of
queries, results, and credentials that are exchanged. The client
contacts the engine through an SSL handshake during which the client
provides the engine a certificate with a public key. The SSL module
uses the public key to authenticate the user. Once this process is
complete, the module notifies the client of its decision. If there was
successful authentication, the client is allowed to submit SPARQL
queries to the Federation Engine.

\subsection{Validator}

\label{sse:valid}

The validator checks the query to see whether it is compatible with the SPARQL
1.0 syntax specified in ~\cite{sparqlw3c}. It also asserts that all the prefixes
used in the WHERE clause of the query has been declared in the PREFIX section
of the query. Moreover, specific to this federation engine, the validator
verifies that the various triples in the query contain no variable
predicates. Bound predicates are necessary for the Mapper to map the triples in
the query to the various endpoints, whose service descriptions are known to the Federation
Engine. If any of the above checks fail, the user is notified of the
submission of an invalid query.

It is possible to use variable predicates when querying a single SPARQL endpoint
because the predicate could take on the value of any of the predicates the
endpoint contains. However, in a federated setting, variable predicates would
mean that the Federation Engine would fail to map a particular query to any
endpoint. If subject and/or the object of a triple containing a variable
predicate is bound, it may be possible, generally speaking, to map this triple to
a particular endpoint. However, a design decision was made in the case of this
Federation Engine to have only the list of predicates in the source description
file (described in more detail in ~\ref{sse:sdesc}). While it is possible
to find out if an endpoint has a particular predicate based on the bound
subject/object information by issuing queries on the fly, such a step would
drastically increase the time required to execute a federated query, thereby
reducing the utility of this Federation Engine.

\subsection{Mapper}

\label{sse:map}

The Mapper takes the validated query and generates subqueries based on a
predicate to source mapping rules, which are generated by the Map Generator
utility. For instance, suppose that the user has input the query in Listing
~\ref{lst:usrin}.

\begin{center}
\begin{lstlisting}[caption={Input Query},label={lst:usrin},float]
PREFIX dese: <http://www.mass.gov/dese#> 
PREFIX teacher: <http://www.mass.gov/dese/teacher_db#>
SELECT ?student ?mscore ?name ?cert_score ?status
WHERE 
{ 
  ?student dese:id ?sasid ;  
           dese:3rd_math_score ?mscore ;  
           dese:has_math_teacher ?teacher
  ?teacher teacher:cert_status ?status ;
           teacher:math_score ?score .
  OPTIONAL 
  {         
    ?teacher teacher:has_name ?name
  }
}
\end{lstlisting}
\end{center}

From the set of mapping rules (an example is shown in Listing ~\ref{lst:maprule}), it is evident
that the student information is contained in the MCAS endpoint - \\
http://dese.mass.gov/mcas/data/sparql - and the teacher information is found
in the educator information endpoint - \\
http://dese.mass.gov/educators/sparql. Based on this information, the
Mapper transforms the query into the subqueries in Listing ~\ref{lst:mapquery}.

\begin{center}
\begin{lstlisting}[caption={Mapped Query},label={lst:mapquery},float]
SELECT ?student ?mscore ?name ?cert_score ?status
WHERE 
{ 
  SERVICE <http://dese.mass.gov/mcas/data/sparql>
  {
    ?student <http://www.mass.gov/dese#id> ?sasid .
    ?student <http://www.mass.gov/dese#3rd_math_score> ?mscore .  
    ?student <http://www.mass.gov/dese#has_math_teacher> ?teacher .
  }
  SERVICE <http://dese.mass.gov/educators/sparql>
  {
    ?teacher <http://www.mass.gov/dese/teacher_db#cert_status> ?status .
    ?teacher <http://www.mass.gov/dese/teacher_db#math_score> ?score . 
  OPTIONAL 
  {
    SERVICE <http://dese.mass.gov/educators/sparql>
    {         
      ?teacher <http://www.mass.gov/dese/teacher_db#has_name> ?name .
    }
  }
}
\end{lstlisting}
\end{center} The Mapper puts in the SERVICE annotations, which the Orchestrator uses to
select the endpoints to send the subqueries to. Also, notice that the
Mapper has resolved the prefixes during the query transformation process.

If the Mapper cannot find one of the query predicates in the set of mapping
rules, the user is notified that the query cannot be successful executed. As a
result, one could argue that there is some validation done by the Mapper as
well.

\subsection{Source Descriptions}

\label{sse:sdesc}

The details of the SPARQL endpoints that are registered with the
Federation Engine are stored in the source descriptions. Two sample
source descriptions are shown in Listings ~\ref{lst:desesdesc} and
~\ref{lst:teachersdesc}. The source descriptions are in the Notation3
(N3)\footnote{Notation3 is a shorthand non-XML serialization of
  Resource Description Framework models, designed with human
  readability in mind~\cite{bernerslee06n3}} format. Each contains an
endpoint's name, URI, read latency, total number of triples, and a
list of predicates. For each predicate, the number of triples that
contain that predicate as well as the number of distinct objects
associated with the predicate are provided. The optimizer makes use of
this statistical information. It is possible to generate this
statistical information with a set of predefined SPARQL
queries. However, this work assumes that they are part of the input
from each endpoint that registers with the Federation Engine.

When an endpoint registers with the Federation Engine, it provides a source
description. The endpoint administrator also updates the source description when
any changes are made to the endpoint's data.

\begin{center}
\begin{lstlisting}[caption={DESE MCAS Endpoint's Source Description},label={lst:desesdesc},float]
@prefix dese: <http://www.mass.gov/dese#>.
@prefix rdf: <http://www.w3.org/1999/02/22-rdf-syntax-ns#>.
@prefix sd: <http://dig.csail.mit.edu/service_description#>.

<http://dese.mass.gov/mcas/data/sparql> rdf:type          sd:Endpoint ;
                                sd:name           \``MCAS Test Database'' ;
                                sd:has_policy     <http://dese.mass.gov/mcas/policy.n3> ;
                                sd:read_latency   5.2;
                                sd:total_triples  4673239;
                                sd:num_predicates 3;
                                sd:has_Predicate  dese:id  ;
                                sd:has_Predicate  dese:3rd_math_score ;
                                sd:has_Predicate  dese:has_math_teacher .
dese:id                         sd:num_triples    532346 ; 
                                sd:num_objects    532346 .
dese:3rd_math_score             sd:num_triples    214759 ;
                                sd:num_objects    100 .
dese:has_math_teacher           sd:num_triples    528631 ; 
                                sd:num_objects    31209 .
\end{lstlisting}
\begin{lstlisting}[caption={MA Teacher Information Endpoint's Source Description},label={lst:teachersdesc},float]
@prefix teacher: <http://www.mass.gov/dese/teacher_db#>.
@prefix rdf: <http://www.w3.org/1999/02/22-rdf-syntax-ns#>.
@prefix sd: <http://dig.csail.mit.edu/service_description#>.

<http://dese.mass.gov/educators/sparql> rdf:type          sd:Endpoint ;
                              sd:name           \``MA Educator Database'' ;
                              sd:policy         <http://dese.mass.gov/educators/policy.n3>
                              sd:read_latency   4.7;
                              sd:total_triples  27931373;
                              sd:num_predicates 3 ;
                              sd:has_Predicate  teacher:has_name ;
                              sd:has_Predicate  teacher:math_cert_score ;
                              sd:has_Predicate  teacher:cert_status .
teacher:has_name              sd:num_triples    77546 ; 
                              sd:num_objects    77536 .
teacher:math_cert_score       sd:num_triples    234634 ;
                              sd:num_objects    100 .
teacher:cert_status           sd:num_triples    156450 ;
                              sd_num_objects    5 .
\end{lstlisting}
\end{center}

\subsection{Map Generator}

\label{sse:mapgen}

The Map Generator utility generates a set of rules that provides a mapping from
the predicates contained in the various source descriptions to the appropriate
endpoint. The set of rules generated based on the two source descriptions
in Listings ~\ref{lst:desesdesc} and ~\ref{lst:teachersdesc} is illustrated in Listing ~\ref{lst:maprule}. The Mapper uses
these rules to rewrite the query with SERVICE annotations for each triple in the
query. The set of mapping rules is generated out-of-band and the generation
happens when new sources register with the Federation Engine or when an existing
source description is updated.

\begin{center}
\begin{lstlisting}[caption={Mapping Rules for Education},label={lst:maprule},float]
LABEL 'http://www.mass.gov/dese#id' CONSTRUCT 
{?rs <http://www.mass.gov/dese#id> ?ro} {SERVICE
<http://dese.mass.gov/mcas/data/sparql> 
{?rs <http://www.mass.gov/dese#id> ro}}
LABEL 'http://www.mass.gov/dese#school' CONSTRUCT 
{?rs <http://www.mass.gov/dese#school> ?ro} {SERVICE
<http://dese.mass.gov/mcas/data/sparql> 
{?rs <http://www.mass.gov/dese#school> ?ro}}
LABEL 'http://www.mass.gov/dese#reduced_lunch' CONSTRUCT 
{?rs <http://www.mass.gov/dese#reduced_lunch> ?ro} {SERVICE
<http://dese.mass.gov/mcas/data/sparql> 
{?rs <http://www.mass.gov/dese#reduced_lunch> ?ro}}
LABEL 'http://www.mass.gov/dese#3rd_math_score' CONSTRUCT 
{?rs <http://www.mass.gov/dese#3rd_math_score> ?ro} {SERVICE 
<http://dese.mass.gov/mcas/data/sparql>
{?rs <http://www.mass.gov/dese#3rd_math_score> ?ro}} 
LABEL 'http://www.mass.gov/dese#has_math_teacher' CONSTRUCT 
{?rs <http://www.mass.gov/dese#has_math_teacher> ?ro} {SERVICE
<http://dese.mass.gov/mcas/data/sparql> 
{?rs <http://www.mass.gov/dese#has_math_teacher> ?ro}}
LABEL 'http://www.mass.gov/dese/teacher_db#has_name' CONSTRUCT 
{?rs <http://www.mass.gov/dese/teacher_db#has_name> ?ro} {SERVICE
<http://dese.mass.gov/educators/sparql> 
{?rs <http://www.mass.gov/dese/teacher_db#has_name> ?ro}} 
LABEL 'http://www.mass.gov/dese/teacher_db#cert_status' CONSTRUCT 
{?rs <http://www.mass.gov/dese/teacher_db#cert_status> ?ro} {SERVICE
<http://dese.mass.gov/educators/sparql> 
{?rs <http://www.mass.gov/dese/teacher_db#cert_status> ?ro}} 
LABEL 'http://www.mass.gov/dese/teacher_db#math_cert_score' CONSTRUCT 
{?rs <http://www.mass.gov/dese/teacher_db#math_cert_score> ?ro} {SERVICE
<http://dese.mass.gov/educators/sparql>
{?rs <http://www.mass.gov/dese/teacher_db#math_cert_score> ?ro}}
LABEL 'http://www.mass.gov/dese/teacher_db#cert_date' CONSTRUCT 
{?rs <http://www.mass.gov/dese/teacher_db#cert_date> ?ro} {SERVICE
<http://dese.mass.gov/educators/sparql>
{?rs <http://www.mass.gov/dese/teacher_db#cert_date> ?ro}}
LABEL 'http://www.mass.gov/dese/teacher_db#teaches_at' CONSTRUCT 
{?rs <http://www.mass.gov/dese/teacher_db#teaches_at> ?ro} {SERVICE
<http://dese.mass.gov/educators/sparql>
{?rs <http://www.mass.gov/dese/teacher_db#teaches_at> ?ro}}
\end{lstlisting}
\end{center}

\subsection{Optimizer}

\label{sse:opt}

The optimizer takes the mapped query and reorders the SERVICE clauses
(subqueries) based on the statistical information contained in the
service descriptions. The optimization algorithm used by the Optimizer
is based on the techniques described in ~\cite{bernstein07optarq}. The
purpose of optimization is to minimize the execution time of a
federated query. To do this, it is essential to minimize the transfer
of result set data from one endpoint to another. The Optimizer ensures
that the subquery that would produce the smallest result set is
executed first so that the variable bindings from that result set may
be used to bind variables in other subqueries, which share the same
variables, before they are executed.

\begin{center}
\begin{lstlisting}[language=Pascal,caption={Optimization Algorithm},label={lst:optalgo},mathescape=true,keywordstyle=\bfseries,float]
Definitions: s: subject; p: predicate; o: object, t: triple; 
             a$_t$: element a of t, bound(a): $\not$ variable, for a $\in$ {s,p,o};
             A.index(a) - value in A that corresponds to 'a'
             num_triples(p) - number of triples containing p; 
             num_objects(p) - number of objects with predicate p;
             $E  =  \bigcup_{i=1}^{n} E_i$, is the set of all endpoints
             $MQ =  \bigcup_{i=1}^{n} SQ_{E_i}$ //$ SQ_{E_i} $ is the subquery bound for $E_i$ 
             $S_{E_i} = \bigcup_t s_t, \forall t \in SQ_{E_i}$ is the set of all subjects in $SQ_{E_i}$
             $S  =  \bigcup_{i=1}^{n} S_{E_1}$
             $O_{E_i} = \bigcup_t o_t, \forall t \in SQ_{E_i}$ is the set of all objects in $SQ_{E_i}$
             $O  =  \bigcup_{i=1}^{n} O_{E_1}$ 
             RS_size$_{SQ_{E_n}}$ = $\bigcup_t$ rs_size$_t, \forall t \in SQ_{E_i}$
             RS_sizes = $\bigcup_{i=1}^{n}$ RS_size$_{SQ_{E_i}}$

#Ranking Endpoints
Estimate_Result_Set_Size($MQ$)
for each $SQ_{E_i} \in MQ, $ do
  for each $atom \in ${$S_{E_i},O_{E_i}$}$, \forall i$ do
      for each {$S_{E_j},O_{E_j}$} $\in$ {$S,O$} $\forall j \neq i$ do
          if $atom \in S_{E_j}$ then
             temp = RS_Size$_{SQ_{E_i}}$.index(atom) - RS_Size$_{SQ_{E_j}}$.index(atom)
             if (temp < 0) then
                 RS_Size_Reduce_Ability$_{SQ_{E_i}}$.index(atom) = 
                                   max(RS_Size_Reduce_Ability$_{SQ_{E_i}}$)
             else
                 RS_Size_Reduce_Ability$_{SQ_{E_j}}$.index(atom) = 
                                   max(RS_Size_Reduce_Ability$_{SQ_{E_j}}$)
sort {$E$} by ($\sum_i$RS_Size_Reduce_Ability$_{SQ_{E_i}}$ \over Read_Latency$_{E_i}, \forall i$)
return {$E$}

#Estimate_Result_Set_Size($MQ$)
for each $SQ_{E_i} \in MQ, $ do
  for each $t \in SQ_{E_i}$ do      
    rs_size$_t$ = num_triples(p$_t$)
    if bound($s_t$) then
       rs_size$_t$ = 1 + (1 - #o(p$_t$)/#t(p$_t$)) * num_triples($_t$)
    if bound(o$_t$) then
       rs_size$_t$ = 1
    if $s_t \in S_{E_i}$ then
       rs_size$_t$ = rs_size($S_{E_i}.index(s_t)$) = min(rs_size$_t$,rs_size($S_{E_i}.index(s_t)$))  
    if $s_t \in O_{E_i}$ then
       rs_size$_t$ = rs_size($O_{E_i}.index(s_t)$) = min(rs_size$_t$,rs_size($O_{E_i}.index(s_t)$))
    if $o_t \in S_{E_i}$ then
       rs_size$_t$ = rs_size($S_{E_i}.index(o_t)$) = min(rs_size$_t$,rs_size($S_{E_i}.index(o_t)$))
    if $o_t \in O_{E_i}$ then
       rs_size$_t$ = rs_size($O_{E_i}.index(o_t)$) = min(rs_size$_t$,rs_size($O_{E_i}.index(o_t)$))
    $S_{E_i}$.add($\bigcup_t s_t$), $O_{E_i}$.add($\bigcup_t o_t$), rs_size.add($\bigcup_t$ rs_size$_t$), $\forall t \in SQ_{E_i}$    
\end{lstlisting}
\end{center} 
Optimization is a two step process. In the first step, the size of
the result set of a subquery directed towards a specific SPARQL endpoint is
estimated based on the statistical information - number of triples that contain
a specific predicate and the number of distinct objects associated with that predicate - contained in the endpoint's source
description. Then, the subjects and objects in the triples of a particular
subquery are compared against the subjects and objects in triples of all other
subqueries to see whether the subqueries share variables. If there are shared
variables, it means that it is better to execute the subquery that would result
in the smaller result set. The optimization algorithm is described in Listing ~\ref{lst:optalgo}.

\subsection{Orchestrator}

\label{sse:orch}

The Optimizer sends the reordered query to the Orchestrator. The Orchestrator
sends each subquery to the endpoint listed after the SERVICE keyword in the
subquery. Once the results are returned from an endpoint, the Orchestrator checks
to see if any of the subject- or object-bindings in the result set maybe used to bind
the variables in the remaining subqueries. If so, these variables are bound
before those subqueries are sent to their respective SPARQL endpoints. For those
endpoints that require credentials from the querying user, the Orchestrator
forwards the policy proofs generated by the Proof Generator using the
credentials supplied by the client. Once all the queries have returned with the
results, the Orchestrator combines the result sets and returns the combined
result set back to the client via the web-form.

\subsection{Proof Generator}

\label{sse:proofgen}

The Proof Generator generates a proof that demonstrates that a given client is
privy to the information contained in an endpoint that restricts access to its
data to a subset of users. To generate this proof, the Proof Generator makes use
of user credentials, provided by the client, and the data usage policies for an
endpoint, which the endpoint provides the Federation Engine with (in addition to
the source description) during the registration/update process. The endpoint
would provide the data usage policies defined in AIR\footnote{AIR (AMORD In RDF)
  is a policy language that is represented in Turtle (subset of N3) + quoting
  and supports AMORD-like constructs. The language describes several classes and
  properties that can be used to define policies~\cite{air}}, a policy language
grounded in Semantic Web Technologies.

The authorization mechanism proposed for the Federation Engine is based on
Proof-carrying Authorization (PCA)~\cite{bauer03access, bauer05distributed} and
earlier work on Policy-Aware Web (PAW)~\cite{paw, kolovski05towards,
  kagal06self, kagal06using} done at DIG. PCA is an authorization framework
that is based on a higher-order logic (AF logic) where clients have to generate
proofs using a subset of AF logic and the authorizing server's task is to check
if the proof is grounded and consistent. This allows objects in the system to
have a finer-grained control of information and enables a smaller trusted
computing base on the server. DIG's work moved these ideas to the open Web using
Semantic Web technologies to express policies and proofs.

Though proof generation may be performed by the client, by delegating it to the
federation, the load on the client is reduced as are the round trips between the
client and secure SPARQL endpoints to obtain required credentials. As a result,
if a client does not possess the necessary credentials, she can be notified well
before the subqueries are sent off to the endpoints, thereby improving the
efficiency of a federated setup. 

The Proof Generator is a forward chained reasoner~\cite{kagal08using} that uses
client credentials and online resources to generate a proof for how the client
meets a specific policy. This proof is forwarded to the orchestration engine,
which uses it to execute subqueries at endpoints that require proofs. If the
Proof Generator is not able to generate a required proof based on the client's
credentials, the client is informed and is afforded the option to provide
additional credentials.

\subsection{PAW-enabled SPARQL Endpoint}

SPARQL endpoints exist as autonomous entities that interact with the
secure Federation Engine via SPARQL queries and responses. Each
endpoint may, and ideally will, have some data and corresponding
descriptions that are unique to it. Any endpoint that wants to operate
as part of the architecture described here, would provide the
Federation Engine with a source description and, if applicable, usage
policies that suit its needs. Those secure endpoints that have usage
policies and require proofs from the Federation Engine to allow user
access would have a built-in proof checking
component~\cite{kolovski05towards}, which verifies the proofs. If the
proof is valid, the endpoint provides the Federation Engine with the
results to the query. If not, the Federation Engine is notified of the
failed proof check. 

If the Proof Generator in the Federation Engine functions properly, it
is very unlikely that the proof check would fail. However, the proof
check is still necessary because the SPARQL endpoints do not
implicitly trust the Federation Engine.




