database theory Database theory encapsulates a broad range of topics related to the study and research of the theoretical realm of databases and database management systems. Theoretical aspects of data management include, among other areas, the foundations of q ...

and systems, a monotonic query is one that does not lose any tuples it previously made output, with the addition of new

tuples In mathematics, a tuple is a finite ordered list (sequence) of elements. An -tuple is a sequence (or ordered list) of elements, where is a non-negative integer. There is only one 0-tuple, referred to as ''the empty tuple''. An -tuple is defi ...

in the database. Formally, a query ''q'' over a schema ''R'' is monotonic if and only if for every two instances ''I'', ''J'' of ''R'',

I \subseteq J \Rightarrow q(I) \subseteq q(J)

(''q'' must be a

monotonic function In mathematics, a monotonic function (or monotone function) is a function between ordered sets that preserves or reverses the given order. This concept first arose in calculus, and was later generalized to the more abstract setting of order ...

). An example of a monotonic query is a select- project-

join Join may refer to: * Join (law), to include additional counts or additional defendants on an indictment *In mathematics: ** Join (mathematics), a least upper bound of sets orders in lattice theory ** Join (topology), an operation combining two top ...

query containing only conditions of equality (also known as conjunctive queries). Examples of non-monotonic queries are aggregation queries, or queries with set difference. Identifying whether a query is monotonic can be crucial for

query optimization Query optimization is a feature of many relational database management systems and other databases such as NoSQL and graph databases. The query optimizer attempts to determine the most efficient way to execute a given query by considering the p ...

, especially in view maintenance and data stream management. Since the answer set for a monotonic query can only grow as more tuples are added to the database, query processing may be optimized by executing only the new portions of the database and adding the new results to the existing answer set.

Applications

Unnesting Queries

Monotonic queries are important in the topic of unnesting SQL queries. If a query is monotonic, it implies that a nested query can actually be unnested.

Data streams

A data stream is a real-time, continuous, ordered (implicitly by arrival time or explicitly by timestamp) sequence of items. The number of items is considered to be infinite and therefore cannot feasibly be stored in its entirety. Queries over data streams are often called ''continuous'' or ''long-running'' queries, and are mostly run over a limited window of tuples in the stream. To evaluate a continuous query, one can simply reevaluate the query over newly arrived tuples, and append the new tuples to the existing result set. More formally, let ''A(Q, t)'' be the answer set of a continuous query ''Q'' at time t, τ be the current time, and 0 the start time. Then, if Q is monotonic, its result set at time τ is :

A(Q, \tau) =\bigcup_^ (A(Q,t) - A(Q, t-1)) \cup A(Q,0)

In contrast, non-monotonic queries have the following answer semantics: :

A(Q, \tau) =\bigcup_^ A(Q,t)

References

Database theory {{database-stub