Variables

• A term is a direct constituent of
  • a list $l$ if it is
    • an element of $l$, or
    • a direct constituent of a list-element of $l$;
  • a triple $t$ if it is
    • the subject, predicate or object of $t$, or
    • a direct constituent of the subject, predicate or object of $t$;
  • a graph $G=(U, E, F)$ if it is
    • a direct constituent of a triple $t ∈ F$.
  We denote the set of direct constituents of a graph $G$ as $DC(G)$. Variables, IRIs, literals and graph terms do not have direct constituents.
• A term is a constituent of a graph $G_1$ if it is either
  • a direct constituent of $G_1$, or
  • a constituent of graph $G_2$, where the graph term $<G_2>$ is a direct constituent of $G_1$.
  We denote the set of constituents of a graph $G$ as $C(G)$.

• :socrates :says {_:x a :Mortal}.
  becomes
  $(\{\},\{\},\{(\text{:socrates}, \text{:says}, <\{\},\{x\},\{(x,\text{rdf:type}, \text{:Mortal} )\}>) \})$
  • Direct constituents: $\text{:socrates}, \text{:says}, <\{\},\{x\},\{(x,\text{rdf:type}, \text{:Mortal} )\}>$.
  • Constituents: all direct constituents (see above), $x,\text{rdf:type}, \text{:Mortal}$

Note that the definition makes a difference between graphs and graph terms. A graph term is a direct constituent of the graph ("containing graph") in which it occurs as a triple component. However, the direct constituents of the graph term's graph, and their direct constituents (and so on), are not direct constituents of the containing graph. Rather, they are constituents of the containing graph. This difference is crucial for the definitions below: a graph is not the same as a graph term.

With that definition, we now introduce free variables: these are variables which occur directly or nested in the graph but which are not covered by a quantification set.

• $FV(x) = \emptyset$ if $x ∈ R ∪ L$,
• $FV(x) = \{x\}$ if $x ∈ V$,
• $FV(x) = FV(x_1) ∪ … ∪ FV(x_n)$ if $x=(x_1 … x_n)$ is a list,
• $FV(x) = FV(s) ∪ FV(p) ∪ FV(o)$ if $x=(s,p,o)$ is a triple,
• $FV(x) = ⋃_{t ∈ x} FV(t)$ if $x$ is a set of triples,
• $FV(x) = FV(F)\setminus(U ∪ E)$ if $x=<U,E,F>$ is a graph term.

• We say that $v$ is free in $G$ iff $v\not\in U\cup E$ and there exists $x\in DC(G)$ such that $v\in FV(x)$;
• Otherwise we call $v$ scoped in $G$;
• We denote the set of variables which are free in $G$ as $FV(G)$.

Examples:

1. In $(\{x\},\{y\},\{(x, \text{:knows}, y) \})$ all variables are scoped.
2. In $(\{\},\{y\},\{(x, \text{:knows}, y) \})$ the variable $x$ is free while $y$ is scoped.
3. In $(\{\},\{\},\{(y, \text{:says}, <\{\},\{x\},\{(x,\text{rdf:type}, \text{:Mortal} )\}>) \})$, the variable $x$ is scoped while the variable $y$ is free.

This enables us to introduce the notion of closed graphs and ground terms.

• A graph $G=(U,E,F)$ is closed if all variables $v\in C(G)\cap V$ are scoped in $G$.
• A term is ground if it is either
  • an IRI,
  • a Literal,
  • a list of ground terms or the empty list,
  • a graph term $<G>$ if $G$ is closed.

We denote the set of ground terms as $T_G$.

A triple is ground if all of its direct constituents are ground.

A graph $G=(U,E,F)$ is ground if $E=U=\emptyset$ and all triples in $F$ are ground.

An abstract N3 graph which is constructed from a graph in the direct N3 syntax cannot contain free variables. However, when considering a specific graph term in isolation, all variables that are quantified outside that graph term will appear to be free in that graph term.
For instance, the following N3 concrete syntax:
    `_:y :says { ?x :knows :bob }.`
corresponds to
$\qquad (\{x\}, \{y\}, \{( \text{:y}, \text{:says}, <\{\},\{\},\{(x, \text{:knows}, \text{:bob})\}>)\})$
When considering the graph term's graph in isolation:
    `({},{},{(x, :knows, :bob)})`
the variable $x$ will be a free variable (as it was quantified in the containing N3 graph).

