RDF Surfaces Primer

1. Introduction

This document presents a Notation3 sublanguage to express a revised RDF logic as envisioned by Pat Hayes in his 2009 ISWC Invited Talk: BLOGIC. RDF Surfaces logic can be thought as an implementation of Charles Sanders Peirce's Existential Graphs in RDF.

An RDF surface is a kind of sheet of paper on which RDF graphs can be written. All triples that are part of an RDF graph are then on this sheet of paper, including all [URI]s, literals, and Blank nodes. A sheet of paper can contain more than one RDF graph. An RDF graph can’t be split over multiple sheets of paper. However, one can copy an RDF graph from one sheet of paper to another sheet of paper.

Blank nodes are special. They can’t be copied to a new piece of paper. They can be thought of as scratches on a piece of paper. These scratches, or graffiti, are engraved into the piece of paper and can’t be transferred. When copying data with blank nodes onto a new sheet of paper, new scratches need to be made.

@prefix : <http://example.org/ns#> .

[] a :City .
[] a :Cat .

Positive surface

The default surface on which RDF graphs are written is a positive surface. For instance, the sheet of paper in Example 1 is an example of a positive surface. (In this document, we use a paper with a black border as a positive surface.) Any RDF triple written on this surface is interpreted as logical assertion (true). An empty sheet of positive paper is an empty claim and is treated as a logical tautology (true).

When there is more than one RDF triple on the surface, it is a logical conjunction (AND). If we interpret the sheets of paper with black borders in the examples above as positive surfaces, then they express:

• Example 1: true.

• Example 2: It is true that: Ghent a City.

• Example 3: It is true that: ∃ x : x a City.

• Example 4: It is true that: ∃ x , y : ( x a City ) AND ( y a Cat ).

The blank nodes need to be interpreted as existential quantified variables on logical paper.

Negative surface

In the same way that a positive surface asserts a logical truth, a negative surface asserts a logical negation. The examples below will use a sheet of paper with a red border as a negative surface.

An empty negative surface on the default positive surface expresses a logical contradiction. When one or more RDF graphs are written on a negative surface, they mean the negation of those RDF graphs.

A blank node on a negative surface is interpreted as a universal quantified variable. The reason is as follows:

NOT(∃ x : P(x)) ⇔ ∀ x : NOT(P(x))

Propositional logic

With combinations of conjunction, by putting triples on a positive surface, and negation, by putting triples on a negative surface, any compound truth-functional statement can be symbolized with positive and negative sheets of paper:

• The logical conjunction AND is given by putting RDF triples on a positive surface.

• The logical negation NOT is given by putting RDF triples on a negative surface.

• The logical disjunction OR can be made by a combination of positive and negative surfaces:

  • NOT ( P AND Q ) = NOT ( P ) OR NOT ( Q )

  • NOT ( NOT ( P ) AND NOT ( Q ) ) = P OR Q

• The logical implication → can be made with a combination of AND and OR:

  • P → Q = NOT ( P ) OR Q = NOT ( P AND NOT ( Q ) )

First-order logic

First-order logic can be added to the RDF surfaces by interpreting a blank node as an existential quantified variable, and using the rule that a universal quantified variable can be made from an existential quantified variable by placing it in an enclosing negative surface:

• A blank node on a positive surface references an existential quantified variable.

• A blank node on a negative surface references a universal quantified variable.

First-order logic in Notation3

RDF Surfaces provide a way to express the notion of positive and negative surfaces in Notation3 with help of the built-in log:onNegativeSurface. A log:onNegativeSurface is true when at least one of the nested triples in the object is false. A negative surface can be constructed from a single log:onNegativeSurface built-in. A positive surface can be constructed from double-nested log:onNegativeSurface built-ins.

The subjects of both built-ins are the blank nodes that need to be put on the surfaces (so that they become existential or universal quantified variables, depending on the nesting level of the surface).

@prefix : <http://example.org/ns#> .
@prefix log: <http://www.w3.org/2000/10/swap/log#> .

() log:onNegativeSurface {
  (_:X) log:onNegativeSurface {
    _:X a :City .
  }
} .

