As of 5 May, This HTML version is out of date. In fact, the nearby PDF version might be out of date too; you have to check it out with SVN to be sure.

Under consideration for publication in Theory and Practice of Logic Programming (TPLP) special issue on Logic Programming and the Web.

# A Logic For the Web

Lalana Kagal
The Stata Center, Building 32
32 Vassar Street
Cambridge, MA 02139
USA

E-mail:
and TimBL? DanC? JimH?
$Revision$ of $Date: 2006/04/20$

#### Abstract

The Semantic Web is geared towards making the Web more machine understandable and involves technologies for automating the use of Web data. It mainly deals with knowledge models that promote common understanding of shared information. Though there are several technologies for representing and querying these models, there is still a requirement for an appropriate logic for the Web. The Web has several characteristics that need careful handling (i) openness where anyone can say anything, (ii) the possibility of inconsistencies, and (iii) the ability to use, extend, and combine Web resources. In this paper, we describe N3Logic, which was developed with these particular goals in mind to be a logic for the Web.

@@@ more ...... @@@

@@comment  Adding logic to the Web means to use rules to make inferences, choose courses of action and answer questions is the task before the Semantic Web community at the moment. A mixture of mathematical and engineering decisions complicate this task. The logic must be powerful enough to describe complex properties of objects but not so powerful that agents can be tricked by being asked to consider a paradox. Fortunately, a large majority of the information we want to express is along the lines of "a hex-head bolt is a type of machine bolt," which is readily written in existing languages with a little extra vocabulary. 
logic, Web, Semantic Web, scoped negation, quoting, RDF
@@

