PaperlayerView exact revision on arXiv

Source-linked AI summary

Notation3: Graph Terms for RDF

Dörthe Arndt, Pierre-Antoine Champin

arXiv:2610.31266v1cs.LOcs.AI

TL;DR

Notation3’s graph terms support statements about entire graphs and rules, but their semantics were not fully covered by earlier formal work. This paper defines a two-level semantics for graph terms and N3’s special predicates. It shows compatibility with RDF simple entailment on RDF graphs and extends RDF’s interpolation result to N3 basic entailment on finite graphs.

  • Problem

    Earlier formal treatments clarified rules and implicit quantification but left the semantics of graph terms incompletely specified, despite their use for statements about graphs and rules.

    Source: §1 · p. 1, §5.3 · p. 19

  • Method

    The paper introduces an abstract syntax and defines basic semantics for graph terms followed by N3-entailment semantics for selected special predicates.

    Source: §5.4 · p. 23, §8 · p. 27

  • Results

    For RDF graphs, basic entailment coincides with RDF simple entailment, and the N3 interpolation lemma extends the RDF result to finite graphs.

    Source: §6 · p. 24

  • Takeaways & Limitations

    The formalization covers graph-term uses in statements about statements and rules, with requirements that the authors report their semantics meets.

    Source: §8 · p. 27

    For log:includes, the paper excludes universal quantification because b-entailment with it is complex and no supporting reasoner is known to the authors.

    Source: §5.4 · p. 23

Abstract

from arXiv · show

Notation3 Logic was introduced as an extension of RDF allowing the user to express rules on top of triples and to make statements about graphs. The original proposal of the logic only came with an informal specification of its semantics which has been refined later on. While this refinement clarified the meaning of rules and implicitly quantified variables, it left the meaning of graphs used as terms - so-called graph terms - open. In this paper we aim to close this gap. We discuss in detail, how graph terms are used in Notation3, which formal requirements they need to meet, and provide examples to illustrate the difficulties when defining their semantics. We then introduce an abstract syntax for the logic and define its semantics in two steps: similarly to RDF's simple interpretations, we define interpretations and basic entailment for Notation3 which covers plain RDF triples but also triples containing graph terms. N3-entailment is then an extension of basic entailment which assigns meaning to the different special predicates of the logic like for example the implication symbol. N3-entailment is defined in a way that it can be extended whenever a new predicate is added to the logic. As Notation3 Logic is currently under development, we expect many predicates to be added. Our research provides and important step towards the full standardisation of the logic.

1 Introduction

Notation3 Logic uses graph terms to make statements about statements, including entire graphs, but their semantics remained incompletely specified. This paper formalizes graph terms through a two-level semantics for basic entailment and N3’s logical predicates.

1 Introduction

  • N3 graph terms can denote entire graphs, unlike RDF-star’s triple terms, but their interpretation and blank-node scoping pose challenges.Graph terms are also used to express logical constructs.Source: §1 · p. 2
  • Earlier formal work clarified rules and implicit quantification but did not fully cover graph-term semantics as originally intended.The original N3 semantics was informal, and graph terms raise questions about self-reference, larger graphs, blank-node scope, and logical constructs.Source: §1 · p. 2
  • The paper analyzes semantic requirements from informal specifications and implementations, then defines an abstract syntax and semantics in two steps.Basic semantics covers graph terms without special-predicate meanings; N3-semantics adds predicates such as log:implies and log:includes.Source: §1 · p. 2
  • The authors report that their definitions meet the identified requirements.The paper’s structure includes analysis of graph-term use, requirements, syntax, semantics, and comparison with other approaches to statements about statements in RDF.Source: §1 · p. 2

2 Graph terms in N3

N3 uses graph terms both to make statements about graph content and to express rules. The same graph-term machinery applies in both uses, including the treatment of quantification.

