Contents

Monotonic query

The topic of this article may not meet Wikipedia's general notability guideline. Please help to demonstrate the notability of the topic by citing reliable secondary sources that are independent of the topic and provide significant coverage of it beyond a mere trivial mention. If notability cannot be shown, the article is likely to be merged, redirected, or deleted. Find sources: "Monotonic query" – news · newspapers · books · scholar · JSTOR (January 2011) (Learn how and when to remove this message)

Indatabase theory and systems, a monotonic query is one that does not lose any tuples it previously made output, with the addition of new tuples in the database. Formally, a query q over a schema R is monotonic if and only if for every two instances I, JofR, ${\displaystyle I\subseteq J\Rightarrow q($I)\subseteq q(J)} (q must be a monotonic function). ^[1]

An example of a monotonic query is a select-project-join 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, 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.

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.

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 continuousorlong-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

${\displaystyle A(Q,\tau )=\bigcup _{t=1}^{\tau }(A(Q,t)-A(Q,t-1))\cup A(Q,0)}$

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

${\displaystyle A(Q,\tau )=\bigcup _{t=0}^{\tau }A(Q,t)}$

^[2]

This database-related article is a stub. You can help Wikipedia by expanding it.