--- name: zsets description: Reference for Z-sets — the integer-weighted multiset algebra at the heart of DBSP, differential dataflow, and OpenIVM's delta tables. Focused on the algebra itself (definition, group structure, operators) and on its lineage (Green/Tannen K-relations, Koch's Z-relations, Naiad/differential dataflow). Mirrors the structure of Feldera's `01-zsets-and-dbsp.md` worked example. For DBSP system details see `explain-related-systems`; for the broader IVM operator theory see `explain-ivm`; for compilation/cost work see `incrementalization-strategies`. --- ## Scope and cross-references This skill covers **the Z-set algebra itself** and prior work that produced it. It does **not** re-cover material already in sibling skills: - **`explain-related-systems`** — DBSP system, DBToaster, pg_ivm, Snowflake Dynamic Tables, Materialize. Look there for the DBSP operator algebra (D, I, lift), the four fundamental operators, the linear/bilinear/non-linear classification of incremental forms, and the system-level comparison. - **`explain-ivm`** — operator-by-operator delta rules, multiplicity tracking, correctness considerations. Look there for the delta-rule cookbook. - **`incrementalization-strategies`** — higher-order IVM, factorisation, F-IVM, compilation-based approaches, cost models. Look there for "how to make Z-set IVM faster". - **`merge-ivm-reference`** — how the Z-set delta gets turned into a SQL MERGE in OpenIVM's compile path. What is unique to this skill: the algebraic object as a standalone topic, the worked Feldera medallion-pipeline trace that motivates it, and the literature lineage (semirings → K-relations → Z-relations → differential dataflow → DBSP). When the user asks "what is a Z-set really", or "where does this idea come from", land here. --- ## 1. What is a Z-set? A **Z-set** over a domain *A* is a function `Z : A → ℤ` with **finite support** (only finitely many elements have non-zero weight). Equivalently, a finitely-supported function `A → ℤ` — the free abelian group on *A*, written `ℤ[A]` in the algebra literature. | Element | Weight | Meaning | |---|---|---| | `row_A` | `+1` | present (inserted) | | `row_B` | `+2` | present with multiplicity 2 | | `row_C` | `-1` | retracted (deleted) | | `row_D` | `0` | absent (not materialised) | ### 1.1 Why integers? — the group property Pointwise addition gives Z-sets a **commutative group** structure. `0` is identity; `−Z` is the inverse: ``` {(A, +1), (B, +1)} -- batch 1 + {(B, -1), (C, +1)} -- batch 2 = {(A, +1), (B, 0), (C, +1)} -- B cancels ``` The inverse is the *whole point*. Set semantics ({0,1}) and bag/multiset semantics (ℕ) lack inverses, so classical IVM frameworks (Gupta-Mumick-Subrahmanian's counting algorithm, Blakeley-Larson-Tompa deltas) need explicit delete-handling logic. Z-sets get deletes for free from the group structure: a deletion is just an addition of a negative weight. ### 1.2 Z-sets generalise sets and bags | Semantics | Weight domain | Inverse? | Captures | |---|---|---|---| | Set | `{0, 1}` | No | classical RA | | Bag / multiset | `ℕ` | No | SQL with duplicates | | **Z-set** | `ℤ` | **Yes** | sets + bags + deltas in one object | | K-relation | any commutative semiring K | depends | provenance, probability, security | A Z-set with only positive weights *is* a multiset; restricted to {0,1} it *is* a set. The novel structure relative to bag semantics is the negative weights, which let one object represent both *a relation and a delta to it*. ### 1.3 Operators on Z-sets The relational operators are defined on Z-sets in the natural algebraic way; for the per-operator *incremental* forms see `explain-ivm`. - **Addition** `Z₁ + Z₂`: pointwise sum. Used to apply a delta. - **Negation** `−Z`: flip all weights. Used to retract. - **Selection** `σ_p(Z)`: keep weights for elements satisfying *p*. Linear. - **Projection** `π_X(Z)`: sum weights of elements that agree on the projected columns. Linear. - **Join** `Z₁ ⋈ Z₂`: weight of `(a,b)` is `Z₁(a) · Z₂(b)`, filtered by predicate. **Bilinear**. - **Union (bag)** = addition. **Difference** = `Z₁ + (−Z₂)`. - **Distinct** `δ(Z)`: project to {0,1} weights — drops duplicates **and** drops negatives. Non-linear, the source of most IVM cost. The point: positive RA + aggregation can be expressed as polynomial expressions on Z-sets, and each operator's incremental form follows mechanically from its algebraic shape (linear / bilinear / non-linear). This is what `explain-related-systems` covers under the DBSP heading. --- ## 2. The medallion-pipeline worked example (Feldera `01-zsets-and-dbsp.md`) This is the concrete trace that the source document hangs everything on. Including it here because it makes the Z-set semantics tangible. ### Setup A bronze→silver→gold pipeline: ``` bronze_supplier ─Δ─┐ bronze_partsupp Δ─┐│ ││ ▼▼ ┌──────┐ ┌──────┐ ┌────────────┐ │filter│───►│ join │───►│ aggregate │───► gold_agg_supply_cost └──────┘ └──┬───┘ │ (SUM cost) │ │ └────────────┘ ┌───┴────┐ │ Z1 │ one-tick delay; holds trace of partsupp │ trace │ └────────┘ ``` A new row arrives: `Δ(bronze_supplier) = {(supplier_42, +1)}`. ### Trace through each operator | Stage | Z-set transformation | Cost | |---|---|---| | Δ input | `{(supplier_42, +1)}` | — | | Filter (`s_acctbal > 0`) | unchanged (predicate true) | O(1), stateless | | Join vs. partsupp trace | probes Z1-stored state, emits `{((supplier_42, ps_100), +1), ((supplier_42, ps_101), +1)}` | O(matches), stateful | | SUM aggregate | reads previous group total, emits `{(group_key, +$550)}` | O(1) per group | | Output | retract old, insert new: `{(g, old, −1), (g, new, +1)}` | — | **Total: 4 rows touched** vs. millions in batch mode. The Z-set framing is what lets every operator speak the same language: Δ in, Δ out, weights composing under +. For *why* `Q(i + Δi) = Q(i) + ΔQ(Δi, state)` and the operator algebra behind it (`Q^Δ = D ∘ lift(Q) ∘ I`), see `explain-related-systems` §DBSP. --- ## 3. Z-sets in code — Feldera Rust pointers For grounding in the reference implementation: | Concept | Type / location | |---|---| | Weight type | `pub type ZWeight = i64;` — `crates/dbsp/src/algebra/zset.rs:39` | | Flat Z-set (no value) | `OrdZSet` | | Indexed Z-set ((key, value, weight)) | `IndexedZSet`; backings `OrdIndexedWSet`, `FileIndexedWSet`, `FallbackIndexedWSet` (auto-spill) | | Trace trait (state for stateful ops) | `crates/dbsp/src/trace.rs` | | Spine (default trace, 9-level LSM-style) | `crates/dbsp/src/trace/spine_async.rs`, `MAX_LEVELS = 9` | | Z1 one-tick delay | `Z1` in `crates/dbsp/src/operator/z1.rs` | | Circuit driver | `DBSPHandle` in `crates/dbsp/src/circuit/dbsp_handle.rs` | These are the same data structures Naiad/differential-dataflow used (under different names) — see §4.3. --- ## 4. Prior and adjacent work — Z-sets are a unification, not a fresh invention The Feldera/DBSP write-up presents Z-sets cleanly, but the algebraic object has a long pedigree. This is the part most worth tracking — it's where the literature search adds something the source document doesn't. ### 4.1 Provenance semirings — Green, Karvounarakis & Tannen (PODS 2007) *"Provenance Semirings"*. The seminal paper that established **K-relations**: relations where each tuple is annotated with a value from a commutative semiring `K`, and positive RA is interpreted via `+` and `·` of *K*. Specialising K recovers many models: | K | Model recovered | |---|---| | `({0,1}, ∨, ∧)` | classical set semantics | | `(ℕ, +, ·)` | bag/multiset semantics | | **`(ℤ, +, ·)`** | **Z-relations / DBSP Z-sets** | | `(ℕ[X], +, ·)` | provenance polynomials (most informative) | | confidentiality lattice | access-control | | `([0,1], +, ·)` truncated | probabilistic databases | Tannen is explicitly an author on the DBSP paper — the connection is direct, not analogical. ### 4.2 Z-relations and IVM — Koch (PODS 2010) *"Incremental Query Evaluation in a Ring of Databases"*, Christoph Koch. The paper that made the IVM case for Z-relations explicit: - Relations annotated with positive **or negative** integers, viewed as elements of a commutative ring. - The difference operator of RA *is* the ring's additive inverse — uniform handling of inserts and deletes. - Equivalence of RA queries over Z-relations is **decidable** (in contrast to set/bag semantics, where it is undecidable). A real optimisation lever — rewrite rules become algebraically checkable. - Updates and base relations live in the same algebraic universe; a batch can be reordered freely. The direct algebraic ancestor of DBSP's Z-sets. Koch's later **DBToaster** (VLDB Journal 2014) operationalises the same view as a compiler producing higher-order delta rules — covered in `explain-related-systems` and `incrementalization-strategies`. ### 4.3 Differential dataflow / Naiad — McSherry et al. (CIDR 2013, SOSP 2013) *"Differential Dataflow"*, Frank McSherry, Derek G. Murray, Rebecca Isaacs, Michael Isard. Built on Naiad's timely dataflow. - Collections carry **multisets with ℤ weights** — the same object as Z-sets, predating the DBSP name by a decade. - Innovation vs. plain incremental dataflow: differences are indexed by a **partial-order timestamp** (loop counter × epoch), enabling efficient incremental computation across iterations of a recursive computation, not just across input epochs. - Operators maintain **arrangements** — sorted, indexed, time-versioned views of a collection. Conceptual ancestor of DBSP's traces. Feldera's Spine is essentially a re-implementation. Frank McSherry is a DBSP co-author, so the lineage is direct: DBSP gives a denotational, paper-friendly semantics to what differential-dataflow already did operationally. This is worth knowing because differential-dataflow has *more* (recursion across nested time) than DBSP-as-deployed in many systems chooses to expose. ### 4.4 The classical IVM line (pre-Z-set) For context — the non-Z-set IVM tradition: - **Blakeley, Larson & Tompa (1986)** "Efficiently Updating Materialized Views". Original delta expressions for SPJ over sets. - **Gupta, Mumick & Subrahmanian (SIGMOD 1993)** the counting algorithm — augments tuples with a derivation count. Anticipates Z-sets but stops at ℕ; deletes still need special-case logic. - **Bancilhon (1986); Balbin & Ramamohanarao (1987)** semi-naïve evaluation for Datalog — recursive analogue, also implicitly counting. - **Roussopoulos (1991)** ViewCache; **Quass & Widom (1997)** self-maintainable views. The Z-set framing subsumes these: where the count algorithm uses ℕ-weighted bags + auxiliary delete logic, Z-sets use ℤ and get deletes for free from the group inverse. (Detail on per-operator deltas: `explain-ivm`.) ### 4.5 Adjacent algebraic frameworks - **F-IVM (Olteanu et al.)** — *factorised* IVM over rings; extends Koch's ring-of-databases with factorisation of join results. Triple-lock factorisation (SIGMOD 2018) is the entry point. Complementary to DBSP. See `incrementalization-strategies`. - **Provenance for FO / fixpoints** — Grädel & Tannen, extending semirings to first-order logic and Datalog. Relevant if you care about *why* a tuple is in the view, not just whether. - **CRDTs** — different community, same instinct: commutative monoids/groups for conflict-free updates. PN-Counters and Add-Wins sets are essentially Z-set-shaped. --- ## 5. How OpenIVM realises the Z-set abstraction OpenIVM compiles the DBSP view of IVM to standard SQL upserts. As of commit `fc6dab9` ("Z-set refactor"), the realisation mirrors the algebra natively: | Z-set concept | OpenIVM realisation | |---|---| | Z-set element with weight ∈ ℤ | row in `delta_` with `_duckdb_ivm_multiplicity: INTEGER` (signed) | | Weight ±1 (single insert / delete) | column value `+1` or `-1` | | Weight > 1 (batch) | encoded as repeated rows today; the column type can carry any signed weight | | Z-set addition (consolidation) | `SUM(_duckdb_ivm_multiplicity)` per distinct tuple — no `CASE WHEN` round-trip | | Z-set bilinear product (join) | leaves multiply weights; `IvmJoinRule` additionally applies a Möbius IE sign `(-1)^(k-1)` because OpenIVM's "current base" reads `R_now = R_old + ΔR` | | Trace / Z1-stored state | the materialised view itself; DuckLake snapshots for time-travelled bases | | One circuit step | one `PRAGMA ivm('view_name')` invocation | **Pre-`fc6dab9` divergence (now closed)**: OpenIVM previously stored multiplicity as `BOOLEAN` (`true`=insert, `false`=delete) and used `SUM(CASE WHEN mul = false THEN -col ELSE col END)` as the canonical consolidation. Joins combined leaf multiplicities with XOR. The refactor replaced both with their native Z-set forms (signed integer + bilinear product); the Möbius sign is the one OpenIVM-specific addition on top of the textbook DBSP algebra. For the operator-rule details (`IvmJoinRule` inclusion-exclusion, `IvmAggregateRule`, etc.), see `AGENTS.md` or `CLAUDE.md`, `explain-ivm`, and `docs/internals/linearity.md`. --- ## 6. Suggested reading order 1. **DBSP paper** — Budiu et al., VLDB 2023, `arXiv:2203.16684`. Cleanest single statement. 2. **Provenance semirings** — Green, Karvounarakis, Tannen, PODS 2007. Algebraic foundation. 3. **Koch, "Incremental Query Evaluation in a Ring of Databases"** — PODS 2010. The IVM case for Z-relations. 4. **Differential dataflow** — McSherry et al., CIDR 2013, plus the Naiad SOSP 2013 paper. The operational precursor. 5. **Feldera Rust code** — `crates/dbsp/src/algebra/zset.rs`, `operator/z1.rs`, `trace/spine_async.rs`. Reference implementation. 6. **OpenIVM paper** — Battiston, Kathuria, Boncz, SIGMOD-Companion 2024, `arXiv:2404.16486`. SQL-to-SQL translation. ## 7. Source This skill consolidates Feldera's `01-zsets-and-dbsp.md` (`mdrakiburrahman/feldera`, branch `dev/mdrrahman/research`). The §1 algebra and §2 medallion-pipeline trace follow that document. The §4 prior-work lineage and §5 OpenIVM mapping are added here. DBSP system mechanics (operator algebra D/I/lift, trace/Spine internals beyond pointers) deliberately omitted — those live in `explain-related-systems`.