@prefix : <http://example.org/ns#> .
@prefix log: <http://www.w3.org/2000/10/swap/log#> .

_:X a :City .

@prefix : <http://example.org/ns#> .
@prefix log: <http://www.w3.org/2000/10/swap/log#> .

( _:X ) log:onNegativeSurface {
  () log:onNegativeSurface {
    _:X a :City .
  }
} .

@prefix : <http://example.org/ns#> .
@prefix log: <http://www.w3.org/2000/10/swap/log#> .

( _:X ) log:onNegativeSurface {
    _:X a :Problem .
} .

@prefix : <http://example.org/ns#> .
@prefix log: <http://www.w3.org/2000/10/swap/log#> .

( _:X ) log:onNegativeSurface {
    _:X a :Cat .

    () log:onNegativeSurface {
        _:X :is :Alive .
    } .

    () log:onNegativeSurface {
        _:X :is :Dead .
    } .
} .

@prefix : <http://example.org/ns#> .
@prefix log: <http://www.w3.org/2000/10/swap/log#> .

( _:X ) log:onNegativeSurface {
    _:X a :Cat ;
        :is :Alive .
    () log:onNegativeSurface {
        _:X :says :Meow .
    } .
} .

A surface can be queried by providing a query surface with the log:onNegativeAnswerSurface built-in. The results of this query will be the final results of the reasoning engine interpreting the surfaces.

@prefix ex: <http://example.org/ns#> .
@prefix log: <http://www.w3.org/2000/10/swap/log#> .

ex:Ghent a ex:City.

# Every city is a human community
( _:S ) log:onNegativeSurface {
    _:S a ex:City .
    () log:onNegativeSurface {
        _:S a ex:HumanCommunity .
    }.
}.

# Query
( _:S _:C ) log:onNegativeSurface {
    _:S a _:C .
    () log:onNegativeAnswerSurface {
      _:S a _:C .
    } .
} .

@prefix ex: <http://example.org/ns#> .

ex:Ghent a ex:City .
ex:Ghent a ex:HumanCommunity .

More test cases can be found at https://github.com/eyereasoner/rdfsurfaces-tests.

2. Document Conventions

Within this document, the following namespace prefix bindings to [URI]s are used:

3. Surface

Surfaces are written as triples where the subject is a list of zero or more blank nodes. The object is a graph term or a boolean literal. The blank nodes in the subject list are treated as marks on the object RDF graph. The predicate specifies the kind of surface. Any kind of surface may be used, but the following built-ins have special semantics:

A surface can contain zero or more other surfaces. These contained surfaces are "nested". Nested surfaces can share the same [URIs] and literals (by copying the data), but can’t share blank nodes. Any blank nodes that are written inside a surface (not as subject of an RDF Surface) are to be interpreted as coreferences to the blank node graffiti defined on a parent RDF Surface. If no such parent RDF Surface exists, then it is assumed that the blank node is a coreference to an implicitly declared blank node graffiti on the default positive surface.

@prefix ex: <http://example.org/ns#> .

( _:X ) ex:myFirstSurface {

    ex:Statement1 a ex:NiceStatement .
    _:X a ex:OtherStatement .
     
    () ex:mySecondSurface {
        _:X ex:is true . 
        _:Y a ex:AnotherStatement .

        ( _:X ) ex:myThirdSurface {
            _:X ex:is false .
        } .
    }.
} .

3.1. Default Positive Surface

The default positive surface claims that any RDF Graph that is placed on it is true. This is the current interpretation of RDF Semantics. When no surfaces are provided in an RDF document, the implicit default positive surface is assumed.

@prefix : <http://example.org/ns#> .
@prefix log: <http://www.w3.org/2000/10/swap/log#> .

:Alice a :Person .

@prefix : <http://example.org/ns#> .
@prefix log: <http://www.w3.org/2000/10/swap/log#> .

() log:onNegativeSurface {
  () log:onNegativeSurface {
    :Alice a :Person .
  } .
}

The semantics of the default positive surface are interpreted as a logical truth:

• An empty RDF graph on the default positive surface is a tautology.

