Idempotence: Difference between revisions
imported>Howard C. Berkowitz No edit summary |
imported>Richard Pinch (added section In computing from talk page) |
||
| Line 1: | Line 1: | ||
{{subpages}} | {{subpages}} | ||
In [[mathematics]] '''idempotence''' is the property of an | 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 10: | Line 12: | ||
Examples of idempotent binary operations include [[join]] and [[meet]] in a [[lattice (order)|lattice]]; [[union]] and [[intersection]] on [[set (mathematics)|sets]]; [[disjunction]] and [[conjunction]] in [[propositional logic]]. | Examples of idempotent binary operations include [[join]] and [[meet]] in a [[lattice (order)|lattice]]; [[union]] and [[intersection]] on [[set (mathematics)|sets]]; [[disjunction]] and [[conjunction]] in [[propositional logic]]. | ||
A [[unary operation]] (function from a set to itself) π is idempotent if it is an idempotent element for [[function composition]], | 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. | |||
Revision as of 15:47, 23 December 2008
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.