# Paper 2 related-work ledger

Status: author-side provisional ledger
Evidence cut: 22 July 2026
Scope: `papers/02-physical-compilation/`

This ledger separates established prior art from the candidate CatDB delta. It
does not treat a cited feature as evidence that CatDB implements it.

| Key | Primary source | Established baseline | Relation to Paper 2 | Candidate CatDB delta | Evidence status |
|---|---|---|---|---|---|
| B51 | Selinger et al., *Access Path Selection in a Relational Database Management System* | Cost-based access-path and join-order selection | Native optimizer baseline | Preserve typed mapping intent before handing physical choice to the backend | Prior art verified; CatDB delta unimplemented |
| B52 | Graefe, *Volcano* | Extensible and parallel physical operators | Physical execution baseline | Keep CatDB semantic compilation outside native row operators | Prior art verified; hot-path claim untested |
| B53 | Graefe, *Cascades* | Rule-based transformation and search framework | Optimizer architecture baseline | Version semantic dependencies and backend dispositions upstream of physical search | Prior art verified; delta untested |
| B54 | Avnur and Hellerstein, *Eddies* | Adaptive query processing | Runtime-adaptation baseline | Distinguish backend adaptation from semantic recompilation | Prior art verified; no CatDB runtime evidence |
| B62 | Mackert and Lohman, *R\* Optimizer Validation and Performance Evaluation for Distributed Queries* | Distributed cost, shipping, and plan validation | Federation cost baseline | Add typed mapping and provenance dependencies to shipping decisions | Prior art verified; future planner work |
| B20 | Sheth and Larson, *Federated Database Systems* | Heterogeneity, autonomy, and federation taxonomy | Federation baseline | Treat source-to-domain meaning as immutable typed mappings | Prior art verified; maintenance benefit untested |
| B21 | Wiederhold, *Mediators* | Mediated domain access | Semantic access baseline | Make mediation rules typed, composable, versioned artifacts with loss records | Prior art verified; candidate delta untested |
| B22 | Begoli et al., *Apache Calcite* | Modular logical and physical planning over heterogeneous sources | Closest general planning-framework comparator | Preserve categorical path/mapping evidence through a capability-checked handoff | Prior art verified; no comparative implementation |
| B23 | Trino pushdown documentation | Connector-specific projection, predicate, aggregation, and join pushdown | Pushdown capability baseline | Four-way exact/residual/approximate/unsupported disposition tied to semantic artifacts | Official docs verified; CatDB classifier absent |
| B42 | Calvanese et al., *Ontop* | Mapping-aware SPARQL rewriting over relational databases | Closest mapping/query-rewrite comparator | Span categorical equations, cache dependencies, lineage, and multiple backend models | Prior art verified; CatDB span unimplemented |
| B40 | W3C R2RML | Standard relational-to-RDF mapping language | Mapping baseline | Directional read witnesses with explicit loss and execution dispositions | Standard verified; novelty requires comparison |
| B37 | W3C RDF 1.1 | RDF graph and dataset semantics | RDF boundary | Refuse to conflate finite total instances with open RDF graphs | Standard verified; RDF lowering not implemented |
| B39 | W3C SPARQL 1.1 | Graph query and federation semantics | RDF query baseline | Typed categorical path provenance across rewrites | Standard verified; future work |
| B41 | ISO/IEC 39075:2024 GQL | Property-graph query-language boundary | Graph execution baseline | Identify exact fragment of total functional paths | Standard record verified; fragment open |
| B43 | Alsubaiee et al., *AsterixDB* | Scalable semistructured database system | Document/multimodel baseline | Capability manifests that record missing/null/array preservation | Prior art verified; document connector absent |
| B64 | Duggan et al., *BigDAWG* | Polystore islands, shims, and casts | Heterogeneous-engine baseline | Attach categorical mapping and loss evidence to casts and routing | Prior art verified; polystore work future |
| B55 | Apache Arrow columnar format | Language-neutral columnar memory and IPC layout | Data interchange candidate | Carry semantic artifact identities alongside batches | Official specification verified; use not selected |
| B56/B56a/B56b | Substrait specification, about, and extensions | Portable compute-plan representation and extension model | Plan interchange candidate | Retain CatDB mapping, capability, and provenance evidence outside or beside the plan | Official specification verified; integration absent |
| B44 | Malkov and Yashunin, HNSW | Approximate nearest-neighbor graph index | Vector operator baseline | Classify ANN as approximate candidate generation, never identity evidence | Prior art verified; vector operator absent |
| B45 | Johnson, Douze, and Jégou, Faiss | Billion-scale similarity search | Vector execution baseline | Version metric, index, parameters, and result provenance | Prior art verified; no CatDB results |
| B46 | Wang et al., Milvus | Purpose-built vector data management | Vector system baseline | Integrate vector candidates into typed semantic plans without hiding approximation | Prior art verified; future work |
| B65 | Chu et al., *HoTTSQL* | Mechanized SQL rewrite semantics | Formal-verification comparator | Prove selected CatDB IR/lowering laws, then refine to a backend subset | Prior art verified; P2 has paper proofs only |
| PG18 docs | PostgreSQL 18 official documentation | Prepared statements, generic/custom plans, explain, types, constraints | PostgreSQL capability source | Version the capability and evidence contract | Backend facilities verified; CatDB connector absent |
| SQLite docs | SQLite official documentation | Preparation, bytecode, explain, counters, constraints, typing, strict tables, JSON | SQLite capability source | First exact relational vertical slice | Backend facilities verified; CatDB connector absent |

## Comparison obligations before acceptance

1. Compare the CatDB logical/physical boundary with Calcite rather than
   describing Calcite only as an adapter framework.
2. Compare mapping-aware rewriting with Ontop using equivalent source data and
   query families.
3. Compare pushdown coverage and diagnostics with Trino connector behavior.
4. Compare heterogeneous-engine routing and casts with BigDAWG before making a
   polystore novelty claim.
5. Compare any portable-plan proposal with Substrait and any process-boundary
   representation with Arrow.
6. Compare vector behavior with explicit ANN quality and provenance baselines;
   do not use similarity as identity evidence.
7. Keep backend optimizer decisions attributed to SQLite/PostgreSQL rather than
   to CatDB.

## Out-of-scope claims

- Category theory is not a replacement for cost-based optimization.
- Typed mappings are not new by themselves.
- Federation, mediation, mapping-aware rewriting, pushdown, and polystores are
  established areas.
- Arrow is not a semantic layer.
- Substrait is not proof of cross-engine semantic equivalence.
- Approximate nearest-neighbor search is not exact query evaluation.