2 Graph terms in N3

  • A graph term can contain a set of triples interpreted as a conjunction, allowing a statement to refer to multiple triples together.This differs from RDF-star’s use of a single triple as a term.Source: §2 · p. 2
  • A blank node inside a graph term is existentially quantified within that term, so Bob’s statement is that someone likes both pizza and pasta.The paper notes that this interpretation remains under discussion and that the semantics should accommodate possible changes in implicit quantification scope.Source: §2 · pp. 2–3
  • N3 rules use graph terms as subject and object of log:implies, with ?x implicitly universally quantified.The example rule says that if someone likes pasta, they also like spaghetti; graph-term decisions apply to rules as well as statements about statements.Source: §2 · p. 3
  • N3’s log:implies predicate has a dual role: it can be treated as a predicate relating graph terms and as an implication that can be applied to derive a triple.The example derives Alice’s liking pasta and pizza from Bob’s statement and the rule about what Bob says.Source: §2 · p. 3

3 Requirements on a formal semantics

The paper identifies requirements concerning RDF compatibility, graph-term opacity and closedness, and clear quantification scopes. Its choices aim to preserve RDF entailment compatibility while keeping graph terms usable in rules and statements about statements.

3 Requirements on a formal semantics

  • N3 semantics should be compatible with RDF simple entailment, while D-entailment is left outside this paper’s scope.The stated compatibility requirement is limited to simple entailment because the focus is graph terms.Source: §3 · pp. 3–4
  • Opaque graph terms avoid unwanted derivations from referential transparency, while a rule can locally enable those derivations when desired.The paper characterizes opacity as a weaker, less constraining option than transparency.Source: §3 · p. 4
  • Graph terms are closed: the term denotes exactly its stated triples, since allowing arbitrary additional triples would prevent proving rule antecedents from known triples.The paper contrasts this with an open interpretation that could include further triples.Source: §3 · p. 4
  • N3’s historical local blank-node and global universal-variable scopes leave interactions ambiguous, motivating explicit ways to express quantification scope.The example can mean either that everybody loves somebody or that someone is loved by everyone; implicit scoping has also diverged across implementations.Source: §3 · pp. 4–5

4 Syntax

This section defines an abstract syntax for N3, relating it to concrete syntax and establishing syntactic relationships among N3 graphs, including isomorphism, subgraphs, instances, generalisations, merge, and closure.

4 Syntax

  • The syntax discussion motivates an abstract syntax to express different quantification scopes and make quantification easier to handle.Concrete syntax is described in a W3C Community Group draft, with examples illustrating graph terms and rules.Source: §4 · p. 5

4.1 Abstract Syntax

  • The abstract syntax makes all variables explicit and defines graphs as disjoint sets of universally and existentially quantified variables plus a set of triples.Terms are atomic terms or finite graph terms; unlike RDF, N3 permits any kind of term in every triple position.Source: §4.1 · pp. 5–6

4.2 From concrete to abstract syntax

  • Concrete N3 syntax maps IRIs and literals to abstract terms, while implicit universals enter the outer graph and blank nodes are existentially quantified in the innermost graph.Explicit @forAll and @forSome declarations turn the identified IRIs into variables and must precede triples in their graph, with @forAll declarations first.Source: §4.2 · pp. 6–7

4.3 Variables

  • The section defines constituents and free variables, distinguishes ground graph terms from ground graphs, and normalizes graphs by removing quantifiers on variables absent from triples.A graph term is ground when its variable constituents are scoped; a graph is ground only if its direct triples are ground and it has no quantified variables. Normalization retains only quantified variables occurring in the triples.Source: §4.3 · pp. 7–9

4.4 Isomorphisms

  • N3 graphs are isomorphic when their structure matches under variable renaming, including nested graph terms, and this relation is reflexive, symmetric, and transitive.The definition compares normalized graphs and uses mappings to account for variables scoped inside graph terms.Source: §4.4 · pp. 9–10
  • Isomorphism is transitive, and the example shows G1 is isomorphic to G2 but not to G3.Source: §4.4 · p. 11