• When a triple is placed on the default positive surface, the surface is valid when the triple is true.

• When two or more triples are placed on the default positive surface, the surface is valid when the logical conjunction of all triples is true.

:Alice a :Person AND 
:Alice :knows :Bob AND (
  :Bob a :Person AND 
  :Bob :knows :Alice
)

@prefix : <http://example.org/ns#> .
@prefix log: <http://www.w3.org/2000/10/swap/log#> .

:Alice a :Person .
:Alice :knows :Bob .

() log:onNegativeSurface {
  () log:onNegativeSurface {
    :Bob a :Person .
    :Bob :knows :Alice .
  } .
} .

When a blank node is marked on an evenly-nested negative surface, it is interpreted as an existential quantified variable in the scope of the nested surface.

∃ _:X : _:X a :Person AND _:X :knows :Alice

NOT ( NOT ( ∃ _:X : _:X a :Person AND _:X :knows :Alice ) )

@prefix : <http://example.org/ns#> .
@prefix log: <http://www.w3.org/2000/10/swap/log#> .

() log:onNegativeSurface {
  ( _:X ) log:onNegativeSurface {
    _:X a :Person .
    _:X :knows :Alice .
  } .
} .

In RDF Surfaces, a default positive surface is implicitly assumed for each RDF document. On this default positive surface, all existential variables are implicitly quantified. Example 20 can be rewritten as:

@prefix : <http://example.org/ns#> .
@prefix log: <http://www.w3.org/2000/10/swap/log#> .

_:X a :Person .
_:X :knows :Alice .

When a blank node is marked on an oddly-nested negative surface, it is interpreted as a universal quantified variable in the scope of the nested surface.

∀ _:X : _:X a :Person AND _:X :knows :Alice

NOT( ∃ _:X : NOT ( _:X a :Person AND _:X :knows :Alice ) )

@prefix : <http://example.org/ns#> .
@prefix log: <http://www.w3.org/2000/10/swap/log#> .

(_:X) log:onNegativeSurface {
  () log:onNegativeSurface {
    _:X a :Person .
    _:X :knows :Alice .
  } .
} .

3.2. Negative Surface

A negative surface claims that any RDF Graph that is placed on it is false. The interpretation of the negative surface is the negation of the RDF Graph that is placed on it.

The semantics of a negative surface are interpreted as a logical falsehood:

• An empty negative surface is a contradiction.

• When a triple is placed on a negative surface, the surface is valid when the triple is false.

• When two or more triples are placed on a negative surface, the surface is valid when the logical conjunction of all triples is false.

:Alice a :Person AND 
:Alice :knows :Bob AND NOT (
  :Bob a :Person AND 
  :Bob :knows :Alice
)

@prefix : <http://example.org/ns#> .
@prefix log: <http://www.w3.org/2000/10/swap/log#> .

:Alice a :Person .
:Alice :knows :Bob .

() log:onNegativeSurface {
    :Bob a :Person .
    :Bob :knows :Alice .
} .

When a blank node is marked on a negative surface, it should be interpreted as an existential quantified variable in the scope of the negative surface.

:Alice a :Person AND 
:Alice :knows :Bob AND NOT (
  ∃ _:X :
     _:X a :Person AND 
     _:X :knows :Alice
)

:Alice a :Person AND 
:Alice :knows :Bob AND 
  ( ∀ _:X :
     NOT (
      _:X a :Person AND 
      _:X :knows :Alice
    )
  ) 
)

@prefix : <http://example.org/ns#> .
@prefix log: <http://www.w3.org/2000/10/swap/log#> .

:Alice a :Person .
:Alice :knows :Bob .

( _:X ) log:onNegativeSurface {
    _:X a :Person .
    _:X :knows :Alice .
} .

When two or more negative surfaces are nested in a parent negative surface, it should be interpreted as a logical disjunction.

:Alice a :Person OR
:Bob a :Person OR
:Charly a :Person 

NOT (
  NOT ( :Alice a :Person ) AND
  NOT ( :Bob a :Person ) AND
  NOT ( :Charly a :Person )
)

