TiramemsuMetagraph Encodings over Identified Triples
Hypergraphs, metagraphs, edges about edges and containers inside containers all fit on one shape of row: a triple with its own id. Writing them in is cheap. Reading them back out is a different matter. Some stores decode to the structure you meant, some decode to something else, and some to nothing at all. This paper states exactly which stores decode, and shows that every condition it imposes is needed.
Abstract
Identified triples give statements identities that other statements can reference, so set-valued incidence, higher-order endpoints and containment fit on one carrier. We argue that this representation is cheap and that invertibility is a separate integrity obligation, and we state that obligation exactly. We cover finite directed hypergraphs, nonempty-end Basu–Blanning metagraphs, identified higher-order metagraphs, a well-founded ubergraph fragment and a finite attributed annotating presentation. For each we give source signatures and exact image constraints under which encoding and decoding are inverse up to renaming. The roundtrip proofs are short bookkeeping; the contribution is the constraint set, and we show that each constraint is necessary. Four results go beyond roundtrips. A temporal theorem separates asserted rows from retained referents, so an annotation may be valid outside its bearer's interval. A supersession relation records identity across versions. An executable-metapath recognizer decides in linear time whether an edge set can fire, and we characterize when it agrees with walk reachability. Reference rank gets operational consumers: the number of strata for referentially complete bulk loading and the depth of retraction cascades. Evidence is exhaustive bounded enumeration, seeded randomized property tests, executable SHACL validators and a Lean proof of the directed roundtrip. We report no performance or retrieval results.
The main results
Exact, and each condition needed
For each family the paper says which stores decode, up to renaming of ids. For every constraint it gives a store that breaks only that one and does not decode.
Annotations outlive their bearers
A snapshot can keep the referents of what it asserts. Then "this 2020 fact was disputed in 2025" is valid in 2025. Extensional images do not survive time.
Reachable is not executable
A linear-time check decides whether every edge in a set can fire when it needs all its inputs. Walks agree with firing when dependencies are acyclic or every edge has one input.
Depth has a price
Reference rank gives the minimum number of bulk-load batches and bounds the rounds of a retraction cascade. Anchored encodings stay at rank one however deep the nesting.
Who it is for
Readers who model metagraphs, hypergraphs or nested contexts on a statement store, whether that is tiramemsu, RDF 1.2 reifiers or a property graph with edge ids, and want to know which integrity checks make the encoding safe to read back. If you want the ideas without the proofs, start with the companion article. For the tiramemsu recipes it formalizes, see metagraphs from one row shape.
Status
A draft preprint, archived on Zenodo. It has not been peer reviewed. The engine does not enforce the image constraints. The checkers, the SHACL and SPARQL validators and the Lean proof show what a validator would check. The Lean proof covers the directed, higher-order and extensional roundtrips under canonical naming only.
Cite
@misc{pavlyshyn2026metagraphenc,
author = {Pavlyshyn, Volodymyr},
title = {Metagraph Encodings over Identified Triples: Exact Images,
Temporal Integrity, and Structural Depth},
year = {2026},
note = {Draft preprint, revision 2. CC BY 4.0},
doi = {10.5281/zenodo.23167938},
url = {https://doi.org/10.5281/zenodo.23167938}
}← Paper 1: Layered Bitemporal Graphs · Paper 3: When Is a Temporal Statement Store a Statement Graph? →