CS Paper Radar

Extending Triple Graph Grammars to Formalize Complex View Definitions on Families of Models - Long Version

Lars König, Jens Kosiol

cs.SE ·submitted 2026-08-11 10:47 UTC · v1
top venue

Abstract

View-based development is an important technique to manage complexity and facilitate cooperation in the development of modern and complex systems of systems. This approach places high demands on view definition languages used in the development process. First, such a language needs to be approachable and extremely versatile so that developers from diverse backgrounds are able to use it and can define views for a diverse set of different tasks. Yet, the language also needs to have a precise and formal semantics so that it is possible to integrate the work performed on various views in a controlled manner to obtain a coherent overall system. In this paper, we continue previous work of equipping the NeoJoin view definition language with a formal semantics that is based on triple graph grammars (TGGs). This paves the way for obtaining automated and incremental synchronization procedures between models and views that come with high formal guarantees for their behavior. Simultaneously, our work serves as a further case study of the expressivity and usability of TGGs. We identify one gap, namely convenient support for the translation of overlapping queries from the view definition language, and tackle that gap by introducing a skip semantics for TGG rules, i.e., allowing to skip certain actions a rule prescribes, depending on the application context.

Comment
Long version of paper accepted at the 23rd Workshop on Model Driven Engineering, Verification and Validation (MoDeVVa 2026); 14 pages, 12 figures, 2 tables

Closest papers

Nearest neighbours by meaning across the whole index.

Notation3: Graph Terms for RDF

cs.LO cs.AI ·2026-10-22 ·Dörthe Arndt, Pierre-Antoine Champin
similarity 0.63
Abstract · Submitted to TGDK

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.

0.24

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.62
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.36

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

GeoReform: Reflective Formalization Evolution for Multimodal Geometry Problem Solving

cs.AI ·2026-10-08 ·Jialu Wang, Ruichen Zhang, Xiaoou Liu, Hua Wei, Tianlong Chen
similarity 0.61
Abstract

Multimodal large language models (MLLMs) often struggle to identify and use geometric relations in diagrams. Recent methods address this challenge by converting geometric entities, relations, and constraints into explicit textual representations for the model to reason over. However, effective formalization is highly non-trivial: on Geometry3K, structure injection fixes 28 errors but introduces 13 new ones among 200 examples. Redundant relations can distract the model, while ambiguous references to diagram elements can lead it to apply constraints incorrectly. This suggests that the key challenge is not merely extracting more geometric facts, but organizing them into representations that support downstream reasoning. To fully exploit the power of formalization, we further propose GeoReform, a reflective formalization evolution framework that treats formalization as an optimizable policy rather than a fixed parser output. GeoReform executes the full reasoning pipeline, collects failed rollouts, diagnoses defects in the current representation, and mutates the policy to better select, ground, group, and present geometric entities, relations, constraints, and targets. On Geometry3K, GeoReform improves Qwen3VL-2B accuracy from 42.0\% to 56.0\%. Extensive experiments and analyses across geometry reasoning benchmarks demonstrate that effective formalization is crucial for improving multimodal geometry reasoning.

0.21

An Extended Tutorial and Vocabulary for Relational Language Design in an Era of AI-Assisted Query Generation

cs.DB ·2026-08-12 ·Wolfgang Gatterbauer
top venue similarity 0.60
Abstract · 7 pages, VLDB 2026 tutorial, tutorial page: https://northeastern-datalab.github.io/relational-language-tutorial/

