\chapter{Background}

\section{RDF Data Model}

RDF is a graph data model, wherehe nodes have labels\cite{rdf-semantics}. There are labelled arcs between the nodes. An RDF \emph{statement}, or triple, is a triple of $(subject, predicate, object)$, representing one arc of the graph. The subject and object nodes may be any of a number of things, including anonymous, or blank, nodes, literals, typed literals, and RDF symbols, uniquely represented using URIs. The predicates will be URIs.

There is a universe. Actually, there are many possible universes. Some of them are supported by the RDF graph. 

Central to the idea of RDF semantics is the idea of RDF entailment. Given two RDF graphs $A$ and $B$, the fragment $A$ entails $B$ if own can get from $A$ to $B$ using only the following rules
\begin{enumerate}
\item removing a statement
\item Take a subset $C \subset A'$, where $A'$ is the current graph. Take a term $x$. Add $C$ to the graph $A'$ with all instances of $x$ replaced by a new blank node $y$.
\end{enumerate}

Two graphs are equivalent if they entail each other. A graph is \emph{clean} if it is entailed by no strict subset of itself. 

While this is the definition of RDF entailment, there may be entailments under the semantics of some RDF based languages that do not appear in the base RDF. 

The RDF specification itself has some entailments not covered by the base RDF semantics. In particular, it defines a set of axiomatic triples. These triples are entailed by every RDF graph. \verb|rdf:_n rdf:type rdf:Property| is an axiom for all integers $n$, so this set is not finite.

\subsection{Modeling Data as RDF}
A relational database is a set of $k$-ary relations, $(n_1,n_2,\ldots,n_k)$. This is easy to model as RDF. We create $k$ predicates. Then, we have $(_n,r1,n1) (_n,r2,n2) \ldots (_n,r_k,n_k)$, where $_n$ is an anonymous node. In this way, a $k$-ary relation was encoded in $k$ ternary relations. This is often the best way to model data in RDF \footnote{It is of course possible to represent data as RDF modeled in ways that are not useful. RDF is general enough to encode anything. For instance, one can represent our data as in Appendix \ref{useless-rdf}. Nonetheless, data can usually be represented in ways that are reasonable. }. 

The W3C Semantic Web Best Practices Working Group\cite{bestpractices} publishes recommendations about how to represent data as RDF. Many things can be represented in multiple ways, and some ways are better for some things than others. 


\section{RDF Syntaxes}
%%% Should this go into an appendix?
The usual syntax for RDF \cite{w3c04rdfxml} is difficult for both people and computers, though for different reasons. Throughout this thesis, we will be using the Notation3 syntax \cite{bl01n3}. Notation3 is a syntax for RDF explained in \cite{N3Logic}. Subsets of Notation3 which do not have extensions to RDF have been defined; in particular, there is Turtle \cite{beckett04turtle}. 

A Notation3 statement is formed by $subject \quad predicate \quad object .$ , terminated as here with a period. Multiple statements with the same subject, or subject object, can be separated with a semicolon or comma, respectively. IRI references are enclosed in \verb|<>|. Literals are enclosed within quotes. 

As a shortcut for IRI references, we can declare \emph{prefixes}. Once a prefix is declared, it can be used in the form \qname{prefix:localname}. There are based on Qnames in XML \cite{xmlnames}, and have inspired the CURIE standard \cite{curie}. 

For more about the syntax of Notation3, see appendix \ref{notation3-syntax}

\section{RDFS Reasoning}
RDFS adds vocabulary to RDF to talk about types. The type of types, rdfs:Class, is defined. Simple ways of describing how types as properties interact, like domain, range, and sub-class, are defined. It is very difficult to write an inconsistent RDFS document
\footnote{Though it is not impossible to. See Appendix \ref{inconsistentrdfs} for the example given in the standard}.

RDFS associates with each node a set known as the \emph{class extension}. The class extension of a node $y$ is precisely the set of terms $x$ for which \verb|x rdf:type y| is true. Axioms like \verb|x rdf:subClassOf y| assert the subset relationship of the class extensions of $x$ and $y$, thus the truth of statements that were never directly asserted. 
RDFS entailment is defined by RDF entailment of these closure graphs under the RDF semantics. Note that there are also an infinite number of axiomatic triples in RDFS, that are entailed by every graph. 

\section{OWL}
This type of logical reasoning as in RDFS quickly becomes constraining. It would be nice to declare equality, and to say that things are not the members of classes. Indeed, one would like to have a very expressive logical language.

