CS Paper Radar

Notation3: Graph Terms for RDF

Dörthe Arndt, Pierre-Antoine Champin

cs.LO cs.AI ·submitted 2026-10-22 13:38 UTC · v1

Abstract

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.

Comment
Submitted to TGDK

Closest papers

Nearest neighbours by meaning across the whole index.

Translating RDF 1.2 Graphs to Property Graphs

cs.DB ·2026-10-24 ·Maxime Jakubowski, Dominik Tomaszuk, Daniel Fernández-Álvarez, Ruben Taelman, Ruben Dedecker +2 more
similarity 0.68
Abstract · 13 pages, 5 figures. Accepted for the 2nd International Workshop on Data Management for Knowledge Graphs (DMKG 2026), Bari, Italy

RDF 1.2 introduces statement-level constructs, such as triple terms, reifiers, and descriptions, that pose new challenges for transforming RDF data into labeled property graphs (LPGs). This work presents and compares three algorithms for translating RDF 1.2 data into LPGs, each interpreting a different amount of the RDF 1.2 reification vocabulary. Algorithm Structural interprets no vocabulary and losslessly supports arbitrary RDF 1.2 graphs by representing triple terms explicitly as nodes; Direct interprets rdf:reifies to recover annotated edges while preserving reifiers as graph objects; and Fold additionally folds reifier descriptions into edge properties, resulting in a more concise, albeit lossy, LPG representation. We define the three translations, analyze which class of RDF 1.2 graphs each preserves, and experimentally evaluate their implementations. The experiments confirm the predicted trade-offs: all variants scale linearly on the tested workloads, the generality of Structural has no runtime penalty, and folding descriptions into edge records can significantly reduce the number of edges on description-heavy data.

0.35

Does SRL Pave the Road to Explainable Reasoning? Lessons Learned from an Implementer's Perspective

cs.DB ·2026-09-03 ·Lander Maes, Bryan-Elliott Tam, Jitse De Smet, Jos De Roo, Pieter Colpaert +1 more
similarity 0.67
Abstract

The Shape Rules Language (SRL) Working Draft defines how to derive new RDF triples from an RDF graph using inference rules. Each rule matches graph patterns and instantiates triple templates whose output feeds into validation pipelines, SPARQL queries, or further inference. RDF reasoning has traditionally relied on fixed entailment regimes (RDFS, OWL), rule-based ad-hoc languages such as N3, or other implementation-specific solutions without a shared standard. SRL introduces user-defined production rules with a defined grammar, dependency analysis, execution ordering, and termination guarantees. However, no authoritative implementation exists, leaving practitioners with little guidance on how to build a conformant engine or on what problems the language can solve. We implemented two SRL engines and evaluated both on classical RDF reasoning tasks for soundness, completeness, and speed. The first reuses an existing SPARQL query engine and its query parser; the second is a dedicated engine. The SPARQL-based engine reused an existing modular parser for query construction and SPARQL CONSTRUCT for triple production, reducing engine-specific work. The dedicated engine was two to six times faster, the gap widening as rule sets grow. Both engines were validated against the SRL conformance test suite, supplemented by additional use-case-driven tests. A usable SRL engine can be built inexpensively on top of a SPARQL engine, with a moderate speed trade-off that a dedicated implementation recovers. Despite the specification's immaturity, the language already supports practically useful reasoning tasks.

0.19

GQL Datatypes as an RDF Vocabulary

cs.DB ·2026-10-12 ·Dominik Tomaszuk, Daniel Szałaj
similarity 0.66
Abstract · 13 pages, 7 figures, 3 tables. Accepted for DMKG 2026 (2nd International Workshop on Data Management for Knowledge Graphs), Bari, Italy

The ISO GQL standard introduces a rich value-type system for property graphs, including scalar, temporal, byte-string, list, record, and dynamic union datatypes. The vocabulary presented here additionally covers a vector extension. At the same time, RDF-based knowledge graph systems identify literal datatypes by IRIs and interpret typed literals through value spaces, lexical spaces, and lexical-to-value mappings. This paper presents the GQL Datatypes RDF Vocabulary, a lightweight RDF vocabulary that represents selected GQL datatypes and the vector extension as RDF datatype IRIs and describes their hierarchy, aliases, and selected constraints using RDF, RDFS, OWL, and XML Schema Datatypes vocabulary terms. The vocabulary is intended to support interoperability between GQL-oriented property graph systems and RDF-based knowledge graph systems. We describe its namespace and datatype model, summarize its datatype coverage, and show how the accompanying generator and validator use the vocabulary. In the reference implementation, RDF literals retain GQL datatype IRIs; XSD mappings declared in the vocabulary support scalar validation, while lists, records, and vectors are encoded directly as JSON lexical forms of vocabulary-typed literals.

0.28

Structural Morphisms for Nested Conditions - Full Version

cs.LO ·2026-08-12 ·Arend Rensink, Andrea Corradini
published similarity 0.66
Abstract · This is the full version (including proofs) of the paper published in GCM 2026

