\documentclass{llncs}
\usepackage{url,color,floatflt}
\usepackage{fancyvrb,relsize,url,graphicx,epsfig}

\setlength{\abovecaptionskip}{0pt}
\setlength{\belowcaptionskip}{0pt}

\addtolength{\oddsidemargin}{-.3in}
\addtolength{\evensidemargin}{-.3in}
\addtolength{\textwidth}{.6in}

%\addtolength{\topmargin}{-.875in}
%\addtolength{\textheight}{1.75in}

% to fix the line wrapping issue
\sloppy

\DefineVerbatimEnvironment%
   {VerbatimN3}%
   {Verbatim}%
   {fontsize=\scriptsize, xleftmargin=0.25in}
\DefineVerbatimEnvironment%
   {VerbatimScript}%
   {Verbatim}%
   {fontsize=\scriptsize}

% comment out a section
\long\def\comment#1{\relax}

% qname
\newcommand{\qname}[1]{\texttt{#1}}

% something to do with air
\newcommand{\air}[1]{\textbf{\textit{#1}}}

% something to do with rdf/n3
\newcommand{\rdf}[1]{{\bf #1}}

% Put remarks in the paper easily located by ``bigodot'' in margin
% Usage: \todo{twf: we need a better example here.}
\newcommand{\todo}[1]{
\mbox{}\marginpar[\hfill$\bigodot$]{$\bigodot$\hfill}
{\sc#1}}
%\newcommand{\todo}[1]{{\bf TODO:} #1}

%% ISWC 2010 Research Track
%% http://iswc2010.semanticweb.org/node/8

\begin{document}

\title{Gasping for AIR -- Why we need linked rules and justifications
  on the Semantic Web\thanks{\small This work was supported in part by
    NSF Cybertrust award number CNS-0831442, IARPA award number
    FA8750-07-2-0031 and AFOSR award number FA9550-09-1-0152}}

\author{Lalana Kagal\inst{1} \and Ian Jacobi\inst{1} \and Ankesh
  Khandelwal\inst{2}}

\institute{MIT CSAIL \\
Cambridge, MA 02139 \\ 
\email{ \{lkagal, jacobi\}@csail.mit.edu}
\and
Rensselaer Polytechnic Institute \\
Troy, NY 12180\\
\email{ankesh@cs.rpi.edu}
}


\maketitle
%\todo{think about new title}


\begin{abstract}


The Semantic Web is a distributed model for publishing, utilizing and
extending structured information using Web protocols. One of the main
goals of this technology is to automate the retrieval and integration
of data and to enable the inference of interesting results. This
automation requires logics and rule languages that make inferences,
choose courses of action, and answer questions. The openness of the
Web, however, leads to several issues including the handling of
inconsistencies, integration of diverse information, and the
determination of the trustworthiness of data. \comment{The goals of
  Web rule languages should, therefore, include localizing
  inconsistencies, extracting relevant information from Web resources,
  tracking information sources, and maintaining detailed provenance
  information.} AIR is a Semantic Web-based rule language that
provides this functionality while focusing on generating and tracking
explanations for its inferences and actions and conforming to Linked
Data principles.  AIR supports \air{Linked Rules}, which can be
combined and re-used in a manner similar to Linked Data. Additionally,
AIR explanations themselves are Semantic Web data so they can be used
for further reasoning.  In this paper we present an overview of AIR,
discuss its potential as a Web rule language by providing examples of
how its features can be leveraged for different inference
requirements, describe how justifications are represented and
generated, and present an overview of AIR semantics.


\end{abstract}

\section{Introduction}
\label{sec:intro}

\comment{Semantic Web technologies enable the publication, processing and
analysis of structured data on the Web. }

Though RDF Schema (RDFS) and the Web Ontology Language (OWL 1 \& 2)
provide some reasoning capability over Resource Description Framework
(RDF) data, the application of Semantic Web technologies to
e-government, business, policy management, workflow systems, and many
other fields requires more expressive rule languages to capture the
underlying system logic.  \comment{Along with taking advantage of
  Semantic Web technologies, these rule languages need to also address
  problems that arise from the openness of the Web.}  Much of the
Semantic Web's growth today has been in the form of Linked Data, which
means that any Web rule language must be able to handle highly
interconnected and spatially dispersed data.  It must be able to
dynamically traverse this web of data to find additional facts to
support the conclusions of its reasoner. Furthermore, a Web rule
language should expose its rules as Linked Data as well so that they
can be re-used and combined in a similar manner. \comment{Furthermore,
  due to the annotation of resources with links to other resources as
  Linked Data, any Semantic Web rules language should ideally expose
  the rules as Linked Data as well.  This also may allow such rule
  languages to define rules recursively, so that they may depend on
  other rules elsewhere on the web of Linked Data.}

%\todo{Not sure how to express trustworthiness, as we don't really
%  refer to it elsewhere in the paper.}

Web rule languages must be able to cope with the problems that arise
from the inherent openness of the Web. Reasoning over data on the Web
can easily lead to logical inconsistencies as anyone can assert
anything. For example, a reasoner could infer multiple subjects for
the same value of an \rdf{Inverse Functional} property,
\rdf{foaf:mbox\_sha1sum}\footnote{\url{http://xmlns.com/foaf/spec/#term_mbox_sha1sum}},
caused by the incorrect copying of someone's Friend of A Friend (foaf)
page, leading to a logical inconsistency. A Web rule language must be
able to isolate the results of reasoning~\cite{polleres06ruleswith} to
prevent them from causing inconsistencies in the global state.
Another problem with Web systems involves the trustworthiness of data
--- what data to trust and what criteria to use for this
decision. Different Web documents may be trusted with assertions about
different data but not all data they contain. For example, a hospital
site may be trusted with information about a potential virus outbreak
but may not be trusted with respect to its inflation predictions. The
ability to access only trusted RDF subgraphs from Web pages is useful
in maintaining the quality of inference results. In order to trust
inference results, deduction traces, or justifications as they are
known, are also required~\cite{horridge08laconic,kagal08using}.  They
provide detailed provenance information, including the data sources
and the rules applied, to allow applications to evaluate the
trustworthiness of a particular result through automated proof
checking~\cite{bauer05distributed,kolovski05towards}. Capturing and
tracking this provenance information is another important property of
Web rule languages.

\comment{AIR is a Semantic Web rule language that provides these
  features while conforming to linked data principles. It also extends
  RDF with named rules, graphs and quantified variables as well as
  with functions for accessing Web resources, querying SPARQL
  endpoints, and for cryptographic, string, and math operations.  AIR
  rules are part of the Linked Data Cloud so they can be reused easily
  and can be developed modularly. AIR has two independent ontologies
  --- one for defining rules that infer new RDF data and the second
  for defining justifications associated with each inference.  In this
  paper we present an overview of AIR, discuss its potential as a Web
  rule language by providing examples of how its features can be
  leveraged in different application domains, and present an overview
  of its semantics.  }

AIR ({\bf A}ccountability {\bf I}n {\bf R}DF) is a Semantic Web rule
language that provides these features. It is represented in N3 and
supports named rules, graphs, quantified variables and functions for
accessing Web resources and SPARQL endpoints, and for cryptographic,
string, and math operations. It also includes functions for
objectively retrieving subgraphs from Web resources as well as
functions for scoped contextualized reasoning.

AIR also provides \air{Linked Rules}. Most rules, whether laws,
security policies, business rules, or workflow plans, are rarely
defined by a single entity or exist in a single document. They usually
comprise of several rules that are defined and maintained by different
entities. For example, a University policy depends on concepts and
rules defined by the HR department, the different schools, as well as
the labs within the schools. Additionally, rules often reference other
rules, including those of other organizations. As an example, a
hospital might want to know with whom a pharmaceutical company might
share patient records it provides and might want to reason over the
latter's rules before transferring patient information. AIR models
this rule re-use and linkage by (i) enabling rules to be uniquely
identified by Uniform Resource Identifiers (URIs) such that they can
be spatially dispersed but combined during reasoning, (ii) allowing
rules to be developed modularly using existing rules, and (iii)
allowing rules to be executed from within other rules and their
results to be queried. This conformance of AIR rules to Linked Data
principles forms the basis of \air{Linked Rules} that provide a more
natural way to think about and model real world rules, laws and
policies on the Web.

AIR has been used in various projects to meet different rule-based
inferencing requirements.  It has been used for controlled information
exchange in information sharing
environments\footnote{http://dig.csail.mit.edu/2009/DHS-fusion/} where
contextualized reasoning was very important. It has been used to
secure access to Web resources~\cite{auyeung09providing} and SPARQL
endpoints~\cite{cherian10www} based on the credentials of the
user. AIR has also been used to analyze database
queries~\cite{kagal10ppssi} with respect to privacy policies that
required ontology-based reasoning, the querying of large knowledge
bases for factual information and expressive non-monotonic
reasoning. Lastly, AIR has been used in accountability mechanisms for
processing audit logs and looking for data usage outside of what was
allowed by data usage policies~\cite{weitzner08cacm}. All of the above
projects made use of justifications, for deductions by the reasoner,
for debugging and accountability purposes.

This paper is structured as follows: we start by describing a
motivating scenario in Section~\ref{sec:usecase} before providing an
overview of the AIR language in Section~\ref{sec:air}. In
section~\ref{sec:justifications}, we discuss AIR's support for
justifications --- how they are generated and the representation
schema.  The next section, Section~\ref{sec:semantics}, deals with an
overview of the procedural and declarative semantics of AIR followed
by a comparison to related work in Section~\ref{sec:related}.  We
conclude the paper with a summary and directions for future work in
Section~\ref{sec:summary}.


\section{Motivating Use Case}
\label{sec:usecase}

To better understand how AIR's features may be used to solve complex
problems, consider the following hypothetical scenario: Maury conducts
genomic research at BigPharma, a pharmaceutical company. As part of a
larger effort by BigPharma to develop new therapies for diseases of
the lung, BigPharma has established a partnership with a number of
hospitals including BigCity Hospital. The purpose of this relationship
is to obtain the responsiveness of patients with certain disease
expressions to particular medications. \comment{BigPharma believes
  that this information is critical to designing novel drugs based on
  the newly minted organ response research.} Maury performs a
federated search over the SPARQL endpoints of these hospitals for
patient response information.

BigCity receives this request but the information cannot be simply
given to Maury, as BigCity, like all hospitals, restricts how patient
information may be disseminated to third parties. Here, BigCity must
determine whether or not dissemination of the requested patient
information to Maury would violate any of its rules. \comment{Ideally,
  we should be able to encode these rules in a Web rule language and
  then use a reasoner to determine whether such dissemination is
  possible.}

BigCity's rules state that patient information may only be
disseminated to requesters from ``pharmaceutical collaborators''.
\comment{For Maury to be able to receive the information, it must be
  possible to prove that Maury is a member of a ``pharmaceutical
  collaborators''.} Since Maury's credentials need to be verified by
information on a particular SPARQL endpoint maintained by BigPharma,
whatever language we implement must be able to query SPARQL endpoints
and incorporate the results of queries into its rules.  In this way,
Maury may be determined to truly be a member of BigPharma, a
pharmaceutical collaborator. Other rules might require patients to
have consented to share their information and might need to query
another SPARQL endpoint for this information.

Determining Maury's affiliation is not entirely sufficient for BigCity
to send the data.  Maury must also be able to prove that he is
authorized to act in an appropriate role as defined by another BigCity
rule.  This rule defines role-based access control (RBAC) rules for
all BigCity employees and states that only ``Principal Researchers''
can access patient response information. The rule also reasons over
ontology mappings of collaborators. Maury must be able to prove that
he is employed at BigPharma in a role equivalent to BigCity's
``Principal Researcher''. As the definitions in the RBAC rule are used
in multiple rules, BigCity should be able to encode it as a separate
rule which may be invoked from other rules.  In practice, a rule
language that satisfies BigCity's needs should be \textit{recursive}.

Unfortunately, Maury is not working in an appropriate role and is
denied access to the information.  Although it is entirely possible
that BigCity would not desire that Maury know why he was denied access
in the first place, Maury may benefit from knowing exactly why he was
not shown the material he requested.  Thus, the rule language used
should be able to encode and present justifications that correspond to
the logic used.  With such a justification, Maury will be able to
determine not only how the decision against access was made, but he
will also be able to verify the correctness of this determination.

\section{AIR Overview}
\label{sec:air}

AIR is an extension to N3Logic~\cite{n3logic} and has been structured
to meet the justification and reusability requirements of Web
information systems. Along with including the N3Logic features of
scoped negation, scoped contextualized reasoning, nested graphs, and
built-in functions, AIR also supports \air{Linked Rules} and is
focused on generating useful \air{justifications} for all actions made
by the reasoner. Like N3Logic, AIR is written in
N3\footnote{http://www.w3.org/DesignIssues/Notation3.html}, which
provides a human-readable syntax for a superset of RDF.  N3 extends
the RDF data model by allowing for the quantification of variables as
URIs with the \rdf{@forAll} and \rdf{@forSome} directives.  It also
permits the inclusion of nested graphs by using curly braces to quote
subgraphs.

AIR is made up of a set of built-in functions and two independent
ontologies --- the first is for the specification of AIR rules, and
the second deals with describing justifications for the inferences
made by AIR rules. The built-in functions allow rules to access Web
resources, query SPARQL endpoints, and perform scoped contextualized
reasoning, as well as basic math, string and cryptographic
operations. While developing the rule ontology, we focused on
capturing how real world rules and laws are written to allow them to
be represented naturally in AIR. For the justification ontology, our
focus was on re-usability of justifications and on automated proof
checking. When given as input some AIR rules, defined in the AIR rules
ontology, and some Semantic Web data, the AIR reasoner produces a set
of inferences that are annotated with justifications, described in the
justification ontology. The runtime input to AIR rules can be any RDF
graph or an empty graph, if the rules only access Web resources.

All the examples in the paper are in N3. Please refer to
\url{http://www.w3.org/2000/10/swap/Primer} for an overview of N3 and
to the Appendix for the list of namespaces used in the paper.


\subsection{AIR Rules}
As illustrated in Figure~\ref{fig:ont}, AIR rules are defined using
the following properties: \air{air:if}, \air{air:then},
\air{air:else}, \air{air:description}, \air{air:rule} and
\air{air:assert}. Every rule is named with a URI, and they are grouped
into \air{air:RuleSets} or nested under other rules. This nesting can
happen either under the \air{air:then} property or the \air{air:else}
property. The rules nested directly under the \air{RuleSet} are
referred to as the top rules of the ruleset. \comment{The rules (child
  rule) nested under another rule (parent rule) via the
  \air{air:then.air:rule} property chain is said to be positively
  nested and that nested via an \air{air:else.air:rule} chain are said
  to be negatively nested.} A chain of rules is defined as a sequence
of rules, such that every rule, barring the first in the chain, is
nested under either the \air{then} or the \air{else} of the preceding
rule.  Figure~\ref{fig:rules} provides an example of nested rules. In
this case, \texttt{:CheckCollaboratingPharma} only becomes active if
the \air{air:if} of the parent rule, \texttt{:CheckQueryRule}, matches
a pattern in the knowledge base.  On the other hand,
\texttt{:NonCollaboratorRequestProcessing} becomes active when the
\air{air:if} of its parent rule fails.

\begin{figure}[!t]
\begin{center}
\includegraphics[width=5.3in]{images/air-ont.jpg}
\end{center}
\caption{{\bf AIR Rule Ontology}}
\label{fig:ont}
\end{figure}



There are three kinds of rules in AIR --- \air{air:Belief-rule},
\air{air:Hidden-rule} and \air{air:Elided-rule}. All rules are, by
default, \air{Belief-rules}.  The descriptions and conditions of
\air{Belief-rules} contribute to the overall
justification. \texttt{:CheckQueryRule} in Figure~\ref{fig:rules} is
an example of a \air{Belief-rule}. In contrast, \air{Hidden-rules} and
\air{Elided-rules} are used to modify the default
justification. (Please refer to Section~\ref{sec:justgen} for more
information about justification generation and modification).



The conditions of a rule (for example, \rdf{:REQUEST a
  ex:Patient\_Record\_Request} in Figure~\ref{fig:rules}) are defined
as graph patterns which are matched against RDF graphs, similar to the
Basic Graph Pattern (BGP) of SPARQL queries\footnote{\url{
    http://www.w3.org/TR/rdf-sparql-query/#BasicGraphPatterns}}.  If
the condition matches the current state of the world, defined as the
facts known or inferred to be true so far, then all the actions under
\air{then} are fired, otherwise all the actions under \air{else} are
fired. The condition matches the current state if there is a subgraph
of known facts that matches the graph pattern. This subgraph is
referred to as the matched graph.

Existentially quantified variables may be declared within graph
patterns by using the \rdf{@forSome} directive. Any universally
quantified variables, quantified using \rdf{@forAll}, are declared
outside of the rule. The scope of a existentially quantified variable
is the graph pattern in which it is declared, whereas that of a
universally quantified variable is any chain of nested rules.

Rules with conditions where some graph pattern must match the current
state and others should not match the current state can be specified
through the nesting of rules. The actions under \air{then} and
\air{else} (together referred to as actions) are defined by an
assertion pattern using the \air{air:assert} property, or a rule
reference, using the \air{air:rule} property.  All actions may be
annotated with the natural-language description of the rule or action
through the use of the \air{air:description} property.

\begin{figure}[!t]
\begin{VerbatimN3}
@forAll :REQUEST, :R, :CRED, :C, :G, :SE.

:BigCityDissemination a air:RuleSet;
    air:rule :CheckQueryRule.
:CheckQueryRule a air:Belief-rule;
    air:if {
        :REQUEST a ex:Patient_Record_Request;
                 ex:requester :R;
                 ex:credentials :CRED.               
    };
    air:then [ 
	air:description ("Received patient record request, " :REQUEST " from " :R ".");
        air:rule :CheckCollaboratingPharma ;
    ].
:CheckCollaboratingPharma a air:Belief-rule;
    air:if {
         :CRED log:semantics :C.
         :C log:includes { :G foaf:member :R }.
         :BIGCITYDB log:includes { :G a ex:CollaboratingPharma ; 
                                      ex:sparqlendpoint :SE. }.            
    };
    air:then [
        air:description ( :REQUEST " might be from collaborating
        pharmaceutical company, need further verification from their sources.");
        air:rule bcc:CollaboratorRequestProcessing ] ;
    air:else [  air:rule  bnc:NonCollaboratorRequestProcessing ].
\end{VerbatimN3}
\caption{{\bf Example AIR RuleSet:} Following from the motivating use
  case, this rule checks if the request is from a collaborating
  pharmaceutical company. Maury's credential identifies his
  organization and BigCity checks whether it is a collaborating
  partner and if so, identifies its SPARQL endpoint. The input also
  includes the RDF graph of Maury's request, described at
  $<$http://bigcity.example.com/record\_request\_log.n3$>$ }

\label{fig:rules}
\end{figure}


When the action is executed, the variables in an assertion pattern
(for example, the variable \qname{:CRED} in Figure~\ref{fig:rules})
are substituted by their bindings and the pattern is asserted. If a
rule reference is defined instead, an instance of that rule, created
by substituting the variable bindings acquired so far, is
activated. The variables in any \air{air:description} property are
also instantiated, and the description is maintained by the reasoner.


\comment{All actions may be annotated with the natural language
  description of the rule or action through the use of the
  \air{air:description} property. The rule to be activated is declared
  through the \air{air:rule} property, and the graph pattern to be
  asserted is declaring using the \air{air:assert} property.}

Any asserted graph pattern cannot contain blank nodes or existentially
quantified variables.  When a rule containing an \air{air:else}
property is activated, its condition cannot contain unbounded
universally quantified variables.

\comment{The asserted graph pattern cannot contain blank nodes or
  existentially quantified variables. When the nested rule is
  activated an instance of the rule with known variable bindings
  substituted is created. When a rule under an \air{air:else} property
  is activated, its condition can not contain unbounded universally
  quantified variables.}

\begin{figure} [!t]
\begin{VerbatimN3}
@forAll :SPARQL, :RESULTS, :ORG, :ROLE.

bcc:CollaboratorRequestProcessing a air:Belief-rule;
    air:if { 
        ("""
PREFIX foaf: <http://xmlns.com/foaf/0.1/>
CONSTRUCT { ?G foaf:member """ :R """ . """ :R """ rdf:type ?ROLE . ?G foaf:name ?ORG . }
WHERE { ?G foaf:member """ :R """ .
        ?G foaf:name ?ORG.
        """ :R """ rdf:type ?ROLE . }
       """) string:concatenation :SPARQL .
        ( :SE :SPARQL ) sparql:queryEndpoint :RESULTS .
        :RESULTS log:includes { :G foaf:member :R . :G foaf:name :ORG.
                                :R rdf:type :ROLE . }.
    };
    air:then [
        air:description ( :R " has been confirmed to be employed at "
        :ORG ", which is an authorized collaborator.");
        air:rule bc:CheckAppropriateRole ;
    ];
    air:else [ air:rule bnc:NonCollaboratorRequestProcessing ].
\end{VerbatimN3}
\caption{{\bf Querying a SPARQL endpoint Within AIR Rules:} An AIR
  rule that may be used to query the SPARQL endpoint to discover if
  Maury is indeed employed by the organization he claims to represent
  and to retrieve his role there. There will be a similar rule that
  checks if patient consent has been given.}
\label{fig:sparql}
\end{figure}


Since AIR supports \air{Linked Rules}, AIR rules may be identified by
their URIs that allows them to be easily reused and developed
modularly. For instance, \texttt{bc:CheckAppropriateRole} and
\texttt{bnc:NonCollaboratorRequestProcessing} in
Figure~\ref{fig:sparql} are defined outside of their parent rule's
document, and AIR semantics cause them to be included during the
reasoning of their parent rule,
\texttt{bcc:CollaboratorRequestProcessing}.  The effect of reusing a
rule is that all the rule chains starting with that rule are reused.

%\todo{how do built-ins \& justifications provide trustworthiness}





\subsection{AIR Built-ins}

AIR supports most N3Logic built-ins including those for cryptographic,
math, string, list and time functions.  \air{:LEN math:notGreaterThan
  6} is an example graph pattern that uses the
\qname{math:notGreaterThan} built-in function. The subgraph of
\air{:LEN math:notGreaterThan 6} matches if the value of \qname{:LEN},
which is a variable, is found to be less than or equal to 6. Arguments
to N-ary functions and built-ins are declared using an
\rdf{rdf:List}. RDF graphs in Web documents can be accessed using the
built-in function \air{log:semantics}, and subgraph matching
functionality is provided by the \air{log:includes} property. The
\air{log:semantics} and \air{log:includes} properties allow rules to
extract certain RDF graphs from Web documents making them useful in
{\it trust management} as different Web documents may be trusted with
assertions about certain data but not all data. Accessing only trusted
RDF subgraphs from Web pages is useful in maintaining the quality of
inference results. The \air{log:notIncludes} property is used to check
if a graph is not included in another graph (with closed world
semantics).  \comment{In Figure~\ref{fig:builtins}, the rule checks
  whether the requester, \qname{Maury}, is a member of an agency that
  is certified by a board by checking the contents of a Web resource,
  \qname{board\_cert:Board\_Certified}, and seeing if it contains the
  required triple, \rdf{ board\_cert:Board\_Certified
    foaf:Organization :AGENCY}.}

\begin{figure}
\begin{VerbatimN3}
@forAll :LOG, :RULE, :FUNCTION .

bc:CheckAppropriateRole a air:Belief-rule;
    air:if {
        ( { :R a ex:Requester; rdf:type :ROLE. :G foaf:member :R. }. :RESULTS)
               log:conjunction :LOG.
        <http://bigcity.example.com/bcrbac.n3> log:semantics :RULE.
        ( ( :LOG ) ( :RULE ) ) air:justifies 
            { :R air:compliant-with bcpol:BigCityRBAC.
              :R ex:authorized_role :FUNCTION . } .
    } ;
    air:then [ 
        air:description ( :R " is in an authorized role " :FUNCTION
                          " as defined by BigCity RBAC." );
        air:assert { :REQUEST air:compliant-with :BigCityDissemination. } ;
    ] ;
    air:else [
        air:description ( :R " performing function " :ROLE
                          " but is not in a permissible role
                            as defined by BigCity RBAC." );
        air:assert { :REQUEST air:non-compliant-with :BigCityDissemination. } ;
    ] .
\end{VerbatimN3}
\caption{{\bf Recursive Execution of AIR Rules:} \air{air:justifies}
  may be used to recursively call rule sets, as in this example where
  \qname{BigCityRBAC} is executed from within
  \qname{CheckAppropriateRule} and \air{log:includes} is used to check
  the results of its execution.}
\label{fig:justifies}
\end{figure}

As seen in Figure~\ref{fig:sparql}, SPARQL queries can be executed
from within AIR rules using \air{sparql} built-ins. SPARQL CONSTRUCT
queries may be sent to SPARQL endpoints using the
\air{sparql:queryEndpoint} property assertion, and subgraph patterns
may be searched for in the graph returned by the endpoint. 

AIR's ability to incorporate the contents of SPARQL queries meets the
first need of the motivating use case; BigCity may query back to
BigPharma's SPARQL server to verify Maury's identity and role.  The
rule in Figure~\ref{fig:sparql} includes a SPARQL CONSTRUCT query to
determine Maury's affiliation and extract a graph that may be used in
additional rules.  If this graph contains a desired triple \rdf{:G
  foaf:member :R .}, it would allow for the conclusion that Maury is
actually a member of BigPharma as his credentials claim.


\comment{The \air{air:justifies} property can be used to check if the
  AIR-closure of facts in a set of RDF graphs with respect to the AIR
  rules in another graph RDF-entail a graph pattern.}

The \air{air:justifies} property can be used to check if the execution
of some external AIR rules (AIR-closure) against some Semantic Web
data produces (RDF-entails) a certain RDF graph. The results of these
external rules are not directly included into the current state but
can be queried selectively. Together, the \air{log} and
\air{air:justifies} built-ins provide {\it scoped contextualized
  reasoning}.  Figure~\ref{fig:justifies} provides an example of the
use of \air{air:justifies} in order to prove that Maury performs an
appropriate role, as defined in a separate rule,
\qname{bcpol:BigCityRBAC} (located at
\qname{$<$http://bigcity.example.com/bcrbac.n3$>$}).  AIR thus meets
the second need of our hypothetical use case: that BigCity should be
able to reuse and execute rules defined in other documents.


 \comment{RDF and AIR documents can be dynamically
   determined. i.e. RDF and AIR documents can be referred to by
   variables that acquire bindings at the time of reasoning, depending
   on the input facts.}


\section{AIR Justifications}
\label{sec:justifications}


Upon finalizing its reasoning results, the AIR reasoner produces a
justification that contains sufficient information to understand the
decisions and actions made by the reasoner and to debug the rules, if
needed. We have developed a justification ontology based on basic
Proof Markup Language (PML) concepts~\cite{pml}. The AIR operational
semantics (as described in Section~\ref{sec:semantics}) also define
how this justification is generated by the reasoner. As AIR
justifications themselves are N3 data, they can be consumed by other
reasoners including AIR to evaluate the {\it quality} and {\it
  trustworthiness} of the results based on the rules and data sources
used.

 
\subsection{Justification Ontology}
\label{sec:justont}

The AIR justification ontology extends certain PML~\cite{pml} concepts
as shown in Figure~\ref{fig:justont}. We use the PML-Lite
vocabulary\footnote{PML-Lite - http://tw.rpi.edu/proj/tami/PML-Lite}
that represents a subset of PML and is modeled as Events, which can be
conveniently used for representing the AIR reasoning steps.  The AIR
justification ontology consists of three main classes ---
\air{pmll:Event}, \air{pmlj:Mapping} and \air{pmll:Operation}. The
\air{pmll:Event}s may be categorized into \air{airj:BuiltinAssertion},
\air{airj:ClosingTheWorld}, \air{airj:ClosureComputation},
\air{airj:Dereference}, \air{airj:Extraction}, and
\air{airj:RuleApplication} events depending on the operation
performed.

\begin{figure}[!t]
\begin{center}
\includegraphics[height=2.25in]{images/just-ont.jpg} 
\end{center}
\caption{{\bf AIR Justification Ontology:} PML concepts are enclosed
  in solid boxes and ovals, sub-concepts and sub-properties are
  depicted in the boxes adjacent to the concept and property labels,
  respectively.}
\label{fig:justont}
\end{figure}


The AIR reasoner computes the closure of input facts with respect to a
given AIR ruleset. An \air{airj:ClosureComputation} event captures
this operation. The events of all other types are all part of some
\air{airj:ClosureComputation} event.

The input to an AIR ruleset may be contained in a set of N3 or RDF
documents.  These documents, on the web or on a local machine, are
dereferenced to retrieve their RDF representation. This step is
encoded as an \air{airj:Dereference} event.  In the example in
Figure~\ref{fig:justification}, the document located at
\qname{$<$http://bigcity.example.com/record\_request\_log.n3$>$} is
dereferenced to get the RDF graph \qname{\_:g1} in the
\qname{\_:g0}.

Apart from the input triples, there are RDF triples that are
tautologically true.  Some of these are built-in assertions. In
practice, built-in triples are created dynamically. However, we
abstract this process and represent it through
\air{airj:BuiltinAssertion} and \air{airj:BuiltinExtraction}
events. The output of an \air{airj:BuiltinAssertion} event is assumed
to be the graph that contains all the true built-in assertions
(potentially unbounded in number) for the built-in function specified
by the \air{airj:builtin} property. The assertions needed to match
rule conditions are then extracted from this output in an
\air{airj:BuiltinExtraction} event. The \air{airj:Extraction} event
from which \air{airj:BuiltinExtraction} is derived, is used to encode
the step where a subgraph is obtained from a graph. The input to
airj:BuiltinExtraction event is also left implicit, but may be
determined by the \air{airj:BuiltinAssertion} event on which the
extraction has an \air{airj:dataDependency}.

\begin{figure}[!t]
\begin{VerbatimN3}
_:g0 a airj:Dereference ;
     airj:source <http://bigcity.example.com/record_request_log.n3> ;
     airj:outputdata _:g1 .

_:g2 a airj:BuiltinAssertion ;
     airj:builtin log:includes .

# Note, we use :BIGCITYDB as a short-hand for the graph bound to :BIGCITYDB in
# :CheckCollaboratingPharma

# In practice, :BIGCITYDB would be replaced with what the graph was bound to, rather
# than remaining a URI.
_:g3 a airj:BuiltinExtraction ;
     airj:dataDependency _:g2 ;
     airj:outputdata { :BIGCITYDB
       log:includes {
         <http://bigpharma.example.com/> a ex:CollaboratingPharma ;
           ex:sparqlendpoint <http://bigpharma.example.com/sparql> } } .

# Other built-ins are asserted similarly...

_:g4 a airj:RuleApplication ;
     air:rule :CheckCollaboratingPharma ;
     airj:branch air:then ;
     airj:dataDependency _:g0, _:g3 ; 
     # More dependencies would be here to justify the 
     # other built-ins in :CheckCollaboratingPharma.
     airj:outputVariableMappingList (_:mapping1 _:mapping2) . # and so on

_:mapping1 a pmlj:Mapping ;
           airj:mappingFrom :G ;
           airj:mappingTo <http://bigpharma.example.com/> .

# More mappings like this would be generated for each and every mapping
# bound in the particular rule application.
\end{VerbatimN3}
\caption{{\bf An AIR Justification:} Part of the justification of
  Maury's employment at BigPharma as based on the rules provided in
  Figures~\ref{fig:rules}.  Note that for reasons of convenience, all
  events generated have been assigned to blank nodes
  (e.g. \qname{\_:g0}), but could just as easily be assigned to
  automatically generated dereferenceable URIs in a local
  justification log.}
\label{fig:justification}
\end{figure}

In the example in Figure~\ref{fig:justification}, to match the
condition of \qname{:CheckCollaboratingPharma} it was required
that the graph \qname{:BIGCITYDB} include (among others) the
triple \rdf{$<$http://bigpharma.example.com/$>$ a
  ex:CollaboratingPharma}.  This was tested using the
\air{log:include} built-in. Using the abstract event \qname{\_:g2},
we get all \air{log:include} triples that can be true, and extract
the one relevant for reasoning in the \qname{\_:g3} event. Thus,
\qname{\_:g3} has a data dependency on \qname{\_:g2}.

The \air{airj:ClosingTheWorld} event refers to a step of reasoning
where triples other than the ones in the input or those inferred so
far, and rules other than those that are active, are believed not to
be true. \comment{Once the world is closed the conditions of active
  rules that are not satisfied are assumed to be false and all the
  failed rules are fired.} An \air{airj:ClosingTheWorld} event has
data and/or flow control dependencies on all prior
\air{airj:RuleApplication} events. These dependencies are represented
through \air{airj:dataDependency} and \air{airj:flowDependency}
properties.


In Figure~\ref{fig:closedworld}, another part of the justification
begun in Figure~\ref{fig:justification}, an \air{airj:ClosingTheWorld}
event, \qname{\_:g11}, is used to close the world to decide
\qname{bc:CheckAppropriateRole} so that it may follow the
\air{air:else} action.  This allows the reasoner to conclude that
Maury is not performing a valid function that would justify releasing
the patient records from BigCity.  Note that event \qname{\_:g11}
has an \air{airj:dataDependency} on all previous
\air{airj:BuiltinExtraction} and \air{airj:Dereference} events which
built the now-closed knowledge base.

\begin{figure}
\begin{VerbatimN3}
_:g11 a airj:ClosingTheWorld ;
      airj:dataDependency _:g0, _:g4 . # And others in the same way.

_:g12 a airj:RuleApplication ;
      air:rule bc:CheckAppropriateRole ;
      airj:branch air:else ;
      # ...
      airj:dataDependency _:g11 ;
      airj:outputdata { <http://bigcity.example.com/record_request_log.n3#mauryRequest>
        air:non-compliant-with :BigCityDissemination . } .
\end{VerbatimN3}
\caption{{\bf Justifying Maury's rejection:} Closing the world to
  assert \air{air:else}.}
\label{fig:closedworld}
\end{figure}

The \air{airj:RuleApplication} event represents a rule firing event.
It is linked to the rule that fired with the \air{air:rule}
property. When a nested rule is activated, the known variable bindings
are passed from the parent rule. The \air{airj:RuleApplication} event
for a nested rule has a special flow dependency, referred to as an
\air{airj:nestedDependency}, on the \air{airj:RuleApplication} event
where the parent rule fired.  The input variable bindings for the
nested rule are implicit and are the same as the output variable
bindings of the parent.

When the condition of the rule is satisfied, variable bindings may be
acquired, and the \air{air:then} actions are effected. Otherwise, the
\air{air:else} actions are effected. Which actions are effected is declared
using the \air{air:branch} property. The variable bindings are
acquired upon pattern matching of the rule condition against the fact
base, and declared using the \air{airj:outputVariableMappingList}
property. Any triples asserted when the rule fires are declared using
the \air{airj:outputdata} property and the event is annotated with
natural-language description specified by the \air{air:description} property.
\air{airj:RuleApplication} events also may have data dependencies
on other events.  The condition can be satisfied by triples from more
than one input log, or by triples asserted in some of the prior
\air{airj:RuleApplication} events may.  These events also have flow
control dependencies on prior \air{airj:ClosingTheWorld} events.

In the example given in Figure~\ref{fig:justification} and its
continuation in Figure~\ref{fig:closedworld} we observe two
\air{airj:RuleApplication} events, \qname{\_:g4}, using the
rule \qname{:CheckCollaboratingPharma}, and \qname{\_:g12},
using \qname{bc:CheckAppropriateRole}.  Neither rule application was a
result of a nested rule, so no \air{airj:nestedDependency} triples
were generated.  \qname{\_:g4} followed the \air{air:then} path,
and depended on information generated by dereferencing the log in
\qname{\_:g0} and a built-in asserted in \qname{\_:g3}.
\qname{\_:g12}, in contrast, followed the \air{air:else} path by
depending on closing the world in \qname{\_:g11}.  This particular
action asserted non-compliance, which is indicated by the
\air{airj:outputdata} property.

By manually or automatedly tracing the output data and rule
dependencies from each \air{airj:BuiltinExtraction},
\air{airj:Dereference}, or \air{airj:RuleApplication} event, we may
determine the order in which rules were applied and what data was
used.  This also allows for the construction of meaningful,
human-readable justification traces and
interfaces~\cite{kagal08using}.

\subsection{Justification Generation}
\label{sec:justgen}

AIR supports justification generation for every action taken by the
reasoner. When an action is taken (either a graph pattern asserted
or a rule activated), the action is annotated with the identity of the
rule and with either the matched subgraph or a list of components
known to be true under the closed world assumption. The operational
semantics, described later in Section~\ref{sec:semantics}, define
how the justification is generated by the reasoner.  \comment{(Please
  refer to the Section~\ref{sec:semantic} for more details) } The
default justification for an AIR conclusion is constructed by taking
the union of annotations for the conclusion and the rule in which the
conclusion was asserted.

Though knowing the rules and facts from which a conclusion is derived
is useful, it does not describe what the rule was attempting to do. In
order to provide natural-language explanations, we allow
\air{air:descriptions} to be added to \air{air:actions}. These
descriptions are English sentences and can contain variable
values. The \air{air:description} property is a list instance, where
list items are enclosed in brackets and separated by commas. Each list
item can either be a string enclosed in quotes or a quantified URI
variable. During the reasoning process, each variable is replaced by
its current value and inserted into the description string. For
example, the \air{description} of
\texttt{:CollaboratorRequestProcessing} from Figure~\ref{fig:sparql}
is a list consisting of two variables, \qname{:R} and \qname{:Q} and
two strings --- {\it has been confirmed to be employed at } and {\it
  which is an authorized collaborator}.

\begin{figure}
\begin{VerbatimN3}
...
@forSome _:g11 .
_:g11 a airj:RuleApplication ;
         # an air:flowDependency may be given.
         airj:outputdata { <http://bigcity.example.com/record_request_log.n3#mauryRequest>
         air:non-compliant-with :BigCityDissemination . } .
...
\end{VerbatimN3}
\caption{{\bf Justification of Elided Rule:} Justification for Maury's
  rejection does not contain the \air{Elided-rule},
  \texttt{:CheckAppropriateRole}}
\label{fig:hiddenjust}
\end{figure}

Sometimes, the default justification can be unwieldy or very
revealing, and needs to be modified to hide trivial or sensitive
information.  AIR provides mechanisms to {\it declaratively modify
  justifications} generated by default. Rules in AIR may be declared
to be \air{air:Hidden-rules} or \air{air:Elided-rules} to suppress
justifications for certain actions. The detailed justifications for
actions executed when an \air{Elided-rule} fires are suppressed, and
only the natural-language description is provided. The justification
for actions executed when a \air{Hidden-rule} or its descendants fire
are suppressed completely. This flexibility to control the level of
details, at a rule-based granularity, helps the rule writers to adjust
the justification so that sensitive information is not revealed and so
explanations are not overly verbose.  Nesting of rules can be used
advantageously to split a rule's conditions across multiple rules when
parts of the graph pattern refer to sensitive (or insignificant)
information, such that rules with sensitive conditions may be elided
or hidden.

From our use case, Maury must be able to prove that he is authorized
to act in an appropriate role in order to access information from
BigCity. It is entirely possible that BigCity would desire that Maury
not know what roles are allowed access, in order to prevent later
exploitation. In this case, \texttt{bc:CheckAppropriateRole} from
Figure~\ref{fig:justifies} could be declared to be an
\air{Elided-rule} such as \air{bc:CheckAppropriateRole a
  air:Elided-rule.} As illustrated in Figure~\ref{fig:hiddenjust}, the
justification for Maury's rejection would not contain information
about \texttt{:CheckAppropriateRole}.


\comment{
\section{AIR Profiles} 
%\todo{How AIR can be used in other scenarios - Lalana. Only add if there is
%  space.}
}

\section{AIR Semantics}
\label{sec:semantics}

\begin{figure}[!t]
\begin{center}
\includegraphics[height=1.2in]{images/RuleNestingEx.jpg}
\end{center}
\caption{{\bf Example of AIR Rule Nesting}}
\label{fig:nestingex}
\end{figure}

The procedural semantics of AIR describe how AIR rules fire and how
inferences are made. The AIR reasoner applies forward chaining
reasoning to compute the closure of AIR rules over the input
data. When AIR rules fire, their actions, substituted with known
variable bindings, are effected. As a result, new rules may be added
to the rule base, i.e. new rules may be activated, and/or facts may be
deduced. Initially the rule base contains all top rules in the
ruleset, and the fact base is made of the input facts. The rules in
the rule base are said to be active. The active rules whose conditions
match the current state of the world (fact base) are referred to as
successful rules, whereas those active rules whose conditions have no
match are called failed rules.

AIR reasoning is performed in stages. In any given stage, the
successful rules are given priority over failed rules and their
then-actions are effected before failed rules fire. When all
successful rules have fired the world is temporarily closed and the
else-actions of all the failed rules are fired simultaneously with the
belief that the conditions of all the failed rules are false. AIR
reasoning enters the next stage once the failed rules have all
fired. The AIR closure is computed in a finite number of
stages~\cite{khandelwal10air}.

In order to illustrate rule nesting, we consider an arbitrary nesting
shown in Figure~\ref{fig:nestingex}. Initially, i.e. before entering
stage 1, only Rule$_{A}$ and Rule$_{B}$ are in the rule base. Then, if
the condition of Rule$_{B}$ is satisfied, Rule$_{D}$ would be active
in stage 1. However, if in stage 1 Rule$_{B}$ doesn't succeed, then
Rule$_{C}$ will be added to the rule base after the world is closed
for stage 1, and will be active from stage 2. Now, in stage 2, if
Rule$_{C}$ succeeds then Rule$_{E}$ will become active in stage
2. Otherwise Rule$_{F}$ will be active from stage 3. Note that if
Rule$_{B}$ succeeds in later stages, say stage 3, then Rule$_{D}$ will
also be active (in addition to Rule$_{C}$) from stage 3 onwards.

The declarative semantics of an AIR program are defined through
translation to stratified Logic
Programs~\cite{przymusinski88declarative}. The AIR-closure computation
is polynomially-complete in data-complexity and exponentially-complete
in program-complexity, where data complexity is the complexity of
computing the closure when the program is fixed and the facts are
input and program complexity is the complexity when the facts are
fixed and program is input~\cite{khandelwal10air}.

Nesting introduces an ordering of rules that can be leveraged to
encode fairly expressive Logic Programs (LP) in AIR, such as Positive
LP and a special class of stratified LP - Positively Stratified
Negatively Hierarchical LP~\cite{khandelwal10air}. Furthermore, SPARQL
SELECT and CONSTRUCT queries may be encoded in AIR and executed by the
AIR reasoner~\cite{khandelwal10air}.

\section{Related Work}
\label{sec:related}

%\todo{how about other justification systems - if we say our focus is
%  on the justification generation then we should refer to these. If we
%  say our focus is on the ontology then we have to make sure that the
%  ontology does not have any problems}

There are many rule languages and rule systems, some advanced and
others at prototypical levels. Examples of Web rule languages include
N3Logic~\cite{n3logic}, NG~\cite{schenk08ng}, SILK~\cite{grosof09silk}
and SWRL\footnote{http://www.daml.org/rules/proposal/}, while some
rule engines are Jess\footnote{http://www.jessrules.com/},
Jena\footnote{http://jena.sourceforge.net/} and XSB~\cite{xsb}.
Liang et. al. give a nice overview of popular, and often advanced,
rule systems~\cite{liang09openrulebench}.

Though N3Logic supports monotonic negation, AIR supports non-monotonic
negation. In comparison, NGs supports the well-founded (WF) negation,
XSB support negation-as-failure, and Jess supports non-logical
negation. SILK supports WF non-monotonic negation as well as classical
negation. Nesting of rules is unique to AIR amongst the systems
mentioned above. OPS/YES~\cite{schor86advances} extends the
OPS5~\cite{forgy81ops5} production rule system with many features
including that which allows matching in the actions. This is referred
to as incremental rule addition and AIR has a similar notion of rule
nesting.

Amongst the above systems, only AIR provides justifications. The
Ontonova system~\cite{angele03ontologybased} provides natural-language
explanation of proof trees for conclusions by the Ontobroker, through
meta-inferencing. The meta-inferencing rules are defined for different
rule instantiations and applied over the logs generated by Ontobroker
during the inferencing process. The logs contain instantiated rules
that were successfully applied and led to the derivation of an
answer. The defeasible reasoning system, DR-DEVICE, has a similar
mechanism for generating proofs\cite{bassiliades07proof}. Defeasible
rules can be translated to XSB rules, and interpreted by XSB. The XSB
trace is processed and tagged with a proof schema. In the context of
OWL, a subset of the ontology that is sufficient for OWL entailment to
hold is treated as the justification for the entailment and algorithms
exist to derive the minimal such subset
\cite{horridge08laconic,kalyanpur07finding}. Unlike the above systems,
AIR supports syntax and semantics to provide for the alteration of
rule definitions, addition of natural-language descriptions and hiding
of portions of the justification.

\comment{Amongst the above systems, only AIR provides
  justifications. The Ontonova system~\cite{angele03ontologybased}
  provides natural-language explanation of proof trees for conclusions
  by the Ontobroker, through meta-inferencing. The meta-inferencing
  rules are defined for different rule instantiations and applied over
  the logs generated by Ontobroker during the inferencing process. The
  logs contain instantiated rules that were successfully applied and
  led to the derivation of an answer. The defeasible reasoning system,
  DR-DEVICE, has a similar mechanism for generating
  proofs\cite{bassiliades07proof}. Defeasible rules can be translated
  to XSB rules that can be interpreted by XSB. Unlike AIR, however,
  the XSB trace is processed and tagged with a proof schema.}

Contextualized reasoning is important for Web rule languages because
information on the Web is often assumed to be incomplete or
inconsistent, and its correctness is subject to the trustworthiness
of the source. \cite{polleres06ruleswith} gives a formal definition of
LPs with context and scoped negation. AIR borrows its contextualized
reasoning aspects from N3Logic. Other than N3Logic and AIR, SILK
supports contextualized reasoning. In SPARQL queries, the query
patterns can be restricted to selective named graphs, and as a result
NGs naturally supports contextualized reasoning.

The Rule Interchange Format (RIF)~\cite{kifer08rule} has two major
dialects --- the Framework for Logic Dialects (FLD) and the Production
Rule Dialect (PRD). Unlike PRD, actions in AIR cannot modify or remove
facts, but they can add new production rules. However, because of the
former, AIR negation can be termed logical. RIF-FLD is an extensible
framework for rule-based languages, and includes the Basic Logic
Dialect (BLD), which corresponds to the definite Horn rules with
equality and standard first order logic semantics. AIR is neither more
nor less expressive than BLD. AIR supports negation unlike BLD, but it
does not support function symbols that BLD does. Further, AIR has a
rich set of built-ins. SWRL is a function-free rule language limited
to binary and unary predicates, and all its features, barring
different-from, are covered by RIF-BLD. Therefore, AIR is at least as
expressive as SWRL.  As mentioned earlier, PLPs can be encoded in AIR
and therefore OWL 2
RL\footnote{http://www.w3.org/TR/owl2-profiles/\#OWL\_2\_RL} inference
rules can be encoded in AIR and used concurrently with other rules.

\comment{The Rule Interchange Format (RIF)~\cite{kifer08rule} has two
  major dialects --- the Framework for Logic Dialects (FLD) and the
  Production Rule Dialect (PRD). Unlike RIF-PRD, actions in AIR cannot
  modify or remove facts, but they can add new production
  rules. RIF-FLD is an extensible framework for rule-based languages,
  and includes the Basic Logic Dialect (BLD), which corresponds to the
  definite Horn rules with equality and standard first order logic
  semantics. AIR is neither more nor less expressive than
  RIF-BLD. Unlike BLD, function symbols are not supported in AIR. SWRL
  is a function-free rule language limited to binary and unary
  predicates, and all its features, barring different-from, are
  covered by RIF-BLD. Therefore, AIR is at least as expressive as
  SWRL.  As mentioned earlier, PLPs can be encoded in AIR and
  therefore OWL 2
  RL\footnote{http://www.w3.org/TR/owl2-profiles/\#OWL\_2\_RL}
  inference rules can be encoded in AIR and used concurrently with
  other rules.}

Though several rule languages provide a subset of AIR's features, AIR
is unique in its support of \air{Linked Rules}, its focus on
justification (both generated by default and declaratively modified),
and its ability to objectively query the contents of Web resources
(both Web pages and SPARQL endpoints). For a more detailed comparison
of AIR with other rule languages, rule engines and rule systems,
please refer to our technical report~\cite{khandelwal10air}.

\section{Summary and Future Work}
\label{sec:summary}
% restate AIR contributions, naming - if, then, else, policy
% conflicts, policy defaults

We have found that AIR's expressiveness and functionality allow it to
easily capture real world rules and policies while leveraging
(Semantic) Web data and protocols. It supports \air{Linked Rules} so
AIR rules can be developed and re-used in a manner similar to Linked
Data, provides functions for scoped contextualized reasoning, and
provides justification for its inferences that can be used to evaluate
the trustworthiness of its results. Though our use case demonstrates
how AIR can be used in collaborative environments, AIR has also been
used for information
sharing\footnote{http://dig.csail.mit.edu/2009/DHS-fusion/}, for
access control and policy
management~\cite{kagal08using,auyeung09providing}, to secure SPARQL
endpoints~\cite{cherian10www}, to check the compliance of queries
against privacy policies~\cite{kagal10ppssi} and as an accountability
mechanism for checking whether audit logs comply with data usage
policy~\cite{weitzner08cacm}. Thus far, our focus has been on studying
the rule requirements of open Web information systems, designing
appropriate features in the rule language, and implementing AIR-based
systems. Moving forward we will work on handling conflicts between
rules and on enabling default behavior when none of the conditions of
a \air{RuleSet} match. We are also interested in understanding the
performance and scalability of AIR and plan to use or extend existing
benchmarks~\cite{liang09openrulebench}.

\comment{
\section*{Acknowledgements}
We would like to thank Joe Pato, Mike Speciner and other members of
the Decentralized Information Group at MIT as well as Li Ding, Jie
Bao, and the members of Tetherless Constellation Group at RPI for
their advice and contributions to this project.  This work was
supported in part by NSF Cybertrust award number 04281, IARPA award
number FA8750-07-2-0031, and AFOSR award number 6921570.
}

\bibliographystyle{abbrv}
\bibliography{paper}

\pagebreak
\appendix

\section{APPENDIX: Namespaces}

In this paper, we refer to the namespaces defined in
Figure~\ref{fig:namespaces}.

\begin{figure}
\begin{VerbatimScript}
@prefix air: <http://dig.csail.mit.edu/2009/AIR/air#>.
@prefix airj: <http://dig.csail.mit.edu/2009/AIR/airjustification#>.
@prefix log: <http://www.w3.org/2000/10/swap/log#>.
@prefix math: <http://www.w3.org/2000/10/swap/math#>.
@prefix string: <http://www.w3.org/2000/10/swap/string#>.
@prefix sparql: <http://www.w3.org/2000/10/swap/sparqlCwm#>.

@prefix pmlj: <http://inference-web.org/2.0/pml-justification.owl#>.
@prefix pmlp: <http://inference-web.org/2.0/pml-provenance.owl#>.
@prefix pmll: <http://inference-web.org/2.0/pml-lite.owl#>.

@prefix rdfs: <http://www.w3.org/2000/01/rdf-schema#>.
@prefix foaf: <http://xmlns.com/foaf/0.1/>.

@prefix ex: <http://bigcity.example.com/ont#>.
@prefix bcc: <http://bigcity.example.com/bccrule#>.
@prefix bnc: <http://bigcity.example.com/bcrule#>.
@prefix bc: <http://bigcity.example.com/bigcitydissemination#>.
@prefix bcpol: <http://bigcity.example.com/bcrbac#>.
@prefix : <http://bigcity.example.com/bigcitydissemination#>.
\end{VerbatimScript}
\caption{{\bf Namespaces Used}}
\label{fig:namespaces}
\end{figure}

\comment{
@prefix fusion: <http://dig.csail.mit.edu/2010/DHSfusion/common/fusion#>.
@prefix core10: <http://dig.csail.mit.edu/2010/DHSfusion/core10/core10#>.
@prefix mgl: <http://dig.csail.mit.edu/2010/DHS-fusion/MA/rules/MGL_66A-1_ONT#>.
@prefix mgl66a: <http://dig.csail.mit.edu/2010/DHS-fusion/MA/rules/MGL_66A-1#>.
@prefix : <http://dig.csail.mit.edu/2010/DHSfusion/MA/rules/MGL_6-172#>.
}

\end{document}
