Monotonic Query¶

A fixed database query preserves every prior answer tuple when its input fact instance grows by inclusion under declared set-valued semantics.

Version: v1 · 2026-10-07 · History
Domain-specific #: 13951
Domain group: Applied Sciences & Engineering
Origin domain: Computer Science & Software Engineering
Subdomains: Relational Queries, Distributed Querying → Computer Science & Software Engineering
Aliases: Monotone Query

Core Idea¶

A monotonic query preserves answers as facts are added. Fix one database query \(Q\), a schema, and set-valued answer semantics. If instance \(I\) is contained in a larger instance \(J\), monotonicity requires \(Q(I)\subseteq Q(J)\): every answer tuple already obtained from \(I\) remains an answer from \(J\). For a partial query, the formal definition also requires it to remain defined on \(J\) when it was defined on \(I\). The test is about the query's outputs under input inclusion, not about how fast an implementation runs.^[1]

Selection over an append-only stream and transitive closure over accumulating edge facts are unlike positive cases. One may materialize old selection results and add new ones; the other can accumulate newly discovered reachable pairs. The shared guarantee is answer inclusion. Neither case proves that every monotonic query can be processed using only the newly arrived tuples.^[1]^[2]

Structural Signature¶

Fixed query and answer representation — constitutive bearer. Compare the same \(Q\) over one schema, with outputs represented as sets of tuples. Changing \(Q\) or the output order changes the proposition being tested.^[1]
Input inclusion — constitutive comparison. \(I\subseteq J\) means each prior fact remains while more may be added. Deletions and revisions do not meet that antecedent.^[1]
Answer inclusion — constitutive invariant. Require \(Q(I)\subseteq Q(J)\) for every such pair, preserving definedness where necessary. One newly added fact that removes a prior answer is a counterexample.^[1]

Execution choices follow from these roles but are not roles themselves. ARGUS's selection delta uses stored old answers plus new matching tuples; its join delta also needs old–new combinations. Ameloot and colleagues give a distributed reachability construction, but its coordination result has the paper's model-specific meaning.^[1]^[2]

What It Is Not¶

Monotonicity is not a promise that evaluating only new input tuples is always sufficient. For a selection \(\sigma\), \(\sigma(n\cup\Delta n)=\sigma(n)\cup\sigma(\Delta n)\). A join of two growing relations, however, can produce answers from a new tuple on one side paired with an old tuple on the other. Jin and Carbonell explicitly include both cross terms and a new–new term.^[2]

Nor is monotonicity the same as eventual consistency, communication-free execution, or membership in one syntax class. The CALM equivalence in Ameloot and colleagues' transducer model uses particular definitions of distributed computation and coordination; their transitive-closure example sends messages. A query may be monotonic without being a conjunctive query.^[1]

Scope of Application¶

Use this entry when a fixed database query receives fact instances ordered by inclusion and returns set-valued answer relations. It applies to a bounded continuous selection over newly appended stream tuples and a recursive reachability query over added edges. Their execution settings differ, while the input/output inclusion test is the same.^[1]^[2]

State the data and answer conventions. SQL bag multiplicities, a moving time window that expires old tuples, deletion updates, and a numeric ordering of aggregate values need their own analysis. The entry's guarantee concerns insertion-only fact inclusion and no retraction of answer tuples; it does not assert unchanged numeric results under a different output order.^[1]^[2]

Clarity¶

Separate semantic monotonicity from incremental evaluation. The first is the universal implication \(I\subseteq J\Rightarrow Q(I)\subseteq Q(J)\). The second is an implementation technique that computes changes from newly arrived input and retained state. A filter satisfies the simple delta identity; a join requires old–new and new–old pairings even while its answer set can remain monotonic.^[1]^[2]

The same distinction guards against blanket claims about operators. Under set-valued answers, \(A\setminus B\) is nonmonotonic when an inserted \(B\) fact removes an old answer. A query returning a singleton tuple containing COUNT also retracts its old count tuple when a new fact changes the number. Those are explicit deductions from the definition for those encodings, not claims that every bounded use of difference or aggregation is nonmonotonic.^[1]

Manages Complexity¶

The inclusion test reduces a large family of execution questions to one stable invariant: will any added fact invalidate an emitted tuple? If the answer is no, results can be accumulated without semantic retraction under insertion-only growth. That does not prescribe a single algorithm or memory cost.^[1]

ARGUS illustrates the distinction. Selection can add \(\sigma(\Delta n)\) to a materialized \(\sigma(n)\). For joins, the incremental result also depends on newly arrived tuples joined against retained old relations. Recording the semantic invariant and the delta formula separately prevents the false shortcut that every monotone join sees only fresh input.^[2]

Abstract Reasoning¶

To test a proposed query, keep \(Q\) fixed and choose arbitrary \(I\subseteq J\) on the same schema. Trace an answer tuple from \(Q(I)\). If its witness remains valid after adding facts, that supports monotonicity; if one extension removes it, the query fails. This proof or counterexample must be stated in the chosen set-valued encoding. For a partial query, check that definedness also persists.^[1]

An equality selection is positive: a tuple that already met a fixed equality predicate still meets it after unrelated rows arrive. Transitive closure is positive: an old path remains a path when edges are added. Difference is negative when adding the subtracted fact removes a prior output. These are claims about all allowed input extensions, not only a few sampled datasets.^[1]^[2]

Knowledge Transfer¶

The three-role test transfers from append-only stream selection to distributed recursive closure. In the first, input growth is newly appended stream facts and output growth is additional matching tuples. In the second, input growth is added graph edges and output growth is additional reachable pairs. Both instantiate the same fixed-query/inclusion/answer-inclusion relation, while their evaluation methods and latency differ.^[1]^[2]

