# P12 related-work ledger

Status: provisional paper-local author ledger

External-source verification date: 23 July 2026

This ledger records what primary prior work establishes and the novelty
boundary that Paper 12 must preserve. `references.bib` contains the citation
records; `primary-source-bibliography.md` records source provenance and use.
No source below is evidence that CatDB implements the corresponding system.

| BibTeX key | Established result or system capability used by P12 | P12 boundary / forbidden novelty implication |
|---|---|---|
| `P12S01Selinger1979` | Statistics-based access-path and join-order selection in a relational optimizer. | Cost-based physical planning is prior art and belongs after P12 admissibility checks. |
| `P12S02BernsteinEtAl1981` | Distributed query processing with semijoin-based reduction in SDD-1. | Distributed planning and communication reduction are not CatDB novelties. |
| `P12S03BernsteinChiu1981` | Semijoin transformations and communication tradeoffs for relational queries. | A semijoin is neither automatically cheaper nor permission to change bag/null/scalar semantics. |
| `P12S04MackertLohman1986` | R* validation of distributed alternatives using messages, I/O, CPU, shipping, fetch-matches, semijoins, and Bloom joins. | P12 needs an equally explicit communication-aware baseline and cannot call semantic routing sufficient by itself. |
| `P12S05DeWittGray1992` | Shared-nothing parallel execution, partitioned operators, skew, and data movement. | Semantic names do not remove partition imbalance or exchange. |
| `P12S06Graefe1994` | Exchange as an explicit parallel-query operator boundary. | P12 must retain physical movement in every candidate plan. |
| `P12S07DeWittEtAl2013` | Query shipping, data shipping, and split execution across heterogeneous engines. | Split execution and pushdown are established; capability and semantic compatibility remain obligations. |
| `P12S08ModiEtAl2022` | Exchange placement and partial semijoin pushdown in a production distributed engine. | Modern exchange optimization is a baseline, not evidence for P12 performance. |
| `P12S09CurinoEtAl2010` | Workload-driven database partitioning using access graphs, balance, and distributed-transaction objectives. | Workload-aware locality and tuple placement predate CatDB. |
| `P12S10KallmanEtAl2008` | Single-partition and distributed transaction distinctions in H-Store. | Tenant or semantic-object placement does not make every transaction local. |
| `P12S11ThomsonEtAl2012` | Deterministic ordering for partitioned distributed transactions. | Ordering and coordination costs remain explicit P10/P11 concerns. |
| `P12S12TaftEtAl2014` | Fine-grained elastic partitioning under hotspots, skew, movement, and drift. | Repartitioning and workload drift are not solved by semantic metadata. |
| `P12S13KargerEtAl1997` | Consistent hashing as a conventional distributed placement baseline. | P12 must compare with ordinary physical-key routing. |
| `P12S14DeCandiaEtAl2007` | Partitioning, replication, membership, versioning, and availability tradeoffs in Dynamo. | Semantic metadata does not remove replica or coordination tradeoffs. |
| `P12S15CorbettEtAl2012` | Geographic placement, replication, and globally ordered transactions in Spanner. | Region labels do not imply authorization, residency, or zero coordination. |
| `P12S16ChangEtAl2008` | Range tablets, locality groups, and timestamped versions in Bigtable. | Range and temporal locality are established physical techniques. |
| `P12S17ShraerEtAl2018` | Multi-tenancy-guided placement and distribution in CloudKit. | Tenant-aware placement predates CatDB and does not by itself prove isolation. |
| `P12S18AulbachEtAl2008` | Multi-tenant physical/logical schema techniques. | Tenant scope, workspace scope, and physical placement must remain distinct. |
| `P12S19NeumannWeikum2008` | RDF index permutations and join processing in RDF-3X. | Semantic-graph indexes and path access are established. |
| `P12S20WeissEtAl2008` | Sextuple RDF indexing with explicit storage cost. | Additional semantic indexes are not free locality. |
| `P12S21HuangEtAl2011` | RDF graph partitioning, overlap, query decomposition, and network tradeoffs. | Semantic-object or graph partitioning does not eliminate edge cuts. |
| `P12S22GurajadaEtAl2014` | Distributed RDF execution with asynchronous messaging in TriAD. | Cross-shard graph joins and message passing remain physical work. |
| `P12S23KarypisKumar1998` | Multilevel graph partitioning that optimizes cut quality. | Graph-cut optimization does not guarantee balance under every workload or drift. |
| `P12S24SudhirEtAl2023` | Logical data partitioning and metadata-rich data skipping in Pando. | Logical predicate pruning is direct prior art; P12 must prove zero false-negative exclusion under its exact semantics. |
| `P12S25Motro1986` | Scoped completeness information for query processing over incomplete data. | Source coverage is not inferred from provenance or successful access. |
| `P12S26BeckmannEtAl1990` | Multidimensional spatial indexing with the R*-tree. | Geographic index locality is established and does not imply residency admissibility. |
| `P12S27JensenSnodgrass1999` | Distinction between valid time and transaction/system time. | Valid time, system time, source frontier, and refresh time must not be conflated. |
| `P12S28GreenEtAl2007` | Compositional database provenance via semirings. | A provenance domain does not automatically form a complete routing partition. |
| `P12S29CheneyEtAl2009` | Surveyed definitions, uses, and limitations of database provenance. | Provenance records derivation; it does not establish placement completeness or authority. |
| `P12S30BlakeleyEtAl1986` | Incremental maintenance of materialized views. | Materialization and incremental maintenance are established; P12 must preserve dependency validity. |
| `P12S31McSherryEtAl2013` | Distributed incremental dataflow with arranged state and logical time. | Distributed materialization carries time, state, exchange, and frontier costs. |
| `P12S32GjengsetEtAl2018` | Dynamic, partially stateful dataflow with partial materialization in Noria. | Partial state and sharded views are prior art and require consistency/availability boundaries. |
| `P12S33BudiuEtAl2023` | Algebraic and implemented incremental view maintenance for rich query languages. | A local-plus-merge materialization claim needs an admitted algebra, not a slogan. |
| `P12S34DugganEtAl2015` | Polystore islands, shims, and cross-engine data movement in BigDAWG. | Source/engine boundaries and movement predate CatDB semantic routing. |
| `P12S35ChenEtAl2021` | SPANN partitions billion-scale vector data with balanced clustering, replicated closure assignments, and query-aware machine selection. | Distributed vector locality is established prior art; approximate recall, replication, fanout, build, memory, disk, and update costs remain baseline dimensions. |
| `P12S36BuschEtAl2012` | Earlybird hash-partitions documents across servers and maintains real-time inverted indexes under concurrent ingestion and reads. | Sharded full-text indexing and low-latency freshness are established; they do not prove CatDB semantic pruning or eliminate fanout. |