An abstract graph $G=(U,E,F)$ can also contain quantified variables $v\in U\cup E$ which do not occur in any triple of $F$. These variables do not contribute to the interpretation of the graph. In order to simplify our considerations for the following sections, we introduce the notion of normalised graphs:

For each graph $G=(U,E,F)$, we call $G^N=(U\cap (FV(F)), E\cap(FV(F)), F)$ the normalisation of $G$.

1. $(\{x,z\},\{y\},\{(x, \text{:knows}, y) \})^N=(\{x\},\{y\},\{(x, \text{:knows}, y) \})$.
2. $(\{x_1, x_2, x_3\},\{y_1, y_2, y_3\},\{(\text{:socrates}, \text{:knows}, \text{:plato}) \})^N=(\{\},\{\},\{(\text{:socrates}, \text{:knows}, \text{:plato}) \})$.
3. $(\{x\},\{y\},\{(y, \text{:says}, <\{\},\{x\},\{(x,\text{rdf:type}, \text{:Mortal} )\}>) \})^N=$
   $(\{\},\{y\},\{(y, \text{:says}, <\{\},\{x\},\{(x,\text{rdf:type}, \text{:Mortal} )\}>) \})$.

Isomorphisms

For two mappings $M$ and $N$ from terms to terms, we define their combination as follows:

• $M\bullet N(v)=N(v)$ if $v\in dom(N)$
• $M\bullet N(v)=M(v)$ if $v\not\in dom(N)$

With combinations of mappings we can define isomorphisms between abstract N3 graphs:

Let $M$ be a bijection between the variables of $V$, we define:

• a graph $G_1$ is isomorphic to $G_2$ under $M$ iff, $G_1^N =(U_1,E_1,F_1)$ and $G_2^N=(U_2,E_2,F_2)$ and
  • $M(U_1) := \{M(u)|u\in U_1\}= U_2$ and $M(E_1):= \{M(e)|e\in E_1\}= E_2$
  • $F_1$ is isomorphic to $F_2$ under $M$
• a set of triples $F_1$ is isomorphic under $M$ to a set of triples $F_2$ if there is a bijection $N$ from $F_1$ to $F_2$ such that, for each triple $t_1=(s_1, p_1, o_1)\in F_1$, $N((s_1, p_1, o_1))=(s_2, p_2, o_2)\in F_2$ and $s_1$, $p_1$ and $o_1$ are isomorphic under $M$ to $s_2$, $p_2$ and $o_2$ respectively
• a variable $v$ is isomorphic under $M$ to $M(v)$,
• an IRI or Literal is isomorphic to itself,
• a list $l_1=(l_{1,1} \ldots l_{1,n})$ is isomorphic under $M$ to a list $l_2=(l_{2,1} \ldots l_{2,m})$ if $m=n$ and for each $0\leq i\leq n$, the element $l_{1,i}$ of $l_1$ is isomorphic under $M$ to the corresponding element $l_{2,i}$ of $l_2$,
• a graph term $< G_1 >$ is isomorphic under $M$ to $< G_2 >$ if for $G_1^{N} =(U_1,E_1,F_1)$ and $G_2^{N}=(U_2,E_2,F_2)$ there is a bijection $P$ between $U_1 \cup E_1$ and $U_2 \cup E_2$ such that $G_1$ is isomorphic to $G_2$ under $M\bullet P$.

We call a graph $G_1$ isomorphic to a graph $G_2$, written as $G_1\simeq G_2$, if there exists some $M$ such that $G_1$ is isomorphic to $G_2$ under $M$.

If $G_1$ is isomorphic to $G_2$ then $G_2$ is also isomorphic to $G_1$.

Consider the following graphs:

• $G_1 = (\{\}, \{x\}, \{(x, \text{:knows}, \text{:p}), (\text{:p}, \text{;says} <\{\}, \{x\} \{(x, \text{rdf:type}, \text{:Genius})\}>)\})$
  – in concrete syntax: _:x :knows :p. :p :says {_:x a :Genius}.
• $G_2: = (\{\}, \{y\}, \{(y, \text{:knows}, \text{:p}), (\text{:p}, \text{:says} <\{\}, \{z\} \{(z, \text{rdf:type}, \text{:Genius})\}>)\})$
  – in concrete syntax: {_:y :knows :p. :p :says {_:z a :Genius}.}
• $G_3: = (\{\}, \{y\}, \{(y, \text{:knows}, \text{:p}), (\text{:p}, \text{:says} <\{\}, \{x, z\} \{(x, \text{rdf:type}, z)\}>)\})$
  – in concrete syntax: {_:y :knows :p. :p :says {_:x a _:z}.}

