A Logic For the Web

Introduction

@@@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:address "mtw@www.org",
      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.

\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.

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

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

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

@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}.

@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 }.

Other Built-ins

math, string, date, crypto,

Related Work

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.