Monotonic Query¶
A fixed database query preserves every prior answer tuple when its input fact instance grows by inclusion under declared set-valued semantics.
Core Idea¶
A monotonic query keeps every answer it has already produced when facts are added. For one fixed database query \(Q\) under set-valued semantics, if fact instance \(I\) is contained in \(J\), then \(Q(I)\subseteq Q(J)\). For partial queries, definedness must also persist when the input grows. The guarantee concerns answer tuples, not processing speed or any update that deletes facts.[^ref-046168d4fb37]
Scope of Application¶
Use the entry for fixed queries over fact instances compared by inclusion. A selection over appended stream tuples and transitive closure over added graph edges both qualify because no old matching tuple or reachable pair becomes false just from adding facts. State the schema, query, update convention and answer-set encoding.[ref-046168d4fb37][ref-4381774f1323]
Time windows that expire old facts, deletion updates and SQL bag counts require separate analysis. A query that returns a changing singleton COUNT tuple is nonmonotonic under answer-set inclusion even though the underlying number may grow.[^ref-046168d4fb37]
Clarity¶
Monotonicity is the implication \(I\subseteq J\Rightarrow Q(I)\subseteq Q(J)\). Incremental evaluation is an implementation method. Jin and Carbonell show that a selection can combine stored old results with results from new tuples. A join can also be monotonic, yet its new answers may join a newly arrived tuple against retained old data. So “no answer retraction” does not mean “evaluate only new input.”[ref-046168d4fb37][ref-4381774f1323]
Manages Complexity¶
The fixed-query inclusion test asks one practical question: can an added fact invalidate an already emitted answer? If not, output can accumulate under insertion-only growth. The implementation still needs its own plan, stored state and cost analysis. In the ARGUS stream setting, selection has a simple delta identity, while a join has old–new and new–old cross terms.[^ref-4381774f1323]
Abstract Reasoning¶
Hold the query fixed and compare arbitrary \(I\subseteq J\). Follow any tuple in \(Q(I)\); if it must remain in \(Q(J)\), the condition survives that comparison. A single counterexample with a lost tuple disproves monotonicity. For \(Q(A,B)=A\setminus B\), adding a fact to \(B\) can remove an old answer. This is a direct deduction from the stated definition for set-valued answers.[^ref-046168d4fb37]
Knowledge Transfer¶
The same three roles transfer between a continuous filter and distributed reachability: a fixed query, input fact inclusion, and answer inclusion. The filter can emit additional matching rows as stream facts arrive; the closure query can emit additional reachable pairs as graph edges arrive. Their algorithms differ, but their semantic no-retraction condition is identical.[ref-046168d4fb37][ref-4381774f1323]
The approved strict parent is live Monotonic Function: a query is an order-preserving map from inclusion-ordered fact instances to inclusion-ordered answer sets. General monotonic functions need not be database queries.
Example¶
Append-only stream selection. ARGUS gives \(\sigma(n\cup\Delta n)=\sigma(n)\cup\sigma(\Delta n)\). For a fixed equality filter, the query is selection, the input order compares \(n\) with \(n\cup\Delta n\), and the answer invariant keeps every tuple in \(\sigma(n)\). The equality predicate is an editorial instance of the source's general selection formula. This example says nothing about join evaluation from only new tuples.[^ref-4381774f1323]
Distributed transitive closure. Ameloot and colleagues give a transducer network that accumulates edge facts and derived paths. The query returns reachable pairs, the input order adds edges, and the answer invariant keeps old paths valid while allowing new pairs. The network sends messages; its coordination classification uses the paper's defined model.[^ref-046168d4fb37]
Relationships to Other Abstractions¶
Current abstraction Monotonic Query Domain-specific
Parents (1) — more general patterns this builds on
-
Monotonic Query is a kind of Monotonic Function Domain-specific
A monotonic query is an order-preserving map from fact instances to answer sets.
Hierarchy paths (3) — routes to 3 parentless roots
- Monotonic Query → Monotonic Function → Order → Comparison → Self Checking
- Monotonic Query → Monotonic Function → Order → Relation
- Monotonic Query → Monotonic Function → Order → Set and Membership
Neighborhood in Abstraction Space¶
Monotonic Query sits in a sparse region of the domain-specific corpus (85th percentile for distinctiveness): few abstractions share its structure, so a faithful description tends to retrieve it precisely.
Family — Unclustered & Miscellaneous (2551 abstractions)
Nearest neighbors
- Truth-table reduction — 0.82
- Query rewriting — 0.82
- Reduction (complexity) — 0.81
- Maximal and minimal elements — 0.81
- Relational database — 0.81
Computed from structural-signature embeddings · 2026-10-08
Not to Be Confused With¶
Append-only input is the comparison condition, not proof that any query is monotonic. Incremental view maintenance is a method, not the semantic property. Coordination-free computation has a precise model-bound relationship to monotonicity in the cited paper and does not mean no messages. Numeric increase of COUNT does not preserve an old singleton answer tuple. Monotonic Function is the broader ordered-map parent; this entry fixes database instance and answer-set carriers.[ref-046168d4fb37][ref-4381774f1323]
References¶
[^ref-046168d4fb37]: Tom Ameloot, Frank Neven, and Jan Van den Bussche, “Relational transducers for declarative networking,” PODS 2011, author full text, §2 definition of monotone query (PDF p. 2), Example 3 (p. 5), and Theorem 12/Corollary 13 (p. 8). The coordination result uses the paper's relational-transducer model. https://arxiv.org/pdf/1012.2858
[^ref-4381774f1323]: Chun Jin and Jaime Carbonell, “ARGUS Rete + DBMS = Efficient Continuous Profile Matching on Large-Volume Data Streams” (title page places a colon after ARGUS), Carnegie Mellon University author full paper (6 July 2004), §3.2, PDF pp. 10–11 (zero-index pp. 9–10). Supports the append-only selection and join delta identities; equality filtering here is an editorial instance of its general selection formula. https://www.cs.cmu.edu/~cjin/publications/Rete.pdf