The portable order-preserving map belongs to the live Monotonic Function entry. This query-specific version remains domain-specific because its operands are database fact instances and answer relations, and because its usefulness depends on query semantics and update assumptions. General monotonic functions include maps that are not queries.

Examples¶

Continuous selection over appended stream facts¶

Jin and Carbonell's ARGUS uses append-only data and gives the relational selection identity \(\sigma(n\cup\Delta n)=\sigma(n)\cup\sigma(\Delta n)\). Instantiate its fixed selection with an equality predicate on a stream attribute. A previously matching tuple remains in the selected relation after more tuples arrive, and newly matching tuples can be added.^[2]

Mapped back: the fixed query is this selection under set-valued output; the input order compares old facts \(n\) with \(n\cup\Delta n\); the answer invariant is the union identity retaining \(\sigma(n)\). The equality predicate is an editorial instantiation of the paper's general \(\sigma\), not a quoted worked filter. This case does not license evaluating a join from \(\Delta n\) alone.^[2]

Distributed transitive closure of added edges¶

Ameloot, Neven and Van den Bussche describe a transducer network that accumulates input edges and derived paths, inserting from \(S\cup R\cup T\cup(T\circ T)\). Adding edges can add paths but does not erase old ones, so the output reachability relation is monotonic. Their example sends messages while the source classifies the computation under its formal coordination definition.^[1]

Mapped back: the fixed query returns reachable node pairs; the input order compares an edge set with a larger edge set; the answer invariant retains every old reachable pair. The result does not claim instant convergence, no network messages, or a universal coordination theorem outside the paper's model.^[1]

Structural Tensions¶

No answer retraction versus absence-sensitive output. If a fixed query must preserve every old tuple as facts arrive, it cannot in the same set-valued encoding answer every question whose current answer depends on missing facts. With \(Q(A,B)=A\setminus B\), adding a fact to \(B\) can remove a prior answer. For a singleton COUNT tuple, adding a fact can replace the old count tuple. A monotonic query permits accumulated outputs; a nonmonotonic formulation may answer those questions but must accommodate changed outputs.^[1]

Diagnostic: can a newly inserted fact invalidate an answer tuple already returned by this fixed query? If yes, either revise the output encoding and claim carefully, or treat the query as nonmonotonic under set-valued answer inclusion. The coordination consequence remains conditional on the particular distributed model.^[1]

Structural–Framed Character¶

Evaluative weight: monotonicity describes an inclusion invariant, not a judgment that the query is better. Human-practice dependence: analysts choose schemas and semantics, but the implication can be checked formally once chosen. Institutional origin: no institution determines whether a query satisfies the implication. Vocabulary travel: “monotone” names order preservation in mathematics too; the query bearer fixes its meaning here. Import versus recognition: recognizing this entry requires testing answer inclusion for growing database instances, not applying the word to any output that tends upward.^[1]

The portable skeleton is a function preserving an order on its inputs and outputs. Live Monotonic Function is the approved strict parent; this child fixes both orders to fact inclusion and answer inclusion for a database query. An ordered numerical measure, an antitone map, or a non-query monotonic map belongs elsewhere. Its character: structural within a database frame, because the query, fact-instance carrier, and set-valued answer relation are necessary to this named identity.

Structural Core vs. Domain Accent¶

The core relation is fixed query + input fact inclusion → output answer inclusion. Selection and reachability are different accents: one can use a simple delta selection, while the other computes a recursive closure in a network. Their shared identity does not include a particular execution algorithm or a universal coordination claim.^[1]^[2]

The broader mathematical relation is the live Monotonic Function identity. The query entry does not clear the Prime bar as a new universal principle: remove database instances and answer tuples and the remainder is already the wider order-preserving map. The strict edge records that genus and the database-specific differentia without duplicating it.

This entry is a kind of Monotonic Function.

Monotonic Function is the approved strict parent after independent Gate 4: under set-valued semantics \(Q\) is an isotone map between inclusion-ordered carriers, and many monotonic functions are not database queries. Order supplies the mathematical order background but is not asserted as a second direct edge. Conjunctive query is a positive syntactic class, not every monotonic query. Query Theory concerns a different preference-retrieval identity. These names do not substitute for the explicit input/output inclusion test.

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

Show alternative paths (2)

Neighborhood in Abstraction Space¶

Monotonic Query sits in a sparse region of the domain-specific corpus (85^th percentile for distinctiveness): few abstractions share its structure, so a faithful description tends to retrieve it precisely.

Family — Unclustered & Miscellaneous (2551 abstractions)

Nearest neighbors

Computed from structural-signature embeddings · 2026-10-08

Not to Be Confused With¶

Append-only input is the update condition, not proof that an arbitrary query is monotonic. Incremental view maintenance is an implementation strategy; a monotonic join may still require retained old facts. Coordination-free computation has a formal, model-bound relation to monotonicity in the cited work; it does not mean zero communication. Numeric monotonicity of COUNT under the usual number order does not preserve a prior singleton count tuple under answer-set inclusion. Deletion-tolerant processing makes a different promise from insertion-only monotonicity.^[1]^[2]

References¶

[1] 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 registry ↩a ↩b ↩c ↩d ↩e ↩f ↩g ↩h ↩i ↩j ↩k ↩l ↩m ↩n ↩o ↩p ↩q ↩r ↩s ↩t ↩u ↩v

[2] 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 registry ↩a ↩b ↩c ↩d ↩e ↩f ↩g ↩h ↩i ↩j ↩k ↩l ↩m