@prefix : <http://example.org/ns#> .
@prefix log: <http://www.w3.org/2000/10/swap/log#> .

:Alice a :Person .
:Alice :knows :Bob .

() log:onNegativeSurface {
    () log:onNegativeSurface {
      :Alice a :Person .
    } .

    () log:onNegativeSurface {
      :Bob a :Person .
    } .

    () log:onNegativeSurface {
      :Charly a :Person .
    } .
}.

Other logical truth functions can be built with combinations of AND and NOT, such as the following:

• Disjunction: P ∨ Q : NOT ( NOT ( P ) AND NOT ( Q ) )

• Material implication P → Q : NOT ( P AND NOT Q ) .

• Converse implication P ← Q : NOT ( NOT ( P ) AND Q ) .

• Biconditional (P → Q) ∧ (Q → P) : NOT ( P AND NOT Q ) AND NOT ( Q AND NOT P )

Negative surfaces should also follow the law of double negation elimination: P = NOT ( NOT ( P ) ).

3.3. Answer Surface

TODO

4. Examples

As an illustration of RDF Surface, we offer a graph traversal example. Example 26 provides information about French roads where some roads are blocked due to road works. In this example, we use the predicate :oneway to indicate that a connection is possible from one city to another. To deny this connection, we use a negative surface.

@prefix : <urn:example:> .

:Paris :oneway :Orleans .
:Paris :oneway :Chartres .
:Paris :oneway :Amiens .
:Orleans :oneway :Blois .
:Orleans :oneway :Bourges .
:Blois :oneway :Tours .
:Lemans :oneway :Angers .
:Lemans :oneway :Tours .
:Angers :oneway :Nantes .

# blocking some roads
() log:onNegativeSurface {
    :Chartres :oneway :Lemans .
}.

Next, we would like to provide the logic of a "path" through the French road system. We would like to share an RDF document that states: "When there is a :oneway from one city to another city, then there is a :path from the first to the second". Or, expressed in a symbolic form:

∀ _:A, _:B : ( _:A :oneway _:B ) IMPLIES ( _:A :path _:B )

These paths are transitive. When there is a path from A to B and a path from B to C, there is a path from A to C. Or, expressed in a symbolic form:

∀ _:A, _:B, _:C : ( ( _:A :path _:B ) AND ( _:B :path _:C ) ) IMPLIES ( _:A :path _:C )

Using the patterns for IMPLIES from the previous sections these logical formulas can be written as RDF Surfaces in Example 27.

@prefix log: <http://www.w3.org/2000/10/swap/log#> .
@prefix : <urn:example:> .

# oneway subproperty of path
( _:A _:B ) log:onNegativeSurface {
    _:A :oneway _:B .
    () log:onNegativeSurface {
        _:A :path _:B .
    } .
} .

# path transitive property
( _:A _:B _:C ) log:onNegativeSurface {
    _:A :path _:B .
    _:B :path _:C .
    () log:onNegativeSurface {
        _:A :path _:C .
    } .
} .

Based on the RDF documents in Example 26 and 27, we can construct a query to find out which paths are possible that end in Nantes. For this, we use a specialized answer surface that expresses: "If there is some path from A to Nantes, then this is an answer". This is expressed as RDF Surfaces in Example 28.

@prefix log: <http://www.w3.org/2000/10/swap/log#> .
@prefix : <urn:example:> .

(_:A) log:onNegativeSurface {
    _:A :path :nantes .
    () log:onNegativeAnswerSurface {
        _:A :path :nantes .
        :test :is :true .
    } .
} .

Combining the RDF documents from Examples 26, 27, and 28, an RDF Surfaces reasoner should give as answers:

:Angers :path :Nantes .
:Lemans :path :Nantes .

If we remove the negative surface around :Chartes :oneway :Lemans, an RDF Surfaces reasoner should provide more answers:

:Angers :path :Nantes .
:Lemans :path :Nantes .
:Chartres :path :Nantes .
:Paris :path :Nantes .

For more RDF Surfaces examples, see:

• https://github.com/eyereasoner/rdfsurfaces-tests