Relational query languages have been studied and used for more than 50 years, with SQL dominant in practice. Today, queries are increasingly generated by machines and read by humans. At the same time, the landscape also includes dataframe, pipeline, logical, functional, graph, and relational programming notations. These developments invite two related questions beyond expressive power: which relational structures do languages make explicit, and how well can notation support users in reading and revising queries? This 3-hour tutorial extends an earlier SIGMOD'26 tutorial in three directions: recursive and path queries (connecting relational and graph query languages), nested relational data, and relational languages for problems beyond PTIME. Rather than beginning from formal definitions, we start from example queries and compare how different languages express the same intent. To compare recurring structure across notations, we use Abstract Relational Calculus (ARC) and Relational Diagrams as reference representations. From these examples, we develop a vocabulary for relational language design, including information need, query mapping, relational pattern structure, relational pattern denotation, and semantic conventions. Participants will leave with a framework for comparing existing and future relational languages, a precise vocabulary for articulating design trade-offs, and a concrete set of examples connecting classical database languages with alternative proposals.

0.48

Visual Graph Reasoning via Knowledge Compilation

cs.MM cs.AIcs.CV ·2026-09-16 ·Rongzheng Wang, Zhe Wang, Ke Qin, Rongwei Wang, Muquan Li +4 more
top venue similarity 0.59
Abstract · Accepted at the 34th ACM International Conference on Multimedia (MM '26)

Visual graph reasoning requires answering graph-theoretic questions directly from graph images, where graph topology and state are conveyed visually rather than given in symbolic form. Despite recent progress of vision-language models (VLMs), current approaches to visual graph reasoning still fail on simple visual graph problems. This reveals a fundamental limitation of existing approaches: they prioritize final-answer supervision over the intermediate recovery of an explicit graph representation that preserves graph topology and state from visual input. To address this limitation, we propose VGCompiler, a compilation-centric paradigm for visual graph reasoning via knowledge compilation. VGCompiler organizes reasoning around two compilers: a representation compiler that recovers a structure-preserving intermediate graph representation from visual input, and an operation compiler that compiles query intent under the recovered graph state into an executable graph operation. Specifically, we build VGCompiler on Qwen3-VL-8B and train it with reinforcement learning guided by a layered reward over executability, compiled graph validity, representation quality, and operation quality. VGCompiler uses a frozen observer to summarize graph and question conditions into lightweight signatures, enabling archive retrieval and code reuse across similar regimes. Experiments on three benchmarks GVLQA, VisionGraph, and VGCURE, show that Qwen-VGCompiler, built on an 8B backbone, surpasses the strongest closed-source VLM baseline by 28.9% and the strongest code-based baseline by 23.7%, while maintaining high efficiency. We further evaluate VGCompiler on three real-world domains, including metro routing, logistics delivery, and network fault assessment, where it generalizes across heterogeneous visual graphs and domain-grounded tasks.

0.26

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

Compiling WebAssembly Concolic Execution with Staging, Continuations, and Snapshots (Extended Version)

cs.PL ·2026-08-18 ·Dinghong Zhong, Alexander Bai, Mikail Khan, Guannan Wei
published similarity 0.58
Abstract · 29 pages; preprint of paper accepted at OOPSLA 2026

Concolic execution is a variant of symbolic execution that runs a program simultaneously with concrete and symbolic inputs. It records the symbolic constraints encountered along a concrete execution path, then solves those constraints to generate inputs that explore new paths. Existing concolic engines generally follow one of two implementation strategies: Interpreter-based systems are comparatively simple to build but incur substantial interpretation overhead, while instrumentation-based systems avoid this overhead but typically re-execute the program from the beginning for each new input. In this paper, we develop a new approach that achieves the best of both worlds. Starting from the concrete semantics of the target language, we first develop a definitional concolic interpreter and stage it to compile away interpretation overhead while retaining the simplicity of an interpretation-based implementation. By expressing the staged interpreter in continuation-passing style, we can capture execution snapshots at branch points and resume from them when exploring alternative paths, avoiding repeated execution from the program entry. Because snapshot-reuse can itself incur overhead, we further develop a heuristic that favors snapshot-reuse only when it is expected to be beneficial. We instantiate this approach for WebAssembly and implement it in a new concolic-execution compiler GenWasym. Across 184 benchmarks, GenWasym with staging alone achieves a $29.4\times$ average speedup over the interpreter-based WASP; heuristic snapshot-reuse further increases the speedup to $44.9\times$.

0.30