\documentclass{llncs}
\usepackage{graphicx}
\usepackage{url}
\usepackage{subfigure}
\usepackage{listings}
\usepackage{color}
\usepackage{epsfig}
\usepackage{color}
\usepackage{alltt}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%% ISWC 2009 Research Track/Call for Papers, max . 16 pages, CfP see:
%% http://iswc2009.semanticweb.org/wiki/index.php/ISWC_2009_Research_Track/Call_for_Papers

\definecolor{lightblue}{rgb}{.3,.5,1}
\definecolor{orange}{rgb}{1,.7,0}
\definecolor{darkorange}{rgb}{1,.4,0}
\definecolor{darkgreen}{rgb}{0,.4,0}
\definecolor{darkblue}{rgb}{0,0,.4}
\definecolor{darkred}{rgb}{.56,0,0}
\definecolor{gray}{rgb}{.2,.2,.2}
\definecolor{shadecolor}{gray}{0.7}

%% define RDFa look and feel
\lstdefinelanguage{RDFa}{
      morekeywords=[1]{about, ref, rel, content, property, href, resource, datatype, typeof},
      morestring=[b]",
      sensitive=false%
}[keywords,comments,strings]

\lstset{
      basicstyle = \scriptsize \ttfamily,%
      keywordstyle = [1]\color{darkgreen},%
      stringstyle  = \ttfamily\color{darkred},%
      commentstyle = \itshape\color{darkblue},%
      showstringspaces = false,%
%     fancyvrb = true,%
      firstnumber = auto, stepnumber=1, numbersep=5pt,%
      numbers=left, numberstyle=\tiny \ttfamily,
      frame = shadowbox, frameround = ffff, rulesepcolor = \color{shadecolor},
      breaklines=true, breakatwhitespace=true,%
%     prebreak=\textellipsis,postbreak=\textellipsis,%
      emphstyle = \color{red}\underbar, emphstyle = {[2]\color{blue}\underbar},%
      extendedchars = true, inputencoding = utf8,%
%     backgroundcolor=\color{shadecolor},
      xleftmargin=20pt, xrightmargin=10pt,
      captionpos = b
}


%% define N3 look and feel
\lstdefinelanguage{N3}{
      morekeywords=[1]{@prefix, a },
      morestring=[b]",
      morecomment=[s]{<}{>}, % missusing comments for URIrefs
      otherkeywords={^, [, ], (, )},%
      %otherkeywords=[2]{<, >},% for URIrefs
      sensitive=false%
}[keywords,comments,strings]

\lstset{
      basicstyle = \scriptsize \ttfamily,%
      keywordstyle = [1]\bfseries\color{darkgreen},%
      stringstyle  = \ttfamily\color{darkred},%
      commentstyle = \itshape\color{darkblue},%
      showstringspaces = false,%
%     fancyvrb = true,%
      firstnumber = auto, stepnumber=1, numbersep=5pt,%
      numbers=left, numberstyle=\tiny \ttfamily,
      frame = shadowbox, frameround = ffff, rulesepcolor = \color{shadecolor},
      breaklines=true, breakatwhitespace=true,%
%      prebreak=\textellipsis,postbreak=\textellipsis,%
      emphstyle = \color{red}\underbar, emphstyle = {[2]\color{blue}\underbar},%
      extendedchars = true, inputencoding = utf8,%
%     backgroundcolor=\color{shadecolor},
      xleftmargin=5pt, xrightmargin=2pt,
      captionpos = b
}

\begin{document}

\title{Provenance of Inferences: A Trail of Proofs in Linked Open Data}

\author{Kanghao Lu \and Oshani Seneviratne \and Tim Berners-Lee}

\institute{MIT CSAIL, Cambridge\\
Massachusetts, USA\\ 
\email{( kennylu | oshani | timbl )@csail.mit.edu }
}

\maketitle
\begin{abstract}

With the recent uptake on the linked open data on the Web, there are many interlinked data sets on the Web today. Interesting results that might not be obvious from this \emph{raw} data itself, can be derived by computing answers to rules using the data and essentially connecting the dots to see the big picture. We describe a novel method to crawl the Web of data and make inferences that satisfy rules of a particular domain and to re-inject the derived conclusions, along with their proofs in a proof ontology, back into the read-write Web. We have developed a ``Computation Agent" to do this, using rules written in a formal Semantic Web rule language, and a user interface for viewing data along with their proofs that give the justification for that particular data in an intuitive manner.

\end{abstract}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%% Introduction
\section{Introduction}								\label{intro}