The problems one runs into with logic are inconsistency and undecidability. A na\"\i{}ve way of implementing a RDFS with more operators can easily run afoul of Russell's paradox\cite{russell}, allowing the definition of the class of all classes that do not contain themselves. Further, it would at times not be possible to definitively answer whether an item actually belongs to a set. Indeed, allowing any sort of complex operations to define compound predicates in terms of other predicates will almost certainly lead to undecidable problems.  

The solution for these problems is description logic. Description logics (DL) are subsets of first order logic, with the number of constructs allowed deliberately limited to insure decidability. The algorithms that people typically use for these are Tableau based algorithms\cite{sroiq}. 

Entailment in these logics is defined in terms of consistency. If $A \land \sim B$ is inconsistent, then $A$ must entail $B$. (If A is inconsistent, then it entails everything). The tableau can test for consistency well, therefore, it can test for entailment. \footnote{For descriptive DL's, a tableau is NEXPTIME worst case, while the problem can be solved in EXPTIME. Nonetheless, the time on problems people want to solve is far faster on a tableau than the methods which are EXPTIME.}

OWL was designed with that in mind. It defines a vocabulary. A document written using that vocabulary may be a serialization of a DL formula of type SHOIN(D). In that case, it is called OWL-DL, and the semantics are clear. Otherwise, it is called OWL FULL, and a different set of semantics, that may lead to undecidability, apply. 

We note that the entailment rules of OWL-DL are the entailment rules of the underlying description logic. Therefore, a document which is not the serialization of any description logic formula cannot be entailed by any OWL-DL graph. Because some axioms if OWL-DL are constructs built of multiple triples, simply removing a triple will make the graph invalid OWL-DL. This means that OWL-DL entailment is not a superset of even base RDF entailment, and the OWL-DL is therefore not RDF. The price we pay for representing other languages in RDF is that RDF has its own semantics and assumptions, which the representation may disallow. 

It is here that we must note that the OWL vocabulary includes terms from RDFS. Therefore, a document written using RDFS terms may have RDFS semantics, or OWL-DL semantics (OWL FULL semantics should be the same as RDFS semantics in that case). A document written with in OWL-DL will also have OWL FULL semantics, which may be different. All of these are different from the base RDF semantics. This can create headaches for RDF processors, as the RIF group has encountered \footnote{See \uri{http://lists.w3.org/Archives/Public/public-rif-wg/2007Jul/0033.html.}. Odd things happen when we combine different RDF languages.}. Nonetheless, in general the differences are minor and making a guess is unlikely to create completely wrong conclusions with our reasoners.  



\section{Rule Languages}
A different subset of FOL can be used for reasoning in RDF. A Rule, where a conjunction of facts implies a fact (or conjunction thereof), is a logical construct used many places. So called expert systems do not do full FOL reasoning, but only handle such rules. Rule languages have existed for a long time, and many exist, tailored to specific tasks\cite{microplanner}\cite{Kowalski74}.


\subsection{N3Logic}
We run into the problem that RDF is not very introspective. That is, RDF graphs are not good at all at talking about RDF graphs. Considering the importance on the Web of keeping track of who says what, it would be useful to be able to refer directly to RDF graphs in RDF.

Notation3, among other things, allows this. The types of nodes allowing as subjects or objects in Notation3, besides being URI's or literals, can also be Notation3 graphs. This allows for arbitrary levels of quoting.

We note that this quoting is just that, quoting. The semantics of RDF vocabularies like OWL allow for statements to change the meaning of other statements. It is important that these not interact with the contents of quoted formulae. As the classic example, we have the superman problem:
\begin{verbatim}
:LoisLane :says {:Superman a :FlyingThing} .
:Superman = :ClarkKent .
\end{verbatim}
It should not be true that we can infer from this that  \\ \verb|:LoisLane :says {:ClarkKent a :FlyingThing} .|. 

By adding syntax for variable declaration, Notation3 can be used to write rules. A simple N3 rule looks like 
\begin{verbatim}
{?x a :Man} => {?x a :Mortal}
\end{verbatim}
where \verb|=>| stands for \verb|<http://www.w3.org/2000/10/swap/log#implies>|. 

We note that it is impossible to write either NOT or OR in N3. The limitation on OR keep the reasoning steps for the rules simple. The limitation on NOT means that there is no way to express negation as failure.

The fact that there is no way to write NOT in N3 is actually a careful design decision. The world is bigger than any one reasoner knows. Just because at this time we do not know something, does not mean it is false. Reasoning where we don't know what we don't know is called open world reasoning. This leads to monotonic reasoning, which can make the rules to figure something more complicated, but gives nice properties if they ever find an answer. 

By contrast, many rules languages out there use negation as failure, which can test directly for the nonexistence of a statement. These resulting programs can be unstable, with the nonexistence of a statement leading to it existing. People have devised ways of understanding such programs. Such a program can have stable model semantics\cite{gelfond88stable}, well-founded semantics\cite{vangelder91wellfounded}\cite{xsb}, or completion semantics\cite{completion-semantics}. Regular Prolog has none of these, and is dependant on the ordering of the source file. All of these are subtly different. Having the programmer understand what indeed the program is doing could be difficult. 

We note that the actual syntax of N3 rules does not allow for any sort of ordering or prioritization of the rules; they are unordered. Besides that, there is no real limitation on the reasoning strategy used. Indeed, several reasoners have been written. In this way, arbitrary rules from different sources can be combined in a safe way. 

\subsubsection{Built In Predicates}
\label{builtin-n3}
We note that pure pattern matching rules are often not enough. While the Notation3 language allows for arbitrary quoting levels, these by themselves are difficult to use. One would like to use them on the Web, yet nothing intrinsic to the language allows a Notation3 formula to be connected to a document IRI. Further, the Notation3 rules are limited. There are many types of operations that are simply not possible with raw rules, and would necessitate expressing the data in a level breaking way to allow for doing those operations \footnote{As noted in Appendix \ref{turing}, if you build your data as a giant list, then Notation3 rules are Turing-complete}. 

Towards this end, Notation3 rules have builtin predicates. A builtin predicate is defined to be a predicate that in understood natively by the reasoner. It is assumed that all triples containing the predicate that match the builtin are true. Evaluation of the builtin may involve doing arbitrary work. Indeed, the code in table \ref{table:runaspython} would create a \verb|runAsPython| builtin, which would take the subject string, run it as a python program, and bind the object variable to what was printed.

One of these builtins in the \verb|log:notIncludes| predicate. It tests whether the subject graph does \emph{not} include the object graph. By doing so, it allows for tests of noninclusion without having to worry about the subtle issues of closed-world reasoning. 

We note that the semantics of builtin predicates is still not well defined. Indeed, subtle changes in reasoning strategy can change whether or not they match. The basic idea is that different builtins can require either the subject, object, both, or neither to be ground terms in order to match. The \verb|log:includes| predicate requires that the object be a N3 graph, but it may have free variables.

The implementation becomes difficult when dealing with builtins that can be functions either way. Let us look at one of them. \url{http://www.w3.org/2000/10/swap/math#negation} (to be referred to after this as \verb|math:negation|) is a property between two numbers. Given a number, it is the \verb|math:negation| of exactly one thing, and has exactly one \verb|math:negation|. Indeed therefore, given a subject we can compute the object, and given an object we can compute the subject. Therefore, given a pattern,
\begin{verbatim}
...
?x math:negation ?y
...
\end{verbatim}
we do not without further work know if it would match \verb|?x| given \verb|?y| or \verb|?y| given \verb|?x|. Indeed, it may depend on the facts being matched which way works.

It may seem odd that this is the case. If nothing in a pattern can match, then it fails. Matching a variable, removing a pattern triple and variable, can never make the match harder. Therefore, the order would seem to be clear.

The problem is that builtin predicates are still pattern triples. One can add to the knowledge base the triple \verb|1 math:negation 1 . | and it would match, despite being not being matched as a builtin predicate. Therefore, simply given a pattern it is not necessarily clear where it would start.

Further, this problem that builtins are triples too complicates the design of the matcher. Any pattern triple with a builtin predicate may match as a builtin or a pattern. Further, a pattern with a variable as the predicate may be any builtin at all. Indeed, CWM does not currently handle the last case correctly.

It may be argued that adding the statement \verb|1 math:negation 1 . | is inconsistent, that it introduces a contradiction. As such, the reasoner may be free to ignore that statement, because the builtin returns false on it. Nonetheless, the code does not currently make that assumption, and it seems it assumes that, given the open world, it simply does not know the statement exists if the builtin returns false.

Implementing a builtin predicate was designed to be easy. Indeed, in table \ref{table:runaspython} would be the code for the \verb|runAsPython| builtin, written for Cwm.
\begin{table}
\label{table:runaspython}
\begin{verbatim}
class RunAsPython(HeavyBuiltIn, Function):
       def evaluateObject(self, subj):
              stdout = sys.stdout
              sys.stdout = newStdout = StringIO()
              exec subj in {}
              sys.stdout = stdout
              return newStdout.getvalue()              
\end{verbatim}
\caption{The ``RunAsPython'' builtin}
\end{table}
Note that nowhere in CWM is there such a builtin. This would be a clear level breaker, and would not interact well with any other facts and rules in Notation3. 