4.5 Syntactic relations between graphs

  • An N3 subgraph must preserve free variables and be a subset in its quantified variables, existential variables, and triples; concrete variable names matter.The examples show that G4 is a subgraph of G, whereas G5 and G6 are not; a graph with different variable names may instead be isomorphic to a subgraph.Source: §4.5 · pp. 11–12
  • Total application replaces free variables directly or nested in a graph with their mapped values, but leaves variables quantified in a nested graph unchanged.In the example, x is replaced while quantified y is not.Source: §4.5 · p. 12
  • E-instances extend RDF graph instances, while N3's universal quantification motivates separate U-instance and generalisation notions; these definitions support a counterpart to RDF's interpolation lemma [24, Section 5.2].An E-instance substitutes mapped existential variables, whereas a U-instance substitutes mapped universal variables; generalisation reverses each relation.Source: §4.5 · pp. 12–13
  • A merge is formed by taking the disjoint union of graphs made isomorphic to each input graph.Source: §4.5 · p. 13
  • A graph is closed when it has no free variables, and every graph is semantically equivalent to its closure.The closure adds the graph's free variables to its universally quantified variables.Source: §4.5 · p. 13

5 Semantics

This section develops Notation3 semantics in two stages, characterizing basic entailment through universal extensions and a generalized interpolation lemma before defining N3-entailment with meanings for special predicates. It gives conditions for log:implies and log:includes and identifies limits on entailment and its scope.

5.1 Base Semantics

  • Ground graph terms denote isomorphic copies of themselves, while variables can denote resources in triples but remain ground terms inside graph terms.This treatment of variables differs from RDF’s mapping of blank nodes to resources, though basic entailment on RDF graphs remains equivalent to RDF simple entailment.Source: §5.1 · pp. 14–15
  • Every N3 graph has a basic model, and each graph has the same models as its closure.Basic entailment does not support rules or negation, so it cannot construct contradictions.Source: §5.1 · p. 16

5.2 Semantic relations between graphs

  • Isomorphic closed graphs share models, and a closed N3 graph b-entails each of its subgraphs.The section also establishes that a closed graph is b-entailed by any of its E-instances, while a graph b-entails any of its U-instances.Source: §5.2 · pp. 17–18
  • If a graph b-entails two closed graphs, it also b-entails their merge.The result applies when the merged graphs are logical consequences of the same graph.Source: §5.2 · p. 18

5.3 Interpolation Lemma

  • The interpolation section seeks an N3 counterpart to RDF’s interpolation lemma, accounting for universal quantification and the added complexity of existential variables depending on universals.The supplied passages introduce this aim and examples but do not state the section’s eventual result.Source: §5.3 · p. 19
  • Universal extensions capture, up to variable mapping, triples true in every model of a finite normalized closed N3 graph and are equivalent to that graph under basic entailment.The generalized interpolation lemma characterizes basic entailment between two graphs by a mapping between their universal extensions that matches every E-instance triple.Source: §5.3 · pp. 19–20
  • G1 basic-entails G2 exactly when a mapping from N2 to N1 makes every E-instance triple of G2’s universal extension match a triple of G1’s extension.This is the generalized interpolation criterion for finite normalized closed graphs.Source: §5.3 · p. 20
  • For finite RDF graphs without graph terms, basic entailment holds exactly when a subgraph of G1 is an E-instance of G2; the result does not cover infinite graphs.The proof needs fresh ground terms for existential variables, which are unavailable when a graph uses all possible ground terms.Source: §5.3 · pp. 20–21

5.4 N3-entailment

  • N3 models satisfy basic entailment plus conditions for log:implies and log:includes, and the definition can be extended to cover other log-namespace predicates omitted here.The paper focuses on graph terms and omits predicates for literal operations and term types.Source: §5.4 · p. 21
  • log:implies supports existential rules, deriving a hasMother fact from tom’s human-type fact, but allowing blank nodes in rule heads makes N3-entailment undecidable in general.The semantic condition is one-way: N3-entailment between graphs does not necessarily mean that the corresponding log:implies triple holds.Source: §5.4 · pp. 22–23
  • log:includes holds exactly for graph-term pairs where the second graph is an existential consequence of the first, excluding derivations by universal instantiation.The paper omits universal-quantification entailment because it is complex and unsupported by known reasoners, though graphs containing universally quantified variables can still have existential consequences.Source: §5.4 · p. 23

6 Discussion of the requirements

