Use this when revising the main paper. PODS papers are read by database theoreticians, so they need a precise model and a precise result stated on the first page and proofs a reviewer can verify. The failure this skill prevents is a paper whose interesting idea is buried under systems language or whose theorems are stated loosely enough that no one can tell what was proved.
| Section | Job it must do | Common failure |
|---|---|---|
| Intro | Problem, model, result, tightness, what it settles — first page | Leads with a system or a trend, not a model and a theorem |
| Preliminaries | Fix the data/query model, notation, and the exact problem | Definitions too informal for the theorem to be unambiguous |
| Main results | State each theorem precisely; give the key proof ideas | Theorems stated so loosely the contribution is unclear |
| Upper bound | The algorithm/construction + its correctness and complexity proof | Complexity asserted, not proved; hidden dependence on parameters |
| Lower bound | The hardness reduction or impossibility, with its assumptions | No matching lower bound, so optimality is unproven |
| Related work | Delta-first positioning against PODS/ICDT/logic literature | A citation catalog with no contrast of results |
| Draft pattern | PODS-safe rewrite |
|---|---|
| "Our algorithm is very efficient." | "runs in O(n log n) data complexity (Thm 3), matching the Ω(n log n) lower bound of §5" |
| "The problem is hard." | "consistent query answering for this class is coNP-complete in data complexity (Thm 2)" |
| "We handle a broad class of queries." | "we prove the dichotomy for all self-join-free conjunctive queries; self-joins remain open (§7)" |
| "Experiments confirm our approach." | "we give a matching lower bound; a small empirical check (§6) illustrates the constants" |
| "It is easy to see that..." | Replace with the actual argument or a pointer to the appendix proof |
[Model] fix the data model, query class, and cost/complexity measure before any theorem
[Quantifiers] say exactly what is universal and what is existential; data vs. combined complexity
[Tightness] pair each upper bound with a lower bound or state the gap as an open problem
[Assumptions] name every conjecture a bound rests on (e.g. OMv, ETH); never present conditional
hardness as unconditional
-> a reader should be able to restate your main theorem exactly from the abstract alone
A draft with an upper-bound algorithm, a lower-bound reduction, three corollaries, and a long preliminaries section: keep both main theorems and their proof ideas in the body, move the full reduction gadget and the corollary proofs to the appendix with forward references, and cut preliminaries to exactly the definitions the theorems use. The test of a good cut: a reviewer should be able to state what was proved and why it is tight from the body alone, and find every full proof in the appendix.
[Writing diagnosis] clear / under-specified model / loose theorems / gap unstated / over-scoped
[First-page fix] <new framing leading with the model and the exact result>
[Theorem audit] <theorem -> hypotheses stated? complexity exact? proof located? tight?>
[Tightness fix] <where a matching lower bound or an honest open-case statement must be added>
[Anonymity edits] <named systems / self-citations / acknowledgements to rewrite>