Nested conditions are used, among other things, as a graphical way to express first order formulas ruling the applicability of a graph transformation rule to a given match. In this paper, we first introduce several operators on conditions mimicking logical connectives. Next we propose an original notion of structural morphism among nested conditions, and we identify circumstances under which morphisms are consistent with the entailment of the corresponding conditions. Finally we frame the results in a categorical context, proving functoriality and universality properties of the various operations.

0.19

Rewrite Once, Validate Anywhere: Producing OWL-Aware SHACL Constraints (Extended Version)

cs.LO cs.AI ·2026-08-14 ·Anouk Oudshoorn, Piotr Gorczyca, Dörthe Arndt
benchmark similarity 0.65
Abstract · Technical report of our ISWC'26 paper

The Shapes Constraint Language (SHACL) is a W3C recommendation to express syntactic constraints, called shapes, on RDF graphs. SHACL validators are used to test whether a given graph adheres to such a shape. However, RDF graphs often come with OWL ontologies, whose implicit knowledge needs to be taken into account. This is classically handled by first applying reasoning and then performing the constraint checking on the results, often using different technologies which makes the process inefficient and vulnerable for mistakes. To overcome this, we propose to internalise the OWL axioms in the SHACL constraints; we construct a rewriting which takes as input both shapes and an OWL EL$^-$ ontology -- a fragment of OWL EL restricting the usage of existential restrictions -- and produces SHACL constraints. This output can then be evaluated by any validator supporting SHACL core regardless of its reasoning support, while yielding the same results as the traditional approach. The implementation of our translation is evaluated both against applying state-of-the-art reasoners and validators consecutively, as against validators with built-in reasoning support. For our benchmark, we show that our approach is in general more efficient in finding violations compared to the sequential approach, thus providing a powerful tool which simplifies combining reasoning with validation.

0.04

How to prove equations using diagrams: A categorical and operational semantics for e-graphs

cs.LO math.CT ·2026-11-04 ·Evan Patterson
similarity 0.64
Abstract

E-graphs are a powerful algorithmic technique for automated equational reasoning but have resisted a conceptual understanding independent of issues of presentation and implementation. We propose an operational semantics for e-graphs based on the fundamental category-theoretic concepts of diagrams, limits, and initial functors. We illustrate the formalism through numerous example calculations and establish its soundness and completeness. Technical prerequisites are kept to a minimum in the main text; less standard elements of the mathematical theory are developed in two appendices.

0.25

MGQL: An Executable, Small-Step Semantics of GQL

cs.PL cs.DB ·2026-08-25 ·Aditya Thimmaiah, Tong-Nong Lin, Milos Gligoric
publishedtheory similarity 0.64
Abstract · Accepted at OOPSLA 2026

ISO Graph Query Language (GQL) is the first international standard for property graph-based graph query languages, standardized as ISO/IEC 39075 in 2024. However, ISO/IEC 39075 codifies its semantics informally across 600+ pages of prose, making it difficult to formally reason about the standard or for a standard-faithful implementation. Existing formalizations are not adequate because they either: (1) significantly reduce the semantic complexity by omitting bag semantics, schemas, and composite queries on multiple graphs; (2) or significantly reduce the syntactic complexity by only considering isolated fragments such as pattern-matching, leaving the full query pipeline unformalized. Yet it is these semantic-syntactic features that make formalizing GQL non-trivial. We present MGQL, the first mechanized, small-step operational semantics for a substantial read-only fragment of GQL that is grounded in the ISO/IEC 39075 standard. Our formalization models multi-graph property graphs with mixed edge directionality and supports a large fraction of GQL pattern constructs: quantified paths and edges, directional and undirected matching, label expressions, pattern lists, and composite queries. The semantics is supported by a schema-aware type system that refines variable types via closed-graph schemas, tracks nullability, supports multiple composite query operators, and models quantified-path bindings with list types. We prove that our type system is sound, ensuring an end-to-end guarantee of well-formed queries yielding results that conform to their declared schemas. MGQL provides the first bridge between GQL's informal specification and a mechanized implementation, enabling formal reasoning about correctness.

0.37

RDFdL: Integrating RDF with Differential Dynamic Logic

cs.AI cs.FLcs.LO ·2026-08-16 ·Yuyang Li, Lukas Kubelka, Julia Butte, Tobias Käfer
theory similarity 0.63
Abstract · Preprint

Knowledge graphs modeled in RDF are powerful for describing static knowledge, but they cannot capture or reason about the dynamic behavior of physical systems, e.g., systems described by differential equations, which is a critical gap for AI-driven cyber-physical systems. To solve this, we propose RDFdL, a framework that integrates RDF with Differential Dynamic Logic (dL) to represent and reason about both static knowledge and the continuous dynamics of physical systems. For the dynamic part, we syntactically represent differential equations and ranges in the state space in RDF and SHACL and provide semantics using a translation to dL. Linking RDF and dL through their shared foundation in first-order logic achieves a unique integration: verification results for safety and reachability properties in the dynamic logic domain become available as entailment to SPARQL queries over RDF data. We implement the pipeline using Apache Jena for ontology-driven RDF reasoning and KeYmaera X, the theorem prover for dL, and sketch its applicability in manufacturing.

0.06