\newtheorem{definition}{Definition} % [section]
\newtheorem{example}{Example} % [section]
\newcommand{\pivot}[1]{\mathbin{\, {#1} \,}}
\newcommand{\Pivot}[1]{\mathbin{\; {#1} \;}}
\let\from=\leftarrow

## Introduction

@@comment The Semantic Web wants to make data available on the web more machine understandable and provide more automation. ..... Provide common models for describing meta data about resources and providing techniques for retrieving appropriate resources through querying at various levels of abstraction. Common models grounded in RDF. More automation requires reasoning. Why RDF ? What is the role of URIs ?

@@@Characteristics of the Web : openness, anyone can say anything, decentralized, motivate quoting...@@@

@@@Semantic Web, intro to RDF, URI, {s p o}@@@

@@@Data is expressed as graphs, graph like nature is imp for data. Thats the only way we can build systems that can be merged effortless. Using graph topology. Why did we pick N3 ?@@@

The abstract representation of RDF [w3c02rdfs] is a directed labeled graph -- i.e. nodes and arcs. A subset of the nodes have URIs; these are "named" nodes. Other nodes may not have (or may not yet have) identifying URIs but the graph can still describe properties of such nodes including relationships with other named and un-named nodes. The properties and relationships are the edges in the graph. Every edge has its own label and these same edge labels themselves can be used to name other nodes in the graph that represent the edge. This permits properties of edges to be represented in an RDF graph.

Through RDF the Semantic Web provides a unifying representation of richly structured data. And through the Web, application developers can share these data representations so that their applications can made "decisions" on the basis of combining data published in the Web.

@@@ N3 @@@@

N3Logic aims to do for logical information what RDF did for data: to provide a common data model and a common syntax, so that extensions of the language are made simply by defining new terms in an ontology. Declarative programming languages such as Scheme[scheme] already do this. However, they differ in their choice of pairs rather than the RDF binary relational model for data, and lack the use of universal identifiers as symbols. The main goal of N3Logic was to make a minimal extension to the RDF data model, so that the same language could be used for logic and data.

## N3Logic Features

The extensibility of RDF is deliberate so that a document may draw on predicates from many sources. The statement {s p o} expresses that the relationship denoted by p holds between the things denoted by s and o. The meaning of the statement {s p o} in general is defined by any specification for p. The Architecture of the Web specifies informally how information about the relation can be discovered [awww]. [@@@ more info about how@@@] N3Logic defines the semantics of certain properties. However, in a manner similar to RDF, N3Logic allows properties to be used that are not defined within N3Logic. The definitions of these external properties can be discovered and used. Clearly a system which includes further logical predicates, beyond those defined in N3Logic, whose meaning introduces greater logical expressiveness would change the properties of the logic.

One of the main motivations of N3Logic is to be useful as a tool in the open Web environment. The Web contains many sources of information, with different characteristics and relationships to any given reader. Whereas a closed system may be built based on a single knowledge base of believed facts, an open web-based system exists in an unbounded sea of interconnected information resources. This requires that an entity be aware of the provenance of information and responsible for its disposition. The language for use in this environment typically requires the ability to express which document or message said what, so the ability to quote subgraphs and match them against variable graphs is essential. This quotation and reference, with its inevitable possibility of direct or indirect self-reference, if added directly to first order logic presents problems such as paradox traps. To avoid this, N3Logic has deliberately been kept to limited expressive power: it currently contains no general first order negation. However, negated forms of many of the built-in functions are available.

Another goal of N3Logic is that information, such as but not limited to rules, which requires greater expressive power than the RDF graph, should be sharable in the same way as RDF can be shared. This means that one person should be able to express knowledge in N3Logic for a certain purpose, and later independently someone else can reuse that knowledge for a different unforeseen purpose. As the context of the latter use is unknown, this prevents us from making implicit closed assumptions about the total set of knowledge in the system as a whole.

Further, we require that other users of N3Logic in the Web have the ability to express new knowledge without affecting systems we have already built. This means that N3Logic must be fundamentally monotonic: the addition of new information from elsewhere, while it might cause an inconsistency by contradicting the old information (which would have to be resolved before the combined system is used), the new information cannot silently change the meaning of the original knowledge. The non-monotonicity of many existing systems follows from a form of negation as failure (NAF) in which a sentence is deemed false if it not held within (or, derivable from) the current knowledge base. It is this concept of current knowledge base, which is a variable quantity, and the ability to indirectly make reference to it which causes the non-monotonicity. In N3Logic, while a current knowledge base is a fine concept, there is no ability to make references to it implicitly in the negative. The negation provided is called Scoped Negation As Failure (SNAF) and is the ability for a specific given document (or, essentially, some abstract formula) to objectively determine whether or not it holds, or allows one to derive, a given fact.

## Motivating Scenario

We describe a web-based scenario that will be used to illustrate the different features of N3 logic. Consider a conference management system that handles different aspects of registration for conferences. It allows people to register by specifying their names, addresses, affiliations, and their Friend-of-a-Friend (foaf) [foaf] page. A foaf page includes information such as the organization the registrant works for, her/his current and past projects, and her/his interests. Using this information, the conference management system goes out onto the Web and retrieves relevant information. By reasoning over this information it is able to make inferences about the registrant such as whether the registrant is a vegetarian or not, which workshops she/he would be most interested in, whether she/he is a member of a certain professional organization, and whether the registrant is a student. This allows the conference management system to provide greater support in the registration process by figuring out what registration fees are applicable, whether to order vegetarian meals, and by suggesting appropriate workshops. In the following sections, we will show how N3Logic can be used to realize this web-based conference management system.

## Syntax/Notation

N3 provides a human-readable syntax for RDF and is a language that uses conventional unix-style punctuation, which is both more easily writable and readable than the RDF/XML syntax.

The N3 example below uses prefix for describing namespaces and defines conf1 an instance of the Conference class as defined in ex namespace. Please refer to the primer [bl05n3primer] for more details about the N3 syntax.

@prefix ex:  <http://example.org/conf.rdf#> .
conf1 rdf:type ex:Conference;
ex:EventName "WWW2006 Workshop on Models of Trust for the Web",
ex:Acronym "MTW06",
ex:homepage "http://www.l3s.de/~olmedilla/events/MTW06_Workshop.html".

N3Logic extends RDF and N3 with variables and nested graphs to enable the descriptions of rules and its syntax is as follows.

Production N3 syntax examples used below
symbol <foo#bar>    <http://example.com/> c d e f
variable Any symbol qualified by @forAll or @forSome in the same or an outer formula. x y z
formula {     ...    } F  G K
set of universat variables of F@forAll :x, :y.uvF
set of existential variables of F@forSome :z, :w.evF
set of statements of FstF
statement   ex:Joe   ex:color   "green". Fi   or  {s p o}
string "hello world" s
integer 34 i
list ( 1 2 ?x  <a> ) K  L
Element i of list LLi
length of list|L|
node see cfg n m
Set* {$1, 2, <a>$} R S T
The syntax of N3 is defined by the following context-free grammar
\begin{table*} [!t]

\comment{\begin{tabular}{|p{3cm}|p{5cm}|}}

\comment{\begin{tabular}{ll}}

\hline \hline

barename & [a-zA-Z\_][a-zA-Z0-9\_]\\

\hline

declaration & "@prefix" prefix explicituri \\

\hline

document   & statements\_optional EOF \\

\hline

dtlang &    "@" langcode \\
& \verb "^^" symbol \\
& void \\
\hline

existential/explicituri & \verb <[^>]*> \\

\hline

formulacontent &    statementlist \\
&  void \\
\hline

langcode & \verb [a-z]+(-[a-z0-9]+)* \\
\hline

literal & string dtlang \\
\hline

node  & literal \\
&    numericliteral \\
&    symbol \\
&    variable \\
&    \verb "(" pathlist ")" \\
&    \verb "@this" \\
&    \verb "[" propertylist "]" \\
&    \verb "{" formulacontent "\}"  \\
\hline

numericliteral &   \verb  [-+]?[0-9]+(\.[0-9]+)?(e[-+]?[0-9]+)? \\
\hline

object &    path \\
\hline

objecttail  &  "," object objecttail \\
&    void \\
\hline

path &    node pathtail \\
\hline

pathlist &    path pathlist \\
&    void \\

\hline

pathtail & \verb "!" path \\
&    \verb "^" path \\
&    void \\
\hline

\end{tabular}
\end{table*}
}}

## Informal Semantics

N3Logic includes properties which can be used to express rules, which talk about the provenance of information, contents of documents on the web, and so on. Just as OWL [owl] is expressed in RDF by defining properties, in the same way rules, queries, differences, and such can be expressed in RDF with N3Logic.

N3Logic allows statements to be made about, and to query, other statements such as the content of data in information resources on the Web. We have, in formulae, the ability to represent such sets of statements. To allow statements about them, we take some of the relationships we have defined and give them URIs so that these statements and queries can be written in N3.

While N3Logic properties can be used simply as ground facts in a database, is very useful to take advantage of the fact that in fact they can be calculated. In some cases, the truth or falsehood of a binary relation can be calculated; in others, the relationship is a function so one argument (subject or object of the statement) can be calculated from the other.

We also introduce a set of properties whose truth may be evaluated directly by machine. We call these "built-in" functions. The implementation as built-in functions is not in general required for any implementation of N3Logic, as they can always soundly be treated as ground facts. However, their usefulness derives from their implementation. We say that for example { 1 math:negation -1 } is entailed by calculation. Like other RDF properties, the set is designed to be extensible, as others can use URIs for new functions. When the truth of a statement can be deduced because its predicate is a built-in function, then we call the derivation of the statement calculated entailment.

The fact that the rule language and the data language are the same gives a certain simplicity (there is only one syntax) and completeness (rules can operate on themselves, anything written in N3 can be queried in N3). This would be broken if a special syntax were added for built-in functions and operators. Instead, these are simply represented as RDF properties. The N3 rule engine, cwm, when analyzing a rule prior to running it, treats specially those properties it knows as calculable functions which occur in the antecedent. Rules may have full N3, even with nested graphs, on both sides of the implication. This gives a form of completeness as rules can generate rules.

### Dereferencing URIs

We expose the web as a mapping between URIs and the information returned when such a URI is dereferenced, using appropriate protocols. In N3Logic, the information resource is identified by a symbol, which is in fact is its URI. The information is represented in formulae, so we represent the information retrieved as a formula. Not all information on the web is, of course in N3. However, we propose that N3 should be the interlingua. Therefore, from the point of view of this system, the semantics of a document is exactly what can be expressed in N3, no more and no less.

log:semantics is a logical property that represents the relation between a document and the logical expression which represents its meaning expressed as N3. The log:semantics of an N3 document is the formula achieved by parsing representation of the document. Currently, cwm parses RDF/XML, and N3 and its subsets.

In order to access a foaf file and store its N3 representation to a variable, log:semantics is used in the following manner

<http://www.example.org/myfoaf.rdf> log:semantics F.

The Architecture of the World Wide Web defines algorithms by which a machine can determine representations of document given its symbol - URI. For a representation in N3, this is the formula which corresponds to the document production of the grammar. For a representation in RDF/XML it is the formula which is the entire graph parsed. For any other languages, it may be calculated in as much a specification exists which defines the equivalent N3 semantics for files in that language.

The N3 formula of a document is not the semantics of the document in any absolute sense. It is the semantics expressed in N3. In turn, the full semantics of an N3 formula are grounded, in the definitions of the properties and classes used by the formula. In the HTTP space in which URIs are minted by an authority, definitive information about those definitions may be found by dereferencing the URIs. This information may be in natural language, in some machine-processable logic, or a mixture. Two patterns are important for the semantic web. One is the grounding of properties and classes by defining them in natural language. Natural language, of course, is not capable of giving an absolute meaning to anything in theory, but in practice a well written document carefully written by a group of people achieves a precision of definition which is quite sufficient for the community to be able to exchange data using the terms concerned. The other pattern is the raft-like definition of terms in terms of related neighboring ontologies. Other languages for web documents such as GRDDL [grddl] and RDF/A [rdfa] may be defined whose N3 semantics are therefore also calculable, and so they could be added in due course. @@@ is this required @@@

Relationship between resource, URI, string, N3 representation, and logic properties.

Other related logical properties include log:uri, log:content, log:parsedAsN3, and log:N3String.

• log:uri is the URI of a resource. Normal logic processing doesn't look at URIs but in some cases one needs to. This is a level-breaker: it lets an N3 system look at its infrastructure. It is a function which cwm can evaluate either way: resource to URI or URI to resource.
<http://example.org/> log:uri "http://example.org/"

• log:content of a document, is the string which was returned as the document contents when the URI of the resource was looked up.
• log:parsedAsN3 is the logical property that returns the formula got by parsing the string as a Notation3 document.
• log:N3String returns the string which expressed a certain formula in N3.

Figure relationship illustrates the relationship between URI, resource, string, N3 representation, and the different logical properties.

### Quoting

Various forms of literal value are allowed in RDF graphs, however the RDF standard does not provide for a RDF graph to be a data value. Remedying this allows one to express relationships between graphs, for example that a given graph is the RDF content of a particular document. The importance of agents on the semantic web being aware of where data has come from and where it is allowed to go to raises a need to be able to explicitly talk about graphs.

In our conference management example, we assume that there are several administrators. Each administrator specifies a list of people who may not register due to some reason.

ex:Joe  ex:said
{  mit:Peter policy:notpermitted ex:Register }.

### Rules

N3Logic extends RDF (and N3) with variables and nested graphs to enable the descriptions of rules. In its blank nodes (items in the graph not directly identifies by a URI) an RDF graph has a form of existential variable. Extending the language to allow variables existentially or universally quantified over a graph allows N3 to be used for a form of logic. The drive for this initially for N3Logic was so that, given variables, a rule is just a relation between two graphs. Variables are defined such that when substitution occurs in a graph, it also occurs in any nested graph.

In the <http://www.w3.org/2000/10/swap/log#> namespace, here given the prefix log:, the log:implies property expresses a rule, its subject being the antecedent graph, and the object being the consequent graph. It relates two formulae, expressing implication. A statement using log:implies cannot be calculated. It is not a built-in function, but a predicate which allows the expression of a rule. The shorthand => may be used for log:implies. N3 allows blank nodes in the conclusion of a rule, hence allowing the creation of new objects.

Continuing with our earlier example, though anyone can specify a list of people who cannot register, the conference management system only trusts administrators of the system with this information.

@forAll A, X.
A ex:said { X policy:notpermitted ex:Register }.
} => { X policy:notpermitted ex:Register }.

To do some inference within another set of rules, a useful relationship is log:conclusion. It is a property between a formula, and the result of thinking about it - running any rules in the formula on all the data and recursively. To make up the initial formula, log:conjunction can be used to merge a list of formulae.

@@@ example @@@

### Graph Functions

The logic function, log:includes, checks whether one graph is a subset of the other or in other words if one formula entails another formula. Together, log:semantics and log:includes allow rules to access the web, and to objectively check the contents of documents, without having to load them and believe everything they say.

The following rule states that if the home page of a registrant says that she/he is a vegetarian, then the system believes that she/he is a vegetarian.

@forAll X, H, HS.
{ X a ex:Registrant.
X foaf:homepage H.
H log:semantics HS.
HS log:includes { X a ex:Vegetarian }
} => { X a ex:Vegetarian}.

Whereas some datasets (such as a list of members of a club) are definitively complete, others (such as a set of temperature measurements) are not. This aspect of the Semantic Web makes negation as failure meaningless unless it is associated to a specific dataset. As a formula is a finite size, it can be tested for what it does not say. As a form of negation, log:notIncludes is completely monotonic. It can be evaluated by a mathematical calculation on the value of the two terms: no other knowledge gained can influence the result. This is the scoped negation as failure mentioned in the introduction. This is not a non-monotonic negation as failure.

Figure includes-not shows how log:includes and log:notIncludes relate to quoting.

Quoting and its relation to log:includes and log:notIncludes

We continue with our example. We assume that every school website has a property linking to its directory. The directory provides information about people including their foaf pages, their designation (such as student, faculty, associate), and their email address. Below we have a rule that states if the directory of the school does not specify that the person under consideration is a student, the system gives the person the academic rate but not the student rate.

@forAll X, H, HS, D, DS.
{ X a ex:Registrant.
X foaf:schoolHomepage H.
H log:semantics HS.
HS log:includes { H ex:directory D }.
D log:semantics DS.
DS log:notIncludes { X a ex:Student }
} => { X ex:registrationRate ex:AcademicRate }.

The effect of a default with an explicit domain is achieved with log:notIncludes, the negation of log:includes. Defaults can be handled by first running rules to work out everything that is specified, and then doing a log:notIncludes on the result as shown in the example above.

## Other Built-ins

math, string, date, crypto,

## Conclusion

The main goal of N3Logic is to extend the RDF data model, so that the same language could be used for logic and data.

The semantics of N3 have been defined, as have some built-in opertor properties which add logical inference using rules to the langauge, and allow rules to define inference which can be drawn from specific web documents on the web, as a function of ofther informatiuon about those documents.

The language has been found to have some useful practical properties. The separation betwen the Nottaion3 extensions to RDF and the logic properties has allowed N3 by itself to be used in many other applications directly, and to be used with other properties to provide other functionality such as the expression of patches (updates) [Diff].

The use of log:notIncludes to allow default reasoning without non-monotonic behavior achieves a desgn goal for disributed rule systems.

[scheme]
Scheme
[rdfa]
RDF/A Primer 1.0. Embedding RDF in XHTML. W3C Working Draft 10 March 2006
[grddl]
Gleaning Resource Descriptions from Dialects of Languages (GRDDL), W3C Team Submission 16 May 2005
[owl]
OWL Web Ontology Language Reference, W3C Recommendation February 2004
[bl01n3]
Notation 3 (N3) A readable RDF Syntax 1998
[bl00cwm]
Cwm : General-purpose Data Processor for the Semantic Web 2000
[bl05]
Primer: Getting into RDF and Semantic Web using N3 2005
[bl05experience]
Experience with N3 rules W3C Workshop on Rule Languages for Interoperability April 2005
[xml]
Extensible Markup Language (XML) 1.0 (Third Edition). W3C Recommendation February 2004
[w3c02rdfs]
RDF Vocabulary Description Language 1.0: RDF Schema, W3C Recommendation. February 2002
[foaf]
Friend of a Friend (FOAF) project
[awww]
The Architecture of the World Wide Web, W3C Recommendation