Then $G_1$ is isomorphic to $G_2$:

• define $M = {x\mapsto y}$,
• and for the inner graph term, $P = {x\mapsto z}$.

$x$ as the subject of the first triple is replaced with $M(x)=y$, while $x$ as the subject of the unique triple in the graph term is replaced with $M\bullet P(x) = z$ (P overrides M).

On the other hand, G1 is not isomorphic to G3.

Ground graphs

Given $I$ a basic interpretation, we recursively define $I(x) =$

• $D_I(x)$ if $x$ is an IRI or a Literal,
• $(I(x_1), I(x_2),..., I(x_n))$ if $x$ is a list $(x_1, x_2, ..., x_n)$ and all $I(x_i)$ are defined,
• $Q_I(x)$ if $x$ is a ground graph term,
• $I(x)=\textit{true}$ if $x=(s, p ,o)$ is a ground triple and $(I(s), I(p) ,I(o))\in EXT_I$, otherwise $I(x)=\textit{false}$,
• $I(x)=\textit{false}$ if $x=F$ is a set of ground triples and $I(t)=\textit{false}$ for some triple $t\in F$, otherwise $I(x) =\textit{true}$,
• $I(F)$ if $x=(\emptyset, \emptyset, F)$ is a ground graph

Graphs with variables

?x :says {?x :is :wise}.

$G = (\{x\}, \{\}, \{(x, \text{:says}, <\{\}, \{\}, \{(x, \text{:is}, \text{:wise})\}>)\})$.

$G_{bob} = (\{\}, \{\}, \{(\text{:bob}, \text{:says}, <\{\}, \{\}, \{(\text{:bob}, \text{:is}, \text{:wise})\}>)\})$