## Required comparison dimensions

Any experimental P12 must compare:

- conventional hash, range, time, tenancy, and communication-aware planning;
- workload/graph partitioning and metadata-rich logical skipping;
- the same ordinary statistics and capability metadata in every baseline;
- result-bag and provenance equality before performance interpretation;
- false-negative and false-positive pruning separately;
- overlap, replicas, source incompleteness, snapshot mismatch, and failures;
- skew, workload drift, migration, and global-index maintenance;
- local, broadcast, repartition, semijoin/Bloom, lookup, coordinator, query
  shipping, and data-shipping alternatives;
- metadata storage, validation, refresh, and planning overhead; and
- feature-by-feature semantic ablation;
- vector recall at \(k\), machine fanout, closure replication, memory/disk
  cost, index build, and updates against SPANN-style placement; and
- full-text query fanout, ingestion/indexing latency, freshness, posting
  placement, and update concurrency against Earlybird-style indexing.

## Source-use constraints

- Primary work supports only its stated model and evaluation.
- Published external performance is not CatDB performance.
- A graph or semantic index is not proof of physical locality.
- Approximate vector recall is not relational answer completeness.
- Full-text index freshness is not source or mapping completeness.
- A completeness annotation is not evidence that live metadata is current.
- A routing or partitioning mechanism does not erase CAP, consensus,
  coordination, failure, or latency boundaries.
- A source change reopens citation, related-work, novelty, and manuscript
  review.