\chapter{Background Technologies} Data on the World Wide Web is readily available to human agents, but notoriously for machines to interpret. The Semantic Web is an ongoing initiative to develop Web-based data systems that are easily readable by both humans and machines. Common tactics for achieving this goal include tagging data, linking data, and writing software to draw conclusions on data. This project draws heavily on Semantic Web technologies. In this chapter, I discuss the Semantic Web initiative as well as several technologies that were used in this project. This overview is far from exhaustive, as there are a large number of technologies that comprise the Semantic Web vision; rather, this summary is here to explain the suitability of the technologies chosen, as well as to provide an introduction to these technologies for the reader. \section{Semantic Web Overview} \subsection{The Vision} \begin{quote} \emph{``The Semantic Web is not a separate Web but an extension of the current one, in which information is given well-defined meaning, better enabling computers and people to work in cooperation.''} --Tim Berners-Lee. From \cite{sciam} \end{quote} In broad terms, the Semantic Web is a set of extensions to the current World Wide Web designed to make it easier for automated systems to interact data, and thus, to make it easier for humans to interact with data. The goal is to provide tools that make it possible to improve data handling in a large, heterogeneous, decentralized environment such as the Web. The current strategy is to provide tools that allow us to describe data, and tools that perform reasoning over data. The Semantic Web development effort has directly led to a number of technologies \cite{swa} that enable data markup, ontology definition, and other useful tasks. These tools extend existing systems (such as the HTML language), and serve as adaptations of other technologies (such as XML). \begin{figure} \centering \includegraphics[scale=0.5]{layerCake-4} \caption{Semantic Web ``layer cake,'' showing how components relate\cite{swot}.} \label{layercake} \end{figure} Developments in the Semantic Web effort have produced a way of naming abstract concepts, a way of describing concepts using other concepts or literals, and a way of finding descriptions and matching patterns. More importantly, these technologies make it much easier for both human and machine agents to read, reason on, and operate upon data. In a world that is ever more interdisciplinary, being able to connect disparate data is a boon. Semantic Web technologies are moving out of the realm of research and into commercial production. Adobe offers tools to embed RDF metadata in a number of formats\cite{adobe-xmp}. The Creative Commons license\cite{cc-ns} embeds RDF metadata that helps determine usage rights for media. Major Web search engines as of this mid-2009 writing, such as Google, bing, and Wolfram Alpha, employ Semantic Web technologies to help improve the quality of search results. RDF triples are becoming popular in the biomedical and intelligence communities, where collaboration between disciplines is crucial to success. \subsection{The URI} The Uniform Resource Identifier, or URI, is the unique technology that enables naming on the Web\cite{uris}. A URI may serve as a pointer to a resource, be it a Web page, an e-mail address, the location of a music file, the name of a service. A URI may point to something that does not exist. Regardless of its destination, a URI serves as a unique identifier in the Web world. A URI enables us to refer to items in a namespace as well. The idea of ``URI as a name'' is a crucial cornerstone of the Semantic Web. For example, let us consider the following URI: \begin{Verbatim} http://www.example.org/ \end{Verbatim} This URI points to a resource that might be located there. Now, let's create a simple ontology for describing things that I might find at a local grocery store: \begin{Verbatim} http://www.example.org/grocery#banana http://www.example.org/grocery#apple http://www.example.org/grocery#spaghetti \end{Verbatim} Each of these URIs contains value itself. When I resolve the URI, and fetch the resource to which it points, I may find a textual description of a banana, or a photograph of an apple, or nutritional information about spaghetti. I may find nothing at all. I can capture the design pattern of common prefixes as a name space. Instead of repeating ourselves, let us define the ``grocery'' namespace as the set of URIs that begin with ``\Verb|http://www.example.org/grocery|''. \subsection{HTML, the Hyper\-Text Mark\-up Language, and XML, the eX\-ten\-si\-ble Mark\-up Language} The Hypertext Markup Language (HTML) serves as the backbone language of the World Wide Web. As a markup language, it provides a standardized way of creating Web documents that users can read with any of a number of programs, including Web browsers. HTML's characteristic property is its ability to encapsulate data with a pre-defined set of tags, easily recognizable with angle brackets. A common tag may look like this: \Verb| Bananas Apples \end{Verbatim} The expressive power of XML is also its weakness: without any standardization, I would have an infinite number of meaningless and unrelated descriptive languages, defeating our goal of human and machine interoperability. An XML schema gives us a way to standardize a description, but even this is not sufficiently robust for machine readability. \section{RDF} The Resource Description Framework, or RDF, provides an infrastructure for creating metadata using the ides of the URI\cite{rdf}\cite{rdf-syntax}. RDF builds on XML technologies to provide a framework for using XML to describe data. \begin{figure} \centering \includegraphics[scale=0.5]{rdf_w3c_icon} \caption{The RDF logo. Its structure suggests the triple pattern. From \cite{rdf}.} \label{rdflogo} \end{figure} At its core, RDF is little more than a formalization of the triple pattern: \Verb+{ subject predicate object }+ The triple pattern is a representation of a \Verb|(noun,verb,modifier)| sentence construct. These three pieces of information describe relationships between objects. Indeed, this pattern is very similar to the constructs for description available in many spoken and written languages. As an example, I show how triple patterns might represent the following relationships in pseudocode in table \ref{basic-triples}. \begin{table} \centering \begin{tabular}{p{4.0cm} p{8.5cm}} \hline Free text & Triple pattern(s) \\ \hline The population of Boston is one million. & \Verb|{ "Boston", "population", "1E6" }| \\ The Red Line stops at Park Street. & \Verb|{ "Red Line", "station", "Park Street" }| \\ The color of the sky is blue. & \Verb|{ "Sky", "color", "blue" }| \\ \hline \end{tabular} \caption{Expressing natural language as triples.} \label{basic-triples} \end{table} I can chain triple patterns together to make more complex statements, as I show in table \ref{jane-triples}. \begin{table} \centering \begin{tabular}{p{4.0cm} p{8.5cm}} \hline Free text & Triple pattern(s) \\ \hline Jane has a pet dog named Zach and a house in Illinois. & \Verb|{ "Jane", "pet", "Zach" }|\\ & \Verb|{ "Zack", "species", "dog" }|\\ & \Verb|{ "Jane", "residence", "house" }|\\ & \Verb|{ "house", "location", "Illinois" }|\\ Zach lives in the house.&\Verb|{ "Zach", "residence", "house" }|\\ \hline \end{tabular} \caption{Expressing natural language as triples.} \label{jane-triples} \end{table} From this information, I could conclude that Zach lives in Illinois\endnote{The names in the pet example are not arbitrary! Zach is a little Pembroke Welsh Corgi who lives in a little ranch house in central Illinois.}. This system of description lends itself to automated reasoning, which is precisely why it is suitable for Semantic Web activity. I will discuss tools to perform this kind of analysis shortly. In practice, there are two additional clarifications that allow definition of triple patterns. First, every subject, predicate, and object must be a URI, a literal, or possibly a variable: \begin{Verbatim} "1,000,000" \end{Verbatim} Secondly, RDF triples must be serialized (written) in a standard format. The two popular approaches for RDF serialization are RDF/XML and Notation 3, or N3 (cite http://www.w3.org/DesignIssues/Notation3.html). I can express this example in RDF/XML as follows, using abbreviations for the RDF and fictitious "geography" namespaces for convenience. RDF/XML fulfills the need for expression of triple pattern relationships in a standardized, royalty-free, open format. \begin{Verbatim} 8000000 \end{Verbatim} In a more general sense, triple patterns enable the expression of nodes and edges of a (directed) graph. Subjects and objects are nodes in the graph, and predicates define the edges. %(diagram of the Jane Zach example from above) Caption: Demonstration of previous (number!) example. \subsection{Notation 3} Notation 3, or N3, is able to express all of RDF/XML, with the goal of being more human readable. For comparison, I show the same triple pattern with an N3 serialization, assuming the same namespaces. \begin{Verbatim} @prefix geography: . geography:boston geography:population 1000000 . \end{Verbatim} The N3 serialization, a form of shorthand or ``syntactic sugar'', is equivalent to the RDF/XML serialization above; tools exist that will transform one into the other. The real strength of N3 - in light of the goals of the Semantic Web - is that it is more human readable. Notation 3 is more expressive than pure RDF; indeed, the complete RDF 1.0 specification is a subset of N3. The language supports implication and quantifiable variables (``for all'' and ``for some''). This additional expressive power enables some interesting applications, such as reasoners, rule systems, and query processing. \section{OWL} RDF and the URI together can describe the properties that an object has, by using unique names and expressing {subject,predicate,object} relationships. In order to have multiple parties agree on a standard set of descriptors for objects, and encode restrictions such as ``there is exactly one of these'' or ``this is a subtype of that'', another system is necessary. The Web Ontology Language, or OWL, provides a common way to capture these design patterns\cite{owl}. OWL offers a way to create ontologies that is more expressive than XML or RDF. Its three dialects, OWL Lite, OWL DL, and OWL Full, offer graded levels of expressive power. OWL allows URIs to have structure, with cardinality, equivalence, and subtyping. OWL can connect different ontologies. \section{Tabulator} The Tabulator\cite{tabulator} is a Semantic Web browser. Implemented as a browser plug-in, or possibly as a standalone application, it makes it easier for humans to view and understand RDF data. Tabulator enables searching, outlining, and tabular display of semantic data. It supports add-ins that enable micro-blogging, and help users understand the structure of some specific RDF formats. Tabulator's role in the Semantic Web project is to serve as a crucial bridge to human usability. \section{SPARQL} RDF data defines a graph structure. This graph may be more complex than a relational model, which focuses on linked tables of row/column attributes. Thus, for reasons of performance or simplicity, it may be useful to create a new data structure for storing triple patterns. For the purpose of this paper, it is sufficient to assume that there exists a way to store triple patterns. Data is meaningless unless it has context and an interested party is able to find it. The URI and the triple pattern\cite{triple-store} allow data to have context, using standards and ontologies that many parties may use. The missing piece of the puzzle is SPARQL, a query language for RDF data and triple stores. From the SPARQL language specification\cite{sparql}: \begin{quote} ``SPARQL can be used to express queries across diverse data sources, whether the data is stored natively as RDF or viewed as RDF via middleware. SPARQL contains capabilities for querying required and optional graph patterns along with their conjunctions and disjunctions. SPARQL also supports extensible value testing and constraining queries by source RDF graph. The results of SPARQL queries can be results sets or RDF graphs.'' \end{quote} Given the N3 triples in figure \ref{sparql-01}, and the SPARQL query in figure \ref{sparql-02}, a SPARQL query processor might return the output in table \ref{sparql-03}. (This example comes from the SPARQL W3C Recommendation \cite{sparql}.) \begin{figure} \centering \begin{Verbatim} \ "SPARQL Tutorial" . \end{Verbatim} \caption{A sample RDF data set, using backslash to denote newline. From \cite{sparql}.} \label{sparql-01} \end{figure} \begin{figure} \centering \begin{Verbatim} SELECT ?title WHERE { \ ?title . } \end{Verbatim} \caption{A sample SPARQL query. From \cite{sparql}.} \label{sparql-02} \end{figure} \begin{table} \centering \begin{tabular}{c c} \hline Variable & Binding \\ \hline title & ``SPARQL Tutorial''\\ \hline \end{tabular} \caption{The output of a basic SPARQL query.} \label{sparql-03} \end{table} SPARQL's syntax is reminiscent of SQL, and this is intentional. A SPARQL implementation will find triple patterns that match the triple patterns specified in the WHERE part of a SPARQL query, and bind and return variables in the SELECT part of the query. In this case, the SPARQL engine will look for any objects in triple patterns, such that the subject of the triple pattern is \Verb|""| and the object of the triple pattern is \Verb|""|. Given only the data in figure 1, it finds exactly one triple pattern with this subject and predicate, the triple pattern with the object ``SPARQL Tutorial''. The SPARQL language is a robust query language. In short, SPARQL is to RDF graphs as SQL is to relational databases. The introduction of SPARQL provides a much needed tool for querying RDF graphs, using a simple, familiar syntax. It enables joins through multiple match patterns. It allows a user to CONSTRUCT a new RDF graph based on the results of the query, to FILTER data, to mark a certain match as OPTIONAL, and to alter the results using LIMIT and OFFSET directives. A user can ASK if any pattern matches a pattern, or have the SPARQL engine DESCRIBE its data set. A user can even specify our own RDF graphs for a query using FROM and FROM NAMED; the SPARQL engine may or may not handle user-specified graphs. (A more thorough discussion of the features of the SPARQL query language follows in a later section, as part of the discussion of this project's query translator.) \section{Reasoning} The reasoning systems in this project build on some classic principles of logic and logical programming. A brief overview of those technologies follows. \subsection{Forward Chaining} Forward chaining, or modus ponens, is a reasoning method by which a set of rules are used to draw all possible conclusions about a data set. A rule typically has two parts, a left hand side and a right hand side, an ``if'' clause and a ``then'' clause, a condition and a consequent. This is also known as a data driven approach, since the rules used and the outcome will vary depending on the data. Of course, the rules determine which possible outcomes a forward chaining system may reach. The inverse of a forward chaining system is backward chaining. In a backward chaining system, the goal is to find data to support a conclusion. This approach is also called a goal driven approach. Indeed, the SPARQL language presented above uses forward reasoning to match triple patterns. In the case of figure \ref{sparql-02}, there must be a rule, somewhere, whose condition is ``if there is a triple pattern with this subject and this predicate'', and whose consequent is ``then output that same triple's object''. The forward chaining approach allows arbitrary conclusions given data and rules; given an unlimited data set, rules could run for a long time, possibly forever. \subsection{Production Rule Systems} A production rule system is a computer program that implements a forward chaining reasoner with a set of rules over a data set. The production rules also feature a condition and a consequent. In addition to forming conclusions, the rules in a production system may have side effects, triggering outside events or causing side effects within the system. A ``naive'' production rule system will simply apply every rule, repeatedly, until it finds a match. Some optimizations will change the order of the rules, or perhaps give certain rules priority. \subsection{The Rete Algorithm} Rete (pronounced REE-tee) is the name of a particular algorithm used for pattern matching in production rule systems\cite{rete}. Developed in the late 1970s by Charles Forgy, Rete offers substantial performance improvements to previous production rule systems by using a tree-based approach. The Rete algorithm makes use of some moderately advanced graph theory in its implementation. for our purposes, what is important is that the algorithm scales well. \subsection{Semantic Web Application Platform} The Semantic Web Application Platform is the name of a number of technologies developed for the purpose of furthering Semantic Web research\cite{swap}. The platform is working to create tools and utilities to enable conversion, extraction, and use of Semantic Web data. \subsection{cwm and cwmrete} Cwm is a software suite written to facilitate Semantic Web work\cite{cwm-cwmrete}. From the Cwm homepage: \begin{quote} \emph{``Cwm (pronounced coom) is a general-purpose data processor for the semantic web, somewhat like sed, awk, etc. for text files or XSLT for XML. It is a forward chaining reasoner which can be used for querying, checking, transforming and filtering information. Its core language is RDF, extended to include rules, and it uses RDF/XML or RDF/N3 serializations as required.''} \end{quote} The cwm reasoner is the backbone of many Semantic Web projects, including this one. Cwmrete, an implementation of the Rete algorithm in cwm, allows advanced forward chaining, as required by the AIR language. \section{AIR} \subsection{Introduction} The AIR policy language, for ``Accountability in RDF'' or ``AMORD\cite{amord} in RDF,'' is a specification for writing policies and making assertions. The language makes use of Notation 3 (N3), an RDF syntax, for expressing policies. These policies consist of individual rules and patterns that, if matched, will trigger other rules and assertions. AIR implements a system of production rules using forward chaining reasoning. The current implementation of the AIR reasoner draws on pre-existing technologies. The reasoner presently incorporates a truth maintenance system (TMS). The AIR reasoner also incorporates work from the Rein project\cite{rein}, which specified policies written in N3, and reasoning using the cwm engine. Rein also introduced distributed policies, and reasoning over such policies in the Semantic Web. In its current form, the AIR reasoner consists of several components. Rules files, written in N3, specify policies, each with at least one rules, which can make assertions. Log files, also in the N3 format, contain facts upon which I might apply AIR rules. AIR permits multiple log files. Finally, a reasoner, or ``policy runner'', accepts a rule file and one or more log files as input. The reasoner will continue to apply the rules using either an open-world or a closed-world assumption until there is nothing more to deduce. For the purpose of this project, the reasoner uses a closed-world assumption so that all assertions depend solely on rules and policies I provide. The reasoner's output, in the N3 format, details the reasoning it performed, including a nested list of the assertions it made. The AIR ontology serves to define the AIR language, in showing which classes are subclasses of other classes and demonstrating how rules inherit from containers and actions. A diagram of the ontology appears in figure \ref{air-ontology}. \begin{figure} \centering \includegraphics[scale=0.5]{air-ont} \caption{Diagram of the AIR policy language ontology.} \label{air-ontology} \end{figure} \subsection{A Brief AIR Tutorial} In this section, I demonstrate the features of a relatively simple AIR policy: a slightly amended version of the policy in the MIT Prox Card Scenario\cite{s0}. The sample policy is complete, and exemplifies many of the features of the AIR language. The online AIR policy tutorial is a helpful reference here\cite{air-t}. The full text of this example policy is in the appendix. The main body of this paper will contain some more advanced policies. It bears mentioning that the policies discussed herein are in ``version 1'' of the AIR language. All of the policies presented later are in ``version 1'' as well. An updated syntax, ``version 2'', is current and was introduced on 13 April 2009. I will quickly demonstrate the differences in versions and rationale for the change here, and discuss the need to move to the new version in the Future Work section. First, any AIR file should declare the air namespace, as AIR policies rely upon the ontology that this namespace defines. The trailing dot is mandatory. \begin{verbatim} @prefix air: . \end{verbatim} An individual policy may declare any namespace as its local namespace, and also specify any number of additional namespaces. \begin{verbatim} @prefix : . (additional namespaces) \end{verbatim} The policy file must declare the variables it will use using an @forAll or @forSome declaration toward the beginning. This is mandatory, as the AIR file has N3 semantics! \Verb|@forAll :U, :D, :P1.| An AIR policy file may contain multiple policies; our example only contains policy. I recall that N3 has some reserved keywords, such as \Verb|a| and \Verb|is a|, which refer to concepts in the OWL ontology. For example, \Verb|a| is shorthand for \Verb|owl:sameAs|. (cite \Verb|http://www.w3.org/TR/owl-ref/#sameAs-def|) A policy may call one or more rules in an attempt to forward chain and make an assertion. \begin{Verbatim} :MITProxCardPolicy a air:Policy; air:rule :MITRule1. \end{Verbatim} Note that this is equivalent to: \begin{Verbatim} http://dig.csail.mit.edu/TAMI/2007/s0/mit-policy#:MITProxCardPolicy \ owl:sameAs http://dig.csail.mit.edu/TAMI/2007/amord/air#:Policy; http://dig.csail.mit.edu/TAMI/2007/s0/mit-policy#:MITProxCardPolicy \ air:rule http://dig.csail.mit.edu/TAMI/2007/s0/mit-policy#:MITRule1. \end{Verbatim} A policy will point to one or more rules. A rule can contain: \begin{itemize} \item a description, which is a free text descriptor of the rule and may contain variable references; \item a pattern, which is a set of conditions that must all be true for a rule to activate; \item a label, which is a name for the rule; \item an assert, which is the action the reasoner takes if the pattern is matched; \item an alt, which is the action the reasoner will take if the pattern is not matched. \end{itemize} The first rule merits further investigation: \begin{Verbatim} :MITRule1 a air:BeliefRule; air:label "MIT prox-card policy"; air:pattern { :U a air:UseEvent; air:data :D; air:purpose :P1. :D a mit:ProxCardEvent. }; air:rule :MITRule2. \end{Verbatim} This code captures the following meaning: ``Suppose I can find something, call it \Verb|:U|, that is an \Verb|air:UseEvent|, with an \Verb|air:Data| of something else that I can call \Verb|:D|, and an \Verb|air:purpose| of yet another thing that I can call \Verb|:P1|. If that \Verb|:D| turns out to be an \Verb|mit:ProxCardEvent|, then activate \Verb|:MITRule2|.'' Let's take a look at the following two rules. \begin{Verbatim} :MITRule2 a air:BeliefRule; air:pattern { :P1 :sameAs pur:criminal-law-enforcement. }; air:description (:P1 " is same as a criminal activity"); air:assert { :U air:compliant-with :MITProxCardPolicy. }; air:alt [ air:rule :MITRule3 ]. :MITRule3 a air:BeliefRule; air:pattern {}; air:description (:P1 " is different from a criminal activity"); air:assert { :U air:non-compliant-with :MITProxCardPolicy }. \end{Verbatim} This pair of rules says, ``If that purpose \Verb|:P1| I found is, in fact, the same as \Verb|pur:criminal-law-enforcement|, then this \Verb|:U| is compliant. Otherwise, this \Verb|:U| is not compliant!'' The MIT Prox Card Policy, though relatively simple, serves to encode a real-world policy in an electronic format that a machine can readily use. There is some effort to further this work, to encode more real world laws and policies; it is the focus of TAMI, the Transparent Accountable Datamining Initiative (cite tami), and other works (cite any that you find). \subsection{Changes to the AIR language} On 15 April 2009, Ian Jacobi announced the following changes to the AIR language specification, bringing it to version 2. As all of the policies in this thesis use version 1 of the AIR language specification, porting them to version 2 is an important future work. The changes are as follows. \begin{enumerate} \item The \Verb|air:pattern| and \Verb|air:alt| properties have been effectively renamed to \Verb|air:if| and |air:else|. So: \begin{Verbatim} [ air:pattern :A ; air:alt :B ] . \end{Verbatim} Would become: \begin{Verbatim} [ air:if :A ; air:else :B ] . \end{Verbatim} \item The \Verb|air:assert| property now behaves like the \Verb|air:assertion| property, while \Verb|air:assertion| (and the old functionality of \Verb|air:assert|) is no longer supported. Thus: \begin{Verbatim} [ air:assert :A ; air:assertion :B ] . \end{Verbatim} Would become: \begin{Verbatim} [ air:assert [ air:statement :A ] ; air:assert :B ] . \end{Verbatim} \item The \Verb|air:rule| and \Verb|air:assert| properties are no longer permitted to accept \Verb|air:Abstract-rule| as a subject. They now take \Verb|air:Abstract-action| (like the bnode object of the old \Verb|air:alt|). To allow for the old actions, a new property has been added, \Verb|air:then|, that behaves like \Verb|air:alt|, except that the actions trigger on match. An \Verb|air:Abstract-action| may have only one of {\Verb|air:rule|, \Verb|air:goal-rule|, \Verb|air:assert|, \Verb|air:assert-goal|}. \end{enumerate} In summary, then: \begin{Verbatim} [ air:pattern :A ; air:rule :B ; air:goal-rule :C ; air:assert :D ; air:assert-goal :E ; air:assertion :F ; air:alt :AnAlt ] . :AnAlt [ air:rule :G ; air:assert :H ] . \end{Verbatim} Would now become: \begin{Verbatim} [ air:if :A ; air:then [ air:rule :B ] , [ air:goal-rule :C ] , [ air:assert [ air:statement :D ] ] , [ air:assert-goal [ air:statement :E ] ] , [ air:assert :F ] ; # Note that the air:alt no longer can hold both air:rule :G # and air:assert :H. # They must be added as objects of separate air:else statements now. air:else [ air:rule :G ] , [ air:assert [ air:statement :H ] ] ] . \end{Verbatim} \subsection{AIR Summary} The AIR language allows a user to write arbitrary policies, to draw arbitrary conclusions. It is a flexible, relatively easy to use and understand language. It draws upon some technologies that are decades old to perform its reasoning. It provides an interesting application of Semantic Web technologies and is a crucial cornerstone of this project. \section{Summary} The ongoing Semantic Web initiative has grown to include a number of technologies, such as RDF and SPARQL, for describing and manipulating data. This project makes use of a number of technologies, most importantly SPARQL and AIR. All of these technologies are fields of active research, and as such, subject to change in the future. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%