% Semantic Web is a Web of machine processable data, preferably in RDF and are linked together. The fundamental assumption of Semantic Web is that every important thing has a unique global name in the form of a Universal Resource Identifier (URI). This URI can be dereferenced to obtain a file. From this file, it may be possible to extract some RDF triples. A nonempty subset of these triples compose information about the thing, namely, the subject or the object of the thing. Therefore, Semantic Web provides a platform to include integration of heterogeneous data using explicit semantics, simplified annotation, explicit models for data representation, aggregation and easier re-use of data in unanticipated ways. Application of logic to infer additional information is one of the key benefits of exposing the data on the Semantic Web as ``linked open data". 

The linked open data cloud has seen a steady growth since DBPedia \cite{Auer:ISWC07} project started in 2007. The DBpedia knowledge base alone currently describes more than 2.6 million things, and the knowledge base consists of 274 million pieces of information expressed in RDF triples \cite{dbpedia-info}. Some Weblog hosting sites and social networking sites have already begun exporting user profiles in to RDF \cite{rdf} using the Friend-Of-A-Friend (FOAF) vocabulary \cite{foaf}. Many other data sets have linked up to this nucleus of DBpedia data set, and to each other, effectively increasing the intelligence of the Web and supporting large scale data integration.  This allows people to use data browsers such as Tabulator \cite{tab} to surf across silos of data that have been converted into linked data.

Although much of the linked data cloud is interlinked there are many data sets that have no explicit semantic associations with each other even though these relationships might be obvious after a simple reasoning process. Once these relationships are exposed through a computation mechanism, the newly found relationships should be contributed back to the linked data cloud. This will allow reuse of these derived facts, without having to reason over the entire graph of data again. For someone who may be interested in knowing how a particular fact is derived, a proof tree detailing the derivation steps could be attached with the fact to enable provenance~\footnote{The impatient reader is encouraged to glance through~\cite{slides} or to take a look at the implementation of the User Interface given in Section~\ref{ui}.}. 