The discussion argues that the proposed semantics meets the identified requirements for graph terms. It relates basic entailment to RDF simple entailment and addresses opacity, closedness, and quantification scope.

Semantic compatibility with RDF

  • For RDF graphs, N3 basic entailment coincides with RDF simple entailment; its interpolation lemma extends the RDF result to finite graphs, while the RDF lemma also holds for infinite graphs.The authors consider this difference minimal because entailment between infinite RDF graphs is rarely needed in practice.Source: §6 · p. 24
  • The N3 interpolation lemma is limited to finite graphs, and the authors conjecture that Lemma 34 generalizes to a broader class, possibly including infinite graphs.Source: §6 · p. 24

Referential Opacity

  • Representing graph terms as syntactic objects supports referential opacity while allowing derivations associated with transparency to be enabled locally.The discussion illustrates this with a graph term about Lois Lane knowing that Clark Kent can fly.Source: §6 · p. 24

Closedness of graph terms

  • Graph terms are interpreted by isomorphic syntactic representations, and implication graph terms can be used in models to derive new facts.The authors note that IRIs could represent open graphs if needed.Source: §6 · pp. 24–25

Clarity and flexibility of quantification scopes

  • Explicit quantification scopes follow the original specification’s universal-over-existential ordering, and the empty graph’s truth gives the example its intended meaning.With N3-entailment, this scope choice does not restrict expressivity.Source: §6 · p. 25

7 Related work

The related work traces N3’s informal origins and the later formalization of syntax and semantics, then compares graph terms with approaches to referring to triples and graphs across RDF and logic. It also connects N3 entailment to existential-rule reasoning.

N3 formalization

  • Early N3 specifications informally introduced all features discussed, including graph terms and two types of implicit quantification, without formal semantics; prior mapping [5, 6] handled FOL-like formulas but not unquoting or log:includes.This paper builds on W3C community-group semantics [8] and adds a semantic definition for log:includes, which earlier work described using n3-derivation [13, p.13].Source: §7 · pp. 25–26

Web formalisms and graph references

  • RDF 1.2 triple terms [28] and [23], reification [24], singleton properties [31], and RDF datasets [30] differ from N3 in what they can name and how those names behave.RDF 1.2 restricts triple terms to object position; singleton properties require asserting the triple, while dataset semantics remain unsettled across proposals [39].Source: §7 · p. 26

Logic beyond RDF

  • Common Logic supports naming formulae but not quantifying into them or unquoting, whereas Qiana [17] supports both through a different formalization.For variables used both inside and outside a graph term, this paper uses grounding; Qiana treats quoted formulae as logical functions.Source: §7 · pp. 26–27

Existential rules

  • Existential-rule reasoning relates to N3 rules using log:implies [4, 3], and query answering for N3 entailment is generally undecidable.The paper relates basic entailment’s ∀∃-formulae to existential rules with empty bodies and adapts chase-style reasoning to universal extensions.Source: §7 · p. 27

8 Conclusion and future work

The paper proposes an abstract syntax and two-level formal semantics for N3 graph terms, covering statements about statements and rules. It establishes that the semantics meets identified requirements, while noting limits in interpolation and special-predicate coverage.

Conclusion

  • The formal semantics covers N3 graph terms used for statements about statements and rules, with basic semantics extended by N3 semantics for special predicates such as log:implies.The authors show it satisfies requirements for these use-cases and extends RDF’s interpolation lemma to basic N3 semantics on finite graphs.Source: §8 · p. 27

Interpolation lemma

  • The generalized interpolation lemma is proved only for finite graphs; extension to infinite graphs remains conjectural.The proof permits infinitely many triples but requires that graphs not use all variables or all ground terms.Source: §8 · p. 27
  • The generalized interpolation lemma is less practical than RDF’s counterpart because universal extensions become infinite when a graph contains a universal variable.The authors plan an entailment procedure considering only terms in the two graphs.Source: §8 · p. 27

Future work

  • N3 semantics formally covers log:implies and log:includes, but many special predicates from the original specification remain to be added.Planned extensions include negation and aggregation; variable predicate positions rule out classical stratification, motivating chain stratification.Source: §8 · p. 28
Loading 2610.31266v1…