The semantics for ground graphs maps IRIs to not further specified domain elements, while ground graph terms are mapped to an isomorphic version of themselves. The interpretation of the above example $I(G_{bob})$ will be true if $(D_I(\text{:bob}), D_I(\text{:says}), Q_I(<\{\}, \{\}, \{(\text{:bob}, \text{:is}, \text{:wise})\}>)\in EXT_I$.

If we revert back to our original example with variables, a regular valuation function (such as the mapping A used for blank nodes in [[RDF11-MT]]) will simply replace both occurrences of variable $x$ with a domain element $\delta_i$ from $\Delta_I$. In that case, $Q_I$ will have to map the graph term $<\{\}, \{\}, \{(\delta_i, \text{:is}, \text{:wise})\}>$ to an isomorphic copy. However, the isomorphism is only defined for concrete N3 terms, and not domain elements. If not applying the valuation function to the graph term, $Q_I$ will have to map the graph term $<\{\}, \{\}, \{(x, \text{:is}, \text{:wise})\}>$, which is however no longer ground as its graph is no longer closed ($x$ is quantified outside of the graph). In our basic interpretation, the mapping $Q_I$ is only defined for ground graph terms. We thus need to first ground these kinds of leaked variables, i.e., variables that become free when considering the graph term in isolation (as is required when determining isomorphisms).

We need to extend RDF's classical semantic condition for blank nodes and use a so-called assignment, which, instead of simply mapping variables to resources, maps variables to pairs of resources and term representations:

Given a basic interpretation $I$ and a set of variables $V_1$. We call a mapping $A$ from $V_1$ to $Δ_I\times T_G$ such that $A(v)=(A_1(v),A_2(v))$ and $I(A_2(v))=A_1(v)$ an assignment for $V_1$.

We can consider both values $A_1$ and $A_2$ of an assignment $A(v)=(A_1(v), A_2(v))$ as separate mappings. The mapping $A_2$ assigns variables to terms, and will be used to ground free variables within graph terms. Note that given an interpretation $I$ and two assignments $A$ for a set $V_1$, and $B$ for a set $V_2$ of variables, the combination $A\bullet B$ is again an assignment for $V_1\cup V_2$.

Let $G=(U,E,F)$ be a graph and let $M$ be a mapping from a set of variables $V$ into a set $S$. A total application $M^t(G)$ of $M$ is defined as follows:

$M^t(G) = (U, E, \{ (M^t(s), M^t(p), M^t(o)) | \; (s, p, o) \in F \})$ such that:

• If $x\in FV(G)$ then $M^t(x)=M(x)$.
• If $x=(x_1\ x_2\ \ldots \ x_n)$ is a list, then $M^t(x)=(M^t(x_1)\ M^t(x_2)\ \ldots \ M^t(x_n))$.
• If $x=<H>$ is a graph term then $M^t(x) = <M^t(H)>$.
• $M^t(x)=x$ else.

$M^t($$<\{\},\{y\},\{(x, \text{:hasMother}, y)\}>$$)$ $=$$<\{\},\{y\},\{(tom, \text{:hasMother}, y)\}>$

The definition of total applications enables us to define interpretations with assignment:

For a closed graph $G=(U,E,F)$, a basic interpretation $I$ and an assignment $A$ on the set of variables $U\cup E$, we define $I[A](x)$ as:

• $A_1(x)$ if $x ∈ dom(A)$ and $x$ is a direct constituent of $G$,
• $(I[A](x_1) \ldots I[A](x_n))$ if $x=(x_1 \ldots x_n)$ is a list,
• $Q_I(A_2^t(x))$ if $x$ is a graph term, where $A_2^t$ represents the total application of $A_2$,
• $I(x)$ otherwise.

For a closed graph $G=(U, E, F)$ and a basic interpretation $I$, we say $I(G)=\textit{true}$ or interpretation $I$ satifies $G$, if for all assignments $A$ for $U$ (universal variables) there exist an assignment $B$ for $E$ (existential variables) such that $I[A\bullet B](F)=\textit{true}$. We also write that as $I\models G$.

Note that the interpretation of a variable $x$ depends on its position in a graph. In the expression $(\emptyset, \emptyset,\{(x, \text{:p}, <\emptyset, \emptyset, \{(x, \text{:q}, \text{:r})\}>)\})$, the first $x$ is interpreted as $A_1(x)$ while the second is interpreted as $A_2(x)$. The connection between these two values is established by the condition that $I(A_2(v))=A_1(v)$.

For instance:

$I(\{x\}, \{\}, \{(x, \text{:says}, < \{\}, \{\}, \{( x, \text{:is}, \text{:wise} )\} >)\})$

will be true if for all assignments $A:\{x\}\rightarrow Δ_I\times T_G$, the following is true:

$I(\{(A_1(x), \text{:says}, < \{\}, \{\}, \{ (A_2(x), \text{:is}, \text{:wise}) \} >)$

Let $G=(U,E,F)$ be a graph. We say that $G$ is true under the interpretation $I$ and the assignment $A$ if $I[A]\models G$. That is, for each assignment $A^1$ for the variables in $U$ there exists an assignment $B^1$ for the variables in $E$ such that $I[A\bullet A^1\bullet B^1](F)=true$.

This last definition handles all variables occurring freely in a graph as universally quantified.

Basic entailment

Let $G$ and $H$ be two graphs, we say that $G$ b-entails $H$, noted $G ⊨ H$, if and only if every interpretation $I$ that satisfies $G$ $(I ⊨ G)$ also satisfies $H$ $(I ⊨ H)$.

• $(\{\},\{\},\{(\text{:socrates}, \text{:knows}, \text{:plato})\})$
  – in concrete syntax: :socrates :knows :plato.
  b-entails
  $(\{\},\{x\},\{(\text{:socrates}, \text{:knows}, x)\})$
  – in concrete syntax: :socrates :knows _:x.
• $(\{x\},\{\},\{(x, \text{:knows}, \text{:plato})\})$
  – in concrete syntax: ?x :knows :plato.
  b-entails
  $(\{\},\{\},\{(\text{:socrates}, \text{:knows}, \text{:plato})\})$
  – in concrete syntax: :socrates :knows :plato.
• $(\{x\},\{\},\{(<\{\},\{\},\{(x, \text{rdf:type}, \text{:Human})\}>, \text{log:implies}, <\{\},\{\},\{(x, \text{rdf:type}, \text{:Mortal})\}>)\})$
  – in concrete syntax: {?x a :Human} => {?x a :Mortal}.
  b-entails
  $ (\{\},\{\},\{(<\{\},\{\},\{( \\ \qquad \text{:socrates}, \text{rdf:type}, \text{:Human})\}>, \\ \qquad \text{log:implies}, \\ \qquad <\{\},\{\},\{(\text{:socrates}, \text{rdf:type}, \text{:Mortal}\}> \\ ))\})$
  – in concrete syntax: {:socrates a :Human} => {:socrates a :Mortal}.
• $(\{\},\{\},\{(\text{:socrates}, \text{:says}, <\{\},\{\},\{(\text{:socrates},\text{rdf:type}, \text{:Mortal} )\}>) \})$
  – in concrete syntax::socrates :says {:socrates a :Mortal}.
  b-entails
  $(\{\},\{x\},\{(x, \text{:says}, <\{\},\{\},\{(x,\text{rdf:type}, \text{:Mortal} )\}>) \})$
  – in concrete syntax: @forSome :x. :x :says { :x a :Mortal}.

• $ \{\},\{\},\{ \\ \qquad (\text{:socrates}, \text{rdf:type} \text{:Human}), \\ \qquad (<\{\},\{\},\{ (\text{:socrates}, \text{rdf:type}, \text{:Human})\}>, \\ \qquad\ \ \text{log:implies}, \\ \qquad\ \ <\{\},\{\},\{(\text{:socrates}, \text{rdf:type}, \text{:Mortal})\}>) \\ \})$
  – in concrete syntax: :socrates a :Human. {:socrates a :Human} => {:socrates a :Mortal}.
  does not b-entail
  $(\{\},\{\},\{(\text{:socrates}, \text{rdf:type}, \text{:Mortal})\})$
  – in concrete syntax: :socrates a :Mortal.
• $(\{\},\{\},\{(\text{:socrates}, \text{:says}, <\{\},\{\},\{(\text{:socrates},\text{rdf:type}, \text{:Mortal} )\}>) \})$
  – in concrete syntax: :socrates :says {:socrates a :Mortal}.
  does not b-entail
  $(\{\},\{\},\{(\text{:socrates}, \text{:says}, <\{\},\{x\},\{(x,\text{rdf:type}, \text{:Mortal} )\}>) \})$
  – in concrete syntax: :socrates :says {_:x a :Mortal}.
  and it does also not b-entail
  $(\{\},\{x\},\{(x, \text{:says}, <\{\},\{x\},\{(x,\text{rdf:type}, \text{:Mortal} )\}>) \})$
  – in concrete syntax: _:x :says {_:x a :Mortal}.

Constraints for `log:implies`

The aim of the predicate log:implies is to provide a form of logical implication. This interpretation acts on the ground terms which are true under basic interpretations.

If $t = (s, \text{log:implies}, o )$ is a triple, then $I[A\bullet B]\models_{log} t$ if:

• $I[A\bullet B](s)=< G_1>$ and $I[A\bullet B](o)=<G_2>$ are graph terms and $I[A\bullet B]\models_{log} G_2$ holds if $I[A\bullet B]\models_{log} G_1$, or
• $I[A\bullet B](s)=<G_1>$ is a graph term and $I[A\bullet B](o)=I(\text{false})$ and $I[A\bullet B]\not\models_{log} G_1$, or
• $I[A\bullet B](s)$ is not a graph term or $I[A\bullet B](o)$ is neither a graph term nor $I(\text{false})$.

The first bullet of the above definition clarifies how implications with graph terms $< G_1>$ and $<G_2>$ in subject and object position are interpreted. Note that under the simple interpretation these graph terms are ground, that is, $I[A\bullet B](G_1)$ and $I[A\bullet B](G_2)$ are closed graphs. To determine the meaning of the implications these closed graphs are further interpreted using $I[A\bullet B]$ as an interpretation. The log-interpretation thus interprets the basic interpretation of a graph term.

The second bullet covers implications with the boolean literal false in the consequence. In log-semantics this literal is understood as truth constant "false" (or $\bot$). Note that the interpretation process here consists of two steps: we first consider the basic interpretation of the implication triple which needs to be true and then we test whether - using the same interpretation as a log interpretation - the premise is false. However, the mere fact that a closed graph $G_1$ is false under an interpretation $I$ ($I\not\models_{log} G_1$), does not allow us to conclude that $I\models_{log} (\{\}, \{\}, \{ (< G_1>, \text{log:implies}, \text{false})\})$.

The last bullet ensures that the truth value of triples having log:implies in predicate position but no graph term or truth value in subject or object position like for example :socrates log:implies :plato. is only determined by the basic interpretation of the triple. That is, log:implies only has a special meaning when used with graph terms and/or truth values.

Log entailment

Let $G$ and $H$ be two graphs, we say that $G$ log-entails $H$, written as $G ⊨_{log} H$, if and only if every interpretation $I$ that log satisfies $G$ ($I ⊨_{log} G$) also log satisfies $H$ ($I ⊨_{log} H$).