Idempotence: Difference between revisions
imported>Richard Pinch (new entry, just a stub) |
Pat Palmer (talk | contribs) m (→In mathematics) |
||
| (4 intermediate revisions by 2 users not shown) | |||
| Line 1: | Line 1: | ||
In [[mathematics]] '''idempotence''' is the property of an | {{subpages}} | ||
In [[mathematics]] and [[computer science]] '''idempotence''' is the property of an operation that repeated application has no further effect. | |||
==In mathematics== | |||
A [[binary operation]] <math>\star</math> is ''idempotent'' if | A [[binary operation]] <math>\star</math> is ''idempotent'' if | ||
| Line 7: | Line 10: | ||
equivalently, every element is an [[idempotent element]] for <math>\star</math>. | equivalently, every element is an [[idempotent element]] for <math>\star</math>. | ||
Examples of idempotent binary operations include [[join]] and [[meet]] in a [[lattice (order)|lattice]]. | Examples of idempotent binary operations include [[join]] and [[meet]] in a [[lattice (order)|lattice]]; [[union]] and [[intersection]] on [[set (mathematics)|sets]]; [[disjunction]] and [[Conjunction (logical and)|conjunction]] in [[propositional logic]]. | ||
A [[unary operation]] (a [[function (mathematics)|function]] from a set to itself) π is idempotent if it is an idempotent element for [[function composition]], <math>\pi \circ \pi = \pi</math>. | |||
==In computing== | |||
In applications such as [[database]]s and [[transaction processing]], idempotent operations are those for which the intended effect is that repeated application should have no effect, such as inserting a [[record]] into a [[file]], an element into a [[set (mathematics)|set]], or sending a message. Implementations must therefore be constructed in such a way that the intended effect is actually carried into practice. For example, messages might have unique sequence numbers with duplicates being discarded on receipt; a set might be implemented as a bit vector, and member [[insertion]] implemented by an idempotent mathematical operation such as [[inclusive or]] with a bit mask. | |||
When a particular unit of work (i.e., transaction), has the idempotent property, relaxation of the [[ACID properties]] usually required for reliable transaction processing, can be relaxed. | |||
Latest revision as of 13:20, 18 November 2022
In mathematics and computer science idempotence is the property of an operation that repeated application has no further effect.
In mathematics
A binary operation is idempotent if
- for all x:
equivalently, every element is an idempotent element for .
Examples of idempotent binary operations include join and meet in a lattice; union and intersection on sets; disjunction and conjunction in propositional logic.
A unary operation (a function from a set to itself) π is idempotent if it is an idempotent element for function composition, .
In computing
In applications such as databases and transaction processing, idempotent operations are those for which the intended effect is that repeated application should have no effect, such as inserting a record into a file, an element into a set, or sending a message. Implementations must therefore be constructed in such a way that the intended effect is actually carried into practice. For example, messages might have unique sequence numbers with duplicates being discarded on receipt; a set might be implemented as a bit vector, and member insertion implemented by an idempotent mathematical operation such as inclusive or with a bit mask.
When a particular unit of work (i.e., transaction), has the idempotent property, relaxation of the ACID properties usually required for reliable transaction processing, can be relaxed.