For example, in Fig \ref{fig-shortcircuit}, we have a simple linked data graph. There are several different nodes (encoded A - J), and different kinds of relations between these nodes and beyond. (One could assume that node A corresponds to the WebID of Alice, node B corresponds to the WebID of Bob, and the edge between A and B, i.e. 'rel:AB' corresponds to `foaf:knows'. Likewise, other nodes and edges in this graph can be any other entity and relationship exposed as linked data). By merely looking at this graph of data, the relationship between the triple \emph{A $ \rightarrow $ E} and \emph{H $ \rightarrow $ K} may not be obvious at a first glance. But after the application of a specific rule we might discover that there is a relationship between these two triples. Assume that the derivation path of this fact is as outlined in the red arrows where new relationships between triples are created. It would be useful to make these new relationships on the linked open data cloud persistent, so that somebody else might be able to reuse this fact later. However, to reinforce the trustworthiness of the fact that \emph{A $ \rightarrow $ E} derives \emph{H $ \rightarrow $ K} we attach the derivation steps of the proof to it. 
%This derivation path is essentially an `audit trail' outlining what data was used in coming to the conclusion that \emph{A $ \rightarrow $ E} derives \emph{H $ \rightarrow $ K}.

\begin{figure}[!h]
  \centerline{\epsfig{file=images/short_circuit.jpg, height=2in}}
  \caption{Computations on a Linked Data Cloud (\emph{Starting from the triple \{A rel:AE E\} we derive the triple \{H rel:HK K\} using the path outlined in red.})}
  \label{fig-shortcircuit}
\end{figure}

The recommended method of querying RDF, and hence extracting data from linked open data is by using SPARQL queries \cite{sparql}.  The SPARQL protocol \cite{sparql-protocol} offers a standard way to serve and access structured data on the Semantic Web. However, SPARQL queries are designed to give an answer based on a particular data set at a given end point. We envision a slightly different system where answers to specific queries are computed using a \emph{crawler based} ``Computation Agent". These answers are updated using the SPARUL protocol \cite{sparql-update} along with the method of derivation in the form of a proof using a specific attachment mechanism. This ``Computation Agent" will act on the given rule written in the N3 (Notation 3) rule language \cite{n3logic} using any given URI as a seed to start the process of crawling the linked data cloud. Once it finds information that matches the criteria specified in the rule, it will update the derived facts from the computation and the proofs associated with these facts. In summary, this project has the following components:
\begin{itemize}
\item \textbf{Computation Agent} that crawls looking for data, makes deductions and sends the result along with the proof 
\item \textbf{Light weight Server} that accepts SPARQL Update + Proof
\item \textbf{User Interface} for viewing proofs
\end{itemize}

The remainder of the paper is organized as follows:  In Section \ref{motiv} we describe the motivation behind this project and the desired features of such a system. Section \ref{usecases} illustrates few use cases that could use a computation such as the one we have implemented.  Section \ref{system} outlines the protocols used in the implementation. Section \ref{related} describes several related work from the Semantic Web world and from outside this area, especially where the inspiration for this system was drawn from. Section \ref{future-work} discusses several future directions for this project. Finally in section \ref{conclusion} we provide a summary and outlook of the overall system.

%@@ kenny, we don't want to discourage the reader from reading the paper now, do we ? ;)
%As this paper is lengthy and contains lots of details that might not be of interest to the reader, we encourage the reader to glance over the slides \cite{slides}, which contains more screenshots of the User Interface, before reading the rest of the paper.
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%% Motivation
\section{Motivation}					\label{motiv}

We find inspiration for such a system to provide solutions for maintaining the data web, particularly in creating new data, updating existing data and deleting unwanted data. We also believe attaching a proof with the derived result will make the fact more trustworthy, and hence give it a relative importance based on the number of proofs supporting the same derived fact.
%We hereby present possible reasons why we may need to drive a system such as this. 
%These are two general concepts that we have experimented so far. Since we can write N3 rules as if it were a programming language, there are countless potential applications where we could apply the same concept.

\subsection{Maintenance of the Data Web}                    \label{web-maintainace}


%We have explored two general mechanisms for updating new information and deleting old information respectively. 

%Here we consider information on the Data Web, precisely, the RDF Linked-Data Web. -- @@kenny, this is redundant!

\subsubsection{Creating New Data and Updating Existing Data:}                          \label{add-new}

The general mechanism in use for this is to use SPARQL Update \cite{sparql-update}. After new triples are generated, the `Computing Agent' sends SPARQL Update queries to `Publication Agents', such as Web servers or SPARQL endpoints~\footnote{See section \ref{update-protocol} for the technical details as to how this was achieved.}. A `Publication Agent' accepts this update query and modifies the corresponding RDF document or deny the request for update. It is relatively easy to modify pure RDF documents such as RDF/XML or RDF/N3 documents with the help of a decent serializer. But if the publication agent does not have write access, or if the documents in question are in RDFa or XML+GRDDL formats~\footnote{It's relatively hard to programmatically find the correct piece to modify in RDFa or in XML+GRDDL documents.}, the Publication Agent could send a notification to the person in charge making a change request. 

\subsubsection{Deleting Unwanted Data}                                     \label{delete-old}

%The protocol for deleting is again SPARQL Update. 
In general, we can treat the number of proofs of a triple to be the reference count of a triple, and do reference count-based garbage collection. That is, if a triple is deleted, all the proofs which has the triple as one of its antecedents should be removed. If all the proofs of a triple are removed, we delete this triple. In other words, if this triple is no longer supported by any evidence we delete it. Therefore, proofs or provenance data can help agents induce chained deletion. 

%As this is a new idea and nothing was implemented, this is idea is illustrated with pictures in the Future Work section \ref{web-gc}.

\subsection{Valuing Information}                                              \label{value-info}

Attaching proofs to a triple gives rise to a naive way of giving relative weights to the triples. I.e. by counting the number of proofs supporting that triple we can deduce the relative importance of the triple. For example, in Fig \ref{fig-explanation}, we can see that the statements like ``Illaria Liccardi is a Tabulator developer'' and ``Albert Au Yeung is a Tabulator developer'' are no longer supported with proofs, which suggests that they may be previous developers. A user who has a problem using Tabulator might not want to consult Illaria or Albert, but instead someone with a higher proof count such as KangHao Lu. We also experimented with a very controversial and a subjective example, in which we deduce \emph{smart people} by using several criteria. As a matter of practical use, if an employer wants to select the smartest people from a group, she can use our user interface and select the one with the highest number evidence supporting the fact. Another scenario is when there are contradictory information. For example, if a video on \emph{YouTube} has $x$ number of `good' ratings and $y$ number of `bad' ratings, then a user can naively compare the ratings and get a sense for the value of that video. Similarly with triples attached with contradictory proofs, we can get an estimate for the importance of the proof by naively comparing the respective `good' and `bad' proof counts.

\subsection{Desired Features}								\label{features}

Some of the desired features of the ``Computing Agent" are as follows:

\subsubsection{Never Ending Crawler:}

It needs to crawl data, generate new information, and update those information with proofs as long as data that satisfies the criteria are available. 
We imagine that in the future, people write opinions in machine readable rules. Then for example, a never ending crawler+updater would spread opinions of a person to places she doesn't even know. Notice that in this sense, crawlers+updaters are just like spamming programs. But since these crawlers+updaters also send proofs along with the data, we propose the idea of proof-based content filtering, as described in section \ref{proof-based}.

\subsubsection{Support Generalized Rules}

When the rules are general, it can be reused by others with very few modifications. For example, the rule mentioned in section \ref{chained-proofs}, can be used to give notifications to all the absent-minded people all over the world.


\subsubsection{Multilingual Information}

All the information updated by this agent, including the proofs, are in RDF. Hence it is readable by people who speak different languages. This is because at the UI level, the \emph{rdfs:label} with the correct language tag of the URIs could be displayed instead of one specific language.
% There is no limit to the Linked Open Data cloud. Therefore, the required data pertaining to a given query could be somewhere out there. Therefore we have designed our crawler to look for the required data progressively. In other words, it would not stop when a particular data item has been found.

% This part Kenny doesn't understand
% \subsubsection{Lightweight Computations}

% Lightweight computations are provided in the form of N3 rules \cite{n3logic}. These rules are used to reveal interesting relationships using publicly available linked data cloud and provides the basis for finding a resource, making an assertion, or even predict events that may happen in the future. Once a result is computed, this result is also contributed back to the linked data cloud. In essence, lightweight computations provide a mechanism for increased understanding of  unprocessed raw data without resorting to heavy-weight reasoning mechanisms which require many parameters and generated esoteric proofs.

\subsubsection{Persistence of Derived Results}

One of the major objectives of this system is that the results are made persistent for later reuse. By making these derived conclusions persistent on a read-enabled Web, we are extending the knowledge of the world. More importantly this prevents reinventing the wheel, which saves time and effort. 

\subsubsection{Provenance Preservation}

Provenance is an important metric to get an idea about where a piece of information came from, the stakeholders involved in generating that piece of information and the trustworthiness of the component data items used in deriving it. The proof entails where the data came from. Therefore, by attaching a proof to a particular data item we are preserving provenance.

% \subsubsection{Proof Abstraction}

% The proofs are attached to a data item. An intuitive user interface is used to hide the derivation path of the data items and show only the relevant pieces of information. Only when the user demands to know why a particular data item is the way it is, the proof is shown.


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%% 
\section{Use Cases}								\label{usecases}

%Sorry, Oshani, I think the use cases are kind of vague and we haven't found good reference to those described. As this is in the former part of the paper, I would prefer examples that are more concrete.

 Much of the adoption of the Semantic Web has resulted from a strong need to be able to integrate and analyze data across databases, applications, and communities. It has been fascinating to witness the breadth of solutions that have been implemented to meet these needs. In this section we outline several use cases that portray the utility of the Computation Agent that we propose.

\subsection{Support Propagation of Changes in Facts}

Rules would prove to be very useful if the pieces of data are cached or mirrored at several different places, and these rules are applied on such data automatically. For example, there used be a period when the de-facto content type of N3 was \emph{text/rdf+n3}. After some discussion, it was changed to \emph{text/n3}. This became confusing for new developers, as some user documentation still says the content type of N3 is \emph{text/rdf+n3}. If the N3 format has been given a URI and the triple \emph{\{$<$N3 URI$>$ format:content-type ``text/rdf+n3''\}} is stored with the URI and all the pages are decorated with RDFa, then, when the information changes to \emph{{$<$N3 URI$>$ format:content-type ``text/n3'}}, running the above rule on such incorrect Web pages will identify the errors, update where possible, or notify the owners for updates for documents which it cannot update.

 \subsection{Biomedical Data Analysis}

 Diverse types of data about drugs, patients, diseases, proteins, cells, pathways, and so on are already being effectively integrated on the linked open data cloud. Biomedical researchers often need to be able to ask questions that span many heterogeneous data sources in order to make well-informed decisions that may lead to important scientific breakthroughs. Once an important relationship has been found it would be very useful to other researchers to look for the result only without having to go through the burden of computing it from the beginning. Say for example, that a biomedical researcher finds out that a very specific symptom exhibited by patient X is subdued by a drug administered to him over a given period of time in a specific manner. This leads to the conclusion that the drug has an improved effectivity in fighting a certain disease. This fact obviously has some great benefit to other biomedical researchers. Of course one can issue a SPARQL query to obtain this same piece of information. However, whenever a researcher finds this fact, if he were to make an assertion and create some new data reflecting this discovery, it would relieve the others from the burden of doing the same thing over and over again. Also, for the skeptics of the effectiveness of this new derived fact of the drug, the derivation tree should be available with the data as a form of reinforcement.

 % @@ read about $http://esw.w3.org/topic/HCLS/ClinicalObservationsInteroperability/DrugMapping.html$ and add stuff

% \subsection{Employment Decision Making}

% When hiring new employees, recruiters almost always use the Web to find out more information about the candidates. Usually, this would be by looking up projects that the applicant has claimed to have worked on in the past, publications and/or articles written by that individual and anything else that might be useful in the application review process. One specific question that reviewers might have is to figure out whether a given applicant has the required programming skills in a particular language. From the linked data point of view, data about and related to the individual might be exposed on the Web as FOAF (Friend Of A Friend), DOAP (Description Of A Project), SIOC (Semantically Interlinked Online Communities) and DOAC (Description Of A Career) ontologies. Therefore, evidence that a famous hacker competent in a particular programming language knows our applicant (using \emph{foaf:knows}) or that she is a \emph{doap:developer} of a particular project that uses the said programming language  corroborates that the applicant might be competent in the programming language.  

% \subsection{Authentication}

% Why was I granted access?
% @@Complete - Kenny, can you do it?

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%% 


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%% 

\section{System Design and Implementation} \label{system}

 \begin{figure}[!h]
  \centerline{\epsfig{file=images/architecture.jpg, height=2.5in}}
  \caption{System Design}
  \label{fig-design}
\end{figure}

The design of the current implementation is given in Fig \ref{fig-design}. The `Computation Agent' includes a `Rule Engine' based on CWM (Closed World Machine) \cite{cwm} and an `Updater' which supports SPARQL updates. The User Interface is implemented on the Tabulator.

%About CWM
% This is a program that can parse and serialize RDF in several formats including RDF/XML, Notation3, and NTriples, stores triples in a queryable triples database, perform inferences as a forward chaining First Order Predicate Logic inference engine. It can also be used to perform built-in functions such as comparing strings, retrieving resources using an extensible built-ins suite.

% @@ check $ /afs/csail.mit.edu/group/dig/www/data/2009/tms_web/social_computing.py $

\subsection{The Proof Vocabulary and Structure}

Proof visualization relies upon the proof vocabulary which follows from the `Truth Maintenance System \emph{(tms)}' vocabulary developed by the TAMI project~\footnote{The current proof vocabulary may be revised in the future to make the proofs less verbose, and more human readable. However, even if the vocabulary changes, the changes expected in our system are at a bare minimum, and we expect the client implementation to be backwards compatible. (Project URI: \url{http://dig.csail.mit.edu/TAMI/ })}. In order for Tabulator to understand the proof to render we use the following proof structure. This is highly customizable, and we envision support for languages such as Proof Markup Language (PML) \cite{pml} in the future.

\begin{verbatim}
@prefix tms: <http://dig.csail.mit.edu/TAMI/2007/amord/tms#> .
@prefix doap: <http://usefulinc.com/ns/doap#> .
@prefix doac: <http://ramonantonio.net/doac/0.1/#> .
@prefix swe: <http://dig.csail.mit.edu/2009/06/software_engineering#> .
@prefix ken: <http://dig.csail.mit.edu/People/kennyluck#> . 

{ ken:I doac:skill "Javascript" . } #subject, the conclusion in formula
   tms:justification #predicate 
   [ #object, a bnode
      tms:antecedent-expr  [ 
         a tms:And-justification; #a bnode of And-justification
         tms:sub-expr swe#doap2doac-skill , #the ruleURI is optional
            { #the antecedents in formula
               <http://dig.csail.mit.edu/2005/ajar/ajaw/data#Tabulator> 
                  doap:developer ken:I;
               doap:programming-language "Javascript" .
            } 
      ] 
   ] .
\end{verbatim}

The proof given above constitutes two formulae, namely the conclusion and the antecedent, two blank nodes, and effectively 5 triples. This is written using Turtle+Formula syntax, which is a subset of the full N3 allowing formulae or graphs, to be subjects or objects~\footnote{As specified in the Design Issues Note for N3. See \url{http://www.w3.org/DesignIssues/diagrams/n3/venn}}. The client store of the proof visualization UI is required to support formulae as subjects or objects, but some of the full N3 constructs such as variables and quantification are not needed.

\subsection{The Proof Update Protocol for the Computing Agent} \label{update-protocol}

The update protocol is adapted from the SPARQL Update protocol as described in the Tabulator-Redux \cite{tab}. This includes sending SPARQL queries via HTTP POST with the MIME type ``application/sparql-query". For example, the following code snippet illustrates the update of the triple which says that the person identified by the URI $<$\url{http://dig.csail.mit.edu/People/kennyluck#I}$>$ has Javascript skills.

\begin{verbatim}
POST /path-of-updatable-document HTTP/1.1
Content-Type: application/sparql-query

PREFIX ken <http://dig.csail.mit.edu/People/kennyluck#> .
PREFIX doac <http://ramonantonio.net/doac/0.1/#> .
INSERT { ken:I doac:skill "Javascript" . }
\end{verbatim}

A consistent extension of SPARQL Update should allow subjects and objects to be graphs or formulae~\footnote{See Section \ref{future-work} for a more comprehensive discussion on this.}. But SPARQL Update is not standardized and widely adopted yet. Therefore, we chose the following workaround in order to reduce the amount of work on the SPARQL Update server by introducing an additional HTTP Header called `X-Meta':

%#no percent encoding -- @@kenny, what does this mean? anyways, we shouldn't have comments inside the code snippets in the paper. better to describe those in the text of the paper.

\begin{alltt}
POST /path-of-updatable-document HTTP/1.1
Content-Type: application/sparql-query
\textcolor{blue}{\textbf{X-Meta: http://dig.cail.mit.edu/proof-tmp-storage/3deDQp}}

PREFIX ken <http://dig.csail.mit.edu/People/kennyluck#> .
PREFIX doac <http://ramonantonio.net/doac/0.1/#> .
INSERT \{ ken:I doac:skill "Javascript" . \}
\end{alltt}

This means that we give the SPARQL Update server a URI link to the generated temporary proof. Notice that one disadvantage of this is that the computing agent has to have the power to write on the Web. As a multi-threaded application, the agent sends the data along with a pointer to the proof as long as a deduction is made. In the mean time, the crawling threads will be continuously fetching more data on the Web.

%Server side code:
%$ /afs/csail.mit.edu/group/dig/www/data/2007/wiki/_get.php and /afs/csail.mit.edu/group/dig/www/data/2007/wiki/_post.php $

\subsection{Providing Proofs from a Server and Retrieving Proofs from a Client}

The current proof providing mechanism uses the standard HTTP content negotiation protocols. If the client store has the ability to store triples with formula subject or object, when fetching a document, the client's HTTP Accept header contains the content type representing the N3 format, namely \emph{text/n3}, the server sends a big document containing proofs of some of the information in the document. If the client store only does flat RDF, the server sends a small document, with all the proofs removed from the big document.
The proposed mechanism of proof transfer uses extra HTTP header as follows:

%The first author believes all information should be sent along with the proofs, while the last author believes data and proofs should be separated into different files. 

\begin{alltt}
GET /data-file HTTP/1.1

HTTP/1.1 200 OK
\textcolor{blue}{\textbf{Link: http://dig.csail.mit.edu/meta-file-for-data-file}}

<data-file-content>
\end{alltt}

The `Link' header points to a meta file of the data file containing the information about the data file, and the client can fetch the meta file afterwards. The advantage of this approach is that it preserves the integrity of the data file. %@(optional)illustrate with the recovery.gov use case, or ask Tim
Notice that the Link header is not yet standardized and as far we know, no existing HTTP server uses this mechanism yet. It is also not implemented in our system yet. 

\subsection{User Interface}								\label{ui}

\subsubsection{Simple Proofs}

\begin{figure}[!h]
  \centerline{\epsfig{file=images/triples_with_explanation.jpg, height=3in}}
  \caption{User Interface Showing the Existence of Proof}
  \label{fig-ui}
\end{figure}

Fig \ref{fig-ui} shows what the user interface of the system looks like on Tabulator. The `question mark' symbol indicates that there is a proof associated with the corresponding triple. It is expected that the user will click on this icon and explore the proof using Tabulator's `Justification UI'.  The \textcolor{red}{x n} next to the question mark symbolizes how many proofs that particular triple has. Higher the number, more proofs supporting this particular triple, and hence more trustworthy the fact represented by the triple becomes.

\begin{figure}[!h]
  \centerline{\epsfig{file=images/timbl_tab_devloper.jpg, width=1\linewidth}}
  \caption{User Interface on Tabulator Showing the Reasons behind the Conclusion Given}
  \label{fig-explanation}
\end{figure}

Once the question mark icon is clicked the justification of that particular triple will be displayed as shown in Fig \ref{fig-explanation}. In this particular example, the user has clicked the question mark icon next to the triple which says `Timothy Berners-Lee' is a `Developer' of the Tabulator project given in Fig \ref{fig-ui}. The justification of this fact consists of recent commits that he has done to the Tabulator version control system. Reason 1 of the justification gives a particular commit revision of which `Timothy Berners-Lee' is the creator of, and so on.

\subsubsection{Chained Proofs}                                                  \label{chained-proofs}

\begin{figure}[!h]
  \centerline{\epsfig{file=images/scenario.png, width=7in}}
  \caption{Example of a Scenario which involves several Chained Proofs}
  \label{fig-scenario}
\end{figure}

Our system is capable of handling proof chaining as well. Let us illustrate this with a simple example. Suppose there are few rules as follows:
\begin{itemize}
\item If a person commits to a project, that person must be a developer of the project.
\item If a person is a developer of a project and that project uses a programming language Y. Then that person must have the skill of programming in Y.
\item If a person made a document, which lists some information but not complete, and there are some new information about a fact in the document, then that person should update the document.
\end{itemize}
The `should' information in the last rule is encoded in the form of a RSS feed. Therefore once the last rule is fired, this feed would be sent to the person's personal RSS reader. Notice the fact that an RSS 1.0 channel is also a valid RDF/XML document. The scenario, as experienced by the user, is illustrated in Fig \ref{fig-scenario}:

\begin{enumerate}
\item Our user will see that there is an event called ``TODO: You should update the document". 
\item Once he clicks on it, he will see all the information associated with it in the Tabulator outline view. Further, he notices that some of the triples have some derivations (question marks along with the triples).
\item He clicks on the question mark for the triple \emph{$<$the event$>$ handler `KangHao Lu'}, and sees more information on the justification UI. This gives the reasons for why he is the handler of the event. This includes 5 facts. These facts are stacked in the order of derivation (and thus reads from bottom to top). The first fact indicates that KangHao Lu's CV has a particular URI. The second fact says that the CV includes a `skill' category. The third fact indicates that these skills do not include `Javascript'. The fourth fact says that the creator of the CV is KangHao Lu, and the final fact says that KangHao Lu is skilled in Javascript. Notice that there is a question mark next to the last triple.
\item Once you click on the question mark to learn why `KangHao Lu' has skills in Javascript, the proofs for that is appended. In this case it happens to be that he is a developer of Tabulator, and the primary programming language used in Tabulator is Javascript. There is again a question mark next to the triple \emph{Tabulator developer `KangHao Lu'}. By clicking on that, we learn the proof for this fact. in this case, it happens to be that `KangHao Lu' has committed to the Tabulator project.
\end{enumerate}

The last rule of this chain of deduction is implemented with the following simplified N3 rule:

%@@I want to give this a header like "Rule 4.1" or something, does \begin{theorem} help?

%\textbf{Rule 1}

\begin{alltt}
@prefix log: <http://www.w3.org/2000/10/swap/log#> .
@prefix doape: <http://dig.csail.mit.edu/2007/wiki/doapextension#> .

@forAll :subject, :predicate, :object .
\{   ?document dc:creator ?person .
    :subject :predicate :object .
    ?document log:semanticsIncludes \{ :subject :predicate [] . \} .
    ?document log:notSemanticsIncludes \{ :subject :predicate :object .\} . \}
=>
\{   [ a     rss:item;
      rss:title "TODO: You should update the document";
      doape:handler ?person;
      doape:relatedSource ?document ] . \}.
\end{alltt}

This rule means that if a document has the triple \emph{``\{\ s \} \{ p \} \{ o1 \} .''}, but does not have the triple \emph{``\{ s \} \{ p \} \{ o2 \} .''}, which we assume is available at another source, then the creator of this document is responsible for making this modification and a notification for an RSS item is generated. 


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%% Related Work

\section{Related Work}								\label{related}

AIR ({\bf A}ccountability {\bf I}n {\bf R}DF) \cite{air} a policy language that exploits a dependency tracking approach to generate proofs with quasi-natural language explanations for a given policy and a log file. AIR policies are represented in Turtle~\cite{beckett04turtle}, which is a human readable syntax for RDF, and include the quoting feature of N3Logic~\cite{n3logic}. AIR consists of an ontology and a reasoner, which when given a set of policies and data in Turtle, attempts to compute compliance of the data with respect to the policies.  Each computed compliance result has an associated explanation in Turtle outlining the derivation of the result from the inputs. The AIR reasoner is only capable of generating a proof at a document level, but not at the triple level. Also, it does not have the capabilities to update a corresponding file as in our method.

Proof Markup Language (PML) is a general proof language or ``proof interlingua" that is used to describe proof steps generated by different kinds of reasoning engines. Inference Web (IW) provides a framework for displaying and manipulating proofs defined in Proof Markup Language (PML)~\cite{mcguinness04iw}.  IW concentrates on displaying proofs whereas our approach is for both generating and displaying proofs. We also allow chaining of proofs so that they can be explored recursively.

Although it is outside of the domain of Semantic Web, we can draw a strong analogy between our work and the the work done by Bill Lewis on the Omniscient Debugging concept \cite{lewis-2003}. Omniscient Debugging is the idea of collecting ``time stamps" at each ``point of interest" (setting a value, making a method call, throwing/catching an exception) in a program and then allowing the programmer to use those time stamps to explore the history of that program run. Similar to his idea, our ``Social Computing Agent" performs computations and at a particular ``point of interest" generates a useful triple and updates the document where the triple fits along with the proof of how it was derived. 

SPARQL queries currently support for querying multiple graphs. Quilitz et al~\cite{darq} describe an optimized method for querying distributed RDF data sources with SPARQL using their DARQ\footnote{http://darq.sf.net} implementation. Schenk et al~\cite{simon} describe a way for linking user generated content on the Semantic Web. Yars2 (Yet Another RDF Store, Version 2)~\cite{yars2} presents an end-to-end semantic search engine that uses a graph data model to enable interactive query answering over structured and interlinked data collected from many disparate sources on the Web. Zhao et al~\cite{JunZhao03012009} describe various design patterns for representing and querying provenance information relating to mapping links between heterogeneous data from sources in the domain of functional genomics. Their work illustrates the use of named RDF graphs at different levels of granularity to make provenance assertions about linked data. It also demonstrates that these assertions are sufficient to support requirements including data currency, integrity, evidential support and historical queries. While all the work mentioned above are analogous to the work we have done in gathering information from several sources, our `Computation Agent' is able to find information that matches as long as such information is available. In addition, all of those works described above do not  support SPARQL updates.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%% 
\section{Future Work}								\label{future-work}

We envision SPARQL/Update to be the most important communication protocol in the future.
%, attached proofs as why or how this piece of information is generated, there are countless potential future works. 
Here we briefly list some of the future work we consider interesting.

\subsubsection{Proof-based Content Filtering:}                       \label{proof-based}

Different from normal machine learning-based content filtering schemes, which are more of less based on heuristics, SPARQL Update + Proofs provides a logical way of content filtering. We can implement a SPARQL Update receiver agent that validates proofs or checks whether the rule generating this new information is in its white list of rules. As rules have URIs and are part of the Linked Data, meta information of rules allows the agent to do more things, for example, building the white list of rules from rules that have more than certain number of supporters.

SPARQL Update + Proofs is machine readable, traceable and multilingual. We believe it has the potential of replacing email in certain circumstances, for example in sending bug reports.

\subsubsection{Linked Data Garbage Collector(s):}                  \label{web-gc}

Consider the following example which was briefly described in Sec \ref{web-maintenance}:

\begin{figure}[!h]
  \centerline{\epsfig{file=images/Linked_Data_GC.pdf, width=1\linewidth}}
  \caption{Phases of a Linked Data GC example}
  \label{GC-phases}
\end{figure}

Node A is the statement ``Kenny is a member of the DIG group'', Node B is ``Kenny is a developer of Tabulator'', Node C is ``Kenny has the access right to the Tabulator repository'' and the links represent the proofs. In the first phase, the statement ``Kenny is a member of the DIG'' is deleted, so in the second phase the proof that has Node A as an antecedent is also deleted. But at this point, Node C is still supported by a proof and hence remains existing. During the last phase, all the proofs of Node C, the statement ``Kenny has the access right to the Tabulator repository'', are no longer existing. Therefore we can remove this statement.

As Web is a decentralized system and there are a lot of information getting deleted at a particular time, the Web incorporated with this system can be imagined as a huge memory space with lots of garbage collectors. Few technical challenges remain:
\begin{enumerate}
\item Should servers or crawler clients send these removing notifications? Maybe both?
\item How does this system deal with cyclic dependency?~\footnote{This is also a well known problem in programming GC.}
\end{enumerate}

\subsubsection{Mechanism and User Interface for Grading Triples:}

As pointed out in section \ref{value-info}, the current implementation of user interface displays values of triples by naively counting the number of proofs. More grading algorithms should be created and provided to the end user in a customizable way. A a simple next step would be grading a proof with numbers of supporters of the corresponding rule. Google's Page Rank is also a possibility, namely strong statements proves strong results. However, it requires collaboration of different servers.

%A simple next step, as pointed out by an attendant at the Cambridge Semantic Web Gathering \cite{slides}, would be grading a proof with numbers of supporters of the corresponding rule. Google's Page Rank is also a possibility, namely strong statements proves strong results. It requires collaboration of different servers though.

\subsubsection{Other future works include:}

\begin{itemize}
\item Extend SPARQL Update consistently to include updating formulae or graphs
\item Implement the HTTP Link Header both on the server-side and the client-side
\item Visualization for statements with cyclic dependency
\item Upgrade Computing Agent with support for more rule formats, Including AIR~\cite{air} and RIF~\cite{rif}
\end{itemize}


% Proper SPARQL update semantics to update graphs instead of triples

% \begin{verbatim}
% GRAPH data.n3 INSERT {<s> <p> <o>}
% GRAPH proof.n3 INSERT {proof graph}
% \end{verbatim}

% For triples that have more than one proof display the relative weights - how to measure the importance of it



%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%% 
\section{Conclusion}								\label{conclusion}

The ultimate vision of the Semantic Web is to make it an immortal brain where the computers work as if they were neurons~\cite{semweb}. Before wikis and blogs became popular, the Web had been basically a read-only medium and the machines did not resemble anything close to communicating neurons. This is perhaps due to the fact that HTML is not flexible enough for updating. This project investigated methods and protocols for updating the ``Data Web", a Web with RDF as it's main data format. We described some protocols for achieving this. All these decisions are far from being standardized. Therefore, they are subject to change, but we expect later versions of the current implementation to be backwards compatible. The never ending crawler and updater demonstrates that the Web can be designed to think and learn by itself. The garbage collecting paradigm, as described in section \ref{web-gc}, demonstrates a reasonable way in which certain parts of the Data Web could be programmed to forget. We believe that proofs on the Web will eventually weave into a Truth Maintenance System and that updating the proofs back to the Data Web will be a key point for achieving the Web Intelligence.

%Kenny, um, seriously, I don't think this is really needed!
%\section*{Acknowledgements}
%The first author wants to thank the last author for introducing him the concept and power of URI, RDF and the new world. This project does not yet have any funding.

\bibliographystyle{abbrv}
\bibliography{paper-reference}


\end{document}
